第五届“传智杯”全国大学生计算机大赛（练习赛）

A [传智杯 #5 练习赛] 复读

题目描述

给定若干个字符串，不定数量，每行一个。有些字符串可能出现了多次。如果读入一个字符串后，发现这个字符串以前被读入过，则这个字符串被称为前面相同的字符串的复读，这个字符串被称为复读字符串。相应的，每个首次出现的字符串就是非复读字符串。

举个例子，

abc
def
abc
abc
abc

第 $1,3,4,5$ 行是字符串 abc，那么 $3,4,5$ 行的字符串会被称为“复读”。

请你把所有的非复读字符串，按照行号从小到大的顺序，依次拼接为一个长串并输出。

输入格式

多个字符串，每行一个，含义见题目描述。

注意：如果这个字符串是 0，说明所有字符串都读完了。这个 0 不认为是一个“非复读字符串”。

输出格式

共一行，表示所有非复读字符串，按照行号从小到大依次连接的结果。

样例 #1

样例输入 #1

cc
b
a
cc
0

样例输出 #1

ccba

提示

【数据范围】

字符串的个数不超过 $500$ 个，字符串总长度不超过 $50000$，每个字符串中只包含小写字母、数字、 . 、! 和 &，不包含空格等特殊符号。

代码解析如下

• 大循环：
  • 读入字符串，存入数组，计数，
  • 目前已经读到第 cnt 个，如果是"0"就跳出
  • 枚举这个字符串有没有被读过，使用小循环枚举。如果没出现过就输出这个字符串。
• 小循环：
  • 从1枚举到 cnt -1，看看之前有没有出现过这个学符串。

#include <iostream>
#include <string>
using namespace std;
string s[600];
int main() {
	int cnt = 0;
	while (true) {
		++cnt;
		cin >> s[cnt];
		if (s[cnt] == "0") break;
		bool vis = false;
		for (int i = 1; i < cnt; i++)
		{
			if (s[i] == s[cnt]) {
				vis = true; break;
			}
		}
		if (vis == false) cout << s[cnt];
	}
	return 0;
}

B [传智杯 #5 练习赛] 时钟

题目描述

你有一个电子钟，可以显示 0:00 到 23:59 之间的所有时间，以数字的形式显示。其中小时是 0 到 23（0 时会显示一个 0，而 1 到 9 时不会显示前导 0），分钟是 00 到 59（0 到 9 分都会显示前导 0）。任何时刻，电子钟都会显示三个或者四个 $0$ 到 $9$ 的数字。如果在某时刻，这些数字依次组成了一个等差数列，则这个时刻被称为“好时刻”。

你感觉很无聊，从 0:00 时刻开始盯着这个电子钟。一共盯了 $x$ 分钟。请问整个过程中，"好时刻"来临了多少次（算上开头和结尾）？

输入格式

一个不超过 $10^9$ 的非负整数。

输出格式

请输出"好时刻"来临了多少次？

样例 #1

样例输入 #1

120

样例输出 #1

10

样例 #2

样例输入 #2

2880

样例输出 #2

79

样例 #3

样例输入 #3

987654321

样例输出 #3

26748975

提示

【样例解释】

你观察了 2 个小时，其中这些“好时刻”来临了：

0:00
0:12
0:24
0:36
0:48
1:11
1:23
1:35
1:47
1:59

一共是 10 个。

代码解析如下

• 直接按分钟枚举？10^9会超时！
• 每一天都是一样的，所以可以先计算这么多分钟是几个整天。
• 一天有39个“好时刻”
• 对于剩下的时间，可以进行枚举。这里使用两重循环枚举，小时和分钟。
• 将各个位数拆散。
• 如果小时不小于10，则比较4个数字是否等差，否则比较3个。

#include <iostream>
#include <string>
using namespace std;
int main() {
	int n, days, ans = 0;
	cin >> n;
	days = n / 1440; n %= 1440;
	ans = days * 39;
	for (int h = 0; h < 24; h++)
	{
		for (int m = 0; m < 60; m++) {
			int a, b, c, d;
			a = h / 10; b = h % 10;
			c = m / 10; d = m % 10;
			if (h >= 10 && b - a == c - b && c - b == d - c) 
				ans++;
			if (h <= 9 && c - b == d - c)
				ans++;
			n--;
			if (n < 0) break;
		}
	}
	cout << ans << endl;
}

C [传智杯 #5 练习赛] 平等的交易

题目描述

你有 $n$ 件道具可以买，其中第 $i$ 件的价格为 $a_i$。

你有 $w$ 元钱。你仅能用钱购买其中的一件商道具。当然，你可以拿你手中的道具换取其他的道具，只是这些商道具的价值之和，不能超过你打算交换出去的道具。你可以交换无数多次道具。道具的价值可能是 $0$，但是你不能使用空集换取价值为 0 的商品。

请问，在这个条件下，最多可以换取多少件道具？

输入格式

第一行一个正整数 $n$，表示道具个数。

接下来一行 $n$ 个正整数，表示 { a n } \{a_n\} {an​}。

接下来一行 $1$ 个正整数，表示 $w$。

输出格式

一个正整数，表示答案。

样例 #1

样例输入 #1

3 
1 1 2
5

样例输出 #1

2

提示

【样例解释】

买价值为 $2$ 的道具，并交换为两个价值为 $1$ 的道具。

【数据范围及约束】

测试数据满足，$1\le n\le 10^6$，$0\le a_i\le 10^9$，$1\le w\le 2\times 10^9$。

代码解析如下

• 贪心题。贪心需要证明。
• 首先排序。
• 用钱买最贵的那一个。
• 用这一个去尽可能换价值低的，能拿就拿。
• 证明：
  • 钱变成有价值的商品，只能买一个，那选择最贵的。
  • 一定数量的钱，买便宜的可以更多（可以反证法）。

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int n, w;
long long tmp, cnt = 0;
long long a[1000010];
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	cin >> w;
	sort(a+1,a+n+1);
	for (int i = n; i>=1 ; i--)
	{
		if (a[i] <= w) {
			tmp = a[i];
			break;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (tmp - a[i] >= 0) {
			cnt++;
			tmp -= a[i];
		}
	}
	cout << cnt;
	return 0;
}

D [传智杯 #5 练习赛] 清洁工

题目描述

有一个 $n\times n$ 的地块，一个连续 $i$ 分钟没人经过的地面在第 $i$ 分钟会落上 $i$ 个单位的灰，有人经过时不会落灰但灰也不会清零，在人走后第一分钟又会落上一个单位的灰，以此类推。你在这个 $n\times n$ 的范围内移动，你的移动轨迹可以描述为一个由 $\text{N,S,W,E}$ 组成的字符串，每个字母分别表示上、下、左、右。这个人一开始在点 $(x,y)$，每一分钟移动一步。

求最后每一个位置上落下的灰的量。

本题中的上和右分别表示 $y$ 轴正方向和 $x$ 轴正方向。保证你没有超过移动的范围。

输入格式

第一行四个正整数 $n,m,x,y$，含义如题面所示，其中 $x,y$ 表示横纵坐标，不是数组下标。
第二行一个长度为 $m$ 的字符串，表示你的移动序列。

输出格式

共$n$ 行，每行 $n$ 个数，第 $i$ 行的第 $j$ 个数表示坐标 $(j,n-i+1)$ 上的灰的数量

样例 #1

样例输入 #1

5 4 1 1
NENW

样例输出 #1

10 10 10 10 10 
10 10 10 10 10 
10 6 10 10 10 
4 4 10 10 10 
6 10 10 10 10

样例 #2

样例输入 #2

7 14 1 1
NENENENENESSSS

样例输出 #2

105 105 105 105 105 105 105 
105 105 105 105 55 61 105 
105 105 105 49 51 69 105 
105 105 51 49 105 79 105 
105 61 55 105 105 91 105 
79 69 105 105 105 105 105 
91 105 105 105 105 105 105

样例 #3

样例输入 #3

10 70 2 2
NWSNSNNNSNNSSNNSENNNNEESNWSESESSWENNSEWESWWWESEEESENNSENWNESNWSNNNEESS

样例输出 #3

2485 2485 2485 2485 2485 2485 2485 2485 2485 2485 
2485 1407 1205 1267 2485 2485 2485 2485 2485 2485 
2485 1435 1281 1167 2485 2485 2485 2217 2281 2347 
2485 1465 2485 1255 1041 2485 2485 2155 2485 2415 
1557 1497 2485 2485 969 1177 2485 1733 1807 2485 
1471 1531 1315 907 935 1267 2485 1473 1647 2485 
1631 2485 2485 1357 1381 1407 1435 1499 1645 2485 
2021 2347 2485 2485 2485 2485 1465 1497 2485 2485 
2087 2415 2485 2485 2485 2485 2485 2485 2485 2485 
2485 2485 2485 2485 2485 2485 2485 2485 2485 2485

样例 #4

样例输入 #4

5 4 2 1
NENW

样例输出 #4

10 10 10 10 10 
10 10 10 10 10 
10 10 6 10 10 
10 4 4 10 10 
10 6 10 10 10

提示

本题 y 轴朝上，x 轴朝右，样例输出中的左下角表示 $(1,1)$，第一分钟你在初始点处，第二分钟移动到相应的位置，第 $m+1$ 分钟移动到最后一个点，但是总共只有 $m$ 分钟，因此最后一个点不受移动的影响

---

样例 1 解释：

你的移动路径为 $(1,1)\to (1,2)\to (2,2)\to (2,3)\to (1,3)$，共 $4$ 分钟。

对于第 $1$ 分钟，$(1,1)$ 灰层数不变，其余点被落下了 $1$ 层灰。

对于第 $2$ 分钟，$(1,2)$ 灰层数不变，$(1,1)$ 被落下了 $1$ 层灰，其余点落下 $2$ 层灰。

对于第 $3$ 分钟，$(2,2)$ 灰层数不变，$(1,1)$ 落下 $2$ 层灰，$(1,2)$ 落下 $1$ 层灰，其余点落下 $3$ 层灰。

对于第 $4$ 分钟，$(2,3)$ 灰层数不变，$(1,1)$ 落下 $3$ 层灰，$(1,2)$ 落下 $2$ 层灰，$(2,2)$ 落下 $1$ 层灰，其余点落下 $4$ 层灰。

注意最后你移动到了 $(1,3)$，但是时间只有 $4$ 分钟，所以实际上不会对 $(1,3)$ 造成影响。初始点不一定在 $(1,1)$。

$1\le n\le 50,1\le m\le 1000$。

代码解析如下

• 模拟题。
• 开一个 n * n 的 vector 阵列，有点像三维数组。
• 读入字符串，根据每个字符进行模拟。记录位置，然后v[x][y]的 vector 记录访问时间。
• 对于每个位置，计算间隔，再根据等差数列的性质计算厚度。
• 考察了 STL 的用法

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, x, y;
vector <int> v[1005][1005];
string s;
int calc(int x) {
	return x * (x + 1) / 2;
}
int main(){
	cin >> n >> m >> y >> x;
	cin >> s;
	for (int i = 0; i < s.size(); i++)
	{
		v[x][y].push_back(i + 1);
		if (s[i] == 'N') x++;
		if (s[i] == 'S') x--;
		if (s[i] == 'E') y++;
		if (s[i] == 'W') y--;
		if (x<1 || x>n || y<1 || y>n) {
			cout << "Wrong!";
			return 0;
		}
	}
	for (int i = n; i >= 1; i--, printf("\n")) {
		for (int j = 1; j <= n; j++)
		{
			v[i][j].push_back(s.size() + 1);
			int ans = 0, now = 0;
			for (int k = 0; k < v[i][j].size(); k++)
			{
				ans += calc(v[i][j][k] - now - 1);
				now = v[i][j][k];
			}
			printf("%d ", ans);
		}
	}

	return 0;
}

E [传智杯 #5 练习赛] 树的变迁

代码解析如下

• 数据结构题，考察树的性质和并查集。有删边但没有恢复边的操作：
• 存下所有操作，逆序操作的套路。
• 逆序后操作：只有加边没有删边了，并查集维护。
• 求点权和：用带权并查集维护，祖结点维护权值和。
• 修改权值：在父亲的点上减去本身的贡献加上新的贡献即可。

#include<bits/stdc++.h>
using namespace std;
const int N=100100;
int fa[N];
int getfa(int u){
	if(fa[u]==u){
		return u;
	}
	return fa[u]=getfa(fa[u]);
}
int val[N],siz[N];
vector<int> v[N];//记录出现过的点权
void merge(int u,int v){
	u=getfa(u);
	v=getfa(v);
	if(siz[u]>siz[v])	swap(u,v);
	fa[u]=v;
	val[v]+=val[u];//中途更新点权和
	siz[v]+=siz[u];
}//按秩合并
struct ask{
	int opt,u;
}a[N];
int x[N],y[N];
bool vis[N];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>val[i];
		v[i].push_back(val[i]);
		fa[i]=i;
	}
	for(int i=1;i<n;i++)	cin>>x[i]>>y[i];
	for(int i=1;i<=m;i++){
		cin>>a[i].opt>>a[i].u;
		if(a[i].opt==1)	vis[a[i].u]=1;
		else if(a[i].opt==2){
			cin>>val[a[i].u];
			v[a[i].u].push_back(val[a[i].u]);
		}
	}
	for(int i=1;i<n;i++)
		if(!vis[i])
			merge(x[i],y[i]);	//没有删除的边先加进去
	vector<int> ans;
	for(int i=m;i;i--)
		if(a[i].opt==1){
			int l=a[i].u;
			merge(x[l],y[l]);
		}//加边
		else if(a[i].opt==2){
			int u=a[i].u;
			int last=v[u].back();
			v[u].pop_back();
			val[getfa(u)]+=(v[u].back()-last);
		}//更改点权，增加踢出当前栈顶的新栈顶-当前栈顶的贡献
		else{
			int u=a[i].u;
			ans.push_back(val[getfa(u)]);
		}//处理询问
	for(;ans.size();ans.pop_back())	cout<<ans.back()<<endl;//注意要倒序
	return 0;
}

后面一题战略性放弃……
可以看剪贴板https://www.luogu.com.cn/paste/fi60s4yu