好像克拉麗絲小姐姐題解寫(xiě)的超詳細(xì)我都沒(méi)啥好說(shuō)的了

?

Problem A. Ascending Rating

仔細(xì)一看m是固定的單調(diào)DQ就好了

1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int maxn = 1e7 + 10; 5 int st, ed, deq[maxn]; 6 int a[maxn]; 7 8 inline void add(int i) { 9 while(st < ed && a[deq[ed]] <= a[i]) ed--; 10 deq[++ed] = i; 11 } 12 13 int main() { 14 int T; 15 scanf("%d", &T); 16 while(T--) { 17 int n, m, k, p, q, r, MOD; 18 scanf("%d %d %d %d %d %d %d", &n, &m, &k, &p, &q, &r, &MOD); 19 for(int i = 1; i <= k; ++i) scanf("%d", a + i); 20 for(int i = k + 1; i <= n; ++i) a[i] = ((LL) p * a[i - 1] + (LL) q * i + r) % MOD; 21 LL A = 0, B = 0; 22 st = ed = 0; 23 for(int i = n; i >= n - m + 2; --i) add(i); 24 for(int i = n - m + 1; i >= 1; --i) { 25 add(i); 26 while(st < ed && deq[st + 1] > i + m - 1) st++; 27 A += a[deq[st + 1]] ^ i; 28 B += (ed - st) ^ i; 29 } 30 printf("%lld %lld\n", A, B); 31 } 32 return 0; 33 } Aguin

?

Problem B. Cut The String

回文樹(shù)好像不太會(huì)會(huì)阿?

?

Problem C. Dynamic Graph Matching

被卡怕了嚇得用$2^{n-2}$枚舉三段拼起來(lái)……

還肥腸紙張的用int加了兩次沒(méi)取模！

還有很多人問(wèn)這個(gè)枚舉順序其實(shí)沒(méi)有影響阿……

1 #include <bits/stdc++.h> 2 using namespace std; 3 const int mod = 1e9 + 7; 4 int cnt[1<<11], ans[6]; 5 int ppc[1<<11]; 6 7 int main() { 8 for(int i = 0; i < (1 << 11); ++i) ppc[i] = __builtin_popcountll(i) / 2; 9 int T; 10 scanf("%d", &T); 11 while(T--) { 12 int n, m; 13 scanf("%d %d", &n, &m); 14 for(int i = 0; i < (1 << n); ++i) cnt[i] = 0; 15 cnt[0] = 1; 16 for(int i = 0; i <= n / 2; ++i) ans[i] = 0; 17 for(int i = 1; i <= m; ++i) { 18 char s[11]; 19 int u, v; 20 scanf("%s %d %d", s, &u, &v); 21 if(u > v) swap(u, v); 22 int msk1 = (1 << (u - 1)) | (1 << (v - 1)); 23 for(int j = 0; j < (1 << (n - v)); ++j) { 24 for(int k = 0; k < (1 << (v - u - 1)); ++k) { 25 for(int p = 0; p < (1 << (u - 1)); ++p) { 26 int msk2 = (j << v) | (k << u) | p; 27 ans[ppc[msk2|msk1]] = (ans[ppc[msk2|msk1]] + mod - cnt[msk2|msk1]) % mod; 28 if(s[0] == '+') cnt[msk2|msk1] = (cnt[msk2|msk1] + cnt[msk2]) % mod; 29 else cnt[msk2|msk1] = (cnt[msk2|msk1] + mod - cnt[msk2]) % mod; 30 ans[ppc[msk2|msk1]] = (ans[ppc[msk2|msk1]] + cnt[msk2|msk1]) % mod; 31 } 32 } 33 } 34 for(int i = 1; i <= n / 2; ++i) printf("%d%c", ans[i], i == n / 2 ? '\n' : ' '); 35 } 36 } 37 return 0; 38 } Aguin

?

Problem D. Euler Function

談學(xué)姐寫(xiě)的

1 #include<bits/stdc++.h> 2 using namespace std; 3 long long T,i,j,k,n; 4 int main() 5 { 6 scanf("%d",&T); 7 while (T--) 8 { 9 scanf("%lld",&n); 10 if (n==1) puts("5"); 11 else printf("%lld\n",n+5); 12 } 13 } 談學(xué)姐

?

Problem E. Find The Submatrix

抄抄題解

1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const LL inf = 1e18; 5 LL w[101][3001], a[101][3001], f[101][4][2][10001]; 6 int m; 7 8 LL tmp[10001]; 9 void solve(int i, int j, int o, int l, int r, int L, int R) { 10 int mid = (l + r) >> 1, M; 11 tmp[mid] = -inf; 12 for(int x = max(L, mid - m); x <= min(mid, R); ++x) 13 if(tmp[mid] < f[i - 1][j - o][o][x] + a[i][mid - x]) 14 tmp[mid] = f[i - 1][j - o][o][x] + a[i][mid - x], M = x; 15 if(l < mid) solve(i, j, o, l, mid - 1, L, M); 16 if(mid < r) solve(i, j, o, mid + 1, r, M, R); 17 } 18 19 int main() { 20 int T; 21 scanf("%d", &T); 22 while(T--) { 23 int n, A, B; 24 scanf("%d %d %d %d", &n, &m, &A, &B); 25 for(int i = 1; i <= n; ++i) 26 for(int j = 1; j <= m; ++j) 27 scanf("%lld", &w[i][j]); 28 for(int i = 1; i <= n; ++i) { 29 sort(w[i] + 1, w[i] + 1 + m); 30 a[i][m] = 0; 31 for(int j = m - 1; j >= 0; --j) a[i][j] = a[i][j + 1] + w[i][j + 1]; 32 } 33 for(int i = 0; i <= n; ++i) 34 for(int j = 0; j <= B; ++j) 35 for(int k = 0; k <= 1; ++k) 36 for(int p = 0; p <= A; ++p) 37 f[i][j][k][p] = -inf; 38 f[0][0][1][0] = 0; 39 for(int i = 1; i <= n; ++i) { 40 for(int j = 0; j <= B; ++j) { 41 // f[i][j][0][k] = max{f[i - 1][j][0][x] + a[i][k - x], f[i - 1][j - 1][1][x] + a[i][k - x]} 42 solve(i, j, 0, 0, A, 0, A); 43 for(int k = 0; k <= A; ++k) f[i][j][0][k] = max(f[i][j][0][k], tmp[k]); 44 if(j >= 1) { 45 solve(i, j, 1, 0, A, 0, A); 46 for(int k = 0; k <= A; ++k) f[i][j][0][k] = max(f[i][j][0][k], tmp[k]); 47 } 48 // f[i][j][1][k] = max{f[i - 1][j][0][k], f[i - 1][j][1][k]} 49 for(int k = 0; k <= A; ++k) f[i][j][1][k] = max(f[i - 1][j][0][k], f[i - 1][j][1][k]); 50 } 51 } 52 LL ans = 0; 53 for(int i = 0; i <= B; ++i) 54 for(int j = 0; j <= 1; ++j) 55 for(int k = 0; k <= A; ++k) 56 ans = max(ans, f[n][i][j][k]); 57 printf("%lld\n", ans); 58 } 59 return 0; 60 } Aguin

?

Problem F. Grab The Tree

談學(xué)姐教我貪心！

1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int main() { 5 int T; 6 scanf("%d", &T); 7 while(T--) { 8 int n, x, sum = 0; 9 scanf("%d", &n); 10 for(int i = 1; i <= n; ++i) scanf("%d", &x), sum ^= x; 11 for(int i = 1; i < n; ++i) { 12 int u, v; 13 scanf("%d %d", &u, &v); 14 } 15 puts(sum ? "Q" : "D"); 16 } 17 return 0; 18 } Aguin

?

Problem G. Interstellar Travel

一眼凸包寫(xiě)的時(shí)候忘了嚴(yán)格增……

1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 200000 + 10; 4 typedef long long LL; 5 LL x[maxn], y[maxn], id[maxn], st[maxn]; 6 bool cmp(LL i, LL j) { 7 if(x[i] != x[j]) return x[i] < x[j]; 8 if(y[i] != y[j]) return y[i] > y[j]; 9 return i < j; 10 } 11 LL cross(LL i, LL j, LL k) {return (x[i] - x[k]) * (y[j] - y[k]) - (x[j] - x[k]) * (y[i] - y[k]);} 12 vector<LL> L; 13 int main() { 14 int T; 15 scanf("%d", &T); 16 while (T--) { 17 int n; 18 scanf("%d", &n); 19 for (int i = 1; i <= n; ++i) scanf("%lld %lld", x + i, y + i), id[i] = i; 20 sort(id + 1, id + 1 + n, cmp); 21 L.clear(); 22 for(int i = 1; i <= n; ++i) if(i == 1 || x[id[i]] > x[id[i-1]]) L.push_back(id[i]); 23 int p = 0; 24 for(int i = 0; i < L.size(); ++i) { 25 while (p >= 2 && cross(st[p], L[i], st[p - 1]) > 0) p--; 26 while (p >= 2 && cross(st[p], L[i], st[p - 1]) == 0 && L[i] < st[p]) p--; 27 st[++p] = L[i]; 28 } 29 for (int i = 1; i <= p; i++) printf("%lld%c", st[i], i == p ? '\n' : ' '); 30 } 31 return 0; 32 } Aguin

?

Problem H. Monster Hunter

cmp一直寫(xiě)不對(duì)被set去重掉了……

1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1e5 + 10; 4 typedef long long LL; 5 LL a[maxn], b[maxn]; 6 vector<int> G[maxn]; 7 8 int fa[maxn], vis[maxn]; 9 void dfs(int x, int f) { 10 fa[x] = f; 11 for(int i = 0; i < G[x].size(); ++i) { 12 int to = G[x][i]; 13 if(to == f) continue; 14 dfs(to, x); 15 } 16 } 17 18 int pa[maxn]; 19 int Find(int x) { 20 return x == pa[x] ? x : pa[x] = Find(pa[x]); 21 } 22 23 struct node { 24 int id; 25 LL a, b; 26 node(LL A = 0, LL B = 0, int ID = 0): a(A), b(B), id(ID) {} 27 friend bool operator < (node A, node B) { 28 if(A.b - A.a > 0 && B.b - B.a <= 0) return true; 29 if(A.b - A.a == 0 && B.b - B.a < 0) return true; 30 if(B.b - B.a > 0 && A.b - A.a <= 0) return false; 31 if(B.b - B.a == 0 && A.b - A.a < 0) return false; 32 if(A.b - A.a > 0) { 33 if(A.a != B.a) return A.a < B.a; 34 return A.id < B.id; 35 } 36 if(A.b != B.b) return A.b > B.b; 37 return A.id < B.id; 38 } 39 }; 40 set<node> S; 41 42 int main() { 43 int T; 44 scanf("%d", &T); 45 while(T--) { 46 int n; 47 scanf("%d", &n); 48 for(int i = 1; i <= n; ++i) G[i].clear(), pa[i] = i, vis[i] = 0; 49 S.clear(); 50 for(int i = 2; i <= n; ++i) 51 scanf("%lld %lld", a + i, b + i), S.insert(node(a[i], b[i], i)); 52 for(int i = 2; i <= n; ++i) { 53 int u, v; 54 scanf("%d %d", &u, &v); 55 G[u].push_back(v), G[v].push_back(u); 56 } 57 dfs(1, 0); 58 LL A = 0, B = 0; 59 for(int i = 1; i < n; ++i) { 60 int x = (*S.begin()).id; 61 S.erase(S.begin()); 62 if(fa[x] == 1 || vis[Find(fa[x])]) { 63 LL t = b[x] + B - a[x] - A; 64 A = max(A, A - B + a[x]), B = A + t; 65 vis[x] = 1; 66 } 67 else { 68 int y = Find(fa[x]); 69 S.erase(S.find(node(a[y], b[y], y))); 70 LL t = b[x] + b[y] - a[x] - a[y]; 71 a[y] = max(a[y], a[y] - b[y] + a[x]), b[y] = a[y] + t; 72 S.insert(node(a[y], b[y], y)); 73 pa[x] = y; 74 } 75 } 76 printf("%lld\n", A); 77 } 78 return 0; 79 } Aguin

?

Problem I. Random Sequence

感覺(jué)還是狀態(tài)不太好想到吧……

1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const LL mod = 1e9 + 7; 5 int gcd[101][101], a[101]; 6 LL f[2][101][101][101]; 7 vector<int> fac[101]; 8 LL v[101]; 9 10 LL fp(LL a, LL b) { 11 LL ret = 1; 12 while (b) { 13 if (b & 1) ret = ret * a % mod; 14 a = a * a % mod; 15 b >>= 1; 16 } 17 return ret; 18 } 19 20 LL inv(LL x) { 21 return fp(x, mod - 2); 22 } 23 24 int main() { 25 for(int i = 1; i <= 100; ++i) 26 for(int j = i; j <= 100; j += i) 27 fac[j].push_back(i); 28 for(int i = 1; i <= 100; ++i) 29 for(int j = 1; j <= 100; ++j) 30 gcd[i][j] = __gcd(i, j); 31 int T; 32 scanf("%d", &T); 33 while(T--) { 34 int n, m, c = 0; 35 scanf("%d %d", &n, &m); 36 for(int i = 1; i <= n; ++i) scanf("%d", a + i), c += a[i] == 0; 37 for(int i = 1; i <= m; ++i) scanf("%lld", v + i); 38 int o = 0; 39 for(int i = 1; i <= m; ++i) { 40 for(int j = 0; j < fac[i].size(); ++j) { 41 for(int k = 0; k < fac[fac[i][j]].size(); ++k) { 42 f[o][i][fac[i][j]][fac[fac[i][j]][k]] = 0; 43 } 44 } 45 } 46 for(int i = 1; i <= m; ++i) { 47 if(a[3] && a[3] != i) continue; 48 for(int j = 1; j <= m; ++j) { 49 if(a[2] && a[2] != j) continue; 50 for(int k = 1; k <= m; ++k) { 51 if(a[1] && a[1] != k) continue; 52 f[o][i][gcd[i][j]][gcd[gcd[i][j]][k]]++; 53 } 54 } 55 } 56 for(int p = 3; p < n; ++p) { 57 for(int i = 1; i <= m; ++i) { 58 for(int j = 0; j < fac[i].size(); ++j) { 59 for(int k = 0; k < fac[fac[i][j]].size(); ++k) { 60 f[o ^ 1][i][fac[i][j]][fac[fac[i][j]][k]] = 0; 61 } 62 } 63 } 64 for(int i = 1; i <= m; ++i) { 65 if(a[p] && a[p] != i) continue; 66 for(int j = 0; j < fac[i].size(); ++j) { 67 if(a[p - 1] && gcd[a[p - 1]][i] != fac[i][j]) continue; 68 for(int k = 0; k < fac[fac[i][j]].size(); ++k) { 69 if(a[p - 2] && gcd[fac[i][j]][a[p - 2]] != fac[fac[i][j]][k]) continue; 70 for(int q = 1; q <= m; ++q) { 71 if(a[p + 1] && a[p + 1] != q) continue; 72 f[o ^ 1][q][gcd[q][i]][gcd[q][fac[i][j]]] = (f[o ^ 1][q][gcd[q][i]][gcd[q][fac[i][j]]] + v[gcd[q][fac[fac[i][j]][k]]] * f[o][i][fac[i][j]][fac[fac[i][j]][k]]) % mod; 73 } 74 } 75 } 76 } 77 o ^= 1; 78 } 79 LL ans = 0; 80 for(int i = 1; i <= m; ++i) { 81 for(int j = 0; j < fac[i].size(); ++j) { 82 for(int k = 0; k < fac[fac[i][j]].size(); ++k) { 83 ans = (ans + f[o][i][fac[i][j]][fac[fac[i][j]][k]]) % mod; 84 } 85 } 86 } 87 printf("%lld\n", ans * fp(inv(m), c) % mod); 88 } 89 return 0; 90 } Aguin

?

Problem J. Rectangle Radar Scanner

快樂(lè)分治，好像每次加完點(diǎn)要?jiǎng)h掉

1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int maxn = 1e5 + 10; 5 const int maxm = 1e6 + 10; 6 LL xl[maxm], xr[maxm], yl[maxm], yr[maxm], P[maxm], MAX[maxm], MIN[maxm]; 7 LL k, y[maxn], w[maxn]; 8 int n; 9 10 // seg 11 const LL INF = 1e18; 12 LL pr[maxn<<2], ma[maxn<<2], mi[maxn<<2]; 13 void gather(int p) { 14 pr[p] = pr[p << 1] * pr[p << 1 | 1] % k; 15 ma[p] = max(ma[p << 1], ma[p << 1 | 1]); 16 mi[p] = min(mi[p << 1], mi[p << 1 | 1]); 17 } 18 void build(int p, int l, int r) { 19 if (l < r) { 20 int mid = (l + r) >> 1; 21 build(p << 1, l, mid); 22 build(p << 1 | 1, mid + 1, r); 23 gather(p); 24 } else pr[p] = 1, mi[p] = INF, ma[p] = -INF; 25 } 26 void modify(int p, int tl, int tr, int x, LL y) { 27 if (tl == tr) { 28 if (!y) pr[p] = 1, mi[p] = INF, ma[p] = -INF; 29 else pr[p] = pr[p] * y % k, mi[p] = min(mi[p], y), ma[p] = max(ma[p], y); 30 return; 31 } 32 int mid = (tl + tr) >> 1; 33 if (x <= mid) modify(p << 1, tl, mid, x, y); 34 else modify(p << 1 | 1, mid + 1, tr, x, y); 35 gather(p); 36 } 37 typedef pair<LL, LL> pii; 38 typedef pair<LL, pii> tr; 39 tr operator + (tr A, tr B) { 40 return {A.first * B.first % k, {max(A.second.first, B.second.first), min(A.second.second, B.second.second)}}; 41 } 42 tr query(int p, int tl, int tr, int l, int r) { 43 if (tl > tr) return {1, {-INF, INF}}; 44 if (tr < l || r < tl) return {1, {-INF, INF}}; 45 if (l <= tl && tr <= r) return {pr[p], {ma[p], mi[p]}}; 46 int mid = (tl + tr) >> 1; 47 return query(p << 1, tl, mid, l, r) + query(p << 1 | 1, mid + 1, tr, l, r); 48 } 49 50 tr ret[maxm]; 51 bool cmp1(int i, int j) {return xl[i] > xl[j];} 52 bool cmp2(int i, int j) {return xr[i] < xr[j];} 53 void solve(int l, int r, vector<int> Q) { 54 int mid = (l + r) >> 1, p; 55 vector<int> QL, QM, QR; 56 for(int i = 0; i < Q.size(); ++i) { 57 int o = Q[i]; 58 if(l != r && xr[o] <= mid) QL.push_back(o); 59 else if(l != r && xl[o] > mid) QR.push_back(o); 60 else QM.push_back(o); 61 } 62 sort(QM.begin(), QM.end(), cmp1); 63 p = mid + 1; 64 for(int i = 0; i < QM.size(); ++i) { 65 int o = QM[i]; 66 while(p > xl[o]) --p, modify(1, 1, n, y[p], w[p]); 67 ret[o] = query(1, 1, n, yl[o], yr[o]); 68 } 69 while(p <= mid) modify(1, 1, n, y[p], 0), p++; 70 p--; 71 sort(QM.begin(), QM.end(), cmp2); 72 for(int i = 0; i < QM.size(); ++i) { 73 int o = QM[i]; 74 while(p < xr[o]) ++p, modify(1, 1, n, y[p], w[p]); 75 ret[o] = ret[o] + query(1, 1, n, yl[o], yr[o]); 76 if(ret[o].second.first == -INF) P[o] = MAX[o] = MIN[o] = 0; 77 else P[o] = ret[o].first, MAX[o] = ret[o].second.first, MIN[o] = ret[o].second.second; 78 } 79 while(p > mid) modify(1, 1, n, y[p], 0), p--; 80 if(!QL.empty()) solve(1, mid, QL); 81 if(!QR.empty()) solve(mid + 1, r, QR); 82 } 83 84 int main() { 85 int T; 86 scanf("%d", &T); 87 while(T--) { 88 scanf("%d", &n); 89 for(int i = 1; i <= n; ++i) scanf("%lld %lld", y + i, w + i); 90 LL m, a0, b0, c0, d0, p, q, r, MOD; 91 scanf("%lld %lld %lld %lld %lld %lld %lld %lld %lld %lld", &m, &a0, &b0, &c0, &d0, &p, &q, &r, &MOD, &k); 92 vector<int> Q; 93 for(int i = 1; i <= m; ++i) { 94 LL ai = (p * a0 + q * b0 + r) % MOD; 95 LL bi = (p * b0 + q * a0 + r) % MOD; 96 LL ci = (p * c0 + q * d0 + r) % MOD; 97 LL di = (p * d0 + q * c0 + r) % MOD; 98 a0 = ai, b0 = bi, c0 = ci, d0 = di; 99 xl[i] = a0 % n + 1, xr[i] = b0 % n + 1; 100 if(xl[i] > xr[i]) swap(xl[i], xr[i]); 101 yl[i] = c0 % n + 1, yr[i] = d0 % n + 1; 102 if(yl[i] > yr[i]) swap(yl[i], yr[i]); 103 Q.push_back(i); 104 } 105 build(1, 1, n), solve(1, n, Q); 106 LL ans = 0; 107 for(int i = 1; i <= m; ++i) ans = ans + (P[i] ^ MAX[i] ^ MIN[i]); 108 printf("%lld\n", ans); 109 } 110 return 0; 111 } Aguin

?

Problem K. Transport Construction

那個(gè)牛逼哄哄的Boruvka？啥玩意兒好像就是每次對(duì)每個(gè)連通塊找到邊權(quán)最小的邊，把這些邊合并一下下，這樣每次連通塊至少減少一半，所以只有l(wèi)ogn次

然后點(diǎn)乘最小就是拿一個(gè)垂線(xiàn)從下往上掃一下，最先碰到的就是投影最小的，所以一定在下凸殼上

然后再每次按連通塊編號(hào)快樂(lè)分治，下凸殼里面是斜率遞增的，所以詢(xún)問(wèn)的向量也按斜率遞增排，雙指針搞搞，好像也沒(méi)有啥要注意的……

1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1e5 + 10; 4 typedef long long LL; 5 typedef pair<int, int> pii; 6 LL X[maxn], Y[maxn]; 7 LL cross(int i, int j, int k) {return (X[i] - X[k]) * (Y[j] - Y[k]) - (Y[i] - Y[k]) * (X[j] - X[k]);} 8 LL dot(int i, int j) {return X[i] * X[j] + Y[i] * Y[j];} 9 10 // UF 11 int fa[maxn]; 12 int Find(int x) { 13 return fa[x] == x ? x : fa[x] = Find(fa[x]); 14 } 15 void Union(int x, int y) { 16 fa[Find(x)] = Find(y); 17 } 18 19 // Tarjan 20 stack<int> S; 21 vector<int> G[maxn], bcc[maxn]; 22 int dfs_clock, dfn[maxn], low[maxn]; 23 int bcc_cnt, bccno[maxn]; 24 void dfs(int u) { 25 dfn[u] = low[u] = ++dfs_clock; 26 S.push(u); 27 for (int i = 0; i < G[u].size(); i++) { 28 int v = G[u][i]; 29 if (!dfn[v]) { 30 dfs(v); 31 low[u] = min(low[u], low[v]); 32 } else if (!bccno[v]) low[u] = min(low[u], dfn[v]); 33 } 34 if (low[u] == dfn[u]) { 35 bcc_cnt++; 36 while (1) { 37 int x = S.top(); 38 S.pop(); 39 bccno[x] = bcc_cnt; 40 bcc[bcc_cnt].push_back(x); 41 if (x == u) break; 42 } 43 } 44 } 45 void find_bcc(int n) { 46 dfs_clock = bcc_cnt = 0; 47 for (int i = 1; i <= n; ++i) dfn[i] = bccno[i] = 0, bcc[i].clear(); 48 for (int i = 1; i <= n; i++) if (!dfn[i]) dfs(i); 49 } 50 51 // D & C 52 LL M[maxn]; 53 pii pr[maxn]; 54 bool cmpx(int i, int j) {return X[i] < X[j];} 55 bool cmpk(int i, int j) {return Y[i] * X[j] < Y[j] * X[i];} 56 vector<int> hull[maxn << 2], line[maxn << 2]; 57 void solve(int p, int l, int r) { 58 hull[p].clear(), line[p].clear(); 59 if(l == r) { 60 line[p] = bcc[l]; 61 sort(line[p].begin(), line[p].end(), cmpx); 62 for(int i = 0; i < line[p].size(); ++i) { 63 int x = line[p][i], sz = hull[p].size(); 64 while(sz > 1 && cross(hull[p][sz - 1], x, hull[p][sz - 2]) <= 0) hull[p].pop_back(), sz--; 65 hull[p].push_back(x); 66 } 67 sort(line[p].begin(), line[p].end(), cmpk); 68 return; 69 } 70 int mid = (l + r) / 2, p1 = 0, p2 = 0; 71 solve(p << 1, l, mid), solve(p << 1 | 1, mid + 1, r); 72 for(int i = 0; i < line[p << 1].size(); ++i) { 73 int x = line[p << 1][i], bx = bccno[x]; 74 while(p1 + 1 < hull[p << 1 | 1].size() && dot(x, hull[p << 1 | 1][p1 + 1]) <= dot(x, hull[p << 1 | 1][p1])) p1++; 75 int y = hull[p << 1 | 1][p1]; 76 LL DOT = dot(x, y); 77 if(DOT <= M[bx]) M[bx] = DOT, pr[bx] = pii(x, y); 78 } 79 for(int i = 0; i < line[p << 1 | 1].size(); ++i) { 80 int x = line[p << 1 | 1][i], bx = bccno[x]; 81 while(p2 + 1 < hull[p << 1].size() && dot(x, hull[p << 1][p2 + 1]) <= dot(x, hull[p << 1][p2])) p2++; 82 int y = hull[p << 1][p2]; 83 LL DOT = dot(x, y); 84 if(DOT <= M[bx]) M[bx] = DOT, pr[bx] = pii(x, y); 85 } 86 p1 = p2 = 0; 87 while(p1 < line[p << 1].size() || p2 < line[p << 1 | 1].size()) { 88 if(p1 == line[p << 1].size()) line[p].push_back(line[p << 1 | 1][p2++]); 89 else if(p2 == line[p << 1 | 1].size() || cmpk(line[p << 1][p1], line[p << 1 | 1][p2])) line[p].push_back(line[p << 1][p1++]); 90 else line[p].push_back(line[p << 1 | 1][p2++]); 91 } 92 p1 = p2 = 0; 93 while(p1 < hull[p << 1].size() || p2 < hull[p << 1 | 1].size()) { 94 int x, sz = hull[p].size(); 95 if(p1 == hull[p << 1].size()) x = hull[p << 1 | 1][p2++]; 96 else if(p2 == hull[p << 1 | 1].size() || cmpx(hull[p << 1][p1], hull[p << 1 | 1][p2])) x = hull[p << 1][p1++]; 97 else x = hull[p << 1 | 1][p2++]; 98 while(sz > 1 && cross(hull[p][sz - 1], x, hull[p][sz - 2]) <= 0) hull[p].pop_back(), sz--; 99 hull[p].push_back(x); 100 } 101 } 102 103 int main() { 104 int T; 105 scanf("%d", &T); 106 while(T--) { 107 LL ans = 0; 108 int n, cnt = 0; 109 scanf("%d", &n); 110 for(int i = 1; i <= n; ++i) scanf("%lld %lld", X + i, Y + i), fa[i] = i, G[i].clear(); 111 while(cnt < n - 1) { 112 find_bcc(n); 113 for(int i = 1; i <= bcc_cnt; ++i) M[i] = 1e18; 114 solve(1, 1, bcc_cnt); 115 for(int i = 1; i <= bcc_cnt; ++i) { 116 int x = pr[i].first, y = pr[i].second; 117 if(Find(x) == Find(y)) continue; 118 Union(x, y), ans += M[i], cnt++; 119 G[x].push_back(y), G[y].push_back(x); 120 } 121 } 122 printf("%lld\n", ans); 123 } 124 return 0; 125 } Aguin

?

Problem L. Visual Cube

甩鍋給談學(xué)姐他竟然寫(xiě)不出來(lái)

1 #include <bits/stdc++.h> 2 using namespace std; 3 4 void printChar(int n, char c) { 5 if (n <= 0) return; 6 while (n--) putchar(c); 7 return; 8 } 9 10 int main () { 11 int a, b, c, N; 12 scanf("%d", &N); 13 while (N--) { 14 scanf("%d%d%d", &a, &b, &c); 15 int pnts; 16 for (int i = 0; i < 2 * c + 2 * b + 1; i++) { 17 printChar(2 * b - i, '.'); 18 for (int j = 0; j < 2 * a + 1; j++) { 19 if (i % 2) 20 putchar((j%2)?'.':((2 * b > i)?'/':'|')); 21 else 22 putchar((j%2)?'-':'+'); 23 } 24 pnts = 2 * a; 25 if (2 * b > i) pnts += 2 * b - i; 26 for (int j = pnts; j < 2 * a + 2 * b; j++) { 27 if (i >= 2 * c + 1 && j >= 2 * (b + a + c) - i) 28 putchar('.'); 29 else 30 if (i % 2) 31 putchar((j%2)?'|':'/'); 32 else 33 putchar((j%2)?'+':'.'); 34 } 35 puts(""); 36 } 37 } 38 } 摸瑜瑜

?

Problem M. Walking Plan

其實(shí)應(yīng)該先做一遍Floyd……

1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const LL INF = 1e18; 5 LL a[101][55][55], b[101][55][55]; 6 7 int main() { 8 int T; 9 scanf("%d", &T); 10 while(T--) { 11 int n, m, q; 12 scanf("%d %d", &n, &m); 13 for(int i = 1; i <= n; ++i) 14 for(int j = 1; j <= n; ++j) 15 b[1][i][j] = INF; 16 for(int i = 1; i <= m; ++i) { 17 int u, v, w; 18 scanf("%d %d %d", &u, &v, &w); 19 b[1][u][v] = min(b[1][u][v], (LL) w); 20 } 21 for(int j = 1; j <= n; ++j) 22 for(int k = 1; k <= n; ++k) 23 for(int p = 1; p <= n; ++p) 24 b[1][k][p] = min(b[1][k][p], b[1][k][j] + b[1][j][p]); 25 for(int i = 2; i <= 100; ++i) { 26 for(int j = 1; j <= n; ++j) 27 for(int k = 1; k <= n; ++k) 28 b[i][j][k] = INF; 29 for(int j = 1; j <= n; ++j) 30 for(int k = 1; k <= n; ++k) 31 for(int p = 1; p <= n; ++p) 32 b[i][k][p] = min(b[i][k][p], b[i - 1][k][j] + b[1][j][p]); 33 } 34 for(int j = 1; j <= n; ++j) 35 for(int k = 1; k <= n; ++k) 36 a[1][j][k] = b[100][j][k]; 37 for(int i = 2; i <= 100; ++i) { 38 for(int j = 1; j <= n; ++j) 39 for(int k = 1; k <= n; ++k) 40 a[i][j][k] = INF; 41 for(int j = 1; j <= n; ++j) 42 for(int k = 1; k <= n; ++k) 43 for(int p = 1; p <= n; ++p) 44 a[i][k][p] = min(a[i][k][p], a[i - 1][k][j] + a[1][j][p]); 45 } 46 scanf("%d", &q); 47 while(q--) { 48 int s, t, k; 49 scanf("%d %d %d", &s, &t, &k); 50 int A = (k - 1) / 100, B = k % 100 == 0 ? 100 : k % 100; 51 LL ans = INF; 52 if(A) for(int i = 1; i <= n; ++i) ans = min(ans, a[A][s][i] + b[B][i][t]); 53 else ans = min(ans, b[B][s][t]); 54 printf("%lld\n", ans == INF ? -1 : ans); 55 } 56 } 57 return 0; 58 } Aguin

?

轉(zhuǎn)載于:https://www.cnblogs.com/Aguin/p/9399842.html

總結(jié)

以上是生活随笔為你收集整理的2018 Multi-University Training Contest 3的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。