jzoj阿里郎【数论】【贪心】

数论】【贪心】"/>

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;
}