2024-10-07 17:53 沈阳化工大学算法工程师发布于辽宁

关注

沈阳化工大学第十一届程序设计竞赛专业组题解

题目难度排序：

⭐ $A$

⭐⭐ $B$

⭐⭐⭐ $C, D, H$

⭐⭐⭐⭐ $F$

⭐⭐⭐⭐⭐ $E, G$

A. 转"人工"

根据题意模拟即可。

#include <iostream>

using namespace std;
int main() {
    string s;
    cin >> s;
    cout << s.back() << "模式";
    return 0;
}

B.马弓手关羽请战华雄

考虑倒着做。

用cnt来记录当前走了多少区块，每当 $a_i \geq 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.整整齐齐

思路：贪心+思维

先对左端点进行排序,枚举左端点 $L$ ，每次优先处理 $R$ 最小的书，一直向后放置，直到下一个 $L$ 的时候停止, 这个过程我们可以用一个小根堆进行维护；

即：

先对左端点排序，然后把同一个左端点的右端点都丢进去小根堆，然后尽可能多的放置右端点更小的书，若没有放置完的，保留在小根堆里等待下一个左端点。

因为是在下一个左端点处理上一个左端点，所以我们要在最后加入一个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个， $a_i$ 也不超过300，可以想到300以内质数的数量一定很少，不超过70个；

区间欧拉函数就是区间积，很明显可以用线段树维护 。把欧拉函数看成两部分相乘，一个是 $x$ 本身，一个是 $x$ 包含的所有质因子项的乘积，我们线段树维护的节点有两个信息，一个是区间乘积，一个是区间包含的质因子，后者用状压，用一个longlong的变量保存。
质因子项我们可以预处理+逆元得到，用 $f[i]$ 表示第i个质数 $p[i]$ 的 $(p[i]-1)/p[i] % mod$ ;

#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.寻宝

首先解决第一个问题，如何求最长回文子串？

可以发现，字符串很长，想到解决这个问题，我们需要一个算法：马拉车算法。

使用马拉车后，我们便可以求出 $m$ 的大小。

然后，我们先考虑如果在数组中选择不超过 $m$ 个宝物的最大价值。

$dp[i]$ 表示：以 $i$ 为右端点，长度不超过 $m$ 的连续子区间的最大总和

那么易知： $dp[i] = max\left\{s_{i}- s_{j}\right\} (1 \leq i - j \leq m)$ 其中 $s_i$ 表示前缀和

观察转移方程： $s_i$ 是常量，则 $dp[i] = s_i - min \left\{ s_{j} \right\} (1 \leq i - j \leq m)$

因此发现我们需要动态去找一个区间中的最小值，我们便考虑滑动窗口维护DP

最后期望只需要 $max\left\{dp_i\right\}(1 \leq i \leq n) · inv(k)$ 即可注意取模。

#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

考点：圆方树

首先要求找到 $A\rightarrow C$ 的任意简单路径。对于经过的每一个点双联通分量，如果 $B$ 在此点双内，则必然存在 $A\rightarrow B \rightarrow C$ 的简单路径；

如果 $B$ 不属于任一经过的点双，则不可能存在 $A\rightarrow B \rightarrow C$ 的简单路径；

因此，我们可以使用 $Tarjan$ 算法构造原图的圆方树 $G$ 来解决此问题。

则：

在 $G$ 上找到 $A \rightarrow C$ 的唯一简单路径。对于每一个方点，如果 $B$ 是与其相邻的圆点，则必然存在 $A \rightarrow B \rightarrow C$ 的简单路径；

如果 $B$ 不与任一经过的方点相邻，则不可能存在 $A \rightarrow B \rightarrow C$ 的简单路径；

#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;
}