沈阳化工大学第十一届程序设计竞赛专业组题解
沈阳化工大学第十一届程序设计竞赛专业组题解
题目难度排序：
⭐
⭐⭐
⭐⭐⭐
⭐⭐⭐⭐
⭐⭐⭐⭐⭐
A. 转"人工"
根据题意模拟即可。
#include <iostream>
using namespace std;
int main() {
string s;
cin >> s;
cout << s.back() << "模式";
return 0;
}
B.马弓手关羽请战华雄
考虑倒着做。
用cnt来记录当前走了多少区块，每当 , cnt便可重新置0。
最后看cnt 是否大于0即可。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int cnt = 0;
for (int i = n - 1; i >= 1; i--) {
cnt++;
if (a[i] >= cnt) cnt = 0;
}
cout << (cnt ? "NO" : "YES");
return 0;
}
C.整整齐齐
思路：贪心+思维
先对左端点进行排序,枚举左端点，每次优先处理
最小的书，一直向后放置，直到下一个
的时候停止, 这个过程我们可以用一个小根堆进行维护；
即：
先对左端点排序，然后把同一个左端点的右端点都丢进去小根堆，然后尽可能多的放置右端点更小的书，若没有放置完的，保留在小根堆里等待下一个左端点。
因为是在下一个左端点处理上一个左端点，所以我们要在最后加入一个inf来处理最后一个左端点。
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define int long long
using namespace std;
using PII = pair<int, int>;
const int inf = 2e9 + 1;
void solve() {
int n;
cin >> n;
vector<PII> v(n);
for(int i = 0; i < n; i ++) {
cin >> v[i].first >> v[i].second;
}
sort(v.begin(), v.end());
v.push_back({inf, inf});
priority_queue<int, vector<int>, greater<int> > q;
int ok = 1;
int pos = -1;
for(auto [l, r] : v) {
if(pos == l) {
q.push(r);
} else {
while(pos < l && q.size()) {
auto t = q.top();
q.pop();
if(pos <= t){
pos ++;
} else {
ok = 0;
}
}
pos = l;
q.push(r);
}
}
if(ok) {
cout << "Yes\n";
}
else {
cout << "No\n";
}
return;
}
signed main() {
int T = 1;
cin >> T;
while(T --){
solve();
}
return 0;
}
D.凿冰 Action
最优决策问题。
可以发现小A和小B永远按照最优决策来选择冰块。
显然两人会采取这样的策略：对于每一根冰柱，保护属于自己容易取到的那一半不被对方取走。
即：谁都不放弃自己的价值高的冰块，就导致小A和小B能且只能拿到离自己近的冰块
Last：
对于有偶数个冰块的冰柱：小A、小B各拿一半，答案加上这些冰块的价值即可
那么如果冰块数是奇数的冰柱，那么中间那一块，就会陷入两难的境地。
所以我们考虑把中间的冰块价值差入一个大根堆中，两人轮流取最大值，这样就能保证两人所得分数最大。
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
int n;
cin >> n;
int ans1 = 0, ans2 = 0;
priority_queue<int> q; // 大根堆
for (int i = 0; i < n; i ++ ) {
int k ;
cin >> k;
if (k % 2 == 0) { // 对半取
for (int j = 1, x; j <= k; j ++) {
cin >> x;
if (j > (k / 2)) {
ans2 += x;
} else {
ans1 += x;
}
}
} else { //中间的插入堆中
for (int j = 1, x; j <= k; j ++ ) {
cin >> x;
if (j == (k / 2 + 1)) {
q.push(x);
} else if (j <= k / 2) {
ans1 += x;
} else {
ans2 += x;
}
}
}
}
int ok = 0;
while (q.size()) {
if (!ok) {
ans1 += q.top();
q.pop();
ok ^= 1;
} else {
ans2 += q.top();
q.pop();
ok ^= 1;
}
}
cout << ans1 << " " << ans2 << "\n";
return 0;
}
E.城中分支
首先发现序列数不多，不超过300个，也不超过300，可以想到300以内质数的数量一定很少，不超过70个；
- 区间欧拉函数就是区间积，很明显可以用线段树维护 。把欧拉函数看成两部分相乘，一个是
本身，一个是
- 质因子项我们可以预处理+逆元得到，用
表示第i个质数
的
;
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using PII = pair<i64, i64>;
#define lc rt << 1
#define rc rt << 1 | 1
const int MAXN = 4e5 + 10;
const int maxx = 40;
const int mod = 1e9 + 7;
//给定序列 初始值不超过300 区间乘 查询区间积的欧拉函数
//维护区间积以及区间积的质因子状态
//用线段树 欧拉函数根据公式计算 由于涉及取模 需要记录质因子 预处理每个质因子乘积项
i64 tree[MAXN << 2],has[MAXN << 2]; //区间积 区间质因子状态
i64 tag1[MAXN << 2],tag2[MAXN << 2]; //乘积的懒标记 乘积质因子懒标记
i64 sta[305]; //数i的质因子压缩状态 右边第一位是第一个质数2
int pri[65], tot = 0; //质数表
bool vis[305];
i64 f[65]; //预处理质因子项
i64 inv[305]; //逆元
void init() {
for (int i = 2; i <= 300; i ++) {
if (!vis[i]) pri[++ tot] = i;
for (int j = 1;j <= tot && i * pri[j] <= 300; j ++) {
vis[i * pri[j]] = 1;
if(i % pri[j] == 0) break;
}
}
for (int i = 2; i <= 300; i ++) {
//i的每个质因子都压缩成二进制状态 右边第一个位置对应质数2
for(int j = 1; j <= tot; j ++) {
if(i % pri[j] == 0) sta[i] |= 1LL << (j - 1); //注意LL
}
}
inv[1] = 1;
for (int i = 2; i <= 300; i ++) {
inv[i] = mod - 1LL * (mod / i) * inv[mod % i] % mod;
}
for (int i = 1; i <= tot; i ++) {
f[i] = inv[pri[i]] * (pri[i] - 1) % mod; //预处理 方便计算欧拉函数
}
}
void pushup(int rt) { //合并区间信息
tree[rt] = tree[lc] * tree[rc] % mod;
has[rt] = has[lc] | has[rc];
}
void build(int rt,int l,int r) {
tag1[rt] = 1; //乘标记
tag2[rt] = 0; //质因子标记 这个区间乘的数包括哪些质因子 状压
if(l == r) {
scanf("%d", &tree[rt]);
has[rt] = sta[tree[rt]];
return;
}
int mid = l + r >> 1;
build(lc, l, mid);
build(rc, mid + 1, r);
pushup(rt);
}
i64 qpow(i64 a,int b) {
i64 ans = 1;
while (b) {
if (b & 1) {
ans = ans * a % mod;
}
a = a * a % mod;
b >>= 1;
}
return ans;
}
void change(int rt, int len, i64 v, i64 y) { //区间每个数乘v 更新区间乘积以及质因子状态
tree[rt] = qpow(v, len) * tree[rt] % mod;
has[rt] |= y;
tag1[rt] = tag1[rt] * v % mod;
tag2[rt] |= y;
}
void pushdown(int rt,int l, int r) {
if(!tag2[rt]) return; //这个区间没有乘过
int mid = l + r >> 1;
change(lc, mid - l + 1, tag1[rt], tag2[rt]);
change(rc, r - mid, tag1[rt], tag2[rt]);
//下传完 标记初始化
tag1[rt] = 1;
tag2[rt] = 0;
}
void updata(int rt, int l, int r, int v, int vl, int vr) { //[vl,vr]每个数乘v
if(vl > r || vr < l ) return;
if(vl <= l && r <= vr) {
change(rt,r - l + 1, v, sta[v]);
return;
}
int mid = l + r >> 1;
pushdown(rt, l, r);
updata(lc, l, mid, v, vl, vr);
updata(rc, mid + 1, r, v, vl, vr);
pushup(rt);
}
PII hb(PII a, PII b) {
a.first = a.first * b.first % mod;
a.second |= b.second;
return a;
}
//返回[vl,vr]区间积以及质因子状态
PII query(int rt,int l,int r,int vl,int vr) {
if(vl <= l && r <= vr) {
return make_pair(tree[rt], has[rt]);
}
int mid = l + r >> 1;
pushdown(rt, l, r);
if(vr <= mid) return query(lc, l, mid, vl, vr);
else if(vl > mid) return query(rc, mid + 1, r, vl, vr);
return hb(query(lc, l, mid, vl, vr), query(rc, mid + 1, r, vl, vr));
}
int n, m;
int main() {
init();
scanf("%d%d", &n, &m);
build(1, 1, n);
char op[15];
int l, r, v;
while(m --) {
scanf("%s%d%d",op, &l, &r);
if(op[0] == 'Q') {
PII t = query(1, 1, n, l, r);
for (int i = 1; i <= tot; i ++) {
if(t.second & (1LL << (i - 1)))
t.first = (t.first * f[i]) % mod;
}
printf("%lld\n", t.first);
}
else
{
scanf("%d", &v);
updata(1, 1, n, v, l, r);
}
}
return 0;
}
F.寻宝
首先解决第一个问题，如何求最长回文子串？
可以发现，字符串很长，想到解决这个问题，我们需要一个算法：马拉车算法。
使用马拉车后，我们便可以求出的大小。
然后，我们先考虑如果在数组中选择不超过个宝物的最大价值。
表示：以
为右端点，长度不超过
的连续子区间的最大总和
那么易知： 其中
表示前缀和
观察转移方程： 是常量，则
因此发现我们需要 动态去找一个区间中的最小值，我们便考虑滑动窗口维护DP
最后期望只需要 即可 注意取模。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 998244353;
int a[N], sum[N];
struct Manacher { // 马拉车算法
string s;
Manacher(string str) {
s = str;
}
int get_len() { // 获得最长回文子串
string b;
b += "$#";
for (int i = 0; i < s.size(); i ++) {
b += s[i];
b += '#';
}
b += '^';
int len = b.size();
vector<int> p(len + 1);
int mr = 0, mid = 0;
for (int i = 0; i < len; i ++) {
if (i < mr) {
p[i] = min(p[2 * mid - i], mr - i);
} else {
p[i] = 1;
}
while (b[i - p[i]] == b[i + p[i]]) {
p[i] ++;
}
if (i + p[i] > mr) {
mr = i + p[i];
mid = i;
}
}
int res = 0;
for(int i = 0; i < len; i ++) {
res = max(res, p[i]);
}
return res - 1;
}
};
int qmi(int a, int b) {
int res = 1;
while (b) {
if (b & 1) {
res = res * a % mod;
}
a = a * a % mod;
b >>= 1;
}
return res;
}
signed main() {
int len, n, k;
cin >> len >> n >> k;
string s;
cin >> s;
Manacher str(s); // 马拉车算法
int m = str.get_len();
for (int i = 1; i <= n; i ++) {
cin >> a[i];
sum[i] = (sum[i - 1] + a[i]); // 前缀和
}
vector<int> dp(n + 1, -1e18); // dp
deque<int> q;
q.push_back(0);
for (int i = 1; i <= n; i ++) { // 滑动窗口
while (q.size() && i - m > q[0]) {
q.pop_front();
}
dp[i] = max(dp[i], sum[i] - sum[q[0]]);
while (q.size() && sum[q.back()] >= sum[i]) {
q.pop_back();
}
q.push_back(i);
}
int ans = -1e18;
for (int i = 1; i <= n; i ++) {
ans = max(ans, dp[i]);
}
ans = max(ans, 0ll);
cout << ans * qmi(k, mod - 2) % mod << "\n";
return 0;
}
G.寻宝II
考点：圆方树
首先要求找到 的任意简单路径。对于经过的每一个点双联通分量，如果
在此点双内，则必然存在
的简单路径；
如果不属于任一经过的点双，则不可能存在
的简单路径；
因此，我们可以使用算法构造原图的圆方树
来解决此问题。
则：
在上找到
的唯一简单路径。对于每一个方点，如果
是与其相邻的圆点，则必然存在
的简单路径；
如果不与任一经过的方点相邻，则不可能存在
的简单路径；
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 2e5 + 10;
void chmin(int& x, int y) {
if(y < x) x = y;
}
vector<int> edge[MAXN], T[MAXN << 1];
void add_edge(vector<int>* V, int x, int y) {
V[x].push_back(y);
V[y].push_back(x);
}
int dfc, dfn[MAXN], low[MAXN], top, st[MAXN], cnt;
void tarjan(int v) { // 构造圆方树
low[v] = dfn[v] = ++ dfc;
st[++ top] = v;
for(int u: edge[v]) {
if(!dfn[u]) {
tarjan(u);
chmin(low[v], low[u]);
if(low[u] == dfn[v]) {
add_edge(T, v, ++cnt);
do {
add_edge(T, st[top], cnt);
} while(st[top--] != u);
}
} else chmin(low[v], dfn[u]);
}
}
int n, m, a, b, c, ct[MAXN << 1];
void dfs(int v, int par) {
if(v > n) {
for(int u: T[v]) {
ct[u] ++;
}
}
if(v == c) {
cout << (ct[b] ? "Yes\n" : "No\n");
exit(0);
}
for(int u: T[v]) {
if(u != par) {
dfs(u, v);
}
}
if(v > n) {
for(int u: T[v]) {
ct[u] --;
}
}
}
int main() {
cin >> n >> m >> a >> b >> c;
while (m --) {
int x, y;
cin >> x >> y;
add_edge(edge, x, y);
}
cnt = n;
tarjan(1);
dfs(a, -1);
return 0;
}
H.关键学生
考点：并查集。
可以发现，如果按顺序暴力维护每次老师抓走后学生中帮派数，会超时。
我们考虑在所有具有关系的同学对中，所有会被老师抓走的学生先不进行合并，那么最后帮派的数量就是老师抓走所有人之后的帮派数量。
然后我们倒着做，每次将与当前抓走学生有关系的所以学生进行合并，维护并查集，从而便可以快速得到帮派数量。
tip：将所有姓名用数字表示便可以使用普通并查集， 也可以使用字符串并查集。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using PII = pair<string, string>;
constexpr int N = 4e5 + 10;
int n, m;
map<string, string> p; // 字符串并查集
map<string, vector<string>> g; // 存放跟某个学生有关系的所有学生
string find(string x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i ++) {
string s;
cin >> s;
p[s] = s;
}
vector<PII> adj; // 存放所有学生关系对
for (int i = 0; i < m; i ++) {
string a, b;
cin >> a >> b;
adj.push_back({a, b});
g[a].push_back(b);
g[b].push_back(a);
}
int k;
cin >> k;
vector<string> op(N); // 存放被抓学生姓名
map<string, int> vis; // 存放学生是否被抓
for (int i = 1; i <= k; i ++) {
cin >> op[i];
vis[op[i]] = 1;
}
int ans = n - k;
for (auto [a, b] : adj) { // 将没有被抓的学生进行合并
if (vis.count(a) || vis.count(b)) {
continue;
}
string pa = find(a), pb = find(b);
if (pa != pb) {
p[pa] = pb;
ans --;
}
}
vector<int> cnt(N);
for (int i = k; i >= 1; i --) { // 倒着做
cnt[i] = ans;
set<string> s;
for (auto v : g[op[i]]) {
if (!vis.count(v)) {
s.insert(find(v));
string pa = find(op[i]), pb = find(v);
if (pa != pb) {
p[pa] = pb;
}
}
}
ans -= (int)(s.size()) - 1;
vis.erase(op[i]);
}
cnt[0] = ans;
for (int i = 0; i <= k; i ++) {
cout << cnt[i] << "\n";
}
return 0;
}