A. A-characteristic (CF 1823 A)
題目大意
要求構造一個僅包含\(1\)和 \(-1\)的長度為 \(n\)的陣列 \(a\)，使得存在 \(k\)個下標對 \((i, j), i < j\)滿足 \(a_i \times a_j = 1\)，
解題思路
當有\(x\)個 \(1\)， \(y\)個 \(-1\)時，其滿足條件的下標對數量為 \(\frac{x (x - 1)}{2} + \frac{y (y - 1)}{2}\)，
由于\(n\)只有 \(100\)，直接列舉 \(x\)即可，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while(t--){
int n, k;
cin >> n >> k;
int one = 0;
for(; one <= n; ++ one){
int neg = n - one;
if (neg * (neg - 1) + one * (one - 1) == 2 * k)
break;
}
if (one > n)
cout << "No" << '\n';
else{
cout << "Yes" << '\n';
for(int i = 0; i < one; ++ i)
cout << 1 << ' ';
for(int i = 0; i < n - one; ++ i)
cout << -1 << ' ';
cout << '\n';
}
}
return 0;
}
B. Sort with Step (CF 1823 B)
題目大意
給定一個排序，問能否僅通過交換相隔\(k\)的倆元素，使得有序，不能的話問能否事先通過一次任意交換操作后，再通過之前的操作交換得到有序，
解題思路
考慮每個元素的原始位置和最后所在的位置，它們對\(k\)的取模應該相同，否則就不能有序，
而如果恰好有兩個元素其對\(k\)的取模不同，且交換之后是相同的，則可以，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while(t--){
int n, k;
cin >> n >> k;
vector<int> a(n);
for(auto &i : a){
cin >> i;
i --;
}
bool ok1 = true;
map<pair<int, int>, int> cnt;
for(int i = 0; i < n; ++ i){
if (i % k != a[i] % k){
ok1 = false;
cnt[{min(i % k, a[i] % k), max(i % k, a[i] % k)}] ++;
}
}
if (ok1)
cout << 0 << '\n';
else if (cnt.size() == 1 && cnt.begin()->second == 2)
cout << 1 << '\n';
else
cout << -1 << '\n';
}
return 0;
}
C. Strongly Composite (CF 1823 C)
題目大意
給定一個陣列\(a\)，構造陣列 \(b\)，要求最大化陣列的元素數量，使得倆陣列的所有元素的乘積相同，且陣列 \(b\)的每個數都是強合數，
強合數的定義為，合數因子數量\(\geq\)質數因子數量，
解題思路
乘積相同，相當于將陣列\(a\)里的質數重新組合；數量最大，相當于盡可能少用質數來組成一個新的數，
可以發現，兩個相同的質陣列成一個強合數，或者三個不同的質數可以組成一個強合數，
由此我們統計陣列 \(a\)中的每個質數的數量，同個質數倆倆組合，不同質數三三組合，就能最大化答案了，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
map<int, int> cnt;
auto fac = [&](int a){
for(int i = 2; i * i <= a; ++ i){
while (a % i == 0){
cnt[i] ++;
a /= i;
}
}
if (a != 1)
cnt[a] ++;
};
for(int i = 0; i < n; ++ i){
int a;
cin >> a;
fac(a);
}
LL ans = 0;
int left = 0;
for(auto &[_, value] : cnt){
ans += value / 2;
left += (value & 1);
}
ans += left / 3;
cout << ans << '\n';
}
return 0;
}
D. Unique Palindromes (CF 1823 D)
題目大意
要求構造一個僅包含小些字母的字串\(s\)，長度為\(n\)，且滿足 \(k\)個限制，
每個限制表述為\((x_i, c_i)\)， 字串\(s\)的長度為 \(x_i\)的前綴滿足有 \(c_i\)個本質不同的回文串）
解題思路
通過打表發現本質不同的回文串數量不會超過字串長度，
注意到\(k\)最大只有 \(20\)，這啟示我們每個限制可以用一個字符去滿足，
思考樸素的構造方法，對于一個長度為 \(n\)的字串，我們可以 \(aaaaaaaabcabcabc\)這樣去構造，一開始連續的 \(a\)的數量就能控制這個字串的本質不同的回文串的數量，這樣的構造方法滿足其數量在 \([3, n]\)之內，這剛好符合題意里 \(c_i \geq 3\)的限制，
因此我們可以先根據第一個限制構造出如上的字串，對于之后的限制進行增量構造，增加的回文數量用 \(dddd\)， \(eeeee\)這樣構造，剩下的長度用 \(abc\)這樣不會增加回文串數量的形式去填充，
注意用于填充的字串，在每次填充時應該繼續前面的，而不是從頭（從\(abc\) ）開始（如代碼的fill_cur），不然可能會新增回文串，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--){
int n, k;
cin >> n >> k;
vector<int> x(k), c(k);
for(auto &i : x)
cin >> i;
for(auto &i : c)
cin >> i;
string ans;
int fill_cur = 0;
auto fill = [&](int x){
while(x--){
ans.push_back('a' + fill_cur);
fill_cur = (fill_cur + 1) % 3;
}
};
auto ok = [&](){
int cur = 0;
for(int i = 0; i < k; ++ i){
int dis = x[i] - c[i];
if (dis < 0)
return false;
if (cur > dis)
return false;
cur = dis;
}
ans += string(c[0] - 3, 'a');
fill(x[0] - ans.size());
for(int i = 1; i < k; ++ i){
ans += string(c[i] - c[i - 1], 'c' + i);
fill(x[i] - ans.size());
}
return true;
};
if (ok()){
cout << "YES" << '\n';
cout << ans << '\n';
}else {
cout << "NO" << '\n';
}
}
return 0;
}
E. Removing Graph (CF 1823 E)
題目大意
兩人博弈，
給定\(n\)個環，每個人可以從\([l, r]\) 中選一個數\(x\)，然后選擇由\(x\) 個點組成的連通子圖，將點及其邊去掉，不能操作者輸，
在絕頂聰明的情況下，問先后手誰必贏，
解題思路
每個環都是一個獨立局面，因此我們求出每個環的\(sg\)值，異或起來，非零就先手贏，否則后手贏，
對于一個環來說，取了一次之后就變成一條鏈了，因此一個環的 \(sg\)值就是所有可能的鏈的長度對應的\(sg\)值的 \(mex\)，
對于一個鏈來說，取了一次之后就變成兩條鏈，這兩條鏈分別都是一個獨立局面，因此一個鏈的 \(sg\)值，就是一些操作值的 \(mex\)， 而操作值就是取了之后（有取的長度和取的位置兩個因素）的兩個鏈的\(sg\)值的異或，
abc287g和abc297g就是要求一個鏈的\(sg\)值，
注意到題目保證了 \(l \neq r\)，對于一條鏈來說，如果它能取（即長度 \(\geq l\)），則必定能分成兩條長度一樣的鏈，之后先手就模仿后手的操作，就能必贏了，
也就是說，對于一個環來說，如果其長度\(len \geq l + r\)，那么先手取了一次后，變成的鏈因為后手必定可以再取（\(len - r \geq l\) )，所以對于后手來說必定是個必勝態，所以這樣的環對于先手來說必定是個必敗態，其 \(sg\)值為 \(0\)，
而長度小于 \(l\)，不能取，那肯定是必敗態，其 \(sg\)值為 \(0\)，
考慮環長度 在 \([l, l+r)\)之間的\(sg\)值，其對應的鏈長度有 \(len - l, len - l - 1, len - l - 2, ..., len - r\)，其\(sg\)值就是這些可能的鏈長度的 \(sg\)值取 \(mex\)，
考慮鏈長度，小于 \(l\)，是必敗態，其 \(sg\)值為 \(0\)， 而\(sg(l) = sg(l + 1) = sg(l + 2) ... = sg(l + l - 1) = 1\)，
\(sg(2l) = mex(sg(l), sg(l - 1), sg(l - 2), ..., sg(1), sg(0)) = mex(1, 0, 0, 0, ..., 0) = 2 = sg(2l + 1) = sg(2l + 2)\)
\(sg(3l) = mex(sg(2l), sg(2l - 1), ..., sg(l), sg(l - 1), ..., sg(0)) = mex(2, 1, ..., 1, 0, ..., 0) = 3 = sg(3l + 1) = sg(3l + 2)\)
上述的\(mex\)里的每一項都是取最邊邊的結果（即取了之后還有一個鏈），至于有兩條鏈的結果，是長度更小的兩個鏈的\(sg\)的異或值，其不會超過上面的最大值，
由此（或打表）可以發現長度為\(sg(len) = \lfloor \frac{len}{l} \rfloor(l \leq len < l + r)\)
進而環的 \(sg_c(len) = mex(sg(len - l), sg(len - l - 1), ..., sg(len - r)) = \lfloor \frac{len}{l} \rfloor(l \leq len < l + r)\)
環的\(sg\)值求出來了，異或一下就知道誰贏了，
至于環大小，用并查集或\(BFS\)一下就知道了，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
class dsu {
public:
vector<int> p;
vector<int> sz;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
sz.resize(n);
iota(p.begin(), p.end(), 0);
fill(sz.begin(), sz.end(), 1);
}
inline int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
sz[y] += sz[x];
return true;
}
return false;
}
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, l, r;
cin >> n >> l >> r;
dsu d(n);
for(int i = 0; i < n; ++ i){
int u, v;
cin >> u >> v;
-- u;
-- v;
d.unite(u, v);
}
int ans = 0;
for(int i = 0; i < n; ++ i){
if (d.get(i) == i){
if (d.sz[i] >= l && d.sz[i] < l + r)
ans ^= d.sz[i] / l;
}
}
if (ans)
cout << "Alice" << '\n';
else
cout << "Bob" << '\n';
return 0;
}
F. Random Walk (CF 1823 F)
題目大意
樹上隨機游走，從點\(s\)到點 \(t\)，問每個點訪問次數的期望值，
解題思路
每次的期望題感覺都比較神仙，
注意到這是棵樹，點\(s\)到點\(t\)的路徑是唯一的，設路徑為\(s, u_0, u_1, ..., u_k, t\)，
一開始設狀態\(dp[s][v][t]\)表示從 \(s\)點到 \(t\)點，期望訪問到 \(v\)號點的次數，然后列舉到相鄰點的狀態，即\(dp[s][v][t] = \sum_{(s, u) \in E}dp[u][v][t]\)，但感覺怎么都算不出來，
然后想著從點 \(s\)出發，它可以往很多個相鄰點走，只有一個點\(u_0\)是更接近點 \(t\)的， 且最終到點\(t\)時立刻停下來，這意味著點\(t\)之后的點的訪問次數的期望值一定是 \(0\)，
考慮到一旦走到點\(u_0\)時，發現問題貌似變成了一個子問題了，可以認為是從點\(u_0\)出發，到點 \(t\)的情況，換句話說，我們可以將 點\(s\)到點 \(t\)的步驟分成若干步，分別是點 \(s\)到點 \(u_0\)，點 \(u_0\)到點 \(u_1\)... 點\(u_t\)到點 \(t\)，由于期望的線性可加性，每個點的期望訪問次數，可以由這些的每個步驟的影響依次累計，
設 \(dp[s][w]\)表示從 \(s\) 點往更接近點\(t\)的方向走（即走到 \(u_0\)點），對 \(w\)點的期望訪問次數，
設點 \(s\)的度數為 \(du_s\)，其余字母定義看圖，根據期望定義，可以得到：
這里有三個部分：
- 有\(\frac{1}{du_s}\)的概率選擇走到 \(u_0\)，然后就停下來了，此時對 \(v\)的訪問貢獻是\(0\)，
- 有\(\frac{1}{du_s}\)的概率往 \(w\)所在的子樹走（即點 \(x\)），此時對\(w\)的訪問貢獻是由\(x \to s\)和\(s \to u_0\)組成，即 \(dp[x][w] + dp[s][w]\)，
- 有\(\frac{du_s - 2}{du_s}\)的概率往其他子樹走（即點 \(y\)表示的其他所有點），此時對\(w\)的訪問貢獻是由\(y \to s\)和\(s \to u_0\)組成，即 \(dp[y][w] + dp[s][w]\)，但由于從點\(y\)到點\(w\)必須經過點 \(s\)，而一旦到點 \(s\)就會停下來（ \(dp[y][w]\)即表示從點 \(y\)到更接近 點\(t\)的方向走（即往點 \(s\)），對點 \(w\)的訪問貢獻），因此 \(dp[y][w] = 0\)，
這樣上述式子移一下項，就得到
\[dp[s][w] = dp[x][w] \]即點\(s\)往點 \(u_0\)走時的對點\(w\)訪問次數的貢獻是等價于點 \(x\)往點 \(s\)走時，對點 \(w\)的貢獻，由此就可以得到
\[dp[s][w] = dp[x][w] = dp[x_1][w] = ... = dp[x_k][w] = dp[w][w] \]剩下的就是求 \(dp[w][w]\)，根據期望定義，可以得到
\[dp[s][s] = \frac{1}{du_s} \times 1 + \frac{du_s - 1}{du_s}(dp[o][s] + dp[s][s]) \]這里有兩部分：
- 有\(\frac{1}{du_s}\)的概率選擇走到 \(u_0\)，此時就停下來了，因此對\(s\)的訪問貢獻是\(1\)（一開始在\(s\)時的貢獻），
- 有\(\frac{du_s - 1}{du_s}\)的概率選擇走到除點\(u_0\)之外的其他點(設點\(o\)，即 \(x\)或 \(y\))，因此對\(s\)的訪問貢獻是\(o \to s\)和 \(s \to s\)，即\(dp[o][s] + dp[s][s]\)，而因為點\(o\)到點 \(s\)就會停下來（點 \(s\)是更接近點 \(t\)的點），因此 \(dp[o][s] = 1\)（一開始在\(s\)時的貢獻包含在 \(dp[s][s]\)里），
這樣上述式子移一下項，就得到
\[dp[s][s] = du_s \]綜合上述的兩個式子\(dp[s][w] = dp[w][w] = du_w\)，可以得出，每當進行一次 \(s \to u_0, u_0 \to u_1,\cdots, u_k \to t\) 時，其他點\(w\)的期望訪問次數都會增加 \(du_w\)，其中點\(w\)是點 \(s\)除了 \(u_0\)方向的其他方向的點（見上圖的虛線包括起來，就是對應顏色的箭頭的影響），
也就是說一個點\(a\)的期望訪問次數就是\(du_a \times cnt_a\)，其中 \(cnt_a\)等于該點與路徑\(s \to t\)的交點（以上圖為例，就為 \(u_{k-1}\)）到 \(t\)的點數（見上圖的點\(a\)），
剩下的就是如何求 \(cnt_w\)，我們可以以點 \(s\)為根，然后我們從點 \(t\)開始，一路沿著 父親節點上去，就回到點\(s\)，其中每往父親跳一次時， \(cnt_w\)就會加一，比如從\(t \to u_k\)時， \(cnt = 0 + 1 = 1\)，此時再遍歷一下除了\(t\)和 \(u_{k - 1}\)方向的所有點 \(w\)，它們的答案就是 \(du_w \times cnt\) ，
最終的時間復雜度是\(O(n)\)，
雖然答案不會超過\(n^2\)，但記得對\(998244353\)取模，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mod = 998244353;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, s, t;
cin >> n >> s >> t;
-- s, -- t;
vector<vector<int>> edge(n);
vector<int> du(n);
for(int i = 1; i < n; ++ i){
int u, v;
cin >> u >> v;
-- u, -- v;
edge[u].push_back(v);
edge[v].push_back(u);
++ du[u];
++ du[v];
}
vector<int> fa(n);
function<void(int, int)> dfs = [&](int u, int f){
fa[u] = f;
for(auto &v : edge[u]){
if (v == f)
continue;
dfs(v, u);
}
};
dfs(s, s);
vector<int> ans(n);
int cnt = 1;
ans[t] = 1;
function<void(int, int, int)> dfs2 = [&](int u, int f, int cnt){
ans[u] = 1ll * du[u] * cnt % mod;
for(auto &v : edge[u]){
if (v == f)
continue;
dfs2(v, u, cnt);
}
};
do{
int cur = fa[t];
ans[cur] = 1ll * cnt * du[cur] % mod;
for(auto &u : edge[cur]){
if (u != fa[cur] && u != t)
dfs2(u, cur, cnt);
}
t = cur;
++ cnt;
}while(s != t);
for(auto &i : ans)
cout << i << ' ';
cout << '\n';
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/551501.html
標籤：其他
上一篇：Vulnhub之GreenOptics靶機詳細測驗程序
下一篇：返回列表