20191028 牛客网CSP-S Round2019-1

花了 (30min) 打了 (180) 分的暴力...

仓鼠的石子游戏

问题描述

链接：https://ac.nowcoder.com/acm/contest/1100/A

仓鼠和兔子被禁止玩电脑，无聊的他们跑到一块空地上，空地上有许多小石子。兔子捡了很多石子，然后将石子摆成n个圈，每个圈由a[i]个石子组成。然后兔子有两根彩色笔，一支红色一支蓝色。兔子和仓鼠轮流选择一个没有上色的石子涂上颜色，兔子每次可以选择一个还未染色的石子将其染成红色，而仓鼠每次可以选择一个还未染色的石子将其染成蓝色，并且仓鼠和兔子约定，轮流染色的过程中不能出现相邻石子同色，谁不能操作他就输了。假设他们两个都使用了最优策略来玩这个游戏，并且兔子先手，最终谁会赢得游戏？

输入格式

第一行输入一个正整数T，表示有T组测试案例。

每组测试案例的第一行输入一个n，表示有n圈石子。第二行输入n个正整数a[i]，表示每个圈的石子数量。

输出格式

对于每组测试案例，如果兔子赢了，输出”rabbit“(不含引号)如果仓鼠赢了，输出"hamster"(不含引号)。

数据规模与约定

本题共有10组测试点数据。
对于前 (30\%) 的数据，满足 (n=1,1 le a[i] le 7,1 le T le 10)

对于前 (60\%) 的数据，满足 (1 le n le 10^3,1 le a[i] le 7,1 le T le 10^2) 。

对于前 (100\%) 的数据，满足 (1 le n le 10^3,1 le a[i] le 10^9,1 le T le 10^2)。

对于测试点 (6) ，在满足前 (60\%) 的数据条件下，额外满足 (a[i]=1) 。

题解

发现对于每一堆来说：

偶数堆相当于没有：不能改变先后手顺序
奇数堆：只能放偶数个
(1)的堆：改变先后手

因此，只保留 (1) 个奇数堆。这个奇数堆进入时是先手的人输。

就相当于用 (1) 的堆改变先后手后，看谁是后手。

发现当 (1) 堆的数目为奇数时， rabbit 赢，否则 hamster 赢。

(mathrm{Code})

#include<bits/stdc++.h>
using namespace std;
 
template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') ch=getchar(),fh=-1;
    else fh=1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=fh;
}
 
const int maxn=1007;
 
int T,n,sum;
int a[maxn];
int cnt;
void reset(){
    sum=cnt=0;
}
 
int main(){
    read(T);
    while(T--){
        read(n);reset();
        for(int i=1;i<=n;i++){
            read(a[i]);
            if(a[i]==1) ++sum;
            else if(a[i]&1) ++cnt;
        }
        cnt=cnt%2;
        if(cnt==0){
            if(sum&1) puts("rabbit");
            else puts("hamster");
        }
        else{
            if(sum&1) puts("rabbit");
            else puts("hamster");
        }
    }
    return 0;
}

乃爱与城市的拥挤程度

问题描述

题解

(80\%)

随机树部分+链

直接暴力跑就完事了。

#include<bits/stdc++.h>
using namespace std;

template <typename Tp>
void read(Tp &x){
	x=0;char ch=1;int fh;
	while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
	if(ch=='-') ch=getchar(),fh=-1;
	else fh=1;
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	x*=fh;
}

const int maxn=100007;
const int maxm=200007;
const int mod=1000000007;

int n,k;
int Head[maxn],to[maxm],Next[maxm],tot=1;

void add(int x,int y){
	to[++tot]=y,Next[tot]=Head[x],Head[x]=tot;
}

int ans,tmp;
int aaa[maxn],bbb[maxn];

int dfs(int x,int fa,int dis){
	int res=1;++ans;
	if(dis==k) return res;
	for(int i=Head[x];i;i=Next[i]){
		int y=to[i];
		if(y==fa) continue;
		res+=dfs(y,x,dis+1);
	}
	tmp=(long long)tmp*(long long)res%mod;
	return res;
}

void solve(int x){
	ans=0,tmp=1;
	dfs(x,0,0);
	aaa[x]=ans,bbb[x]=tmp;
}

int main(){
	read(n);read(k);
	for(int i=1,x,y;i<n;i++){
		read(x);read(y);
		add(x,y);add(y,x);
	}
	for(int i=1;i<=n;i++){
		solve(i);
	}
	for(int i=1;i<=n;i++){
		printf("%d%c",aaa[i]," 
"[i==n]);
	}
	for(int i=1;i<=n;i++){
		printf("%d%c",bbb[i]," 
"[i==n]);
	}
	return 0;
}

(100\%)

换根DP。