- define时间：
#define itn int
#define int long long
#define ind long double
#define yes cout << "Yes"
#define no cout << "No"
#define pii pair<long long, long long>
#define pci pair<char, int>
#define re return;
QOJ补题：第九届中国大学生程序设计竞赛 秦皇岛站（CCPC 2023 Qinhuangdao Site） - Dashboard - Contest - QOJ.ac
G. Path
签到。
读懂题意容易发现，先往右再往下走即满足条件，所以答案为行间差之和+列间差之和。
void solve()
{cin >> n >> m;num = 0;for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1; i <= m; i++){cin >> b[i];}for (int i = 1; i <= n - 1; i++){num += abs(a[i] - a[i + 1]);}for (int i = 1; i <= m - 1; i++){num += abs(b[i] - b[i + 1]);}cout << num;
}
A. Make SYSU Great Again I
构造。
第 i 行在[ i , i ] [ i , i+1]放入两个相邻的数字，可以保证每行 \(gcd=1\)，注意最后一行特判。
这样第一列是 1 和 n，\(gcd=1\) ；其他列也都是相邻的数字，所以保证每列 \(gcd=1\) 。
多余的数字随便找空位放就行。
void solve()
{cin >> n >> k;x = 1, y = 1;map<pii, int> mp;for (int i = 1; i <= n * 2 - 2; i++) //前n-1行{if (i % 2){cout << x << ' ' << y;mp[{x, y}] = 1;y++;}else{cout << x << ' ' << y;mp[{x, y}] = 1;x++;}cout << '\n';}cout << x << ' ' << y << '\n'; //特判最后一行mp[{x, 1}] = 1;mp[{x, y}] = 1;cout << x << ' ' << 1 << '\n';num = max(k - n * 2, 0ll); //还有多数字的找空随便放for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){if (num == 0){break;}if (!mp[{i, j}]){cout << i << ' ' << j << '\n';mp[{i, j}] = 1;num--;}}}
}J.Keyi LIkes Reading
状压dp。
遍历一遍当前态和期望态，先找到可以通过 i -> j 的情况：如果 i -> j 中所有 i 没有但 j 有的加上还小于 m 就可以转移。
具体可见注释。
void solve()
{cin >> n >> m;int maxn = 0;for (int i = 1; i <= n; i++){cin >> x;maxn = max(maxn, x);a[x - 1]++;}int ans = 0;for (int i = 0; i < maxn; i++) //找出终态{if (a[i])ans |= (1ll << i);}for (int i = 0; i < (1ll << maxn); i++){ // 当前状态for (int j = 0; j < (1ll << maxn); j++){ // 期望状态if ((i & j) != i) // 剪枝，如果当前状态有但期望没有直接下一个continue;int num = 0;bool ok = 1;for (int k = 0; k < maxn; k++){if (!(i & (1ll << k)) && (j & (1ll << k))){ // 如果当前状态没有，但期望有，就加上num += a[k];if (num > m){ok = 0;break;}}}if (ok) //说明这种情况下i->j可以转移{e[i].emplace_back(j);}}}fill(dp, dp + N, INT_MAX);dp[0] = 0;for (int i = 0; i < (1ll << maxn); i++){for (auto j : e[i]){dp[j] = min(dp[j], dp[i] + 1);}}cout << dp[ans];
}
D. Yet Another Coffee
贪心。
首先优惠券可以叠加，并且价钱可以为负值。所以我们可以把所有优惠券都给一个商品。
但是每个优惠券有时间限制，可以想到维护一个前 \(i\) 个商品的最小值。
每次到达时间 \(i\)，我们就把能用的优惠券都给前 \(i\) 个最小的商品。
vector<int> e[N];
void solve()
{cin >> n >> k;for (int i = 1; i <= n; i++){cin >> a[i];e[i].clear();}for (int i = 1; i <= k; i++){cin >> x >> y;e[x].emplace_back(y);}int idx = 1;for (int i = 1; i <= n; i++){if (a[i] < a[idx]) //维护前i个商品的最小值{idx = i;}for (auto j : e[i]) //把所有优惠券给前i个商品的最小值{a[idx] -= j;}}sort(a + 1, a + 1 + n);sum = 0;for (int i = 1; i <= n; i++){sum += a[i];cout << sum << " ";}
}
F. Mystery of Prime
dp。
对不同类型的变化情况考虑，\(dp[i][j]\) 表示第 i 个数状态为 j 情况下的最少转化数。
$dp[i][0] $表示不变 \([1]\) 表示变成1 \([2]\)表示变成偶数 \([3]\)表示变成除1外的奇数
有四种情况：
- 如果当前数不变，依次讨论下一个数的四种情况。
- 如果当前数变成1，对下一个数讨论第1、2、3的情况。
- 如果当前数变成偶数，对下一个数讨论1、2、4的情况。
- 如果当前数变成奇数，对下一个数讨论1、3的情况。
void solve()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1; i <= n; i++){for (int j = 0; j < 4; j++){dp[i][j] = INT_MAX;}}dp[1][0] = 0;dp[1][1] = dp[1][2] = dp[1][3] = 1;auto prime=[&](int x){for (int i = 2; i <= sqrt(x); i++){if (x % i == 0){return 0;}}return 1;};for (int i = 1; i < n; i++){// 1. a[i]不变if (prime(a[i] + a[i + 1])){dp[i + 1][0] = min(dp[i + 1][0], dp[i][0]);}if (prime(a[i] + 1)){dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + 1);}if (a[i] % 2){dp[i + 1][2] = min(dp[i + 1][2], dp[i][0] + 1);}elsedp[i + 1][3] = min(dp[i + 1][3], dp[i][0] + 1);// 2. a[i]变1if (prime(1 + a[i + 1])){dp[i + 1][0] = min(dp[i + 1][0], dp[i][1]);}dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + 1);dp[i + 1][2] = min(dp[i + 1][2], dp[i][1] + 1);// 3. a[i]变偶数if (a[i + 1] % 2) //如果下一个是奇数，自适应变成一个互质的偶数{dp[i + 1][0] = min(dp[i + 1][0], dp[i][2]);}dp[i + 1][1] = min(dp[i + 1][1], dp[i][2] + 1);dp[i + 1][3] = min(dp[i + 1][3], dp[i][2] + 1);// 4. a[i]变除1外的奇数if (a[i + 1] % 2 == 0) //同上，自适应变成一个互质的奇数{dp[i + 1][0] = min(dp[i + 1][0], dp[i][3]);}dp[i + 1][2] = min(dp[i + 1][2], dp[i][3] + 1);}cout << min({dp[n][0], dp[n][1], dp[n][2], dp[n][3]}) << ' ';
}