Codeforces Edu Round 54 A-E-蒲公英云

Codeforces Edu Round 54 A-E

A. Minimizing the String

很明显，贪心之比较从前往后第一个不一样的字符，所以可以从前往后考虑每一位，如果把它删除，他这一位就变成$str[i + 1]$，所以只要$str[i] > str[i + 1]$，删除后一定是最优的。

#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int N = 200010; int n; char str[N]; int main(){ scanf("%d%s", &n, str + 1); for(int i = 1; i < n; i++){ if(str[i] > str[i + 1]){ for(int j = 1; j <= n; j++) if(j != i) printf("%c", str[j]); return 0; } } for(int i = 1; i < n; i++) printf("%c", str[i]); return 0; }

B. Divisor Subtraction

单纯暴力可以会超时，考虑到所有偶数的最小质因子都是$2$，故可以分类讨论，对于一个数$x$：

若$x \% 2 = 0$，则每次的$d = 2$，操作次数为$x / 2$
若$x$为质数，最小质因子 $ = x$，$x - x = 0$，操作次数为$1$
若$x$为奇合数，则其的质因子必然也是奇数，这样$(x - d) \% 2 = 0$，可以返回第一步求解。

C. Meme Problem

按照题意，将式子化成一个一元二次方程，接着依照求根公式求解即可。

#include <iostream> #include <cstdio> #include <cmath> using namespace std; int d; int main(){ int T; scanf("%d", &T); while(T--){ scanf("%d", &d); double a, b, delta; delta = d * d - 4 * d; if(delta < 0) puts("N"); else delta = sqrt(delta), printf("Y %.9f %.9f\n", (delta + d) / 2, (-delta + d) / 2); } return 0; }

D. Edge Deletion

可以先用$Dijkstra$跑一棵最短路的树，然后贪心，从节点$1$开始$Bfs$，选择$K$条边即可。

（PS：没开$long$ $long$被卡$Wa$了$N$次）

#include <cstdio> #include <iostream> #include <cstring> #include <queue> #include <algorithm> #include <vector> using namespace std; typedef long long LL; typedef pair<LL, int> PLI; const int N = 300010, M = 300010; const LL INF = 0x3f3f3f3f3f3f3f3f; int n, m, k, numE = 1, head[N], fa[N], faEdge[N]; bool vis[N]; vector<int> G[N], ans; LL dis[N]; priority_queue<PLI, vector<PLI>, greater<PLI> > q; queue<int> Q; struct Edge{ int next, to; LL dis; }e[M << 1]; void addEdge(int from, int to, int dis){ e[++numE].next = head[from]; e[numE].to = to; e[numE].dis = dis; head[from] = numE; } void Dijkstra(){ memset(dis, 0x3f, sizeof dis); q.push(make_pair(0, 1)); dis[1] = 0; while(!q.empty()){ PLI u = q.top(); q.pop(); if(vis[u.second]) continue; vis[u.second] = true; for(int i = head[u.second]; i; i = e[i].next){ int v = e[i].to; if(dis[u.second] + e[i].dis < dis[v]){ dis[v] = dis[u.second] + e[i].dis; fa[v] = u.second, faEdge[v] = i >> 1; q.push(make_pair(dis[v], v)); } } } } void Bfs(){ Q.push(1); while((!Q.empty()) && k > 0){ int u = Q.front(); Q.pop(); for(int i = 0; i < G[u].size(); i++){ int v = G[u][i]; k--; ans.push_back(faEdge[v]); Q.push(v); if(!k) return; } } } int main(){ scanf("%d%d%d", &n, &m, &k); for(int i = 1; i <= m; i++){ int u, v, w; scanf("%d%d%d", &u, &v, &w); addEdge(u, v, w); addEdge(v, u, w); } Dijkstra(); for(int i = 1; i <= n; i++) if(fa[i]) G[fa[i]].push_back(i); Bfs(); printf("%d\n", (int)ans.size()); for(int i = 0; i < ans.size(); i++) printf("%d ", ans[i]); return 0; }

E. Vasya and a Tree

考虑用树状数组维护和，现在的修改类似于”树上扫描线”的东西，因为遍历到子树之前一定会dfs到它的祖先，所以在祖先的区间处理时，进入就加上，退出就剪掉…

#include <iostream> #include <cstdio> #include <vector> using namespace std; const int N = 3 * 1e5 + 5; typedef long long ll; struct Edge{ int next,to; }e[N * 2]; int n,m,head[N],numE=0; ll c[N],ans[N]; vector<pair<int,int> > T[N]; void addEdge(int from,int to){ e[++numE].next = head[from]; e[numE].to = to; head[from] = numE; } ll ask(int x){ ll ans = 0; for(;x;x-=x&-x)ans += c[x]; return ans; } void add(int x,ll k){ for(;x<=n;x+=x&-x)c[x] += k; } void dfs(int u,int last,int dep){ for(int i=0;i<T[u].size();i++){ int d = T[u][i].first; ll x = T[u][i].second; add(dep,x); add(dep + d + 1,-x); } ans[u] = ask(dep); for(int i = head[u];i;i=e[i].next){ int v = e[i].to; if(v == last)continue; dfs(v,u,dep + 1); } for(int i=0;i<T[u].size();i++){ int d = T[u][i].first; ll x = T[u][i].second; add(dep,-x); add(dep + d + 1,+x); } } int main() { scanf("%d",&n); for(int i=2;i<=n;i++){ int x,y; scanf("%d%d",&x,&y); addEdge(x,y); addEdge(y,x); } scanf("%d",&m); for(int i=1;i<=m;i++){ int v,d,x; scanf("%d%d%d",&v,&d,&x); T[v].push_back(make_pair(d,x)); } dfs(1,0,1); for(int i=1;i<=n;i++){ printf("%lld ",ans[i]); } return 0; }