WORIA

http://codeforces.com/contest/1416 B. Make Them Equal   题意：给定一个数列，每次选择 i，j，x，使得 ai:=ai−x⋅i,aj:=aj+x⋅ia_i := a_i - x \cdot i,a_j := a_j + x \cdot iai​:=ai​−x⋅i,aj​:=aj​+x⋅i。每次操作后必须非负。问不超过 3n 次操作后所有数相等。 贪心 先把所有数都尽量变小，把第一个数尽量变大。再重新分配。 变小时可能需要先从第一个数中拿一些，再给出去。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include <bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e6 + 10;const int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f ...

http://codeforces.com/contest/1420 C2. Pokémon Army (hard version)   题意：给定n的排列，要从数列中选出一个子序列，使得 ab1−ab2+ab3−ab4+…a_{b_1} - a_{b_2} + a_{b_3} - a_{b_4} + \dotsab1​​−ab2​​+ab3​​−ab4​​+… 最大，多次操作，每次选择两个数交换，问交换前以及每次交换后这个最大值。 把数列画出来，一定是选择一段递减序列的头和尾，对每段递减序列都是如此。 把每次交换分成两步，del和ins，del删除这两个数的影响，ins插入这两个数。 需要注意的是当这两个数位置相邻时要特殊处理，因为删除时可能重复删除了它们相连的那条边，所以要把它加回来。同理插入时也可能重复加了这条边，要减去。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include<bits/stdc++.h&g ...

http://codeforces.com/contest/1419/problem/D2 D2. Sage’s Birthday (hard version)   题意：给定一个数列，重新排列，要使得满足 a[i]<a[i−1]&&a[i]<a[i+1]a[i]<a[i-1]\&\& a[i]<a[i+1]a[i]<a[i−1]&&a[i]<a[i+1] 的数（首尾必不满足）最多。 从小到大排序，前一半数插到后一半数里。 12345678910111213141516171819202122232425#include <bits/stdc++.h>using namespace std;#define ll long long#define debug(x) cout<<#x<<":\t"<<x<<endl;const int N = 2e6 + 10;const int INF = 0x3f3f3f3f;const l ...

https://codeforces.com/contest/1396 B. Stoned Game   题意：给定 n 堆石子，两人轮流操作，每次选一堆石子并从中拿掉一个，且不能选上一轮（对方轮次）选过的。拿不了的输。 博弈 如果有一堆大于其它堆之和，那么先手只要拿这堆就必赢。 否则，每次拿当前可用的最多的那堆，如果总数为奇数则先手赢，否则后手。 由于先手先选，所以后手不可能更优，所以先手输必定只能是所有石子都拿完了。 12345678910111213141516171819202122#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f;const int N = 2e6 + 10;const ll mod = 1e9 + 7;int n;int a[N];int T;int main() { scanf("%d", &T); while ...

http://codeforces.com/contest/1401 E. Divide Square   题意：在由 (0,0),(0,106),(106,0),(106,106)(0,0),(0,10^6),(10^6,0),(10^6,10^6)(0,0),(0,106),(106,0),(106,106) 围成的正方形里，给定几条竖直或水平的线段，每条线段至少有一端接触正方形的一边，问这些线段把正方形分成几块。 树状数组+扫描线 当初刚刚接触扫描线也是因为一道正方形切割的问题。本题也是类似。 关键点在于，一条线段如果与正方形两边都相连，则每一条这样的线段都可以增加一块。并且，由于每条线段至少有一端在边框上，所以每一次线段相交都能够新增一块。 输入时顺便处理分割整个正方形的情况。接下来就是要算交点个数，老套路了，把每条竖线拆成两个点，横线按照 y 坐标排序，遍历横线，扫描线维护所有穿过当前 y 坐标的竖线的个数，树状数组维护横线所在 x 区间内的竖线个数。 1234567891011121314151617181920212223242526272829303132333435 ...

http://codeforces.com/contest/1395 E. Boboniu Walks on Graph   题意：给定一张有向图，有边权，每点出度最多为k，k≤9k\le 9k≤9，每一个出度为 i 的点取第 cic_ici​ 小的出边，这些 c1,c2,⋯ ,ckc_1,c_2,\cdots,c_kc1​,c2​,⋯,ck​ 组成一个tuple，问有多少种tuple，使得每个点都至少在某个环里。 集合哈希 由于每点取一条出边，所以要每点在一个环里，等价于每点被一条边指着。 k 很小，可以直接暴力枚举tuple中每个数，需要 O(1)O(1)O(1) 判断这个tuple是否满足条件。 先预处理出出度为 i 的点，所有第 j 小的边，并对这个集合进行哈希。对于一个tuple，可以把这 i 个集合哈希的合并，判断是否每点涉及一次。 哈希可以通过给每个数随机一个值，集合的哈希值等于所有数的哈希值的和或者乘积，或者其它满足合并律的操作。 下面的代码是用类似十进制的方式，其实并不严谨，因为可能并不涉及所有数，或者某个数涉及多次，但是哈希值与只涉及一次时相同。 123456789 ...

http://codeforces.com/contest/1393 C. Pinkie Pie Eats Patty-cakes   题意：给定一个数组，要求重排，使得相同数字间隔尽量远，问最远能间隔的距离。 贪心+（二分） 把所有数字按照出现次数排序，出现次数最大的先安排。 出现次数最大的数字把整个数组分成几块，其它数字都可以放在里面，且一定可以构造出使得其他数字间隔都不小于出现次数最大的数字的间隔的方案数。 所以可以二分答案，贪心构造。 1234567891011121314151617181920212223242526272829303132333435363738#include <bits/stdc++.h>#define debug(x) cout << #x << ":\t" << (x) << endl;using namespace std;#define ll long longconst int N = 2e6 + 10;const int INF = 0x3f3f3f3f;con ...

https://codeforces.com/contest/1371 D. Grid-00100   题意：要求构造一个含有k个1的n*n的01矩阵，设R为各行的和，C为各列的和，要求最小化 f(A)=(max⁡(R)−min⁡(R))2+(max⁡(C)−min⁡(C))2f(A) = (\max(R)-\min(R))^2 + (\max(C)-\min(C))^2f(A)=(max(R)−min(R))2+(max(C)−min(C))2。 构造 平均分配就好了。先算出每行有几个1，再按照列循环分配。 12345678910111213141516171819202122232425262728293031323334353637#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f;const ll mod = 1e9 + 7;const int N = 3e5 + 10;i ...

https://codeforces.com/contest/1369 C. RationalLee   题意：有n个数，m个人，每个人分 w[i]w[i]w[i] 个数，每个人的值为他所拿数的最大值和最小值之和，要求所有人的值之和最大，求该和。 贪心 所有数的最小值一定是某人的最小值，然后要考虑最大化其它最小值，所以要隔尽量多的位置取下一个最小值，同时还要保证最大值最大，所以最大值一定要是所有数里最大的m个。 虽然看上去隔 w[i]w[i]w[i] 个位置再取下一个最小值会使最小值更大一些，但是会使得最大值变小，试一下就能发现反而会使和更小。 123456789101112131415161718192021222324252627282930313233#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f;const ll mod = 998244353;const int N ...

https://codeforces.com/contest/1370 C. Number Game   题意：给定一个数n，两个人轮流操作，每次操作可以n-1或n除以它的一个奇数因子。先变为1的人赢。 显然如果n是奇数或2，先手必胜。 如果n没有奇数因子，即n是除2以外的2的幂次，则先手必败。 如果n是2和一个奇质数的乘积，则先手必败。 所以，如果n不是2的幂次，且有多个2，则先手必胜。如果n只有1个2，且有多个奇质数，则先手必胜。 其他情况先手必败。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f;const ll mod = 1e9 + 7;const in ...