NOIP提高组练习（1）

传送门：点击传送（宣传一下OJ）

第一题，潜伏者

分析

这道题目的题意无非是：输入一些字符变换规则，再输入密文，先判断字符串的合法性，再把密文按规则翻译为原文。

因为考虑到加密时是字符的转换，我们采用map来解决问题。

代码

#include<bits/stdc++.h>
using namespace std;
int i,c1[200],c2[200];
string a,b,s;
map<char,char>m;
int main(){
	cin>>a>>b>>s;
	for(i=0;i<a.size();i++){//在a中循环，将a与b放入map中映射
		if(((a[i]<'A'||a[i]>'z')||(b[i]<'A'||b[i]>'Z'))||(m.count(a[i])&&m[a[i]]!=b[i])){//如果有字符不输入大写字母，或者与已有的规则相悖，则输出Failed
			puts("Failed");
			return 0;
		}
		c1[a[i]]=c2[b[i]]=1;//记录
		m[a[i]]=b[i];//放入map
	}
	for(i=65;i<=90;i++)
		if(c1[i]==0||c2[i]==0){//有字符未在规则中出现，也输出Failed
			puts("Failed");
			return 0;
		}
	for(i=0;i<s.size();i++){//遍历一遍密文
		if(m.count(s[i])==0){//有密文在规则中未出现，还是输出Failed
			puts("Failed");
			return 0;
		}
		s[i]=m[s[i]];//否则转换
	}
	cout<<s<<endl;
	return 0;
}

第二题 机器翻译

分析

此题纯模拟，随便调一个队列（queue）加一个用来记录的数组就可以过，所以不想赘述。

代码

#include<bits/stdc++.h>
using namespace std;
int i,j,k,c,m,n,cnt,ago[1005];
queue<int>a;//此题中我们使用队列来模拟存储过程
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++){
		scanf("%d",&k);
		if(ago[k])//如果内存中已经存在k的翻译了，则不需要调用外存
			continue;
		cnt++;//调用次数+1
		if(c==n){//空间已满
			ago[a.front()]=0;//将第一个词语的翻译清空
			a.pop();
			a.push(k);//放入新的翻译
			ago[k]=1;
		}
		else{
			c++;//放入k的翻译
			a.push(k);
			ago[k]=1;
		}
	}
	printf("%d\n",cnt);
	return 0;
}

第三题 铺地毯

分析

这道题如果开数组记录覆盖的地毯的话，恭喜你，时间爆炸+空间爆炸

所以，其实可以用数组记录地毯的xy坐标，在输入询问的xy后，与所有地毯xy坐标比较，如果询问的xy在某一个地毯的xy坐标内的话，则输出。如果没有地毯能覆盖询问的xy，输出-1。

代码

#include<bits/stdc++.h>
using namespace std;
int i,j,k,m,n,x,y,a[10005][5];
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d%d%d%d",&a[i][1],&a[i][2],&x,&y);//输入地毯左上角的xy与地毯的长宽
		a[i][3]=a[i][1]+x,a[i][4]=a[i][2]+y;//计算出地毯右下角的xy
	}
	scanf("%d%d",&x,&y);
	for(i=n;i>=1;i--)
		if(x>=a[i][1]&&x<=a[i][3]&&y>=a[i][2]&&y<=a[i][4]){//在范围内
			printf("%d\n",i);
			return 0;
		}
	puts("-1");//找不到
	return 0;
}

第四题 DNA序列

分析

这道题，我的第一想法为截取子串，通过map计数，期望得分：100，实际得分：80。

然后请教了一下旁边的巨佬，恍然大悟，使用4进制+桶实现满分代码。

代码

#include<bits/stdc++.h>
using namespace std;
int i,j,k,m,n,a[10000005];
string s;
int main(){
	cin>>s;
	scanf("%d",&k);
	for(i=0;i<=s.size()-k;i++){
		int x=0;//记录四进制数
		for(j=i;j<i+k;j++){
			if(s[j]=='A')
				x*=4;//四进制情况下的0
			if(s[j]=='G')
				x=x*4+1;//四进制情况下的1
			if(s[j]=='C')
				x=x*4+2;//四进制情况下的2
			if(s[j]=='T')
				x=x*4+3;//四进制情况下的3
		}
		a[x]++;//用桶计数
	}
	for(i=0;i<=10000000;i++)
		m=max(m,a[i]);
	printf("%d\n",m);
	return 0;
}