2023CCPC东北四省赛题解

K. The Secret Comparison

签到题，比大小。

#include <bits/stdc++.h>
#define x first
#define y second
#define int long longusing namespace std;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int N = 1000010, M = N * 2, mod = 1e9 + 7, P = 131;
int n, a, b, c;void solve()
{int a, b;cin >> a >> b;if (a > b)cout << "orz teralem is the king!";else if (a == b)cout << "even even seven EIeven.";elsecout << "orz overflowker is the king!";
}signed main()
{std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--)solve();return 0;
}

A. Cask Effect

木桶原理，给n块木板从其中一块切下来一段给另一块，最小值最大是多少。
先排序，用最大的给最小的补最优。

#include <bits/stdc++.h>
#define x first
#define y second
#define int long longusing namespace std;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int N = 100010, M = N * 2, mod = 1e9 + 7, P = 131;
int n;
double a[N];void solve()
{cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];sort(a + 1, a + n + 1);if (n == 1){printf("%.1lf\n", a[1]);}else if (n == 2){printf("%.1lf\n", (a[1] + a[2]) / 2.0);}else {if((a[1] + a[n]) >= a[2] * 2) {printf("%.1lf\n", a[2]);}else {printf("%.1lf\n", (a[1] + a[n]) / 2.0);}}
}signed main()
{// std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--)solve();return 0;
}

M. Easy Problem of Prime

$f[i]$表示$i$最少由多少个质数组成，让我们求${\sum }_2^{n}f[i]$。
首先求$f[i]$，如果i是质数，$f[i]=1$，根据哥德巴赫猜想，如果i是偶数，$f[i]=2$，那么如果i是奇数并且不是偶数呢，我们可以把他拆成奇质数+偶数，$f[i]=3$。问题解决，线性筛+前缀和。

#include <bits/stdc++.h>
#define x first
#define y second
#define int long longusing namespace std;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int N = 10000010, M = N * 2, mod = 1e9 + 7, P = 131;
int p[N], cnt, f[N];
bool st[N];void init()
{for (int i = 2; i <= N - 10; i++){if (!st[i])p[cnt++] = i;for (int j = 0; p[j] * i <= N - 10; j++){st[p[j] * i] = true;if (i % p[j] == 0)break;}}for (int i = 2; i <= N - 10; i++){if (!st[i])f[i] = f[i - 1] + 1;else if (i % 2 == 0)f[i] = f[i - 1] + 2;else if (!st[i - 2])f[i] = f[i - 1] + 2;elsef[i] = f[i - 1] + 3;}
}
void solve()
{int x;cin >> x;cout << f[x] << "\n";
}signed main()
{std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t = 1;init();cin >> t;while (t--)solve();return 0;
}

I. Subsetting and Summing

题意是说给n个向量$(x_1,x_2,x_3)$，让你从中选取几个组成新的向量$y=(y_1,y_2,y_3)$，求$|y_1|+|y_2|+|y_3|$的最大值。
看上去毫无头绪，因为我们不知道对于每个向量来说具体每个位置的贡献。但我们可以枚举啊，我们枚举最终答案每一位上的正负情况，这样就可以计算每个向量的贡献了。

#include <bits/stdc++.h>
#define x first
#define y second
#define int long longusing namespace std;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int N = 10000010, M = N * 2, mod = 1e9 + 7, P = 131;
int n;
vector<vector<int>> q;int check(int a, int b, int c)
{int res = 0;vector<int> t;for (int i = 0; i < n; i++){int s = 0;if (a)s += q[i][0];elses -= q[i][0];if (b)s += q[i][1];elses -= q[i][1];if (c)s += q[i][2];elses -= q[i][2];t.push_back(s);}sort(t.begin(), t.end(), greater<int>());for (int i = 0; i < t.size(); i++)if (t[i] > 0)res += t[i];return res;
}
void solve()
{cin >> n ;for (int i = 0; i < n; i++){int x, y, z;cin >> x >> y >> z;q.push_back({x, y, z});}int res = 0;res = max({res, check(1, 1, 1), check(1, 1, 0), check(1, 0, 1), check(0, 1, 1)});res = max({res, check(1, 0, 0), check(0, 1, 0), check(0, 0, 1), check(0, 0, 0)});cout << res << "\n";
}signed main()
{std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--)solve();return 0;
}

H. Light the Street

由数学知识推结论：两个灯中间和两个端点最暗，那么当这两个地方相等的时候最小亮度最高。假设两个灯之间是$x$，端点距离第一个灯是$y$，得到$\frac{2d}{{\frac{x}{2}}^2}=\frac{d}{y^2}$，得到$y=\frac{\sqrt{2}x}{4}$，$(k-1)x+2\ast y=n$。求出$x$后也就能得出亮度了。

#include <bits/stdc++.h>
#define x first
#define y second
#define int long longusing namespace std;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int N = 10000010, M = N * 2, mod = 1e9 + 7, P = 131;
double n, k, d;void solve()
{scanf("%lf%lf%lf", &n, &k, &d);double x = n / (k - 1 + (sqrt(2) / 2.0));double res = 2 * d / ((x / 2.0) * (x / 2.0));printf("%.6lf\n", res);
}signed main()
{// std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--)solve();return 0;
}

G. Expected Sum

递推，最后一位的贡献一定是s[n]，倒数第二位的贡献则可能是$s[n-1]\ast p[n-1]/100+s[n-1]\ast (1-p[n-1])/10$，一步步推就可以发现每一位的贡献，需要注意的时这里有分数需要用到逆元。

#include <bits/stdc++.h>
#define x first
#define y second
#define int long longusing namespace std;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int N = 2000010, M = N * 2, mod = 998244353, P = 131;
int n;
string s;
int p[N];int qmi(int a, int k)
{int res = 1;while (k){if (k & 1)res = res * a % mod;a = a * a % mod;k >>= 1;}return res;
}
void solve()
{cin >> n >> s;s = " " + s;for (int i = 1; i <= n - 1; i++)cin >> p[i];int res = (s[n] - '0'), u = 1;for (int i = n - 1; i >= 1; i--){u = (u * (100 - p[i])) % mod * qmi(10, mod - 2) % mod;u = (u + p[i] * qmi(100, mod - 2) % mod) % mod;res = (res + (s[i] - '0') * u % mod) % mod;}cout << res << "\n";
}signed main()
{// std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--)solve();return 0;
}

D. Concrete Painting

实际上这道题目还是从贡献入手，一段区间对答案的贡献就是$(2^x-1)\ast (2^{n-x})$，x是覆盖这个一段区间的线段数量。只有都不选这段的时候才没有贡献，所以是$(2^x-1)$，选了的情况，只跟不覆盖这段的线段有关，也就是$(2^{n-x})$。方法有了现在只需要离散化+逆元就可以解决。

#include <bits/stdc++.h>
#define x first
#define y second
#define int long longusing namespace std;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int N = 6000010, M = N * 2, mod = 998244353, P = 131;
int n, cnt, res;
vector<PII> q;
int s[N];int qmi(int a, int k)
{int sum = 1;while (k){if (k & 1)sum = sum * a % mod;a = a * a % mod;k >>= 1;}return sum;
}
void solve()
{cin >> n;vector<int> u;for (int i = 1; i <= n; i++){int x, y;cin >> x >> y;q.push_back({x, y});u.push_back(x), u.push_back(y);u.push_back(y + 1);}sort(u.begin(), u.end());map<int, int> mp, ump;for (int i = 0; i < u.size(); i++)if (!mp.count(u[i])){mp[u[i]] = ++cnt;ump[cnt] = u[i];}for (int i = 0; i < n; i++){int l = mp[q[i].x], r = mp[q[i].y];s[l + 1]++, s[r + 1]--;}for (int i = 1; i <= cnt; i++){s[i] += s[i - 1];}for (int i = 2; i <= cnt; i++){int l = ump[i - 1], r = ump[i], x = s[i];// cout << l << " " << r << " " << x << "\n";res = (res + (r - l) * (qmi(2, x) - 1 + mod) % mod * qmi(2, n - x) % mod) % mod;}cout << res << "\n";
}signed main()
{// std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--)solve();return 0;
}

E. Triangle Pick

可以直接暴力搜的，至于判断射线是否与三角相交可以用Möller–Trumbore 算法。

#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
#define double long doubleusing namespace std;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int N = 6000010, M = N * 2, mod = 998244353, P = 131;
int n, m;
struct node
{int x1, x2, x3, y1, y2, y3, z1, z2, z3;
} a[1010];void solve()
{cin >> n >> m;for (int i = 0; i < n; i++){cin >> a[i].x1 >> a[i].y1 >> a[i].z1 >> a[i].x2 >> a[i].y2 >> a[i].z2 >> a[i].x3 >> a[i].y3 >> a[i].z3;}while (m--){int x, y, z;cin >> x >> y >> z;int res = 0;double mx = 1e18;for (int i = 0; i < n; i++){double e1x = a[i].x2 - a[i].x1, e1y = a[i].y2 - a[i].y1, e1z = a[i].z2 - a[i].z1;double e2x = a[i].x3 - a[i].x1, e2y = a[i].y3 - a[i].y1, e2z = a[i].z3 - a[i].z1;double px = y * e2z - z * e2y, py = z * e2x - x * e2z, pz = x * e2y - y * e2x;double det = e1x * px + e1y * py + e1z * pz;if (fabs(det) < 1e-8)continue;double invdet = 1.0 / det;double sx = 0.0 - a[i].x1, sy = 0.0 - a[i].y1, sz = 0.0 - a[i].z1;double u = (sx * px + sy * py + sz * pz) * invdet;if (u < 0.0 || u > 1.0)continue;double qx = sy * e1z - sz * e1y, qy = sz * e1x - sx * e1z, qz = sx * e1y - sy * e1x;double v = (x * qx + y * qy + z * qz) * invdet;if (v < 0.0 || u + v > 1.0)continue;double tval = (e2x * qx + e2y * qy + e2z * qz) * invdet;if (tval > 1e-8 && tval < mx){mx = tval;res = i + 1;}}cout << res << "\n";}
}signed main()
{// std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--)solve();return 0;
}

F. MPFT

大大大大模拟，但我wa了，改了一个多小时，不想写了，代码放这了，等发现了错误或者大佬指正再来改。

#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
#define double long doubleusing namespace std;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int N = 1000010, M = N * 2, mod = 998244353, P = 131;
int n, m, t, k, sum;
int s[N];
bool st[N];void solve()
{cin >> n >> m >> t >> k;priority_queue<PII, vector<PII>, greater<PII>> h;priority_queue<int, vector<int>, greater<int>> p[N];vector<PII> res;while (m--){int ti, pi;cin >> ti >> pi;if (!st[pi]){if (sum == n){while (h.size()){if (!st[h.top().y]){h.pop();continue;}if (s[h.top().y] > 1){s[h.top().y]--;h.pop();}else{st[h.top().y] = 0;while (p[h.top().y].size())p[h.top().y].pop();s[h.top().y] = 0;res.push_back({ti, h.top().y});h.pop();h.push({ti, pi});p[pi].push(ti);s[pi] = 1;st[pi] = 1;break;}}}else{while (p[pi].size() && ti - p[pi].top() > t){p[pi].pop();}if (p[pi].size() + 1 >= k){res.push_back({ti, pi});s[pi] = 0;st[pi] = 0;while (p[pi].size())p[pi].pop();}else{sum++;h.push({ti, pi});p[pi].push(ti);s[pi] = 1;st[pi] = 1;}}}else{while (p[pi].size() && ti - p[pi].top() > t){p[pi].pop();}if (p[pi].size() + 1 >= k){res.push_back({ti, pi});s[pi] = 0;st[pi] = 0;sum--;while (p[pi].size())p[pi].pop();}else{s[pi]++;h.push({ti, pi});p[pi].push(ti);}}}cout << res.size() << " " << sum << "\n";for (int i = 0; i < res.size(); i++){cout << res[i].x << " " << res[i].y << "\n";}for (int i = 1; i <= 1000000; i++)if (st[i])cout << i << " ";
}signed main()
{std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--)solve();return 0;
}