WORIA

https://codeforces.com/contest/1365 E. Maximum Subsequence Value   题意：给定一个数列，选出一个子序列，对于每一位，如果序列中这一位为0的数个数小于3，则序列的值中这一位为1。要求选出的子序列值最大。 子序列大小最多为3。 对于多于3个的子序列，假设该序列的值第i位为1，即第i位最多有2个为0，由鸽巢原理，子序列中任意3个数组成的序列值第i位同样为1。所以任意3个都和序列有同样的值。 那么刚开始选3个就好了。 12345678910111213141516171819202122232425#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f;const int N = 2e5 + 10;const ll mod = 1e9 + 7;int n;ll a[N], ans;int main() { scanf( ...

E. Johnny and Grandmaster   题意：有n个数a[i]，要分成两堆，每堆的和为 ∑pa[i]\sum p^{a[i]}∑pa[i]，两堆的差值最小，问差值。 贪心 首先要发现进制数的性质，对于任意一个i，∑j=1i−1pa[j]\sum_{j=1}^{i-1}p^{a[j]}∑j=1i−1​pa[j] 要么小于 pa[i]p^{a[i]}pa[i]，要么存在一个 k，使得 ∑j=ki−1pa[j]=pa[i]\sum_{j=k}^{i-1}p^{a[j]}=p^{a[i]}∑j=ki−1​pa[j]=pa[i]，且不论k是个怎么样的数组，都成立。 从大到小排列，每次看如果左边多了，就放右边，否则就放左边。 然后就可以分类讨论贪心的正确性了。下面为了方便，直接用 a[i]a[i]a[i] 代替 pa[i]p^{a[i]}pa[i]。 如果 ∑i=1n−1a[i]<a[n]\sum_{i=1}^{n-1}a[i]<a[n]∑i=1n−1​a[i]<a[n] ，则一定是先把最大的放一堆，其他都放另一堆。 假设现在有 a[n]=∑i=kn−1a[i]a ...

https://codeforces.com/contest/1363 C. Game On Leaves   题意：给定一棵树和一个目标节点，两个人轮流操作，每次选一个叶子拿掉，先拿掉目标节点的赢。 以目标节点为根，拿完只剩一条链的肯定输了，所以都是拿长链或者拿完还有边的节点。最后剩下目标节点和另一个节点。拿掉的个数只与结点数有关。所以判断节点数奇偶。 一直读错题了，以为拿完一条链就能拿目标节点了，实际是要变成叶子才能拿，搞成了尼姆游戏。。 12345678910111213141516171819202122232425#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f;const int N = 2e5 + 10;int T;int main() { scanf("%d", &T); while (T--) { int n, ...

https://codeforces.com/contest/1341 E. Nastya and Unexpected Guest   题意：从坐标0出发，要到坐标n，中间有一些安全岛，绿灯持续g秒，红灯持续r秒，红灯时必须在安全岛上等待，且在安全岛上可以改变方向。每秒移动1，要求最少时间到达坐标n。 状态 (u, t) 表示（坐标，绿灯剩余时间），每次转移到相邻安全岛，然后 bfs，初始 (0, g)，目标是 (n, 任意)。 spfa可以过，但是卡时间。绝对不是正解。 01bfs 第一次听说这东西。 spfa的复杂度为 O((E+V)log⁡(E+V))O((E+V)\log (E+V))O((E+V)log(E+V))，之所以会多出来个log，就是因为用堆维护了距离从小到大。 但是对于边权只有0或1的图来说，可以通过一个deque，把经过边权1得到的状态放到队尾，经过边权0得到的状态放到队首，这样自然得到有序的队伍，而少了log。 还要转化问题为01的图。 状态（u，t）仍然表示（坐标，绿灯剩余时间），但是距离不再是时间，而是经过的红绿灯轮数，则每次状态转移最多经过一次红灯，也 ...

https://codeforces.com/contest/1336 A. Linova and Kingdom   题意：有n个节点的树，选k个节点作为特殊点，每个特殊点的舒适度为它到根的路径上非特殊点的个数，问怎么选使得所有特殊点的舒适度之和最大。 贪心 一定只有当节点的所有子孙节点都被选了，才会选它，选择一个节点，会使得舒适度增加它的深度，且它的所有子孙节点舒适度都-1，所以要贪心选择深度-子孙节点数最大的节点。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const int N = 2e5 + 10;int n, k;vector<int>G[N];int siz[N], dep[N], a[N], fa[N];void dfs(int u, ...

https://codeforces.com/contest/1339 C. Powered Addition   题意：n个数，第 xxx 秒可以选任意个数各加上 2x−12^{x-1}2x−1，问最少过几秒能使数列非递减。 加的数字越小，要过的时间越少。 所以就贪心地少加即可，每个数最多只加到和前一个数相等。 1234567891011121314151617181920212223242526272829303132#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const int N = 2e5 + 10;const ll mod = 1e9 + 7;int T;int n;ll a[N];int cal(ll x) { for (int i = 30; i >= 0; i--) { if (x&(1ll << i)) { return i + 1; }  ...

http://codeforces.com/contest/1333 C. Eugene and an array   题意：如果一个数列没有和为0的区间，就是好的，给定一个数列，问有几个子区间是好的。 计数 枚举右端点，每次左端点最左不能包含和为0的区间。 先预处理出每个位置以它为右端点最小的和为0的区间的左端点。 向右枚举右端点时把它对应的预处理出的左端点和之前的比较，大的那个就是枚举的边界。 和牛客的某次练习赛很像，但是那题还要线段树。 12345678910111213141516171819202122232425262728293031#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 3e5 + 10;const int INF = 0x3f3f3f3f;ll a[N];map<ll, int>mp;ll sum[N], ans;int pos[N];int n, mx;int main() { scanf("%d", ...

http://codeforces.com/contest/1330 B. Dreamoon Likes Permutations   题意：给定一个数列，分成两部分，问有几种分割方式使得两部分都是一个排列。 遍历数列，判断左边是否是排列，右边是否是排列。 是排列则不能有相同的数，所以要记录vis，如果已知都不相同，且个数又是一定的，如果是排列，那么总和一定是唯一的，先预处理出每个排列的和，再直接判断即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5 + 10;const int INF = 0x3f3f3f3f;int T;int a[N], n, c1[N], c2[N], vis[N];ll sum[N];void ck() { fill(vis, vis + n + 1, 0) ...

http://codeforces.com/contest/1332 B. Composite Coloring   题意：给定长为n的合数数组，给每个数涂色，要求相同颜色的数不能互质，颜色最多11种，n≤1000,ai≤1000n\leq 1000,a_i\leq 1000n≤1000,ai​≤1000。 关键在于数字很小。第12个为33，33与33相乘得到大于1000，所以数组中每个数的最小质因数一定是前11个质因数中的一个，那么根据最小质因数给数字涂色。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5 + 10;const int INF = 0x3f3f3f3f;int T;int prime[N];bool is_prime[N];int sieve(int n) { int p ...

https://codeforces.com/contest/1325 C. Ehab and Path-etic MEXs   题意：给定一棵树，要求对边赋值，且所有点的路径上的MEX值的最大值最小。 构造 把叶子连出的边从0开始赋值，剩下的边随便赋值。 可知任意两点的路径上不会有大于两个叶子，则MEX最多为3. 12345678910111213141516171819202122232425262728#include <bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const int N = 5e5 + 10;const ll mod = 998244353;typedef pair<int, int> pii;pii es[N];int ans[N], n, d[N];int main() { scanf("%d", &n); for (int i = 1; i < n; i++) { ...