首页 > 其他 > 详细

SGU 137.Funny String

时间:2014-07-16 20:12:51      阅读:463      评论:0      收藏:0      [点我收藏+]

题目描述

      一个序列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,

             即S== 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] << ‘ ‘;
}

 

  

 

 

             

SGU 137.Funny String,布布扣,bubuko.com

SGU 137.Funny String

原文:http://www.cnblogs.com/keam37/p/3837074.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!