cjb-poi2010

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 * 总结： 2010年的题里好多性质到现在都已经被出烂了，比如那个Σfloor(n/k)(1<=k<=n)为nlogn级别。除了煞笔题和板子题，说其中一部分题吧：Railway是先转化模型，然后靠数据结构保证算法复杂度瓶颈的经典题。然后有三道单调队列相关的题啊(Blocks,Frog和Pilots)，其中Frog里的倍增写法蛮漂亮的(卡内存有理有据)。Bridges是经典的混合图求欧拉回路没啥好说的。非常喜欢Teleportation这个构造题，可惜和sub讨论了之后不太能扩展。Monotonicity提醒我们经常要思考分步最优和全局最优的关系，不仅能指向可能的贪心算法，也有可能优化dp状态。Lamp看起来非常Final啊...想知道大佬们写要多久...Ones这个题有点神，求教....


 * Guilds
  * 题意：询问一张图是否能够给所有点分配无、黑、白色且任何点都与最近白(黑)距离<=1，输出方案，n<=200000,m<=500000。
  * 解法：对原图任意生成森林进行黑白染色即满足条件，注意特判孤立点是唯一一种无解的情况，复杂度O(n)。
  * 代码：[wiki:cjb-poi2010guilds Code]

 * Railway
  * 题意：给定一个排列的入栈序列，可以选择入1/2号栈，要求使得出站顺序为升序，输出每个元素入的栈编号，n<=200000。
  * 解法：NOIP2008双栈排序升级版。本质上，考虑i<j<k且a[k]<a[i]<a[j]，则i和j一定不能属于同一个栈(与出栈顺序无关)，NOIP2008双栈排序可以直接n^2^枚举后二分图染色判定，但是这题需要更优秀的复杂度，所以考虑优化遍历方式。我们对每个点只寻找且染色一次，染色结束后再模拟一次检查是否合法，就能保证复杂度了。设b[i]=min(a[i..n])，则若b[j]<a[i]<a[j]，则i和j不能属于同一个栈。我们同时定义c[i]表示最大的j满足b[j]<i，这步可以线性预处理。则i需要向位置于[i+1,c[a[i]]]之间所有满足a[j]>a[i]的j连边，同时考虑另一侧，还需要向值在[b[i]+1,a[i]-1]里所有位置<i的j连边。于是我们建两棵线段树，第一棵按位置维护a的最大值，第二棵按a维护位置的最小值，取出一个点就将其从两棵树中删去即可，复杂度O(nlogn)。
  * 代码：[wiki:cjb-poi2010railway Code]

 * Beads
  * 题意：要求将字符串按k个划分，不足部分去掉，求最优的k使得不同子串最多(若rev(a)=b，则也只算一次)，n<=200000。
  * 解法：经典结论是Σfloor(n/k)(1<=k<=n)为nlogn级别，所以暴力枚举就好，塞正反哈希值较小的那个进set去重，复杂度O(nlog^2^n)。
  * 代码：[wiki:cjb-poi2010beads Code]

 * Divine Divisor
  * 题意：求n个1e18范围的数乘积结果的Divine Divisor，定义为包含幂次最高的因子，问最高次数和这样的因子个数，n<=600。
  * 解法：显然将n个数分解之后，统计下最高次数和这样数字个数cnt，第二个答案就是1<<cnt。所以我们尝试用zimpha自称跑很快的板子去爆艹，结果oj不支持int128，将某定义改成ull后就wa了三个点(bzoj上也没有int128，没救了，看起来速度是可以的)...接下来我们来讲正常做法：首先用1e6以内的素数去爆所有数字，这样剩下来要么是1，要么是p，要么是p^2^，要么是pq，我们先把p和p^2^爆出来，需要用到Miller_Rabin，之后剩下的都是pq了，这部分我们还得用之前判定的p和sqrt(p^2^)再筛一遍，这样筛会把另一半也筛出来，所以p和n/p都要计数。最后剩下的pq，我们相互之间求下gcd，再试图分解一次，同样也会把另一半筛出来。剩下的如果还不是1，那么就是pq，且p和q都没有出现过，直接统计即可。这题tm 1<<cnt还要写个简易高精度，ugly.jpg。
  * 代码：[wiki:cjb-poi2010divinedivisor1 Code1@ZimphaLibrary]，[wiki:cjb-poi2010divinedivisor2 Code2]

 * Intelligence Test
  * 题意：给出长串，问你q个短串是否是子序列，n<=1e7,a[i]<=1e7,Σlen<=1e7。
  * 解法：带log做法满天飞，感觉常数最小的可能是对于每个元素开一个vector，塞长串对应位置进去，然后挨个依次bound一下，不知道能不能过。其实复杂度可以很轻易地变成O(Σlen)，我们还是对每个元素开一个vector，存当前有哪些人匹配到了这个字符在等，顺着扫一遍，每次从对应vector取出来，找到下一位对应的位置塞回进去，就能同时对所有询问进行匹配了。所以有在线的线性做法嘛？
  * 代码：[wiki:cjb-poi2010intelligencetest Code]

 * Antisymmetry
  * 题意：求01串里反对称子串个数(flip之后reverse)，n<=500000。
  * 解法：对正串和反串各hash一次，枚举中心，二分求出半径累计答案是最脑残的做法O(nlogn)。然而其实可以改造下manacher去做，把0标为0，1标为2，插入字符标为1，判定时用相加是否为2判定，最后枚举偶数中心点累计答案即可，效率同manacher，O(n)。
  * 代码：[wiki:cjb-poi2010antisymmetry Code]

 * Hamsters
  * 题意：给出n个字符串，问你出现k次字符串的最短字符串长度，保证没有包含，n<=200，k<=1e9，Σlen<=1e5。
  * 解法：处理出d[i][j]表示字符串i之后最少要接多少个字符才能接出一个j来，暴力dp很显然f[i][j]=min(f[i-1][k]+d[k][j])，d这个矩阵是可以类似于快速幂先行累计的，之后再接上第一段统计答案即可，注意k=1的情况，答案显然是long long级别的。
  * 代码：[wiki:cjb-poi2010hamsters Code]

 * Blocks
  * 题意：给出n个正整数，m组询问，给出一个正整数k，现在可以进行如下操作：每次选择一个大于k的正整数a[i]，将a[i]减去1，选择a[i-1]或a[i+1]中的一个加上1。任意数量操作之后，问最大能够选出多长的一个连续子序列，使得这个子序列的每个数都不小于k，n<=1000000,m<=50。
  * 解法：问题可以转化成询问最长的平均数>=k的区间，对于每个询问将每个数字减去k，变成平均数>=0处理，预处理前缀和，则求max(r-l)且pre[r]-pre[l]>=0。开个栈，每次进栈当且仅当pre[i]<pre[top]，这些为有用的左端点，之后右端点从n倒着枚举，每次弹掉非法的和能统计进答案的左端点并更新答案。总复杂度为O(mn)。
  * 代码：[wiki:cjb-poi2010blocks Code]

 * Sheep
  * 题意：将n个点的凸多边形划成多个三角形，另有m个点，使得每个三角形内的点的个数为偶数。并要求划分线上不能有点，n<=600,m<=20000，输出方案数mod MOD。
  * 解法：对于凸多边形上的顶点i,j，当且仅当两点之间的连线没有经过某只羊，并且两侧的羊的个数为偶数（显然如果分出奇数，对于剩下的小凸多边形就不可能满足题意）时，连线。由于n<=600，所以可以暴力枚举起点，极角排序后依次枚举其他点是否能进行连边，同时累计点的个数，就能预处理出i和j是否能连线。之后f[l][r]表示顶点l..r围成的多边形方法个数，f[l][r]=Σf[l][k]*f[k][r](l<k<r,cut[l][k] && cut[k][j])，注意初始f[l][l+1](一条边)方案数为1。复杂度是(n*mlogm+n^3^)。
  * 代码：[wiki:cjb-poi2010sheep Code]

 * Teleportation
  * 题意：给一张n个点m条边的无向图，可以往里面加任意边(非重边非自环)，要求维持1到2的最短路径>=5，n<=40000,m<=1000000。
  * 解法：构造题，显然最后可以将图除1和2之外划分成A,B,C,D四个团，相邻团之间任意点皆连边，1和A连边，D和2连边。考虑原图中所有与1连边的点组成A集合，所有与2连边的点组成D集合，显然剩下的点不放进A或者D集合一定更优，则A和D集合确定。显然所有与A集合连边的点都要放进B集合，所有与D集合连边的点都要放进C集合。剩下的点既可放B也可放C，则贪心考虑若A集合点数大于D集合点数，就把这部分点放B，反之放C。统计答案既可，复杂度为O(m)。
  * 代码：[wiki:cjb-poi2010teleportation Code]

 * Monotonicity
  * 题意：给出一个长度n的序列，问最长的子序列满足相邻元素关系的符号序列为给定长度为k的符号序列的循环，n,k<=500000,a[i]<=1000000。
  * 解法：Monotonicity是Monotonicity 2的削弱版，k<=100，可将k放进dp状态中即可自然转移，我们直接考虑n,k<=500000的版本。因为可以证明，所有最优解均可转化成一个分步最优解，因此我们可以只考虑局部最优解的转移，所以令f[i]表示以i结尾的最长子序列，这样我们可以得到下一位所需的符号，分三种符号符号建线段树存对应a[i]的最大f[i]值，即可优化转移效率，更新之后插入对应线段树即可(实际上等号的情况可以直接数组维护，但不影响复杂度)，效率为O(nlog(1000000))。此题关键在于分步最优解等价于最优解，另一个浅显的有类似性质的模型就是最长上升子序列。
  * 代码：[wiki:cjb-poi2010monotonicity Code]
  * 其他：[https://blog.csdn.net/kanosword/article/details/52735717  性质证明]

 * The Minima Game
  * 题意：给出n个正整数a[i]，AB两个人轮流取数，A先取。每次可以取任意多个数，直到n个数都被取走。每次获得的得分为取的数中的最小值，A和B的策略都是尽可能使得自己的得分减去对手的得分更大，求最终A的得分减去B的得分为多少，a[i]<=10^9^,n<=10^6^。
  * 解法：考虑最优策略下，每个人面对当前局势肯定都是把前k大的数字取完，f[i]表示面对局势为前i小的数字时先手最优策略下净胜分，显然转移为f[i]=max(a[j]-f[j-1])(1<=j<=i)，因为从i取到j，先手获得a[j]分，后手转先手，最优获得分数为f[j-1]，则实际得分为a[j]-f[j-1]，观察下这个dp方程，f[i]比起f[i-1]只多了一个a[i]-f[i-1]的选择，因此转移变成f[i]=max(f[i-1],a[i]-f[i-1])，效率为O(n)。
  * 代码：[wiki:cjb-poi2010theminimagame Code]

 * Lamp
  * 题意：两幢大楼中间相隔10米，然后B大楼有n面矩形玻璃，C大楼有m面矩形玻璃，光从C大楼地步(0,0)向C照，只有玻璃能反射光线，可以多次反射，遵循入射角等于出射角，问B大楼有几面玻璃被光照到，n,m<=600,-1000<=x[i][1],x[i][2]<=1000,0<=y[i][1],y[i][2]<=1000。
  * 解法：不太会做，先放一个民间解法hold着：通过画图可以发现如果反射p*2^k^次房间到达的窗户，2^k^次也能到达。枚举2的次幂，设x=2^k^，那么光线轨迹是(x,y)->(2x,2y)->(3x,3y)，由于奇数次在左侧，偶数次在右侧。那么将那些矩形分别缩小1/2n或1/2n+1，放到一个平面上。'''假如有k个矩形有公共点(此处存疑未理解)'''，则这意味着一次可行的反射，这个问题可以用线段树来解决。
  * 代码：[wiki:cjb-poi2010lamp Code]

 * Frog
  * 题意：有n个离岸距离逐渐增加的石头，距离岸距离为a[i]，上面都有一只青蛙，青蛙可以在石头间跳，每次会跳到离自己第k远的石头(相同则跳到离岸较近)，问每只青蛙在m步之后所在石头编号，n<=10^6^,a[i],m<=10^18^。
  * 解法：首先要对于每个石头预处理出下一步跳跃的地方，考虑当前位置为i，那么维护一个合法区间[l,l+k]，下一步跳跃的地方一定是区间端点之一，如果存在dis(r+1..i)比dis(l..i)要小的话，说明l已经不优，因此区间左右端点都右移，显然随着i增大，左右端点不减，所以这部分是O(n)的。处理出之后剩下的部分就是倍增了，这部分倍增有比较优美的写法，可以写成类似快速幂一样，同时计算所有位置的答案且维护所有位置跳2^p^步后的位置，这样还大大节省了空间和减小了常数(空间或常数都似乎会被卡?)，总效率为O(nlogm)。
  * 代码：[wiki:cjb-poi2010frog Code]

 * Ones
  * 题意：对于一个01串，其第一个1或者最后一个1如果不和别的1相邻，称为UFO，如10001010有两个UFO，1101011000没有UFO。再定义sks(n)为从1到n所有数字的二进制表示串中UFO数量之和，如sks(5)=5,sks(64)=59,sks(128)=122。之后定义REP(x)为x在二进制表示下，按相同数字拆分成block之后block大小依次组成的序列，如REP(460288)=REP(1110000011000000000)=(3,5,2,9)。下面给出REP(n)，要求输出REP(sks(n))。REP(n)长度k<=10^6^,元素大小a[i]<=10^9^，0<n<2^1000000000^。
  * 解法：'''这题听说代码最短5K，而且真不会啊QAQ 也找不到做法，留给智慧的sub吧....'''
  * 代码：[wiki:cjb-poi2010ones Code]

 * Bridges
  * 题意：给出一张n个点m条边的连通无向图，但是每一条边正反的边权w不同，求从1出发，经过所有点和所有边回到1的路径，并且路径上边权最大值最小，n<=1000,m<=2000,1<=w<=1000。
  * 解法：二分答案，判断是否存在边肯定走不了之后，剩下部分就变成了混合图求欧拉回路。关键在于给无向边定向，首先先随便定个方向，然后因为有向图存在欧拉回路的充分必要条件是所有点入度等于出度，所以此刻若存在一些不平衡点，则考虑反转方向去平衡。如果有点的入度与出度奇偶性不同，则永远无法配平，则无解。反之S向所有出度>入度的点连(出度-入度)/2的边，流量为1，所有出度<入度的点向T连(入度-出度)/2的边，原图所有定向为(x,y)的无向边连一条x到y流量为1的边。跑最大流，若满流则有解。打印答案的时候根据是否满流给原图定向，跑有向图欧拉回路输出答案即可，效率为O(dinic*log(1000))。
  * 代码：[wiki:cjb-poi2010bridges Code]

 * Pilots
  * 题意：给出一个limit值和长度为n的正整数序列a[i]，求最长连续子序列长度且最大最小值之差<=limit，n<=3*10^6^,limit,a[i]<=10^9^。
  * 解法：显然随着r增大，l显然不减，分别维护两个单调队列维护最大值和最小值，每次先插入两个队列队尾，然后拿两个队头作差，如果不符合就弹出下标较小的队头，重复直至合法。注意l的初始值不要忘记赋，复杂度O(n)。
  * 代码：[wiki:cjb-poi2010pilots Code]
  • 总结： 2010年的题里好多性质到现在都已经被出烂了，比如那个Σfloor(n/k)(1<=k<=n)为nlogn级别。除了煞笔题和板子题，说其中一部分题吧：Railway是先转化模型，然后靠数据结构保证算法复杂度瓶颈的经典题。然后有三道单调队列相关的题啊(Blocks,Frog和Pilots)，其中Frog里的倍增写法蛮漂亮的(卡内存有理有据)。Bridges是经典的混合图求欧拉回路没啥好说的。非常喜欢Teleportation这个构造题，可惜和sub讨论了之后不太能扩展。Monotonicity提醒我们经常要思考分步最优和全局最优的关系，不仅能指向可能的贪心算法，也有可能优化dp状态。Lamp看起来非常Final啊...想知道大佬们写要多久...Ones这个题有点神，求教....
  • Guilds
    • 题意：询问一张图是否能够给所有点分配无、黑、白色且任何点都与最近白(黑)距离<=1，输出方案，n<=200000,m<=500000。
    • 解法：对原图任意生成森林进行黑白染色即满足条件，注意特判孤立点是唯一一种无解的情况，复杂度O(n)。
    • 代码：Code
  • Railway
    • 题意：给定一个排列的入栈序列，可以选择入1/2号栈，要求使得出站顺序为升序，输出每个元素入的栈编号，n<=200000。
    • 解法：NOIP2008双栈排序升级版。本质上，考虑i2枚举后二分图染色判定，但是这题需要更优秀的复杂度，所以考虑优化遍历方式。我们对每个点只寻找且染色一次，染色结束后再模拟一次检查是否合法，就能保证复杂度了。设b[i]=min(a[i..n])，则若b[j]a[i]的j连边，同时考虑另一侧，还需要向值在[b[i]+1,a[i]-1]里所有位置
    • 代码：Code
  • Beads
    • 题意：要求将字符串按k个划分，不足部分去掉，求最优的k使得不同子串最多(若rev(a)=b，则也只算一次)，n<=200000。
    • 解法：经典结论是Σfloor(n/k)(1<=k<=n)为nlogn级别，所以暴力枚举就好，塞正反哈希值较小的那个进set去重，复杂度O(nlog2n)。
    • 代码：Code
  • Divine Divisor
    • 题意：求n个1e18范围的数乘积结果的Divine Divisor，定义为包含幂次最高的因子，问最高次数和这样的因子个数，n<=600。
    • 解法：显然将n个数分解之后，统计下最高次数和这样数字个数cnt，第二个答案就是1<2，要么是pq，我们先把p和p2爆出来，需要用到Miller_Rabin，之后剩下的都是pq了，这部分我们还得用之前判定的p和sqrt(p2)再筛一遍，这样筛会把另一半也筛出来，所以p和n/p都要计数。最后剩下的pq，我们相互之间求下gcd，再试图分解一次，同样也会把另一半筛出来。剩下的如果还不是1，那么就是pq，且p和q都没有出现过，直接统计即可。这题tm 1<
    • 代码：Code1@ZimphaLibrary，Code2
  • Intelligence Test
    • 题意：给出长串，问你q个短串是否是子序列，n<=1e7,a[i]<=1e7,Σlen<=1e7。
    • 解法：带log做法满天飞，感觉常数最小的可能是对于每个元素开一个vector，塞长串对应位置进去，然后挨个依次bound一下，不知道能不能过。其实复杂度可以很轻易地变成O(Σlen)，我们还是对每个元素开一个vector，存当前有哪些人匹配到了这个字符在等，顺着扫一遍，每次从对应vector取出来，找到下一位对应的位置塞回进去，就能同时对所有询问进行匹配了。所以有在线的线性做法嘛？
    • 代码：Code
  • Antisymmetry
    • 题意：求01串里反对称子串个数(flip之后reverse)，n<=500000。
    • 解法：对正串和反串各hash一次，枚举中心，二分求出半径累计答案是最脑残的做法O(nlogn)。然而其实可以改造下manacher去做，把0标为0，1标为2，插入字符标为1，判定时用相加是否为2判定，最后枚举偶数中心点累计答案即可，效率同manacher，O(n)。
    • 代码：Code
  • Hamsters
    • 题意：给出n个字符串，问你出现k次字符串的最短字符串长度，保证没有包含，n<=200，k<=1e9，Σlen<=1e5。
    • 解法：处理出d[i][j]表示字符串i之后最少要接多少个字符才能接出一个j来，暴力dp很显然f[i][j]=min(f[i-1][k]+d[k][j])，d这个矩阵是可以类似于快速幂先行累计的，之后再接上第一段统计答案即可，注意k=1的情况，答案显然是long long级别的。
    • 代码：Code
  • Blocks
    • 题意：给出n个正整数，m组询问，给出一个正整数k，现在可以进行如下操作：每次选择一个大于k的正整数a[i]，将a[i]减去1，选择a[i-1]或a[i+1]中的一个加上1。任意数量操作之后，问最大能够选出多长的一个连续子序列，使得这个子序列的每个数都不小于k，n<=1000000,m<=50。
    • 解法：问题可以转化成询问最长的平均数>=k的区间，对于每个询问将每个数字减去k，变成平均数>=0处理，预处理前缀和，则求max(r-l)且pre[r]-pre[l]>=0。开个栈，每次进栈当且仅当pre[i]
    • 代码：Code
  • Sheep
    • 题意：将n个点的凸多边形划成多个三角形，另有m个点，使得每个三角形内的点的个数为偶数。并要求划分线上不能有点，n<=600,m<=20000，输出方案数mod MOD。
    • 解法：对于凸多边形上的顶点i,j，当且仅当两点之间的连线没有经过某只羊，并且两侧的羊的个数为偶数（显然如果分出奇数，对于剩下的小凸多边形就不可能满足题意）时，连线。由于n<=600，所以可以暴力枚举起点，极角排序后依次枚举其他点是否能进行连边，同时累计点的个数，就能预处理出i和j是否能连线。之后f[l][r]表示顶点l..r围成的多边形方法个数，f[l][r]=Σf[l][k]*f[k][r](l3)。
    • 代码：Code
  • Teleportation
    • 题意：给一张n个点m条边的无向图，可以往里面加任意边(非重边非自环)，要求维持1到2的最短路径>=5，n<=40000,m<=1000000。
    • 解法：构造题，显然最后可以将图除1和2之外划分成A,B,C,D四个团，相邻团之间任意点皆连边，1和A连边，D和2连边。考虑原图中所有与1连边的点组成A集合，所有与2连边的点组成D集合，显然剩下的点不放进A或者D集合一定更优，则A和D集合确定。显然所有与A集合连边的点都要放进B集合，所有与D集合连边的点都要放进C集合。剩下的点既可放B也可放C，则贪心考虑若A集合点数大于D集合点数，就把这部分点放B，反之放C。统计答案既可，复杂度为O(m)。
    • 代码：Code
  • Monotonicity
    • 题意：给出一个长度n的序列，问最长的子序列满足相邻元素关系的符号序列为给定长度为k的符号序列的循环，n,k<=500000,a[i]<=1000000。
    • 解法：Monotonicity是Monotonicity 2的削弱版，k<=100，可将k放进dp状态中即可自然转移，我们直接考虑n,k<=500000的版本。因为可以证明，所有最优解均可转化成一个分步最优解，因此我们可以只考虑局部最优解的转移，所以令f[i]表示以i结尾的最长子序列，这样我们可以得到下一位所需的符号，分三种符号符号建线段树存对应a[i]的最大f[i]值，即可优化转移效率，更新之后插入对应线段树即可(实际上等号的情况可以直接数组维护，但不影响复杂度)，效率为O(nlog(1000000))。此题关键在于分步最优解等价于最优解，另一个浅显的有类似性质的模型就是最长上升子序列。
    • 代码：Code
    • 其他： 性质证明
  • The Minima Game
    • 题意：给出n个正整数a[i]，AB两个人轮流取数，A先取。每次可以取任意多个数，直到n个数都被取走。每次获得的得分为取的数中的最小值，A和B的策略都是尽可能使得自己的得分减去对手的得分更大，求最终A的得分减去B的得分为多少，a[i]<=109,n<=106。
    • 解法：考虑最优策略下，每个人面对当前局势肯定都是把前k大的数字取完，f[i]表示面对局势为前i小的数字时先手最优策略下净胜分，显然转移为f[i]=max(a[j]-f[j-1])(1<=j<=i)，因为从i取到j，先手获得a[j]分，后手转先手，最优获得分数为f[j-1]，则实际得分为a[j]-f[j-1]，观察下这个dp方程，f[i]比起f[i-1]只多了一个a[i]-f[i-1]的选择，因此转移变成f[i]=max(f[i-1],a[i]-f[i-1])，效率为O(n)。
    • 代码：Code
  • Lamp
    • 题意：两幢大楼中间相隔10米，然后B大楼有n面矩形玻璃，C大楼有m面矩形玻璃，光从C大楼地步(0,0)向C照，只有玻璃能反射光线，可以多次反射，遵循入射角等于出射角，问B大楼有几面玻璃被光照到，n,m<=600,-1000<=x[i][1],x[i][2]<=1000,0<=y[i][1],y[i][2]<=1000。
    • 解法：不太会做，先放一个民间解法hold着：通过画图可以发现如果反射p*2k次房间到达的窗户，2k次也能到达。枚举2的次幂，设x=2k，那么光线轨迹是(x,y)->(2x,2y)->(3x,3y)，由于奇数次在左侧，偶数次在右侧。那么将那些矩形分别缩小1/2n或1/2n+1，放到一个平面上。假如有k个矩形有公共点(此处存疑未理解)，则这意味着一次可行的反射，这个问题可以用线段树来解决。
    • 代码：Code
  • Frog
    • 题意：有n个离岸距离逐渐增加的石头，距离岸距离为a[i]，上面都有一只青蛙，青蛙可以在石头间跳，每次会跳到离自己第k远的石头(相同则跳到离岸较近)，问每只青蛙在m步之后所在石头编号，n<=106,a[i],m<=1018。
    • 解法：首先要对于每个石头预处理出下一步跳跃的地方，考虑当前位置为i，那么维护一个合法区间[l,l+k]，下一步跳跃的地方一定是区间端点之一，如果存在dis(r+1..i)比dis(l..i)要小的话，说明l已经不优，因此区间左右端点都右移，显然随着i增大，左右端点不减，所以这部分是O(n)的。处理出之后剩下的部分就是倍增了，这部分倍增有比较优美的写法，可以写成类似快速幂一样，同时计算所有位置的答案且维护所有位置跳2p步后的位置，这样还大大节省了空间和减小了常数(空间或常数都似乎会被卡?)，总效率为O(nlogm)。
    • 代码：Code
  • Ones
    • 题意：对于一个01串，其第一个1或者最后一个1如果不和别的1相邻，称为UFO，如10001010有两个UFO，1101011000没有UFO。再定义sks(n)为从1到n所有数字的二进制表示串中UFO数量之和，如sks(5)=5,sks(64)=59,sks(128)=122。之后定义REP(x)为x在二进制表示下，按相同数字拆分成block之后block大小依次组成的序列，如REP(460288)=REP(1110000011000000000)=(3,5,2,9)。下面给出REP(n)，要求输出REP(sks(n))。REP(n)长度k<=106,元素大小a[i]<=109，01000000000。
    • 解法：这题听说代码最短5K，而且真不会啊QAQ 也找不到做法，留给智慧的sub吧....
    • 代码：Code
  • Bridges
    • 题意：给出一张n个点m条边的连通无向图，但是每一条边正反的边权w不同，求从1出发，经过所有点和所有边回到1的路径，并且路径上边权最大值最小，n<=1000,m<=2000,1<=w<=1000。
    • 解法：二分答案，判断是否存在边肯定走不了之后，剩下部分就变成了混合图求欧拉回路。关键在于给无向边定向，首先先随便定个方向，然后因为有向图存在欧拉回路的充分必要条件是所有点入度等于出度，所以此刻若存在一些不平衡点，则考虑反转方向去平衡。如果有点的入度与出度奇偶性不同，则永远无法配平，则无解。反之S向所有出度>入度的点连(出度-入度)/2的边，流量为1，所有出度<入度的点向T连(入度-出度)/2的边，原图所有定向为(x,y)的无向边连一条x到y流量为1的边。跑最大流，若满流则有解。打印答案的时候根据是否满流给原图定向，跑有向图欧拉回路输出答案即可，效率为O(dinic*log(1000))。
    • 代码：Code
  • Pilots
    • 题意：给出一个limit值和长度为n的正整数序列a[i]，求最长连续子序列长度且最大最小值之差<=limit，n<=3*106,limit,a[i]<=109。
    • 解法：显然随着r增大，l显然不减，分别维护两个单调队列维护最大值和最小值，每次先插入两个队列队尾，然后拿两个队头作差，如果不符合就弹出下标较小的队头，重复直至合法。注意l的初始值不要忘记赋，复杂度O(n)。
    • 代码：Code