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]," \n"[i==n]);

	}

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

		printf("%d%c",bbb[i]," \n"[i==n]);

	}

	return 0;

}

\(100\%\)

换根DP。

巴特西

20191028 牛客网CSP-S Round2019-1

仓鼠的石子游戏

问题描述

输入格式

输出格式

数据规模与约定

题解

\(\mathrm{Code}\)

乃爱与城市的拥挤程度

问题描述

题解

小w的魔术扑克

问题描述

最新文章

热门文章