2019年山东省大学生程序设计竞赛 补题记录

A - Sekiro（签到 思维）

• 一定能在很有限的次数内变成 0 或 1

#include <bits/stdc++.h>using namespace std;#define int long long
#define double long double
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int maxn = 1e6;
const int MAXN = 1e5 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n, k; cin >> n >> k;while (k -- ){n = (n + 1) / 2;if (n == 1 || n == 0) break;}cout << n << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

B - Median（图论 找前缀后缀）

• 如果 $a$ 比 $b$ 大，就连一条从 $a$ 指向 $b$ 的有向边，如果图中有环肯定不行，没有环就计算每个点前缀有多少个点，后缀有多少个点，前缀后缀都小于 $\frac{n}{2}$ 就可以了

#include <bits/stdc++.h>using namespace std;#define int long long
#define double long double
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int maxn = 1e6;
const int MAXN = 1e5 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n, m; cin >> n >> m;vector<vector<int>> g(n + 1);bool flag = true;for (int i = 1; i <= m; i ++ ){int a, b; cin >> a >> b;if (a == b) flag = false;g[a].push_back(b);}if (!flag){for (int i = 1; i <= n; i ++ ) cout << 0;cout << '\n';return;}vector<int> from(n + 1), pre(n + 1), suf(n + 1);auto bfs = [&](int rt){queue<int> q;q.push(rt);from[rt] = rt;while (q.size()){auto t = q.front();q.pop();for (int i = 0; i < g[t].size(); i ++ ){int j = g[t][i];if (j == rt) return false;if (from[j] == rt) continue;q.push(j);from[j] = rt;pre[j] ++ , suf[rt] ++ ;}}return true;};for (int i = 1; i <= n; i ++ ){if (!bfs(i)){for (int j = 1; j <= n; j ++ ) cout << 0;cout << '\n';return;}}for (int i = 1; i <= n; i ++ ){if (pre[i] <= n / 2 && suf[i] <= n / 2) cout << 1;else cout << 0;}cout << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

C - Tokens on the Segments（贪心 优先队列）

• 从小到大放到优先队列里，记录当前可以选的最小的 $x$，记作 $pos$
• 每次取出队头，看能不能取到 $pos$，不能就把区间更新为 $[pos,r]$（如果不能这样更新肯定就是直接丢掉了），再存到堆里，可以就累加答案，更新 $pos$

#include <bits/stdc++.h>using namespace std;#define int long long
#define double long double
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int maxn = 1e6;
const int MAXN = 1e5 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n; cin >> n;priority_queue<PII, vector<PII>, greater<PII>> pq;for (int i = 0; i < n; i ++ ){int l, r;cin >> l >> r;pq.push({l, r});}int pos = 1;int ans = 0;while (pq.size()){auto t = pq.top();pq.pop();int l = t.first, r = t.second;if (pos > l){l = pos;if (l > r) continue;pq.push({l, r});continue;}else{ans ++ ;pos = l + 1;}}cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

D - Stones in the Bucket（签到 思维）

• 能求出每一堆最后会剩下多少石子，一定是从多的里面拿，那看多了多少就行

#include <bits/stdc++.h>using namespace std;#define int long long
#define double long double
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int maxn = 1e6;
const int MAXN = 1e5 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n; cin >> n;vector<int> a(n + 1);int sum = 0;for (int i = 1; i <= n; i ++ ){cin >> a[i];sum += a[i];}int cnt = sum / n;int more = 0;for (int i = 1; i <= n; i ++ ){if (a[i] > cnt) more += a[i] - cnt;}cout << more << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

E - BaoBao Loves Reading（树状数组）

• 记录每本书上一次看的时间，如果从上一次看到这一次中间书的种类超过 $k$，就需要重新拿回来
• 区间种类数，用树状数组维护
• 最后后缀和计算

#include <bits/stdc++.h>using namespace std;#define int long long
#define double long double
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int maxn = 1e6;
const int MAXN = 100;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;int n, tree[N];int lowbit(int x)
{return x & -x;
}void add(int i, int x)
{while (i < N){tree[i] += x;i += lowbit(i);}
}int prefix_sum(int i)
{int presum = 0;while (i > 0){presum += tree[i];i -= lowbit(i);}return presum;
}int query(int l, int r)
{return prefix_sum(r) - prefix_sum(l - 1);
}void solve()
{cin >> n;for (int i = 0; i < N; i ++ ) tree[i] = 0;vector<int> last(n + 1);vector<int> ans(n + 2);for (int i = 1; i <= n; i ++ ){int x; cin >> x;if (last[x] == 0) ans[n] ++ ;else{int tmp = query(last[x] + 1, i - 1);ans[tmp] ++ ;add(last[x], -1);}add(i, 1);last[x] = i;}for (int i = n; i >= 1; i -- ) ans[i] += ans[i + 1];for (int i = 1; i <= n; i ++ ){cout << ans[i];if (i != n) cout << ' ';}cout << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

F - Game on a Graph（树的边数）

• 图连通至少需要 $n-1$ 条边，然后就没了，这题也太水了

#include <bits/stdc++.h>using namespace std;#define int long long
#define double long double
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int maxn = 1e6;
const int MAXN = 1e5 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int k; cin >> k;string s; cin >> s;s = " " + s;int n, m; cin >> n >> m;for (int i = 1; i <= m; i ++ ){int x; cin >> x >> x;}int pos = m - (n - 2);pos %= k;if (pos == 0) pos = k;if (s[pos] == '1') cout << 2 << '\n';else cout << 1 << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

H - Wandering Robot（思维）

• 最大距离只会出现在第一次循环和最后一次循环

#include <bits/stdc++.h>using namespace std;#define int long long
#define double long double
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int maxn = 1e6;
const int MAXN = 1e5 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n, k; cin >> n >> k;string s;cin >> s;int x = 0, y = 0;vector<PII> maxx(4); // 左上 左下 右上 右下int ans = 0;for (auto t : s){if (t == 'U') y ++ ;else if (t == 'D') y -- ;else if (t == 'L') x -- ;else x ++ ;ans = max(ans, llabs(x) + llabs(y));}x = x * (k - 1);y = y * (k - 1);for (auto t : s){if (t == 'U') y ++ ;else if (t == 'D') y -- ;else if (t == 'L') x -- ;else x ++ ;ans = max(ans, llabs(x) + llabs(y));}cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

K - Happy Equation（数论）

• 打表发现， $a$ 是奇数答案为 $1$ （不会证明）
• $a$ 是偶数的时候：
  • 如果 $x\ge p$，那 $a^x$ 一定有一个因数是 $2^x$，也就一定有一个因数是 $2^p$，所以 $a^x\mathrm{mod}{2}^p=0$，所以现在是要让 $x^a\mathrm{mod}{2}^p=0$，设 $x$ 中有 $k$ 个 $2$，那么 $ka\ge p$，所以 $k\ge \lceil \frac{p}{a}\rceil =k^{\prime }$，也就是在 $[p,2^p]$ 找 $2^{k^{\prime }}$ 的倍数
  • 否则，枚举计算

#include <bits/stdc++.h>using namespace std;#define int long long
#define double long double
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int maxn = 1e6;
const int MAXN = 100;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;int pow(int a, int n, int p)
{int ans = 1;while (n){if (n & 1) ans = ans * a % p;a = a * a % p;n >>= 1;}return ans;
}void solve()
{int a, p; cin >> a >> p;if (a & 1) cout << 1 << '\n';else{int ans = 0;for (int x = 1; x < p; x ++ ){if (pow(a, x, (1 << p)) == pow(x, a, (1 << p))) ans ++ ;}int k = (p + a - 1) / a;ans += (1 << (p - k)) - (p - 1) / (1 << k);cout << ans << '\n';}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

M - Calandar（签到）

• 每月每天的星期都是一样的

#include <bits/stdc++.h>using namespace std;#define int long long
#define double long double
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int maxn = 1e6;
const int MAXN = 1e5 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;string tmp[6] = {"", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"};void solve()
{int a1, a2, a3;string s;cin >> a1 >> a2 >> a3 >> s;int b1, b2, b3;cin >> b1 >> b2 >> b3;int a4;if (s[0] == 'M') a4 = 1;else if (s[0] == 'T' && s[1] == 'u') a4 = 2;else if (s[0] == 'W') a4 = 3;else if (s[0] == 'T' && s[1] == 'h') a4 = 4;else a4 = 5;if (a3 <= b3){while (a3 != b3){a4 ++ ;if (a4 == 6) a4 = 1;a3 ++ ;}}else{while (a3 != b3){a4 -- ;if (a4 == 0) a4 = 5;a3 -- ;}}cout << tmp[a4] << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

L - Flipping Game（dp）

• 先把末尾状态全变成 $0$
• $dp[i][j]$ 表示前 $i$ 个操作后，还有 $j$ 盏灯亮着
• 可以由 $dp[i][j]$，转移第 $i+1$ 个状态，如果在第 $i+1$ 个操作熄灭了 $x$ 盏灯，也就是点亮了 $m-x$ 盏灯
• $dp[i+1][j-x+(m-x)]+=dp[i][j]\times C_j^x\times C_{n-j}^{m-x}$

#include <bits/stdc++.h>using namespace std;#define int long long
#define double long double
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int maxn = 1e6;
const int MAXN = 100;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;int C[110][110];void init()
{for (int i = 0; i <= MAXN; i ++ ){C[i][0] = 1;for (int j = 1; j <= i; j ++ )C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;}
}void solve()
{int n, k, m; cin >> n >> k >> m;string s, t; cin >> s >> t;int cnt = 0;for (int i = 0; i < n; i ++ ){if (t[i] != '0'){t[i] = '0';if (s[i] == '1') s[i] = '0';else s[i] = '1';}if (s[i] != t[i]) cnt ++ ;}vector<vector<int>> dp(k + 1, vector<int>(n + 1));dp[0][cnt] = 1;for (int i = 0; i < k; i ++ ){for (int j = 0; j <= n; j ++ ){for (int x = 0; x <= j && x <= m; x ++ ){if (n - j < m - x) continue;dp[i + 1][j - x + (m - x)] = (dp[i + 1][j - x + (m - x)] + dp[i][j] * C[j][x] % mod * C[n - j][m - x] % mod) % mod;}}}cout << dp[k][0] << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);init();int t = 1;cin >> t;while (t--){solve();}return 0;
}