Contest Info
| Solved | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| 4/6 | O | O | Ø | Ø |
- O 在比赛中通过
- Ø 赛后通过
- ! 尝试了但是失败了
- - 没有尝试
Solutions
C. Linova and Kingdom
题意：
给定一颗以$1$为根的树，现在要选定$k$个结点为黑点，一个黑点的贡献为从他出发到根节点经过的白点数量
问黑点贡献总和最大为多少。
思路：
- 最直接的想法黑点肯定是位于深度越深的点越好，我们会得到这样一个性质：假设我们选择了一个点，那么该点的所有后代也将会被选择（因为子节点的深度比父节点大，必然优先选完所有子节点才会选他的父节点）。
- 一个黑点产生的贡献为其深度减去到根路径中黑点的数量。
- 直接按照上述思路贪心不好思考，考虑转化一下贡献的计算方法：我们减去黑点的数量时在其祖先结点再减。也就是说每个黑点会减去其子树$size$。
- 那么对于所有点按照$deep−size$进行排序，从大到小贪心选即可。
因为一个点选择了所有子树也会被选，并且显然子树的$deep−size$更大，所以容易证明这种贪心是正确的。
比赛的时候我就是很简单的按照深度贪心，写完测试的时候发现这明显是错的。想想后觉得添加黑点会对在它下方的点造成影响就感觉超级麻烦，的确没想到的有两点：1.一个点选择了所有子树也会被选(这个很关键). 2.能把对答案的贡献转化到父节点，这题想法还是很妙的。
#include <cstdio> #include <cstring> #include <algorithm> #define ll long long using namespace std; const int maxn = 2e5+100; int n, k, u, v; int t, head[maxn], dep[maxn], siz[maxn]; int ans[maxn]; struct node{ int to, nxt; }e[maxn<<1]; bool cmp(int a, int b){ return a > b; } void add(int u, int v){ e[++t].nxt = head[u]; e[t].to = v; head[u] = t; } void dfs(int u, int fa){ siz[u] = 1; for(int i = head[u]; i; i = e[i].nxt){ int v = e[i].to; if(v==fa) continue; dep[v] = dep[u] + 1, dfs(v, u); siz[u] += siz[v]; } ans[u] = dep[u] - siz[u] + 1; } int main(){ scanf("%d%d", &n, &k); for(int i = 1; i <= n-1; i++){ scanf("%d%d", &u, &v); add(u, v), add(v, u); } dfs(1, 0); sort(ans+1, ans+1+n, cmp); ll res = 0; for(int i = 1; i <= k; i++) res += ans[i]; printf("%lld", res); }
D.Xenia and Colorful Gems
题意：
从数组$a,b,c$中分别找到三个数$x,y,z$使得$(x−y)^2+(y−z)^2+(z−x)^2$最小
思路：
我最开始的想法是，固定$b[i]$，从$a$和$c$中找距离$b[i]$最近的数更新$ans$就可以了。但是这样又有个问题，就是距离$b[i]$最近的两个数之间的距离未必是最小的，所以这样还是有问题的。
有个博主给出的思想我觉得是可行易懂的：
观察可以得到，答案的三个数字肯定是从小到大的，两边的数肯定是对应集合中到中间的那个数的距离最小的，但是中间的那个数是哪个集合的呢，对此我们就可以进行枚举，反正才三个数组
#include <cstdio> #include <cstring> #include <algorithm> #define ll long long #define inf 9e18 using namespace std; const int maxn = 1e5+100; int T, na, nb, nc; ll a[maxn], b[maxn], c[maxn], ans; ll cal(ll x, ll y, ll z){ return (x-y)*(x-y)+(y-z)*(y-z)+(z-x)*(z-x); } void sovle(ll *x, int nx, ll *y, int ny, ll *z, int nz){ for(int i = 1; i <= ny; i++){ int px1 = lower_bound(x+1, x+1+nx, y[i])-x, px2 = upper_bound(x+1, x+1+nx, y[i])-x-1; int pz1 = lower_bound(z+1, z+1+nz, y[i])-z, pz2 = upper_bound(z+1, z+1+nz, y[i])-z-1; if(pz1!=nz+1&&px2) ans = min(ans, cal(x[px2],y[i],z[pz1])); if(px1!=nx+1&&pz2) ans = min(ans, cal(z[pz2],y[i],x[px1])); } } int main(){ scanf("%d", &T); while(T--){ scanf("%d%d%d", &na, &nb, &nc); for(int i = 1; i <= na; i++) scanf("%lld", &a[i]); for(int i = 1; i <= nb; i++) scanf("%lld", &b[i]); for(int i = 1; i <= nc; i++) scanf("%lld", &c[i]); sort(a+1, a+1+na), sort(b+1, b+1+nb), sort(c+1, c+1+nc); ans = inf; sovle(b, nb, a, na, c, nc); sovle(a, na, b, nb, c, nc); sovle(a, na, c, nc, b, nb); printf("%lld ", ans); } }
Reference:
https://codeforces.ml/blog/entry/75996
https://www.cnblogs.com/heyuhhh/p/12710644.html