Loading... > 仅为个人存档~ | Solved | A | B | C | D | E | F | G | H | I | J | K | L | M | | :----: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | | 8/13 | O | O | . | O | O | . | . | O | O | . | O | . | O | - O for passing during the contest - Ø for passing after the contest - ! for attempted but failed - · for having not attempted yet ## A. Sequence (xzm2019, 0:06, +2) 其实题目很简单，就是判断一下$abs(A-B) \leq 1\ \&\&\ (A+B>0)$即可 一开始没想到后面那个，成功拿了全场最快提交（ ```cpp #include <bits/stdc++.h> using namespace std; int main() { int T; scanf("%d",&T); while (T--) { long long a,b; scanf("%lld%lld",&a,&b); if (abs(a - b) <= 1 && (!(a == 0 && b == 0))) printf("YES\n"); else printf("NO\n"); } return 0; } ``` ## B. Key (SingleZombie, 1:14, +3) 直接按照顺序去买钥匙，如果满了就优先丢弃下一次出现晚的钥匙即可，用STL维护。 ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 +5; typedef pair<int, int> pii; queue<int> graph[MAXN]; int crt[MAXN]; int arr[MAXN]; int main() { int t; scanf("%d", &t); while (t--) { for (int i = 0; i < MAXN; i++) { while (!graph[i].empty()) { graph[i].pop(); } } int n, m; scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { int a; scanf("%d", &a); arr[i] = a; graph[a].push(i); crt[a] = -1; } int ans = 0; set<pii> st; for (int i = 0; i < n; i++) { int id = arr[i]; //cout << crt[id] << " " << id << endl; if (st.count({crt[id], id})) { st.erase({crt[id], id}); graph[id].pop(); if (!graph[id].empty()) { crt[id] = graph[id].front(); st.insert({crt[id], id}); } continue; } ans++; if (st.size() == m) { st.erase(prev(st.end())); } graph[id].pop(); if (graph[id].empty()) { continue; } st.insert({graph[id].front(), id}); crt[id] = graph[id].front(); } printf("%d\n", ans); } return 0; } ``` ## D. Wander (SingleZombie, 3:50, +) 题目要求从每个点出发的最小时间，如果有$n$个人肯定是要$n-1$圈然后最后找个最近的，队友说STL瞎搞就行了。 ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 +5; int sz[MAXN], minv[MAXN]; int main() { int n, m; scanf("%d%d", &n, &m); int maxSize = 0; memset(minv, 0x3f, sizeof(minv)); for (int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); sz[u]++; maxSize = max(maxSize, sz[u]); if (v < u) { v += n; } minv[u] = min(minv[u], v); } multiset<int> st; for (int i = 1; i <= n; i++) { if (sz[i] == maxSize) { st.insert(minv[i]); //cout << minv[i] << endl; } } for (int i = 1; i <= n; i++) { //cout << i << " " << *prev(st.end()) << endl; int ans = (maxSize - 1) * n + (*prev(st.end()) - i); if (sz[i] == maxSize) { st.erase(st.find(minv[i])); st.insert(minv[i] + n); } printf("%d%c", ans, i == n ? '\n' : ' '); } return 0; } ``` ## E.Race Car (xzm2019, 4:02, +8) 先用floyd跑一遍最短路，然后把整个图变成$K+2$个点，状压dp即可。 一开始读入忘记存双向边然后血WA…… ```cpp #include <bits/stdc++.h> using namespace std; long long mapp[205][205]; long long tmap[15][15]; long long dp[15][1<<15]; int tu[15]; int main() { int T; scanf("%d",&T); while (T--) { int n,m; scanf("%d%d",&n,&m); memset(mapp,0x3f,sizeof(mapp)); for (int i = 1; i <= m; i++) { int u,v; long long c; scanf("%d%d%lld",&u,&v,&c); mapp[v][u] = mapp[u][v] = min(mapp[u][v], c); } for (int i = 1; i <= n; i++) mapp[i][i] = 0; for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) mapp[i][j] = mapp[j][i] = min(mapp[i][j], mapp[i][k] + mapp[k][j]); int K; scanf("%d",&K); if (K == 0) { if (mapp[1][n] == mapp[0][0]) printf("-1\n"); else printf("%lld\n",mapp[1][n]); continue; } int s = K, t = K + 1; memset(tmap, 0x3f, sizeof(tmap)); memset(tu,0,sizeof(tu)); for (int i = 0; i < K; i++) { scanf("%d",&tu[i]); tmap[i][s] = tmap[s][i] = mapp[1][tu[i]]; tmap[i][t] = tmap[t][i] = mapp[n][tu[i]]; } for (int i = 0; i < K; i++) for (int j = 0; j < K; j++) tmap[i][j] = mapp[tu[i]][tu[j]]; memset(dp,0x3f,sizeof(dp)); dp[s][1<<s] = 0; for (int j = 0; j < (1 << t); j++) for (int i = 0; i < t; i++) { if (j & (1 << i)); else continue; for (int k = 0; k < t; k++) { if (k == i) continue; if (j & (1 << k)) { dp[i][j] = min(dp[i][j], dp[k][j ^ (1 << i)] + tmap[i][k]); } } } long long ans = 0x3f3f3f3f3f3f3f3f; for (int i = 0; i < t; i++) { ans = min(ans, dp[i][(1 << t) - 1] + tmap[i][t]); } if (ans == 0x3f3f3f3f3f3f3f3f) printf("-1\n"); else printf("%lld\n",ans); } } ``` ## H. Melborp Kcaspank (xzm2019, 1:22, +2) 这题很明显是一个分数规划，直接二分答案即可，第一发WA了，一开始没找到哪里写残了，于是又想了个dp算法（总觉得题目教背包是在指引dp）。$dp[i][j]$表示前$i$个物品里选$j$个的最大平均值，直接转移即可，注意精度问题和爆`long long`问题。 然后dp写残又WA了一发，在后面疯狂修对两种做法然后交了4发rejudge都过了。 - 二分版本： ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 1e3 +5; const long double EPS = 1e-8; long long v[MAXN],w[MAXN]; long double t[MAXN]; int n,k; pair<long double, int> tmp[MAXN]; bool check(long double x) { for (int i = 1; i <= n; i++) t[i] = v[i] - x * w[i]; sort(t + 1, t + n + 1, greater<long double>()); long double sum = 0; for (int i = 1; i <= k; i++) sum += t[i]; return sum > -EPS; } bool cmp(const pair<long double, int> & a, const pair<long double, int> & b) { return a.first > b.first; } int main() { scanf("%d%d",&n,&k); for (int i = 1; i <= n; i++) scanf("%lld%lld",&v[i],&w[i]); long double l = 0, r = 1e12; for (int i = 1; i <= 200; i++) { long double mid = (l + r) / 2.0; if (check(mid)) l = mid; else r = mid; } long double mid = (l + r) / 2.0; //printf("%.6LF %.6LF %.6LF\n",l,r,mid); for (int i = 1; i <= n; i++) { tmp[i].first = v[i] - mid * w[i]; tmp[i].second = i; } sort(tmp + 1, tmp + n + 1, cmp); long long sumv = 0, sumw = 0; for (int i = 1; i <= k; i++) { sumv += v[tmp[i].second]; sumw += w[tmp[i].second]; } long long xx = __gcd(sumv,sumw); sumv /= xx; sumw /= xx; if (sumw == 1) printf("%lld\n",sumv); else printf("%lld\\%lld\n",sumv,sumw); return 0; } ``` - dp版本： ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 1e3 +5; long long f[2][MAXN][MAXN]; long long v[MAXN],w[MAXN]; int n,k; void print() { for (int i = 1; i <= n; i++) for (int j = 0; j <= k; j++) printf("%lld\\%lld%c",f[0][i][j],f[1][i][j],j == k? '\n' : ' '); } int main() { scanf("%d%d",&n,&k); for (int i = 1; i <= n; i++) scanf("%lld%lld",&v[i],&w[i]); for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) { long long nowp = f[0][i - 1][j - 1] + v[i], nowq = f[1][i - 1][j - 1] + w[i]; long long lastp = f[0][i - 1][j], lastq = f[1][i - 1][j]; //printf("%d %d %lld\\%lld %lld\\%lld\n",i,j,nowp,nowq,lastp,lastq); if ((long double)nowp * lastq >= (long double)nowq * lastp) { f[0][i][j] = nowp; f[1][i][j] = nowq; } else { f[0][i][j] = lastp; f[1][i][j] = lastq; } } long long p = f[0][n][k], q = f[1][n][k]; long long tmp = __gcd(p,q); p /= tmp; q /= tmp; if (q == 1) printf("%lld\n",p); else printf("%lld\\%lld\n",p,q); return 0; } ``` ## I. Poeroz & YYOJ (zhanggengchen, 0:23, +) 直接dp即可，只有三个字母构成，这里用$dp[i][j][0/1]$标识到第$i$位，前一个字母是$j$，当前是否出现过`AC`。 ```cpp #include <bits/stdc++.h> using namespace std; const int maxn = 1000000+10; const int mo = 1e9+7; int n; int i,j,k; int f[maxn][3][2]; int main() { scanf("%d",&n); for (j=0;j<3;j++) f[1][j][0]=1; for (i=1;i<n;i++) { for (j=0;j<3;j++) { for (k=0;k<3;k++) { if (j==0&&k==1) { f[i+1][k][1]=(f[i+1][k][1]+f[i][j][0])%mo; f[i+1][k][1]=(f[i+1][k][1]+f[i][j][1])%mo; } else if (j==2&&k==0) { } else { f[i+1][k][1]=(f[i+1][k][1]+f[i][j][1])%mo; f[i+1][k][0]=(f[i+1][k][0]+f[i][j][0])%mo; } } } } int ans=0; for (j=0;j<3;j++) { ans=(ans+f[n][j][1])%mo; } printf("%d\n",ans); return 0; } ``` ## K. Candy & Magic (zhanggenchen, 3:00, +1) 当时根本没细想，就瞎搞了一下就出来了…… ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 1e3 +5; int n; int i,j,k; int a[MAXN],b[MAXN]; int ans; int main() { while (scanf("%d",&n)!=EOF) { for (i=1;i<=n;i++) scanf("%d",&a[i]); for (i=1;i<=n;i++) b[i]=a[i]; ans=-1000000000; for (i=1;i<=n;i++) { for (k=-100;k<=100;k++) { int cur=0; if (k==a[i]) continue; for (j=1;j<=n;j++) b[j]=a[j]; b[i]=k; for (j=1;j<=n;j+=2) cur+=max(b[j]-b[j+1],b[j+1]-b[j]); ans=max(ans,cur); } } printf("%d\n",ans); } return 0; } ``` ## M. Deadlock (SingleZombie, 2:27, +3) 直接根据题目的要求加边，然后判断是否有环即可。 ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 1e3 +5; int rT[MAXN]; vector<int> graph[MAXN]; pair<int, int> qs[100005]; bool vis[MAXN]; int inDegree[MAXN]; int main() { int t; scanf("%d", &t); while (t--) { int n, m, k; scanf("%d%d%d", &n, &m, &k); bool yes = true; for (int i = 0; i < m; i++) { scanf("%d", &rT[i]); } for (int i = 0; i < k; i++) { int ct, cr; scanf("%d%d", &ct, &cr); qs[i] = {ct, cr}; } { for (int i = 0; i < n; i++) { graph[i].clear(); vis[i] = false; inDegree[i] = 0; } for (int i = 0; i < k; i++) { int ct = qs[i].first, cr = qs[i].second; if (rT[cr] == -1) { //rT[cr] = ct; } else { int u = ct, v = rT[cr]; graph[u].push_back(v); inDegree[v]++; } } queue<int> que; int tmp = 0; for (int i = 0; i < n; i++) { if (inDegree[i] == 0) { que.push(i); } } while (!que.empty()) { int u = que.front(); que.pop(); tmp++; for (int i = 0; i < graph[u].size(); i++) { int v = graph[u][i]; if (--inDegree[v] == 0) { que.push(v); } } } if (tmp == n) { } else { yes = false; } } if (!yes) { puts("YES"); } else { puts("NO"); } } return 0; } ``` Last modification：April 22nd, 2019 at 12:36 am © 允许规范转载 Support If you think my article is useful to you, please feel free to appreciate ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
账号带回来了，回来登陆了下就复制下来了