在福州做网站,网页制作的教程视频,成都比较好的网站设计公司,网站站群Problem A. Diverse Game
Statement
给定 n m n\times m nm 的矩形 a a a#xff0c; a a a 中的每一个数均在 1 ∼ n m 1\sim nm 1∼nm 之间且互不相同。求出 n m n\times m nm 的矩形 b b b#xff0c; b b b 中的每一个数均在 1 ∼ n m 1\sim nm 1∼nm 之间且互…Problem A. Diverse Game
Statement
给定 n × m n\times m n×m 的矩形 a a a a a a 中的每一个数均在 1 ∼ n m 1\sim nm 1∼nm 之间且互不相同。求出 n × m n\times m n×m 的矩形 b b b b b b 中的每一个数均在 1 ∼ n m 1\sim nm 1∼nm 之间且互不相同同时 a i , j ≠ b i , j a_{i,j}\ne b_{i,j} ai,jbi,j。
Solution
注意到 a a a 如果拉长为一个序列则是一个长为 n m nm nm 的排列。故如果直接翻转 a a a则长度为偶数的时候是可行的长度为奇数的时候中间的位置没变只需将第一个位置与中间的位置交换即可。
Code
void solve() {int n, m, x;cin n m;std::vectorint opt;for (int i 1; i n * m; i ) cin x, opt.push_back(x);if (n * m 1) {cout -1 endl;return;}reverse(opt.begin(), opt.end());if (opt.size() 1) swap(opt[0], opt[opt.size() / 2]);for (int i 1; i n * m; i ) {cout opt[i - 1] ;if (i % m 0) cout endl;}
}Problem B. Fun Game
Statement
给定一个长为 n n n 的二进制序列接下来可以进行无限次操作
选择 l , r l,r l,r将 s i s_i si 变为 s i − l 1 ⊕ s i s_{i-l1}\oplus s_i si−l1⊕si。
确定是否能从 s s s 序列变为 t t t 序列。
Solution
考察 s s s 中第一个出现 1 1 1 的位置那么后面需要翻转的位置一定可以通过这个 1 1 1 来翻转状态。形式化的若需要变换的位置为 i i i第一次出现的位置为 j j j则选择区间 l i − j 1 , r i li-j1,ri li−j1,ri 即可在不改变其他位置的前提下因为 j j j 前面全为 0 0 0翻转 i i i 位置。最后 j j j 位置自己异或自己即可。
但是如果前面存在 i i i使得 s i 0 , t i 1 s_i0,t_i1 si0,ti1则必然不存在方案输出 NO反之输出 YES。
Code
void solve() {int n;string s, t;cin n s t;bool ok 0;for (int i 0; i n; i ) {if (s[i] 0 t[i] 1) {cout NO endl;return;}if (s[i] 1) {cout YES endl;return;}}cout YES endl;
}Problem C. Hungry Games
Statement
给定长为 n n n 的序列 a a a 以及变量 g g g初始为 0 0 0选择 l , r l,r l,r依次遍历 l ∼ r l\sim r l∼r 中的每一个数 g g a i gga_i ggai若 g x gx gx则令 g 0 g0 g0。问存在多少个 l , r l,r l,r 使得最终 g g g 的值不为 0 0 0。
Solution
考虑枚举每一个 l l l那么第一个使得 g g g 变 0 0 0 的位置可以轻松通过二分得出令其为 k k k则 l ∼ k − 1 l\sim k-1 l∼k−1 的位置均可以作为右端点。那么 k 1 ∼ n k1\sim n k1∼n 有哪些位置可以作为右端点呢注意到 k k k 位置 g g g 变 0 0 0即和 l ′ k lk l′k 时初始状态时相同的也就是 l ′ k lk l′k 的所有可行的右端点 l l l 位置均可以。
故列出转移方程 f l f k ( k − l ) f_lf_k(k-l) flfk(k−l)。时间复杂度 O ( n log n ) O(n\log n) O(nlogn) log \log log 来源于找 k k k。
Code
void solve() {cin n x;for (int i 1; i n; i )cin a[i], a[i] a[i - 1];for (int i n; i 1; i -- ) {int l i, r n, res -1;while (l r) {int mid l r 1;if (a[mid] - a[i - 1] x) r mid - 1, res mid;else l mid 1;}if (res -1) dp[i] n - i 1;else dp[i] dp[res 1] res - i;}int res 0;for (int i 1; i n; i ) res dp[i];cout res endl;for (int i 1; i n; i ) dp[i] 0;
}Problem D. Funny Game
Statement
给定 n n n 个点以及序列 a a a接下来有若干次操作
选择 u , v u,v u,v其中 ∣ a u − a v ∣ |a_u-a_v| ∣au−av∣ 是 x x x 的倍数连接 u , v u,v u,v。
通过进行 n − 1 n-1 n−1 次操作是否能将 n n n 个点连接成为一棵树是则输出方案。
Solution
观察 Observation
观察样例发现全部均是 YES回想抽屉原理的一个应用即为证明存在性。
深入探究 Investigate Deeply ∣ a u − a v ∣ |a_u-a_v| ∣au−av∣ 是 x x x 的倍数等价于 a u ≡ a v ( m o d x ) a_u\equiv a_v\pmod x au≡av(modx)考虑倒序操作则进行第 x x x 次操作前有 x 1 x1 x1 个连通块即可选的数有 x 1 x1 x1 个而对 x x x 取模后可行的数只有 x x x 个通过抽屉原理不管前面如何操作此时必然有至少 1 1 1 组 a u ≡ a v ( m o d x ) a_u\equiv a_v\pmod x au≡av(modx)通过并查集找出即可。
综上所述答案永远都是存在的
Code
int find(int x) {if (par[x] ! x) par[x] find(par[x]);return par[x];
}
void solve() {cin n;for (int i 1; i n; i ) cin a[i];for (int i 1; i n; i ) par[i] i;for (int i n - 1; i 1; i --) {for (int j 1; j n; j ) pos[a[j] % i].push_back(j);for (int j 0; j n; j ) {sort(pos[j].begin(), pos[j].end(), [](int a, int b) { return find(a) find(b); });if (pos[j].size() 1) continue;if (find(pos[j][0]) ! find(pos[j].back())) {par[find(pos[j][0])] find(pos[j].back());res.emplace_back(pos[j][0], pos[j].back());break;}}for (int j 0; j n; j ) pos[j].clear();}reverse(res.begin(), res.end());cout YES endl;for (auto v : res) cout v.fi v.se endl;res.clear();
}Problem E. Wooden Game
Statement
给定 k k k 棵树第 i i i 棵树有 n i n_i ni 个节点每次可以将任意一棵树的一个子树删除最终的权值即为删除的子树的大小按位或和。
Solution
观察 Observation
简化如果只有 1 1 1 棵树则答案必为这棵树的大小。
证明对于 x 1 x 2 ⋯ x k n x_1x_2\dots x_k n x1x2⋯xkn则 x 1 ∣ x 2 ∣ … ∣ x k ≤ n x_1|x_2|\dots |x_k\le n x1∣x2∣…∣xk≤n。所以这说明对于一棵树至多只存在一个子树给答案是有贡献的而一棵树便是特殊情况必然是这棵树的大小
深入探究 Investigate Deeply
从观察中得出一棵树只有一个子树给答案是有贡献的考察这棵子树的大小取值范围由于可以不断地删除叶子节点取剩余部分所以大小地取值范围为 [ 1 , n i ] [1,n_i] [1,ni]。
问题转化为给定 k k k 个变量 x x x第 i i i 个变量的取值范围为 [ 1 , n i ] [1,n_i] [1,ni]求 max ( x 1 ∣ x 2 ∣ … ∣ x k ) \max(x_1|x_2|\dots |x_k) max(x1∣x2∣…∣xk)。故变为了二进制的问题使用经典方式拆位对于第 i i i 位 如果存在大于等于 2 2 2 个 n j n_j nj 使得第 i i i 位为 1 1 1则一个 n i n_i ni 将这一位变为 1 1 1其余的只需这一位取 0 0 0后面所有位取 1 1 1 即可。 如果存在恰好 1 1 1 个 n j n_j nj 使得第 i i i 位为 1 1 1则只需将第 i i i 位变为 1 1 1 即可。
Code
void solve() {cin n;for (int i 1; i n; i ) {cin a[i];int x;for (int j 2; j a[i]; j ) cin x;}for (int i 1; i n; i )for (int j 0; j 30; j ) cnt[j] (a[i] j 1);int res 0;for (int i 30; i 0; i --) {if (cnt[i] 2) res | ((1ll i) - 1) | (1ll i);else if (cnt[i] 1) {res | (1ll i);}}cout res endl;for (int i 0; i 30; i ) cnt[i] 0;
}Problem F. Stardew Valley
Statement
给定 n n n 个点 m m m 条边的无向图边权为 1 1 1 的边必须选边权为 0 0 0 的边可选可不选。求该图上的一条欧拉回路经过选过的边恰好 1 1 1 次
Solution
观察 Observation
由于欧拉回路的判定方式为所有点的度数均为偶数故问题转化为在选择边权为 1 1 1 的边每个点的度数的奇偶性组成 01 01 01 序列。现在可以加入若干条边使得两个端点的奇偶性可以异或 1 1 1。给出 1 1 1 种选择方案将选出的边加入后跑欧拉回路即可解决问题。
深入探究 Investigate Deeply
上述问题与 ABC155F - Perils in Parallel 化为 1 1 1 道题具体过程此处不再赘述。 聪明的人能看到事物之间的联系更聪明的人能看到联系之间的联系。 Code
void add(int a, int b) {e[idx] b, ne[idx] h[a], h[a] idx ;
}
void dfs(int u) {st[u] d[u], vis[u] true;for (auto v : g[u]) {if (vis[v]) continue;dfs(v);st[u] ^ st[v];if (st[v]) add(u, v), add(v, u);}
}
void Euler_Path(int u) {for (int i h[u]; ~i;) {if (has[i]) { i ne[i]; continue; }int j e[i];has[i ^ 1] true, i ne[i], Euler_Path(j);}res.push(u);
}void solve() {cin n m;for (int i 1; i n; i ) h[i] -1, vis[i] 0, st[i] 0, d[i] 0, g[i].clear();while (m -- ) {int u, v, c;cin u v c;if (!c) g[u].emplace_back(v), g[v].emplace_back(u);else add(u, v), add(v, u), d[u] ^ 1, d[v] ^ 1;}for (int i 1; i n; i )if (!vis[i]) {dfs(i);if (st[i]) {cout NO endl;return;}}Euler_Path(1);cout YES endl;cout res.size() - 1 endl;while (res.size()) cout res.top() , res.pop();cout endl;
}Problem G. Minecraft
Statement
给定目标 01 01 01 串 s s s 和 n n n 个 01 01 01 串 a i a_i ai求出 01 01 01 串 x x x 使得 ∑ a i ⊕ x s \sum a_i\oplus xs ∑ai⊕xs。 01 01 01 串的长度均为 k k k。 1 ≤ n , k ≤ 2 × 1 0 6 1\le n,k\le 2\times 10^6 1≤n,k≤2×106 1 ≤ n ⋅ k ≤ 2 × 1 0 6 1\le n\cdot k\le 2\times 10^6 1≤n⋅k≤2×106
Solution
观察 Observation
二进制问题——拆位考虑对于每一位与 s s s 匹配的方案不过注意到存在加法所以需要同时处理进位问题。对于第 i i i 位这一位上填的 1 1 1 的个数不会超过 2 n 2n 2n所以可以直接存储 1 ≤ n ⋅ k ≤ 2 × 1 0 6 1\le n\cdot k\le 2\times 10^6 1≤n⋅k≤2×106
深入探究 Investigate Deeply
令 f i , j f_{i,j} fi,j 表示前 i i i 位第 i i i 位填了 j j j 个 1 1 1 是否可行。考虑转移 { f i , ⌊ j 2 ⌋ c n t i ← f i 1 , j ⌊ j 2 ⌋ c n t i m o d 2 s i f i , ⌊ j 2 ⌋ n − c n t i ← f i 1 , j ⌊ j 2 ⌋ n − c n t i m o d 2 s i \begin{cases} f_{i,\lfloor\frac{j}{2}\rfloor\mathrm{cnt}_i}\leftarrow f_{i1,j} \qquad \lfloor\frac{j}{2}\rfloor\mathrm{cnt}_i\bmod 2 s_i\\ f_{i,\lfloor\frac{j}{2}\rfloorn-\mathrm{cnt}_i}\leftarrow f_{i1,j}\qquad \lfloor\frac{j}{2}\rfloorn-\mathrm{cnt}_i\bmod 2 s_i \end{cases} {fi,⌊2j⌋cnti←fi1,j⌊2j⌋cntimod2sifi,⌊2j⌋n−cnti←fi1,j⌊2j⌋n−cntimod2si 第一种情况即为当前位 x x x 为 0 0 0第二种情况为当前位 x x x 为 1 1 1。从 i 1 i1 i1 转移过来的原因主要是要从低位向高位做因为进位是从低位向高位的。
Code
void solve() {int n, k;cin n k;char x;std::vectorint s(k), cnt(k, 0);std::vectorvectorint a(n 1, vectorint(k)), dp(k, vectorint(2 * n 1, 0));std::vectorvectorarrayint, 3 pre(k, vectorarrayint, 3(2 * n 1));for (int i 0; i k; i ) cin x, s[i] x 1;for (int i 1; i n; i ) for (int j 0; j k; j ) cin x, a[i][j] x 1, cnt[j] a[i][j];if ((cnt[k - 1] 1) s[k - 1]) dp[k - 1][cnt[k - 1]] 1;if ((n - cnt[k - 1] 1) s[k - 1]) dp[k - 1][n - cnt[k - 1]] 1;for (int i k - 2; i 0; i --)for (int j 0; j 2 * n; j ) {if (!dp[i 1][j]) continue;int put1 ((j 1) cnt[i] 1), put2 ((j 1) n - cnt[i] 1);if (put1 s[i]) dp[i][(j 1) cnt[i]] | dp[i 1][j], pre[i][(j 1) cnt[i]] {i 1, j, 0};if (put2 s[i]) dp[i][(j 1) n - cnt[i]] | dp[i 1][j], pre[i][(j 1) n - cnt[i]] {i 1, j, 1};}if (!dp[0][s[0]]) cout -1 endl;else {PII lst {0, s[0]};std::vectorint res;while (lst.fi ! k - 1) {res.push_back(pre[lst.fi][lst.se][2]);lst {pre[lst.fi][lst.se][0], pre[lst.fi][lst.se][1]};}if (lst.se cnt[k - 1]) res.push_back(0);else res.push_back(1);for (auto v : res) cout v;cout endl;}
}视频讲解 Video Tutorial Codeforces Round 959 sponsored by NEAR (Div. 1 Div. 2)A ~ G 题讲解
