培训套题1

发表于 2016-11-08   |   分类于 动态规划  |  访问: 40 次

enc

【问题描述】
考虑一种简单的加密算法。
假定所有句子都由小写英文字母构成,对于每一个字母,我们将它唯一地映 射到另一个字母。
例如考虑映射规则: a->b, b->c, c->d, d->a. 那么单词 bad 就会被映射为 cba。
这个映射规则的“逆 映射规则”为:b->a, c->b, d->c, a->d。
对于密文 cba,我们很容易将它解密为 bad。
当然,这样的映射需要保证每一个字母映射到的字母是不同的(即不可以出 现两个不同的字母映射到同一个字母,否则将会无法解密)。
一种常见的密码攻击方式被称为已知明文攻击。
具体地,在你不知道映射表 的情况下,给你一段明文和对应的密文,你可以推导出一些的映射规则,下一次 你收到一条密文,你就可能可以解密它。
现在你需要完成这样的一个系统。
【输入格式】
第一行包含一个字符串,仅包含小写字母,表示一段明文。
第二行包含一个字符串,仅包含小写字母,表示这段明文对应的密文,保证 两行长度相同。
第三行包含一个字符串,仅包含小写字母,表示你需要解密的密文。
【输出格式】
输出共一行,表示输入中第三行密文对应的明文。
如果不能解密,输出 “ERROR”(不包含引号)。
注意输入可能出现不自恰的情况。
【样例输入】
ab
cc
cc
【样例输出】
ERROR
【样例输入】
ab
ab
c
【样例输出】
ERROR
【样例输入】
abcde
bcdea
cad
【样例输出】
bec
【数据范围与规定】
对于100%的数据,所有字符串长度<=1000。

乍一卡会以为这题是水题,非常简单,其实真的非常简单。

用点数学名词,这题就是模拟一下双射现象,判断有没有重复映射之类的东西,或者压根不知道映射的值的情况。

但,有个特殊情况,当已经映射25个字母的时候,并且一一对应了,这时候需要手动把最后一个映射过去。

。。。。。我就是这个点被卡的,,,,,

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int a1[44],a2[44],ans[1010];
char s1[1010],s2[1010],s3[1010];
int main(){
	scanf("%s%s%s",s1,s2,s3);
	int l2=strlen(s2),cnt=0;
	bool flag=false;
	for(int i=0;i<l2;i++){
		if(a1[s1[i]-'a'+1] || a2[s2[i]-'a'+1]){
			if(a1[s1[i]-'a'+1]!=s2[i]-'a'+1 || a2[s2[i]-'a'+1]!=s1[i]-'a'+1){
				flag=true;
				break;
			}
		}
		else{
			++cnt; 
			a1[s1[i]-'a'+1]=s2[i]-'a'+1;
			a2[s2[i]-'a'+1]=s1[i]-'a'+1;
		}
	}
	if(cnt==25){
		int u,v;
		for(int i=1;i<=26;i++)
			if(!a1[i])
				u=i;
		for(int i=1;i<=26;i++)
			if(!a2[i])
				v=i;
		a1[u]=v;
		a2[v]=u;
	}
	if(flag)
		printf("ERROR\n");
	else{
		int l=strlen(s3);
		for(int i=0;i<l;i++){
			if(!a2[s3[i]-'a'+1]){
				flag=true;
				break;
			}
			else
				ans[i]=a2[s3[i]-'a'+1];
		}
		if(flag)
			printf("ERROR\n");
		else{
			for(int i=0;i<l;i++)
				printf("%c",ans[i]+'a'-1);
		}
	}
	return 0;
}

 

【问题描述】

zhx 有 N 个妹子,他对第 i 个妹子的好感度为 , 且所有 ,两两不相等。
现 在 N 个妹子随意站成一排,他要将她们根据好感度从小到大排序。
他使用的是 冒泡排序算法(详见下)。
如果排序过程中好感度为的妹子和好感度为的妹 子发生了交换,那么她们之间会发生一场口角。
现在 zhx 想知道,给定妹子的初始排列,在排序完成后,最多存在多少个妹 子,她们任意两人之间没发生过口角。

正式地,考虑对数组进行冒泡排序,如果和在排序过程中发生交换, 那么在两个元素之间连一条边。
你需要求出,排序结束后,最多存在多少个元素, 其中任意两个元素之间不存在连边。
【输入格式】
第一行两个整数 N,表示妹子数量。
接下来一行 N 个整数,表示初始第 i 个妹子的好感度。
【输出格式】
一行一个整数,表示最多满足要求的妹子的个数。
【样例输入】
3
3 1 2
【样例输出】
2
【样例解释】
{1, 2}。
【数据规模与约定】
对于30%的数据,1 ≤ ≤ 16。
对于70%的数据,1 ≤ ≤ 5000。
对于100%的数据,1 ≤ ≤ 100000, 0 ≤ < 。

乍一看,会以为这题非常的难,因为n<=100000,那么暴力建边就非常的麻烦。[准确的说,会超时]

其实这题真的很难。

首先题目的意思大概是求一个独立集,最大独立集的元素个数,使得集合里面的所有点两两没有连边。

当i<j and a[i]>a[j]时才需要连边,那么怎样的点没有连边呢,就是i<j时a[i]<a[j],这是显然的。

既然是求一个最大的集合,那就是说我们要求的是尽可能多的i<j,a[i]<a[j]的情况,即求最长上升子序列。

没错,求最长上升子序列。。。。。

e9d9d96e2feb4b04b3ea5f458fd906d0

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int _maxn=100010;
int a[_maxn],dp[_maxn],ans,n;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int d;
	for(int i=1;i<=n;i++){
		d=lower_bound(dp+1,dp+ans+1,a[i])-dp;
		if(d>ans)	dp[++ans]=a[i];
		else		dp[d]=a[i];
	}
	printf("%d\n",ans);
	return 0;
}

 

发表新评论

© 2017 Powered by Typecho & Theme Quark