河北工业大学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; }
