noip模拟30

\(\color{white}{\mathbb{缀以无尽之群星点点，饰以常青之巨木郁郁，可细斟木纹叶脉，独无可极苍穹之览，名之以：密林}}\)

看完题后感觉整套题都没什么思路，而且基本上整场考试确实是这样

倒序开题，发现 \(t3\) 的做法没有优化空间了，\(t2\) 发现了一些规律，但是卡在求拓扑序上，最后乱搞 \(t1\)，本来复杂度及其不正确，但是测的在随机数据下还是很可观的

事实上最后分数比预期高多了

A. 毛一琛

考完 cyh 说才发现是曾经随机跳题跳到的USACO的题，但不幸的是当时直接跳了……

如果直接枚举的话有三种状态：分到第一组，分到第二组，不要，这样是 \(3^n\)

对于这种范围刚刚超的，而且还是枚举集合的题，常常可以使用折半搜索

对于前半段共 \(\frac{n}{2}\) 个元素暴搜一下，消耗 \(3^{\frac{n}{2}}\)，并且把每种状态记录在其和的 \(vector\) 里面

右边再重复上述操作，设求出的和为 \(sum\)，那么在左边寻找 \(-sum\) 的集合，并且更新和起来的答案即可

代码实现

#include<bits/stdc++.h>

using namespace std;

const int maxn=55,maxm=1e6+1e5+5;

int n,a[maxn],half,tot,ans;

bool vis[maxm];

map<int,int>mp;

vector<pair<int,int> >num[maxm];

void dfs1(int pos,int sum,int S1,int S2){

	if(pos==half+1){

		if(mp.find(sum)==mp.end())mp[sum]=++tot;

		num[mp[sum]].push_back(make_pair(S1,S2));

		return ;

	}

	dfs1(pos+1,sum,S1<<1,S2<<1);

	dfs1(pos+1,sum+a[pos],S1<<1|1,S2<<1);

	dfs1(pos+1,sum-a[pos],S1<<1,S2<<1|1);

	return ;

}

void dfs2(int pos,int sum,int S1,int S2){

	if(pos==n+1){

		if(mp.find(-sum)==mp.end())return ;

		int id=mp[-sum];

		for(int i=0;i<num[id].size();i++){

//			cout<<"hhh";

			vis[S1|S2|((num[id][i].first|num[id][i].second)<<(n-half))]=true;

		}

		return ;

	}

	dfs2(pos+1,sum,S1<<1,S2<<1);

	dfs2(pos+1,sum+a[pos],S1<<1|1,S2<<1);

	dfs2(pos+1,sum-a[pos],S1<<1,S2<<1|1);

	return ;

}

int main(){

	cin>>n;

	half=n/2;

//	if(n>=10)half+=3;

	for(int i=1;i<=n;i++)cin>>a[i];

	dfs1(1,0,0,0);

	dfs2(half+1,0,0,0);

	for(int i=1;i<=(1<<n)-1;i++)if(vis[i])ans++;

	cout<<ans;

	return 0;

}

B. 毛二琛

考场上想到可以根据先后顺序建边，相当于求有向图的拓扑序个数

然后想到以前有到叫 \(SAO\) 的题，然而当时咕咕咕了……

正解是用 \(dp\) 来做

设 \(f[i][j]\) 表示第 \(i\) 个数在前 \(i\) 个数形成的图中拓扑序为 \(j\) 的方案数

考虑从 \(f[i-1][k]\) 转移

如果 \(i-1\) 向 \(i\) 连边，相当于如果 \(i\) 的拓扑序为 \(j\)，那么 \(k\) 的范围为 \([1,j-1]\)

如果 \(i\) 向 \(i-1\) 连边，\(k\) 的范围为 \([j,i]\) (可以取到 \(j\) 是因为加入 \(i\) 这个数相当于把值域往后平移一位，那么原来的 \(j\) 现在相当于 \(j+1\)，是满足条件的)

然后发现 \(k\) 的值域是连续的，可以前缀和优化一下

代码实现

#include<bits/stdc++.h>

using namespace std;

int read(){

	int x=0,f=1;

	char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-')f=-1;

		ch=getchar();

	}

	while(isdigit(ch)){

		x=x*10+ch-48;

		ch=getchar();

	}

	return x*f;

}

const int maxn=5005;

const int mod=1e9+7;

int n,a[maxn],f[2][maxn],g[2][maxn],ans;

bool le[maxn];//rk[i]<rk[i+1]

int main(){

	n=read();

	for(int i=0;i<n;i++)a[i]=read();

	for(int i=0;i<n;i++){

		if(a[i]<i){//往左走

			for(int j=a[i];j<=i-2;j++)le[j]=true;

		}

		else{

			if(i>0)le[i-1]=true;

			le[a[i]-1]=true;

		}

	}

	f[0][1]=g[0][1]=1;

	for(int i=1;i<=n-2;i++){

		for(int j=1;j<=i+1;j++){

			if(le[i-1])f[i&1][j]=(g[(i-1)&1][i]-g[(i-1)&1][j-1]+mod)%mod;

			else f[i&1][j]=g[(i-1)&1][j-1];

		}

		for(int j=1;j<=i+1;j++){

			g[i&1][j]=(g[i&1][j-1]+f[i&1][j])%mod;

		}

	}

	for(int i=1;i<=n;i++)ans=(ans+f[(n-2)&1][i])%mod;

	cout<<ans;

	return 0;

}

B. 毛三琛

玄学题

首先应该乖乖地按照题目上说的确定 \(x\)（考场上因为加了个小优化所以不得不先二分再定 \(x\))

当 \(x\) 随机打乱后，最优解的更新序列长度期望是 \(logP\) 的

那么只需要每次开始二分前，\(O(n)\) 判断一下当前 \(x\) 是否比当前答案优即可

代码实现

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+5;

int n,p,k,a[maxn],ans,b[maxn],x;

int read(){

	int x=0,f=1;

	char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-')f=-1;

		ch=getchar();

	}

	while(isdigit(ch)){

		x=x*10+ch-48;

		ch=getchar();

	}

	return x*f;

}

bool check(int limit,int x){

	int cnt=1,sum=0;

	for(int i=1;i<=n;i++){

		int val=(a[i]+x)%p;

		if(val>limit) return false;

		if(sum+val<=limit)sum+=val;

		else sum=val,cnt++;

		if(cnt>k)break;

	}

	if(cnt<=k)return true;

	return false;

}

int main(){

	srand(time(0));

	n=read();

	p=read();

	k=read();

	for(int i=1;i<=n;i++)a[i]=read(),ans+=a[i];

	for(int i=0;i<p;i++)b[i]=i;

	random_shuffle(b,b+p);

	for(int i=0;i<p;i++){

		x=b[i];

		if(check(ans,x)){

			int l=0,r=ans+1;

			while(l<r){

				int mid=l+r>>1;

				if(check(mid,x))r=mid;

				else l=mid+1;

			}

			ans=l;

		}

	}

	cout<<ans;

	return 0;

}

\(\color{white}{\mathbb{溯洄从之，道阻且长}}\)

巴特西

noip模拟30

A. 毛一琛

B. 毛二琛

B. 毛三琛

最新文章

热门文章