2026“钉耙编程”中国大学生算法设计春季联赛（6）

1003 绩点查询

Problem Description

期末考试结束了，小 Z 想通过自己的平时分和期末分计算自己的绩点 $GPA$，具体的绩点计算方式如下。

平时分和期末分均为不超过 $100$ 的自然数，记平时分为 $S_1$，期末分为 $S_2$。

当期末分 $S_2$ 低于 $45$ 时，被判定为挂科，绩点为 $0$（即 $GPA = 0$），否则计算总分 $S = \lceil 0.6 \times S_1 + 0.4 \times S_2 \rceil$，然后根据总分计算绩点：

$$GPA = \begin{cases} 5, & S \ge 95 \\ 5 - 0.1(95 - S), & 60 \le S < 95 \\ 0, & 0 \le S < 60 \end{cases}$$

注：$\lceil x \rceil$ 表示不小于 $x$ 的最小整数，即向上取整。

Input

第一行输入一个整数 $T$ 表示测试数据组数。

对于每组数据：

一行两个非负整数整数 $S_1, S_2$。

$1 \le T \le 2 \times 10^4$

对于每组数据：

$0 \le S_1, S_2 \le 100$。

Output

对于每组数据：

一行一个浮点数表示 $GPA$，保留一位小数。

题意解读

输入s，输出gpa

解题思路

if…else判断

题解代码

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

void sol(){
	int s1, s2; cin >> s1 >> s2;
	double gpa = 0;
	if(s2 >= 45){
		int s = ceil(0.6 * s1 + 0.4 * s2);
		if(s >= 95)	gpa = 5;
		else if(s < 60);
		else gpa = 5 - 0.1*(95 - s);
	}
	printf("%.1f\n", gpa);
}

int main(){
	int t; cin >> t;
	while(t --)
		sol();
}

1005 向量压缩

Problem Description

在遥远的 $\alpha$ 星球上，人们每天需要处理和传输极长的数字向量。为了在星球一年一度的挑战赛中大幅提高自己的排名，你灵机一动，发明了一种名为“超高性能向量压缩感知”的全新压缩协议。

这个协议的核心灵感来源于古老的游戏“消消乐”：在向量的动态变化过程中，一旦出现了任意相邻的 $k$ 个完全相同的元素，这 $k$ 个元素就会瞬间发生“湮灭”并从向量中彻底消失。

更神奇的是，湮灭操作会引发连锁反应——当一段元素消失后，它前后的元素会重新拼接在一起。如果拼接后再次凑齐了相邻的 $k$ 个相同元素，它们将继续发生湮灭，直到向量中不再存在相邻的 $k$ 个相同元素为止。

现在，你想要实现一个程序，来模拟多组向量在这个压缩协议下的最终形态。

Input

第一行输入正整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行包含两个正整数 $n$ 和 $k$，分别表示向量的初始长度和触发湮灭的阈值 $k$。

第二行包含 $n$ 个正整数 $A_1, A_2, \ldots, A_n$，表示向量的初始元素值。

$1 \le T \le 10$

对于每组数据：$1 \le n \le 10^5$，$2 \le k \le 10^5$，$1 \le A_i \le 10^5$

Output

对于每组测试数据：

输出包含两行，第一行输出一个非负整数 $L$，表示最终压缩后向量的长度。

第二行输出 $L$ 个由空格隔开的正整数，表示最终的向量样子，保证最终向量不会被完全湮灭。

题意解读

给定一个序列，如果出现连续k个相同元素，将其删除，输出最后的序列

解题思路

用栈来存储每个元素，再用变量cnt记录栈顶元素数量，last保存上一个cnt。若当前元素和栈顶元素相同，先向栈中添加进这个元素，再将cnt自增1，如果cnt等于k了，那就将k个元素从栈中弹出，并将cnt变为上一次的数量last；若当前元素和栈顶元素不同，先将cnt保存给last,然后再将cnt变为1，并把这个元素加入栈中。最后注意，开始之前栈要先添加一个很小的元素方便判断。

题解代码

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

#define IO ios::sync_with_stdio(0); cin.tie(0);
//#define endl '\n'
typedef long long ls;
typedef unsigned long long uls;



void sol(){
	int n, k, cnt, last; cin >> n >> k;
	stack<int> stk;
	stk.push(-1);
	cnt = 1;
	last = 1;
	for (int i = 0; i < n; i++){
		int x; cin >> x;
		if (x == stk.top()){
			cnt++;
			stk.push(x);
			if (cnt == k){
				int t = cnt;
				while (t--)
					stk.pop();
				cnt = last;
			}
		}
		else{
			last = cnt;
			cnt = 1;
			stk.push(x);
		}
	}
	vector<int> v;
	while (!stk.empty()){
		v.push_back(stk.top());
		stk.pop();
	}
	cout << v.size() - 1 << endl;
	for (int i = v.size() - 2; i >= 0; i--)
		cout << v[i] << ' ';
}

int main(){
	IO
	int t; cin >> t;
	while (t--)
		sol();
	return 0;
}

1007 不开心世纪

Problem Description

给定一个长度为 $n$ 的正整数序列 $A$。

小 Z 不喜欢序列 $A$，他想要从 $A$ 中删除任意多个元素（包括 $0$ 个），将剩余元素保持原有的相对顺序排列，得到一个新序列 $B$，使得这个新的序列存在一个长度为 $m$ 的连续子段，并且该字段是一个排列。

小 Z 想知道最少需要在 $A$ 中删除多少元素。

补充定义：

排列：一个序列如果仅包含 $1,2,\ldots,m$ 的数字恰好各一个，那么这是一个长度为 $m$ 的排列。

子段：删除一个序列开头和结尾任意多个元素（包含零）后得到的序列。

Input

第一行输入一个整数 $T$，表示数据组数。

对于每组数据：

第一行两个正整数 $n,m$。

接下来一行 $n$ 个正整数 $a_1,a_2,\ldots,a_n$ 表示序列 $A$。

令 $N_{tot}$ 表示所有测试组 $n$ 之和。

$1 \le T \le 10, N_{tot} \le 2.1 \times 10^6$。

对于每组数据：$1 \le n,m,a_i \le 10^6$。

Output

对于每组数据：

输出一行一个整数表示最少删除元素的数量，如果无论如何都无法出现长度为 $m$ 的子段，则输出 $-1$。

题意解读

给一个序列，求最少删除多少个元素后，使得这个剩下数组成的序列存在一个长度为m的连续子段，并且该子段是一个排列

解题思路

方法1：

使用双指针（滑动窗口），右指针不断往右移动，如果符合要求了，就向右移动左指针知道达到符合要求的极限状态，将这个区间长度和ans做判断，随后右指针继续往右移动重复之前的操作，直到最右边。要注意，一个区间满足要求后，左指针不可以移动到右指针位置，因为可能存在后面找一位加上之前跳过的就符合要求的情况。

方法2：

使用二分答案（二分区间长度x，check函数通过双指针判断是否有一个长度为x的区间符合要求）。

题解代码1

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

#define IO ios::sync_with_stdio(0); cin.tie(0);
//#define endl '\n'
typedef long long ls;
typedef unsigned long long uls;
const int inf = 0x3f3f3f3f;


void sol(){	
	int n, m; cin >> n >> m;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	int res = inf;
	int s = 0;
	map<int, int> mp;
	auto add = [&](int x){
		mp[x]++;
		if (mp[x] == 1 && x >= 1 && x <= m)
			s++;
	};
	auto sub = [&](int x){
		mp[x]--;
		if (mp[x] == 0 && x >= 1 && x <= m)
			s--;
	};
	for (int i = 0, j = 0; i < n; i++){
		add(a[i]);
		while (s == m && (mp[a[j]] > 1 || a[j] > m))
			sub(a[j++]);
		if (s == m)
			res = min(res, i - j + 1 - m);
	}
	if (res == inf)
		cout << -1 << endl;
	else
		cout << res << endl;
}

int main(){
	IO
	int t; cin >> t;
	while (t--)
		sol();
	return 0;
}

题解代码2

#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
#define PII pair<int, int>
typedef unsigned long long uls;
typedef long long ls;
const int inf = 0x3f3f3f3f;
const int N = 1LL << 21;
const int M = 1e6 + 10;


void sol(){
	int n, m; cin >> n >> m;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	//判断长度为len是否有至少一个排列
	auto check = [&](int len){
		vector<int> vis(M, 0);
		int s = 0;
		for (int i = 0; i < len; i++){
			vis[a[i]]++;
			if (a[i] >= 1 && a[i] <= m && vis[a[i]] == 1)
				s++;
		}
		if (s == m)
			return true;
		for (int i = len; i < n; i++){
			vis[a[i - len]]--;
			if (a[i - len] >= 1 && a[i - len] <= m && vis[a[i - len]] == 0)
				s--;
			vis[a[i]]++;
			if (a[i] >= 1 && a[i] <= m && vis[a[i]] == 1)
				s++;
			if (s == m)
				return true;
		}
		return false;
	};
	int l = 1, r = n, ans = -1;
	while (l <= r){
		int mid = l + (r - l) / 2;
		if (check(mid)){
			r = mid - 1;
			ans = mid;
		}
		else{
			l = mid + 1;
		}
	}
	if (ans == -1)
		cout << -1 << endl;
	else
		cout << ans - m << endl;
//	cout << check(5) << endl;
}

signed main(){
	IO
	int t; cin >> t;
	while (t--)
		sol();
	return 0;
}