hdoj 2371 decoded string. Decode the Strings

2024-08-28 10:48

本文主要是介绍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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1114551

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

java String.join()的使用小结

《javaString.join()的使用小结》String.join()是Java8引入的一个实用方法,用于将多个字符串按照指定分隔符连接成一个字符串,本文主要介绍了javaString.join... 目录1. 方法定义2. 基本用法2.1 拼接多个字符串2.2 拼接集合中的字符串3. 使用场景和示例3

C# string转unicode字符的实现

《C#string转unicode字符的实现》本文主要介绍了C#string转unicode字符的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随... 目录1. 获取字符串中每个字符的 Unicode 值示例代码:输出:2. 将 Unicode 值格式化

Java中String字符串使用避坑指南

《Java中String字符串使用避坑指南》Java中的String字符串是我们日常编程中用得最多的类之一,看似简单的String使用,却隐藏着不少“坑”,如果不注意,可能会导致性能问题、意外的错误容... 目录8个避坑点如下:1. 字符串的不可变性:每次修改都创建新对象2. 使用 == 比较字符串,陷阱满

IDEA如何将String类型转json格式

《IDEA如何将String类型转json格式》在Java中,字符串字面量中的转义字符会被自动转换,但通过网络获取的字符串可能不会自动转换,为了解决IDEA无法识别JSON字符串的问题,可以在本地对字... 目录问题描述问题原因解决方案总结问题描述最近做项目需要使用Ai生成json,可生成String类型

php中json_decode()和json_encode()

1.json_decode() json_decode (PHP 5 >= 5.2.0, PECL json >= 1.2.0) json_decode — 对 JSON 格式的字符串进行编码 说明 mixed json_decode ( string $json [, bool $assoc ] ) 接受一个 JSON 格式的字符串并且把它转换为 PHP 变量 参数 json

string字符会调用new分配堆内存吗

gcc的string默认大小是32个字节,字符串小于等于15直接保存在栈上,超过之后才会使用new分配。

hdu2072(string的应用)

单词数 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 25447    Accepted Submission(s): 5957 Problem Description lily的好朋友xiaoou333最近很空,他

【UVA】10739 - String to Palindrome(动态规划)

比较水的动态规划 dp[i][j] 将原串 i ~ j 之内的字符转化为回文字符所需要的最小操作次数 其中删除操作和添加操作本质上是一样的。 三个状态转移方程: dp[i][j] = min(dp[i][j] ,dp[i + 1][j]); dp[i][j] = min(dp[i][j] ,dp[i + 1][j - 1]); dp[i][j] = min(dp[i][j] ,dp[