日常签到失败

T1.签到题

所以现在的签到题都写着签到题了吗
结论题，考场没看出来，就死了，成功签到失败
下界是所有点如果连边为\(c\)的倍数则贡献为0，否则为1，答案确实是这个下界
证明需要用到二分图维津定理，扔链接就跑

#include <bits/stdc++.h>
using namespace std;
#define int long long
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;
}
const int N=1000050;
int n,m,k,c,du1[N],du2[N];
signed main()
{
	freopen("qiandao.in","r",stdin);
	freopen("qiandao.out","w",stdout);
	n=read(),m=read(),k=read(),c=read();
	for(int i=1;i<=k;i++)
	{
		int x=read(),y=read();
		du1[x]++;du2[y]++;
	}
	int ans=0;
	for(int i=1;i<=n;i++)if(du1[i]%c)ans++;
	for(int i=1;i<=m;i++)if(du2[i]%c)ans++;
	cout<<ans<<endl;
	return 0;
}

那么教训就是盲猜结论也是做题的一部分

T2.M弟娃

这才是签到题吧……
都是套路，dfs序线段树维护每个点的答案，每次考虑两个点的位置，若两点相同则全局答案加1，若lca不与任意一点相同则二者子树答案加1，否则整棵树除了这条链都加1，直接维护即可，边界稍微留意

#include <bits/stdc++.h>
using namespace std;
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;
}
const int N=300050;
struct node{
	int from,to,next;
}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++;
}
struct tree{
	int ma,lazy;
}tr[4*N];	
inline void luo(int id,int l,int r)
{
	if(tr[id].lazy&&l!=r)
	{	
		tr[id*2].lazy+=tr[id].lazy;
		tr[id*2+1].lazy+=tr[id].lazy;
		tr[id*2].ma+=tr[id].lazy;
		tr[id*2+1].ma+=tr[id].lazy;
		tr[id].lazy=0;
	}	
}	
void change(int id,int pl,int pr,int l,int r,int v)
{
	if(l>r)return;
	if(l<=pl&&r>=pr)
	{
		tr[id].lazy+=v;
		tr[id].ma+=v;return;
	}
	luo(id,pl,pr);int mid=(pl+pr)>>1;
	if(r<=mid)change(id*2,pl,mid,l,r,v);
	else if(l>mid)change(id*2+1,mid+1,pr,l,r,v);
	else change(id*2,pl,mid,l,mid,v),change(id*2+1,mid+1,pr,mid+1,r,v);
	tr[id].ma=max(tr[id*2].ma,tr[id*2+1].ma);
}
int d[N],sum,id[N],tot,t;
int f[N][20],size[N];bool v[N];
void dfs(int x)
{
	v[x]=1;id[x]=++tot;
	for(int i=head[x];i;i=a[i].next)
	{
		int y=a[i].to;
		if(v[y])continue;
		d[y]=d[x]+1;f[y][0]=x;
		for(int j=1;j<=t;j++)
		 f[y][j]=f[f[y][j-1]][j-1];
		dfs(y);size[x]+=size[y];
	}
	size[x]++;
}
inline int getlca(int x,int y)
{
	if(d[x]<d[y])swap(x,y);
	for(int i=t;i>=0;i--)
	{
		if(d[f[x][i]]<d[y])continue;
		x=f[x][i];
	}
	if(x==y)return x;
	for(int i=t;i>=0;i--)
	{
		if(f[x][i]==f[y][i])continue;
		x=f[x][i],y=f[y][i];
	}	
	return f[x][0];
}
inline void gan(int &x,int y)
{
	for(int i=t;i>=0;i--)
	{
		if(d[f[x][i]]<=d[y])continue;
		x=f[x][i];
	}
}
signed main()
{	
	freopen("magic.in","r",stdin);
	freopen("magic.out","w",stdout);
	int n,m;cin>>n>>m;t=log2(n)+1;
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		add(x,y);add(y,x);
	}
	d[1]=1;dfs(1);
	for(int i=1;i<=m;i++)
	{
		int x=read(),y=read();
		if(x==y)sum++;
		else
		{	
			int lca=getlca(x,y);
			if(lca==x||lca==y)
			{
				if(d[x]<d[y])swap(x,y);
				change(1,1,n,id[x],id[x]+size[x]-1,1);gan(x,y);
				change(1,1,n,id[x],id[x]+size[x]-1,-1);sum++;
			}
			else
			{
				change(1,1,n,id[x],id[x]+size[x]-1,1);
				change(1,1,n,id[y],id[y]+size[y]-1,1);
			}
		}
		printf("%d\n",tr[1].ma+sum);
	}
	return 0;
}

某oj较为卡常，要手动开O2

T3.变异大老鼠

发现每个点只有一个前驱，所以可以跑最短路记前驱然后建一棵树
然后就是树形dp了，写的子树合并

#include <bits/stdc++.h>
using namespace std;
const int N=310,M=50050;
const int exs=1e-9;
struct node{
	int from,to,next,w;
}a[2*M];
int head[N],mm=1;
inline void add(int x,int y,int z)
{	
	a[mm].from=x;a[mm].to=y;a[mm].w=z;
	a[mm].next=head[x];head[x]=mm++;
}
int dis[N],n,m,k,fr[N];
double p[N][N],f[N][N],g[N];bool v[N];
inline void dij()
{
	priority_queue <pair<int,int> >q;
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0;fr[1]=1;q.push(make_pair(0,1));
	while(q.size())
	{
		int x=q.top().second,w=-q.top().first;q.pop();
		if(v[x])continue;v[x]=1;
		for(int i=head[x];i;i=a[i].next)
		{
			int y=a[i].to;
			if(y==x)continue;
			if(dis[x]+a[i].w<dis[y])
			 dis[y]=dis[x]+a[i].w,q.push(make_pair(-dis[y],y)),fr[y]=x;
		}
	}
}
inline double gan(double x,int y)
{
	if(!y)return 0.0;
	return x/(double)y;
}
void dfs(int x)
{
	int size=0;memset(g,0,sizeof(g));
	for(int i=head[x];i;i=a[i].next)
	{
		int y=a[i].to;dfs(y);
		memset(g,0,sizeof(g));
		for(int j=0;j<=k;j++)
		 for(int p=0;p<=j;p++)
		  g[j]=max(g[j],gan(f[y][p],size+1)+gan(f[x][j-p]*size,size+1));
		for(int j=0;j<=k;j++)f[x][j]=g[j];
		size++;
	}
	memset(g,0,sizeof(g));
	for(int i=0;i<=k;i++)
	 for(int j=0;j<=i;j++)
	  g[i]=max(f[x][j]*(1-p[x][i-j])+p[x][i-j],g[i]);
	for(int i=0;i<=k;i++)f[x][i]=g[i];
}
signed main()
{
	freopen("arrest.in","r",stdin);
	freopen("arrest.out","w",stdout);
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);add(y,x,z);
	}		
	for(int i=1;i<=n;i++)for(int j=1;j<=k;j++)scanf("%lf",&p[i][j]);
	dij();memset(a,0,sizeof(a));memset(head,0,sizeof(head));mm=1;
	for(int i=2;i<=n;i++)add(fr[i],i,0);
	dfs(1);printf("%.6lf",f[1][k]);
	return 0;
}

T4.朝鲜时蔬

由于过于难以一句话描述所以另开一篇
有些受震撼

考试总结

考试技巧还是不太足，不要老想着正解，猜结论打表也很重要
心理能力要足够好，敢于面对一些（看起来）很毒瘤的题面
永远不要有“得xx分就够了的思想”，别人可能AK，不要弃疗