ZhouChuang Coding CSP-J 仿真模拟题解

ZhouChuang Coding CSP-J 仿真模拟题解

T1 Retribution ∼ Cycle of Redemption ∼

按照题意模拟即可。可以采用递推减少代码编写难度。

注意不开long long的话会获得 60 分的高分。

这里涉及到一个知识点，int类型最多支持算到12!，而long long 最多支持算到20!也就是刚好题目的数据范围，而我们通过简单估算可以发现20!*2仍然在long long的数据范围内所以不用写高精度。

AC code

#include<bits/stdc++.h>
using namespace std;
const int maxn=21;
typedef long long ll;
int a[maxn];
int main()
{
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	a[0]=1;
	for(int i=1;i<=n;i++)
		a[i]=a[i-1]*i;
	cout<<(a[n]-n)*2<<" "<<(a[n]-2*n)*2<<" "<<2<<endl; 
	return 0;
}

T2 Givemeygg lose his unique coin

首先此题旨在考查阅读理解能力。

翻译过来就是一个无向图，每条边有边权，删去一些边使得这个图变成一个二分图，使得花费价值最少。

然后可以发现这个题的

n

是非常小的，于是可以直接暴力枚举每个点所在的集合（

A

或

B

），不同集合的点之间的边都要删去，判断每条边是否删去需要

O(m)

次运算，对枚举的状态进行分解需要

O(n)

次计算，期望复杂度

O(\text{max}(n,m)\times2^n)

，可以通过。

不过也需要注意到这个题的边权是

10^8

次的，考虑极限数据的估算，最多情况下可以超过2.1亿也就是会爆int，所以ans也要开long long。

不开long long 会获得 80 分的高分。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
typedef long long ll;
int a[maxn],b[maxn],c[maxn];
ll k[maxn],num=10000000000; 
int main()
{
	ios::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>a[i]>>b[i]>>k[i];
	for(int i=0;i<=(1<<n)-1;i++)
	{
		int x=i,tot=1;
		memset(c,0,sizeof(c));
		while(x)
			c[tot++]=x%2,x/=2;
		ll ans=0;
		for(int j=1;j<=m;j++)
			if(c[a[j]]==c[b[j]])
				ans+=k[j];
		num=min(num,ans); 
	}
	cout<<num<<endl;
	return 0;
}

T3 Alice vs Bob Ⅰ

考虑 DP 求解。

记状态

dp[i][k]

表示一共剩下

k

次操作，此时走到第

i

个点的胜负情况，

dp[i][k]=A

表示 Al 必胜，

dp[i][k]=B

表示 Bob 必胜，我们认为初始状态的字符串

s

就表示所有的

dp[i][0]

，于是可以发现

dp[i][k]

只由

dp[j][k-1]

决定，其中

j

是从

i

出发可以直接到达的点，即存在边

i->j

。

具体的，如果

k

是偶数，那么是 Al 操作，也就是只要

dp[j][k-1]

中存在一个点是

A

，那么

Al

就可以这步操作走到这个点，然后必胜。所以

dp[i][k]=A

当且仅当存在

dp[j][k-1]=A

，若所有的

dp[j][k-1]=B

,则

dp[i][k]=B

。

同样的，如果

k

是奇数，那么是 Bob 操作，也就是只要

dp[j][k-1]

中存在一个点是

B

，那么 Bob 就可以这步操作走到这个点，然后必胜。所以

dp[i][k]=B

当且仅当存在

dp[j][k-1]=B

，若所有的

dp[j][k-1]=A

,则

dp[i][k]=A

。

然后就可以 DP递推或者记忆化搜搜求解了。时间复杂度

O(\text{max}(n,m)\times 2k)

，可以通过本题。

如果想要进一步优化，可以发现上面两种转移本质上都一模一样，考虑把 A / B 必胜的意义改成先手/后手必胜，那么两部分的转移就可以完全统一到一起，也就是 std 的写法。

最后有一个小细节，注意题目中开头的冷笑话写的是Alice 中的 ice 化掉了，因此我们应该输出 Al 而不是谐音的 AI 。（注意前一个是L的小写后一个是i的大写）

AC Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
typedef long long ll;
vector<int>e[maxn];
int pos[maxn][20],t,n,m,k;
void upd(int x,int k)
{
	for(int i=0;i<e[x].size();i++)
		if(pos[e[x][i]][k-1]==2)
		{
			pos[x][k]=1;
			return;
		}
	pos[x][k]=2;
	return;
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>t;
	while(t--)
	{
		cin>>n>>m>>k;
		string s;
		cin>>s;
		for(int i=1;i<=n;i++)
			e[i].clear();
		for(int i=1;i<=m;i++)
		{
			int x,y;
			cin>>x>>y;
			e[x].push_back(y);
		}
		for(int i=1;i<=n;i++)
			if(s[i-1]=='A')
				pos[i][0]=1;
			else
				pos[i][0]=2;
		for(int i=1;i<=2*k;i++)
			for(int x=1;x<=n;x++)
				upd(x,i);
		if(pos[1][2*k]==1)
			cout<<"Al"<<endl;
		else
			cout<<"Bob"<<endl;
	}
	return 0;
}

T4 完蛋了这么简单的题目放T4肯定被切穿了吧

如题，结论题。

第一步翻译题目意思。

有

n

个硬币构成一个环，每个硬币有一个正反面（正面为

v_i=1

，反面为

v_i=0

）且写着一个面额（

a_i

），每次可以选择拿走一个硬币，若这个硬币的左边或者右边有任意一个的正反面和自己相同，那么拿走这个硬币就不算分。否则这次拿走加上这个硬币上面写着的面额。

定义环中只剩一枚硬币时它的左边与右边都是自己。

首先可以发现，对于连续一段状态相同的硬币，其中必定有且只有一个硬币对答案有贡献，也就是一直取一直取取到这一段只剩一个硬币，且两端都异面，此时再取这个硬币才会对答案有贡献。于是这部分考虑贪心求最大。

于是这个时候我们的硬币形如

0101010101

这样的一个环，设共有

2\times k

个。

首先显然可以发现，这

2k

个硬币里面最多有且只有

k

个会对答案造成贡献。

于是来到了本题最为诈骗的地方，我们考虑证明对于取环中任意

k

个硬币，这样的方案总是存在。

如下：

于是代码实现就很简单了，我们先对原来的环断环为链，然后去重，然后对于新序列排序，取最大的

n

个求和。

注意不要忘记对状态全部相等的情况特判，这个时候答案为

0

。

总复杂度

O(nlogn)

，可以通过本题。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
typedef long long ll;
int vis[maxn<<1];
ll a[maxn<<1],b[maxn];
int main()
{
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>vis[i];
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
		vis[i+n]=vis[i],a[i+n]=a[i];
	int pos=1;
	while(vis[pos]==vis[pos+1]&&pos<n)
		pos++;
	if(pos==n)
	{
		cout<<0<<endl;
		return 0;
	} 
	if(pos!=n) 
		pos++;
	else
		pos=1;
	ll mx=a[pos],num=0,ans=0;
	for(int i=pos;i<pos+n;i++)
		if(vis[i]!=vis[i+1]||i==pos+n-1)
			b[++num]=mx,mx=a[i+1];
		else
			mx=max(mx,a[i+1]);
	sort(b+1,b+1+num);
	for(int i=num/2+1;i<=num;i++)
		ans+=b[i];
	cout<<ans<<endl;
	return 0;
}

T5 Alice vs Bob Ⅱ

决策构造的结论题。由于我们要将这颗树标记合法的边，我们可以想一下这个游戏的性质。

1.首先可以发现一个简单的结论，不可能有两个相邻的节点使得它们都为 $1$ 。

很容易发现，因为如果有一个节点为

1

已经确认，那么另一个节点先手下完后，后手必定会下在这个为

1

的节点，因为在这里后手的意义等同于先手，那么是后手必胜的。

2.其次，两个相邻节点都为 $2$ 是可能的。

因为两个后手必胜的路径可能有所不同，当两个路径不经过同一个点时就可以存在两个相邻的

2

，而这两个节点之间可以任意连边。

3.当一个节点没有出边时，它必定为 $1$ 。

自己手玩可知。

通过上面三条结论我们可以发现一个简单的构造方法：当一个点为

1

时，将目前所有未被标记的边联向自己，并且将周围所有未标记的点标为

2

并进行二次编号.当其为

2

时，将所有的未被标记的边联向他人。这样就可以满足上述三条性质。

然后考虑怎么将询问次数再次降低，使其必小于

\lfloor\frac{n}{2}\rfloor

。我们可以处理好每个点未被标记的边数，每次暴力取出边数最多的点进行询问，最差情况是树退化成一条链，每次最多询问出两条边且都为

2

无法进行二次编号，因此刚好能做到

\lfloor\frac{n}{2}\rfloor

。

总复杂度

O(n^2)

，可以通过本题。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
typedef long long ll;
struct node
{
	int u,v,i;
};
node tr[maxn];
vector<node>s[maxn];
vector<int>q[maxn];
int du[maxn];
int f[maxn];
int win[maxn];
int m;
extern "C"
{
	int ask(int x); 
	void init(int n,vector<node>e)
	{
		m=n;
		for(int i=1;i<=n-1;i++)
		{
			tr[i]=e[i-1];
			s[tr[i].u].push_back(node{tr[i].u,tr[i].v,i});
			s[tr[i].v].push_back(node{tr[i].u,tr[i].v,i});	
			q[tr[i].u].push_back(tr[i].v);
			q[tr[i].v].push_back(tr[i].u);
			f[tr[i].u]++;f[tr[i].v]++;
		}
	}
	string que()
	{
		while(1)
		{
			int fl=1;
			for(int i=1;i<=m-1;i++)
				if(du[i]==0)
					fl=0;
			if(fl==1)
				break;
			int md=0,mi=0;
			for(int i=1;i<=m;i++)
				if(f[i]>md)
					md=f[i],mi=i;
			int tmp=ask(mi);
			win[mi]=tmp;
			for(int i=0;i<s[mi].size();i++)
				if(du[s[mi][i].i]==0)
				{
					du[s[mi][i].i]=((s[mi][i].u==mi)?tmp%2+1:tmp);
					f[s[mi][i].u]--;
					f[s[mi][i].v]--;
				}
			if(tmp==1)
				for(int i=0;i<q[mi].size();i++)
					if(win[q[mi][i]]==0)
					{
						win[q[mi][i]]=1;
						for(int x=0;x<s[q[mi][i]].size();x++)
							if(du[s[q[mi][i]][x].i]==0)
							{
								du[s[q[mi][i]][x].i]=((s[q[mi][i]][x].u==q[mi][i])?2:1);
								f[s[q[mi][i]][x].u]--;
								f[s[q[mi][i]][x].v]--;
							}
					}
		}
		string sk;
		for(int i=1;i<=m-1;i++)
			sk+=char(du[i]+'0');
		return sk;
	}
}

\text{Extra Sub}

优化1.我们先前是暴力寻找最大度数的点，实际可以优化成采用一个优先队列，时间复杂度降为

O(n\log n)

。

优化2.可以开一个桶数组记录度数，每次寻找最大度数的点为

O(1)

，于是总复杂度为

O(n)

。注意这种方法细节比较多，且常数较大。

为什么不加

\text{Extra Sub}

呢？因为

\text{std}

虽然是意义上的

O(n^2)

算法，但是实际因为不卡链且询问很少跑不满，跑起来飞快，

10^5

规模的数据~~只跑了 50ms~~ 。所以写优化其实没有太大必要。

ZhouChuang Coding CSP-J 仿真模拟题解

文章操作

相关推荐

评论

ZhouChuang Coding CSP-J 仿真模拟题解