“卓见杯”郑州轻工业大学第十五届程序设计大赛暨河南省高校邀请赛题解

题目链接

3-11题的题解均已写完

C 最大的数 — 贪心

首先n个点有n条边必然有环，因此可以无限制的加数，又因为题目要求最大不超过1e9，所以答案一定是9位数
如果把形成的环缩点的话就会变成拓扑序列，首先要找到数字最大的那几个点，把他们入队，然后遍历他们的下一个点，找到下一个点里的最大值，再把等于最大值的下一个点入队，这样贪心一定能得到最优解，循环9次，即可找到最大的那个9位数

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

signed main()
{
	int n; cin >> n;
	vector<int> e(n + 1), val(n + 1);
	vector<vector<int>> pos(10);
	// 由题意可知每个点只有一条出边 
 	for(int i = 1, x; i <= n; i ++) cin >> e[i];
	// pos记录值为 i 的 点有哪些 
	for(int i = 1; i <= n; i ++){
		cin >> val[i];
		pos[val[i]].push_back(i);
	}
	
	vector<int> res, can[10];
	// 找出最大的所有点作为出发点 
	int maxv = 0;
	for(int i = 9; i >= 0; i --) 
		if(pos[i].size()) {
			maxv = i;
			can[1] = pos[i];
			break;
		}
	res.push_back(maxv);
	for(int i = 1; i <= 8; i ++){
		maxv = 0;
		// 找出目前所到的点的下一个的最大值 
		for(auto x : can[i]) maxv = max(maxv, val[e[x]]);
		for(auto x : can[i]){
			// 找出等于这个最大值的下一个点，作为下一次遍历的开始 
			if(val[e[x]] == maxv)
				can[i + 1].push_back(e[x]);
		}
		res.push_back(maxv);
	}
	for(auto x : res) cout << x;
}

D 兔子爱吃胡萝卜—01背包

题意可转化为 给一个长度为m的数组，求取出数组中的若干个数，使其和为n的倍数
如果只是凑出n的话就是最经典的01背包，变为n的倍数就要多加一个取模

f[i][j]状态表示为：前i个数，可以凑出模n后的数j
状态计算：分为当前第i个数 取还是不取
取： f[i][(j + a[i]) % n] |= f[i - 1][j]
不取：f[i][j] |= f[i - 1][j]

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

int f[1010][1010] = {0};
int a[1010] = {0};
int n, m;	
signed main()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i ++) cin >> a[i], a[i] %= n;
	for(int i = 1; i <= m; i ++)
	{	
		f[i][a[i]] = 1;
		for(int j = 0; j < n; j ++)
		{
			f[i][(j + a[i]) % n] |= f[i - 1][j];
			f[i][j] |= f[i - 1][j];
		}
	}
	if(f[m][0]) cout << "YES" << '\n';
	else cout << "NO" << '\n';
}

E 小Z的难题—小模拟签到

从后往前遍历，把最后连续的z全变成a
找到第一个不是z的加1

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
signed main()
{
	int n; cin >> n;
	string s; cin >> s;
	bool f = true;
	for(int i = n - 1; i >= 0; i --)
		if(s[i] == 'z') s[i] = 'a';
		else{
			s[i] ++;
			f = false;
			break;
		}
	if(f) cout << "No solution";
	else cout << s;
}

F 莫比乌斯最大值isUsefulAlgorithm—枚举+思维

注：这里gcd指最大公约数
需要注意a，b数组每个值小于1e5，直接枚举gcd，然后枚举gcd的倍数即可
枚举gcd时如果a，b数组还有公约数，根据贪心，一定会枚举到更大的公约数，把答案更新
调和级数，复杂度是Onlogn

#include <iostream>
#include <vector>
using namespace std;
#define int long long
int a[100010], b[100010];
signed main()
{
	int n, x; cin >> n;
	for(int i = 1; i <= n; i ++) cin >> x, a[x] = 1;
	for(int i = 1; i <= n; i ++) cin >> x, b[x] = 1;
	int res = 0;
	for(int i = 1; i <= 100000; i ++)
	{
		int maxa = 0, maxb = 0;
		for(int j = i; j <= 100000; j += i)
		{
			if(a[j]) maxa = j;
			if(b[j]) maxb = j; 	
		}
		res = max(res, maxa * maxb * i);
	}
	cout << res;
}

G 爆米花 — 简单数学签到

总爆米花数为(1+n)*n/2，合并次数为n-1，所以减去n-1即可

#include <iostream>
using namespace std;
signed main()
{
	int n; cin >> n;
	cout << (long long)(n + 1) * n / 2 - (n - 1);
}

H what’s 莫比乌斯最大值—模拟+贪心

每次把问的问题放在哈希表里，问的问题字符串可能是另一个问题的前缀串
因此在处理 回答字符串的时候，直接枚举，贪心找出最长的问题，放到回答问题的哈希表中
然后不断更新

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

signed main()
{
	int n; cin >> n;
	unordered_set<string> ques, ans;
	for(int i = 1; i <= n; i ++)
	{
		string s; cin >> s;
		if(s == "what's") cin >> s, ques.insert(s);
		else
		{
			string tmp = "", maxl = ""; 
			for(int i = 0; i < s.size(); i ++)
			{
				tmp += s[i];
				if(ques.count(tmp) && !ans.count(tmp)) maxl = tmp;
			}
			if(maxl.size()) ans.insert(maxl);
		}
	}
	cout << ans.size();
}

I 神奇的花—大模拟

详细请看代码注释

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define int long long
int st, ed;
int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
vector<int> runy; // 预处理存的闰年
vector<int> set0;// 每次连续两天闭合置零的位置
vector<int> vec;// 下雨天数对应的数字
// 判断是否是闰年
bool is_run(int x) {
	if(x % 400 == 0) return true;
	if((x % 4 == 0) && (x % 100)) return true;
	return false;
}
// 将年月日转换为数字
int cal(int y, int m, int d) {
	auto x = upper_bound(runy.begin(), runy.end(), y - 1);
	// 闰年的天数 
	int runcnt = x - runy.begin();
	int sum = runcnt + (y - 1) * 365;

	if(is_run(y)) mon[2] = 29;
	else mon[2] = 28;
	for(int i = 1; i < m; i ++) sum += mon[i];
	sum += d;
	return sum;
}
//计算出【l, r】这个区间中开放的时间
int cal_day(int l, int r) {
	int ll = l, rr = r;
	int sum = 0;
	// 将左区间不完整7天的地方 更新到完整7天的位置
	while((l % 7) && (l <= r)) {
		sum ++;
		l ++;
	}
	//完整7天，除以7，然后乘6
	int t = (r - l) / 7;
	sum += t * 6;
	//更新到最后一段不完整区间位置
	l += t * 7 + 1;
	// 枚举右区间不完整7天的位置
	for(int i = l; i <= r; i ++)
		if(i % 7) sum ++;
	// 减去 这段时间中包含下雨天数
	for(auto x : vec) if(x >= ll && x <= rr) sum --;
	return sum;
}

signed main() {

	for(int i = 1; i <= 2000000; i ++) if(is_run(i))runy.push_back(i);
	int y, m, d;
	scanf("%lld-%lld-%lld", &y, &m, &d);
	st = cal(y, m, d);
	scanf("%lld-%lld-%lld", &y, &m, &d);
	ed = cal(y, m, d) - st + 1;
	int k;
	cin >> k;
	for(int i = 0; i < k; i ++) {
		scanf("%lld-%lld-%lld", &y, &m, &d);
		vec.push_back(cal(y, m, d) - st + 1);
	}
	st = 1;
	sort(vec.begin(), vec.end());
	// 去除下雨天超过 结束时间的数
	while(vec.back() > ed) vec.pop_back();
	//处理出连续2天需要置零的位置，set0存的是连续天数的第二天
	for(int i = 0; i < vec.size(); i ++) {
		if(i + 1 < vec.size() && vec[i] + 1 == vec[i + 1]) set0.push_back(vec[i + 1]);
		if(vec[i] % 7 == 1) set0.push_back(vec[i]);
		if(vec[i] % 7 == 6) set0.push_back(vec[i] + 1);
	}
	vec.erase(unique(vec.begin(),vec.end()), vec.end());
	sort(set0.begin(), set0.end());
	set0.erase(unique(set0.begin(),set0.end()), set0.end());

	int pre = 1;
	int res = 0;
	for(int i = 0; i < set0.size(); i ++) {
		res = max(res, cal_day(pre, set0[i] - 2));
		pre = set0[i] + 1;
	}
	res = max(res, cal_day(pre, ed));
	cout << res;
}

J 售卖车票—贪心+维护区间

贪心：枚举左端点，对于左端点相同的区间，优先选择右端点比较小的
枚举左端点时维护一个该点被sum个区间占用了，如果sum>k，则从堆里找出右端点最大的去除，直到sum<=k
枚举过l这个左端点后，就可以把以l为右端点区间数的从sum删除掉了，这些区间一定没问题了，加到答案res中
具体看代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define int long long
vector<int> g[200010];
int cnt[200010];
priority_queue<int> q;
signed main() 
{
	int n, m, k; cin >> n >> m >> k;
	for(int i = 1; i <= m; i ++)
	{
		int l, r; cin >> l >> r;
		g[l].push_back(r);		
	} 
	int res = 0, sum = 0;
	for(int l = 1; l <= n; l ++)
	{
		for(auto r : g[l])
		{
			sum ++;
			cnt[r] ++;
			q.push(r);
		}
		while(sum > k)
		{
			cnt[q.top()] --;
			q.pop();
			sum --;
		}
		sum -= cnt[l];
		res += cnt[l];
	}
	cout << res;
}

K Alice and Bob—模拟

有效的距离只有1000，所以先用字符串读入落点，用函数判断是否出靶，如果没出靶就算一下xx+yy
如果都没出靶就比一下xx+yy谁小即可文章来源地址https://www.toymoban.com/news/detail-412208.html

#include <iostream>
#include <cstring>
using namespace std;
#define int long long

bool check(string sx, string sy, int &dis)
{
	if(sx.size() > 6 || sy.size() > 6) return true;
	if(sx[0] == '-') sx = sx.substr(1);
	if(sy[0] == '-') sy = sy.substr(1);
	
	int x = stoi(sx), y = stoi(sy);
	dis = x * x + y * y;
	return dis > 1000000;
}

signed main() 
{
	string x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
	int dis1 = 0, dis2 = 0;
	bool c1 = check(x1, y1, dis1);
	bool c2 = check(x2, y2, dis2);
	if(c1 && c2) cout << "Draw";
	else if(c1) cout << "Bob";
	else if(c2) cout << "Alice";
	else
	{
		if(dis1 == dis2) cout << "Draw";
		else if(dis1 < dis2) cout << "Alice";
		else cout << "Bob";
	}
}

到了这里，关于“卓见杯”郑州轻工业大学第十五届程序设计大赛暨河南省高校邀请赛题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！