首页 > 代码库 > SGU 137.Funny String
SGU 137.Funny String
题目描述
一个序列S1 S2 S3... Sn 如果满足 新序列 S1-1 S2 S3 ...Sn+1能够通过旋转的操作(不是翻转)来得到旧的序列,那么这个序列就叫做Funny序列。例如 1 2 1 2 2就是Funny序列,1 2 1 2 就不是
输入
给定一个数N,表示序列长度。一个数K,表示序列中所有数之和。 gcd(N,K)=1(这能保证本题一定有解)
输出
一行,N个数,表示满足条件的序列。
样例输入
9 16
样例输出
1 2 2 2 1 2 2 2 2
Solution:
假设原串S为,S0,S1....Sn-1.
旋转t次后为,St,St+1....St-1
根据对应的关系可知,
S0==St,S1==St+1,
即Si == Sj ,当 i mod t==j nod t 时成立。
读入n,和k之后,令S中所有元素都为 p=k/n
那么还剩下k mod n,没有分配.
由St=S0+1,知St=S2*t==Sm*t=p+1;
Sn-1=S0+1=p+1;
令 d=k mod n,即要分配的1的个数为d,
当 d*t%n==n-1;此时d个一全部分配完.
由此,先枚举t,确定t的大小.
再确定得到了1的那些元素,最后输出即可
参考代码:
#include <iostream>using namespace std;int n, k, t;int f[1000];int main() { cin >> n >> k; for (t = 1; t < n; t++) if ( (n - 1) == (k % n) *t % n) break; for (int i = t; i != n - 1; i = (i + t) % n) f[i] = 1; f[n - 1] = 1; for (int i = 0; i < n; i++) cout << k / n + f[i] << ‘ ‘;}