Aby_Lightman-CSDN博客

原创 3013 毕加猪

TaskTask 给定一个图，判断A到B的路径上是否存在负环。SolutionSolution 强连通的好处：把图缩点成DAG（有向无环图），用Bellma¬¬_ford算法判断负点，负点所在的强连通分量一定存在负环。问题转化为：在DAG上，询问A的强联通分量到B的强连通分量的路径上是否存在负强连通分量，等价于询问a点到b到的唯一路径上，是否存在c点，用dfs实现。

2016-11-14 22:21:08 347

原创 1725 天黑请闭眼

方法一：树形dp 如果点(i,f[i])建边，得到基环外向树、相邻两个点不能同时作为杀手，即相邻两个点不能同时取。把环砍掉一条边，变成了树，根据“没有上司的舞会”，定义dp[0][x],表示x不取最大杀手数，dp[1][x]表示x取得最大杀手数。砍的边(a,b)有三种情况：a，b都不取，a取b不取，a不取b取。简化情况2中:a一定不取，b随便去不去，b一定不取，a随便去不去。一定不

2016-11-14 22:19:58 386

原创 D2T3 运输计划

Task 一棵n节点树，m个询问求(a,b)路径距离。改动一条边距为0，求m个询问中最大距离的最小值。Solution 方法一：暴力出奇迹。根据题意“改动一条边”，最朴素的做法是O(n)枚举改动哪一条边,该边只对路径中存在该边的询问有影响。询问可以按照是否包含该边分为两类,ans=max（包含的最大距离-v，不包含的最大距离）。问题转化成：判定边K是否存在于路径Q(a,b)上。如果把a，

2016-11-14 14:56:37 567

原创 D2T2 子串

Task: 从A中取出K个互不重叠的非空子串，顺序链接构成B串的方案数。取出位置不同认为是不同的方案。对于第 1 组数据：1≤n≤500，1≤m≤50，k=1；对于第 2 组至第 3 组数据：1≤n≤500，1≤m≤50，k=2；对于第 4 组至第 5 组数据：1≤n≤500，1≤m≤50，k=m；对于第 1 组至第 7 组数据：1≤n≤500，1≤m≤50，1≤k≤

2016-11-14 13:56:47 325

原创欢迎使用CSDN-markdown编辑器

欢迎使用Markdown编辑器写博客本Markdown编辑器使用StackEdit修改而来，用它写博客，将会带来全新的体验哦：Markdown和扩展Markdown简洁的语法代码块高亮图片链接和图片上传LaTex数学公式UML序列图和流程图离线写博客导入导出Markdown文件丰富的快捷键快捷键加粗 Ctrl + B 斜体 Ctrl + I 引用 Ctrl

2016-11-14 09:34:28 280

原创 1727 洪水拯救计划

Task 一棵n个节点的树，给定K个点。求从每个节点（1到n）出发，确定一个遍历顺序，使得遍历完K个点不返回原点的最小距离。 N<=5e5,K<=n,边权<=1e6Solution 普遍化问题： ① 给定一棵树，从根出发，要求遍历每个叶子节点，最后回到根，求最小距离？距离由每条边贡献，用反证法证明每条边至少遍历2次（一上一下）。最小距离=2*边权总和。② 给定一棵树，从根出发

2016-11-12 22:14:15 342

原创 2015

Task D1T3 斗地主共T组，每组n张牌，大小关系大王>小王>K>*>2>1. 花色不对牌大小产生影响，给定出牌方式，求最小出牌次数。数据范围: Solution30%的数据 n<=4 所有的情况都在“三带二”的前面。如果cnt最大值<=2,表明每种牌都单独打（单张或对子），此时最优解=权值种类数。如果cnt>=3，如果存在另一张牌，就可以被带打，只需要1次。1

2016-11-12 16:14:22 275

原创 3031 序列

Task 序列有N个数，m种变化(a,x) 表示A[a]可以变成x，求最长子序列满足任意1个变化或都不变化，子序列都不降。 N<=1e5+3Solution 子序列是由一个一个数构成的，且相邻两数之间满足 Mi[i]>=v[j],v[i]>=mx[i],i>jMi[i]>=v[j],v[i]>=mx[i],i>j由“最长子序列”和“不降”，我们想到了LIS，普通的LIS转移： A[i]>A

2016-11-12 07:34:22 326

原创 2018 有志气博士来种草

Task N节点的树，m个操作分2种： ① (x,y)路径上的各边的值+1 ② 询问边（x，y）的值。Solution 方法一：树链剖分树链剖分使用于树上的区间更新或者区间询问，把链重新编号，加入线段树中。方法二：刷漆法问题属于区间更新，单点求值。如果在序列上，可以用刷漆法+前缀和得到每个点的权值。在树上可以转化成两段区间，即(x,lca),(y,lca)同样的左端

2016-11-11 22:33:27 331

原创 3130 排序

Task 给出1-n的全排列，m次操作分为两种： ① (0,l,r)将区间[l,r]升序排列 ② (1,l,r)将区间[l,r]降序排列。 n，m<=1e5Solution 6秒的时限，真是个暴力的好时机用sort函数sort(A+l,A+r+1,cmp)可以对区间[l,r]升序或者降序排列，这样就有80分了。但是本人粗鄙，写成了sort(A+l+1,A+r+1)，居然还有

2016-11-11 20:46:06 288

原创 3129 树

3129 树 Task 给定根为1，n个节点的树。有2种操作： ① 对x节点打标记 ② 询问x最新一个打了标记的祖先 N,Q<=1e5 1在初始时已被标记。Solution 暴力出奇迹暴力一：O(1)打标记，一步步往上走，找到第一个打标记的祖先，只花了32MS。暴力二：O(1)询问，打标记时dfs子树更新答案+剪枝：遇到某个子树已经打了标记，就不往下走了。并查集由

2016-11-11 20:43:38 233

原创 3086 区域发展

Task 1-n个人，等级从高到低，属于1-m地，除了1外每个人都有个直接导师，等级都比它高。q个询问，A，B(地区)，输出有多少关系x∈A，y∈B，x是y的导师。 x是y的导师：当且仅当x是y的直接导师或是x是y的直接导师的导师。 N<=2e5,m<=25000,q<=2e5Solution 分块决策树：如果把i和i的直接导师连边，就构成一棵树。因为除了1外每个i都有一个父亲节点，而且

2016-11-10 13:54:34 297

原创 3085 蚱蜢

3085 蚱蜢 Task n*n的矩阵，初始位置在x，y，按照以下要求遍历: 下一步为x1,y1 ① |x-x1|=1,|y-y1|>1或|y-y1|=1,|x-x1|>1 ② Val[x1][y1]>val[x][y] 求最多遍历的位置个数。 50% n<=100 80% n<=1000 100% n<=1500,val<=1e6Solution 观察条件②每个点向权值

2016-11-10 11:02:36 487

原创 3084 车库

Task N个停车位，m辆车。每个时刻来一辆或者走一辆。车到达时，有多个停车位选编号最小的，如果没有停车位，就等待。车走时，若有多辆车等待，先到先得空车位。每辆车花的代价=停车位i的价格v*车j的重量w。求所有车的总代价。 N<=100,m<=200,v<=100,w<=10000Solution 此题与3081排队大同小异。考察了堆和队列的应用。如果当前来了一辆车，那么它取的空车

2016-11-10 10:12:13 300

原创 2014

2014 D1T2 联合权值 Task N节点树，每个点有权值val i,定义有序点对(u,v)距离为2时，存在联合权值为val[u]*val[v]。求最大的联合权值，所有点对联合权值之和%10007 N<=2e5,val<=1e4 (u,v) (v,u)是2组不同的符合条件的点对。 Solution 暴力枚举用floyed或bfs预处理任意两点之间的距离。O(n^2)找出所

2016-11-07 16:52:56 208

原创 2013

2013D2T1 积木赛 Task n个初始为0的数，求最少的操作次数变成目标数组。一次操作：选择区间[ l , r ]内所有数+1 n<=1e5,0<=hi<=1e4Solution 贪心：为使操作次数最少，每次选的区间应尽可能的大。因此每次贪心选一段最长都是正数的区间，区间内数-1.最值可以用堆维护。如果当前选出的区间操作完后不含0，那么下一次还是会选择这个区间，为减少操作

2016-11-04 07:18:26 248

原创 2012

2012D2T2 教室 Task 有n个正数，m次操作，每次将[ li, ri ]区间所有值-ci，求操作后第一次出现负数的操作编号。 n,m<=1e6,ci<=1e9Solution 方法一：发现结果是单调的，每个数不可能变大，只可能随操作次数增多越来越小。如果二分操作次数，就把问题转化成一个判定问题：这个区间是否会出现负数？对区间加减可以利用线段树来维护区间最小值判断是否有负

2016-11-02 21:25:30 257

原创 2011

2011D1T2客栈 Task N个点，两个属性c，v表示颜色和花费，求区间[ l, r ]满足l，r颜色相同，且这个区间最小值<=p的个数N<=2e5,c<=50,p<=100Solution 如果枚举两个端点，复杂度是O(n^2)，用前缀和询问这个区间是否有<=p的数，来判断这个区间是否可行。区间问题常见的优化方法：枚举右端点，找左端点。因为颜色的个数很小，因此可以按颜色分类，放入

2016-11-02 21:20:14 294

原创 3066 快餐店

Task 有n个点，n条边，任意两点相互连通。在任意边的任意位置可设置A点，求A到n个点的距离中的最大值的最小值。N<=1e5,边长l<=1e9Solution 最后的答案一定在某一条边上，可以终态枚举。到每个点的距离是最短路径的问题，可以用dijksra来处理。但是怎么确定应该放在这条边的哪个位置呢？边可以分类为链边，环边，如果在环边上dijkstra会怎么样呢？

2016-10-30 22:36:07 357

原创 3065 交叉匹配

Task 给定两行数，求这两行数的最大交叉匹配数。交叉匹配的原则： ① 上下两行，只有值相同的才能连线匹配。 ② 任意一条a匹配线有且仅有一条b匹配线和它相交，且a，b数值不同。左边是合法的，而右边是不合法的。 N<=2000Solution 观察到，如果a，b上下相交，那么两个红色箭头范围内的不可能再有匹配线，否则就不满足②条件。那么一対匹配会把区间分割出独立的一段，类

2016-10-30 22:25:05 498

原创 2719 sheldon数

Task 转化为2进制形如ABABAB…。A，B分别代表1，0，长度各自相同的数为sheldon数，且最高位肯定是1。求它在[ l , r ]区间内的个数。0<=L<=R<2^63Solution 70分枚举•十进制暴力求L,R区间内的数是否符合这个条件。100分终态枚举•二进制求区间内的数可以由前缀思想来处理。 Cal( l, r )=Cal( 0, R )-Cal( 0, L-

2016-10-30 22:21:47 401

原创 3081 排队

Task 一棵n个节点的树，每个节点容纳1个人。1是入口，有m轮操作，共2种操作。 1. 加入x个人，求最后一个人到达的节点。规则 ①只要有空位就往下走 ② 多个空位，选编号最小的 2. 移走x号节点上的人，x上面的人都落下来，求落下来的个数。Solution 规则的特征是尽可能先往左边走，再往右边走，最后是根，特征与后序遍历相似。因此可以用后序遍历确定每个节点的优先级，优

2016-10-26 22:24:41 264

原创 3080 道路规划

Task 给两行数1-n的序列，相同的数连线，求最大的集合满足集合中任意两个数都相交。Solution 比赛的时候想歪了，认为它求最大独立集。于是把任意不相交的两个数之间连边，求出的一个最大独立集必定是任意两个都相交的。但是！但是！匈牙利算法是用来求二分图的最大独立集的，但是构建的图并不一定是二分图。正解=反向求LIS。如果x，y是相交的，观察第二行，发现符合逆序对的概念，如果这个集合中

2016-10-26 22:17:00 404

原创 3079 挖金矿

Task N*m的矩形，每行取[ 1,m ]个数，求取出的最大平均值。H*n<=1e5,a[i][j]∈[1,1e9]Solution 二分的功能: ① 有序数组查找某值 ② 假定解，判可行 ③ 最大化最小值 ④ 最大化平均值本题用2，4个功能。sum1+sum2+*+sumn/num1+num2+***numn>=k (sum1-k*num1)+(sum2-k*n

2016-10-26 22:11:03 364

原创 3078 仓库

Task 给n个节点中有K个入口的树，求有多少个1~n的排列顺序，顺序遍历每个节点时，都存在都入口到该节点的路径，满足路径上不包含之前遍历过的点。答案mod 1e9+7。 Solution 1. K=1。在树上求方案数，容易想到是树形dp。以入口S作为根，发现遍历节点x之前，x的子树必须都已经被遍历过了，dp[ i ]表示，以i为根的子树都已经被遍历的方案数。X子树对应的序列为儿

2016-10-26 17:00:40 258

原创 3077 删边旅行

Task n个点m条边的无向联通图，求删除每一条边后，任意两点间的距离和。数据范围：n<=100个节点,m<=2000条边，边权为1.Solution 60分O( mn ( n+m ) )暴力bfs 由边权为1让人联想到bfs。按照题意模拟的暴力思路，删除每一条边O( m )，枚举一个源点O( n ),跑bfs O( n+m )，得该状态下，该点对答案的贡献。可以先判断是否是重边或自环

2016-10-26 16:44:59 448

原创 3076 翻翻乐

Task 翻转01矩阵，使对任意一个点，周围点的异或和为0.每个点对应一个代价，有的点不能翻转。求最小代价。数据范围：矩阵的大小为n*n,n<=16,如果不可能完成输出-1.Solution 终态枚举对于翻转问题，同一个格子翻转2次会恢复原状。翻转格子集合是相同时，次序是不重要的。不妨先假定第一行的01状态，那么第二行的状态是是由上一行唯一决定的，因此整个图的状态和代价都可以计算。

2016-10-26 16:41:53 509

原创 3075 走捷径

求在树上长为K的最短边数。 N<=2e5,K<=1e6 对70%数据k<=10040分O(n^2)终态枚举。枚举根，dfs访问到每个点的距离，可以最优性减枝。70分O(n*K)树形dp。定义dp[i][j]为到i距离为j的最短边数，考虑树上传过i的路径时，在i子树下选2个节点x，y，要求他们不在i的同一棵子树里，这可以用先访问一遍子树求答案，再访问一遍子树记录dp值来解决。转移的方程：M

2016-10-08 15:18:56 530 1

Aby_Lightman的博客