2024icpc南京站

$2024icpc南京站$

官方题解：2023 ICPC 亚洲区域赛南京站 - SUA Wiki

C. Primitive Root

题意

给定质数$P$和非负整数$m$，有多少非负整数$g$满足$ g≤m ~&&~ g⊕(P−1)≡1 (mod P)$？这里 $\oplus$是按位异或（XOR） 运算符。

思路

跟据题目给出的公式，我们可以做以下变形：
$$\begin{gathered} g\oplus (P-1)\equiv 1(modP) \\ g\oplus (P-1)=kP+1 \\ g=(kP+1)\oplus (P-1)\le m \\ (kP+1)+(P-1)\le m \\ (k+1)p\le m \end{gathered}$$
那么对于区间$0\le k\le \lfloor \frac{m}{p}\rfloor -1$，均有$ (kP+1)+(P-1)\le (k+1)P \le m$，满足要求。

对于所有$k\le \lceil \frac{m}{P}\rceil +1$，均有$ (kP+1)+(P-1)\ge (k-1)P + 2 \le m$，不满足要求。

因此我们只需要检查区间$\lfloor \frac{m}{p}\rfloor \le k\le \lceil \frac{m}{p}\rceil$的值即可。

标程

#define int long long 
using namespace std;
void solve() {int p,m;cin >> p >> m;int ans = (m/p);
//	cout << ans << endl;for(int i = m/p; i <= m / p +1; i ++)if(((1 + i * p) ^ (p-1)) <= m)ans++;cout << ans << endl; 
}

F. Equivalent Rewriting

题意

题目首先给出两个数字n,m，分别表示操作次数和数组长度。然后下列操作是对数组进行操作。

• $p{a}_1{a}_2{a}_3...a_p$

若当前为第$i$次操作，那么该操作为将数组中$a_1,a_2,a_3,...,a_p$全部变为$i$。

经过若干次这样的操作之后，得到数组的最后状态。题目要求能够改变操作的顺序，使得最终数组的结果不变。

思路

本题需要考虑是否存在某一个操作可以改变顺序。我们可以发现，当前操作结果可能会被后续操作覆盖，并且分为三种情况：

• 当前的操作结果会部分被后续操作影响。
• 当前的操作结果会全部被后续操作。
• 当前的操作结果不会被后续操作影响。

特别地对于后两种情况，可以分开讨论：

• 某一次操作不会收到后续操作的影响，可将其放置在其后任意一个位置（最后一次操作除外）。
• 某一次操作会被后续操作全部覆盖，那么可将其放置在其前面任意一个位置（第一次操作除外）。

事实上由于是可以选任意位置，我们只需要将其与相邻位置交换即可。

标程

#define int long long
void solve() {int n, m; cin >> n >> m;vector<vector<int>> op(n + 1);for(int i = 1; i <= n; i ++ ) {int x; cin >> x;while(x -- ) {int pos; cin >> pos;op[i].push_back(pos);}}vector<bool> st(m + 1);vector<int> cnt(m + 1);for(auto t : op[n]) cnt[t] ++ ;bool flag = false;for(int i = n - 1; i >= 1; i -- ) {bool flag = true;for(auto t : op[i]) {if(st[t]) continue;cnt[t] ++ ;if(cnt[t] > 1) flag = false;}for(auto t : op[i + 1]) {if(st[t]) continue;cnt[t] -- ; st[t] = true;}if(flag) {cout << "Yes\n";for (int j = 1; j <= i - 1; j ++ ) cout << j << ' ';cout << i + 1 << ' ' << i;for (int j = i + 2; j <= n; j ++ ) cout << ' ' << j;cout << '\n';return;}}cout << "No\n";
}

G. Knapsack

题意

给定$n$件物品的体积$w_i$与价值$v_i$，以及背包的总容量$W$。

你可以优先选择$k$件物品获得他们的价值，随后再选择一些物品，要求随后选择的物品的体积之和不超过`$W$。

最大化选择物品的价值之和。

思路

注意到一定存在一个最优选法同时满足以下两个条件：

1. 如果存在物品$a,b$满足 𝑎 被免费选走，$b$被付费选走，那么$w_a\ge w_b$。否则我们可以改成免费选$b$，付费选 $a$，方案不会变劣。
2. 如果存在物品$a,b$满足$a$被免费选走，$b$没有被选走，那么$v_a\ge v_b$。否则我们可以改成免费选$b$，不选择$a$，方案不会变劣。

因此，如果我们将所有物品按照$w_i$从小到大排序，那么对于最优策略而言，一定存在一个分界点 $M$，满足$i>M$的物品中，价值前$k$大的物品被免费选走。

对于每个$i$，可以通过维护一个堆来预处理出从第$i$个物品开始的后缀免费选出 $k$个物品的最大价值之和。

因此我们只需要对每个前缀维护出 0/1 背包的结果即可。复杂度$O(nw+nk+nlogn)$。

标程

#define int long long 
#define PII pair<int, int>
#define fi first 
#define se secondconst int INF = 0x7fffffff;void Solved() {int n, w, k; cin >> n >> w >> k;vector<PII> a(n);vector<int> f(w + 1), g(n + 1);// f[i]：计算背包问题的滚动数组// g[i]：从第 i 个物品开始的后缀免费选出 K 个物品的最大价值之和priority_queue<int, vector<int>, greater<int>> q;for(auto &[i, j] : a) cin >> i >> j;sort(ALL(a));int sum = 0;g[n] = 0;// 计算出后缀选出的免费物品的最大价值之和for(int i = n - 1; i >= 0; i -- ) {q.push(a[i].se);sum += a[i].se;if(q.size() > k) {sum -= q.top();q.pop();}g[i] = sum;}for(int i = 0; i <= w; i ++ ) f[i] = -INF;f[0] = 0;int res = g[0]; // 结果初值，只买免费物品// 01背包模板for(int i = 0; i < n; i ++ ) {for(int j = w; j >= a[i].fi; j -- ) {f[j] = max(f[j], f[j - a[i].fi] + a[i].se);res = max(res, f[j] + g[i + 1]);    // 计算在分界点i时的情况}}cout << res << endl;
}

I. Counter

题意

有一个计数器，一开始是0，有两种操作，每次操作可以把值+1或清零。

给若干已知条件表示第$x_i$次操作后计数器的值为$v_i$，问是否有一种操作序列满足所有的已知条件。

思路

根据题目的性质，对于已知的操作，分为两种情况：计数器的值是否为0。

同时可以发现，对于某一次操作，若$v_i=5$，那么$x_i$前（包括$x_i$）会有连续5次的+1操作。

那么，若已知的操作中有不符合上述情况的，这个操作序列肯定就不合法。因此可以按照$x_i$排序，然后从后向前遍历。

遍历过程中标记当前位置的+1操作是从哪个位置开始的，然后遍历过程中对于不合法的情况就直接结束即可，对于不合法的情况：

• $v_i=0$
  • $x_i>x$
• $v_i!=0$
  • $x_i=t$
  • $x_i>t\&\&v_i!=x_i-t$
  • 否则为合法，更新标记位置$t$。

标程

#define PII pair<int,int>
#define pb push_back
#define fi first
#define se secondvoid solve() {int n, m; cin >> n >> m;vector<PII> v(m);for(auto &[i, j] : v) cin >> i >> j;sort(v.begin(), v.end());int x = n + 1;for(int i = m - 1; i >= 0; i -- ) {if(v[i].se == 0) {if(v[i].fi > x) {cout << "No\n"; return;}} else {if(v[i].fi == x) {cout << "No\n"; return;}else if(v[i].fi > x) {if(v[i].se != v[i].fi - x) {cout << "No\n"; return;}} else {x = v[i].fi - v[i].se;if(x < 0) {cout << "No\n"; return;}}}}cout << "Yes\n";
}