无一眼题，显然博主太菜

考试经过

状态持续低迷
前一个小时不知道在干啥，然后似乎认为T1很可做甚至有点像CSP的T1，于是肝，无果。。。
T2发现难点在于高精，然而时间撑不住，觉得可以通过贪心dfs啥的得到正解，就没咋细看
时间主要给了T3，推出了自认为正确的式子，然而发现过不了样例，全部输出之后发现会算重，想过改但是没有成功
此时发现只剩1.5h还爆零呢，于是速冲T170+T220，所以预计得分70+20+20=110
然而数据水了T2有50，T4最后特殊性质没冲上，继续被众人爆踩

T1.宝藏

子任务2询问次数远大于\(n\)，启发应该预处理出所有\(x\)的答案然后\(O(1)\)回答
考场上没发现的是对于\(x\)递增答案单调减，所以只要支持区间前\(k\)小的和的数据结构就行了
依然忘记了自己会权值线段树，线段树上二分即可，注意判递归到叶子节点的答案

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=300050,M=1000050;
int n,q,t,ans[N];
struct SGT{
	struct tree{
		int l,r,sum1,sum2;
	}tr[4*M];
	void build(int id,int l,int r)	
	{
		tr[id].l=l;tr[id].r=r;
		if(l==r)return;
		int mid=(l+r)>>1;
		build(id*2,l,mid);build(id*2+1,mid+1,r);
	}
	inline void qi(int id)
	{		
		tr[id].sum1=tr[id*2].sum1+tr[id*2+1].sum1;
		tr[id].sum2=tr[id*2].sum2+tr[id*2+1].sum2;
	}
	void change(int id,int p,int s)
	{
		if(tr[id].l==tr[id].r)
		{
			//assert(tr[id].l==p);
			tr[id].sum1+=s;
			tr[id].sum2+=p*s;
			return;
		}
		int mid=(tr[id].l+tr[id].r)>>1;
		if(p<=mid)change(id*2,p,s);	
		else change(id*2+1,p,s);
		qi(id);	
	}
	inline int er(int id,int k)
	{
		if(!k)return 0;
		if(tr[id].l==tr[id].r)return k*tr[id].l;
		if(tr[id*2].sum1>=k)return er(id*2,k);
		else return tr[id*2].sum2+er(id*2+1,k-tr[id*2].sum1);
	}
}tr1,tr2;
struct node{
	int w,t;
	friend bool operator <(node x,node y)
	{return x.w<y.w;}
}a[N];
signed main()
{
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	cin>>n>>t>>q;
	for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i].w,&a[i].t);
	sort(a+1,a+1+n);
	tr1.build(1,1,(int)1e6);tr2.build(1,1,(int)1e6);
	for(int i=1;i<=n;i++)tr1.change(1,a[i].t,1);
	memset(ans,-1,sizeof(ans));int p=1;
	for(int i=n;i>=1;i--)
	{
		tr1.change(1,a[i].t,-1);
		while(1)
		{
			int len=(p-1)/2;
			if(len>min(n-i,i-1)||p>n)break;
			int sum=tr1.er(1,len)+tr2.er(1,len)+a[i].t;
			if(sum<=t)ans[p]=a[i].w,p+=2;
			else break;
		}	
		tr2.change(1,a[i].t,1);
	}
	for(int i=1;i<=q;i++)
	{
		int x;scanf("%lld",&x);
		printf("%lld\n",ans[x]);
	}
	return 0;
}

数据结构的漏洞同时体现在代码能力和技巧上，看来应该把之前的补一下了

T2.寻找道路

贪心，把开始距离为0的点缩一起，可以用dfs，然后执行bfs
对于当前队列所有点，先取出来，把距离为0的能扩展到的点插进去，再把1插进去
复杂度线性，每个点总会被第一次更新到最优

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pr pair<int,int> 
#define mp make_pair
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;
const int mod=1e9+7;	
vector <pr> p[N];
int n,m,ans[N];bool v[N];
queue <int> q;
void dfs(int x)
{
	ans[x]=0;v[x]=1;q.push(x);
	for(int i=0;i<p[x].size();i++)
	{
		int y=p[x][i].first;
		if(p[x][i].second||v[y])continue;
		dfs(y);
	}
}
void bfs()
{
	dfs(1);memset(v,0,sizeof(v));
	vector <int> sta;
	while(q.size())
	{
		int vv=ans[q.front()];sta.clear();
		while(q.size()&&ans[q.front()]==vv)
		  sta.push_back(q.front()),v[q.front()]=1,q.pop();
		for(int i=0;i<sta.size();i++)
		{
			int x=sta[i];
			for(int j=0;j<p[x].size();j++)
			{
				int y=p[x][j].first;
				if(v[y])continue;
				if(p[x][j].second)continue;
				if(ans[y]==-1)q.push(y),ans[y]=(ans[x]*2)%mod;
			}
		}
		for(int i=0;i<sta.size();i++)
		{
			int x=sta[i];
			for(int j=0;j<p[x].size();j++)
			{
				int y=p[x][j].first;
				if(v[y])continue;
				if(!p[x][j].second)continue;
				if(ans[y]==-1)q.push(y),ans[y]=(ans[x]*2+1)%mod;
			}
		}
	}
}
signed main()
{
	freopen("path.in","r",stdin);
	freopen("path.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x=read(),y=read(),w=read();
		p[x].push_back(mp(y,w));
	}
	memset(ans,-1,sizeof(ans));bfs();
	for(int i=2;i<=n;i++)printf("%lld ",ans[i]);
	return 0;
}

T3. 猪国杀

毒瘤推式子题，大体上用到了一个技巧就是把矩形转过来，类似列队春游
先扔式子：

\(A^n\)是选择总方案数，所以右边应该是所有贡献方案的贡献之和
由于上面提到的技巧应该枚举至少钦定多少张牌有贡献，这个计算方式比较神奇
由于你要保证不重不漏，所以这里枚举了应该最大值，感觉像是先让他有序，然后算出所有的方案数
枚举最大值，小于等于最大值的是钦定的有贡献的部分，那么这里应该是钦定了\(i+k\)个一定有贡献
而右边没有那么简单，由于右面可能有值和\(k\)相等但没有选的牌，所以应该把所有值为\(k\)的都钦定出来，剩下才能乱选
为啥这样是因为必须把最大值全部钦定才会不重不漏，要是一种情况既可以钦定出来也可以乱选出来，那么就会重
下面那个\(g\)是\(i\)个数，值都不大于\(j\)并且最大值不超\(k\)的方案数，跟上面是契合的
他的计算可以用反演+插板组合数算，就是\(g_{i,j,k}=\sum_{t=0}^i (-1)^t \dbinom{i}{t} \dbinom{k-tj}{i}\)
这个式子的复杂度是调和级数，那么直接算就行，由于上界极为宽松导致常数很小，可以直接通过

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N=105,M=1005;
const int mod=998244353;
int n,m,ma;
int jc[M],jcny[M],inv[M];
inline int C(int x,int y)
{
	if(x<y)return 0;
	if(!y)return 1;
	return jc[x]*jcny[y]%mod*jcny[x-y]%mod;
}
inline int g(int i,int j,int k)
{
	int ans=0;
	for(int t=0;t<=i&&t*j<=k;t++)
	{
		if(t&1)ans=(ans-C(i,t)*C(k-t*j,i)%mod+mod)%mod;
		else ans=(ans+C(i,t)%mod*C(k-t*j,i)%mod+mod)%mod;
	}
	return ans;
}
inline int ksm(int x,int y)
{
	int s=1;x%=mod;
	for(;y;y>>=1)
	{
		if(y&1)s=s*x%mod;
		x=x*x%mod;
	}
	return s;
}
signed main()
{	
	freopen("legend.in","r",stdin);
	freopen("legend.out","w",stdout);
	jc[0]=jc[1]=jcny[0]=jcny[1]=inv[1]=1;
	for(int i=2;i<=1000;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;
	}
	cin>>n>>m>>ma;int ans=0;
	for(int i=0;i<=n;i++)for(int j=1;j<=ma;j++)for(int k=1;(k<=n-i)&&(j*k<=m);k++)
	{
		int s=g(i,j-1,m-j*k)*C(n,i)%mod,p=0;
		for(int t=k;t<=n-i;t++)p=(p+C(n-i,t)*ksm(ma-j,n-i-t)%mod)%mod;
		ans=(ans+s*p%mod)%mod;
	}
	int ny=ksm(ksm(ma,n),mod-2);
	cout<<ans*ny%mod<<endl;
	return 0;
}

T4.数树

考场上认为是神仙题，发现数据很小想了状压但没想到
枚举小树每个点作为根，先预处理出小树每个点的直接儿子，可以以此状压
具体方案就是设\(f_{x,son_t}\)表示以大树的\(x\)和小树匹配，\(x\)作为小树的\(t\)的方案数
这个看起来很奇怪，其实是用来确定是否合法，一个节点有这么多儿子才是同构
转移枚举状态，用树上背包的方法转移，这里临时数组表示的是增量，所以应该加上
由于小树重编号后可能和自己同构，所以应该除以这样的方案数，这个可以暴力枚举算
没想到有一天全排列也是正解
还是神仙题，积累思路吧

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=3030;
const int mod=998244353;
struct node{	
	int from,to,next;
}a[2*N],b[25];
int head[N],mm=1,hd[25],mmm=1;
inline void add(int x,int y)
{
	a[mm].from=x;a[mm].to=y;
	a[mm].next=head[x];head[x]=mm++;
}	
inline void addd(int x,int y)
{	
	b[mmm].from=x;b[mmm].to=y;
	b[mmm].next=hd[x];hd[x]=mmm++;
}
int n,m,p[15][15],t[15];
inline int ksm(int x,int y)
{
	int s=1;x%=mod;
	for(;y;y>>=1)
	{
		if(y&1)s=s*x%mod;
		x=x*x%mod;
	}
	return s;
}
int root,son[15],f[N][(1<<11)],g[1<<11];
void dfs1(int x,int fa)
{	
	for(int i=hd[x];i;i=b[i].next)
	{	
		int y=b[i].to;
		if(y==fa)continue;
		son[x]|=(1<<(y-1));
		dfs1(y,x);
	}
}
void dfs2(int x,int fa)
{
	f[x][0]=1;
	for(int i=head[x];i;i=a[i].next)
	{
		int y=a[i].to;
		if(y==fa)continue;
		dfs2(y,x);memset(g,0,sizeof(g));
		for(int j=1;j<=m;j++)
		{
			if(!f[y][son[j]])continue;
			for(int s=0;s<(1<<m);s++)
			{
				if((s>>(j-1))&1)continue;
				g[s|(1<<(j-1))]=(g[s|(1<<(j-1))]+f[x][s]*f[y][son[j]]%mod)%mod;
			}
		}
		for(int s=1;s<(1<<m);s++)f[x][s]=(f[x][s]+g[s])%mod;
	}
}
signed main()
{
	freopen("count.in","r",stdin);
	freopen("count.out","w",stdout);
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int x,y;scanf("%lld%lld",&x,&y);
		add(x,y);add(y,x);
	}
	cin>>m;
	for(int i=1;i<m;i++)
	{	
		int x,y;scanf("%lld%lld",&x,&y);
		addd(x,y);addd(y,x);
		p[x][y]=p[y][x]=1;
	}
	for(int i=1;i<=m;i++)t[i]=i;
	int sum=0;
	do{
		bool fg=1;
		for(int i=1;i<mmm;i+=2)
		{
			int x=b[i].from,y=b[i].to;
			if(!p[t[x]][t[y]]){fg=0;break;}
		}
		if(fg)sum++;
	}while(next_permutation(t+1,t+1+m));
	int ans=0;
	for(int i=1;i<=m;i++)
	{
		root=i;memset(son,0,sizeof(son));
		dfs1(root,0);memset(f,0,sizeof(f));
		dfs2(1,0);
		for(int j=1;j<=n;j++)ans=(ans+f[j][son[i]])%mod;
	}
	cout<<ans*ksm(sum,mod-2)%mod<<endl;
	return 0;
}

考试总结

还是没有回到可以有正解的状态，不过感觉在回升
想着尽量把状态调整回来，不能满状态至少也要正常，不要太低沉
发现数据结构这一块漏洞显示出来了，那么应该有了下一个侧重方向
考试题确实要重视，觉得思考要到位，才能得到有用的东西