ZUST-CCCC选拔赛（L1，L2部分题解）

概览

标号 标题 分数 通过数 提交数 通过率
7-1 传统送分题 5 47 65 0.72
7-2 一个很难的数论题 5 46 77 0.60
7-3 欢乐星期三 10 37 81 0.46
7-4 签个到不就完了嘛，还想签几道？ 10 18 103 0.17（模拟（））
7-5 人被逼急了什么都做的出来，甚至数学题 15 10 93 0.11（模拟）
7-6 题面是真的想不出来 15 10 144 0.07（排列组合）
7-7 【模板】KMP字符串匹配 20 7 70 0.10（KMP模板）

7-8 Rinne喜欢学习-二 25 24 131 0.18（模拟）
7-9 哥德巴赫猜想 25 21 133 0.16（素数筛法）
7-10 happiness 25 0 32 0.00（贪心到DP）
7-11 消费券 30 0 84 0.00（图论最短路-二分答案）

7-12 PRO 30 0 10 0.00（二叉树路径？）
7-13 ydhjuruo的闯关游戏 30 0 14 0.00

Part1. L1，7题

L1-1

7-1 传统送分题 (5 分)
每次比赛都有简单的送分题。请按照样例输出" This is a easy problem! "即可

输入格式:
无

输出格式:
无

输入样例:
在这里给出一组输入。例如：

无
输出样例:
This
is
a
easy
problem!
作者
朱展乐
单位
浙江科技学院
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB

#include<bits/stdc++.h>
using namespace std;
int main(){
	cout<<"This \nis \na \neasy \nproblem!";
	return 0;
}

L1-2

7-2 一个很难的数论题 (5 分)
戴学长是个数学高手，他发明了一种数，取名为“戴氏数”。以下是得到该数的方法：将一个数的每个位上的数的顺序颠倒，再加上颠倒前的数就得到了”戴氏数”。例如，为了得到1234的”戴氏数”，先将1234的数字顺序颠倒，得4321，再加上原来的数，得5555。要是颠倒后的数有前缀0就忽略掉这些0。例如1230, 颠倒忽略前缀0后为321。

输入描述：

一个范围为[1,100000]的正整数N
输出描述：

输出N的“戴氏数”
样例输入：

1234
样例输出：

5555
作者
林志洁
单位
浙江科技学院
代码长度限制
16 KB
时间限制
1000 ms
内存限制
64 MB

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n; cin>>n;
	string s = to_string(n);
	reverse(s.begin(),s.end());
	int d = 0;
	while(s[d]=='0')d++;
	s = s.substr(d);
	cout<<n+stoi(s)<<"\n";
	return 0;
}

L1-3

7-3 欢乐星期三 (10 分)
众所周之，手游阴阳师最大的快乐在于抽卡。又到了一月一度的抽卡时间了，小潘同学攒了好久的蓝票准备开始抽卡。由于他是个新手玩家，不认识式神，所以需要你帮助他。每当小潘同学抽出卡后，输出式神的稀有度。 SSR式神有:jiutuntongzi cimutongzi datiangou huiyeji buzhihuo yunwaijing yuzaoqian yaodaoji dayuewan

输入格式:
输入的第一行给出正整数N(<=100)。随后N行，每行一个字符串代表式神的名字。

输出格式:
如果是SSR式神请输出"SSR!",否则则输出yingyingying!。

输入样例:
1
jiutuntongzi
输出样例:
在这里给出相应的输出。例如：

SSR!
作者
朱展乐
单位
浙江科技学院
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB

#include<bits/stdc++.h>
using namespace std;
int main(){
	string s[10] = {"jiutuntongzi", "cimutongzi", "datiangou", "huiyeji", "buzhihuo","yunwaijing","yuzaoqian","yaodaoji","dayuewan"};
	int T;  cin>>T;
	while(T--){
		string a;  cin>>a;
		int ok = 0;
		for(int i = 0; i < 9; i++){
			if(s[i]==a){
				ok = 1;break;
			}
		}
		if(ok==1){
			cout<<"SSR!\n";
		}else{
			cout<<"yingyingying!\n";
		}
	}
	return 0;
}

L1-4

7-4 签个到不就完了嘛，还想签几道？ (10 分)
由于想签多几道，于是就有了这道题。

目前因为不可抗力，导致某菜🐕需要手动修改数据库

现在给出你表的三个字段：学号，姓名，绩点

目前需要你帮助菜🐕实现CURD

创建（Create）、更新（Update）、读取（Retrieve）和删除（Delete）操作

输入格式:
第一行给出一个整数 n ，代表接下来有 n 行命令

接下来 n 行，按以下格式给出任意一种

C ID Name GPA

U ID Name GPA

R ID

D ID
若操作不合法则无视，例如重复创建，无效读取，删除等

1≤n≤1e5 ，1≤ID≤1e9，5≤∣Name∣≤20，1≤GPA≤5

输出格式:
对每一个合法 R 读取输出该学生的信息

输入样例:
在这里给出一组输入。例如：

10
C 1 cai 1
C 2 bing 2
C 3 xu 3
U 1 cai 4
U 2 bing 5
U 3 xu 5
D 1
R 1
R 2
R 3
输出样例:
在这里给出相应的输出。例如：

2 bing 5
3 xu 5
作者
蔡炳旭
单位
浙江科技学院
代码长度限制
16 KB
时间限制
1000 ms
内存限制
64 MB

#include<bits/stdc++.h>
using namespace std;
struct node{
	int id; string name; int sc;
	//node(int x, string y, int z):id(x),name(y),sc(z){}
};
int main(){
	
	int n;
	while(cin>>n&&n){
		map<int,node>ma;
		for(int i = 1; i <= n; i++){
			string op;  cin>>op;
			int id;  cin>>id;
			if(op.find("C")!=string::npos){
				string name; int sc;
				cin>>name>>sc;
				//if(name.size()<5||name.size()>20)continue;
				if(sc<1||sc>5)continue;
				//if(ma.size()>20)continue;
				
				if(!ma.count(id)){
					node t; t.id = id; t.name=name; t.sc=sc;
					ma[id] = t;
				}
			}else if(op.find("U")!=string::npos){
				string name; int sc;
				cin>>name>>sc;
				//cout<<id<<":"<<ma.count(id)<<"\n";
				if(ma.count(id)){
					ma[id].name = name;
					ma[id].sc = sc;
					//ma[id].sc = max(ma[id].sc,sc);
				}
			}else if(op.find("R")!=string::npos){
				if(ma.count(id)){
					cout<<id<<" "<<ma[id].name<<" "<<ma[id].sc<<"\n";
				}
			}else if(op.find("D")!=string::npos){
				//cout<<id<<" "<<ma.count(id)<<"\n";
				if(ma.count(id)){
					//cout<<"asdf";
					//cout<<ma.size()<<"\n";
					ma.erase(id);
					//cout<<ma.size()<<"\n";
				}
			}
		}
	}
	
	return 0;
}

L1-5

7-5 人被逼急了什么都做的出来，甚至数学题 (15 分)
众所周知，在模意义下，除以一个数等于乘以这个数的逆元，现在给你模为1e9+7的情况下， a 和 它的逆元 inv
​a
​​ 和 n，请问a
​n
​​ 的逆元是多少？

输入格式:
每个测试点第一行包含1个整数 T

接下来 T 行询问，每行包含 3 个整数 a,inv
​a
​​ ,n

1≤T,n≤1000,1≤inv
​a
​​ ≤1e9+7

输出格式:
对每一组询问，在一行中输出 a
​n
​​ 的逆元

输入样例:
在这里给出一组输入。例如：

3
2 500000004 1
2 500000004 2
2 500000004 3
输出样例:
在这里给出相应的输出。例如：

500000004
250000002
125000001
作者
蔡炳旭
单位
浙江科技学院
代码长度限制
16 KB
时间限制
1000 ms
内存限制
64 MB

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const LL mod = 1e9+7;
int main(){
	int T;  cin>>T;
	while(T--){
		LL a, inv, n;
		cin>>a>>inv>>n;
		LL ans = 1;
		for(LL i = 1; i <= n; i++){
			ans = ans*inv%mod;
		}
		cout<<ans<<"\n";
	}
	return 0;
}

L1-6

7-6 题面是真的想不出来 (15 分)
歌德曾经说过，我想不出好的题面。我希望诸位也能好好地体会这句话。 生活中，若想不出好的题面出现了，我们就不得不考虑它出现了的事实。 我们都知道，只要有意义，那么就必须慎重考虑。 生活中，若想不出好的题面出现了，我们就不得不考虑它出现了的事实。 想不出好的题面因何而发生？ 生活中，若想不出好的题面出现了，我们就不得不考虑它出现了的事实。 富勒曾经提到过，苦难磨炼一些人，也毁灭另一些人。这似乎解答了我的疑惑。 我认为， 现在，解决想不出好的题面的问题，是非常非常重要的。 所以， 了解清楚想不出好的题面到底是一种怎么样的存在，是解决一切问题的关键。 想不出好的题面，发生了会如何，不发生又会如何。 想不出好的题面因何而发生？ 我们一般认为，抓住了问题的关键，其他一切则会迎刃而解。 可是，即使是这样，想不出好的题面的出现仍然代表了一定的意义。 查尔斯·史考伯曾经说过，一个人几乎可以在任何他怀有无限热忱的事情上成功。 我希望诸位也能好好地体会这句话。 我们不得不面对一个非常尴尬的事实，那就是， 塞内加在不经意间这样说过，勇气通往天堂，怯懦通往地狱。这句话语虽然很短，但令我浮想联翩。 伏尔泰说过一句富有哲理的话，坚持意志伟大的事业需要始终不渝的精神。这启发了我， 笛卡儿说过一句富有哲理的话，我的努力求学没有得到别的好处，只不过是愈来愈发觉自己的无知。这启发了我， 我认为， 想不出好的题面的发生，到底需要如何做到，不想不出好的题面的发生，又会如何产生。 从这个角度来看， 一般来说， 这样看来， 王阳明曾经说过，故立志者，为学之心也；为学者，立志之事也。带着这句话，我们还要更加慎重的审视这个问题： 一般来说， 我们一般认为，抓住了问题的关键，其他一切则会迎刃而解。 黑格尔在不经意间这样说过，只有永远躺在泥坑里的人，才不会再掉进坑里。我希望诸位也能好好地体会这句话。 那么， 莫扎特说过一句富有哲理的话，谁和我一样用功，谁就会和我一样成功。这启发了我， 达尔文曾经说过，敢于浪费哪怕一个钟头时间的人，说明他还不懂得珍惜生命的全部价值。我希望诸位也能好好地体会这句话。 马克思说过一句富有哲理的话，一切节省，归根到底都归结为时间的节省。这似乎解答了我的疑惑。 罗曼·罗兰说过一句富有哲理的话，只有把抱怨环境的心情，化为上进的力量，才是成功的保证。这句话语虽然很短，但令我浮想联翩。 可是，即使是这样，想不出好的题面的出现仍然代表了一定的意义。 那么， 而这些并不是完全重要，更加重要的问题是， 想不出好的题面，到底应该如何实现。 想不出好的题面因何而发生？ 伏尔泰在不经意间这样说过，不经巨大的困难，不会有伟大的事业。这似乎解答了我的疑惑。 从这个角度来看， 想不出好的题面的发生，到底需要如何做到，不想不出好的题面的发生，又会如何产生。 本人也是经过了深思熟虑，在每个日日夜夜思考这个问题。 而这些并不是完全重要，更加重要的问题是， 了解清楚想不出好的题面到底是一种怎么样的存在，是解决一切问题的关键。 这样看来， 易卜生在不经意间这样说过，伟大的事业，需要决心，能力，组织和责任感。这不禁令我深思。 本人也是经过了深思熟虑，在每个日日夜夜思考这个问题。 想不出好的题面的发生，到底需要如何做到，不想不出好的题面的发生，又会如何产生。 每个人都不得不面对这些问题。 在面对这种问题时， 想不出好的题面的发生，到底需要如何做到，不想不出好的题面的发生，又会如何产生。 想不出好的题面，发生了会如何，不发生又会如何。 我们都知道，只要有意义，那么就必须慎重考虑。 想不出好的题面，发生了会如何，不发生又会如何。 经过上述讨论， 带着这些问题，我们来审视一下想不出好的题面。 一般来说， 问题的关键究竟为何？ 想不出好的题面因何而发生？ 问题的关键究竟为何？ 想不出好的题面的发生，到底需要如何做到，不想不出好的题面的发生，又会如何产生。 那么， 歌德曾经提到过，意志坚强的人能把世界放在手中像泥块一样任意揉捏。这句话语虽然很短，但令我浮想联翩。 我们不得不面对一个非常尴尬的事实，那就是， 本人也是经过了深思熟虑，在每个日日夜夜思考这个问题。 经过上述讨论， 可是，即使是这样，想不出好的题面的出现仍然代表了一定的意义。 生活中，若想不出好的题面出现了，我们就不得不考虑它出现了的事实。 现在，解决想不出好的题面的问题，是非常非常重要的。 所以， 爱迪生曾经说过，失败也是我需要的，它和成功对我一样有价值。这不禁令我深思。 一般来讲，我们都必须务必慎重的考虑考虑。 想不出好的题面因何而发生？ 我们不得不面对一个非常尴尬的事实，那就是， 问题的关键究竟为何？ 我们都知道，只要有意义，那么就必须慎重考虑。 莎士比亚曾经说过，人的一生是短的，但如果卑劣地过这一生，就太长了。这启发了我， 那么， 既然如何， 我认为， 这种事实对本人来说意义重大，相信对这个世界也是有一定意义的。 对我个人而言，想不出好的题面不仅仅是一个重大的事件，还可能会改变我的人生。 带着这些问题，我们来审视一下想不出好的题面。 这样看来， 每个人都不得不面对这些问题。 在面对这种问题时， 生活中，若想不出好的题面出现了，我们就不得不考虑它出现了的事实。 我们都知道，只要有意义，那么就必须慎重考虑。 想不出好的题面，发生了会如何，不发生又会如何。 冯学峰说过一句富有哲理的话，当一个人用工作去迎接光明，光明很快就会来照耀着他。这似乎解答了我的疑惑。 一般来说， 我们都知道，只要有意义，那么就必须慎重考虑。 每个人都不得不面对这些问题。 在面对这种问题时， 所谓想不出好的题面，关键是想不出好的题面需要如何写。 就我个人来说，想不出好的题面对我的意义，不能不说非常重大。 经过上述讨论， 黑格尔曾经提到过，只有永远躺在泥坑里的人，才不会再掉进坑里。我希望诸位也能好好地体会这句话。 莎士比亚曾经说过，人的一生是短的，但如果卑劣地过这一生，就太长了。这启发了我， 维龙在不经意间这样说过，要成功不需要什么特别的才能，只要把你能做的小事做得好就行了。带着这句话，我们还要更加慎重的审视这个问题： 本人也是经过了深思熟虑，在每个日日夜夜思考这个问题。 带着这些问题，我们来审视一下想不出好的题面。 我们不得不面对一个非常尴尬的事实，那就是， 我们一般认为，抓住了问题的关键，其他一切则会迎刃而解。 而这些并不是完全重要，更加重要的问题是， 现在，解决想不出好的题面的问题，是非常非常重要的。 所以， 一般来说， 问题的关键究竟为何？ 而这些并不是完全重要，更加重要的问题是， 可是，即使是这样，想不出好的题面的出现仍然代表了一定的意义。 了解清楚想不出好的题面到底是一种怎么样的存在，是解决一切问题的关键。 富兰克林曾经说过，读书是易事，思索是难事，但两者缺一，便全无用处。我希望诸位也能好好地体会这句话。 要想清楚，想不出好的题面，到底是一种怎么样的存在。 可是，即使是这样，想不出好的题面的出现仍然代表了一定的意义。 总结的来说， 从这个角度来看。从这个角度来看， 本人也是经过了深思熟虑，在每个日日夜夜思考这个问题。 一般来说， 笛卡儿曾经说过，阅读一切好书如同和过去最杰出的人谈话。这不禁令我深思。 这种事实对本人来说意义重大，相信对这个世界也是有一定意义的。 既然如何， 莎士比亚在不经意间这样说过，本来无望的事，大胆尝试，往往能成功。我希望诸位也能好好地体会这句话。 了解清楚想不出好的题面到底是一种怎么样的存在，是解决一切问题的关键。 想不出好的题面，发生了会如何，不发生又会如何。 既然如何， 可是，即使是这样，想不出好的题面的出现仍然代表了一定的意义。 本人也是经过了深思熟虑，在每个日日夜夜思考这个问题。 海贝尔曾经说过，人生就是学校。在那里，与其说好的教师是幸福，不如说好的教师是不幸。这启发了我， 对我个人而言，想不出好的题面不仅仅是一个重大的事件，还可能会改变我的人生。 我们都知道，只要有意义，那么就必须慎重考虑。 既然如何， 我认为， 从这个角度来看， 就我个人来说，想不出好的题面对我的意义，不能不说非常重大。 莎士比亚曾经说过，那脑袋里的智慧，就像打火石里的火花一样，不去打它是不肯出来的。这似乎解答了我的疑惑。 既然如此， 想不出好的题面，到底应该如何实现。 一般来讲，我们都必须务必慎重的考虑考虑。 想不出好的题面的发生，到底需要如何做到，不想不出好的题面的发生，又会如何产生。 想不出好的题面的发生，到底需要如何做到，不想不出好的题面的发生，又会如何产生。 总结的来说， 想不出好的题面，发生了会如何，不发生又会如何。 对我个人而言，想不出好的题面不仅仅是一个重大的事件，还可能会改变我的人生。 我们都知道，只要有意义，那么就必须慎重考虑。 现在，解决想不出好的题面的问题，是非常非常重要的。 所以， 我们一般认为，抓住了问题的关键，其他一切则会迎刃而解。 我们不得不面对一个非常尴尬的事实，那就是， 奥斯特洛夫斯基曾经提到过，共同的事业，共同的斗争，可以使人们产生忍受一切的力量。　我希望诸位也能好好地体会这句话。非洲在不经意间这样说过，最灵繁的人也看不见自己的背脊。这句话语虽然很短，但令我浮想联翩。 卡莱尔曾经提到过，过去一切时代的精华尽在书中。带着这句话，我们还要更加慎重的审视这个问题： 一般来讲，我们都必须务必慎重的考虑考虑。 雷锋说过一句富有哲理的话，自己活着，就是为了使别人过得更美好。这似乎解答了我的疑惑。 可是，即使是这样，想不出好的题面的出现仍然代表了一定的意义。 对我个人而言，想不出好的题面不仅仅是一个重大的事件，还可能会改变我的人生。 我认为， 可是，即使是这样，想不出好的题面的出现仍然代表了一定的意义。 总结的来说， 想不出好的题面的发生，到底需要如何做到，不想不出好的题面的发生，又会如何产生。 这样看来， 我认为， 这种事实对本人来说意义重大，相信对这个世界也是有一定意义的。 亚伯拉罕·林肯曾经提到过，你活了多少岁不算什么，重要的是你是如何度过这些岁月的。这句话语虽然很短，但令我浮想联翩。 现在，解决想不出好的题面的问题，是非常非常重要的。 所以， 我们都知道，只要有意义，那么就必须慎重考虑。 而这些并不是完全重要，更加重要的问题是， 培根曾经说过，要知道对好事的称颂过于夸大，也会招来人们的反感轻蔑和嫉妒。这似乎解答了我的疑惑。 想不出好的题面，到底应该如何实现。 一般来说， 想不出好的题面，发生了会如何，不发生又会如何。 想不出好的题面的发生，到底需要如何做到，不想不出好的题面的发生，又会如何产生。 想不出好的题面，发生了会如何，不发生又会如何。 想不出好的题面的发生，到底需要如何做到，不想不出好的题面的发生，又会如何产生。 就我个人来说，想不出好的题面对我的意义，不能不说非常重大。 现在，解决想不出好的题面的问题，是非常非常重要的。 所以， 可是，即使是这样，想不出好的题面的出现仍然代表了一定的意义。 而这些并不是完全重要，更加重要的问题是， 想不出好的题面的发生，到底需要如何做到，不想不出好的题面的发生，又会如何产生。 想不出好的题面，到底应该如何实现。 总结的来说， 在这种困难的抉择下，本人思来想去，寝食难安。 想不出好的题面，发生了会如何，不发生又会如何。 俾斯麦曾经说过，对于不屈不挠的人来说，没有失败这回事。带着这句话，我们还要更加慎重的审视这个问题： 奥斯特洛夫斯基在不经意间这样说过，共同的事业，共同的斗争，可以使人们产生忍受一切的力量。　这启发了我， 了解清楚想不出好的题面到底是一种怎么样的存在，是解决一切问题的关键。 而这些并不是完全重要，更加重要的问题是， 想不出好的题面，到底应该如何实现。 韩非在不经意间这样说过，内外相应，言行相称。这启发了我， 歌德说过一句富有哲理的话，决定一个人的一生，以及整个命运的，只是一瞬之间。带着这句话，我们还要更加慎重的审视这个问题： 要想清楚，想不出好的题面，到底是一种怎么样的存在。 就我个人来说，想不出好的题面对我的意义，不能不说非常重大。 想不出好的题面因何而发生？ 这样看来， 既然如此， 想不出好的题面因何而发生？ 所谓想不出好的题面，关键是想不出好的题面需要如何写。 生活中，若想不出好的题面出现了，我们就不得不考虑它出现了的事实。 本人也是经过了深思熟虑，在每个日日夜夜思考这个问题。 既然如此， 康德曾经提到过，既然我已经踏上这条道路，那么，任何东西都不应妨碍我沿着这条路走下去。我希望诸位也能好好地体会这句话。 了解清楚想不出好的题面到底是一种怎么样的存在，是解决一切问题的关键。 贝多芬曾经提到过，卓越的人一大优点是：在不利与艰难的遭遇里百折不饶。这启发了我， 那么， 歌德曾经说过，意志坚强的人能把世界放在手中像泥块一样任意揉捏。我希望诸位也能好好地体会这句话。 一般来讲，我们都必须务必慎重的考虑考虑。 经过上述讨论， 本人也是经过了深思熟虑，在每个日日夜夜思考这个问题。 想不出好的题面，到底应该如何实现。 总结的来说， 想不出好的题面，发生了会如何，不发生又会如何。 我们不得不面对一个非常尴尬的事实，那就是， 可是，即使是这样，想不出好的题面的出现仍然代表了一定的意义。 吉格·金克拉曾经说过，如果你能做梦，你就能实现它。这不禁令我深思。 对我个人而言，想不出好的题面不仅仅是一个重大的事件，还可能会改变我的人生。 所谓想不出好的题面，关键是想不出好的题面需要如何写。 我们都知道，只要有意义，那么就必须慎重考虑。 从这个角度来看， 现在，解决想不出好的题面的问题，是非常非常重要的。 所以，如果有n个问题要解决，你我瞬间都能解决任意个，我先选择问题，剩下的由你解决，那么有多少种可能你解决问题的数量比我多呢？

输入格式:
输入在一行中给出一个整数 T，代表 T 行询问

接下来 T 行中，每行给出一个整数 n

1≤T≤1000，1≤n≤50

输出格式:
对每一行询问输出答案

输入样例:
3
1
3
5
输出样例:
在这里给出相应的输出。例如：

1
4
16
作者
蔡炳旭
单位
浙江科技学院
代码长度限制
16 KB
时间限制
1000 ms
内存限制
64 MB

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int maxn = 1e5+10;
//C(n,m)=n!/m!(n-m)!
int main(){
	int T;  cin>>T;
	while(T--){
		LL n, m;  cin>>n;
		if(n%2==0)m=n/2-1;
		else m = n/2;
		LL ans = 1, cnt = 1;
		for(int i = 0; i < m; i++){
			cnt = cnt*(n-i)/(i+1); //C(n,i)=n!/(n-i)!i!
			//cout<<n<<":"<<i<<":"<<cnt<<"\n";
			ans += cnt; //cnt == C(n,i+1);
		}
		cout<<ans<<"\n";
	}
	return 0;
}

L1-7

7-7 【模板】KMP字符串匹配 (20 分)
给出两个字符串text和pattern，其中pattern为text的子串，求出pattern在text中所有出现的位置。

为了减少骗分的情况，接下来还要输出子串的前缀数组next。

输入格式:
第一行为一个字符串，即为text。

第二行为一个字符串，即为pattern。

输出格式:
若干行，每行包含一个整数，表示pattern在text中出现的位置。

接下来1行，包括length(pattern)个整数，表示前缀数组next[i]的值，数据间以一个空格分隔，行尾无多余空格。

输入样例:
ABABABC
ABA
输出样例:
1
3
0 0 1
样例说明:
snap650.jpg

作者
李廷元
单位
中国民用航空飞行学院
代码长度限制
16 KB
时间限制
4000 ms
内存限制
64 MB

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int maxn = 1e6+10;
int n, Next[maxn];
void pre(string a){
    int j = 0;
    for(int i = 1; i < a.size(); i++){
        while(j>0 && a[i+1]!=a[j+1])j = Next[j];
        if(a[i+1]==a[j+1])j++;
        Next[i+1] = j;
    }
}
int main(){
	ios::sync_with_stdio(false);
	string a, b;
	cin>>a>>b;
	int d = 0, t = 0;
	vector<int>vc;
	while(a.find(b,d)!=string::npos){
		d = a.find(b,d);
		cout<<d+1<<"\n";
		d++;
	}
	b = "0"+b;
	pre(b);
	for(int i = 1; i < b.size()-1; i++)
		cout<<Next[i]<<" ";
	cout<<Next[b.size()-1];
	return 0;
}

Part2. L2，4题

L2-1

7-8 Rinne喜欢学习-二 (25 分)
题目描述
Rinne 喜欢使用一种奇怪的方法背单词，现在这些单词被放在了一个 n×m的格子里。由于背单词是一个令人烦躁的事情，所以她决定每天只背同一行或者同一列的单词。她一共会背 T 次单词，为了方便巩固，她现在想知道：对于每个单词，最后一次背是什么时候呢？ 她这么可爱当然会算啦！但是她想考考你。

输入描述:
第一行三个整数 n,m,T。
接下来 T 行，第 i+1 行描述第 i 天干了什么，每行的格式如下：
1 x:说明她在这一天背了第 x 行的单词；
2 y说明她在这一天背了第 y 列的单词。
接下来一行一个整数q，表示查询次数
接下来 q 行，每行两个整数，表示第i行和第j列
输入的所有量的具体意义请参考「题目描述」。
输出描述:
每次查询输出一个答案表示第i行和第j列的单词背了几次

示例1

输入
3 3 3
1 2
2 2
1 1
1
2 3
输出
1
备注:
n≤10^5, m≤10^5, T≤10^5

作者
林志洁
单位
浙江科技学院
代码长度限制
16 KB
时间限制
1000 ms
内存限制
64 MB

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int maxn = 1e5+10;
int hang[maxn], lie[maxn];
int main(){
	ios::sync_with_stdio(false);
	int n, m, T;  cin>>n>>m>>T;
	for(int i = 1; i <= T; i++){
		int op, x;  cin>>op>>x;
		if(op==1){
			hang[x]++;
		}else{
			lie[x]++;
		}
	}
	int q;  cin>>q;
	while(q--){
		int x, y; cin>>x>>y;
		cout<<hang[x]+lie[y]<<"\n";
	}
	return 0;
}

L2-2

7-9 哥德巴赫猜想 (25 分)
1742年，德国业余数学家克里斯蒂安·哥德巴赫（Christian Goldbach）给莱昂哈德·欧拉（Leonhard Euler）写了一封信。 信中他推测说：

大于2的每一个数都可以写成三个质数的和。

后来，欧拉将这一推测表述为：
每一个大于或等于4的偶数都可以表示为两个质数之和。

例如：

8=3+5。3和5都是奇数素数。
20=3+17=7+13。
42=5+37=11+31=13+29=19+23。
今天，这一推测是否正确还没有得到证实。

不管怎样，现在你的任务是验证所有偶数是否满足欧拉所表达的哥德巴赫猜想。

全部数字之和不会超过一百万。

输入
输入文件将包含一个或多个测试用例。

每个测试用例由一个6≤n<1000000的偶数n组成。

输入将以0的值终止。

输出
对于每个测试用例，打印一行形式n=a+b，其中a和b是奇数素数。

数字和运算符应该由一个空格分隔，就像下面的示例输出一样。 如果还有更多答案，选择b-a的值最大的那对。

如果没有答案，输出“Goldbach’s conjecture is wrong.”。

输入样例
8
20
42
0
输出样例
8 = 3 + 5
20 = 3 + 17
42 = 5 + 37
作者
林志洁
单位
浙江科技学院
代码长度限制
16 KB
时间限制
1000 ms
内存限制
64 MB

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int maxn = 1000010;
//const int maxn = 10010;
bitset<maxn>p;//prime==0
vector<int>vc;
set<int>se;
int main(){
	ios::sync_with_stdio(false);
	for(int i = 2; i <= maxn; i++){
		if(!p[i]){
			vc.push_back(i);
			se.insert(i);
			for(int j = 2*i; j <= maxn; j+=i){
				p[j] = 1;
			}
		}
	}
	//cout<<vc.back()<<"\n";
	int n;
	while(cin>>n &&n){
		int ok = 1;
		for(int i = 0; i < vc.size(); i++){
			if(se.count(n-vc[i])){
				cout<<n<<" = "<<vc[i]<<" + "<<n-vc[i]<<"\n";
				ok = 0;
				break;
			}
		}
		if(ok==1){
			cout<<"Goldbach's conjecture is wrong.\n";
		}
	}
	return 0;
}

L2-3

7-10 happiness (25 分)
Happiness
又是一年盛夏，ZUST ACM集训队的 n 位队员们要排成一排拍一张合照，他们一开始站的位置编号分别为 1,2,…,n。

队员们对自己拍照所处的位置不是很满意。（凭什么高个要站在两边？我就想偷偷摸摸的站在角落谁也看不到我！）

站在第 i 个位置的队员有一个 a
​i
​​ ，重新排列后，新的位置越远大家越能产生新鲜感，所以队员们的开心值为 a
​i
​​ ∗∣newpos−oldpos∣， oldpos表示他们原先的位置 i， newpos 表示重新排列后的所在位置。

林老师要重新排列队员们的位置来最大化所有人的开心值的和，他很好奇这个值是多少。

输入格式:
第一行输入：n

第二行输入：a
​1
​​ ,a
​2
​​ ,…,a
​n
​​

1≤n≤5000

1≤a
​i
​​ ≤10
​9
​​

输出格式:
输出重新排列后所有人的开心值的和。

输入样例1:
6
8 6 9 1 2 1
输出样例1:
85
输入样例2:
6
5 5 6 1 1 1
输出样例2:
58
作者
孙寅
单位
浙江科技学院
代码长度限制
16 KB
时间限制
1000 ms
内存限制
256 MB

/*
题意：
+ n个人，初始站在1...n，并且有开心值ai。
+ 交换若干个人，每个人获得abs(x2-x1)*ai的开心值，求开心值最大。
思路：
+ 容易想到贪心把大的放两边，但是一个点都没过，，因为会影响后续的答案，比如一个人在中间点它既可以放到左边又可以放到右边对他是一样的，但是对后续的点就不一定是这样了，所以要把左右的情况都包含进去。
+ 所以是个dp，f[i][j]表示当前左边放了i个，右边放了j个的最大值。先排序后，枚举时考虑下一个放在左边还是放在右边的情况来转移。
*/
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int maxn = 1e4+10;
LL f[maxn][maxn];
int main(){
	int n;  cin>>n;
	vector<pair<int,int> >a;
	for(int i = 0; i < n; i++){
		int x;  cin>>x;  a.push_back(make_pair(x,i+1));
	}
	sort(a.rbegin(),a.rend());
	
	//vector<vector<LL>>f(n+1,vector<LL>(n+1));
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= i; j++){
			int k = i-j;
			f[j+1][k] = max(f[j+1][k], f[j][k]+a[i].first*(LL)abs(a[i].second-(j+1)));
			f[j][k+1] = max(f[j][k+1], f[j][k]+a[i].first*(LL)abs(n-k-a[i].second));
		}
	}
	LL ans = 0;
	for(int i = 0; i <= n; i++)
		ans = max(ans, f[i][n-i]);
	cout<<ans<<"\n";
	return 0;
}

L2-4

7-11 消费券 (30 分)
消费券
给定一个含有 n 个点 m 条边的无向带权图，你在起始点 start 号点，你想到 end 号点去。

定义 cnt
​edge
​​ ： 你从 start 到 end 所经过的边数。

你有一张消费券，上面有一个数字 cnt， 它的效果是：

cnt
​edge
​​ ≤cnt，则你的花费为 0。

cnt
​edge
​​ >cnt，则你任选 cnt 条边使得他们的花费为 0，你的花费为剩余的边中花费最大的边。

请问聪明的你能否告诉我最小花费为多少？

输入格式:
第 1 行依次输入：n m start end cnt

第 2 m+1 行依次输入: u
​i
​​ v
​i
​​ w
​i
​​ ，表示点 u
​i
​​ 到 v
​i
​​ 有一条花费为 w
​i
​​ 的边。

1≤n,start,end,u
​i
​​ ,v
​i
​​ ≤100000

0≤cnt≤10

1≤m≤200000

1≤w
​i
​​ ≤1000000000

输出格式:
若可以从 start 号点抵达 end 号点，则输出"Yes"，并在下一行输出最小花费。

若无法从 start 号点抵达 end 号点，则输出"No"。

输入样例:
5 8 2 5 0
3 4 4080296
4 5 769190610
1 2 957482570
2 5 976698513
5 1 250784393
4 2 121355339
3 5 252291285
1 3 542663147
输出样例:
Yes
252291285
作者
孙寅
单位
浙江科技学院
代码长度限制
16 KB
时间限制
3000 ms
内存限制
256 MB

/*
题意：
+ n个点m条边的图，从s出发到达t，选cnt条边不算权重，求最短路径。
思路：
+ 出题人说，首先答案是单调的，可以二分。然后问题就变成了如何check。跑dijkstra，大于x的边权记为1，若d<=cnt则返回true。
+ 然后数据范围小，也可以建立一个分层图跑dijkstra。
*/
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int maxn = 1e5+10;

int n, m, s, t, cnt;
vector<pair<int,int> >G[maxn];

int dist[maxn], vis[maxn];
bool check(int x){
	memset(dist,0x3f,sizeof(dist));
	memset(vis,0,sizeof(vis));
	dist[s] = 0;
	
	priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > >q;
	q.push({0,s});
	while(q.size()){
		int u = q.top().second;  q.pop();
		if(vis[u])continue;
		vis[u] = 1;
		for(int i = 0; i < G[u].size(); i++){
			int v=G[u][i].first, w=G[u][i].second;
			if(dist[v]>dist[u]+(w>x)){
				dist[v]=dist[u]+(w>x);
				q.push(make_pair(dist[v],v));
			}
		}
	}
	return dist[t]<=cnt;
}


int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m>>s>>t>>cnt;
	for(int i = 1; i <= m; i++){
		LL u, v, w;  cin>>u>>v>>w;
		G[u].push_back({v, w});
		G[v].push_back({u, w});
	}
	int l = 0, r = 1e9+10, ans = -1;
	while(l < r){
		int mid = l+r>>1;
		if(check(mid)){
			r = mid; ans = mid;
		}else{
			l = mid+1;
		}
	}
	if(ans==-1)cout<<"No\n";
	else cout<<"Yes\n"<<ans<<"\n";
	return 0;
}

Part3. L3部分，2题，部分分

L3-1，9分

7-12 PRO (30 分)
有一颗n个结点的树，给你树上每条边的初始长度，问两个结点间距离是多少。

当然由于这颗树是会生长的，所以你需要回答当前情况下给定结点间的距离。

输入格式:
第一行给定n和m，表示结点数量和询问次数

接下来n-1行每行给出u，v，w，表示结点u和结点v之间存在一条初始长度为w的边

下面m行每行给出三个数，第一个数为op

op = 1时，后面给出两个数x和w，表示第x条边生长了w的长度
op = 2时，后面给出两个数u和v，表示询问结点u和结点v之间的距离
数据范围：30%的数据 1 <= n, m <= 1000 ，100%的数据 1 <= n, m <= 2e5，1 <= w <= 1e5
输出格式:
对于每次询问，当且仅当op = 2时你需要进行回答

输入样例:
在这里给出一组输入。例如：

5 4
1 2 1
1 3 1
2 4 1
2 5 1
2 4 5
1 2 2
1 4 2
2 3 5
输出样例:
在这里给出相应的输出。例如：

2
7
作者
龙旭
单位
浙江科技学院
代码长度限制
16 KB
时间限制
1000 ms
内存限制
64 MB

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int maxn = 1e5+10;
int n, m;
int u[maxn], v[maxn], w[maxn];
map<pair<int,int>,int>ma;
vector<int>G[maxn];
int vis[maxn], ans;
void dfs(int s, int t, int res){
	if(s==t){
		ans = res;
		return ;
	}
	vis[s] = 1;
	for(int i = 0; i < G[s].size(); i++){
		if(!vis[G[s][i]]){
			///vis[G[s][i]] = 1;
			//cout<<s<<" "<<G[s][i]<<" ";
			//cout<<ma[make_pair(s,G[s][i])]<<"\n";
			dfs(G[s][i], t, res+ma[make_pair(s,G[s][i])]);
			//vis[G[s][i]] = 0;
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i = 1; i <= n-1; i++){
		cin>>u[i]>>v[i]>>w[i];
		ma[make_pair(u[i],v[i])] = w[i];
		ma[make_pair(v[i],u[i])] = w[i];
		G[u[i]].push_back(v[i]);
		G[v[i]].push_back(u[i]);
	}
	for(int i = 1; i <= m; i++){
		int op;  cin>>op;
		if(op==1){
			int x, ww;  cin>>x>>ww;
			//x--;
			ma[make_pair(u[x],v[x])]+=ww;
			ma[make_pair(v[x],u[x])]+=ww;
		}else{
			int x, y;  cin>>x>>y;
			memset(vis,0,sizeof(vis));
			ans = 0;
			dfs(x,y,0);
			cout<<ans<<"\n";
		}
	}
	return 0;
}

L3-2，3分

7-13 ydhjuruo的闯关游戏 (30 分)
蒟蒻ydh喜欢玩游戏，他最近迷上了一个闯关类游戏，并且只剩最后俩关，就可以通关这个游戏了。通过这俩关都需要一定数量的经验，第一关需要s1的经验，第二关需要s2的经验。现在有n个任务，每个任务只能做一次。对于第i个任务，他在第一关完成的话，会给xi点经验，但要消耗ti分钟，在第二关完成的话，会给yi点经验，但要消耗ri分钟（如果经验累加到超出需要数量的话，是不会留到下一关的）。ydh想知道通关花费的最少时间。

输入格式:
第一行包括三个数字n，s1，s2(1≤n,s1,s2≤500)，分别代表任务数，通过第一关需要的经验，通过第二关需要的经验。 接下来有n行，每一行有四个数字，分别代表xi，ti，yi，ri(1≤yi<xi≤500, 1≤ri<ti≤10e9)xi和yi分别代表第i个任务在第一关完成所给的经验和在第二关完成所给的经验，ti和ri分别代表第i个任务在第一关完成所花费的时间和在第二关完成所花费的时间。

输出格式:
输出一个数字，代表通关花费的最少时间，如果没能够通关，则输出-1；

输入样例:
在这里给出一组输入。例如：

2 100 100
100 100 10 10
101 11 100 10
输出样例:
在这里给出相应的输出。例如：

110
作者
尹栋豪
单位
浙江科技学院
代码长度限制
16 KB
时间限制
1000 ms
内存限制
64 MB

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int maxn = 1e6+10;
int main(){
	cout<<"-1\n";
	return 0;
}

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/115032927