hdoj 2371 decoded string. Decode the Strings

本文主要是介绍hdoj 2371 decoded string. Decode the Strings，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=2371

题意：给出编码的原则，给一个字符串，输出该字符串经过m次解码后的字符串。

啊啊啊啊。。。。无耻的看错题意了，以为给出字符串输出经过m次解码的后的字符串，样例死活过不了，赛后才发现问的是“decoded string”. 即解码后的字符串。。

思路：对于

5 3

2 3 1 5 4

helol

问经过3次按照2 3 1 5 4编码后是helol的原字符串是什么，即对helol经过3次解码。

2 3 1 5 4

1 2 3 4 5

上面2 3 1 5 4的意思是在2 3 1 5 4位置的字符编码后在1 2 3 4 5 的位置上。那么 1-2,2-3,3-1，（1,2,3）在一个集合里；5-4,4-5，（4,5）在一个集合中。集合（1,2,3）的循环节是3，集合（4,5）的循环节是2，那么整个字符串的循环节是6.

我拿vector存每个集合里的节点。

#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <limits.h>
#include <algorithm>
#define LL long long
//define LL __int64
#define abs(x) ((x)>0?(x):-(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define max3(a, b, c) (a>b?max(a, c):max(b, c))
#define min3(a, b, c) (a<b?min(a, c):min(b, c))
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define min4(a, b, c, d) min(min(a, b), min(c, d))
#define Ee 2.718281828459045
#define Pi acos(-1.0)
#define eps 1e-8
#define INF 1 << 30
using namespace std;int n,m;
char s[85];
int a[85];
int vis[85];
int cnt;vector <int> edge[85];int gcd(int a, int b)
{if(b == 0)return a;return gcd(b,a%b);
}int solve(int t)
{int num = 1;vis[t] = cnt;edge[cnt].push_back(t);while(1){t = a[t];if(!vis[t]){vis[t] = cnt;num++;edge[cnt].push_back(t);}else break;}return num;
}int main()
{while(~scanf("%d %d",&n,&m)){if(n == 0 && m  == 0) break;for(int i = 1; i <= n; i++){scanf("%d",&a[i]);edge[i].clear();}getchar();gets(s+1);memset(vis,0,sizeof(vis));int ans = 1;for(int i = 1; i <= n; i++){if(!vis[i]){cnt++;	//集合数加1int res = solve(i); // res代表该集合的元素个数ans = (ans*res)/gcd(ans,res);}}int tmp = m%ans;if(tmp == 0){puts(s+1);continue;}char ss[85];for(int i = 1; i <= n; i++){int num = vis[i];for(int j = 0; j < (int)edge[num].size(); j++){if(edge[num][j] == i){ss[ edge[num][(j+tmp)%edge[num].size()] ] = s[i];break;}}}ss[n+1] = '\0';puts(ss+1);}return 0;
}

这篇关于hdoj 2371 decoded string. Decode the Strings的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---