WORIA

https://codeforces.com/contest/1201 B. Zero Array   题意：n个数，每次挑两个数各-1，问能否都等于0。 显然总和为偶数不行。 如果最大值大于总和一半，也不行。 其他都可以，比如3，4，5，可以把3拆成1和2，5-2变3，4-1变3. 123456789101112131415#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const int N = 2e5 + 10;int n;ll a[N];ll mx, sum;int main() { scanf("%d", &n); for (int i = 1; i <= n; i++)scanf("%lld", &a[i]), mx = max(mx, a[i]), sum += a[i]; if (sum & 1 || mx > sum / 2)puts(&qu ...

https://codeforces.com/contest/1199 E. Matching vs Independent Set   题意：给定一个3n个节点，m条边的无向图，求一个包含n条边的匹配，或包含n个点的独立集。 n条边的匹配有2n个点，n个点的独立集有n个点，加起来刚好3n个点，自然要想到两种可以完全分开来。 贪心 直接找匹配，如果边数大于等于n，输出。 否则，剩下的不再匹配里的点之间一定没有边，那就是一个独立集。点数一定大于等于n。输出。 123456789101112131415161718192021222324252627282930313233343536373839#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const int N = 5e5 + 10;int T, n, m;int vis[N];vector<int>vc;typedef pair<int, int>pii;pii e[ ...

https://codeforces.com/contest/1179 A. Valeriy and Deque   题意：一个队列，每次拿出队首和队首后面那个，把大的放回队首，小的放到队尾，多次询问，问第m次操作时拿出的是哪两个数。 模拟 显然如果队首是最大值，以后就是队列其他元素循环。所以先模拟到把最大值放到队首，以后只要看循环到哪里即可。 12345678910111213141516171819202122232425262728293031323334353637383940#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5 + 10;const int INF = 0x3f3f3f3f;const ll mod = 998244353;int n, q, mx, cnt, A, B;ll m;int ansa[N], ansb[N];deque<int>dq;vector<int>vc;int main() { scan ...

https://codeforces.com/contest/1172 A. Nauuo and Cards   题意：有n张数字1到n的牌，和n张0牌，手里有n张，队列里有n张，每次操作从手里选一张放进队列尾部，再从队首拿出一张。问最少操作几次使得队列里牌从1到n升序。 模拟 只有当后部分已经从1开始升序，且前部分每个数在需要时能拿出来，才能不需要把所有牌都拿出来。 确定哪些牌要拿出来后，先把最小的拿出来，在它后面的那些牌需要额外的时间拿，它们的位置和需要他们的时间之差就是增加的时间，当确定需要时都能拿到后，就一边拿一边放。 123456789101112131415161718192021222324252627282930#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5 + 10;const int INF = 0x3f3f3f3f;const ll mod = 998244353;int n;int a[N], b[N], p[N], vis[N];int ...

https://codeforces.com/contest/1174 D. Ehab and the Expected XOR Problem   题意：给定数n和x，要求构造一个尽可能长的数组，任意区间内的异或和不等于0或x。 遇到区间还是要变成前缀和。问题变为构造n个不相等的数，两两异或不为x。 所以直接筛就好了，从前到后遍历，遇到没删的就取，然后删掉x异或的值。 可以发现这么做最终一定剩下一半的数，并且这是最多的情况。 得到了前缀和，直接构造即可。 1234567891011121314151617181920212223242526#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f;const int N = 1e6 + 10;const ll mod = 1e9 + 7;int n, x;int die[N];vector<int>ans;int main( ...

https://codeforces.com/contest/1158 A. The Party and Sweets   题意：n个男生，m个女生，每个男生送每个女生礼物，给出每个男生送出的礼物的最小价值和每个女生的收到的礼物的最大价值。问所有男生花的钱之和最少是多少。 贪心 让价值最高的男生送所有女生她们收到的最贵的礼物，其他男生只送最便宜的。 但是也不能让最高的男生送所有，因为可能他的最小值就不对了，所以如果不对了就让第二个男生送最小的女生。 12345678910111213141516171819202122#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const int N = 2e5 + 10;int n, m;int a[N], b[N];ll sum, ans;int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= ...

https://codeforces.com/contest/1163 D. Mysterious Code   题意：给定3个字符串，串c中有小写字母和星号，串s和t只有小写字母，现在要把所有星号变成小写字母，要求最大化 串s在c中的出现次数-串t在c中的出现次数，这里的出现指作为子串出现。 KMP/AC自动机+dp dp[i][j][k]dp[i][j][k]dp[i][j][k] 表示c串到第 i 位，s串到第 j 位，t串到第 k 位，最大的s，t出现次数差值。 每当s串到结尾时，差值+1；当t串到结尾时差值-1。 遍历i，j，k。当c在第i位，s在第j位，t在第k位，要假设s串前j-1位就是c串的i前j-1位，并且t串前k-1位就是c串前k-1位。当加入了c串第i位后，要考虑s串可以到第几位，t串到第几位。这里可以用kmp预处理出来，因为kmp是不断压缩后缀，且前后缀相同，所以如果s串前i-1位是c串到i为止的后缀，那么s的next[j-1] 一定也是c到i-1为止的后缀，所以不断跳next，直到c的第i位能接到后面。 用AC自动机的话每个节点记录这个节点表示的前缀的后缀是否 ...

http://codeforces.com/contest/1161 A. Hide and Seek   题意：有n个位置，Alice在某个位置放了一个球，Bob猜m次，每次猜之前或之后Alice可以把球换到相邻的位置，但是整个过程最多只能换一次，要Bob一次都猜不对，问有几种初始放球和最终球位置的情况数。 判断每个位置作为初始位置，能不能向左或向右交换，或者不动。 仅当交换之后Bob的序列里没有换完之后的位置才能交换。 1234567891011121314151617181920212223242526272829#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5 + 10;const int INF = 0x3f3f3f3f;int n, k, a[N], l[N], r[N];ll ans;int main() { scanf("%d%d", &n, &k); memset(l, 0x3f, sizeof(l) ...

https://codeforces.com/contest/1151 E. Number of Components   题意：给定一条链，编号从1到n，每点有颜色，f(L,R)f(L,R)f(L,R) 为颜色在 [L,R][L,R][L,R] 的点的点导出子图上联通块的个数，问所有区间的 f 值之和。 dp/计数 和上一场Atcoder的几乎一样，但是这里是一条链，并且每种颜色的点数不固定。 当然可以用并查集把相邻的颜色相同的点合起来，再同样做法遍历颜色，只不过这里每次加入的可能不止一个点。 思路相同，但是其实本题更简单，可以直接计数。 假设是一条横着的链，每个点与它左边的点相连。则如果某个区间时该点左边的点也在这个区间里，则可以视为该点与左边的点合并了。 则遍历每个点，每次考虑加入这个颜色会使得所有区间的 f 值增加多少。 对于同时包含了它和它左边点的区间，联通块个数不会增加；对于不包含它的区间，当然也不会增加；对于只包含它，而不包含它左边点的区间，联通块个数+1。 则只要遍历每点，找到只包含它，而不包含它左边点的颜色区间的个数即可。 1234567891011121314151 ...

https://codeforces.com/contest/1153 E. Serval and Snake   题意：交互题。给定一个n*n的网格，n小于1001，里面有一条链，可能是弯曲的，不超过2019次询问，每次询问对一个矩形，有几次经过这个矩形边界。求链的两个端点坐标。 二分 一个矩形如果包含了链的几个节点，那就可以看成这几个节点缩点了。原来是一条链，是一个欧拉路径，缩点后必定还是欧拉路径或欧拉回路。 如果矩形包含一个端点，则有奇数个度，如果包含两个或者0个，则有偶数个度。 考虑询问每一行，如果这一行包含一个端点，则有奇数度，确定行后二分确定列坐标。 如果两个端点在同一行，则无法得到结果。但是这两点就必定不在同一列了，所以再询问每一列，确定列后同样二分确定行坐标。因为知道是同一行了，所以只要二分一次就得到两个的行坐标了。 最差情况询问每一行每一列+一次二分，2010次。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556 ...