NOIP模拟赛[2]

#UsernameName机器翻译
100
最大和
100
爱情经验值
100
Total
300
1copyright张淇 100
02:20
100
02:32
0
03:37
200
08:44
2pang陈浩南 100
01:55
100
03:04
0
04:00
200
09:15
3mmaayy马悦程 100
03:41
100
03:41
0
03:52
200
11:30
4chestnut栗明磊 90
02:46
60
03:04
-
150
06:00
5shiniestasia李松轩 100
02:23
40
03:43
0
03:50
140
10:22
6yigong许开彦 100
03:43
-
-
100
03:48
7jyjy田宇航 100
03:00
0
03:58
-
100
07:08
8tjtzgby郭博源 100
03:15
0
03:57
-
100
07:28
91036850657邸新澈 100
03:27
0
03:57
-
100
07:39
10czm陈张萌 100
02:55
0
03:58
0
03:49
100
11:08
11heheda吴梦堉 100
03:59
0
03:39
0
03:38
100
11:36
122327129970王科澳 100
03:26
0
03:59
0
03:56
100
11:37
13zyfzyf张烨飞 100
03:50
0
03:54
0
03:55
100
11:55
14l90537517刘宇飞 20
03:20
0
03:48
0
03:56
20
11:25
1518166167张家辉 10
03:13
0
03:46
-
10
07:10
16zhang张品先 0
03:59
-
-
0
04:04
17592ddd文卓达 0
03:47
0
03:49
0
03:48
0
11:44

【问题描述】
小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。
这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替
换。对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用
它进行翻译;如果内存中没有,软件就会在外存中的词典内查找,查出单词的中文含义然后翻译,
并将这个单词和译义放入内存,以备后续的查找和翻译。
假设内存中有m个单元,每单元能存放一个单词和译义。每当软件将一个新单词存入内存前,
如果当前内存中已存入的单词数不超过m − 1,软件会将新单词存入一个未使用的内存单元;若内
存中已存入m个单词,软件会清空最早进入内存的那个单词,腾出单元来,存放新单词。
假设一篇英语文章的长度为n个单词。给定这篇待译文章,翻译软件需要去外存查找多少次词
典?假设在翻译开始前,内存中没有任何单词。
【输入】
输入文件为input.txt。
第一行为两个正整数m和n,代表内存容量和文章的长度。
第二行为n个非负整数,按照文章的顺序,每个数(大小不超过1000)代表一个英文单词。文
章中两个单词是同一个单词,当且仅当它们对应的非负整数相同。
【输出】
输出文件为output.txt。
共1行,包含一个整数,为软件需要查词典的次数。
【输入输出样例】
input.txt
3 7
1 2 1 5 4 4 1
output.txt
5
【样例解释】
整个查字典过程如下:每行表示一个单词的翻译,冒号前为本次翻译后的内存状况:
空:内存初始状态为空。
1.1:查找单词1并调入内存。
2.1 2:查找单词2并调入内存。
3.1 2:在内存中找到单词1。
4.1 2 5:查找单词5并调入内存。
5.2 5 4:查找单词4并调入内存替代单词1。
6.2 5 4:在内存中找到单词4。
7.5 4 1:查找单词1并调入内存替代单词2。
【数据范围】
对于10%的数据有m = 1,n ≤ 5;
对于100%的数据有1 ≤ m ≤ 1000,0 ≤ n ≤ 100,0 ≤每个英文单词≤ 1000。

T1水题。。。。现在才发现似乎it.end()和–it.end()指向的是同一个元素。。。。

#include<cstdio>
#include<set>
#include<queue>
using namespace std;
queue<int> q;
set<int> s;
int m,n,ans;
int main(){
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++){
		int a;
		scanf("%d",&a);
		if(s.find(a)==s.end()){
			if(q.size()==m){
				s.erase(q.front());
				q.pop();
				s.insert(a);
				q.push(a);
				ans++;
			}
			else
			{
				s.insert(a);
				q.push(a);
				ans++;
			}
		}
	}
	printf("%d",ans);
}

T2DP,找出最大段和最小段。。。。。写正解的时候数组开小了还忘记改(捂脸

【问题描述】
n个数围成一圈,要求从中选择若干个连续的数(注意每个数最多只能选一次)加起来,问能
形成的最大的和。
【输入】
输入文件为input.txt。
第一行输入n,表示数字的个数。
第二行输入这n个数字。
【输出】
输出文件为output.txt 。
共1行,为最大和。
【输入输出样例】
input.txt
8
2 -4 6 -1 -4 8 -1 3
output.txt
14
【数据范围】
对于40%的数据,1 ≤ n ≤ 300;
对于60%的数据,1 ≤ n ≤ 2000;
对于100%的数据,1 ≤ n ≤ 100000,答案在int(pascal 是longint)范围内。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,ans,dp[100010],a[100010],dp2[100010],ansa,ansb,s;
int main(){
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)dp[i]=max(dp[i-1]+a[i],a[i]),ansa=max(ansa,dp[i]);
	for(int i=1;i<=n;i++)dp2[i]=min(dp2[i-1]+a[i],a[i]),ansb=min(ansb,dp2[i]);
	for(int i=1;i<=n;i++)s+=a[i];
	printf("%d",max(ansa,s-ansb));
} 

 

此条目发表在DP, JCYZOJ, NOIP, 线形DP分类目录。将固定链接加入收藏夹。