模拟85 考试总结

2024-02-01 10:12:10

~~题目背景好评~~

考试经过

还是开题顺序有问题
目测T1不简单，T2是个什么贪心之类的，于是一头扎进T3开始推柿子，结果1.5h无果，然后心态崩掉
然后开始打暴力，T2搞了个一直排序的乱搞不知道有多少分，T1看出来是斯特林就有了40，T4拿个子任务跑路
剩半个小时不知道干啥，oj也不用查文件，于是瞎推了半天啥也没推出来
40+35+20+20=125,比预期高，虽然还是啥也不是

T1.莓良心

考场上想的是枚举每个人所在的组的大小，就有

\[ans=\sum_{w_i}\times (\sum_{i=0}^{n-k}(i+1)\dbinom{n-1}{i}{n-i-1 \brace k-1}) \]

然后发现不会算一列斯特林，就死了
正解是换了一种方法，他的意思是对于一组里的所有元素，每一对都会产生\(w_x+w_y\)的贡献，就是

第二个就是把1个和两个的分开算了，这个柿子会发现全程只用算一个斯特林
那么由斯特林公式得到

\[{n \brace k}=\frac{1}{k!}\sum_{i=0}^k (-1)^i\dbinom{k}{i}(k-i)^n \]

于是就能直接做了，公式学长讲课有讲，先背过吧

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
const int N=2050;
int sit[N][N],jc[N],n,k,a[N],inv[N],jcny[N];
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;
}
signed main()
{
	freopen("ichigo.in","r",stdin);
	freopen("ichigo.out","w",stdout);
	sit[0][0]=jc[0]=1;
	for(int i=1;i<=2000;i++)
	{
	 	sit[i][0]=0;
	 	for(int j=1;j<=i;j++)
		 sit[i][j]=(sit[i-1][j-1]+j*sit[i-1][j]%mod)%mod;
		jc[i]=jc[i-1]*i%mod;
	}
	jc[1]=jcny[1]=jcny[0]=inv[1]=1;
	for(int i=2;i<=2000;i++)
	{
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
		jcny[i]=jcny[i-1]*inv[i]%mod;
	}
	cin>>n>>k;int ans=0,sum=0;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),sum=(sum+a[i])%mod;
	for(int i=0;i<=n-k;i++)ans=(ans+(i+1)*C(n-1,i)%mod*sit[n-1-i][k-1]%mod)%mod;
	ans=ans*sum%mod;cout<<ans<<endl;
	return 0;	
}

T2.尽梨了

发现应该按照\(a/b\)排序，这样最终选择的一定是他的一个子序列，更准确讲\(i\)在\(j\)前面满足\((b_i+1)a_j<(b_j+1)a_i\)
这个东显然可dp，\(f_{i,j}\)表示前\(i\)个买了\(j\)个的最少花费，发现当\(a>0\)他的花费指数增加，所第二维只开\(log\)
最后剩下一堆\(a=0\)的，扫过去判断还能买多少即可，总复杂度\(n\log n\)

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=200030;
struct t{int a,b;}p[N];
inline bool cmp(t x,t y)
{
	if((x.b+1)*y.a!=(y.b+1)*x.a)return (x.b+1)*y.a<(y.b+1)*x.a;
	return x.b<y.b;
}
int f[N][35];
signed main()
{
	freopen("eriri.in","r",stdin);
	freopen("eriri.out","w",stdout);
	int n,T;cin>>n>>T;
	for(int i=1;i<=n;i++)scanf("%lld%lld",&p[i].a,&p[i].b);
	sort(p+1,p+1+n,cmp);int ga=n+1;
	for(int i=1;i<=n;i++)if(!p[i].a){ga=i;break;}
	memset(f,0x3f,sizeof(f));
	f[0][0]=0;
	for(int i=1;i<ga;i++)
	{
		for(int j=0;j<=min(i,(int)30);j++)
		{
			if(f[i-1][j]<=T)f[i][j]=min(f[i][j],f[i-1][j]);
			if(f[i-1][j-1]<=T&&j)f[i][j]=min(f[i][j],f[i-1][j-1]+1+(f[i-1][j-1]+1)*p[i].a+p[i].b);
		}
	}
	int ans=0;
	for(int i=0;i<=30;i++)
	{
		if(f[ga-1][i]>T)break;int s=i,sum=f[ga-1][i];
		for(int j=ga;j<=n;j++)
		{
			sum+=p[j].b+1;
			if(sum>T)break;s++;
		}
		ans=max(ans,s);
	}		
	cout<<ans<<endl;
	return 0;
}

T3.团不过

卡农的弱化版，思路基本一样，设\(f_i\)表示\(i\)堆先手必败方案数，\(p_i\)表示堆总方案数
题解写的贼清楚，所以直接复制了

关键在于能看出来这个是个卡农，否则怎么都白搭

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int N=1e7+10;
int p[N],f[N],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;
}
signed main()
{
	freopen("yui.in","r",stdin);
	freopen("yui.out","w",stdout);
	cin>>n;int ga=ksm(2,n);
	p[0]=1;for(int i=1;i<=n;i++)p[i]=p[i-1]*(ga-i)%mod;
	f[1]=f[2]=0;
	for(int i=3;i<=n;i++)f[i]=(p[i-1]-f[i-1]+mod-(ga-i+1+mod)%mod*(i-1)%mod*f[i-2]%mod+mod)%mod;
	cout<<(p[n]-f[n]+mod)%mod<<endl;
	return 0;
}

T4.七负我

如果两个点之间没有连边，那么在他们分配的权值和确定的的情况下，一个分0一定不劣
那么就找图中的最大团就行了，然后权值平均分配
可以状压折半，预处理前一半的所有子集的最大团，枚举后一半的团（要\(check\)一下是团），看他的出边与前一般的交集\(s\),那当前团的点数\(i\)加上\(f_s\)就是答案，然后取最大的即可，实现比较简单

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2000;
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++;
}
int n,m,sum;
inline int getsum(int x)
{
	int s=0;
	while(x)
	{	
		if(x&1)s++;
		x>>=1;
	}
	return s;
}
vector <int> sta[22];
int f[1ll<<22],to[45],t,tt,v[45][45];
inline bool check(int s)
{
	for(int i=1;i<=tt;i++)
	{
		if(!((s>>(i-1))&1))continue;
		int x=i+t;
		for(int j=1;j<=tt;j++)
		{
			if(!((s>>(j-1))&1))continue;
			if(j==i)continue;
			if(!v[i+t][j+t])return 0;
		}
	}
	return 1;
}
signed main()
{
	freopen("nanami.in","r",stdin);
	freopen("nanami.out","w",stdout);
	cin>>n>>m>>sum;t=n/2;
	for(int i=1;i<=m;i++)
	{
		int x,y;scanf("%lld%lld",&x,&y);
		add(x,y);add(y,x);
		if(x<=t)to[y]|=1ll<<(x-1);
		if(y<=t)to[x]|=1ll<<(y-1);
		v[x][y]=v[y][x]=1;
	}
	for(int i=1;i<(1ll<<t);i++)sta[getsum(i)].push_back(i);
	for(int i=1;i<=t;i++)f[1ll<<(i-1)]=1;
	for(int i=1;i<=t;i++)
	{
		for(int j=0;j<sta[i].size();j++)
		{
			int s=sta[i][j];
			for(int k=1;k<=t;k++)
			{
				if((s>>(k-1))&1)continue;
				if((to[k]&s)==s&&f[s]==i)f[s|(1ll<<(k-1))]=max(f[s|(1ll<<(k-1))],f[s]+1);
				else f[s|(1ll<<(k-1))]=max(f[s|(1ll<<(k-1))],f[s]);
			}				
		}
	}
	int ans=0;tt=n-t;
	for(int i=1;i<(1ll<<t);i++)ans=max(ans,f[i]);
	for(int i=1;i<(1ll<<tt);i++)
	{
		if(!check(i))continue;
		int s=(1ll<<t)-1;
		for(int j=1;j<=tt;j++)
		{
			if((i>>(j-1))&1)s&=to[j+t];
		}
		ans=max(ans,getsum(i)+f[s]);
	}
	printf("%.6lf\n",1.0*ans*(ans-1)*sum*sum/(2.0*ans*ans));
	return 0;
}

考试总结

感觉最近陷进这样的怪圈中：

想题，想了半天，然后假掉
两条路：
继续，然后爆零，然后垫底
换题，然后暴力，然后垫底
有时我选择前者，因为我太懦弱，没有力挽狂澜的勇气
有时我选择后者，因为我太懒惰，没有绝处逢生的毅力

于是嘲笑自己，然后又是一天过去
希望自己想明白一些事情吧，毕竟时间不多了

码农公寓