2024 (ICPC) Jiangxi Provincial 省赛
前言
和队友 vp 7t，赛后补了几题。
A. Maliang Learning Painting
思路
输出 a + b + c
代码
cin>>n>>m>>k;
cout<<n+m+k<<endl;
C. Liar
思路
队友写得
代码
void solve() {
int n,k;
cin>>n>>k;
int ans=0;
vector<int>a(n);
for (int i = 0; i <n ; ++i) {
cin>>a[i];
}
sort(a.begin(), a.end());
for (int i = 0; i <n ; ++i) {
ans+=a[i];
}
if(ans==k)
cout<<n<<endl;
else{
cout<<n-1<<endl;
}
}
D. Magic LCM
思路
数学、质因数分解
考虑 \(a,b\) 互质，则其中一方会变为 \(1\)，另一方变为 \(ab\)；若 \(a＝kx,b=ky\) ，则有一方变为 \(k\)，另一方变为 \(kxy\) ，因为 \(xy＞x+y\)，所以我们应该把质因子尽量地合在一起，且要独立考虑每个质因子的幂次，即将各质因子按幂次从大到小地尽量合，最后就是要么不互质，要么就是 1，所以可以考虑用筛法将质数筛出来，为了降低复杂度，只筛 1e3 以内的，一个小于 1e6 的数不可能产生幂次大于 1 且大于 1e3 的质因子，因此碰到大质数我们直接乘到对应的答案中，小质数需要按照幂次排序再相乘。
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr i64 mod = 998244353;
i64 ksm(i64 x, i64 y) {
i64 res = 1;
while (y) {
if (y & 1) res = res * x % mod;
x = x * x % mod;
y >>= 1;
}
return res;
}
//欧拉函数,质数
vector<int> euler_range(int n) {
vector<int> phi(n + 1), prime;
vector<bool> is_prime(n + 1, true);
is_prime[1] = 0, phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (is_prime[i]) prime.push_back(i), phi[i] = i - 1;
for (int j = 0; j < (int)prime.size() && i * prime[j] <= n; j++) {
is_prime[i * prime[j]] = 0;
if (i % prime[j]) phi[i * prime[j]] = phi[i] * (prime[j] - 1);
else {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
}
}
return prime;
}
constexpr int N = 1e3;
auto pr = euler_range(N);
void solve() {
int n;
cin >> n;
vector<vector<int>> mp(pr.back() + 1);
vector<i64> res(n + 1, 1);
map<int, int> mp2;
int noone = 0, a, cnt = 0;
for (int i = 1; i <= n; i ++) {
cin >> a;
for (auto &j : pr) {
if (a % j == 0) {
cnt = 0;
while (a % j == 0) {
a /= j;
cnt ++;
}
mp[j].emplace_back(cnt);
noone = max(noone, (int)mp[j].size());
}
}
if (a > 1) {
(res[++mp2[a]] *= a) %= mod;
noone = max(noone, mp2[a]);
}
}
i64 ans = n - noone;
for (auto v : pr) {
if (mp[v].size()) {
sort(mp[v].begin(), mp[v].end());
}
}
for (int i = 1; i <= noone; i ++) {
for (auto &v : pr) {
if (mp[v].size()) {
auto mi = mp[v].back();
mp[v].pop_back();
res[i] = res[i] * ksm(v, mi) % mod;
}
}
ans = (ans + res[i]) % mod;
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
E. Magic Subsequence
思路
双向 dfs，三进制枚举（？
注意到一个长度为 n 的正整数序列的子序列的和最多只有 \(2n\) 种，那么取 \(n = 30\)，有 \(2^n > M × n\) 存在，因此本题只需要通过任意 30 个数进行判断。（实际上存在更紧凑的界
对于子集的选取，若有解，一定存在一个子集间互相不交的解，那么 30 个数可以分为三类，属于集合 A 的数，属于集合 B 的数，不在集合中的数。所以可以采用双向 dfs 搜索，不过我这里采取的是三进制枚举，带了个 10 左右的常数，跑满 \(3^{15}\) 会超时，所以只跑了 \(3^{13}\) 和 \(3^{14}\) ，就像上面说的跑不满，选取28会TLE，26会WA，很神奇（，实际写的话还是更推荐 dfs，最后合并的时候可以用归并，也可以哈希一下前半段的和，后半段搜到符合条件的解直接输出即可。
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++)
cin >> a[i];
n = min(n, 27);
int mid = n >> 1;
int end1 = 1;
for (int i = 1; i <= mid ; i ++)
end1 *= 3;
vector<pair<int, int>> pre, suf;
for (int i = 1; i < end1; i ++) {
int sum1 = 0, sum2 = 0;
int x = i;
for (int j = 1; j <= mid; j ++) {
if (x % 3 == 1) sum1 += a[j];
if (x % 3 == 2) sum2 += a[j];
x /= 3;
}
pre.emplace_back(sum1 - sum2, i);
}
int end2 = 1;
for (int i = 1; i <= n - mid; i++)
end2 *= 3;
for (int i = 1; i < end2; i ++) {
int sum1 = 0, sum2 = 0;
int x = i;
for (int j = 1 + mid; j <= n; j ++) {
if (x % 3 == 1) sum2 += a[j];
if (x % 3 == 2) sum1 += a[j];
x /= 3;
}
suf.emplace_back(sum2 - sum1, i);
}
auto print = [ &mid, &n](int pre, int suf)->void{
vector<int> A, B;
for (int i = 1; i <= mid; i ++) {
if (pre % 3 == 1) A.emplace_back(i);
if (pre % 3 == 2) B.emplace_back(i);
pre /= 3;
}
for (int i = 1 + mid; i <= n; i ++) {
if (suf % 3 == 1) A.emplace_back(i);
if (suf % 3 == 2) B.emplace_back(i);
suf /= 3;
}
cout << A.size() << ' ';
for (auto i : A) {
cout << i << " \n"[i == A.back()];
}
cout << B.size() << ' ';
for (auto i : B) {
cout << i << " \n"[i == B.back()];
}
};
sort(pre.begin(), pre.end());
sort(suf.begin(), suf.end());
int l = 0, r = suf.size() - 1;
while (l < pre.size() && r >= 0) {
auto [pv, pst] = pre[l];
auto [sv, sst] = suf[r];
if (pv + sv == 0) {
print(pst, sst);
return;
}
if (pv < -sv) l ++;
else r --;
}
cout << "-1\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
G. Multiples of 5
思路
队友写得，放个官方题解吧
考虑到对每个位的数独立考虑对 5 取模的余数，假设第 i 位的数为 x，它们的贡献为 \((11^i−1 × x) \bmod 5\)。
对连续长度的同一个数的贡献可以等比数列求和，根据实现细节的不同可能需要使用逆元。
注意到 \(11^i\) 的末位均为 1，因此其对 5 取模的结果均为 1，那么所有数位的贡献都是相等的，直接考虑有多少个当前数计算即可。
代码
void solve() {
cin>>n;
char x;
int s=0;
for(int i=1;i<=n;i++){
cin>>a[i];
cin>>x;
int t;
if(x=='A'){
t=x-'A'+10;
}else{
t=x-'0';
}
s+=(t*a[i]%5);
}
if(s%5){
cout<<"No\n";
}else{
cout<<"Yes\n";
}
}
H.Convolution
思路
队友写得，放个官解吧
考虑卷积核 \(K\) 中的每个元素产生贡献。\(K\) 中的每个元素都对应矩阵 \(I\) 中的一个子矩阵。
例如 \(K_{i,j}\) 产生的贡献是 \(K_{i,j}×\) 矩阵 $I_{i,j∼n−k+i,m−l+j} $的子矩阵之和，其中的 \(k, l\) 是卷积核 \(K\) 的长宽。
所以当子矩阵和为负数时，\(K_{i,j}\) 取 −1；子矩阵和为正数时，\(K_{i,j}\) 取 1。快速求出某个子矩阵和可以用二维前缀和来实现。
代码
void solve() {
cin>>n>>m>>k>>l;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
b[i][j]=b[i-1][j]+a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i<=n-k+1)c[i][j]=c[i][j-1]+b[i][j];
else{
c[i][j]=c[i][j-1]+b[i][j]-b[i-(n-k+1)][j];
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(j<=m-l+1)d[i][j]=c[i][j];
else{
d[i][j]=c[i][j]-c[i][j-(m-l+1)];
}
}
}
int ans=0;
for(int i=0;i<k;i++){
for(int j=0;j<l;j++){
ans+=abs(d[i+n-k+1][j+m-l+1]);
}
}
cout<<ans<<endl;
}
I. Neuvillette Circling
思路
计算几何
实际上所有的最小覆盖圆，都是由这 n 个点中的两个点（作为直径时）或者三个点确定。所以只需要 \(n^2 + n^3\) 分别枚举所有圆，并且再分别计算每个圆覆盖了多少点和它的半径。这样就可以维护所有 k 点覆盖圆中最小的半径。总复杂度为 \(O(n^4)\)。
\(n^2\) 两点距离作为直径，中心作为圆心，\(n^3\) 三点求外切圆。
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr double eps = 1e-8; // 根据题目精度要求进行修改
constexpr double PI = acos(-1.0); // pai, 3.1415916....
int sgn(double x) { // 进行判断, 提高精度
if (fabs(x) < eps) return 0; // x == 0, 精度范围内的近似相等
return x > 0 ? 1 : -1; // 返回正负
}
// Need: sgn()
typedef struct Point {
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y) {} // 构造函数, 初始值为 0
// 重载运算符
// 点 - 点 = 向量(向量AB = B - A)
Point operator- (const Point &B) const { return Point(x - B.x, y - B.y); }
// 点 + 点 = 点, 点 + 向量 = 向量, 向量 + 向量 = 向量
Point operator+ (const Point &B) const { return Point(x + B.x, y + B.y); }
// 向量 × 向量 (叉积)
double operator^ (const Point &B) const { return x * B.y - y * B.x; }
// 向量 · 向量 (点积)
double operator* (const Point &B) const { return x * B.x + y * B.y; }
// 点 * 数 = 点, 向量 * 数 = 向量
Point operator* (const double &B) const { return Point(x * B, y * B); }
// 点 / 数 = 点, 向量 / 数 = 向量
Point operator/ (const double &B) const { return Point(x / B, y / B); }
// 判断大小, 一般用于排序
bool operator< (const Point &B) const { return x < B.x || (x == B.x && y < B.y); }
// 判断相等, 点 == 点, 向量 == 向量, 一般用于判断和去重
bool operator== (const Point &B) const { return sgn(x - B.x) == 0 && sgn(y - B.y) == 0; }
// 判断不相等, 点 != 点, 向量 != 向量
bool operator!= (const Point &B) const { return sgn(x - B.x) || sgn(y - B.y); }
} Vector;
// Need: (-, *)
double dist(Point a, Point b) { return sqrt((a - b) * (a - b)); }
// Need: Point()
struct Circle {
Point o;
double r;
Circle(Point _o = Point(), double _r = 0) : o(_o), r(_r) {}
// 圆的面积
double Circle_S() { return PI * r * r; }
// 圆的周长
double circle_C() { return 2 * PI * r; }
};
// Need: sgn(), dist()
// 点在圆上, 返回 0
// 点在圆外, 返回 -1
// 点在圆内, 返回 1
int Point_with_circle(Point p, Circle c) {
double d = dist(p, c.o);
if (sgn(d - c.r) == 0) return 0;
if (sgn(d - c.r) > 0) return -1;
return 1;
}
// Need: dist()
Circle get_circumcircle(Point A, Point B, Point C) {
double Bx = B.x - A.x, By = B.y - A.y;
double Cx = C.x - A.x, Cy = C.y - A.y;
double D = 2 * (Bx * Cy - By * Cx);
double x = (Cy * (Bx * Bx + By * By) - By * (Cx * Cx + Cy * Cy)) / D + A.x;
double y = (Bx * (Cx * Cx + Cy * Cy) - Cx * (Bx * Bx + By * By)) / D + A.y;
Point P(x, y);
return Circle(P, dist(A, P));
}
int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
int n;
scanf("%d", &n);
vector<Vector> p;
for (int i = 1; i <= n; i ++) {
double x, y;
scanf("%lf%lf", &x, &y);
p.emplace_back(x, y);
}
vector<double> ans(n * (n - 1) / 2 + 1, 1e15);
for (int i = 0; i < n; i ++) {
for (int j = i + 1; j < n; j ++) {
Point mid((p[i].x + p[j].x) * 0.5, (p[i].y + p[j].y) * 0.5);
double R = dist(mid, p[i]);
Circle O(mid, R);
int num = 0;
for (int k = 0; k < n; k ++) {
if (Point_with_circle(p[k], O) != -1)num++;
}
int op = num * (num - 1) / 2;
for (int idx = 1; idx <= op; idx ++)
ans[idx] = min(ans[idx], R);
}
}
for (int i = 0; i < n; i ++) {
for (int j = i + 1; j < n; j ++) {
for (int k = j + 1; k < n; k ++) {
Circle O = get_circumcircle(p[i], p[j], p[k]);
int num = 0;
for (int l = 0; l < n; l ++) {
if (Point_with_circle(p[l], O) != -1)
num++;
}
int op = num * (num - 1) / 2;
for (int idx = 1; idx <= op; idx ++)
ans[idx] = min(ans[idx], O.r);
}
}
}
for (int i = 1; i <= n * (n - 1) / 2; i ++) {
printf("%.10lf\n", ans[i]);
}
return 0;
}
J.Magic Mahjong
思路
字符串模拟。
需要注意国士无双是 13 种幺九牌各一张再加上其中任意一张，且牌之间是无序的。
需要注意七对子不能有相同的对子。
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
set<string> Thirteen, seven;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string t = "1p9p1s9s1m9m1z2z3z4z5z6z7z";
for (int i = 0; i < t.size(); i += 2) {
Thirteen.insert(t.substr(i, 2));
}
int n;
cin >> n;
while (n --) {
string s;
cin >> s;
bool f = 1;
set<string> k;
for (int i = 0; i < s.size(); i += 2) {
string p = s.substr(i, 2);
k.insert(p);
if (!Thirteen.count(p)) f = 0;
}
if (f && k.size() == 13) {
cout << "Thirteen Orphans\n";
} else if (k.size() == 7) {
cout << "7 Pairs\n";
} else {
cout << "Otherwise\n";
}
}
return 0;
}
K. Magic Tree
思路
诈骗题。
注意到换行后树实际上截断了，原来一侧的是一条没有选择的链。可以基于这个进行简单的动态规划。
继续观察可以发现，当上次 dfs 时进行了换行后，下一次操作只有一种情况（另一侧延伸是死路），而如果当前没有换行，下一次操作可以选择继续延伸或者不换行。
因为列增加即会导致两种可能，因此方案数为 \(2^{n−1}\)
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr i64 mod = 998244353;
i64 ksm(i64 x, i64 y) {
i64 res = 1;
while (y) {
if (y & 1) res = res * x % mod;
x = x * x % mod;
y >>= 1;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 m;
cin >> m;
cout << ksm(2, m - 1) % mod << '\n';
return 0;
}
L. Campus
思路
最短路
时间段最多只有 \(2k+1\) 个，也就是 15 个互不相交的区间和没有大门开的区间，所以只要对这 k 个大门都做一遍 dijkstra ，然后判断哪些时间段有哪些大门开着即可。
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct DIJ {
using i64 = long long;
using PII = pair<i64, i64>;
vector<i64> dis;
vector<vector<PII>> G;
DIJ() {}
DIJ(int n) {
dis.assign(n + 1, 1e18);
G.resize(n + 1);
}
void add(int u, int v, int w) {
G[u].emplace_back(v, w);
}
void dijkstra(int s) {
priority_queue<PII> que;
dis[s] = 0;
que.push({0, s});
while (!que.empty()) {
auto p = que.top();
que.pop();
int u = p.second;
if (dis[u] < p.first) continue;
for (auto [v, w] : G[u]) {
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
que.push({ -dis[v], v});
}
}
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k, T;
cin >> n >> m >> k >> T;
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++)
cin >> a[i];
vector<DIJ> dij(k, n);
vector<array<int, 3>> door(k);
for (auto &[p, l, r] : door) {
cin >> p >> l >> r;
}
for (int i = 0; i < m; i ++) {
int u, v, w;
cin >> u >> v >> w;
for (int j = 0; j < k; j ++) {
dij[j].add(u, v, w);
dij[j].add(v, u, w);
}
}
for (int i = 0; i < k; i ++) {
dij[i].dijkstra(door[i][0]);
}
vector<i64> dis;
auto res = [&](int x)->i64{
if (!x) return -1;
vector<i64>(n + 1, 1e18).swap(dis);
for (int i = 0; i < k; i ++) {
if (x >> i & 1) {
for (int j = 1; j <= n; j ++) {
dis[j] = min(dis[j], dij[i].dis[j]);
}
}
}
i64 res = 0;
for (int i = 1; i <= n; i ++)
res += a[i] * dis[i];
return res;
};
unordered_map<int, i64> ans;
for (int t = 1; t <= T; t ++) {
int mask = 0;
for (int i = 0; i < k; i ++) {
auto &[p, l, r] = door[i];
if (l <= t && t <= r)
mask |= 1 << i;
}
if (!ans.count(mask)) {
ans[mask] = res(mask);
}
cout << ans[mask] << '\n';
}
return 0;
}