「CF1240X」Codeforces Round #591 (Div. 1)
A. Save the Nature
二分答案，计算一下 x% y% (x + y)% 的票的数量，贪心地让贵的比例最高
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; ll x, y, a, b; int p[200005]; ll k; int gcd(int a, int b) { return b == 0? a: gcd(b, a%b); } bool check(ll m) { ll ta = m / a, tb = m / b, tc = m / (a * b / gcd(a, b)); ll sum = 0; for(int i = 1; i <= tc; i++) sum += p[i] / 100 * (x + y); for(int i = 1; i <= ta - tc; i++) sum += p[i + tc] / 100 * x; for(int i = 1; i <= tb - tc; i++) sum += p[i + ta] / 100 * y; return sum >= k; } int main() { int T = read(); while(T--) { n = read(); for(int i = 1; i <= n; i++) p[i] = read(); x = read(), a = read(); y = read(), b = read(); if(x < y) { swap(x, y); swap(a, b); } k = read(); sort(p + 1, p + n + 1, greater<int>()); int ans = -1; int l = 1, r = n; while(l <= r) { int mid = (l + r) >> 1; if(check(mid)) ans = mid, r = mid - 1; else l = mid + 1; } cout << ans << endl; } return 0; } |
B. Sequence Sorting
离散化以后，则不用移动的数的数值是连续的一段，递推一下最长连续的序列，或者双指针实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } set<int> st; int n; int a[300005]; int mn[300005], mx[300005], ans[300005]; int main() { int T = read(); while(T--) { n = read(); st.clear(); int tot = 0; for(int i = 1; i <= n; i++) mx[i] = mn[i] = ans[i] = 0; st.insert(0); for(int i = 1; i <= n; i++) { a[i] = read(); st.insert(a[i]); } for(int i = 1; i <= n; i++) { int x = a[i]; if(!mn[x]) { tot++; mn[x] = i; } mx[x] = i; } int ANS = 0; for(int i = 1; i <= n; i++) { int x = a[i]; int t = *(--st.lower_bound(x)); if(i == mn[x]) { if(mn[x] < mx[t]) { ans[x] = 1; continue; } ans[x] = ans[t] + 1; ANS = max(ANS, ans[x]); } } cout << tot - ANS << endl; } return 0; } |
C. Paint the Tree
每个点只能选择不超过 𝑘 个相连的边，dp 一下，f[x] 表示选了 x 和其父亲的边，g[x] 表示没选
转移的时候，贪心选收益前 k 大的边
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n, k, cnt; int last[500005]; struct edge{ int next, to, v; }e[1000005]; ll f[500005], g[500005]; // colored, no colored; ll st[500005], top; void dfs(int x, int fa) { for(int i = last[x]; i; i = e[i].next) { int y = e[i].to, w = e[i].v; if(y == fa)continue; dfs(y, x); } top = 0; ll sum = 0; for(int i = last[x]; i; i = e[i].next) { int y = e[i].to, w = e[i].v; if(y == fa)continue; ll d = f[y] + w - g[y]; st[++top] = d; sum += g[y]; } sort(st + 1, st + top + 1, greater<ll>()); g[x] = f[x] = sum; for(int i = 1; i <= k && i <= top; i++) { if(st[i] <= 0) break; g[x] += st[i]; if(i <= k - 1) f[x] += st[i]; } } int main() { int T = read(); while(T--) { n = read(), k = read(); cnt = 0; for(int i = 1; i <= n; i++) last[i] = f[i] = g[i] = 0; for(int i = 1; i < n; i++) { int u = read(), v = read(), w = read(); e[++cnt].to = v; e[cnt].next = last[u]; last[u] = cnt; e[cnt].v = w; e[++cnt].to = u; e[cnt].next = last[v]; last[v] = cnt; e[cnt].v = w; } dfs(1, 0); cout << g[1] << endl; } return 0; } |
计数器 9786079
OI 课件=>
OI 课件=>
黄学长是拿小号交的？
我是自己的号交的
昨晚的比赛黄学长咋只过了一题就不干了啊，B题面后来改了啊。
因为打不开题目
加个QQ好友吧。。我一般都会保存pdf题面的，一开始比赛就打开所有的题面再存为pdf
598460606