（一）
就，被虐爆的五小时ヽ(*。>Д<)o゜
B-Suffix Array
Parameterized Suffix Arrays for Binary Strings
Infinite Tree
virtual tree+Segment Tree/Fenwick Tree
Domino
Distances in Domino Flip Graphs
Quadratic Form
Lagrange Duality
Counting Spanning Trees
Enumerative properties of Ferrers graphs
Infinite String Comparision
Periodicity Lemma
BaXianGuoHai, GeXianShenTong
compute
Minimum-cost Flow
Minimum-cost Flow
1 or 2
Edmond's Algorithm
Easy Integration
Wallis' integrals
（1）高等数学：分块求积分
（2）分数取模$a^{-1}equiv a^{m-2} mod {m}$（费马小定理）
（二）
哟罗本，又是被虐死的一天啊（喝茶）
知识点都不会呢，四个小时坐在那里绞尽脑汁似乎有思绪但是又不会写真是太受虐了...怎么补嘛、、真是过分呜呜呜
https://ac.nowcoder.com/discuss/451028?type=101&channel=-1&source_id=0
All with pairs
前后缀+next数组
Boundary
同弧所用的圆周角相等+叉乘
更简单的方法：已知三点求圆心。
如何求？设圆心坐标。然后利用圆心到三点距离相等的等式解得坐标（二元一次方程组：使用cramer's rule）
证明：
https://blog.csdn.net/Healer66/article/details/82669436
模板：
https://blog.csdn.net/Miranda_ymz/article/details/81174852
double X,Y,R;
struct Point{
double x,y;
}pp[maxn];
double dis(Point x,Point y)
{
return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}void solve(Point a,Point b,Point c)//三点共圆圆心公式
{
X=( (a.x*a.x-b.x*b.x+a.y*a.y-b.y*b.y)*(a.y-c.y)-(a.x*a.x-c.x*c.x+a.y*a.y-c.y*c.y)*(a.y-b.y) ) / (2*(a.y-c.y)*(a.x-b.x)-2*(a.y-b.y)*(a.x-c.x));
Y=( (a.x*a.x-b.x*b.x+a.y*a.y-b.y*b.y)*(a.x-c.x)-(a.x*a.x-c.x*c.x+a.y*a.y-c.y*c.y)*(a.x-b.x) ) / (2*(a.y-b.y)*(a.x-c.x)-2*(a.y-c.y)*(a.x-b.x));
R=sqrt((X-a.x)*(X-a.x)+(Y-a.y)*(Y-a.y));//return (Point){x,y};
}
用STL vector存储遍历任何两点与原点得到的圆心。然后sort将相同圆心聚在一起。再遍历一遍vector找到出现次数最多的圆心。最后从1遍历到n，因为同一圆心出现次数一定是【算出来的圆心在这个点】的点的集合抽取任意两个算得到。所以通过C(i,2)来求等于最多出现的圆心的出现次数。找这个i。
思路参考：https://blog.nowcoder.net/n/f9fc7c3b1fbb455c9074f725515d0702
我的代码：
https://ac.nowcoder.com/acm/contest/5667/B
Cover the tree
无根树+DFS序
需要证明。
Duration
水题
Exclusive OR
异或题，不是很懂
Fake Maxpooling
LCM优化/单调队列（二维）
我的代码：
https://ac.nowcoder.com/acm/contest/5667/F
Greater and Greater
bitset
Happy Together
维护：set+平衡树+哨兵节点
Interval
图论：网格图网络流
Just Shuffle
环+逆元，没看懂
Keyboard Tree
叉积+积分+期望，没懂
（四）
https://ac.nowcoder.com/acm/contest/5669
Ancient Distance
贪心+树+二分
Count new string
后缀树（字典树）
Investigating legions
连通块
Dividing strings
分类讨论+枚举暴力
Eliminate++
思维+分类讨论+贪心
Jumping on the graph
连通块+最短路+暴力枚举+分类讨论
Geometry Challenge
几何逻辑
（五）
https://ac.nowcoder.com/acm/contest/5670#question
Graph
异或最小生成树
boruvka
https://www.iteye.com/blog/dsqiu-1689178
Portal
复杂DP+Dijkstra
Easy
生成函数
Drop Voicing
最长递增子序列
Bogo Sort
高精度（大数乘法+lcm处理）
Greetings Souvenir
二分图+残余网络流
Interval
二维偏序
Cone Walker
计算几何+分类讨论
Git Merge
模拟+DP
（六）
https://ac.nowcoder.com/acm/contest/5671
African sort
环论+概率
Data Structure
树链剖分+莫队+拆分
Fibonacci Partition
(Zenkorf representation) Treap+Lucas number
Grid Coloring
构造
Harmony Pairs
数位DP
Interesting Stirling Task
斯特林数+Lucas定理的证明
Josephus Transform
约瑟夫变换
K-bag
思维+unordered map
（七）
Pointer Analysis（模拟）
理解题意，通过一些基础数据结构
A National Pandemic
树上路径查询+LCA+Qtree
Social Distancing
打表+模拟退火/复杂DP
Topo Counting
DAG+拓扑排序
Valueable Forests
森林（代价）+prufer序列
Tokens on the Tree
并查集+连通块+线段树/树状数组
NeoMole Synthesis
树型DP+整数线性规划+带权二部图的最小权完美匹配（Kuhn-Munkres）+最短路（Floyd-Warshal）+同构子树
（八）
I Interesting Computer Game（连通块+并查集）
G Game SET（暴力枚举）
E Enigmatic Partition（数字拆分+初始化）
A All-Star Game（连通块+LCT/线段树+可撤销并查集）
D Disgusting Relationship（复杂群、环论+Lucas定理+五边形数定理）
C Cinema（状压DP）
J Jumping Points（计算几何：贪心+凸壳）
B Bon Voyage（线段树+二分+前缀和）
F Factorio（DAG+高精度：bitset维护超长整型）
H Hard String Problem（字符串）
（九）
A-Groundhog and 2-Power Representation
朴素递归思想+高精度
模板：高精度进制转换
int conversion(//函数实现任意进制的转换 int input[],//输入的数字，数字的长度就是数组的长度 int length,//数字的长度 int output[],//将结果输出到目标数组,注意这是从低位到高位 int m,int n //将m进制的输入转换成n进制的输出 ){ int sz=0;// sz用来记录output当前大小 for(int i=0;i<length;){ // i用来表示被除数当前最高位，手动除法时也是从最高位开始 int k=0; // k用来记录余数 for(int j=i;j<length;j++){ // j用来控制从i位置开始的所有有效位 int t=(input[j]+k*m)%n; // t临时变量用来记录余数 input[j]=(input[j]+k*m)/n; k=t; } output[sz++]=k; // 以十进制转二进制为例，这边余数是最终的二进制数的一部分 while(input[i]==0)i++; // 被除过一次后会减小，高位会变成零，因此需要重新定位高位，直到被除数除尽 } return sz; }
当然这题也可以用py
print(eval(input().replace("(","**(")))
B-Groundhog and Apple Tree
树+贪心：
把dp分两个，一个是遍历完这个子树最少需要a初始体力（即途中最差的情况所需要的体力），一个是遍历完之后能加上的b体力（要保持为正才行）
重点在于遍历子树的顺序。用贪心思维：对比两个子树
（1）优先遍历跑完之后体力增加的子树
（2）若两者都是体力增加，优先遍历途中最差情况要求体力最少的子树
（3）若两者都是体力减少，优先遍历【途中最差情况要求体力-跑完之后减少的体力】最大的子树（在最多体力的时候优先处理需要初始体力大但是总体消耗体力小的子树）
代码有所参考，细节并不是很清楚，此处挖坑
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; struct node{ long long a,b; //dp: 遍历完这个子树最少需要a初始体力;遍历完这个子树能够加上b体力. } dp[N]; //回溯的时候才结算从子树回到当前点的边权,所以sort的时候其实是少算了一条直接边权 vector<node> v[N]; //v: 另外一个点为a;边权为b. int a[N]; bool cmp(node a,node b){ if(a.b-a.a>=0){if(b.b-b.a<0) return 1;return a.a<b.a;} else{if(b.b-b.a>=0) return 0;return a.b>b.b;} } void dfs(int x,int y){ vector<node> vv; long long z=a[x],m=a[x]; for(auto i:v[x]){ if(i.a==y) continue; dfs(i.a,x); //遍历子树 dp[i.a].a+=i.b,dp[i.a].b-=i.b; //单向边权结算 if(dp[i.a].b<0) dp[i.a].a-=dp[i.a].b,dp[i.a].b=0; //维护使得遍历完能加上的体力大于或等于0 vv.push_back(dp[i.a]); //存进vector以便结算从子树回到当前点的边权 } sort(vv.begin(),vv.end(),cmp); //决定访问子树的顺序 for(auto i:vv) m=min(m,z-i.a),z+=i.b-i.a; //m维护最差情况需要体力;z维护当前剩余体力,i.a相当于去路边权,来路等同,再次减掉. if(m>=0) dp[x].a=0,dp[x].b=z; //如果所需体力小于0,等于不需体力.遍历完能加上的体力即为z else dp[x].a=-m,dp[x].b=z-m; //要加上 遍历完当前子树最坏情况下需要的体力 抵消损耗 防止b为负数 } int main(){ int T,n,x,y,z,i; scanf("%d",&T); while(T--){ scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]),v[i].clear(); for(i=1;i<n;i++){ scanf("%d%d%d",&x,&y,&z); v[x].push_back(node(y,z)); v[y].push_back(node(x,z)); } dfs(1,0); printf("%lld ",dp[1].a); } return 0; }
C-Groundhog and Gaming Time
线段树优化DP
D-Groundhog and Golden Apple
并查集（连通块）+并查集回撤（按秩合并并查集+线段树分治简化）/Splay维护括号序列
E-Groundhog Chasing Death
储备知识：
（1）容斥定理：(a~b)交(c~d)=(1~b)交(1~d)+(1~(a-1))交(1~(c-1))-(1~b)交(1~(c-1))-(1~(a-1))交(1~d)
（2）幂次取模=取模（p-1）（欧拉定理/欧拉降幂）
（3）质因数分解
思维：
（1）GCD：把原题转化为对于每一个共同因子，找两者谁幂次更小的，取之的子问题，求和，再对其取幂，不同因子之间答案累乘。
（2）容斥原理：对于每一个共同因子，运用容斥原理，对于每一个1~x和1~y，枚举x，找什么时候谁大，什么时候谁小，等差数列求和。
（3）全部设为int型，计算过程中转化成long long可以节省近一半的时间
时间复杂度：max(b,d)(log x+log y)
#include<bits/stdc++.h> using namespace std; const long long mod=998244353; int u,v; int quickp(int a,int n){ int ans=1; while(n){ if(n&1) ans=1ll*ans*a%mod; a=1ll*a*a%mod; n>>=1; } return ans; } int solve(int x,int y){ int tmp=0,i,j; for(i=1;i<=x;++i){ j=u*i/v; if(j>y) j=y; //如果j>y，说明分界点超过了y，于是j这边都小于i那边 tmp=(tmp+(j+1ll)*j/2%(mod-1)*v%(mod-1))%(mod-1); tmp=(tmp+1ll*(y-j)*i%(mod-1)*u%(mod-1))%(mod-1); } return tmp; } int main(){ int a,b,c,d,x,y,i; scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&x,&y); int ans=1,mi; for(i=2;i*i<=max(x,y);++i){ //这里取max，保证最后剩下来的x可能是两者共同的因子 u=v=0; while(x%i==0) x/=i,u++; while(y%i==0) y/=i,v++; if(u==0||v==0) continue; mi=(2ll*(mod-1)+solve(b,d)+solve(a-1,c-1)-solve(a-1,d)-solve(b,c-1))%(mod-1); //容斥原理 减了两次，所以加两次mod-1 ans=1ll*ans*quickp(i,mi)%mod; } if(x>1&&x==y){ //质因数分解所剩下来的最后一个因子 u=v=1; mi=(2ll*(mod-1)+solve(b,d)+solve(a-1,c-1)-solve(a-1,d)-solve(b,c-1))%(mod-1); ans=1ll*ans*quickp(x,mi)%mod; } printf("%d ",ans); }
F-Groundhog Looking Dowdy
尺取/基数排序
G-Groundhog Playing Scissors
凸包
H-Groundhog Speaking Groundhogish
动态规划/生成函数优化（分治NTT求出倒数积再求逆）
I-The Crime-solving Plan of Groundhog
贪心+高精度
T=int(input()) for _ in range(T): n,a=int(input()),''.join(sorted(input().split(' '))) v=a.count('0') print(int(a[v])*int(a[v+1]+'0'*v+a[v+2:]))
J-The Escape Plan of Groundhog
枚举+前缀和
K-The Flee Plan of Groundhog（树上DFS）
（1）（A朝B）定向行走，经过t秒到达哪里？以A为根dfs一遍，记录到达所有点的时间；计算出距离B还需多长时间；从B开始，往上找祖先。
（2）树上追及（B追A）：以A为根dfs一遍，记录到达所有点的时间；再以B为根dfs一遍，记录到达所有点的时间；最后以A为根dfs，找最大的【B到达此处的时间刚刚小于A到达此处的时间】的时间，即为最长的追及时间。
L-The Shopping Plan of Groundhog
二维平面的矩阵加减操作
（十）
A. Permutation
x只向2*x连边，模p时会形成一个环；只向3*x连边的时候也是会形成一个环；
B. KMP Algorithm
卷积
C. Decrement on the Tree
把整棵树拆分成若干条路径；修改用set维护
D. Hearthstone Battlegrounds
贪心思维
E. Game
思维：最大的前缀平均值
F. Parenthesis sequence（难题）
平衡树+单向递归：类top tree的分治结构 三种cluster
G. Math Test
数论：枚举+CRT+生成
H. Heyawake（难题）
构造
I. Tournament
思维
J. Identical Trees
树形DP+二分图最大权匹配