本来想写个last什么的还是算了，毕竟是越来越菜了

考试经过

T1：直觉告诉我不可做，然而我不相信我的直觉，于是两个小时过去了，暴力x1
T2：第一眼，时光倒流；第二眼，这啥啊。。。暴力x2
T3：我会扫描线，我会，我会……个鬼，暴力x3
T4：暴力x4（对就这么直接）
很难进行评价

T1.法阵

原题3100，张口放T1
情况需要分类讨论，主要是把模型抽象出来

发现左右的黄色被分成了两个部分，那么可以枚举中间的分界线\(i\),然后再枚举\(A,B\)的位置
实际上轮廓可以表示成走地图的形式，就是从四个角走到对应位置的方案数，于是可以组合数
暴力\(nm^2\)，前缀和优化可以\(nm\),然后考虑反过来，就是整个图关于\(y=x\)对称，直接交换\(n,m\)
注意做第二遍的时候要限制\(j-k>=1\)，否则都是两个联通块会算重
最后答案要乘2，因为可以完全对称过来再构造方案

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
const int N=4050;
int n,m,ans,sum[N];
int jc[2*N],inv[2*N],jcny[2*N];
inline void pre()
{
	jc[0]=jc[1]=inv[1]=jcny[0]=jcny[1]=1;
	for(int i=2;i<=4049;i++)
	{	
		jc[i]=jc[i-1]*i%mod;
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
		jcny[i]=jcny[i-1]*inv[i]%mod;
	}
}
inline int C(int x,int y)
{
	assert(x>=0);assert(y>=0);
	if(x<y)return 0;if(!y)return 1;
	return jc[x]*jcny[y]%mod*jcny[x-y]%mod;
}
signed main()
{
	freopen("magic.in","r",stdin);
	freopen("magic.out","w",stdout);
	cin>>n>>m;pre();
	for(int i=1;i<m;i++)
	{	
		memset(sum,0,sizeof(sum));
		for(int j=1;j<n;j++)sum[j]=(sum[j-1]+C(m-i+j-1,m-i)*C(m-i-1+n-j,m-i-1)%mod)%mod;
		for(int j=1;j<n;j++)ans=(ans+C(i+n-j-1,i)*C(i-1+j,i-1)%mod*sum[j]%mod)%mod;
	}
	swap(n,m);
	for(int i=1;i<m;i++)
	{		
		memset(sum,0,sizeof(sum));
		for(int j=1;j<n;j++)sum[j]=(sum[j-1]+C(m-i+j-1,m-i)*C(m-i-1+n-j,m-i-1)%mod)%mod;
		for(int j=1;j<n;j++)ans=(ans+C(i+n-j-1,i)*C(i-1+j,i-1)%mod*sum[j-1]%mod)%mod;
	}
	cout<<ans*2%mod<<endl;
	return 0;	
}	

T2.连通块

似乎是模拟15的原题，然而考场依旧不会
倒着处理询问，把删边改成加边
事实上最远距离就是到直径端点的距离，因此只要维护直径就行了
跟那道题一样，分情况并查集，记录两个端点

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=200050;
struct node{
	int from,to,next,op;
}a[2*N];
int head[N],mm=1;
inline void add(int x,int y)
{	
	a[mm].from=x;a[mm].to=y;
	a[mm].next=head[x];head[x]=mm++;
}
int d[N],fa[N],size[N],son[N],top[N];
bool v[N];int f[N],n,m,op[N],c[N],pa[N],pb[N];
inline int find(int x)
{	
	if(f[x]!=x)f[x]=find(f[x]);
	return f[x];
}
void dfs1(int x)
{
	v[x]=1;
	for(int i=head[x];i;i=a[i].next)
	{
		int y=a[i].to;
		if(v[y])continue;
		d[y]=d[x]+1;fa[y]=x;
		dfs1(y);size[x]+=size[y];
		if(size[y]>size[son[x]])son[x]=y;
	}
	size[x]++;
}
void dfs2(int x,int h)
{
	if(!x)return;v[x]=1;
	top[x]=h;dfs2(son[x],h);
	for(int i=head[x];i;i=a[i].next)
	{	
		int y=a[i].to;
		if(v[y]||y==son[x])continue;
		dfs2(y,y);
	}
}
inline int getlca(int x,int y)
{
	int fx=top[x],fy=top[y];
	while(fx!=fy)
	{
		if(d[fx]<d[fy])swap(fx,fy),swap(x,y);
		x=fa[fx],fx=top[x];
	}
	if(d[x]<d[y])swap(x,y);
	return y;
}
inline int getd(int x,int y)
{
	int lca=getlca(x,y);
	return d[x]+d[y]-2*d[lca];
}
inline void gan(int id)
{
	int x=a[id].from,y=a[id].to;
	int fx=find(x),fy=find(y);
	if(fx==fy)return;
	int p1=pa[fx],p2=pb[fx],p3=pa[fy],p4=pb[fy];
	f[fy]=fx;int ma=getd(p1,p2);
	int s1=getd(p1,p3),s2=getd(p1,p4),s3=getd(p2,p3),
		 s4=getd(p2,p4),s5=getd(p3,p4);
	if(s1>ma)ma=s1,pa[fx]=p1,pb[fx]=p3;
	if(s2>ma)ma=s2,pa[fx]=p1,pb[fx]=p4;
	if(s3>ma)ma=s3,pa[fx]=p2,pb[fx]=p3;
	if(s4>ma)ma=s4,pa[fx]=p2,pb[fx]=p4;
	if(s5>ma)ma=s5,pa[fx]=p3,pb[fx]=p4;
}	
vector <int> ans;
signed main()
{
	freopen("block.in","r",stdin);
	freopen("block.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<n;i++)
	{
		int x,y;scanf("%lld%lld",&x,&y);
		add(x,y);add(y,x);
	}
	d[1]=1;dfs1(1);memset(v,0,sizeof(v));dfs2(1,1);
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld",&op[i],&c[i]);
		if(op[i]&1)a[2*c[i]].op=a[2*c[i]-1].op=1;
	}
	for(int i=1;i<=n;i++)pa[i]=pb[i]=f[i]=i;
	for(int i=1;i<mm;i+=2)if(!a[i].op)gan(i);	
	for(int i=m;i>=1;i--)
	{
		if(op[i]&1)gan(c[i]*2);
		else
		{
			int x=c[i],fx=find(x);
			int p1=pa[fx],p2=pb[fx],d1=getd(p1,x),d2=getd(p2,x);
			ans.push_back(max(d1,d2));
		}
	}
	while(ans.size())printf("%lld\n",ans.back()),ans.pop_back();
	return 0;
}

T3.军队

先考虑每行的数量怎么求
扫描线是没问题的，关键是怎么处理\(k\)
显然不能暴力递归到叶子，我们线段树中维护最小的\(k\)个值的数值的数量
在合并的时候用归并的思想合并，然后处理完了扫一遍就行
回答询问二分出位置，剩下的前缀和处理就行

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pb push_back
#define pir pair<int,int> 
#define mp make_pair
const int N=300050;
inline int read()
{		
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
int n,m,c,k,q;long long sum[N],sum1[N],sum2[N];
struct node{
	int l,r,lazy;
	vector<pir> p;
}tr[4*N];
pir tmp[25];
inline void qi(int id)
{
	tr[id].p.clear();
	//merge(tr[id*2].p.begin(),tr[id*2].p.end(),tr[id*2+1].p.begin(),tr[id*2+1].p.end(),tmp+1);
	int p1=0,p2=0,s=0,tot=0,s1=tr[id*2].p.size(),s2=tr[id*2+1].p.size();
	while(p1<s1&&p2<s2)
	{
		if(tr[id*2].p[p1].first<=tr[id*2+1].p[p2].first)tmp[++tot]=tr[id*2].p[p1++];
		else tmp[++tot]=tr[id*2+1].p[p2++];
	}
	while(p1<s1)tmp[++tot]=tr[id*2].p[p1++];
	while(p2<s2)tmp[++tot]=tr[id*2+1].p[p2++];
	for(int i=1;i<=tot;i++)	
	{
		if(i!=1&&tmp[i].first!=tmp[i-1].first)tr[id].p.pb(mp(tmp[i-1].first,s)),s=0;
		if(tr[id].p.size()>=k)break;s+=tmp[i].second;
	}
	if(tr[id].p.size()<k&&s)tr[id].p.pb(mp(tmp[tot].first,s));
}
void build(int id,int l,int r)
{
	tr[id].l=l;tr[id].r=r;
	if(l==r){tr[id].p.pb(mp(0,1));return;}int mid=(l+r)>>1;
	build(id*2,l,mid);build(id*2+1,mid+1,r);
	qi(id);
}
inline void luo(int id)
{
	if(tr[id].l!=tr[id].r&&tr[id].lazy)
	{
		for(int i=0;i<tr[id*2].p.size();i++)tr[id*2].p[i].first+=tr[id].lazy;
		for(int i=0;i<tr[id*2+1].p.size();i++)tr[id*2+1].p[i].first+=tr[id].lazy;
		tr[id*2].lazy+=tr[id].lazy;tr[id*2+1].lazy+=tr[id].lazy;tr[id].lazy=0;
	}
}
void add(int id,int l,int r,int v)
{
	if(l<=tr[id].l&&r>=tr[id].r)
	{	
		for(int i=0;i<tr[id].p.size();i++)tr[id].p[i].first+=v;
		tr[id].lazy+=v;return;
	}
	luo(id);int mid=(tr[id].l+tr[id].r)>>1;
	if(r<=mid)add(id*2,l,r,v);
	else if(l>mid)add(id*2+1,l,r,v);
	else add(id*2,l,mid,v),add(id*2+1,mid+1,r,v);
	qi(id);
}
struct cge{int l,r,op;};
vector <cge> cc[N];
inline long long get1(int l,int r){if(l>r)return 0;return sum1[r]-sum1[l-1];}
inline long long get2(int l,int r){if(l>r)return 0;return sum2[r]-sum2[l-1];}
signed main()
{	
	freopen("army.in","r",stdin);
	freopen("army.out","w",stdout);
	n=read(),m=read(),c=read(),k=read(),q=read();
	for(int i=1;i<=c;i++)
	{
		int x=read(),y=read(),xx=read(),yy=read();
		cc[x].pb((cge){y,yy,1});cc[xx+1].pb((cge){y,yy,-1});
	}
	build(1,1,m);
	for(int i=1;i<=n;i++)
	{	
		for(int j=0;j<cc[i].size();j++)
		{
			cge ga=cc[i][j];
			add(1,ga.l,ga.r,ga.op);
		}
		for(int j=0;j<tr[1].p.size();j++)
		{
			if(tr[1].p[j].first>=k)break;
			sum[i]+=1ll*tr[1].p[j].second;
		}
	}
	for(int i=1;i<=n;i++)sum[i]=min(sum[i],1ll*m-sum[i]),sum[i]=-sum[i];sort(sum+1,sum+n+1);
	for(int i=1;i<=n;i++)sum1[i]=sum1[i-1]-sum[i],sum2[i]=sum2[i-1]+sum[i]*sum[i];
	for(int i=1;i<=q;i++)
	{
		int x=read(),y=read();
		long long s=y>>1,pp=upper_bound(sum+1,sum+n+1,-s)-sum-1ll;pp=min(pp,1ll*x);
		long long ans=s*(1ll*y-s)*pp+get1(pp+1,x)*y-get2(pp+1,x);
		printf("%lld\n",ans);
	}
	return 0;
}	

T4.棋盘

不会，咕了
要是不退役就补上

考试总结

心态还是不稳，不能被一道题搞崩
联赛的时候也应该注意时间分配和策略，如何快速评估题目难度，找到可做的题是个问题，不要反复跳题，控制思考时间
考虑每半个小时短暂调整一次，及时改变策略，争取拿到高分
倒计时在走，希望没有遗憾