比赛链接
今天发挥正常，昨天不在状态……
花了很久A了第一题
第二题打了30分暴力
第三题投机取巧输出test1答案（连暴力都不知道怎么打，太弱了）
2585分和4个人并列rank3
还行吧
LXL的雕像
x 可以为任意非负实数。
lxl想在土地上摆尽可能多的雕像，请你告诉他此时 x 的取值应为多少。
一行三个正整数表示 l,n,m。
一行一个实数 x ，精确到小数点后五位。 如果无法摆下雕像，输出-1。
2 18 13
0.50000
这道题算是复习了拓展gcd解不定方程
我的做法和讲解人不同，是用exgcd做的
我一开始看到这道题，以为是二分
因为当时想到x越小，雕像肯定越多
所以我就去二分x
写完然后发现，貌似x的取值并不连续
我们设雕像的横着有a个，竖着有b个
符合条件的x值只有很少的一部分，对于每个x有唯一的a与b对应。
这个时候我就想去求最大的（a,b）下的x
然后我就去推公式
显然有
al + a(x + 1) = n
bl + b(x + 1) = m
可以求得
x = (n - al) / (a+1)
x = (m - al) / (b+1)
把x消去
即(n - al) / (a+1) = (m - al) / (b+1)
化简可得
a(m + l) - (n + l)b = n - m
这里只有a和b是不知道的
想到了什么？
拓展gcd求不定方程
显然a越大，b也越大
那么可以求出最大的a，然后通过这个a可以求出x，x即答案
那么a的限制条件是什么
显然有a * l < n
那么a < n / l (向下取整)
所以我们可以通过调整解来取得最大的a
最后注意要特判一下n <= l 和 m <= l是无解的，直接输出-1
#include<bits/stdc++.h> #define REP(i, a, b) for(register int i = (a); i < (b); i++) #define _for(i, a, b) for(register int i = (a); i <= (b); i++) using namespace std; void exgcd(int a, int b, int& d, int& x, int& y) { if(!b) { d = a; x = 1; y = 0; return; } else { exgcd(b, a % b, d, y, x); y -= x * (a / b); } } int main() { int l, n, m; scanf("%d%d%d", &l, &n, &m); if(n <= l || m <= l) { puts("-1"); return 0; } int A, B, K, d, x, y; A = m + l, B = -(n + l), K = n - m; exgcd(A, B, d, x, y); if(K % d != 0) { puts("-1"); return 0; } x *= K / d; int mod = abs(B / d); x = (x % mod + mod) % mod; int max_x = n / l; if(n % l == 0) max_x--; int t = (max_x - x) / mod; x = x + t * mod; if(n - x * l <= 0) puts("-1"); else printf("%.6lf\n", ((double)n - x * l) / (x + 1)); return 0; }
XYK的音游
在 0 时刻xyk可以把鼠标放在任意位置。鼓点出现的时刻大于 0 。保证同一时间不会有两个鼓点。由于这款音游并不看重连击，xyk希望分数尽可能高就好。请你帮助他计算他能获得的最高分数。
对于 50% 的数据， n×m≤106 。
对于 100% 的数据， n,m≤100000,p≤5,ti≤1000000 。
第一行三个正整数 n,m,p。 接下来 m 行每行三个正整数 t_i,w_i,x_i 描述第 i 个鼓点。
一行一个整数表示最大分数。
5 5 1 2 42 4 3 23 4 1 70 4 2 31 5 1 85 5
150
觉得第三题比第二题简单一点，先写第三题
考试的时候给这道题留的时间不多
感觉是dp，但是因为时间不多没有深入去想，只想打打暴力
然而最后暴力都没打出来
这一题其实dp方程很好想
50分的数据说明可以有一个O（nm）的做法
可以设f[i]为处理了前i个鼓点，第i个一定选的最高分数
如果按照时间排序的话，那么有
f[i] = w[i] + f[j] (|x[i]-x[j]| <= p(t[i]-t[j]))
如果给我多点时间，我估计只能想到这
接下来的操作就非常秀了
可以发现，如果不按照时间排序，就按照输入的顺序，这个方程仍然成立
f[i] = w[i] +max(f[j]) (|x[i]-x[j]| <= p(t[i]-t[j]))
因为如果j的时间大于i的时间，那么这个条件 (|x[i]-x[j]| <= p(t[i]-t[j]))不可能成立
也就是说这个方程已经把按照时间排序这一步给省掉了。
那么我们是不是可以排其他东西来优化呢？
目前还看不出来，我们继续分析
这个做法主要的时间花在求max(f[j])要O（n）的时间
我们能不能优化成O（logn）
我们把绝对值拆开（这一步很骚）
可以得到
-p(t[i]-t[j]) <= x[i] - x[j] <= p(t[i]-t[j])
这里i和j是混在一起的，我们试着把i放在不等式的一边，j放在不等式的另外一边
-p(t[i]-t[j]) <= x[i] - x[j]
变成
pt[j] + x[j] <= pt[i] + x[i]
同样
p(t[i]-t[j]) >= x[i] - x[j]
变成
pt[i]-x[i]>=pt[j]-x[j]
那么
对于pt[i]-x[i]>=pt[j]-x[j]，可以一开始排序完成
对于pt[j] + x[j] <= pt[i] + x[i]，用树状数组优化，把pt[i] + x[i]当作下标，dp值作为值
和用树状数组求LIS的思路很像
那么这道题就可以优化到nlogn了。
注意排序的时候如果第一个条件相等，就排第二个条件。否则会WA5个点（在这卡了好久）
#include<bits/stdc++.h> #define REP(i, a, b) for(register int i = (a); i < (b); i++) #define _for(i, a, b) for(register int i = (a); i <= (b); i++) using namespace std; const int MAXN = 1e5 + 10; int f[MAXN], dp[MAXN], b[MAXN]; int n, m, p, N, ans; struct node { int t, w, x, k; bool operator < (const node& rhs) const { return p * t - x < p * rhs.t - rhs.x || p * t - x == p * rhs.t - rhs.x && p * t + x < p * rhs.t + rhs.x; } }a[MAXN]; void read(int& x) { int f = 1; x = 0; char ch = getchar(); while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); } while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } x *= f; } inline int lowbit(int x) { return x & (-x); } void motify(int x, int p) { for(; x <= N; x += lowbit(x)) f[x] = max(f[x], p); } int get_max(int x) { int res = 0; for(; x; x -= lowbit(x)) res = max(res, f[x]); return res; } int main() { read(n); read(m); read(p); REP(i, 0, m) { read(a[i].t), read(a[i].w), read(a[i].x); a[i].k = p * a[i].t + a[i].x; } sort(a, a + m); _for(i, 0, m) b[i] = a[i].k; sort(b, b + m); N = unique(b, b + m) - b; REP(i, 0, m) a[i].k = lower_bound(b, b + N, a[i].k) - b + 1; REP(i, 0, m) { dp[i] = get_max(a[i].k) + a[i].w; ans = max(ans, dp[i]); motify(a[i].k, dp[i]); } printf("%d\n", ans); return 0; }
ZYZ的游戏
zyz希望得到的森林中的最长路径尽可能小。zyz当然知道啦，但他想考考你这个最小值是多少。
对于 60% 的数据， n,k≤50000 。
对于 100% 的数据， n,k≤400000 。
第一行两个整数 n,k。 接下来 n-1 行，每行两个正整数 x,y ，描述一条树边 (x,y)。
一行一个整数，最长路径的表示最小值。
6 2 1 2 1 3 1 4 2 5 3 6
1
比赛的时候打了个30分暴力
#include<bits/stdc++.h> #define REP(i, a, b) for(register int i = (a); i < (b); i++) #define _for(i, a, b) for(register int i = (a); i <= (b); i++) using namespace std; const int MAXN = 4e5 + 10; struct Edge{ int to, next, w; }; Edge e[MAXN<<1]; int head[MAXN], tot, o, cnt; int vis[MAXN], n, m, k; void read(int& x) { int f = 1; x = 0; char ch = getchar(); while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); } while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } x *= f; } void AddEdge(int to, int from) { e[tot] = Edge{to, head[from], 1}; head[from] = tot++; } int dfs(int u) { vis[u] = 1; int max1 = 0, max2 = 0; for(int i = head[u]; ~i; i = e[i].next) { int v = e[i].to; if(vis[v] || !e[i].w) continue; int now = dfs(v) + 1; if(now > max1) max2 = max1, max1 = now; else if(now > max2) max2 = now; } cnt = max(cnt, max1 + max2); return max1; } int num(int x) { return !x ? 0 : 1 + num(x & (x - 1)); } int main() { memset(head, -1, sizeof(head)); tot = 0; read(n); read(k); m = n - 1; REP(i, 0, m) { int u, v; read(u); read(v); u--; v--; AddEdge(u, v); AddEdge(v, u); } int ans = 1e9; REP(S, 0, 1 << m) { if(num(S) != k) continue; REP(i, 0, m) { if(S & (1 << i)) { e[2 * i].w = 0; e[2 * i + 1].w = 0; } else { e[2 * i].w = 1; e[2 * i + 1].w = 1; } } int t = 0; memset(vis, 0, sizeof(vis)); REP(i, 0, n) if(!vis[i]) { cnt = 0; dfs(i); t = max(t, cnt); } ans = min(ans, t); } printf("%d\n", ans); return 0; }
这道题还是很精彩的。
首先最长路径尽可能小可以想到二分答案（智障的我没有想到，对二分不够敏感）
对于每一个二分值ans可以做一次树形dp
每次把路径长度要超过ans的子树删掉
这里有个小优化，可以O（n）完成这个过程
把子树的路径分为大于ans/2以及小于等于ans/2的
如果是大于ans / 2，只留下一个，因为如果大于等于两个，加起来就会大于ans
对于小于等于ans/2的全部留下，同时记录此时最长路径
那么最后要考虑要不要打大于ans/2的剩下的那一个删掉
我们就比较大于ans/2里面剩下的（也就是最小的）和小于等于ans/2最大的加起来
看有没有大于ans，如果大于，那么剩下的唯一一个的大一ans/2的就也要删掉
这样就可以O（n）的维护这个过程。
如果不这么做的话就只能排序来比较，复杂度是O（logn）
所以二分O（logn），树形dp O（n），总复杂度O（nlogn）
注意一定要在纸上画图想清楚每一个细节，然后就可以一遍AC了
#include<bits/stdc++.h> #define REP(i, a, b) for(register int i = (a); i < (b); i++) #define _for(i, a, b) for(register int i = (a); i <= (b); i++) using namespace std; const int MAXN = 4e5 + 10; struct Edge{ int to, next; }; Edge e[MAXN << 1]; int head[MAXN], dp[MAXN], d[MAXN], tot; int n, m, k; void read(int& x) { int f = 1; x = 0; char ch = getchar(); while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); } while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } x *= f; } void AddEdge(int to, int from) { e[tot] = Edge{to, head[from]}; head[from] = tot++; } void dfs(int u, int fa, int ans) { int cnt = 0, mind = 1e9, maxd = 0; for(int i = head[u]; ~i; i = e[i].next) { int v = e[i].to; if(v == fa) continue; dfs(v, u, ans); dp[u] += dp[v]; if(d[v] + 1> ans / 2) { cnt++; mind = min(mind, d[v] + 1); } else maxd = max(maxd, d[v] + 1); } if(cnt) { if(mind + maxd > ans) dp[u] += cnt, d[u] = maxd; else dp[u] += cnt - 1, d[u] = mind; } else d[u] = maxd; } bool check(int ans) { memset(dp, 0, sizeof(dp)); memset(d, 0, sizeof(d)); dfs(1, -1, ans); return dp[1] <= k; } int main() { memset(head, -1, sizeof(head)); tot = 0; read(n); read(k); REP(i, 1, n) { int u, v; read(u); read(v); AddEdge(u, v); AddEdge(v, u); } int l = -1, r = n - 1; while(l + 1 < r) { int m = (l + r) >> 1; if(check(m)) r = m; else l = m; } printf("%d\n", r); return 0;
总结
（1）拓展gcd，无解特判
（2）二分答案，树形dp，ans/2优化
（3）dp，排序，拆绝对值，树状数组优化