cjb-poi2011

从 Trac 迁移的文章

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

原文章内容如下：

 * 总结： 


 * Lollipop
  * 题意：给出一个长度为n的只包含1或2的序列，m个询问是否存在一个子序列和为k，输出l,r，n<=1000000。
  * 解法：有一个很漂亮的性质：对于一个和为k的子序列，他一定可以变成任何和<=k且同奇偶的子序列：当a[l]=a[r]=1，将l和r删去得到k-2，否则a[l]和a[r]必有一个为2，删去也可得到k-2。由于询问最多只有2e6种，我们直接找到原串和最大的两个奇偶序列，有一个必为全串，另一个必然是某前缀或某后缀，找出来分别模拟一次把答案记录下来，询问就O(1)了。整体复杂度为O(n)。
  * 代码：[wiki:cjb-poi2011lollipop Code]

 * Lightning Conductor
  * 题意：已知一个长度为n的序列a[1],a[2],…,a[n]。对于每个1<=i<=n，找到最小的非负整数p满足对于任意的j, a[j] < = a[i] + p – sqrt(abs(i-j))，n<=500000,0<=ai<=1000000000)。
  * 解法：移项之后得到p<=a[j]-a[i]+sqrt(abs(i-j))，不妨只考虑j<=i(另一边把序列反转再做一次即可)，设f[i]=p=max(a[j]+abs(i-j))-a[i](j<=i)。设对于i，j>k且j比k优，那么对于i+1而言，j必然也比k优，因为f(x)=sqrt(x)的导函数是递减的，也就是sqrt(k)-sqrt(p)>sqrt(k+1)-sqrt(p+1)。那么综上，该dp满足决策单调性，分治dp即可。对于决策单调性dp，除了传统的单调队列然后在上面二分的做法之外，还有很方便的递归写法(想想这还是2015年ydc教我的...光阴似箭啊....)，假设当前求解区间为[l,r]，决策区间为[fl,fr]，则取mid=(l+r)/2，枚举转移出f[mid]，记录最优决策位置p，则[l,mid-1]的决策位置是[fl,mid]，[mid+1,r]的决策位置是[mid,fr]，递归下去即可。复杂度为O(nlogn)。
  * 代码：[wiki:cjb-poi2011lightningconductor Code]

 * Plot
  * 题意：给一个平面上的点组成的长度为n的序列，要求把这个序列切成至多m段，每一段都用圆覆盖，要求最大半径最小，n,m<=100000,-1000000<=xi,yi<=1000000。
  * 解法：二分答案之后转成判定问题。如果每次都暴力二分下一个断点，我们需要二分m次，直接二分可能会使check复杂度变成O(n*mlogn)。这里我们使用一点小技巧，先检验长度为1的方案，然后检验长度为2的方案，然后4,8.....直到找到一个不合法的k，然后我们在[k/2,k]这个区间里二分就可以了。因为这样这次搜索的二分上限为O(klogn)，而对答案的贡献至少为k，所以check时间复杂度上限为O(nlogn)。总复杂度为O(log*nlogn)。然而这样在oj上还是卡不过去，还要卡常数。提供几个技巧：1.开一个map把已经算过的[l,r]覆盖答案存下来; 2.加inline; 3.缩减一些存储的操作，比如最后才存储答案而不是每次都塞进ans里。
  * 代码：[wiki:cjb-poi2011plot Code]

 * Strongbox
  * 题意：有个密码箱，0到n-1中某些整数是密码，满足如果a和b是密码，那么(a+b)%n也是密码，现在猜了k-1个都是错的，第k个是对的，问题密码集合最大是多大，n<=10^14^,k<=250000。
  * 解法：如果x是密码，那么gcd(n,x)肯定也是密码；如果x和y是密码，那么gcd(x,y)也是密码。假设最后答案集合为S，那么S必包含所有密码的gcd，于是我们考虑枚举L=gcd(a[k],n)的因子，然后用gcd(a[i],n)去筛掉即可，直接check会tle，需要类似于筛素数那样，利用L的质因子利用倍数去筛掉原数，最后复杂度是O(n^0.5^log^2^n)。
  * 代码：[wiki:cjb-poi2011strongbox Code]

 * Difference
  * 题意：给一个长度为n的小写字母序列，求一个子序列满足出现最多的字母减去出现最少的字母数量最大，求这个最大值,n<=1000000。
  * 解法1：枚举出现最多的字母和出现最少的字母，将其位置归并成一个+-1的序列，则等价于经典的求子段和最大，扫一遍即可，但是这题有个额外的条件是必须包含至少1个-1，需要特判当前值是否合法以及不能忘记统计最后一段正值进入答案(见代码注释部分)，因为每个字母的位置会被合并至多alphabet次，所以总复杂度为O(alphabet*n)。
  * 解法2：对于两个字符计算答案为cnt[r][a]-cnt[l][a]-(cnt[r][b]-cnt[l][b])，可以转化成cnt[r][a]-cnt[r][b]和cnt[l][a]-cnt[l][b]，于是我们只要记录一下当前值和前面的最小值，次小值，更新一个前缀y的数量不一样的就好了。因为每移动一格只会更新2*alphabet个cnt，于是复杂度也是O(alphabet*n)。
  * 代码：[wiki:cjb-poi2011difference Code] (代码是算法一)

 * Garbage
  * 题意：给一张n个点，m条边的无向图，每条边是黑色或者白色，给出每条边初始和最终的颜色，每次操作可以选择一个简单环并把上面的边flip，问你转换方案，n<=100000,m<=1000000。
  * 解法：对于一条初始和最终颜色相同的边，如果有方案要经过他，那么一定是偶数次，可以把2*n环合并成n个环从而不经过该边，因此只需要考虑起始和最终颜色不同的边。剩下就变成是否能用数个简单环覆盖所有的边，类似欧拉回路，首先所有点度数必须为偶数，否则无解。接下来遍历并将点压进栈，如果发现当前点已经在栈里了就不断弹栈直到让当前点出栈位置，这样的就成为一个简单环。要注意实现细节，每条边只能走一次，可以类似dinic那样的小技巧实现当前弧优化，即int&p=gh[x]，最后复杂度为O(n+m)。
  * 代码：[wiki:cjb-poi2011garbage Code] 

 * Tree Rotations
  * 题意：给一棵叶子节点个数为n的二叉树，任何节点左右儿子可以交换，要求交换之后从左到右由叶子节点下标组成的序列逆序对数量最少，n<=1000000。
  * 解法：考虑l和r两个子树，他们里面的构造不影响l和r合并之后新增的逆序对数量，所以启发式合并过程中维护下新增的逆序对数量，取sum和sum-cnt中的较小值即可，用平衡树维护按值递增的序列，复杂度存疑，感觉应该是O(nlogn)的，暂时说不清楚是1个log还是2个log。版本1的n<=500000，一般拿来练习线段树合并，但是n<=1000000版本的空间卡得比较紧，所以用平衡树来维护启发式合并的过程。
  * 代码：[wiki:cjb-poi2011treerotations Code] 

 * Temperature
  * 题意：给出n天温度的阈值[l,r]，问气温不降的最长连续天数可能是多少，n<=1000000。
  * 解法：假设[i,j-1]合法，那么[i,j]合法当且仅当max(l[i]..l[j-1])<=r[j]，所以依次扫每一天，维护一个l不增的单调队列，每次进来从tail开始把l<=l[i]都压掉，然后head把不合法的部分弹掉，用i-q[head-1]更新答案即可，复杂度为O(n)。
  * 代码：[wiki:cjb-poi2011temperature Code] 

 * Dynamite
  * 题意：
  * 解法：
  * 代码：[wiki:cjb-poi2011dynamite Code] 

 * Periodicity
  * 题意：
  * 解法：
  * 代码：[wiki:cjb-poi2011periodicity Code] 

 * Meteors
  * 题意：
  * 解法：
  * 代码：[wiki:cjb-poi2011meteors Code] 

 * Sticks
  * 题意：给出不超过1000000根木棒，木棒颜色为[1,k]，求任意三根不同色且能组成三角形的木棒，k<=50。
  * 解法：排序后依次枚举最长的那根木棍，暴力维护每种颜色当前最长木棍，枚举找到不同色的最长两根，判别即可，效率为O(nlogn+nk)。
  * 代码：[wiki:cjb-poi2011sticks Code] 

 * Programming Contest
  * 题意：n个人，m道题，每道题用时r，总时间t，给出k组关系表示a能做出b，问最多题数下最少罚时(Σ完成时间)，n,m<=500,r,t<=1000000。
  * 解法：有个显然的费用流，对每个人拆出从S连过来的t/r条边，费用为k*r，流量为1，其余用边链接人和对应题目，题目和T，费用为0，流量为1。然后边数可能就爆炸了，所以要换种思路。我们发现这个图的费用都在左侧，所以可以直接按照费用从小到大的顺序去增广，也就是直接跑匈牙利，这里特别说明一下：匈牙利算法本质上在求一张左右端点流量皆为1的图的最大流，如果在不清0的情况下迭代k次匈牙利算法，则实际上在求左端点流量为k，右端点流量为1的图的最大流。所以，可以直接对应到这道题上，再考虑有效增广不超过m次，且每个人增广失败后以后一定也会失败，总复杂度均摊下来是O(nm^2^)的，很遗憾由于常数会差两个点过不去。其实我们再次理解这个费用流过程，实际上就是让尽量多的人做费用为r的第一道题,然后让尽量多的人做费用为2r的第二道题.....那么我们写个网络流，每次把源点连出去的边流量reset就好，虽然这样做会使得不能够沿着流量边反悔了，但是这道题的性质使得反悔一定不会更优，比如：如果考虑费用为r的时候让1号人做了1号题,然后考虑费用为2r的时候发现可以让2号人做1号题，1号人做2号题，这种情况是不会出现的，因为在考虑费用为r的时候就可以让2号人做1号题，1号人做2号题。Dinic的复杂度也是三次方级别的，然而由于数据以及dinic算法本身的特性，跑得飞快，顺利通过所有测试点。至于打印答案，我们发现同一个人做的题目之间顺序是无所谓的，所以只要按人分组，随便输出即可。
  * 代码：[wiki:cjb-poi2011programmingcontest1 Hungary 80pts(TLE)]      [wiki:cjb-poi2011programmingcontest2 Dinic 100pts]
  • 总结：
  • Lollipop
    • 题意：给出一个长度为n的只包含1或2的序列，m个询问是否存在一个子序列和为k，输出l,r，n<=1000000。
    • 解法：有一个很漂亮的性质：对于一个和为k的子序列，他一定可以变成任何和<=k且同奇偶的子序列：当a[l]=a[r]=1，将l和r删去得到k-2，否则a[l]和a[r]必有一个为2，删去也可得到k-2。由于询问最多只有2e6种，我们直接找到原串和最大的两个奇偶序列，有一个必为全串，另一个必然是某前缀或某后缀，找出来分别模拟一次把答案记录下来，询问就O(1)了。整体复杂度为O(n)。
    • 代码：Code
  • Lightning Conductor
    • 题意：已知一个长度为n的序列a[1],a[2],…,a[n]。对于每个1<=i<=n，找到最小的非负整数p满足对于任意的j, a[j] < = a[i] + p – sqrt(abs(i-j))，n<=500000,0<=ai<=1000000000)。
    • 解法：移项之后得到p<=a[j]-a[i]+sqrt(abs(i-j))，不妨只考虑j<=i(另一边把序列反转再做一次即可)，设f[i]=p=max(a[j]+abs(i-j))-a[i](j<=i)。设对于i，j>k且j比k优，那么对于i+1而言，j必然也比k优，因为f(x)=sqrt(x)的导函数是递减的，也就是sqrt(k)-sqrt(p)>sqrt(k+1)-sqrt(p+1)。那么综上，该dp满足决策单调性，分治dp即可。对于决策单调性dp，除了传统的单调队列然后在上面二分的做法之外，还有很方便的递归写法(想想这还是2015年ydc教我的...光阴似箭啊....)，假设当前求解区间为[l,r]，决策区间为[fl,fr]，则取mid=(l+r)/2，枚举转移出f[mid]，记录最优决策位置p，则[l,mid-1]的决策位置是[fl,mid]，[mid+1,r]的决策位置是[mid,fr]，递归下去即可。复杂度为O(nlogn)。
    • 代码：Code
  • Plot
    • 题意：给一个平面上的点组成的长度为n的序列，要求把这个序列切成至多m段，每一段都用圆覆盖，要求最大半径最小，n,m<=100000,-1000000<=xi,yi<=1000000。
    • 解法：二分答案之后转成判定问题。如果每次都暴力二分下一个断点，我们需要二分m次，直接二分可能会使check复杂度变成O(n*mlogn)。这里我们使用一点小技巧，先检验长度为1的方案，然后检验长度为2的方案，然后4,8.....直到找到一个不合法的k，然后我们在[k/2,k]这个区间里二分就可以了。因为这样这次搜索的二分上限为O(klogn)，而对答案的贡献至少为k，所以check时间复杂度上限为O(nlogn)。总复杂度为O(log*nlogn)。然而这样在oj上还是卡不过去，还要卡常数。提供几个技巧：1.开一个map把已经算过的[l,r]覆盖答案存下来; 2.加inline; 3.缩减一些存储的操作，比如最后才存储答案而不是每次都塞进ans里。
    • 代码：Code
  • Strongbox
    • 题意：有个密码箱，0到n-1中某些整数是密码，满足如果a和b是密码，那么(a+b)%n也是密码，现在猜了k-1个都是错的，第k个是对的，问题密码集合最大是多大，n<=1014,k<=250000。
    • 解法：如果x是密码，那么gcd(n,x)肯定也是密码；如果x和y是密码，那么gcd(x,y)也是密码。假设最后答案集合为S，那么S必包含所有密码的gcd，于是我们考虑枚举L=gcd(a[k],n)的因子，然后用gcd(a[i],n)去筛掉即可，直接check会tle，需要类似于筛素数那样，利用L的质因子利用倍数去筛掉原数，最后复杂度是O(n0.5log2n)。
    • 代码：Code
  • Difference
    • 题意：给一个长度为n的小写字母序列，求一个子序列满足出现最多的字母减去出现最少的字母数量最大，求这个最大值,n<=1000000。
    • 解法1：枚举出现最多的字母和出现最少的字母，将其位置归并成一个+-1的序列，则等价于经典的求子段和最大，扫一遍即可，但是这题有个额外的条件是必须包含至少1个-1，需要特判当前值是否合法以及不能忘记统计最后一段正值进入答案(见代码注释部分)，因为每个字母的位置会被合并至多alphabet次，所以总复杂度为O(alphabet*n)。
    • 解法2：对于两个字符计算答案为cnt[r][a]-cnt[l][a]-(cnt[r][b]-cnt[l][b])，可以转化成cnt[r][a]-cnt[r][b]和cnt[l][a]-cnt[l][b]，于是我们只要记录一下当前值和前面的最小值，次小值，更新一个前缀y的数量不一样的就好了。因为每移动一格只会更新2*alphabet个cnt，于是复杂度也是O(alphabet*n)。
    • 代码：Code (代码是算法一)
  • Garbage
    • 题意：给一张n个点，m条边的无向图，每条边是黑色或者白色，给出每条边初始和最终的颜色，每次操作可以选择一个简单环并把上面的边flip，问你转换方案，n<=100000,m<=1000000。
    • 解法：对于一条初始和最终颜色相同的边，如果有方案要经过他，那么一定是偶数次，可以把2*n环合并成n个环从而不经过该边，因此只需要考虑起始和最终颜色不同的边。剩下就变成是否能用数个简单环覆盖所有的边，类似欧拉回路，首先所有点度数必须为偶数，否则无解。接下来遍历并将点压进栈，如果发现当前点已经在栈里了就不断弹栈直到让当前点出栈位置，这样的就成为一个简单环。要注意实现细节，每条边只能走一次，可以类似dinic那样的小技巧实现当前弧优化，即int&p=gh[x]，最后复杂度为O(n+m)。
    • 代码：Code
  • Tree Rotations
    • 题意：给一棵叶子节点个数为n的二叉树，任何节点左右儿子可以交换，要求交换之后从左到右由叶子节点下标组成的序列逆序对数量最少，n<=1000000。
    • 解法：考虑l和r两个子树，他们里面的构造不影响l和r合并之后新增的逆序对数量，所以启发式合并过程中维护下新增的逆序对数量，取sum和sum-cnt中的较小值即可，用平衡树维护按值递增的序列，复杂度存疑，感觉应该是O(nlogn)的，暂时说不清楚是1个log还是2个log。版本1的n<=500000，一般拿来练习线段树合并，但是n<=1000000版本的空间卡得比较紧，所以用平衡树来维护启发式合并的过程。
    • 代码：Code
  • Temperature
    • 题意：给出n天温度的阈值[l,r]，问气温不降的最长连续天数可能是多少，n<=1000000。
    • 解法：假设[i,j-1]合法，那么[i,j]合法当且仅当max(l[i]..l[j-1])<=r[j]，所以依次扫每一天，维护一个l不增的单调队列，每次进来从tail开始把l<=l[i]都压掉，然后head把不合法的部分弹掉，用i-q[head-1]更新答案即可，复杂度为O(n)。
    • 代码：Code
  • Dynamite
    • 题意：
    • 解法：
    • 代码：Code
  • Periodicity
    • 题意：
    • 解法：
    • 代码：Code
  • Meteors
    • 题意：
    • 解法：
    • 代码：Code
  • Sticks
    • 题意：给出不超过1000000根木棒，木棒颜色为[1,k]，求任意三根不同色且能组成三角形的木棒，k<=50。
    • 解法：排序后依次枚举最长的那根木棍，暴力维护每种颜色当前最长木棍，枚举找到不同色的最长两根，判别即可，效率为O(nlogn+nk)。
    • 代码：Code
  • Programming Contest
    • 题意：n个人，m道题，每道题用时r，总时间t，给出k组关系表示a能做出b，问最多题数下最少罚时(Σ完成时间)，n,m<=500,r,t<=1000000。
    • 解法：有个显然的费用流，对每个人拆出从S连过来的t/r条边，费用为k*r，流量为1，其余用边链接人和对应题目，题目和T，费用为0，流量为1。然后边数可能就爆炸了，所以要换种思路。我们发现这个图的费用都在左侧，所以可以直接按照费用从小到大的顺序去增广，也就是直接跑匈牙利，这里特别说明一下：匈牙利算法本质上在求一张左右端点流量皆为1的图的最大流，如果在不清0的情况下迭代k次匈牙利算法，则实际上在求左端点流量为k，右端点流量为1的图的最大流。所以，可以直接对应到这道题上，再考虑有效增广不超过m次，且每个人增广失败后以后一定也会失败，总复杂度均摊下来是O(nm2)的，很遗憾由于常数会差两个点过不去。其实我们再次理解这个费用流过程，实际上就是让尽量多的人做费用为r的第一道题,然后让尽量多的人做费用为2r的第二道题.....那么我们写个网络流，每次把源点连出去的边流量reset就好，虽然这样做会使得不能够沿着流量边反悔了，但是这道题的性质使得反悔一定不会更优，比如：如果考虑费用为r的时候让1号人做了1号题,然后考虑费用为2r的时候发现可以让2号人做1号题，1号人做2号题，这种情况是不会出现的，因为在考虑费用为r的时候就可以让2号人做1号题，1号人做2号题。Dinic的复杂度也是三次方级别的，然而由于数据以及dinic算法本身的特性，跑得飞快，顺利通过所有测试点。至于打印答案，我们发现同一个人做的题目之间顺序是无所谓的，所以只要按人分组，随便输出即可。
    • 代码：Hungary 80pts(TLE) Dinic 100pts