T2 美丽的世界

装备可以看成有向边，谁拿了就由谁发出。所以每个弱联通块都只有两种可能性：

1. 树，边的方向是叶到根
2. 基环树，基环方向任意，叶到基环。

注意到反比例函数就是凸的，所以最值一定取在下凸壳上，对于每个弱连通块求闵可夫斯基和 \(A+B=\{\vec a+\vec b|\vec a\in A,\vec b\in B\}\)。

细节和代码实现待补。

T3 大原题

网络流题啊！考虑把每种物品的流向用网络流来维护并求出最优解。然后暴力的就是说把每个东西从一开始的点往下连 \(m\) 条链，交换的时候在那一层的点那边连双向边。优化就是把连着的一条链缩成一条边，相当于是一开始有 \(n\) 个点，每有一个交换操作，就把这个操作涉及到的两个点往下拓一位然后相连。注意到一个麻烦的做法是拆点再连，其实直接连就是可以的。然后跑网络流的时候注意，Dinic的bfs要从 \(t\) 向 \(s\) bfs，这样到了后面的时候，剩下残余网络不多了，这个bfs次数会减少。

建图的转化，换个说法就是说，因为对于最后的答案来说，每一种物品最多只能有 \(1\) 的贡献，那么不妨就把所有物品看成同一种。对于那个 \(a_i\)，因为每一次是在交换，所以可以用一条链的流量来限制。这一步转化还是相当精妙的。

#include
#include
#include
#include
using namespace std;
const int N=3000+13,INF=0x3f3f3f3f;
int n,m,s,t,a[N],las[N];
struct Edge{int v,w,nxt;}e[N<<4];
int h[N<<3],tot,dep[N<<3],cpy[N<<3];
bool vis[N<<3];
inline void clear(){memset(h,0,sizeof h);tot=1;}
inline void add_edge(int u,int v,int w){
	e[++tot]=(Edge){v,w,h[u]};h[u]=tot;
	e[++tot]=(Edge){u,0,h[v]};h[v]=tot;
}
inline bool bfs(){
	memset(dep,0x7f,sizeof dep);
	memcpy(cpy,h,sizeof h);
	memset(vis,0,sizeof vis);
	queue q;while(!q.empty()) q.pop();
	q.push(t),vis[t]=1,dep[t]=0;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=h[u];i;i=e[i].nxt){
			int v=e[i].v,w=e[i^1].w;
			if(w&&!vis[v]) vis[v]=1,dep[v]=dep[u]+1,q.push(v);
		}
	}
	return vis[s];
}
int dfs(int u,int minw){
	if(u==t||!minw) return minw;
	int flow=0,f;
	for(int &i=cpy[u];i;i=e[i].nxt){
		int v=e[i].v,w=e[i].w;
		if(dep[u]==dep[v]+1&&(f=dfs(v,min(w,minw)))){
			minw-=f,flow+=f,e[i].w-=f,e[i^1].w+=f;
			if(!minw) break;
		}
	}
	return flow;
}
inline int dinic(){
	int maxflow=0;
	while(bfs()) maxflow+=dfs(s,INF);
	return maxflow;
}
inline void solve(){
	scanf("%d%d",&n,&m);s=n+1,t=s+1;int total=t; 
	clear();
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	for(int i=1;i<=n;++i) add_edge(s,i,1),las[i]=i;
	for(int i=1;i<=m;++i){
		int u,v;scanf("%d%d",&u,&v);
		total+=2;
		add_edge(total-1,total,1);
		add_edge(total,total-1,1);
		add_edge(las[u],total-1,a[u]);las[u]=total-1;
		add_edge(las[v],total,a[v]);las[v]=total;
	}
	++total;
	add_edge(las[1],total,a[1]);
	add_edge(total,t,INF);
	printf("%d\n",dinic());
}
int main(){
	int T;scanf("%d",&T);
	while(T--) solve();
	return 0;
}

Day 4

T1 度数

一个结论是说，如果原图中所有点度数都 \(\geq 2\)，那么最严的限制 \((x_i=y_i=1)\) 也可以满足。具体做法大概是构造欧拉回路，对于那些度数为奇数的点，先在它们之间连一些虚边，最后再删去。因为欧拉回路保证了入度等于出度，所以直接通过欧拉回路定向即可。

对于一般的情况，考虑先把一度点讨论一下然后删掉，顺带着出来的一度点全删完，动态更新其他点的度数。搞完之后就和上面一样了。

讨论的过程大概就是说，因为只有一个度，所以不能满足两个条件；如果只有一个条件就直接确定，如果没有条件需要满足那就直接当作 \(\geq 2\) 度点一起弄就行了。

如果没有 \(x_i,y_i\leq 1\)？或许可以上下界可行流。考虑每一条边定向相当于是给其中恰好一条边的入度加一，这个可以用网络流流量限制。对于那个 \(x_i\) 和 \(y_i\)，可以发现，这个限制就相当于给每个点 \(i\) 向 \(t\) 连的边限制了一个流量范围（过少会导致入度不够，过多会导致出度不够）。这就是有源汇上下界最大流模型，可以直接求解。

不知为何，dinic跑 \(10^5\) 毫无压力？？

#include
#include
#include
#include
#define rint register int
using namespace std;
inline int rd(){
	rint res=0;register char c=getchar();
	for(;!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar()) res=(res<<1)+(res<<3)+(c-'0');
	return res;
}
const int N=1.1e6+13,INF=0x3f3f3f3f;
struct Edge{int v,w,nxt;}e[N*10];
int n,m,s,t,S,T,lim,to[N],xx[N],yy[N],uu[N],vv[N],deg[N],h[N],tot=1,ad[N];
inline void add(rint u,rint v,rint w){
	e[++tot]=(Edge){v,w,h[u]};h[u]=tot;
	e[++tot]=(Edge){u,0,h[v]};h[v]=tot;
}
int dep[N],cpy[N];
bool vis[N];
inline bool bfs(){
	memset(dep,0x7f,sizeof(dep));
	memcpy(cpy,h,sizeof(h));
	memset(vis,0,sizeof(vis));
	queueq;
	q.push(T),dep[T]=0,vis[T]=1;
	while(!q.empty()){
		rint u=q.front();
		q.pop();
		for(rint i=h[u];i;i=e[i].nxt){
			rint v=e[i].v,w=e[i^1].w;
			if(!vis[v]&&w) dep[v]=dep[u]+1,vis[v]=1,q.push(v);
		}
	}
	return vis[S];
}
int dfs(rint u,rint minw){
	if(u==T||!minw) return minw;
	rint f,flow=0;
	for(rint i=cpy[u];i;i=e[i].nxt){
		cpy[u]=i;
		rint v=e[i].v,w=e[i].w;
		if(dep[u]==dep[v]+1&&(f=dfs(v,min(minw,w)))){
			minw-=f,flow+=f,e[i].w-=f,e[i^1].w+=f;
			if(!minw) break;
		}
	}
	return flow;
}
inline int dinic(){
	rint flow=0;
	while(bfs()) flow+=dfs(S,INF);
	return flow;
}
//小垃圾 ISAP
/*int gap[N<<1],dep[N],cur[N];
bool vis[N];
inline void bfs(){
	memset(dep,-1,sizeof(dep));
	queueq;
	q.push(T),dep[T]=0,gap[0]=1;
	while(!q.empty()){
		rint u=q.front();q.pop();
		for(rint i=h[u];i;i=e[i].nxt){
			rint v=e[i].v,w=e[i^1].w;
			if(dep[v]==-1&&w) dep[v]=dep[u]+1,++gap[dep[v]],q.push(v);
		}
	}
}
int dfs(rint u,rint minw){
	if(u==T||!minw) return minw;
	rint f,flow=0;
	for(rint &i=cur[u];i;i=e[i].nxt){
		rint v=e[i].v,w=e[i].w;
		if(dep[u]==dep[v]+1&&w){
			f=dfs(v,min(minw,w));
			if(f){
				minw-=f,flow+=f,e[i].w-=f,e[i^1].w+=f;
				if(!minw) return flow;
			}
		}
	}
	--gap[dep[u]];
	if(!gap[dep[u]]) dep[S]=lim+1;
	++dep[u],++gap[dep[u]];
	return flow;
}
inline int dinic(){
	rint maxflow=0;
	bfs();
	while(dep[S]<=lim){
		for(rint i=1;i<=lim;++i) cur[i]=h[i];
		maxflow+=dfs(S,INF);
	}
	return maxflow;
}*/
int main(){
	//freopen("degree.in","r",stdin);
	//freopen("degree.out","w",stdout);
	n=rd(),m=rd();s=n+m+1,t=s+1;lim=n+m+4;
	for(rint i=1;i<=n;++i) xx[i]=rd();
	for(rint i=1;i<=n;++i) yy[i]=rd();
	for(rint i=1;i<=m;++i) uu[i]=rd(),vv[i]=rd(),deg[uu[i]]++,deg[vv[i]]++;
	for(rint i=1;i<=n;++i)
		if(xx[i]+yy[i]>deg[i]){puts("-1");return 0;}
	for(rint i=1;i<=m;++i){
		add(s,i+n,1);
		add(i+n,uu[i],1);
		add(i+n,vv[i],1);
	}
	for(rint i=1;i<=n;++i){
		if(deg[i]-yy[i]-xx[i]) add(i,t,deg[i]-yy[i]-xx[i]);
		ad[i]-=xx[i],ad[t]+=xx[i];
	}
	S=n+m+3,T=n+m+4;rint totflow=0;
	for(rint i=1;i<=lim;++i){
		if(ad[i]>0) add(S,i,ad[i]),totflow+=ad[i];
		else if(ad[i]<0) add(i,T,-ad[i]);
	}
	add(t,s,INF);
	if(dinic() q;
	q.push(T);d[T]=0;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=h[u];i;i=e[i].nxt){
			int v=e[i].v,w=e[i^1].w;
			if(w&&d[v]==-1) d[v]=d[u]+1,q.push(v);
		}
	}
	return d[S]!=-1;
}
struct Node{
	int u,d;
	bool operator <(const Node &a)const{return d q;
inline void init(){
	for(int i=h[S];i;i=e[i].nxt){
		int v=e[i].v,w=e[i].w;
		if(w){
			e[i].w=0,e[i^1].w=w,flow[S]-=w,flow[v]+=w;
			if(v!=S&&v!=T&&!vis[v]) q.push((Node){v,d[v]}),vis[v]=1;
		}
	}
}
inline void push(int u){
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].v,w=e[i].w;
		if(d[u]==d[v]+1&&w){
			int f=min(flow[u],w);
			e[i].w-=f,e[i^1].w+=f,flow[u]-=f,flow[v]+=f;
			if(v!=S&&v!=T&&!vis[v]) q.push((Node){v,d[v]}),vis[v]=1;
			if(!flow[u]) break;
		}
	}
}
inline void relabel(int u){
	d[u]=INF;
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].v,w=e[i].w;
		if(w&&d[u]>d[v]) d[u]=d[v];
	}
	++d[u];
}
inline void reset(int u){
	for(int i=1;i<=lim;++i)
		if(i!=S&&i!=T&&d[i]>d[u]&&d[i]<=lim) d[i]=lim+1;
}
inline int dinic(){
	if(!bfs()) return 0;
	d[S]=lim;
	for(int i=1;i<=lim;++i){
		if(d[i]!=-1) ++gap[d[i]];
	}
	init();
	while(!q.empty()){
		int u=q.top().u;q.pop();vis[u]=0;
		push(u);
		if(flow[u]){
			--gap[d[u]];
			if(!gap[d[u]]) reset(u);
			relabel(u);
			++gap[d[u]];
			q.push((Node){u,d[u]});vis[u]=1;
		}
	}
	return flow[T];
}*/ 

T2 数位

暴力做法是从低到高为 dp 然后状压每一位的进位状态。考虑怎么优化？因为如果有一个很小的数进位了，那么一个很大的数也一定会进位。每一层转移的顺序是一样的，所以可以排序一下。注意层与层之间是不一样的。然后注意前导零的限制。

T3 跳跃

首先能够得到这样一个结论：当且仅当根节点 \((1)\) 为直径中点的时候，先手必败。然后考虑树形 \(dp\)，用 \(f_{u,j}\) 表示以 \(u\) 为根的子树，割出一个最大深度为 \(j\) 的连通块，然后考虑用 \(f_{v,k}\) 去更新它即可，可以证明复杂度是 \(O(n^2)\)。计算答案的时候用一个背包来做，考虑一个一个把子树加进去计算答案即可。复杂度 \(O(n^2)\)，期望得分 \(56\)。（虽然没人写出这个部分分……）

发现这个数组第二维是跟深度有关的，这是一个长链剖分的模型，把每个点和往下深度最深的那个儿子连边形成长链剖分结构。如果只花费长链上的点来合并，相当于一个点只会被并一次，这样复杂度可以证明是 \(O(n)\)。

设 \(g_{i,j}\) 表示 \(i\) 为根的子树最深深度为 \(j\) 的答案，考虑这个转移可以化成一个 \(\max\) 卷积的形式，常见的做法就是前缀和，化卷积为点积（普通的卷积直接DFT）。然后考虑乘的时候打一个全局乘的标记，然后分几部分考虑合并带来的影响。

线性求一个数组的所有数的逆元：考虑把所有数乘起来，然后求一次逆元，然后再乘回去就行了。

Day 5

T1 即得

答案肯定是一棵树，然后设 \(f(S)\) 为不通过别的点就能连通的最小代价，然后dp的时候做一个后缀和就可以做到 \(O(n\cdot 2^n)\)。

T2 易见

建立序列自动机，询问 \([l,r]\) 相当于是求 \([l,r]\) 中的点形成的 DAG 路径条数，然后好像是分治作线头dp

设 \(g_l(i,j)\) 表示本质不同的截线左侧的方案数，然后可列出转移方程为 \(g_l(l,1..|\sum|)=1,g_l(i,j)=g_l(i-1,j)+g_l(i-1,s_{i-1})\)。

然后可以写成矩阵形式，然后一大堆看不懂的操作做到了 \(O((n+q)|\sum|)\)。

T3 平凡

考虑记 \(f(i)\) 为以 \(i\) 为根的子树中经过 \(i\) 的路径数，\(g(i)\) 为整个树上经过 \(i\) 的路径数。然后对每种颜色建虚树，分别考虑边和点的贡献，用树上差分实现。然后考虑更新的时候在虚树上打标记……反正就是很阴间的东西。

然后有 \(O(n)\) 做法是基数排序加分块压位稀疏表……

Day 6

模拟赛：

T1 清风

CF838D。神仙题。

考虑首先加一个点化链为环，然后如果没有限制，方案数是 \(2^m(n+1)^m\)，然后因为环上位置是等价的，所以每个位置不被拿走的概率为 \(\frac{n-m+1}{n+1}\)，所以答案为 \(2^m\cdot(n+1)^{m-1}\cdot (n-m+1)\)。

T2 半夜

\(O(n^3)\) 的dp很简单，然后优化的时候可以通过网格图来推出两维上的单调性，然后预处理单调性的拐点即可 \(O(n^2)\) 解决。

T3 鸣蝉

%%%%%%zrz!zrz!zrz!

神仙题。考虑把两个块的集合 bitset & 起来，然后一定带一个 \(\frac{n}w\) 的复杂度。所以分块分 \(w\) 块，然后考虑卡常就是把只出现一次的数前缀和维护，这样就可以做到 \(\frac{n}2\)。总时间复杂度 \(O(\frac{n^2}{w})\)，然后空间复杂度 \(O(n\log w)\)，可以通过此题。

Day 7

模拟赛：

T1 体积

考虑设截面面积为 \(S(h)\)，答案即为 \(\int S(h) dh\)。可以将 \(S(h)\) 分解成 \(a(h)\times b(h)\)，其中 \(a(h)\) 和 \(b(h)\) 分别为 \(x\) 轴和 \(y\) 轴方向上线长。这样就可以分段求积分了……

T2 Number

考虑答案等价于 \(C_n^i\) 在 \(p\) 进制意义下末尾有至少 \(k\) 个 \(0\) 的方案数。然后拆开 \(C_n^i\)，问题转化为求 \(n!\) 在 \(p\) 进制意义下末尾有多少个 \(0\)。注意到 \(C_n^i=\frac{n!}{i!(n-i)!}\)，那么 \(n!\) 与 \(i!(n-i)!\) 的差至多为 \(1\)，考虑直接dp统计进位即可。

T3 编码

注意到出现的不同的概率共有 \(C_{n+3}^3=1771\) 种，所以可以直接对这部分跑哈夫曼编码，然后因为每一次合并都会使集合里的数量减半，所以复杂度可以保证。

Day 8

模拟赛：

T1 CF722F

一种做法是考虑CRT+ST表，然后比较麻烦。还有一种做法是说，考虑用双指针扫这个东西，然后删除相当于需要维护区间 \(\operatorname{lcm}\)，直接对每个质因数维护一个前缀和或者单调队列即可。

std做法是考虑每个同余方程相当于是对 \(x\) 产生了一些贡献，然后考虑这些贡献之间的关系？

T2 CF1063F

首先注意到答案一定是选长度为 \(l,l-1,\ldots,2,1\) 的一些子串，然后考虑dp这个长度。注意到 \(f(i+1)\geq f(i)-1\)，这样就可以直接从大到小枚举，SAM或者SA+线段树判断，复杂度 \(O(n\log n)\)。

T3 CF814E

结论大概是建出树来之后只能在同一深度连边，于是bfs序+dp可以 \(O(n^5)\) 解决。优化就是考虑什么情况会有贡献，然后好像是个时间和空间都是 \(O(n^3)\) 的做法。还可以做到 \(O(n^2)\)。

Day 9

模拟赛:

T1

注意到这个答案相当于是关于 \(r\) 的一个多项式，然后这个答案为 \(\sum_{i=l}^r a_i\times p_i(r)\)，其中 \(p\) 就是关于 \(r\) 的多项式，然后大概是用树状数组维护多项式和？

T2

考虑用一个栈或者堆维护列上的每个位置，然后用线段树维护横向区间高度最小值，那么一个做法是在线段树的叶子节点上开一个堆。

T3

考虑设 \(A(x),B(x)\) 表示 \(A,B\) 点在 \(x\) 时间的位置，那么如果 \(\operatorname{dist}(A(t),B(t+r))=r\)，表示有一个解，同理如果 \( 表示还有一个更小的解，如果对于任意 \(t\) 均 \(>r\) 则解一定 \(>r\)。所以可以二分 \(r\)，然后设 \(C(x)=A(x)-B(x+r)\)，注意到这相当于是两个一次函数相减，所以 \(C(x)\) 也是折线，然后直接枚举每个折距离原点的距离最小值即可。

Day 10

模拟赛：

T1 CF840C

首先把每个数去掉质因子次数模 \(2\)，转化成相邻位置不一样的方案数。然后考虑设一个dp，\(dp_{i,j}\) 表示处理了 \(i\) 个数，有 \(j\) 个相邻位置相同的方案数，直接考虑往里边插即可 \(O(n^3)\) 得解。还有一个做法是考虑容斥，然后可以用类似背包的转移？复杂度是 \(O(n^2)\)，利用分治FFT可以做到 \(O(n\log^2 n)\)。

T2 P7058

首先有一个很显然的dp，然后把那个块拆成两个好维护的块，每个点都查一次然后并一次。可以用正反预处理之后 \(O(1)\) 判断，复杂度 \(O(n^2)\)。

T3 CF674F

\(Ans=\sum_{i=0}^n C_n^i\times d^i\)，证明就是你构造一种方案，让第 \(i\) 天倒的人在那一天去喝第 \(j\) 瓶酒，并且在这之前不喝这一瓶即可。也可以考虑dp。

专题授课

Day 1

图论杂题

Jump

考虑做一次操作，\(x\) 会变成 \(2a_i-x\)，把很多次操作展开成 \(2(a_k+...+(-1)^ka_1)+(-1)^kx\)，然后先对前面那个东西求一个最短路，每次查询先讨论一下 \(k\) 的奇偶性，直接查即可。复杂度 \(O(nv+q)\)。

Today is a rainy day

先做 \(2\) 再做 \(1\)，本质不同的 \(2\) 顺序有 \(O(6^6)\) 种，直接 \(O(6^6\cdot n)\) 枚举即可。

Walk

条件说的是，考虑状压的话有包含关系。第一种连边方式，建虚点拆成几条边，每条边只跟比自己小 \(1\) 的子集连边即可。复杂度是 \(O(n+v\log v)\)。

树上传送

需要用到点分树。

类似NOI2019弹跳，似乎是建点分树把点拆成 \(\log n\) 个分治中心，然后优化dijkstra。

弹跳那个题大概就是主席树优化建图的dij，但是空间不够，可以直接线段树套 set，在线段树上模拟跑dij的过程即可。

那个题是 \(1 \log\) 的，这个题加上点分树应该是 \(2\log\)。

Travel

如果 \((1,n)\) 是较小的，直接输出。

否则讨论 \(a,b\) 的大小关系，直接正着或者反着bfs即可。

Kirakira

做法一：\(f_i-f_{i-1}=n-\sigma_1(x)\)，线筛+前缀和

做法二：随机在 \(\frac{n(n-1)}{4}\) 附近搞就行了。

生成树的另一种做法：Boruvka

每个点选距离最近（最小）的点连边，缩联通块。复杂度 \(O(\)每次找边复杂度\(\log n)\)。

新年的繁荣

生成树计数：Matrix-tree 定理，使用Laplacian矩阵，去掉第一行和第一列的余子式。边权可以体现为重边或者多项式。

有向图欧拉回路计数：BEST定理，对于非空且每个点的入度等于出度的有向图可以使用：\(Ans=T(r)\prod_{u\in V}[(deg(u)-1)!]\)。重边互不可区分需要用 Burnside 引理。

Expectation

相同的 \(a\) 的个数是 \(30\)，考虑 \(Kruskal\) 的过程中，对于相同的 \(a\)，加进去边之后连通块是固定的，直接跑 \(Matrix-tree\) 即可。复杂度 \(O(30^2m)\)。

Flag

二分答案之后转化成 \(2-SAT\) 问题，把数轴按区间长度分块，对于两段分别前后缀和优化即可。复杂度 \(O(n\log v)\)。

Day 2

Rooms

把每个连通块选一个关键点，用二维前缀和预处理出块的关键点个数。加强版是今年USACO一月或者二月的题。

Bajtocja

考虑用哈希值维护每个点在所有图中在哪个连通块内，然后每次加边之后判哈希值即可。

数据结构杂题：

Siano

先按 \(a_i\) 排序，然后大概就是区间推平和修改，可以单 $\log $ 解决。

动态图

线段树分治，并查集改成带权？（不会）

直径

求出 \([a,b]\) 和 \([c,d]\) 的直径，然后实际上最大的就是直径的两个端点之间最长的路径。

Painting Edges

线段树分治？

Segment

李超树

一些科技：

楼房重建

Election

线段树+vector+单调队列？

等差数列

P5278

满足三个条件，分别用主席树等数据结构维护即可。

Good Sebsequences

暴力做法：莫队+扫描线？

然后可以用区间历史最值线段树做 \(O(n\log n)\)

然后还能用到一个科技叫做析合树： https://oi-wiki.org/ds/divide-combine/

Odwiedziny

根号分治。

Bear and Chemistry

虚树+tarjan判边双，直接暴力做即可。

Duff is Mad

CF587F。

Matches Are Not a Child’s Play

CF1137F

Day 3

概率期望与组合数学

AGC028B

考虑算出每条线段的期望贡献然后再乘以 \(n!\) 可以得到答案。然后考虑对删除时间建笛卡尔树（小根），每个点的期望贡献次数就是在笛卡尔树上的期望深度。发现这个可以转化成其他 \(n-1\) 个点在它之前删除的概率之和。

如果 \(j，\(j\) 在 \(i\) 之前删除的概率是 \(\frac{1}{i-j+1}\)，反过来同理。设 \(H_i=\sum_{j=1}^i \frac{1}{i}\)，那么 \(E(i)=H_i+H_{n-i+1}-1\)，然后就做完了。

CF605E

正着做不太好做，考虑倒过来，设 \(E_i\) 表示从 \(i\) 到 \(n\) 的期望，那么 \(i\) 会走到 \(j\) 当且仅当所有 \(E_k 的 \((i,k)\) 都不出现，同时还要规避掉自环的情况。然后这个东西是有后效性的，可以使用类似 dijkstra 的方式，每次固定最小的转移即可。

P5400 [CTS2019]随机立方体

什么是二项式反演？

[FJOI2019] 某道题

Circles of Waiting CF963E

游走型期望题，一般是把终点看做 \(0\)，然后求起点的期望。主元法优化高斯消元？

然后就……没了……

Day 4

CF杂题：

Goods transportation CF724E

很明显像是一个最大流，但是数据范围不允许，所以考虑最大流最小割定理，然后用dp求最小割。具体的dp可以直接 \(O(n^2)\) 暴力，也可以用一些奇奇怪怪的优化做到 \(O(n\log n)\)。

Julia the snail CF793F

粉兔出锅了，待补。

April Fools’ Problem (hard) CF802O

这个题看起来像是个费用流，由于数据范围原因所以考虑用线段树模拟费用流，然后加边和删边都是维护一段区间。

Dirty Arkady’s Kitchen CF827F

大概是考虑可以在一条边上反复横跳，所以到一个点的时间可以分奇偶讨论拆点。然后跑最短路的时候考虑到达区间合并即可。

Day 5

知识点：线性代数与多项式

例题1

把每 \(64\) 位的数看作 \(\mod 2\) 意义下的高维向量，然后异或什么的就是向量左乘一个矩阵，做矩阵快速幂。

多项式知识点：

点值表示、下降幂表示

拉格朗日插值

两类斯特林数

单位根反演

\([n|k]=\frac1n \sum_{j=0}^{n-1}(\omega_n^j)^k\)

生成函数及其运算（快速莫比乌斯变换，快速沃尔什变换）

集合幂级数的三类卷积

另：\(114514\) 是 \(998244353\) 的原根！！！

Day 6

知识点：不定方程与积性函数

裴蜀定理与exgcd；乘法逆元及其各种算法；解线性同余方程组；阶及其求法；原根；BSGS；

Chef and Prime Divisors(CC May15)

考虑设 \((A^\infty,B)\) 为 \(A\) 的很高次幂和 \(B\) 的 \(gcd\)，则 \(B=(A^\infty,B)\iff \frac{B}{A}=(A^{\infty},\frac{B}{A})\)
，然后可以辗转相除。\(O(T\log^2 n)\)。

失控的未来交通工具

好像是在生成树上取一个自由元，然后根据裴蜀定理得出需要维护的那个 \(\gcd\)，然后通过带权并查集维护，最后只需要求一个线性同余方程组的解即可。复杂度 \(O(n\log m+n\alpha(n))\)。

Falsyta in Tina Town(P3306)

先特判掉 \(k=0,1\) 的情况，然后展开式子化一化，然后就是需要求一个阶？？

猜数游戏(P6730)

另一道例题：二次剩余？Cipolla算法？指数提升引理？特征根？

还有一道例题：\(\operatorname{lcm}\) 用 \(\min-\max\) 容斥换为 \(\gcd\)。

循环之美 NOI2016

前面反正一顿化式子，最后化成要求 \(\sum_{i=1}^n \mu(i)[i\perp k]\)

设 \(f(n)=\mu(n)[n\perp k],S_f(n)=\sum_{i=1}^n \mu(i)[i\perp k]\)

构造 \(g(n)=[n\perp k]\)

直接狄利克雷卷积

然后直接杜教筛做完了。

Day 7

讲题：IOI2020集训队作业选讲

CF516D Drazil and Morning Exercise

有一个性质是，然后可以用树状数组+dfs序解决？

AGC032E AT3956 Inversions

Day 8

IOI2020国家队作业选讲

CF521E 先把赋值操作化为加法操作一起处理，最后如果选上了这个赋值操作，再调整它的位置到第一个做。

Feelings

Day 1

今天第一天，本来以为上来可能会跟不太上节奏，不太适应，但是感觉还不错。最近几周的训练感觉效果不错，至少对题目有了一定的想法，并且在实现上也不再会犯那么多低级错误了（虽然还是有）。从成绩来看还不错，预计得分 \(50+35+52=137\)，实际得分 \(45+20+56=121\)，整个班 \(rk18\)——算是在省队集训班考试成绩最好的一次了（去年也是这个班，三四十个人我最好考过二十几名）。

上来之后的开题顺序理性了不少。首先看到T3的阴间数据范围，感觉不太可做，便打了三个 Subtask 的暴力，其中有一个状压分层图bfs/dfs，打的很顺手，基本上在三四十分钟就打出了 \(52pts\)，感觉心里比较稳。然后T2是个博弈论，感觉是Nim游戏但是已经忘了怎么做了，就先去看了T1。看T1的时候想到了一个结论，但是感觉这个结论是 \(60pts->100pts\)，发现了之后只能获得 \(15pts\)，觉得很奇怪，便尝试去写 \(O(n^3)\) 的 \(30pts\) 暴力。其实当时想到这里，已经跟正解十分接近了，但由于枚举顺序的不同，导致没有想到另一个比较好想的结论，于是打了 \(50pts\) 暴力滚粗了。事实上最后这道题A掉的人不少，大概有十个左右，还是比较可惜的。打完之后大概是十一点二十，回去看T2。这时候也不是很着急了，但是T2的最低一层部分分都不会做还是不行的。从头开始仔细的推了一下局面的性质，先手必胜和先手必败的条件，我首先发现每堆石子的异或和为 \(0\) 的时候一定是先手必败的。于是就想到，如果要使局面的异或和为零，实际上就是需要满足 \(\exists i\in[l,r],b_i\oplus z。这样就能推出统计 \(z\) 的二进制最高位为 \(1\) 的石子数量的结论。想到这里就可以做 Subtask \(1,2,3,5\) 了，但是当时已经快十二点半了，我拼命的打了快 \(200\) 行，最终还是功亏一篑，没打完 \(55pts\)，打了 \(35\)。

考完之后朱老师过来说他切了T2，我想了想好像的确是个区间最值线段树，之前好像看过但是忘了怎么实现了。不得不说朱老师还是神啊。中午吃完饭出分，虽然挂了一点但还不错。挂分的主要原因还是最后打的太急了，两个地方忘了开long long，然后判断Subtask的时候条件还打错了……不过总体来说还是很可观的！继续加油！

感受到了来自NOI图论的压力……

之前听过一段时间zr，知道这种课基本是听不懂的，能听懂多少算多少。今天刚开始的时候，还是能感觉到最近的进步的。一些题目虽然自己还是没什么思路，但是听完老师说的之后，能够差不多理解并且抽取出里边的核心部分。但是后面开始讲 \(Matrix-tree\) 定理和 \(BEST\) 定理的时候，包括再往后的一些，题目和算法就听不太懂了。毕竟是这么多难的算法，也不能强人所难非要一天学会，知道自己还是有很大的知识漏洞，以后要抓紧时间补就好了。总体来说，今天收获很大，但是也暴露了一些问题，希望明天能再接再厉！加油！

Day 2

今天一路骑自行车来的，记得去年初三的时候，也是骑着自行车，在推荐生结束之后匆匆赶来看了一眼 SDOI2020 的考场，还蹭了张合照……转眼间，已经过去快一年了啊。一年的时间足以改变很多事情，但不得不说，燕子山这个大坡还是真的大啊……

开题之后瞬间自闭。DFS序线段树？不会。字符串哈希？不太懂。多源BFS？什么阴间东西。还说什么“我已经完全理解了”，看起来今天的题不太可做啊。开题先想了想T1，发现每个点肯定最多只会被加一次，这样就可以用一个树形dp来先求出取到最小值的时候被加的有哪些点。但是看到要输出方案，我感觉我连最低档的部分分都不会写……然后去看了T2和T3，T2是一个随机题，一看就不是什么正经题，做法肯定是什么随机化乱搞，我也不会，所以索性就打个 \(O(n^2)\) 的暴力滚粗了。然后还自作多情地把肯定超时的点打了个卡时限的随机化上去，想着先稳 \(30pts\) 再说。T3看起来像是个计算几何，反正要推很多式子，然后我连 \(n\leq2\) 的做法都推不出来。后来想着可能还有个容斥在里边，但是我也不会。所以就先打了个 \(O(k^2\log k)\) 的纯暴力BFS，只能过三个点。这时候大概是十点多吧，旁边的lrz已经快要把T1切了。看着他一百四五十行的代码，好像还有各种线段树操作，我感觉很难办。可能今天要爆零了。然后仔细思考那个树形dp之后的构造。首先想到的是，可以从底往上构造方案，只要能保证每一次合并儿子的子树之后，假设这个点下面有 \(siz_u\) 个叶子，那就满足 \(val_i\in [1,siz_u]\)。这样每个点可以把儿子合并，就打个标记，然后最后再用一次dfs下传标记即可。但是复杂度是 \(O(n)\) 啊！看着 \(n\leq 2\times 10^5\) 的数据范围，还有一个不知道干什么的 \([1,10^9]\) 值域，然后就很慌。不管了先糊一个上去。然后大概十点半或者十一点开始写，写完之后调了半天，一直出各种错误，因为这个东西的确是比较难维护……写的时候也不大清醒了，\(flag\) 和 \(up\) 的意义都搞不明白了。反正用自己写的checker找错找了好多组数据，又是输出中间变量，又是调试，总归是把方案搞出来了。先不管是不是花费最少，至少不会出现两个同样值的叶子了。开始拍之后我心里还是比较舒服的，不管拿多少分了，反正感觉还不错。最后半个小时基本划水了，T3的式子不会推，T2的随机也不会写，然后就交了。

这样的话，期望得分 \(0-100+30+12=42-142\)，最低分还是有点低的，但是万一T1过了呢？

吃饭的时候，神峰说T1正解是可并堆，然后我感觉我做法更假了……亓神发现了T2随机的本质，然后也切了。感觉今天要崩的节奏啊，毕竟没打多少暴力。吃完饭回来，跟朱老师连了一把，然后还是没测到我的，就又开了一局国际象棋。下着下着觉着时间差不多了，又跑过去看，发现我T1居然真过了！然后T2由于数据随机，居然放了我 \(65pts\)！后来一问才知道，直接写 \(O(n^2)\) 的暴力都能过 \(70pts\)……合着还负优化了。

总分 \(100+65+12=177\)，算是有史以来得分最高的一次了！排名也继续刷新PR，\(rk14\)，甚至超过了部分队爷！很开心！

拖了一个小时的堂……而且净讲一些 *3400 的阴间数据结构题……

之前由于做过几道LCT，就感觉自己数据结构还可以，实际上还是小萌新。一个是有很多基础知识还没学，还有一个是很多经典做法都不知道。总之还是看的题太少了。虽然比起以前，比起去年，能稍微多听懂一些了，但是还是需要更多努力才能填补知识漏洞！比起亓神李神，我的时间已经不多了，希望能抓紧一切时间，提升自己实力，不留遗憾。

Day 3

前几天得分虚高，今天终于中和了一下……

感觉昨天晚上打比赛还是对今天状态影响很大。主要是不太想推式子，只是停留在感性理解，所以其实T1我已经想的跟正解结论很接近了，但是没能做出来。当时只是想到了，如果最小循环节太长了，那么实际上选择更小的循环节会更优，但是并没有仔细推式子，只打了 \(18\) 个字符串来当作最小循环节。对拍的时候发现错误，就直接放弃了，以为这个做法错了。实际上再冷静下来重新思考一下，就完全能做出来的。然后T3打完暴力才发现没有暴力分，白白浪费了二十分钟……T4实际上如果能再多花一会，是有机会做出来的，但是看到 \(3000\) 的数据范围就没往网络流上思考，导致没能做出来。今天的期望得分和实际得分一样，\(10+0+20=30\)，由于有一些爆零的同志，所以没垫底。今天在做题策略和方法上都出现了一定的问题，实际上有希望拿 \(200\) 的场只得了 \(30\)，应该好好反思，明天继续加油！

下午听了几道题就下线了……先补了会觉，实在是太困了，然后又起来补了补前几天的题。今天下午讲的概率期望还有组合数学，基础知识我一个也听不懂，所以上来两三道简单题之后就听不懂了。什么二项式反演，什么拉格朗日反演的，听的迷迷瞪瞪的。这方面的确学的太少，以后有时间慢慢来吧。

Day 5

今天到的早一点，没迟到！

开题之后先看T1，发现那个什么“最小斯坦纳树”完全不会，然后就学了一波板子，发现就是个状压dp加最短路。然后这题当然是加强了的，所以只打了 \(52pts\) 暴力。打完暴力之后两个Sub对拍结果一直报错……然后调了很久，最后发现是斯坦纳树没有先跑floyd求多源最短路……虽然我也不知道这为什么错了。然后这时候已经十一点了，想去打T2暴力，结果突然想到可以枚举点集直接跑最小生成树，写了个 \(O(m\cdot 2^n)\) 做法，能有 \(72pts\)。然后想直接状压选取点状态dp，但是无论怎么考虑总觉得复杂度是 \(O(n^2\cdot 2^n)\) 的。所以就放弃了T1开T2。T2直接想了一个 \(O(n^2+q)\) 的做法，然后dp式子的贡献一直算错，后来就着旁边的 @lrz 的样例才调出来的。然后T3直接写了个暴力中的暴力，枚举四个点然后判断……期望得分 \(76+40+10=126\)。然后实际得分 \(76+0+0=76\)，T3不知道为何挂了，然后T2输出了测试数据所以爆零了……然后就垫底自闭了。