Chinaunix首页 | 论坛 | 博客
  • 博客访问: 489983
  • 博文数量: 137
  • 博客积分: 3874
  • 博客等级: 中校
  • 技术积分: 1475
  • 用 户 组: 普通用户
  • 注册时间: 2010-07-05 10:50
文章分类

全部博文(137)

文章存档

2011年(37)

2010年(100)

分类: C/C++

2010-10-21 22:19:03

今天上体育课,羽毛球,哈哈,虽然被虐,但是学会发球了,发现我是后期型的,嘎嘎,开始被虐,后来反虐成功,主要对手累不行了,我还颠儿颠儿的。。。。
回来继续a道题,水题,贡献了一个tle和wa后ac。
这道题说,有n个数字
a1,a2,,,,an
然后给你一个字符串s和一个数字k
然后先把字符串跟上面的数字对齐,s不够的,拿空格补全。
然后进行转换,是这样转换的,对于s每个元素,把这个元素放到另一个字符串的第m个位置,m就是他对应的那个数字。对于k呢,就是这样重复的次数。开始简单模拟,果断的tle了。
因为k可以很大。
其实对于每个字符来说,他每转换一次,就可能换一个位置。那么至多换n次,就回到原来位置了。
这样就分别对每个字符计算周期,然后存储起来。然后用k对每个字符的周期取模就可以了。
--------------------------------------------------------

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;


char arr[2][210];
int key[210];
int round[210];
int block;
int k;

int main()
{
    // freopen("in","rw",stdin);

    while(cin>>block){
    if(block==0)
     break;

    for(int i=0;i<block;++i)
     cin>>key[i];
    for(int i=0;i<block;++i){
     int count =0;
     int index=i;
     while(++count){
        
        index=key[index];
        index--;
        if(index==i)
         break;
        
     }
     round[i]=count;
    }

    while(cin>>k){
     if(k==0)
        break;
     getchar();
     cin.getline(arr[0],block+1);
     int len = strlen(arr[0]);
     for(int j=len;j<block;++j)
        arr[0][j]=' ';
     arr[1][block]=NULL;
     for(int j=0;j<block;++j){
         int cnt = k%round[j];
         int index=j;
         for(int t=0;t<cnt;++t){
         index = key[index];
         index--;
         }
         arr[1][index]=arr[0][j];
     }
     cout<<arr[1]<<endl;
    }
    cout<<endl;
    }
    return 0;
}


阅读(1630) | 评论(1) | 转发(0) |
给主人留下些什么吧!~~

chinaunix网友2010-10-22 11:05:16

很好的, 收藏了 推荐一个博客,提供很多免费软件编程电子书下载: http://free-ebooks.appspot.com