“卓见杯”郑州轻工业大学第十五届程序设计大赛暨河南省高校邀请赛题解
题目链接
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谁小即可
#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";
}
}