HNU:小学期软件实训第三周（这周简单一点，水题较多）

这周就一题背包（double精度恶心人就是

---

本周作业让我感觉比较有收获的题（从高到低）：

8.ab串

5.最大报销额

---

1.部分A+B

题目

【问题描述】

正整数A的“DA（为1位整数）部分”定义为由A中所有DA组成的新整数PA。例如：给定A = 3862767，DA = 6，则A的“6部分”PA是66，因为A中有2个6；给定A = 3862767，DA = 1，则A的“1部分”PA是0，因为A中有0个1。

现给定A、DA、B、DB，请编写程序计算PA + PB。

【输入形式】

输入在一行中依次给出A、DA、B、DB，中间以空格分隔，其中0 < A, B < 1010。

【输出形式】

在一行中输出PA + PB的值。

【样例输入】

3862767 6 13530293 3

【样例输出】

399

题解

这题就取位就行，可以用string取也可以按位找，我这里就按位找了（

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int main(){
	long long a,da,b,db;
	scanf("%lld %lld %lld %lld", &a,&da,&b,&db);
	long long pa=0,pb=0;
	while(a>0){
		long long data = a%10;
		if(data == da)
			pa=pa*10+da;
		a/=10; 
	}
	while(b>0){
		long long data = b%10;
		if(data == db)
			pb=pb*10+db;
		b/=10;
	} 
	printf("%lld", pa+pb);
	return 0;
}

---

2.导弹防御系统

题目

【问题描述】

某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。

【输入形式】

每组输入有两行，

第一行，输入雷达捕捉到的敌国导弹的数量k（k<=25），

第二行，输入k个正整数，表示k枚导弹的高度，按来袭导弹的袭击时间顺序给出，以空格分隔。

【输出形式】

每组输出只有一行，包含一个整数，表示最多能拦截多少枚导弹。

【样例输入】

8
300 207 155 300 299 170 158 65

【样例输出】

6

题解

199几年NOIP的经典题：最大下降子序列（DP）

然后是可以用二分查找优化的，这里就是用二分查找优化的写法（按CCF也应该不会管这种优化吧，不优化也能过

代码

#include<cstdio>
#include<string.h>
#include<iostream>
using namespace std;
const int maxn=100005;
int a[maxn];
int f[maxn];
int main()
{
    int n;
    int l,r,mid;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
		scanf("%d", &a[i]);
    f[0]=1234123412;
    int ans1=0;
    for(int i=1;i<=n;i++){
        if(f[ans1]>=a[i]){
            f[ans1+1]=a[i];//结束点为a[i]
            ans1++; //当前最长不上升序列的长度加一
        }
        else {//二分查找
            l=0;r=ans1;
            while(l<r){
                mid=(l+r)/2;
                if(f[mid]>=a[i])l=mid+1;
                else r=mid;    
            }
            if(l!=0)f[l]=a[i];
        }
    }
    cout<<ans1<<endl;
}

---

3.魔咒词典

题目

【问题描述】

哈利波特在魔法学校的必修课之一就是学习魔咒。据说魔法世界有100000种不同的魔咒，哈利很难全部记住，但是为了对抗强敌，他必须在危急时刻能够调用任何一个需要的魔咒，所以他需要你的帮助。

给你一部魔咒词典。当哈利听到一个魔咒时，你的程序必须告诉他那个魔咒的功能；当哈利需要某个功能但不知道该用什么魔咒时，你的程序要替他找到相应的魔咒。如果他要的魔咒不在词典中，就输出“what?”

【输入形式】

首先列出词典中不超过100000条不同的魔咒词条，每条格式为：

[魔咒] 对应功能

其中“魔咒”和“对应功能”分别为长度不超过20和80的字符串，字符串中保证不包含字符“[”和“]”，且“]”和后面的字符串之间有且仅有一个空格。词典最后一行以“@END@”结束，这一行不属于词典中的词条。
词典之后的一行包含非负整数N（0=<N<=1000），随后是N个测试用例。每个测试用例占一行，或者给出“[魔咒]”，或者给出“对应功能”。

【输出形式】

每个测试用例的输出占一行，输出魔咒对应的功能，或者功能对应的魔咒。如果魔咒不在词典中，就输出“what?”

【样例输入】

[expelliarmus] the disarming charm
[rictusempra] send a jet of silver light to hit the enemy
[tarantallegra] control the movement of one's legs
[serpensortia] shoot a snake out of the end of one's wand
[lumos] light the wand
[obliviate] the memory charm
[expecto patronum] send a Patronus to the dementors
[accio] the summoning charm
@END@
4
[lumos]
the summoning charm
[arha]
take me to the sky

【样例输出】

light the wand
accio
what?
what?

题解

双map正反存是写起来最快也是跑起来最快的办法，至于分割字符串的话，find和substr一顿操作（巴拉巴拉巴拉~

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
int main(){
	string name;
	string fun;
	map<string, string> findfun;
	map<string, string> findname;
	while(1){
		string s;
		getline(cin, s);
		if(s=="@END@")break;
		int pos2 = s.find(']');
		name = s.substr(0, pos2+1);
		fun = s.substr(pos2+2);
		findfun[name] = fun;
		findname[fun] = name;
	}
	int n;
	cin>>n;
	cin.ignore();
	while(n--){
		string s;
		getline(cin, s);
		if(s[0]=='['){
			if(findfun.find(s)!=findfun.end())
				cout<<findfun[s]<<endl;
			else
				cout<<"what?"<<endl;
		}
		else{
			if(findname.find(s)!=findname.end()){
				string ss = findname[s];
				cout<<ss.substr(1,ss.length()-2)<<endl;
			}
			else
				cout<<"what?"<<endl;
		}
	}
	return 0;
}

---

4.打牌

题目

【问题描述】

牌只有1到9，手里拿着已经排好序的牌a，对方出牌b，用程序判断手中牌是否能够压过对方出牌。
规则：出牌牌型有5种

1. 一张 如4 则5…9可压过
2. 两张 如44 则55，66，77，…，99可压过
3. 三张 如444 规则如2
4. 四张 如4444 规则如2
5. 五张 牌型只有12345 23456 34567 45678 56789五个，后面的比前面的均大。

【输入形式】

输入有多行，第一行代表手中的牌，长度不超过200个数字。接下来的每一行代表每次对方出的牌。

【输出形式】

输出有多行，代表手中的牌是否能压过对方出的牌，压过输出YES， 并列出所有可选项，可选项之间用空格分隔。 否则输出NO。

【样例输入】

17624234556367
33
222
34567

【样例输出】

YES 44 55 66 77
YES 666
NO

题解

其实规则1~4本质上都是一样的，可以一起判断。我这里没用string/map之类的方法，就用了最朴素的写法解决这题。记录自己的手牌中每种有几张然后看对手出牌来判断就是

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int have[10];
int main(){
	char ch[201];
	string s;
	scanf("%s", ch);
	s = ch;
	int l = s.length();
	for(int i=0; i<l;i++)
		have[int(ch[i]-'0')]++;
	while(~scanf("%s", ch)){
		s = ch;
		l = s.length();
		bool flag = false;
		if(l<5){
			for(int i = ch[0]-'0'+1; i<10; i++)
				if(have[i]>l-1){
					flag = true;
					break; 
				}
			if(flag){
				printf("YES");
				for(int i = ch[0]-'0'+1; i<10; i++)
					if(have[i]>l-1){
						printf(" ");
						for(int j=0;j<l;j++)
							printf("%d", i);
					}
				printf("\n");
			}
			else printf("NO\n");
		}
		else{
			for(int i = ch[0]-'0'+1; i<6; i++)
				if(have[i]>0 && have[i+1]>0 && have[i+2]>0 && have[i+3]>0 && have[i+4]>0){
					flag = true;
					break;	
				}
			if(flag){
				printf("YES");
				for(int i = ch[0]-'0'+1; i<6; i++)
					if(have[i]>0 && have[i+1]>0 && have[i+2]>0 && have[i+3]>0 && have[i+4]>0){
						printf(" ");
						for(int j=i;j<i+5;j++)
							printf("%d", j);
					}
				printf("\n");
			}
			else printf("NO\n");
		}
	}
	return 0;
}

---

5.最大报销额

题目

【问题描述】现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书（A类）、文具（B类）、差旅（C类），要求每张发票的总额不得超过1000元，每张发票上，单项物品的价值不得超过600元。现请你编写程序，在给出的一堆发票中找出可以报销的、不超过给定额度的最大报销额。

【输入形式】测试输入包含若干测试用例。每个测试用例的第1行包含两个正数 Q 和 N，其中 Q 是给定的报销额度，N（N<=30）是发票张数。随后是 N 行输入，每行的格式为：
m Type_1:price_1 Type_2:price_2 … Type_m:price_m

  其中正整数 m 是这张发票上所开物品的件数，Type_i 和 price_i 是第 i 项物品的种类和价值。物品种类用一个大写英文字母表示。当N为0时，全部输入结束，相应的结果不要输出。

【输出形式】对每个测试用例输出1行，即可以报销的最大数额，精确到小数点后2位。

【样例输入】

200.00 3
2 A:23.50 B:100.00
1 C:650.00
3 A:59.99 A:120.00 X:10.00
1200.00 2
2 B:600.00 A:400.00
1 C:200.50
1200.50 3
2 B:600.00 A:400.00
1 C:200.50
1 A:100.00
100.00 0

【样例输出】

123.50
1000.00
1200.50

题解

这题判断每张发票是否满足条件还是比较简单的，只是记得要先把可能的结果存起来

然后比较复杂的是接下来的01背包，这题属于01背包的一个变种（装箱问题），而我们一般处理这类问题会把重量/体积作为数组的索引进行DP，而这里体积为double就稍微麻烦点

看到题目要求两位小数就想扩大个100倍，结果因为精度问题只过了4个点，所以咱扩大个10000倍（逃

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int f[100000001];
int main(){
	double have;
	int n;
	while(cin>>have>>n && n>0){
		
		int a[31];
		int num=0;
		
		while(n--){
			
			//printf("%d\n", n);
			
			int t;
			bool flag=false;
			double sum=0;
			cin>>t;
			while(t--){
				char ch;
				cin>>ch;
				cin.ignore();
				double qwq;
				cin>>qwq;
				if(ch != 'A' && ch != 'B' && ch != 'C')
					flag = true;
				if(qwq > 600.00)
					flag = true;
				sum+=qwq;
			}
			
			
			if(sum > 1000.00)
				flag = true;
			if(flag)
				continue;
			
			a[num++] = sum*10000;
			
		}
		
		int v = have*10000;
		memset(f, 0, sizeof(f));
	    for(int i=0; i<num; i++)
	    	for(int j=v; j>=a[i]; j--)
	            f[j] = max(f[j],f[j-a[i]]+a[i]);
	    //cout<<f[v]<<endl;
		printf("%.2f\n", (double)f[v]/10000.0);	
	}
	return 0;
}

---

6.带通配符的数

题目

【问题描述】给定一个可以带通配符问号的正整数W，问号可以代表任意一个一位数字。再给定一个正整数X，和W具有同样的长度。问有多少个整数符合W的形式并且比X大？

【输入形式】多组数据，每组数据两行，第一行是W，第二行是X，它们长度相同，在[1..10]之间。

【输出形式】每行一个整数表示结果。

【样例输入】

36?1?8
236428
8?3
910
?
5

【样例输出】

100
0
4

题解

记录所有?的个数，这里需要稍微模拟一下每个?处的取值，而当前?处理完进入下一个?时此处就与另一个数同位置相同。（这样讲可能讲不明白（

代码

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main(){
    string w, x;
    int len, amount;
    int res;
    while (cin >> w >> x){
        res = 0;
        len = w.length();
        amount = 0;
        for (int i = 0; i < len; i++)
            if (w[i] == '?')
                amount += 1;
        for (int i = 0; i < len; i++){
        	if (w[i] != '?'){
                //相等才有继续比下一位的意义
                if (w[i] > x[i]){
                    res += pow(10, amount);
                    break;
                }
                else if (w[i] < x[i])
                    break;
            }
            else{
                amount -= 1;
                res += (9 - (x[i] - '0')) * pow(10, amount); // 比他大的计数就行，如果等于的之后就会计算到，不用考虑 
            }
        }
        cout << res << endl;
    }
    return 0;
}

---

7.愚人节的礼物

题目

【问题描述】

四月一日快到了，Vayko 想了个愚人的好办法——送礼物。嘿嘿，不要想的太好，这礼物可没那么简单，Vayko 为了愚人，准备了一堆盒子，其中只有一个盒子里面装了礼物。盒子里面可以再放零个或者多个盒子。假设放礼物的盒子里不再放其他盒子。用()表示一个盒子，B表示礼物，Vayko 想让你帮她算出愚人指数，即最少需要拆多少个盒子才能拿到礼物。

【输入形式】

本题目包含多组测试，请处理到文件结束。每组测试包含一个长度不大于 1000, 只包含’(‘,’)’和’B’三种字符的字符串，代表 Vayko 设计的礼物透视图。你可以假设，每个透视图画的都是合法的。

【输出形式】

对于每组测试，请在一行里面输出愚人指数。

【样例输入】

((((B)()))())
(B)

【样例输出】

4
1

题解

看到这种题，有良好做题经验的人第一反应应该是括号匹配，也就是栈模拟。

但是这里没有多种类的括号，所以只模拟栈高度就够了，遇到B的时候就break输出栈高度就行

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack> 
using namespace std;
int main(){
	string s;
	while(cin>>s){
		int l=s.length();
		int qwq=0;
		for(int i=0;i<l;i++){
			if(s[i]=='(')qwq++;
			else if(s[i]==')')qwq--;
			else break;
		}
		printf("%d\n", qwq);
	} 
	return 0;
}

---

8.ab串

题目

【问题描述】

   给定一个由字符'a'和字符'b'组成的字符串，可以删除若干字符，使得剩下来的字符串满足前后段为a，中间段为b（aaa....aaabbbb.....bbbbaaa.....aaa）,区段可以没有字符（ba,ab,b,aa都是合法的），求最长剩下字符串的长度。

【输入形式】

  输入为一行一个长度不超过5000的非空字符串，字符串仅由字符'a'和字符'b'组成。

【输出形式】

  输出为一个整数，表示符合要求的最长剩下字符串长度

【样例输入1】

abba

【样例输出1】

4

【样例输入2】

bab

【样例输出2】

2

题解

这题也老麻烦了。。。

说是前缀和，但我习惯把他看作普通的预处理（确实是前缀和

把ab分别做前缀和处理，那么i->j段的a个数就有numa[j]-numa[i-1]，b也一样

而这题其实只是找两个位置，也就是前面的a串与中间b串的分割点、以及中间b串与后面a串的分割点，枚举并迭代更新即可（可以看作dp也可以看作暴力）

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
const int N = 5000;
int numa[N], numb[N];

int main(){
    string s;
    cin>>s;
    map<char, int> mp;
    int len=s.length();
    
    //预处理前缀和
    if (s[0] == 'a')
        numa[0] = 1;
    else
		numb[0] = 1;
    for (int i = 1; i < len; i++){
        if (s[i] == 'a'){
            numa[i] = numa[i - 1] + 1;
            numb[i] = numb[i - 1];
        }
        else if (s[i] == 'b'){
            numb[i] = numb[i - 1] + 1;
            numa[i] = numa[i - 1];
        }
        mp[s[i]]++;
    }
    
    int MAX = max(mp['b'] ? mp['a'] + 1 : mp['a'], mp['b']);
    
    for(int r = 0; r < len; r++){
        for (int l = 0; l < r; l++){
            int ans1 = numa[l];                         //第一段a的个数
            int ans2 = numb[r] - numb[l - 1];           //中间段b的个数
            int ans3 = numa[len - 1] - numa[r - 1]; 	//后面一段a的个数
            MAX = max(MAX, ans1+ans2+ans3);
        }
    }
    cout << MAX << endl;
    return 0;
}

---

9.占座位

题目

【问题描述】sun所在学校的教室座位每天都是可以预占的。
一个人可以去占多个座位，而且一定是要连续的座位，如果占不到他所要求的这么多座位，那么他就一个座位也不要了。为了降低难度，每次分配座位按座位号从小到大查找，采用最先适配法分配座位。

【输入形式】输入有多组数据。
每组数据输入座位排数n，0<n<=100（座位的排列数相等，座位是按每行从左到右依次排序的, 第1行的最右边一个座位与第二行的第一个座位视为连续座位），m（ 0<m<=min(100,n*n) ）个人。
然后输入k（0<k<=100），最后输入k个命令。
命令只有两种：

1. in id num（代表id,0<=id<m,要占num个座位，若占不到连续的num(0<num<=20)个座位表示该命令无效）
2. out id（代表id要释放他之前占的所有座位）
   注意：如果id之前占过座还没释放那么之后他的in命令都是无效的，
   如果id之前没占过座位那么他的out命令也是无效的。

【输出形式】对每个in命令输出yes或者no，如果命令有效则输出yes，无效则输出no。
在yes no后面只带有回车，不带其他任何字符。

【样例输入】

4 10
9
in 1 7
in 2 3
in 3 3
in 3 3
in 4 3
out 2
in 5 6
out 3
in 5 6

【样例输出】

yes
yes
yes
no
yes
yes
no
yes
yes

题解

这题其实和第一周第十题内存管理其实几乎是一样的（

我这边就不像那题一样写单链表了，过于麻烦，这次就写个纯模拟就好啦！

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int use[10010];
struct node{
	bool have=false;
	int left=-1;
	int right=-1;
}id[10010];

int main(){
	int n,m,k,len;
	scanf("%d %d %d", &n, &m, &k);
	len = n*n;
	for(int i=0;i<len;i++)
		use[i]=-1;
	while(k--){
		string s;
		int a,b;
		cin>>s>>a;
		if(s=="in"){
			cin>>b;
			if(id[a].have){
				printf("no\n");
				continue;
			}
			int i;
			for(i=0;i<len;i++){
				if(use[i] == -1){
					int j;
					for(j=i; j<i+b && j<len; j++)
						if(use[j] != -1)
							break;
					if(j==i+b){
						id[a].have=true;
						id[a].left=i;
						id[a].right=j-1;
						for(j=i; j<i+b; j++)
							use[j]=a;
						printf("yes\n");
						break;
					}
					else
						i=j-1;
				}
			}
			if(i==len)
				printf("no\n");
		}
		else{
			if(!id[a].have){
				printf("no\n");
				continue;
			}
			for(int i=id[a].left; i<=id[a].right; i++)
				use[i]=-1;
			id[a].have=false;
			id[a].left=-1;
			id[a].right=-1;
			printf("yes\n");
		}
	}
	return 0;
}

---

10.Maya历法

题目

【问题描述】

在学术休假期间，M.A. Ya教授在古老的Maya历法上有一个惊人的发现。从一个古老的令人棘手的信息中，教授发现Maya文明以365天为一年，称为Haab，包含19个月。前18个月每月有20天，月份名字为：pop、no、zip、zotz、tzec、xul、yoxkin、mol、chen、yax、zac、ceh、mac、kankin、muan、pax、koyab、cumhu。每月的天数使用数字来表示，从0~19，而不是用名字。Haab的最后一个月叫做uayet，有5天，表示为0、1、2、3、4。玛雅人认为这个月是不吉利的，法院不开庭，贸易停止了，人们甚至停止清扫地板。

   出于宗教的目的，Maya人使用另外一套历法，叫做Tzolkin（冬青年）。一年被分为13个期间，每个期间20天。每天被表示为由数字和日期名表示的数对。使用20个名字：imix、ik、akbal、kan、chicchan、cimi、manik、lamat、muluk、ok、chuen、eb、ben、ix、mem、cib、caban、eznab、canac、ahau，以及13个数字，双循环使用。   请注意，每一天都有一个明确的描述。例如，在年初的日子被描述如下：   1 imix, 2 ik, 3 akbal, 4 kan, 5 chicchan, 6 cimi, 7 manik, 8 lamat, 9 muluk, 10 ok, 11 chuen, 12 eb, 13 ben, 1 ix, 2 mem, 3 cib, 4 caban, 5 eznab, 6 canac, 7 ahau, 在下一个期间开始为 8 imix, 9 ik, 10 akbal . . .   年份（包含Haab和Tzolkin)用数字0、1、...来表示，数字0是世界的开始。因此，第一天表示为：   Haab: 0. pop 0  Tzolkin: 1 imix 0  请帮M.A.Ya教授写一个程序，将Haab日历转换为Tzolkin日历。  

【输入形式】

   在Haab中日期用以下形式表示：           NumberOfTheDay. Month Year   输入文件的第一行包含文件中输入日期的数目。接下来的n行包含Haab日历格式的n个日期，年份小于5000。

【输出形式】

    Tzolkin日期用一下格式：           Number NameOfTheDay Year    输出包括n行，按照与输入日期对应的顺序，输出tzolkin日历格式日期。 

【样例输入】

3
10.zac 0
0.pop 0
10.zac 1995

【样例输出】

3 chuen 0
1 imix 0
9 cimi 2801

题解

化成一个单位再化回去就好了（这题看起来又臭又长我就直接搜题解了

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

string month[19]={"pop","no","zip","zotz","tzec","xul","yoxkin",
"mol","chen","yax","zac","ceh","mac","kankin","muan","pax","koyab","cumhu","uayet"};

string day[20]={"imix","ik","akbal","kan","chicchan","cimi",
"manik","lamat","muluk","ok","chuen","eb","ben","ix","mem","cib","caban","eznab","canac","ahau"};

int find_month(string mon){
	for(int i=0;i<19;i++){
		if(month[i]==mon){
			return i;
		}
	}
}

int main(){
	int n;
	cin>>n;
	while(n--){
		int Haab_day,Haab_year;
		char point;
		string Haab_month;
		cin>>Haab_day>>point>>Haab_month>>Haab_year;
		
		int totol_day=Haab_year*365+find_month(Haab_month)*20+Haab_day;
		int Tzolkin_num,Tzolkin_year;
		
		string Tzolkin_day;
		Tzolkin_year=totol_day/260;
		totol_day%=260;
		Tzolkin_num=totol_day%13+1;
		Tzolkin_day=day[totol_day%20];
		cout<<Tzolkin_num<<" "<<Tzolkin_day<<" "<<Tzolkin_year<<endl;
	}
	return 0;
} 

---

11.数码管

题目

【问题描述】

液晶数码管用七笔阿拉数字表示的十个数字，把横和竖的一 个短划都称为一笔，即７有３笔，８有７笔等。对于十个数字一种排列，要做到两相邻数字都可以由另一个数字加上几笔或减去几笔组成，但不能又加又减。比如 ７→３是允许的，７→２不允许。任意输入一组数，判断是否符合上述规则，注意，1在右边。

【输入形式】

每行输入一个0~9的排列，数字之间用空格分隔，以-1作为输入结束

【输出形式】

输出YES或NO

【样例输入】

4 1 0 7 3 9 5 6 8 2
3 5 1 6 2 7 9 0 4 8
-1

【样例输出】

YES
NO

题解

这题其实把每种数用个表存一下各个短线处就好啦，然后判断只需要看是不是有增有减就行（看代码理解去（

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int num[10][7]={
	{1,1,1,1,1,1,0},
	{0,1,1,0,0,0,0},
	{1,1,0,1,1,0,1},
	{1,1,1,1,0,0,1},
	{0,1,1,0,0,1,1},
	{1,0,1,1,0,1,1},
	{1,0,1,1,1,1,1},
	{1,1,1,0,0,0,0},
	{1,1,1,1,1,1,1},
	{1,1,1,1,0,1,1}
};

int a[10];
int main(){
	while(scanf("%d", &a[0]) && a[0]!=-1){
		int i;
		for(i=1;i<10;i++)
			scanf("%d", &a[i]);
		for(i=1;i<10;i++){
			int temp1=0,temp2=0;
			for(int j=0;j<7;j++){
				if(num[a[i]][j] - num[a[i-1]][j]>0)temp1++;
				else if(num[a[i]][j] - num[a[i-1]][j]<0)temp2++;
			}
			//cout<<a[i]<<"-"<<a[i-1]<<": "<<temp1<<" "<<temp2<<endl;
			if(temp1>0 && temp2>0){
				printf("NO\n");
				break;
			}
		}
		if(i==10)
			printf("YES\n");
	}
	return 0;
}

---

12.多项式加法

题目

【问题描述】

一个多项式可以表示为一组数对，数对中第一个数始终为整数，且唯一，表示多项式的次数，另一数表示为对应的系数且不为0。输入两组数对，每组以0 0作为结束，实现对两个多项式的加法并按降幂输出结果数对

【输入形式】

每行输入一个数对，以空格为分隔符，以0 0结束

【输出形式】

每行输出一个数对，以空格为分隔符

【样例输入】

5 12
3 8
1 2
15 5
0 10
0 0
3 12
30 1
15 5
0 0

【样例输出】

30 1
15 10
5 12
3 20
1 2
0 10

题解

熟练应用map以及其自带排序的特点，还有迭代器的逆序输出也得注意end指针是没有值的（没写过rbegin所以我就用while了

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;

map<int, int> qwq;

int main(){
	int a,b;
	for(int i=0;i<2;i++)
		while(scanf("%d %d", &a,&b)){
			if(a==0 && b==0)
				break;
			qwq[a]+=b;
		}
	
	map<int, int>::iterator it=qwq.end();
	while(1){
		--it;
		if(it->second != 0)
			printf("%d %d\n", it->first,it->second);
		if(it==qwq.begin())
			break;
	}
	return 0;
}

---

13.数字统计

题目

【问题描述】

给定一个k位整数N = dk-110k-1 + … + d1101 + d0 (0<=di<=9, i=0,…,k-1, dk-1>0)，请编写程序统计每种不同的个位数字出现的次数。例如：给定N = 100311，则有2个0，3个1，和1个3。

【输入形式】

每个输入包含1个测试用例，即一个不超过1000位的正整数N。

【输出形式】

对N中每一种不同的个位数字，以D:M的格式在一行中输出该位数字D及其在N中出现的次数M。要求按D的升序输出

【样例输入】

100311

【样例输出】

0:2
1:3
3:1

题解

跟上一题就差不多嘛，不过因为只有0-9，所以在速度上来看直接数组比map快（map的自带排序在这里就害了速度，这里用数组就不需要排序。所以不要滥用数据结构）

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int num[10];
int main(){
	string s;
	cin>>s;
	int l = s.length();
	for(int i=0;i<l;i++)
		num[int(s[i]-'0')]++;
	for(int i=0;i<10;i++)
		if(num[i]>0)
			printf("%d:%d\n", i,num[i]);
	return 0;
}

---

14.A除以B

题目

【问题描述】
【问题描述】

本题要求计算A/B，其中A是不超过1000位的整数（A>=0），B是1位正整数。你需要输出商数Q和余数R，使得A = B * Q + R成立。

【输入形式】

输入在1行中依次给出A和B，中间以1空格分隔。

【输出形式】

在1行中依次输出Q和R，中间以1空格分隔。

【样例输入】

123456789050987654321 7

【样例输出】

17636684150141093474 3

题解

高精度除低精度的题，这里直接用高精度除高精度的板子会超时。

然后取余我这里就取巧了（因为除数只有一位，所以余数也只会有一位（但其实没必要，计算过程就会算余数（

代码

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int main()
{
	char a1[1001],c1[1001];
	int a[1001],c[1001],lena,i,x=0,lenc,b;
	memset(a,0,sizeof(a));
	memset(c,0,sizeof(c));
	cin>>a1>>b;
	lena=strlen(a1);
	for(i=0;i<=lena-1;i++)
		a[i+1]=a1[i]-48;
	for(i=0;i<=lena;i++)
	{
		c[i]=(x*10+a[i])/b;
		x=(x*10+a[i])%b;
	}
	lenc=1;
	while(c[lenc]==0&&lenc<lena)
		lenc++;
	for(i=lenc;i<=lena;i++)
		cout<<c[i];
	
	int temp=a[lena]-c[lena]*b;
	while(temp<0)
		temp+=10;
	cout<<" "<<temp;
	return 0;
}

---

15.公交系统

题目

【问题描述】

    城市公交系统有一个记录仪，用于记录每个站点的乘客人数的变化情况，例如：x表示到站前公交车上的乘客人数，y表示离站时公交车上的乘客人数，则该记录仪记录的该站的数字为y-x。    对于一辆公交车和n个车站，a1,a2,...,an为该公交车在各站的记录数据。    假定w为该公交车可容纳的最大乘客人数，编程求出在第一站停靠之前公交车上人数的可能数据有多少种？

【输入形式】

    第一行包含两个数据n和w(1<=n<=1000, 1<=w<=109)，分别表示车站的数目和公交车可容纳的最大乘客人数。    第二行包含一个序列a1,a2,...,an，表示记录仪记录的各站的数据。

【输出形式】

    输出一个整数，表示公交车在第一站停靠之前可能的乘客人数数据的个数，如果没有，则输出0。

【样例输入1】

3 5
2 1 -3

【样例输出1】

3

【样例输入2】

2 4
-1 1

【样例输出2】

4

【样例输入3】

4 10
2 4 1 2

【样例输出3】

2

【样例说明】

在第一个样例中，乘客数可能有0、1、2，共3种情况
在第二个样例中，乘客数可能有1、2、3、4，共4种情况
在第三个样例种，乘客数可能为0或1，共2种情况

题解

这题也算前缀和吧，不过需要注意好变量的意义。

用max记录前缀和最大值，w-max(max>=0)即决定了初始的最大乘客数

用min记录前缀和最小值, 这里就需要考虑一下，如果min<=0说明初始乘客量至少是-min，而min>0是没有意义的

明确这两点就很容易求解了，max(max>=0)-min(min<=0)即为区间范围，如果区间长度l大于w显然无解，否则答案就是w-l+1（这个就很容易推了吧）

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int main(){
	int n,w;
	scanf("%d %d", &n,&w);
	int ma=0,mi=0,now=0;
	while(n--){
		int q;
		scanf("%d", &q);
		now+=q;
		ma = max(ma, now);
		mi = min(mi, now);
	}
	int t = ma-mi;
	if(t>w)	printf("0");
	else printf("%d", w-t+1);
	return 0;
}

---

16.成绩大排队

题目

【问题描述】

读入n名学生的姓名、学号、成绩，分别输出成绩最高和成绩最低学生的姓名和学号。

【输入形式】

每个测试输入包含1个测试用例，格式为

第1行：正整数n
 第2行：第1个学生的姓名 学号 成绩
 第3行：第2个学生的姓名 学号 成绩
 ... ... ...
 第n+1行：第n个学生的姓名 学号 成绩

其中姓名和学号均为不超过20个字符的字符串，成绩为0到100之间的一个整数，这里保证在一组测试用例中没有两个学生的成绩是相同的。

【输出形式】

对每个测试用例输出2行，第1行是成绩最高学生的姓名和学号，第2行是成绩最低学生的姓名和学号，字符串间有1空格。

【样例输入】

3
Joe Math990112 89
Mike CS991301 100
Mary EE990830 95

【样例输出】

Mike CS991301
Joe Math990112

题解

明显结构体sort，水的不能再水了（

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

struct node{
	string name,id;
	int score;
}p[10086];

bool cmp(node a, node b){
	return a.score<b.score;
}

int main(){
	int n;
	scanf("%d", &n);
	for(int i=0;i<n;i++)
		cin>>p[i].name>>p[i].id>>p[i].score;
	sort(p, p+n, cmp);
	cout<<p[n-1].name<<" "<<p[n-1].id<<endl;
	cout<<p[0].name<<" "<<p[0].id;
	return 0;
}

---

17.字符串数字置换

题目

【问题描述】

从键盘接收用户输入的字符串, 对用户输入的每个字符串的处理是：将字符串内的每一个十进制数字字符置换成下列表格中右边所对应的一个字符串（所有其他字符不变），然后将转换的结果显示在屏幕上；并分别计算每个数字的置换次数。

十进制数字字符置换成

0 (Zero)
1 (One)
2 (Two)
3 (Three)
4 (Four)
5 (Five)
6 (Six)
7 (Seven)
8 (Eight)
9 (Nine)

例如，若用户输入的字符串为

     Page112-Line3，

则程序5的输出是：

     Page(One) (One) (Two)-Line(Three),

数字0到9的置换次数分别是 0 2 1 1 0 0 0 0 0 0

【输入形式】

输入一行字符串，其中可包含字母、数字、空格或其他符号（英文）

【输出形式】

第一行为将字符串中的数字转换为表格中的内容后输出

第二行为数字0~9被转换的次数

【样例输入】

Page112-Line3

【样例输出】

Page(One)(One)(Two)-Line(Three)
0 2 1 1 0 0 0 0 0 0

题解

逐字处理，略

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

string change[10] = {"(Zero)", "(One)", "(Two)", "(Three)", "(Four)", "(Five)", "(Six)", "(Seven)", "(Eight)", "(Nine)"};
int c[10];

int main(){
	string s;
	getline(cin, s);
	int l = s.length();
	for(int i=0;i<l;i++)
		if(s[i]>='0' && s[i]<='9'){
			cout<<change[int(s[i]-'0')];
			c[int(s[i]-'0')]++;
		}
		else cout<<s[i];
	cout<<endl;
	for(int i=0;i<10;i++)
		printf("%d ", c[i]);
	return 0;
}

---

18.写出来吧

题目

【问题描述】

读入一个自然数n，计算其各位数字之和，用汉语拼音写出和的每一位数字。

【输入形式】

每个测试输入包含1个测试用例，即给出自然数n的值。这里保证n小于10的100次方。

【输出形式】

在一行内输出n的各位数字之和的每一位，拼音数字间有1 空格，但一行中最后一个拼音数字后没有空格。

【样例输入】

1234567890987654321123456789

【样例输出】

yi san wu

【样例说明】
友情提示汉语拼音

0~9：ling yi er san si wu liu qi ba jiu

题解

水（就拆字麻烦，正常都是低位到高位拆出，所以输出就反了（不如咱们开个栈处理（逃

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

string change[10] = {"ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"};

int main(){
	string s;
	cin>>s;
	stack<string> st;
	int l = s.length(), sum=0;
	for(int i=0;i<l;i++)
		sum+=s[i]-'0';
	while(sum>0){
		st.push(change[sum%10]);
		sum/=10;
	}
	if(st.empty())
		cout<<change[0];
	else{
		cout<<st.top();
		st.pop();
		while(!st.empty()){
			cout<<" "<<st.top();
			st.pop(); 
		}
	}
	return 0;
}

---

19.到底买不买

题目

小红想买些珠子做一串自己喜欢的珠串。卖珠子的摊主有很多串五颜六色的珠串，但是不肯把任何一串拆散了卖。于是小红要你帮忙判断一下，某串珠子里是否包含了全部自己想要的珠子？如果是，那么告诉她有多少多余的珠子；如果不是，那么告诉她缺了多少珠子。

为方便起见，我们用[0-9]、[a-z]、[A-Z]范围内的字符来表示颜色。例如在图1中，第3串是小红想做的珠串；那么第1串可以买，因为包含了全部她想要的珠子，还多了8颗不需要的珠子；第2串不能买，因为没有黑色珠子，并且少了一颗红色的珠子。

【输入形式】

每个输入包含1个测试用例。每个测试用例分别在2行中先后给出摊主的珠串和小红想做的珠串，两串都不超过1000个珠子。

【输出形式】

如果可以买，则在一行中输出“Yes”以及有多少多余的珠子；如果不可以买，则在一行中输出“No”以及缺了多少珠子。其间以1个空格分隔。

【样例输入】

ppRYYGrrYBR2258
YrR8RrY

【样例输出】

Yes 8

题解

一样的map统计，然后判断有没有缺漏，有缺漏就计数。无缺漏显然l1-l2就是多了多少

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
int main(){
	map<char, int> m;
	string s1,s2;
	cin>>s1>>s2;
	int l1 = s1.length();
	int l2 = s2.length();
	for(int i=0;i<l2;i++)
		m[s2[i]]++;
	
	for(int i=0;i<l1;i++)
		if(m.find(s1[i]) !=  m.end())
			m[s1[i]]--;
	
	int count=0;
	for(map<char, int>::iterator it=m.begin(); it!=m.end(); ++it)
		if(it->second > 0)
			count += it->second;
	if(count>0)printf("No %d", count);
	else printf("Yes %d", l1-l2);
	return 0;
}

---

20.挖掘机技术哪家强

题目

【问题描述】

为了用事实说明挖掘机技术到底哪家强，组织一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。

【输入形式】

输入在第1行给出不超过105的正整数N，即参赛人数。随后N行，每行给出一位参赛者的信息和成绩，包括其所代表的学校的编号、及其比赛成绩（百分制），中间以空格分隔。

【输出形式】

在一行中给出总得分最高的学校的编号、及其总分，中间以空格分隔。题目保证答案唯一，没有并列。

【样例输入】

6
3 65
2 80
1 100
2 70
3 40
3 0

【样例输出】

2 150

【问题说明】

建议练习使用STL中的map

题解

又是一道统计的水题。。。最后迭代器遍历找一下最大和下标就行

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
map<int, int> m;

int main(){
	int n;
	scanf("%d", &n);
	while(n--){
		int a,b;
		scanf("%d %d", &a,&b);
		m[a]+=b;
	}
	int ma=0, index;
	for(map<int, int>::iterator it=m.begin(); it!=m.end(); ++it)
		if(it->second > ma){
			ma = it->second;
			index = it->first;
		}
	printf("%d %d", index,ma);
	return 0;
}

---

21.Web导航

题目

【问题描述】

标准的Web浏览器具有在最近访问的页面中前后移动的特性。实现这些特性的一种方法是使用两个堆栈来跟踪可以通过前后移动到达的页面。在这个问题中，我们要求实现这一点。

   需要支持以下命令：   BACK：将当前页面压入前向堆栈的顶部；从后向堆栈的顶部弹出该页，使其成为新的当前页。如果后向堆栈为空，则该指令忽略。   FORWARD：将当前页面压入后向堆栈的顶部；从前向堆栈的顶部弹出该页，使其成为新的当前页。如果前向堆栈为空，则该指令忽略。   VISIT：将当前页面压入后向堆栈的顶部，将URL指定为新的当前页。前向堆栈被清空。   QUIT：退出浏览器。   假设浏览器最初在网址`http://www.game.org/`上加载网页。

【输入形式】输入是一个命令序列。命令关键字BACK、FORWARD、VISIT和QUIT都是大写。URL中无空格，最多有70个字符。假定在任何时候，每个堆栈中没有问题实例需要超过100个元素。输入的结尾由QUIT命令标识。

【输出形式】除QUIT外的每个命令，如果命令没有被忽略，则在命令执行后输出当前页面的URL，否则，打印”Ignored”。每个命令的输出独立打印一行。QUIT命令无输出。

【样例输入】

VISIT http://game.ashland.edu/
VISIT http://game.baylor.edu/acmicpc/
BACK
BACK
BACK
FORWARD
VISIT http://www.our.com/
BACK
BACK
FORWARD
FORWARD
FORWARD
QUIT

【样例输出】

http://game.ashland.edu/
http://game.baylor.edu/acmicpc/
http://game.ashland.edu/
http://www.game.org/
Ignored
http://game.ashland.edu/
http://www.our.com/
http://game.ashland.edu/
http://www.game.org/
http://game.ashland.edu/
http://www.our.com/
Ignored

题解

题目都把怎么处理告诉你了，总不能这还不会吧

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;
int main(){
	stack<string> fr,ba;
	string code,now="http://www.game.org/";
	while(cin>>code){
		if(code == "QUIT")return 0;
		if(code == "BACK" && !ba.empty()){
			fr.push(now);
			now = ba.top();
			ba.pop();
			cout<<now<<endl;
		}
		else if(code == "FORWARD" && !fr.empty()){
			ba.push(now);
			now = fr.top();
			fr.pop();
			cout<<now<<endl;
		}
		else if(code == "VISIT"){
			ba.push(now);
			cin>>now;
			while(!fr.empty())
				fr.pop();
			cout<<now<<endl;
		}
		else cout<<"Ignored"<<endl;
	}
}

---

结

第三周复盘结束（这周居然这么快就写完了）。有什么问题可以评论留言