526互联

【2023 #84】 锦城ACM周测 (大二个人赛) 题解

发布时间 2023-11-12 14:26:17作者: Martian148

题目难度 \(B<D<E=C<A\)

Candy war

Question

有 \(N\) 个盒子摆成环形，第 \(i\) 和盒子里面有 \(a_i\) 个糖果，他们开始在 \(1\) 好盒子，然后每个人取一次，可以取\(1\)， 或者小于当前盒子内糖果数的一个质数 \(p\), 两个人都取了之后就来到下一个盒子取，当有一个人操作前，当前盒子里面没有糖果了，那么这个人就输了

Solution

先考虑 \(N=1\) 的情况，如果 \(a_i=4\) 那么先取的(Cody) 必输，考虑到偶数的质数只有 \(2\) ，那么如果 \(a_i\) 是 \(4\) 的倍数的话，Cody 先取了 \(x\)，Loy 取 \((4-x\%4)\) 也就是说，Loy 取了之后，把当前盒子的糖果数控制在 \(4\) 的倍数，那么递归地考虑 \(Cody\) 必输。如果 \(a_i\) 不是 \(4\) 的倍数，Cody 第一步可以取 一个质数 p，使得 \((a_i-p)\%4 == 0\) 这 样子就能把糖果数控制在 \(4\) 的倍数，然后轮到 Loy 取。所以 Loy 必输

因为有很多个盒子，所以对于某一个盒子，必赢的那个人肯定想尽早结束游戏，必输的那个人想慢点结束游戏，可得

  • 必赢的人第一次取最大的 \(p\), 使得 \((a_i-p)\% 4==0\)，这样子才能赢的快
  • 必输的那个人每次肯定取 \(2\) ，这样导致必赢的那个人只能也取 \(2\)，这样子才能输的慢

由此推知每个盒子 \(a_i\) 要取的次数为 \(F_i=(a_i-p) /2\) ，要取的轮数是 \(F_i /2\) 这个数，也是他们两个转的圈数，当转到某一圈时当前盒子的糖果数为 \(0\) 时，这个盒子必输的那个人对于整个游戏输了。

取的轮数最少的那个盒子就是第一个取完的盒子

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e6+5;
bool vis[maxn];
int min_turn[maxn]={0,1},max_mod4[4]={2,1,2,3};
inline void init(){
    for(int i=2;i<maxn;i++){
        if(!vis[i]){  //i是一个质数
            for(int j=1;j*i<maxn;j++)
                vis[i*j]=1;
            max_mod4[i%4]=i;  // max_mod4[]记录的是最大的 p,使得 (ai-p) % 4 ==0
        }
        if(i&1)min_turn[i]=(i-max_mod4[i%4])/2+1;  
        else min_turn[i]=i/2;
    }
}
int main(){
    init();
    int T;cin>>T;
    while(T--){
        int N;cin>>N;
        int ans=maxn;
        for(int i=0;i<N;i++){
            int now;cin>>now;
            if(min_turn[now]/2<ans/2) //min_turn 是转的圈数，注意这里的 /2 不能约掉
                ans=min_turn[now];
        }
        printf("%s\n",ans&1?"Cody":"Loy");
    }
    return 0;
}

Tuition dispute

Question

有 \(N\) 个学生，每个学生可以接受的最高学费为 \(a_i\) ，我们要设置一个学费值，使得收到的总的学费最多

Solution

贪心的思想，把学费从高的 \(a_i\) 起往下降，此时收到的学费值是 学分值 \(\times\) 人数，求最大值就好了

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
int N;
LL a[maxn];
LL ans=0,money;
int main(){
    // freopen("A.in","r",stdin);
    cin>>N;
    for(int i=1;i<=N;i++)
        cin>>a[i];
    sort(a+1,a+1+N);
    for(int i=N;i;i--){
        if(a[i]*(N-i+1)>=ans)
            ans=a[i]*(N-i+1),money=a[i];
    }
    cout<<ans<<" "<<money<<endl;
    return 0;
}

Pet

Question

有两个种类的狗，简称 G 和 H，给出 \(a_i\) G/H 表示第 \(i\) 个位置站的是什么类型的狗，每个狗最多往左或者右走 \(k\) 步，你需要在一些位置放上狗的食物，求放的食物最少的数量，并给出一种可行的方案

Solution

考虑到每一只狗向左或者向右走的步数是一样的，那么考虑贪心，从前往后处理，对于一只没有食物吃的狗，那么我们在 \([i-k,i+k]\) 的范围内放食物都可以，考虑到后面处理的狗的初始位置都大于 \(i\) 所以这种食物肯定往右边放好，那么就放在 \(i+k\) 的位置，如果超过了 \(N\) 那么就放在 \(N\)

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    freopen("B.in","r",stdin);
    freopen("B.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);

	int T;
	cin >> T;

	while (T--) {
		int n;
		int k;
		cin >> n >> k;
		string s;
		cin >> s;
		int patchG = -k - 1; 
		int patchH = -k - 1; 
		int cnt = 0;
		string ans(n, '.');
		for (int i = 0; i < n; i++) {
			if (s[i] == 'G' && i - patchG > k) {
				// 最近的 G不能覆盖 i
				++cnt;
				if (i + k >= n) { //如果 超过N 了
					patchG = n-1;
					if (ans[patchG] == 'H') { patchG--; }
				} else {
					patchG = i + k; // i+k的位置放上 G
				}
				ans[patchG] = 'G';
			}
			if (s[i] == 'H' && i - patchH > k) {
				++cnt;
				if (i + k >= n) {
					patchH = n-1;
					if (ans[patchH] == 'G') { patchH--; }
				} else {
					patchH = i + k; 
				}
				ans[patchH] = 'H';
			}
		}
		cout << cnt << endl << ans << endl;
	}
    return 0;
}

SCM

Question

给出一个由 # 和 . 组成的矩阵，其中我们假设 # 代表一个传感器，如果一个传感器的相邻 \(8\) 个各自内有另外一个传感器，那么我们称这两个传感器是关联的，而且这种关系性是可以传递的，相互关联的传感器为一组，问一共有几组传感器

Solution

使用并查集，把相邻的传感器看成是一个祖先的，然后查询有几个祖先就好了

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int H,W,g[maxn][maxn],fa[maxn*maxn],tot,ans,hsh[maxn*maxn];
char mp[maxn][maxn];
const int flg[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
int getfa(int x){
    return (fa[x]==x)?x:fa[x]=getfa(fa[x]);
}
int main(){
    freopen("C.in","r",stdin);
    freopen("C.out","w",stdout);
    scanf("%d%d\n",&H,&W);
    for(int i=1;i<=H;i++)scanf("%s",mp[i]+1);
    for(int i=1;i<=H;i++)
    for(int j=1;j<=W;j++){
        g[i][j]=++tot;
        fa[tot]=tot;
    }
    for(int i=1;i<=H;i++)
    for(int j=1;j<=W;j++)if(mp[i][j]=='#'){
        for(int k=0;k<8;k++)if(mp[i+flg[k][0]][j+flg[k][1]]=='#'){
            int fx=getfa(g[i][j]),fy=getfa(g[i+flg[k][0]][j+flg[k][1]]);
            if(fx==fy)continue;
            fa[fx]=fy;
        }
    }
    
    for(int i=1;i<=H;i++)
    for(int j=1;j<=W;j++)if(mp[i][j]=='#'){
        int F=getfa(g[i][j]);
        if(hsh[F]==0) ans++,hsh[F]=1;
    }
    printf("%d\n",ans);
    return 0;
}

Smartest child

Question

给出两个长度为 \(M\) 的最大值为 \(N\) 的序列 \(S,T\) , 我们需要构造一个长度为 \(N\) 的由 0/1 组成的序列 \(X\)，若能构造出满足 \(X_{S_i} \ne X_{T_i}\) 的 \(X\) 那么称 \((S,T)\) 是 XiaoMo favourite sequence ，问是否可以构造出来

Solution

我们可以把 \(X\) 的 0/1 看成是对点的分类，0为一类，1为一类，然后 \((S,T)\) 相当于对这些点建边，给出了一些边，如果我们能对 \(X\) 分成一个二分图的话，那么就是 yes

那么就有几种判定二分图的方法

我们可以先给图建边，然后dfs给点染色，每一层的颜色和上一层相反(0->1，1->0)

如果存在矛盾点，那么就不能染色成功，就是 No

第二种方法就是 分类 并查集，如果两个点一个是 \(0\) 一个是 \(1\) 那么我们就把 \(i\) 和 \(j+N\) 连边，\(j\) 和 \(i+N\) 连边，正常处理就好了

洛谷题解链接

Code

染色

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int N,M,a[maxn],b[maxn];
vector<int> E[maxn];
int vis[maxn];

void dfs(int x,int val){
    vis[x]=val;
    int len=E[x].size();
    for(int j=0;j<len;j++){
        int son=E[x].at(j);
        if(vis[son]==val) {printf("No\n");exit(0);}
        if(!vis[son])dfs(son,-val);
    }
}
int main(){
    freopen("D.in","r",stdin);
    cin>>N>>M;
    for(int i=1;i<=M;i++)cin>>a[i];
    for(int i=1;i<=M;i++)cin>>b[i];
    for(int i=1;i<=M;i++){
        E[a[i]].push_back(b[i]);
        E[b[i]].push_back(a[i]);
    }
    for(int i=1;i<=N;i++)if(!vis[i]){
        dfs(i,1);
    }
    printf("Yes\n");
    return 0;
}

分种类并查集

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int N,M,a[maxn],b[maxn];
int fa[maxn<<1];
int getfa(int x){
    return fa[x]==x?x:fa[x]=getfa(fa[x]);
}
void merge(int x,int y){
    int fx=getfa(x),fy=getfa(y);
    if(fx!=fy) fa[fx]=fy;
}
int main(){
    freopen("D.in","r",stdin);
    cin>>N>>M;
    for(int i=1;i<=(N<<1);i++) fa[i]=i;
    for(int i=1;i<=M;i++) cin>>a[i];
    for(int i=1;i<=M;i++) cin>>b[i];
    for(int i=1;i<=M;i++){
        int fx=getfa(a[i]),fy=getfa(b[i]);
        if(fx==fy) {printf("No\n");return 0;}
        merge(a[i],b[i]+N);
        merge(b[i],a[i]+N);
    }
    printf("Yes\n");
    return 0;
}

记录路径并查集

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=3e5+5;
LL n,m,a[N],b[N],fa[N],to[N];
LL find(LL x)
{
	if(fa[x]==x)return x;
	LL t=find(fa[x]);
	to[x]+=to[fa[x]];
	return fa[x]=t;
}
int main()
{
    freopen("D.in","r",stdin);
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%lld",&b[i]);
	}	
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		LL fx=find(a[i]),fy=find(b[i]);
		if(fx==fy)
		{
			if((to[a[i]]+to[b[i]])%2==0)
			{
				puts("No");
				return 0;
			}
		}
		else
		{
			fa[fx]=fy;
			to[fx]=1-(to[a[i]]+to[b[i]])%2;
		}
	}
	puts("Yes");
}