阿里郎
题目大意
n 名演员，将按n的所有约数d进行分组。同一组中的演员们将会手拉手围成一个环。第一个环中是1;d+1;2d+1;3d+1……n−d+1，第二个环中是2;d+2;2d+2;3d+2……n−d+2。依次类推。
环中每个相邻的人的衣服颜色不能相同，颜色有a~z，共26种。
给出人数，求出每个演员的衣服颜色。如果颜色不够，输出“impossible”
输入样例
7
输出样例
abababc
数据范围
2 <= n <= 300000
思路
这道题按着题目要求模拟就行了，只是原题题意很难看懂。
枚举每一个人，第一个人直接用第一种颜色，其他人枚举每一个圈，它旁边的人的衣服颜色都不能选，如果全部不能选则多开一种颜色，否则找一个颜色用。
最后如果颜色个数超过了26，就输出“impossible”。否则就输出答案。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,y[10001],ys;
char ans[300001],d='a';
bool in[27];
int main()
{
// freopen("arilang.in","r",stdin);
// freopen("arilang.out","w",stdout);
scanf("%d",&n);//读入
for (int i=1;i*i<=n;i++)
if (n%i==0)//记录下n所有的约数
{
y[++ys]=i;
y[++ys]=n/i;
if (i==n/i) ys--;
}
sort(y+1,y+ys+1);//把约束们从小到大排序
ans[1]='a';//初始化
for (int i=2;i<=n;i++)
{
memset(in,0,sizeof(in));//初始化
int b=0;
bool biao=0;
for (int j=1;j<=ys;j++)
if (y[j]>=i) break;//会退成负数则直接退出
else
{
if (!in[ans[i-y[j]]-96])//圈前面那个人的颜色
{
in[ans[i-y[j]]-96]=1;
b++;
}
if (!in[ans[(i+y[j])%n]-96])//后面那个人的颜色
{
in[ans[(i+y[j])%n]-96]=1;
b++;
}
if (b>=d-96)//所有颜色都用完了
{
d++;
ans[i]=d;
biao=1;
break;
}
}
if (!biao)
for (int j=1;j<=d-96;j++)
if (!in[j])//找可以用的颜色
ans[i]=j+96;//填上去
}
if (d>'z') printf("impossible");//需要的颜色超过了26种
else for (int i=1;i<=n;i++)
putchar(ans[i]);//输出
// fclose(stdin);
// fclose(stdout);
return 0;
}