数论】【贪心】"/>
jzoj阿里郎【数论】【贪心】
>Description
n 名演员,将按n的所有约数d进行分组, {n的所有约数,数学表示(d | n),}每组有n /d 人。,同一组中的演员们将会手拉手围成一个环。第一个环中是1; d + 1; 2d + 1; 3d + 1; : : : ; n-d + 1。第二个环中是2; d+2; 2d+2; 3d+2; : : : ; n-?d+2。依次类推。第d 个环中是d; 2d; : : : ; n。
现在你要为他们分配服装。每个环中相邻的人衣服颜色都不能相同。你只知道了n 的值。衣服只有26 种不同颜色。你能对任何d 值完成任务吗?
>Input
一行,一个整数n。
>Output
若有解,输出一行n 个字符。第i 个字符表示第i 号演员衣服的颜色,用小写英文字母表示。若有多种方案,请输出字典序最小的方案。
若无解,你得给家属留些话,输出"Impossible" 。
>Sample Input
7
>Sample Output
abababc
2 <= n <= 300000.
>解题思路
听了别人讲题以后,还是有点懵逼(黑人问号),然后晚上又问了一下cyz大佬题意后,按照我听懂的内容打了一下,打的过程中瞬间明白,直接A了这道题。
其实手动模拟一下这些各种环,就可以发现:与某个数相邻关系的数,全都在这个数±n的所有约数中,如果越界就按照环的规则处理。
接着就可以使用贪心:枚举每个数,去除与之相邻的数的颜色,(这时只看选过的颜色)剩下中的第一个数为这个数的颜色,如果没有剩下的颜色了,就再开一个颜色。
>代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,f,a[300005],c[300001];
bool yd[26];
int main()
{
// freopen("arilang.in","r",stdin);
// freopen("arilang.out","w",stdout);memset(a,-1,sizeof(a));scanf("%d",&n);f=-1;for(int i=1;i<n/2;i++)if(n%i==0) c[++c[0]]=i,c[++c[0]]=n/i; ///记录约数for(int i=1;i<=n;i++){memset(yd,0,sizeof(yd));for(int j=1;j<=c[0];j++) //枚举约数{int li=i-c[j],sa=i+c[j];if(li<=0) li+=n;if(sa>n) sa-=n; //这里处理越界yd[a[li]]=yd[a[sa]]=1; //标记排除}for(int j=0;j<=f;j++)if(!yd[j]) {a[i]=j; break;} //如果找到了,就标记然后breakif(a[i]==-1) f++,a[i]=f; //如果没有找到,就再开一个颜色}for(int i=1;i<=n;i++)printf("%c",'a'+a[i]);return 0;
}
更多推荐
jzoj阿里郎【数论】【贪心】
发布评论