2022年河北师范大学程序设计大赛题解

A-百廿师大

问题描述：

2022年10月15日，欣逢河北师范大学120周年华诞，学校将隆重举办系列庆典活动。

春秋代序，岁月沧桑。1902年顺天府学堂创建于北京，1906年北洋女师范学堂发轫于天津。两支主脉，筚路蓝缕，自强不息，崇尚真理，爱国担当，开时代教育新风。1996年，原河北师范大学、河北师范学院、河北教育学院、河北职业技术师范学院合并，组建新河北师范大学。

四源汇流，弦歌赓续。学校秉持“怀天下、求真知”校训，坚持“学博为师、德高为范”办学底色，传承红色基因，不忘初心使命。乘高教改革发展长风，抓省部共建和“双一流”建设机遇，围绕建设高水平综合性师范大学目标，致力内涵式高质量发展，肩负人才培养、科学研究、社会服务、文化传承创新、国际交流合作重要使命，努力向党和人民交出满意答卷。

立德树人，思源怀远。学校120周年庆典，旨在宣示庄严使命，展示办学成就，总结办学经验，共谋未来发展。

百廿师大，120周年华诞之日距今天数几何？

输入：

无输入

输出:

输出共一行，包括一个正整数n。n表示今天离河北师范大学120周年校庆的日子还有多少天（不包括今天）。
例：距离2022年4月1日则为 1 天。

样例输入：

//无

样例输出：

//无

拙见：

~~打开屏幕右下角日历去数~~

此比赛是2022年3月31日进行的，所以距离2022年10月15日有31 * 3 + 30 * 3 + 15 = 198天

CODE：

# include <bits/stdc++.h>
using namespace std;

int main() {
	cout << 31 * 3 + 30 * 3 + 15;
}

B-汉堡店的校庆套餐

问题描述：

喜迎校庆，食堂的汉堡店为此推出了许多的组合套餐。一份汉堡一份饮料，配出生活新气象！

汉堡店一共有n种汉堡，同时也有n种汽水，当你购买购买某种汉堡的时候，只要同时购买对应的饮料（即汉堡和饮料的下标相同），就可以享受到校庆专属优惠！

喜欢吃汉堡的河小师当然不会错过这个活动，河小师对不同的饮料和汉堡会有不同的满足度，现在河小师该买哪个套餐，才能获得最大的满足度呢？

给定两个数组，长度均为n。第一个数组给定所有的汉堡满足度，第二个数组给定所有饮料的满足度，河小师可以购买下标相同的饮料和汉堡，问购买第几组套餐，河小师能获得最大满足度。（若存在多组最大满足度套餐，输出下标最小的一组，下标从1开始。）

输入：

输入共三行。

第一行，包括一个正整数n（1 <= n <= 2e5），代表汉堡和饮料的种类数。

第二行，包括n个数 a[1],a[2],…,a[n] （1 <= a[i] <= 2e5）分别表示每种汉堡的满足度。

第三行，包括n个数b[1],b[2],…,b[n] (1 <= b[i] <= 2e5)，分别表示每种饮料的满足度。

输出:

输出共一行，包括一个正整数。表示选择的套餐的下标。

样例输入：

1
2
3

3
1 2 3
1 2 1

样例输出：

拙见：

输出a[i] + b[i]最大的组合套餐的下标。

CODE：

# include <bits/stdc++.h>
using namespace std;

int main() {
	int n,ans,maxV = -1;
	cin >> n;
	vector<int> a(n + 1),b(n + 1);
	for (int i = 1;i <= n;i ++) cin >> a[i];
	for (int i = 1;i <= n;i ++) {
        cin >> b[i];
        b[i] += a[i];
        if (b[i] > maxV) ans = i,maxV = b[i];
    }
	cout << ans;
}

C-多少台阶

问题描述：

享受完美食后，河小师发现食堂门口的台阶贴了喜迎校庆的贴纸，河小师发现，所有阶数为a的倍数或b的倍数的台阶都被贴上了贴纸，好奇的河小师想知道总共有多少台阶上被贴了贴纸。

一共有n个台阶，所有阶数为a的倍数的台阶或者是b的倍数都被贴上了贴纸，求出一共有多少台阶被贴上了贴纸。

输入：

第一行输入一个数t，表示样例数量。(1 <= t <= 1e4)

输入共t行，每行包括三个正整数n,a,b。（1 <= n <= 2e9，1 <= a <=2e9，1 <= b <= 2e9）

输出:

输出共一行，包括一个正整数。被贴上贴纸的台阶总数。

样例输入：

样例输出：

1
2
3

7
5
4

拙见：

容斥原理

能被a染色的台阶数量加上能被b染色的台阶数量，再减去能被a和b的最小公倍数染色的台阶数目

最小公倍数 = a * b / 最大公约数

CODE：

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve() {
	ll n,a,b;
	cin >> n >> a >> b;
	cout << n / a + n / b - n / (a * b / __gcd(a,b)) << endl;
}
int main() {
	int t;
	cin >> t;
	while(t --) solve();
	return 0;
}

D-广场的字符游戏

问题描述：

穿过公教楼，河小师来到了四方广场，这里正在进行校庆游戏，每个人会得到一个由字符’0’和字符’1’组成的字符串，每一次操作可以将其中的任意一个0改成1，也可以将任意一个1改成0，改动之后只要保证不存在任何以101或是010构成的子序列即可完成游戏，获得奖励。河小师怎么样才能以最少的操作次数来解决这个问题呢？

注：某个序列的子序列是从最初序列选出一部分元素但不破坏他们在原序列中的相对顺序而形成的新序列。例如：110001，可以选出第一个，第三个，第六个字符组成101这个子序列。

输入：

输入第一行为数据组数t，表示一共有t组数据。（1 <= t<= 1e3）

每组数据共一行，包括一个字符串s。（1 <= s.size() <= 1e3）

输出:

输出共一行，包括一个正整数。表示解决问题的最少的操作次数。

样例输入：

样例输出：

拙见：

题中所述101和010其实是1……10……01……0和0……01……10……0这种若干个连续数字的序列。

因此要使得这个序列满足条件，只有四种形式

000……000 111……111 1……10……0 0……01……1

统计0和1的数量，取最小值，这一步是当令序列变成0……0和1……1时，所需要的操作次数。

此外需要枚举一个0和1的分界点，取最小值，这一步是当令序列变成1……10……0 和0……01……1时，所需要的操作次数。

CODE：

# include <bits/stdc++.h>
using namespace std;
void solve() {
	string s;
	cin >> s;
	int one = 0,zero = 0;
	for (int i = 0;i < s.size();i ++)
		if (s[i] == '1')	one ++;
		else zero ++;
	int ans = min(one,zero);
	int a = 0,b = 0;
	for (int i = 0;i < s.size();i ++) {	//枚举分界点
		if (s[i] == '1') a ++;
		else b ++;
		ans = min(ans,b + one - a); //1……10……0形式
		ans = min(ans,a + zero - b); //0……01……1形式
	}
	cout << ans << endl;
}
int main() {
	int t;cin >> t;
	while(t --) solve();
	return 0;
}

E-图书馆借书

问题描述：

获得了奖励，河小师开开心心的去图书馆学习，河小师了解到，图书馆最多能放n本书。一开始图书馆里有满满当当的n本书，河小师在第一天的时候会在早上归还m本书，并在晚上的时候借走一本书，第二天的时候在早上归还m本书，并在晚上的借走两本书… 第i天的时候会在早上归还m本书，并在晚上的时候借走i本书，到第几天的时候，图书馆的书第一次被借完呢？

图书馆可以存放的书籍数量最多为n本，多余的书河小师会带回宿舍之后再进行归还。

输入：

输入共一行，包括两个正整数n,m。（1 ≤ n, m ≤ 1e18）

n表示图书馆的书籍最大容量，m表示每次的还书数。

输出:

输出共一行，包括一个正整数。表示在第几天图书馆的书第一次被借完。

样例输入：

5 3

样例输出：

提示：

样例解释：
第1天应该归还3本但是图书馆满了没有还书，只借了1本书，图书馆还有4本书
第2天应该归还3本但是图书馆只能容纳1本书，故还1本书，借了2本书，图书馆还有3本书
第3天应该归还3本但是图书馆只能容纳2本书，故还2本书，借了3本书，图书馆还有2本书
第4天还3本书，借了4本书，图书馆还有1本书
第5天还3本书，应该借5本书，但是图书馆只有4本书了，所以借了4本，第一次没有剩余书本。

拙见：

两种情况，n <= m和n > m.

当n <= m时，每一天早上要还的书都能填满图书馆的容量，所以当第n天时，第一次将所有n本书借走。

当n > m时，由于每天都要还m本书，所以在前m天中图书馆每天的书只会减少1，在第m天时，图书馆此时剩余n - m本书；在第m天以后，图书馆的书每天会减少1,2,3,……本书，可以得知这是一个公差为1的等差数列。我们的问题是求哪天能第一次将图书馆中的书全部借出，所以从第m + 1天开始，求这个等差数列的前 $n$ 项和 $S_n$ 为多少时，刚好能 $S_n \ge n - m$ 。由于公差 $d = 1$ ，所以前n项和公式为 $S_n = \frac {n * (n + 1)} 2$ 。由于这个符合单调性，所以可以用二分来查找。最后答案为 $S_n$ 中的n + m。

关于二分的范围，当n为最大的数据1e18时，大约是 $\frac {x * (x + 1)} 2 = 1e18$ ，即 $x^2 + x = 2e18$ ，所以可以近似为 $x^2 = 2e18, x = 2e9$ ，因此二分的右边最小为 $2e9$ 。

CODE：

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
	ll n,m;
	cin >> n >> m;
	if (n <= m) cout << n << endl;
	else
	{
		ll l = -1,r = 2e9 + 10;
		while(l + 1 != r) {
			ll mid = l + r >> 1;
			if (mid * (mid + 1) / 2 >= n - m)	r = mid;
			else l = mid;
		}
		cout << r + m << endl;
	}
	return 0;
}

F-爱学习的河小师

问题描述：

河小师开始学习啦，他打开一本有趣的算法书，从前往后有n道有趣的题目，每个题目都有一个难度值。因为河小师拥有着勇于挑战的精神，所以做的下一题的难度值和题号都必须高于当前做的题并且河小师只能按题号递增顺序做题（第一题做哪个可以任意选择，若河小师选择做第i题，那么下一个做的题目只能从第i+1个题到第n个题里选择），如何挑选决定去做的题，河小师能做到最多的题目数量呢？

给定n个题目的难度值，从小到大依次输出河小师选择的题目难度

如果有多个答案，请输出其中按数值（注：区别于按单个字符的ASCII码值）进行比较的字典序最小的那个答案。

输入：

输入共两行。

第一行包括一个正整数n，表示数组的长度。（0 <= n <= 2e5）

第二行给定n个正整数a1,a2,a3,…,a[i],…,a[n]，第i题表示题号为i的题目的难度值。（0 <= a[i] <= 1e9）

输出:

输出共一行，从小到大依次输出河小师选择的题目难度。

样例输入：

样例输入一：
9
2 1 5 3 6 4 8 9 7

样例输入二：
5
1 2 8 6 4

样例输出：

样例输出一：
1 3 4 8 9

样例输出二：
1 2 4

提示:

样例一解释：河小师选择第2题，第4题，第6题，第7题和第8题，故难度依次为1，3，4，8，9.

拙见：

这个题本质上是求最长上升子序列。

由于数组的长度最大为2e5，所以不能用 $O(n^2)$ 的DP来做，应该用贪心+二分来优化，并且在每次记录下dp[i]的长度。二分的部分可以用C++的lower_bound()函数代替。

至于最小字典序输出，只需要从后往前找，具有相同长度的，就是最小字典序。

证明，样例二的dp数组为1 2 3 3 3，这个数组是有性质的，比如dp[3],dp[4],dp[5]都为3，那么则说明a[3] $\le$ a[4] $\le$ a[5]，可以证明如果a[5] $\ge$ a[4]的话，那么dp[5]一定比dp[4]要大。

CODE：

# include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int dp[N],f[N],a[N],ans[N],len,n;
int main() {
	cin >> n;
	for (int i = 1;i <= n;i ++)	cin >> a[i];
	for (int i = 1;i <= n;i ++) {
		int idx;
		if (a[i] > f[len]) {
			f[++ len] = a[i];
			idx = len;
		} else idx = lower_bound(&f[1],&f[len],a[i]) - &f[0];
		dp[i] = idx;
		len = max(len,idx);
		f[idx] = a[i];
	}
	int cnt = len;
	for (int i = n;i >= 1;i --)
		if (dp[i] == len) 
			ans[len --] = a[i];
	for (int i = 1;i <= cnt;i ++)
		cout << ans[i] << ' ';
	return 0;
}

G-真知树上真知果

问题描述：

河小师学的有些渴了，想寻些水果充饥解渴。相传（传说往往虚无缥缈），河北师范大学里有一颗神奇的树，叫真知树。这颗树上有n个节点，在这n个节点里，隐藏着许许多多美味多汁的真知果，当你发现有三个节点两两之间的最短路的长度可以构成一个三角形的时候，你就可以发现一个真知果。（节点可以重复使用，但是三个相同节点只能发现一个真知果）

聪明的你可以计算一下真知树上有多少真知果吗？

输入：

第一行包括一个正整数n, 表示树的节点个数。(1≤n≤1e5)

接下来n−1行, 每一行三个整数u, v, w 表示节点u 和 v之间有一条边权为w的边。(1≤w≤1e5,1≤u,v≤n)

输出:

一行共一个整数, 表示真知果的数量。

样例输入：

样例输出：

拙见：

#505. 三角果计数

将样例画出以后发现，构成三角形的条件在本题中与权值并无关系，只要不是在一条路径上的三个点就可以构成一个三角形。三点之间应直接或间接连接同一节点，我们把这个同一节点称为中心节点。

可以发现当且仅当这个中心节点的度大于等于3时，这个中心节点可以产生贡献。把这个中心节点的度分成三部分，这三部分的节点数分别为多少，三部分相乘的结果就是这个中心节点的贡献值。

因此答案就是所有中心节点的贡献值的累加.

三部分

如当节点2的贡献值为1 * 1 * 4 = 4.

dfs时维护一个数组，统计每个节点的度。

CODE：

# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N = 1e5 + 10;
vector<int> g[N];
int siz[N];
int n,ans;
void dfs(int u,int v) {
    for (int i = 0;i < g[u].size();i ++) {
        int t = g[u][i];
        if (t != v) {
            dfs(t,u);
            ans += siz[u] * siz[t] * (n - siz[u] - siz[t] - 1); //三部分相乘
            siz[u] += siz[t];
        }
    }
    siz[u] ++; //自身
}
signed main() {
    cin >> n;
    for (int i = 1;i < n;i ++) {
        int u,v,w;
        cin >> u >> v >> w;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    cout << ans << endl;
    return 0;
}

H-真知树旁

问题描述：

真知树旁，还有一颗有根树，它也拥有个节点，每个节点有一个权值a[i]。同时我们知道，树上逆序对就是一个由当前节点和它的父节点组成的二元对，同时这两个节点满足子节点的权值小于父节点的权值。

对于一颗完全m叉树，节点i的子节点很明显就是 $[m*(i−1)+2,m*(i+1)]$ 和 $[1,n]$ 交集中的所有正整数。

现在我们想要知道，在这颗包含n个节点，同时每个节点的权值分别为的有根树上。河小师抱着怀天下求真知的精神，她想知道若这课树是完全m叉树，其树上逆序对的数量有多少。 $m=1,2,…,n−1.$

输入：

第一行包括一个正整数 n , 表示有根树上结点的个数。 (2≤n≤2e5)

第二行包含 n 个正整数，分别表示结点的权值(1≤ai≤1e9)

输出:

输出一行 n−1 个整数分别表示m=1,2,…,n−1时树上逆序对数

样例输入：

1 2	5 5 4 5 4 3

样例输出：

3 2 3 3

拙见：

CODE：

I-夜幕落星河

问题描述：

夜色渐浓，黄昏不住。

月光触碰夜幕，银河拂过云朵，万千城市共此点亮灯火。

学习了一天的河小师眼中落满星河，看星星一颗，两颗，三颗，四颗，连成线！

河小师一共看见了n颗星星，由上文可知，星星之间是可以连线的，它们一共连成了m条星线。当一些星线组成一个环的时候，就会产生奇幻效应，这个环内的所有点之间会产生非常大的吸引力，导致这个环内的所有点之间可以互相传送。环和环之间同样会产生吸引力，若两个环包含的星星数目相同，则两个环之间也可以相互传送。

河小师想起了牛郎织女的童话故事，织女会随机出现在一个包含k个点的环上，但是织女没有时间等待牛郎慢慢寻找她，天帝只给织女s秒钟的时间和牛郎相见，牛郎从沿着星线从一个星星走到另一个星星需要花费1秒的时间，在环内和环间传送不会花费时间，牛郎特别期待能见到织女，河小师想知道牛郎在哪些星星上出发，能在s秒内见到织女，聪明的同学们，你们能帮帮河小师吗。

数据保证只存在简单环，即去掉环内任意一条边这个环就不存在了

输入：

第一行共四个正整数n,m,k,s。(2<=n<=1e5,1<=m<=2e5，2<=k<=25,0<=s<=100)

n表示星星的数目，m表示星线的数目，k表示织女出现的环包含的点数，s为天帝允许织女等待牛郎的时间

输出:

输出一个数表示答案

样例输入：

样例输出：

提示：

样例解释：
1号星星到达点数为2个点的环需要1秒，2、3、10、11号星星本身就在环内，互相传送不需要花费时间，4、5、6、7、9号星星到达星星数为2的环需要1秒，8号至少需要两秒不符合条件（1种方案是先到达星星4、5、6、7组成的环，再到达2、3组成的环，需要2秒。第二种方案是先到达9号星星，再到达10、11组成的环，因为星星数相同的环之间传送不需要花费时间，不管织女在哪个环上，都可以传送到达）。所以牛郎在10个点的任意一个点出发都可以在1秒之内找到织女