題目鏈接

https://codeforces.com/gym/102133

參考題解

A - Tree Orientation

簡要題意：

給定 $n$ 個結點的無向樹，根為 $1$ 號點，問有多少種將邊定向的方案，使得出度為 $0$ 的點恰有 $m$ 個。

解題思路：

考慮 $dp$，每個結點考慮其到父結點的邊的定向情況，$fp[u][i]$ 表示 $u$ 子樹內， $u$ 結點的邊指向父結點時，恰有 $i$ 個出度為 $0$ 的點的方案數；同理 $fd[u][i][0/1]$ 表示將邊指向 $u$ 結點，這里需要額外加一維表示 $u$ 是否出度為 $0$。轉移時逐子樹合并轉移，復雜度分析同樹上背包。狀態轉移見代碼。

參考代碼：

#include<bits/stdc++.h> using namespace std; #define pb emplace_back #define sz(a) ((int)a.size()) #define lson (rt << 1) #define rson (rt << 1 | 1) #define gmid (l + r >> 1) typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e3 + 5; const int mod = 1e9 + 7; const int inf = 0x3f3f3f3f;vector<int> G[maxn]; int siz[maxn]; ll fd[maxn][maxn][2], fp[maxn][maxn]; int n, m;void dfs(int u, int f){siz[u] = 1, fd[u][1][1] = fp[u][0] = 1;for(auto &v : G[u]){if(v == f) continue;dfs(v, u);memset(fd[0], 0, sizeof fd[0]);memset(fp[0], 0, sizeof fp[0]);for(int i = siz[u]; i >= 0; --i){for(int j = siz[v]; j >= 0; --j){(fd[0][i + j][0] += fd[u][i][0] * (fd[v][j][0] + fd[v][j][1] + fp[v][j])) %= mod;if(i + j > 0) (fd[0][i + j - 1][0] += fd[u][i][1] * (fd[v][j][0] + fd[v][j][1])) %= mod;(fd[0][i + j][1] += fd[u][i][1] * fp[v][j]) %= mod;(fp[0][i + j] += fp[u][i] * (fd[v][j][0] + fd[v][j][1] + fp[v][j])) %= mod;}}memcpy(fd[u], fd[0], sizeof fd[0]);memcpy(fp[u], fp[0], sizeof fp[0]);siz[u] += siz[v];} }int main(){ios::sync_with_stdio(0); cin.tie(0);cin >> n >> m;for(int i = 1; i < n; ++i){int u, v; cin >> u >> v;G[u].pb(v), G[v].pb(u);}dfs(1, 0);ll ret = (fd[1][m][0] + fd[1][m][1]) % mod;cout << ret << endl;return 0; }

B - A Masterpiece

簡要題意：

給一個數 $n$，求構造 $n\times n$ 的矩陣，滿足數 $1$ 到 $n^2$ 分別出現一次，并且任意相鄰的數差值大于 $1$，且任意一組 $n$ 個行下標不同、且列下標不同的數之和相同。

解題思路：

$n=1$ 時單走一個 $1$；$2\le n\le 3$ 無解；否則，令 $a_{i,j}=(i?1)?n+j$，則僅不滿足行內相鄰數差值大于 $1$ 這個條件。由和值相同的條件得到任意 $a_{i1,j1}?a_{i1,j2}=a_{i2,j1}?a_{i2,j2}$，故僅需要對列進行交換調整答案，一個可行方案為先排列偶數列、再排奇數列。

參考代碼：

#include<bits/stdc++.h> using namespace std; #define pb emplace_back #define sz(a) ((int)a.size()) #define lson (rt << 1) #define rson (rt << 1 | 1) #define gmid (l + r >> 1) typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e2 + 5; const int mod = 1e9 + 7; const int inf = 0x3f3f3f3f;int n;int main(){ios::sync_with_stdio(0); cin.tie(0);cin >> n;if(n == 1){cout << "1" << endl;cout << "1" << endl;}else if(n <= 3){cout << "-1" << endl;}else{cout << n << endl;for(int i = 1; i <= n; ++i){int x = (i - 1) * n;for(int j = 2; j <= n; j += 2) cout << x + j << " ";for(int j = 1; j <= n; j += 2) cout << x + j << " ";cout << endl;}}return 0; }

C - Auction

簡要題意：

給定一個數 $n$，現有 $x=1$，$AB$ 兩人輪流對 $x$ 乘上 $2$ 到 $9$ 中的一個數，$A$ 先手，當 $x>n$ 時停止游戲，無法操作的一方輸。問是否先手必勝。

解題思路：

逆向考慮，當 $x>n$ 為必敗態，$x\in (?\frac{n}{9}?,n]$ 為必勝態（存在一種 $\times 9$ 的操作使得對方必敗），$x\in (?\frac{?\frac{n}{9}?}{2}?,?\frac{n}{9}?]$ 為必敗態（無論乘上多少對方都落入前面那個必勝態），以此類推。

參考代碼：

#include<bits/stdc++.h> using namespace std; #define pb emplace_back #define sz(a) ((int)a.size()) #define lson (rt << 1) #define rson (rt << 1 | 1) #define gmid (l + r >> 1) typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e2 + 5; const int mod = 1e9 + 7; const int inf = 0x3f3f3f3f;int main(){ios::sync_with_stdio(0); cin.tie(0);int T; cin >> T;while(T--){ll n; cin >> n;ll l = n / 9, r = n, d = 9, ret = 1;while(l >= 1){d = d == 2 ? 9 : 2;r = l, l /= d, ret ^= 1;// cout << l << " " << r << " " << ret << endl;}cout << (ret ? "YES" : "NO") << endl;}return 0; }

F - Financial Reports

簡要題意：

給一個數組 $a$，求在進行一次交換操作后的最大子段和，并輸出交換方案，交換下標須不同、最大子段和區間非空。

解題思路：

交換后最大子段和必然不減，若最大子段和不變，如果區間長為 $1$，則任意交換都可以成為答案；若區間長度大于 $1$，交換最大子段和內部兩個下標。否則，考慮答案有增加的交換操作，考慮枚舉交換的 $O(n^2)$ 種情況，對答案有增量意味著交換的其中一個下標 $x$ 落在某最大子段和 $[l,r]$ 內部、或恰處于邊界 $l?1,r+1$ 處。故可以枚舉下標 $x$，討論另一個交換下標 $y$：若 $y>x$，則 $x$ 左側 $[1,x?1]$ 取最大的后綴和，$x$ 右側 $[x+1,n]$ 取最大的 $a_y+\sum _{i=x+1}^p{a}_i$，其中 $p<y$。$x<y$ 的情況同理。用線段樹區間合并可以維護。

參考代碼：

#include<bits/stdc++.h> using namespace std; #define pb emplace_back #define sz(a) ((int)a.size()) #define lson (rt << 1) #define rson (rt << 1 | 1) #define gmid (l + r >> 1) typedef long long ll; typedef pair<ll, int> pii; const int maxn = 1e5 + 5; const int mod = 1e9 + 7; const int inf = 0x3f3f3f3f;int a[maxn], n;template<class T> T max(const T &a, const T &b, const T &c){return max(a, max(b, c)); } struct Node{ll sum, pmx, lmx, rmx, lpmx, prmx;int p, l, r, lp, rp;friend Node operator + (const Node &a, const Node &b){Node c;c.sum = a.sum + b.sum;tie(c.pmx, c.p) = max(pii(a.pmx, a.p), pii(b.pmx, b.p));tie(c.lmx, c.l) = max(pii(a.lmx, a.l), pii(a.sum + b.lmx, b.l));tie(c.rmx, c.r) = max(pii(b.rmx, b.r), pii(b.sum + a.rmx, a.r));tie(c.lpmx, c.lp) = max(pii(a.lpmx, a.lp), pii(a.lmx + b.pmx, b.p), pii(a.sum + b.lpmx, b.lp));tie(c.prmx, c.rp) = max(pii(b.prmx, b.rp), pii(b.rmx + a.pmx, a.p), pii(b.sum + a.prmx, a.rp));return c;} } tr[maxn << 2];struct Ans{ll v; int x, y;bool operator < (const Ans &o) const{return v < o.v;} } ans;void pushUp(int rt){tr[rt] = tr[lson] + tr[rson]; }void build(int l, int r, int rt){if(l == r){tr[rt].sum = tr[rt].pmx = tr[rt].lpmx = tr[rt].prmx = a[l];tie(tr[rt].lmx, tr[rt].l) = max(pii(a[l], l), pii(0, l - 1));tie(tr[rt].rmx, tr[rt].r) = max(pii(a[r], r), pii(0, r + 1));tr[rt].p = tr[rt].lp = tr[rt].rp = l;return;}int mid = gmid;build(l, mid, lson);build(mid + 1, r, rson);pushUp(rt); }Node query(int l, int r, int rt, int L, int R){// cout << rt << " " << l << " ?? " << r << " " << tr[rt].prmx << " " << tr[rt].rp << endl;if(l >= L && r <= R) return tr[rt];int mid = gmid;if(L <= mid && R > mid) return query(l, mid, lson, L, R) + query(mid + 1, r, rson, L, R);else if(L <= mid) return query(l, mid, lson, L, R);else return query(mid + 1, r, rson, L, R); }int main(){ios::sync_with_stdio(0); cin.tie(0);cin >> n;for(int i = 1; i <= n; ++i) cin >> a[i];build(1, n, 1);Ans ans = Ans{a[1], 1, 1};for(int i = 1; i <= n; ++i){Node ln = i > 1 ? query(1, n, 1, 1, i - 1) : Node();Node rn = i < n ? query(1, n, 1, i + 1, n) : Node();if(i > 1) ans = max(ans, Ans{ln.rmx + a[i], i, ln.r});if(i > 1) ans = max(ans, Ans{ln.prmx + rn.lmx, ln.rp, i});if(i < n) ans = max(ans, Ans{ln.rmx + rn.lpmx, i, rn.lp});// if(i == 4) cout << ln.prmx << " ?? " << ln.rp << endl;// cout << i << " " << ans.v << " " << ans.x << " " << ans.y << endl;}if(ans.x == ans.y) ans.x = 1, ans.y = n;cout << ans.v << endl;cout << ans.x << " " << ans.y << endl;return 0; }

我寫的另一種比較煩的做法，可以用來練習。枚舉 $O(n^2)$ 個子段和，考慮最大化答案的情況，即內部找一個最小值與外部的最大值交換。考慮與子段內與左邊交換的情況，另一種情況將序列反轉后同理。枚舉 $r$，求 $\underset{l=1}{\overset{r}{\max }}\{\sum _{i=l}^r{a}_i+\underset{i=1}{\overset{l?1}{\max }}{a}_i?\underset{i=l}{\overset{r}{\min }}\}$，迭代 $r$，用線段樹維護該值：$r?1$ 到 $r$ 時，對于 $\sum _{i=l}^r{a}_i$ 這一項，只需要對 $[1,r]$ 加上 $a_r$；最大值項對應一次單點加；最小值項用單調棧維護，每次修改為區間加法。

#include<bits/stdc++.h> using namespace std; #define pb emplace_back #define sz(a) ((int)a.size()) #define lson (rt << 1) #define rson (rt << 1 | 1) #define gmid (l + r >> 1) typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e5 + 5; const int mod = 1e9 + 7; const int inf = 0x3f3f3f3f;typedef pair<ll, int> pli; const ll oo = 1ll << 60; struct Node{ll val; int x, y;bool operator < (const Node &o) const{return val < o.val;} } ans1, ans2; ll a[maxn], b[maxn], sum[maxn]; pli mx[maxn]; pli stk[maxn]; int top; int n;struct SegTree{pli mx[maxn << 2], mn[maxn << 2]; ll add[maxn << 2];void pushUp(int rt){mx[rt] = max(mx[lson], mx[rson]);mn[rt] = min(mn[lson], mn[rson]);}void build(int l, int r, int rt){add[rt] = 0;if(l == r){mx[rt] = mn[rt] = {0, l};return;}int mid = gmid;build(l, mid, lson);build(mid + 1, r, rson);pushUp(rt);}void pushDown(int rt){if(add[rt]){add[lson] += add[rt], add[rson] += add[rt];mx[lson].first += add[rt], mx[rson].first += add[rt];mn[lson].first += add[rt], mn[rson].first += add[rt];add[rt] = 0;}}void update(int l, int r, int rt, int L, int R, ll val){if(l >= L && r <= R){add[rt] += val;mx[rt].first += val;mn[rt].first += val;return;}int mid = gmid; pushDown(rt);if(L <= mid) update(l, mid, lson, L, R, val);if(R > mid) update(mid + 1, r, rson, L, R, val);pushUp(rt);}pli queryMx(int l, int r, int rt, int L, int R){if(l >= L && r <= R) return mx[rt];int mid = gmid; pli ret = {-oo, 0}; pushDown(rt);if(L <= mid) ret = max(ret, queryMx(l, mid, lson, L, R));if(R > mid) ret = max(ret, queryMx(mid + 1, r, rson, L, R));return ret;}pli queryMn(int l, int r, int rt, int L, int R){if(l >= L && r <= R) return mn[rt];int mid = gmid; pli ret = {oo, 0}; pushDown(rt);if(L <= mid) ret = min(ret, queryMn(l, mid, lson, L, R));if(R > mid) ret = min(ret, queryMn(mid + 1, r, rson, L, R));return ret;} } tr_a, tr_sum, tr;void solve(Node &ans){sum[0] = 0, mx[0] = {-oo, 0};for(int i = 1; i <= n; ++i){sum[i] = sum[i - 1] + a[i];mx[i] = max(mx[i - 1], pli{a[i], i});}stk[top = 0] = {-oo, 0};tr_a.build(1, n, 1);tr_sum.build(1, n, 1);tr.build(1, n, 1);for(int i = 1; i <= n; ++i){tr_a.update(1, n, 1, i, i, a[i]);tr_sum.update(1, n, 1, 1, i, a[i]);tr.update(1, n, 1, 1, i, a[i]);tr.update(1, n, 1, i, i, mx[i - 1].first - a[i]);while(a[i] <= stk[top].first){pli er = stk[top--], el = stk[top];tr.update(1, n, 1, el.second + 1, er.second, er.first - a[i]);}stk[++top] = {a[i], i};pli e = tr_sum.queryMx(1, n, 1, 1, i);ll s = sum[i]; int l = e.second;Node tmp = Node{s, l, i};if(ans < tmp) ans = tmp;if(i == 1) continue;e = tr.queryMx(1, n, 1, 2, i);s = e.first, l = e.second;int pl = mx[l - 1].second, pr = tr_a.queryMn(1, n, 1, l, i).second;tmp = Node{s, pl, pr};if(ans < tmp) ans = tmp;} }int main(){ios::sync_with_stdio(0); cin.tie(0);cin >> n;for(int i = 1; i <= n; ++i) cin >> a[i];ans1.val = ans2.val = -oo;solve(ans1);reverse(a + 1, a + 1 + n);solve(ans2);ans2.x = n - ans2.x + 1;ans2.y = n - ans2.y + 1;if(ans1 < ans2) ans1 = ans2;if(ans1.x == ans1.y) ans1.x = 1, ans1.y = n;cout << ans1.val << endl;cout << ans1.x << " " << ans1.y << endl;return 0; }

G - Moore’s Law

簡要題意：

給定 $n$，構造一個數 $x$ 滿足 $x$ 十進制表示僅包含 $1$ 和 $2$，且 $x$ 是 $2^n$ 的倍數。

解題思路：

遞推構造，$an{s}_1=2$，對于 $i>1$，討論 $an{s}_{i?1}\%2^i$，若余數為 $2^{i?1}$，則加上 $10^{i?1}$ 使得余數為 $0$；若余數為 $0$，可不操作，或加上 $2\times 10^{i?1}$。

參考代碼：

ans = [0 for i in range(43)] ans[1] = '2' for i in range(2, 43):if int(ans[i - 1]) % 2**i == 0:ans[i] = '2' + ans[i - 1]else:ans[i] = '1' + ans[i - 1] n = int(input()) print(ans[n])

I - Number builder

簡要題意：

簽到題。

解題思路：

分類討論。

參考代碼：

#include<bits/stdc++.h> using namespace std; #define pb emplace_back #define sz(a) ((int)a.size()) #define lson (rt << 1) #define rson (rt << 1 | 1) #define gmid (l + r >> 1) typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e2 + 5; const int mod = 1e9 + 7; const int inf = 0x3f3f3f3f;int main(){ios::sync_with_stdio(0); cin.tie(0);int n; cin >> n;int s = n % 3 == 1 ? 1 : 2;do{cout << s;n -= s, s = 3 - s;}while(n > 0);cout << endl;return 0; }

總結

以上是生活随笔為你收集整理的2016-2017 7th BSUIR Open Programming Contest. Final 补题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。