模拟73 考试总结

2023-11-10 18:02:22

众所周知题水与分高分低没有关系

考试经过

T1貌似很水，然而不会正解，写了一个\(n^2logn\)的做法，造数据跑的飞快，直接不管了
T2看上去很可以矩阵，然而依旧不会正解，看着部分分很多写了一个50的，有20分本地3s大概率过不了，卡了卡也不管了
T3像多源最短路，改了几次做法之后觉得没啥问题，然后40min写了个暴力拍上，已经10:20了就走了
T4显然不会正解，写了个\(2^m\times n!\)的做法，然后把阶乘优化了，发现去掉记忆化快10倍就离谱，就交了
100+50+100+10=260
都有场切的，太可怕了

T1.小L的疑惑

先排序，如果前面所有数和小于下一个数，则证明一定有数拼不成，答案即为\(sum+1\)，否则一直往后扫

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1000500;
int a[N],sum[N];
signed main()
{
	freopen("math.in","r",stdin);
	freopen("math.out","w",stdout);
	int n;cin>>n;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	sort(a+1,a+1+n);a[n+1]=1e12;
	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
	if(a[1]!=1){cout<<1<<endl;return 0;}
	for(int i=1;i<=n;i++)
	{
		if(sum[i]+1<a[i+1])
		{
			cout<<sum[i]+1<<endl;
			return 0;
		}
	}
	return 0;
}

T2.小L的数列

感觉比较神，考场确实做不出来，还好没肝
事实上后面的每个数都是\(f_1,f_2..f_k\)乘上一个系数的形式，所以对于一个\(f\)可以用一个长度为\(k\)的向量表示每一项的系数
如果你状态只用向量表示的话，就发现很不好转移，根本配不出来转移矩阵
但是思考一下问题所在，谁说状态非要用一维向量存了
因为转移时要考虑前\(k\)种状态，所以可以用一个矩阵表示当前状态和它之前的\(k\)种状态，具体就是：

格子里表示系数，初始是对应\(k+1\)的状态，右对角线全1
转移矩阵想一下就会发现是\(b\)全在下面，主对角线上平移一格全1
直接做矩阵乘就好了，注意模数是\(mod-1\)，因为在指数上，最后把系数乘起来快速幂出答案
顺便特判一线\(n<=k\)的情况

%:pragma GCC optimize(3)
using namespace std;
#define int long long
const int N=205;
const int mod=998244353;
int n,k,a[N],b[N];
int p[N][N],f[N][N],pp[N][N],ans[N];
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;
}
inline void gan()
{
	memset(pp,0,sizeof(pp));
	for(int i=1;i<=k;i++)
	 for(int kk=1;kk<=k;kk++)
	 {
	  if(!p[i][kk])continue;
	  for(int j=1;j<=k;j++)
	   pp[i][j]=(pp[i][j]+p[i][kk]*p[kk][j]%(mod-1))%(mod-1);
	 }
	memcpy(p,pp,sizeof(pp));
}
inline void mul()	
{
	memset(pp,0,sizeof(pp));
	for(int i=1;i<=k;i++)
	 for(int kk=1;kk<=k;kk++)
	 {
	  if(!f[i][kk])continue;
	  for(int j=1;j<=k;j++)
	   pp[i][j]=(pp[i][j]+f[i][kk]*p[kk][j]%(mod-1))%(mod-1);
	 }
	memcpy(f,pp,sizeof(f));
}
inline void work(int x)
{	
	for(;x;x>>=1)
	{
		if(x&1)mul();
		gan();
	}
}
signed main()
{
	freopen("seq.in","r",stdin);
	freopen("seq.out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=k;i++)scanf("%lld",&b[i]);
	for(int i=1;i<=k;i++)scanf("%lld",&a[i]);
	if(n<=k){cout<<a[n]<<endl;return 0;}
	for(int i=1;i<=k;i++)p[k][k-i+1]=b[i],p[i][i+1]=(i!=k);
	for(int i=1;i<=k;i++)f[i][k-i+1]=1;
	work(n-k-1);
	for(int i=1;i<=k;i++)
	 for(int j=1;j<=k;j++)
	  ans[j]=(ans[j]+f[i][j]*b[i]%(mod-1))%(mod-1);
	int an=1;
	for(int i=1;i<=k;i++)an=an*ksm(a[i],ans[i])%mod;
	cout<<an<<endl;
	return 0;
}

~~不开O2我也很绝望啊~~
这个思路没有见过，应该总结积累

T3.连边

朴素思想是优先选短的，但由于要满足最后连出来的还是最短路，所以会假
应该先做一遍多源最短路处理一个点到最近黑点的距离，只有当这个路径在最短路上的时候才合法
直接累加答案会假，应该对于每个点开个答案数组，这样可以反复更新

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=200050;
struct node{
	int from,to,next,w;
}a[2*N];
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 n,m,p[N],dis[N],ans[N];bool v[N];
priority_queue <pair<int,int> >q;
inline void die(){puts("impossible");exit(0);}
signed main()
{
	freopen("minimum.in","r",stdin);
	freopen("minimum.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)scanf("%lld",&p[i]);
	for(int i=1;i<=m;i++)
	{
		int x,y,z;scanf("%lld%lld%lld",&x,&y,&z);
		add(x,y,z);add(y,x,z);
	}
	memset(dis,0x3f,sizeof(dis));int ga=dis[0];
	for(int i=1;i<=n;i++)if(p[i])dis[i]=0,q.push(make_pair(0,i));
	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(dis[y]>dis[x]+a[i].w) 
			 dis[y]=dis[x]+a[i].w,q.push(make_pair(-dis[y],y));
		}
	}
	for(int i=1;i<=n;i++)if(dis[i]>=ga||dis[i]>1e15)die();
	memset(ans,0x3f,sizeof(ans));
	for(int x=1;x<=n;x++)
	{
		if(!p[x])continue;ans[x]=0;
		for(int i=head[x];i;i=a[i].next)
		{
			int y=a[i].to;
			if(p[y])continue;
			ans[y]=min(ans[y],a[i].w),q.push(make_pair(-a[i].w,y));
		}
	}
	while(q.size())
	{
		int x=q.top().second,w=-q.top().first;q.pop();
		if(p[x])continue;p[x]=1;
		for(int i=head[x];i;i=a[i].next)
		{
			int y=a[i].to;
			if(dis[y]!=dis[x]+a[i].w)continue;
			ans[y]=min(ans[y],a[i].w),q.push(make_pair(-a[i].w,y));
		}
	}
	int sum=0;
	for(int i=1;i<=n;i++)sum+=ans[i];
	cout<<sum<<endl;
	return 0;
}

T4.小L的有向图

一个性质就是，如果选择一个点会有\(k\)条边被满足，那么会对答案有\(2^k\)的贡献
意思就是你的合法选择多了\(2^k\)种，没有限制可以随便选
然后状压转移就好了，可能有些卡常

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=500;
const int mod=998244353;
int f[1<<23],sum[1<<23],n,m;
vector <int> sta[23];
inline int getsum(int x)
{
   return __builtin_popcount(x);
}
int bit[N],p[30];
signed main()
{
   freopen("topology.in","r",stdin);
   freopen("topology.out","w",stdout);
   cin>>n>>m;
   for(int i=1;i<=m;i++)
   {
   	int x,y;scanf("%lld%lld",&x,&y);
   	p[y]|=(1<<(x-1));
   }
   for(int i=0;i<(1<<n);i++)sum[i]=getsum(i),sta[sum[i]].push_back(i);
   f[0]=1;bit[0]=1;for(int i=1;i<=m;i++)bit[i]=bit[i-1]*2%mod;
   for(int i=0;i<n;i++)
   {
   	for(int j=0;j<sta[i].size();j++)
   	{
   		int s=sta[i][j];
   		if(!f[s])continue;
   		for(int x=1;x<=n;x++)
   		{
   			if((s>>(x-1))&1)continue;
   			int num=sum[s&p[x]];
   			f[s|(1<<(x-1))]=(f[s|(1<<(x-1))]+f[s]*bit[num])%mod;
   		}
   	}
   }
   cout<<f[(1<<n)-1]<<endl;
   return 0;
}

考试总结

认为是比较成功的一场，正解和暴力权衡的比较到位
当然如果时间更足的话还会分更高，但不拍的话就容易挂分
找到自己的节奏，然后跟着走

码农公寓