河北工業大學ACM選拔賽10月末
- 2020 年 2 月 18 日
- 筆記
題目大意:
給樹染色.相鄰結點的顏色不同.求最後的顏色.後面的顏色會覆蓋前面的.沒有染色成功的輸出0
題解
由於是一棵樹,一個樹結點和他相鄰的結點就是以這個結點作為根的直接孩子還有他的父親.所以考慮先把無根樹轉換成有根樹.這樣就得到了每個結點的直接孩子.每個結點維護一個多重集合.裡面存它的所有直接孩子的顏色.所以我們可以以$O(1)$的複雜度得到他的父親的顏色.以$O(logN)$的複雜度得到他的孩子裡面任意一個顏色.對於每個結點$x$.想要將$x$染成$y$.如果$x$的父親$fa[x]$的顏色是$y$.或者$x$的孩子結點中有顏色是$y$的點.那麼這個點我們不能染.否則.如果這個點曾經染過別的顏色.現在要更新.需要維護父親$fa[x]$的多重集合.先刪除$x$之前的顏色.再插入新的顏色. 所以.總的複雜度大概是$O(MlogN)$
#include <bits/stdc++.h> using namespace std; const int MAX_N = 1e5+100; int N,M; int fa[MAX_N]; vector<int> G[MAX_N]; multiset<int> S[MAX_N]; int color[MAX_N]; void dfs(int u, int f){ fa[u] = f; for(int i = 0; i < G[u].size(); ++i){ int v = G[u][i]; if(v != f) dfs(v, u); } } int main(){ //freopen("in.txt", "r", stdin); int u,v; int x,y; while(~scanf("%d%d", &N, &M)){ for(int i = 0;i <= N; ++i) { G[i].clear(); S[i].clear(); } memset(color, 0, sizeof color); for(int i = 0;i < N-1; ++i){ scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } dfs(1, 0); for(int i = 0;i < M; ++i){ scanf("%d%d", &x, &y); // 判斷 if(color[fa[x]] == y || S[x].find(y) != S[x].end()) continue; // 維護父親 if(color[x]) S[fa[x]].erase(S[fa[x]].find(color[x])); S[fa[x]].insert(y); color[x] = y; } for(int i = 1;i <= N; ++i){ printf("%dn", color[i]); } } return 0; }
F.選舉
題目大意
n個人,m個城市.第i行j列代表第i個城市給第j的編號的人投出的票數.第一輪.每個城市勝出且編號小的貢獻加一.第二輪每個人貢獻最大且編號最小的是最終的答案.輸出每組樣例勝出的人的編號.
題解
題目大意就是題解.一場cf的div 2的A
#include <bits/stdc++.h> using namespace std; // Elections #define MAX_N 105 int n,m; int sum[MAX_N]; int main(){ //freopen("in.txt", "r", stdin); ios::sync_with_stdio(0); cin.tie(0); int x; while(cin >> n >> m){ // n個候選人. m個城市 memset(sum, 0, sizeof(sum)); for(int i = 1; i <= m; ++i){ int idx = 1, maxx = 0; for(int j = 1; j <= n; ++j){ cin >> x; if(maxx < x){ idx = j; maxx = x; } } ++sum[idx]; } int ansidx = 1; int maxx = sum[1]; for(int i = 2; i <= n; ++i){ if(maxx < sum[i]){ maxx = sum[i]; ansidx = i; } } cout << ansidx << endl; } return 0; }
G.訊號與系統
題目大意
題解
emm.大概就是看圖按照這個意思理解.一道cf div2的C題.
#include <bits/stdc++.h> using namespace std; typedef long long LL; #define MAX_N 55 char s[MAX_N]; // emm.這個函數有一個隱藏特性.就是如果參數c不是26個字母的話.返回c的ASCII值 int idx(char c){ if(c >= 'A' && c <= 'Z') return c - 'A' +1; if(c >= 'a' && c <= 'z') return c - 'a' +1; } int main() { //freopen("in.txt", "r", stdin); while(~scanf("%s", s)){ char a[5] = "@[`{"; LL res = 0; for(int i = 0; s[i]; ++i){ char b = s[i]; int f1 = (a[0] < b) & (a[1] > b); int f2 = (a[2] < b) & (a[3] > b); res += (f1 * idx(b) - f2 * idx(b)); } cout << res << endl; } return 0; }
H.大數GCD
題目大意
$1 <= a <= b <= 10^{100}$. 求$gcd(a, a+1, a+2, …, b)$.
題解
emmm.看題目被大數GCD嚇一跳.想用大數寫一個歐幾里得.細讀的話會發現.當$a <= b$的時候$gcd(a,a+1,a+1,…b) = gcd(gcd(a,a+1),a+2,..,d) = gcd(1,a+2,..,d) = 1$.當$a==b$的時候.兩個相等的數的最大公約數就是$a$.一道cf的div2A
#include <bits/stdc++.h> // 1966: Complicated GCD using namespace std; int main() { //freopen("in.txt", "r", stdin); string a, b; cin >> a >> b; if (a == b) cout << a; else cout << 1; return 0; }
I 計算之神
程式碼裡面注釋的是原題鏈接.這道題是當時暑假參加ccpc-wannafly的時候做的題.當時沒有做出來.orz.後面牛客重現賽的時候做出來的.
題目大意
$$ f(l, r) = (sum_{i=l}^r{a_i})*w_{r-l+1} $$ 求解: $$ sum_{l=1}^r{sum_{r=l}^n{f(l, r)}} $$
題解
兩個式子看起來很複雜.無腦暴力一定超時.emmm.具體計算下次再更新.大概就是去掉重複的計算.上程式碼.orz.
#include <bits/stdc++.h> using namespace std; /* https://www.nowcoder.com/acm/contest/204/G */ const int MAX_N = 3*1e5+100; typedef long long LL; const LL MOD = 1e9+7; int n; LL a[MAX_N], w[MAX_N], sum[MAX_N]; inline LL getSum(int l, int r){ return (sum[r] - sum[l-1]) % MOD; } int main(){ // freopen("in.txt", "r", stdin); ios::sync_with_stdio(0); cin.tie(0); cin >> n; memset(sum, 0, sizeof(sum)); for(int i = 1; i <= n; ++i) { cin >> a[i]; sum[i] = (sum[i-1] + a[i]) % MOD; } for(int i = 1; i <= n; ++i) cin >> w[i]; LL ans = 0LL, x = 0LL; for(int i = 1; i <= n >> 1; ++i){ x = (x + getSum(i, n-i+1)) % MOD; ans += (((w[i] + w[n-i+1]) % MOD) * (x % MOD)) % MOD; } if(n & 1) { int i = (n >> 1) + 1; ans += w[i] * (x + a[i]) % MOD; } cout << ans% MOD << endl; return 0; }
J.萊昂哈德·歐拉
emm.這道題出自牛客的一場小白月賽.記得那次出題人背B題的鍋.被罵得很嚴重
題目大意
求$[l,r]$之間有約束的數字的個數.
題解
裸數位dp.emmm.後面細更
#include <bits/stdc++.h> using namespace std; // https://www.nowcoder.com/acm/contest/214/E typedef long long LL; const LL MOD = 20020219; const int INF = 63; #define MAX_N 25 LL f[MAX_N][11][INF+1]; int t; LL l,r; int n; int lim[11],x,len; int num[MAX_N]; LL dfs(int pos, bool limit, int pre, int cnt){ if(cnt > lim[pre]) return 0; if(pos == 0) return 1; if(!limit && f[pos][pre][cnt] != -1) return f[pos][pre][cnt]; // 計算過了 int up = limit ? num[pos] : 9; LL tmp = 0; for(int i = 0;i <= up; ++i){ tmp = (tmp + dfs(pos-1, limit && num[pos] == i, i, i == pre ? cnt+1 : 1) + MOD) % MOD; } return limit ? tmp : f[pos][pre][cnt] = tmp % MOD; } LL solve(LL x){ if(x == -1) return 0; int pos = 0; while(x){ num[++pos] = int(x%10); x /= 10; } // pre初始值是0.orz.就過了.因為對0沒有限制.不能設置成-1.因為數組下標沒有-1 return dfs(pos, true, 0, 1) % MOD; } int main(){ //freopen("in.txt", "r", stdin); ios::sync_with_stdio(0); cin.tie(0); cin >> t; while(t--){ cin >> l >> r >> n; for(int i = 0;i < 10; ++i) lim[i] = INF; for(int i = 1; i <= n; ++i){ cin >> x >> len; lim[x] = min(lim[x], len); } memset(f, -1, sizeof f); cout << (solve(r) - solve(l-1) + MOD) % MOD << endl; } return 0; }
L 超市活動
題目大意
在$n*m$的格子中取數滿足取得數字格子之間沒有公共邊.求取出數字的最大和.
題解
n和m比較小.網路流.emmm.後面細更.這道題目的程式碼我沒動手.拿的別人的程式碼.昨天晚上突然很怕今天有人AK。所以加上了這道題目.
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> #include <vector> using namespace std; const int MAXN = 50*50; const int INFS = 0x7FFFFFFF; struct edge { int from, to, cap, flow; edge(int _from, int _to, int _cap, int _flow) : from(_from), to(_to), cap(_cap), flow(_flow) {} }; class Dinic { public: void initdata(int n, int s, int t) { this->n = n, this->s = s, this->t = t; edges.clear(); for (int i = 0; i < n; i++) G[i].clear(); } void addedge(int u, int v, int cap) { edges.push_back(edge(u, v, cap, 0)); edges.push_back(edge(v, u, 0, 0)); G[u].push_back(edges.size() - 2); G[v].push_back(edges.size() - 1); } bool BFS() { for (int i = 0; i < n; i++) vis[i] = false, d[i] = 0; queue<int> Q; Q.push(s); vis[s] = true; while (!Q.empty()) { int x = Q.front(); Q.pop(); for (int i = 0; i < G[x].size(); i++) { edge& e = edges[G[x][i]]; if (e.cap > e.flow && !vis[e.to]) { vis[e.to] = true; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } int DFS(int x, int aug) { if (x == t || aug == 0) return aug; int flow = 0; for (int i = 0; i < G[x].size(); i++) { edge& e = edges[G[x][i]]; if (d[e.to] == d[x] + 1) { int f = DFS(e.to, min(aug, e.cap - e.flow)); if (f <= 0) continue; e.flow += f; edges[G[x][i]^1].flow -= f; flow += f; aug -= f; if (aug == 0) break; } } return flow; } int maxflow() { int flow = 0; while (BFS()) { flow += DFS(s, INFS); } return flow; } private: vector<edge> edges; vector<int> G[MAXN]; int n, s, t, d[MAXN]; bool vis[MAXN]; }; Dinic dc; int row, col; int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1}; bool check(int x, int y) { if (1 <= x && x <= row && 1 <= y && y <= col) { return true; } return false; } int main() { //freopen("in.txt", "r", stdin); scanf("%d%d", &row, &col); int sum = 0; int s = 0, t = row*col + 1; dc.initdata(t + 1, s, t); for (int i = 1; i <= row; i++) { for (int j = 1; j <= col; j++) { int a; scanf("%d", &a); sum += a; if ((i+j) & 1) dc.addedge((i-1)*col+j, t, a); else { dc.addedge(s, (i-1)*col+j, a); for (int k = 0; k < 4; k++) { int x = i + dir[k][0]; int y = j + dir[k][1]; if (check(x, y)) dc.addedge((i-1)*col+j, (x-1)*col+y, INFS); } } } } printf("%dn", sum - dc.maxflow()); return 0; }
