WORIA

https://codeforces.com/contest/1375 真的吐了，全都是构造 C. Element Extermination   题意：给定一个n的排列，每次操作选择 a[i]<a[i+1]a[i]<a[i+1]a[i]<a[i+1] 的数对并删去其中任一个，问能否最终数列只剩一个数。 构造 结论：若 a[1]<a[n]a[1]<a[n]a[1]<a[n] 则可以，否则不行。 若 a[1]<a[n]a[1]<a[n]a[1]<a[n]，则先把 a[2]⋯a[n]a[2]\cdots a[n]a[2]⋯a[n]，任意贪心地删，最终一定递减，再用 a[1]a[1]a[1] 贪心删其它数，再用 a[n]a[n]a[n] 贪心删其它数，最终一定能删到只剩 a[1],a[n]a[1],a[n]a[1],a[n]，这两个数再删去任意一个。 若 a[1]>a[n]a[1]>a[n]a[1]>a[n]，可以发现对于满足条件的 a[i]a[i]a[i]，删完后 a[i]a[i]a[i] 要么保留，要么变成 a[i+ ...

https://codeforces.com/contest/1368 E. Ski Accidents   题意：给定一个有向图，限定只从小节点连向大节点，且每个节点出度不超过 2。要求删掉不超过 47n\frac{4}{7}n74​n 个点，使得图上不存在长度大于 1 的路径。 贪心 遍历每条路径，当走到第3个点时，就把第3个点删掉。 证明也是实现方式： 设 V0V_0V0​ 为没有入度或者入度全为被删点的点，即删完后每条路径的起点。 V1V_1V1​ 为每条路径的第2个点，即存在 V0V_0V0​ 指向它的点。 V1V_1V1​ 为每条路径的第3个点，也就是要删掉的点，即存在 V1V_1V1​ 指向它的点。 由于每点出度最大为2，所以 V1≥12V2V_1\ge \frac{1}{2}V_2V1​≥21​V2​，V0≥12V1≥14V2V_0\ge \frac{1}{2}V_1\ge \frac{1}{4}V_2V0​≥21​V1​≥41​V2​。 由定义容易发现，每点都恰属于一类，所以 n=V0+V1+V2n=V_0+V_1+V_2n=V0​+V1​+V2​。 所以 n≥74V ...

https://codeforces.com/contest/1326 A. Bad Ugly Numbers   题意：构造出一个正整数，满足长度为n，不含0，不能被包含的数字整除。 2333333这样就好了。 1234567891011121314151617#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5 + 10;const int INF = 0x3f3f3f3f;int T, n;int main() { scanf("%d", &T); while (T--) { scanf("%d", &n); if (n == 1) { puts("-1"); continue; } printf("2"); for (int i = 0; i < n - 1; i++)printf("3"); ...

http://codeforces.com/contest/1266 这场就是纯思维场啊！！ C. Diverse Matrix   题意：构造一个nm矩阵，使得每行的gcd和每列的gcd都不相等，且最大值最小。 增量构造 nm的矩阵可以由22矩阵构造出，先确定每列gcd，再确定行的gcd即可。 123456789101112131415161718192021222324252627282930313233343536373839404142#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 1e4 + 10;const int INF = 0x3f3f3f3f;int n, m;int ans[510][510];int gr[510], gc[510];int main() { cin >> n >> m; if (n == 1 && m == 1) { puts("0"); return ...

http://codeforces.com/contest/1450 B. Balls of Steel   题意：二维平面上n个点，每个点可以把与它曼哈顿距离不超过k的点吸过来，问最少吸几次能全都吸到一起，或者不行。 假设最终吸到某点u，那么与 u 曼哈顿距离不超过 k 的点一定不能操作，否则 u 就被吸走了，那么与 u 曼哈顿距离大于 k 的点就永远不会到 u，所以必须初始时所有点与 u 曼哈顿距离不超过 k。 12345678910111213141516171819202122232425262728#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;const ll inf = 0x3f3f3f3f3f3f3f3f;con ...

[D. Alex and Julian][http://codeforces.com/contest/1220/problem/D] Boy Dima gave Julian a birthday present - set BBB consisting of positive integers. However, he didn’t know, that Julian hates sets, but enjoys bipartite graphs more than anything else! Julian was almost upset, but her friend Alex said, that he can build an undirected graph using this set in such way: let all integer numbers be vertices, then connect any two iii and jjj with an edge if ∣i−j∣|i−j|∣i−j∣ belongs to BBB. Unfortunately ...

先上个模板题 [USACO11FEB] Cow Line https://www.luogu.com.cn/problem/P3014 题意：康托展开模板，给定排列问第几个，给定位置问排列。 可以暴力，但没必要。 注意一下逆康托展开的二分，要找的是满足 query(x) - 1 >= tmp 的最小的数，那么这个数的a值一定是 1，因为再往左a值就-1了，如果右边的数a值为 0，那么 query(x+1) - 1和 query(x) - 1 相同，也满足条件。 树状数组。O(q nlog⁡nlog⁡n)O(q\ n\log n\log n)O(q nlognlogn) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 1e4 + ...

B. Balance of the Force A long time ago in a galaxy far, far away, there was a group of knights who mastered the ancient power - the Force. To bring order and balance to the universe, the Force is divided into two categories that conflict with each other: the Jedi, who acts on the light side of the Force through non-attachment and arbitration, and the Sith, who uses the dark side through fear and aggression. There were NNN knights who mastered the Force. Each knight could join either the light s ...

https://www.lydsy.com/JudgeOnline/problem.php?id=4316 题意：给出一张仙人掌图，求最大独立集。 首先，对于一棵树，我们知道它的最大独立集可以dp求出。 f[i][0/1]f[i] [0/1]f[i][0/1] 表示 不选/选 结点 iii。 {f[u][0]=∑(u,v)∈Emax(f[v][1],f[v][0])f[u][1]=∑(u,v)∈Ef[v][1]\begin{cases} f[u] [0]=\sum_{(u,v)\in E} max(f[v] [1],f[v] [0])\\ f[u] [1]=\sum_{(u,v)\in E} f[v] [1] \end{cases} {f[u][0]=∑(u,v)∈E​max(f[v][1],f[v][0])f[u][1]=∑(u,v)∈E​f[v][1]​ 然而本题有环，环上两点的最大独立集显然无法这样求出，但若只有一个点属于环，则仍然存在父子之间的dp关系。所以考虑把环单独拿出来考虑。 圆圆点之间的连边与树边相同，而方点表示一个环，所以单独考虑。 方点的 f 值表示与环的最高点（d ...

https://www.lydsy.com/JudgeOnline/problem.php?id=2125 题意：多次询问，求仙人掌图上两点最短路。 树上两点最短路可以通过LCA求出。则考虑建出圆方树。 设dis[u]dis[u]dis[u] 表示 uuu 到树根的距离，则树上两点 u,vu,vu,v 最短路为 dis[u]+dis[v]−2⋅dis[lca]dis[u]+dis[v]-2\cdot dis[lca]dis[u]+dis[v]−2⋅dis[lca] 圆方边的意义则是环上点到环的父亲的最短距离。 若两点 u,vu,vu,v 的LCA是方点，则表示两点最终要经过一段弧，则此时需要求出环上某两点之间的最短路，并加上 u,vu,vu,v 到达这个环之前经过的距离。 为了求最终的环上两点的最短距离，还要额外处理，由于之前只记录了环上点到环父亲的最短距离，而这最短距离是否经过返祖边又会影响到能否通过两个距离做差得到两点的距离，所以在处理环时还要额外记录最短距离是否经过了返祖边。 实现起来还挺烦的，一不小心就错了。 树刨求LCA和Tarjan建圆方树的fa，dfn，dis数组都不同， ...