XJOI Noip2016模拟赛1
XJOI的模拟赛，（一个账号提前交卷了出了一些锅），不过还是顺利AK。
【A 吉利挖矿】
【题解】这种题啊一看就是二分答案然后乱搞啦！
非常兹磁！O(nhlog ai,j)
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 | # include <stdio.h># include <vector>// # include <bits/stdc++.h>using namespace std;int n, h;const double eps = 1e-5, fineps = 1e-8;vector<int> a[100010];vector<double> b[100010];inline bool check(double x) { for (int i=1; i<=n; ++i) b[i].clear(); for (int i=1; i<=n; ++i) for (int j=0; j<h; ++j) b[i].push_back((double)a[i][j]-x); /* for (int i=1; i<=n; ++i, printf("\n")) for (int j=0; j<h; ++j) printf("%.4lf ", b[i][j]); puts("=================="); */ double maxx = 0; for (int i=1; i<=n; ++i) { double s=0, cur=-1e9-1; for (int j=0; j<h; ++j) { s=s+b[i][j]; if(s>cur) cur=s; } maxx=maxx+cur; } return maxx>=-fineps;}int main() { scanf("%d%d", &n, &h); for (int i=1, x; i<=n; ++i) { for (int j=1; j<=h; ++j) { scanf("%d", &x); a[i].push_back(x); } } double l, r, mid; l = -1e9-1, r = 1e9+1; while(1) { if(r-l<=eps) break; mid = (l+r) / 2.0; if(check(mid)) l = mid; else r = mid; } printf("%.4lf\n", l); return 0;} |
【B 吉利的道路】
见xiaone校内训练Round1 T1：这里。
【C 膜拜吉利】
【题解】对于操作1，我们可以暴力维护，操作2我们用类似于LCA的往上跳即可，因为膜拜吉利的人一定从下到上集中在几层里，所以就能维护啦，至于怎么维护从小到大？搞LCA的时候排排序啊，DFS序搞搞就行了。
因为会随时push，所以用priority_queue。
Tips： priority_queue<int, vector<int>, greater<int>>是小根堆。
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 | # include <stdio.h># include <algorithm># include <queue># include <vector>// # include <bits/stdc++.h>using namespace std;const int M = 400010, N = 200010, logN = 19;# define next nxt int tot=0, next[M], head[N], to[M];int n, Q;int fa[N][logN], dep[N]; priority_queue< int, vector<int>, greater<int> > q;bool ok[N]; int dfn[N], ndfn[N], DFN=0; inline void add(int u, int v) { ++tot; next[tot]=head[u]; head[u]=tot; to[tot]=v;}inline void dfs(int x, int fat, int depth) { vector<int> v; dep[x]=depth; fa[x][0]=fat; for (int i=1; i<logN; ++i) fa[x][i] = fa[fa[x][i-1]][i-1]; for (int i=head[x]; i; i=next[i]) { if(to[i] == fat) continue; v.push_back(to[i]); } sort(v.begin(), v.end()); int ttx = v.size(); for (int i=0; i<ttx; ++i) dfs(v[i], x, depth+1); dfn[x]=++DFN; ndfn[DFN]=x;}int main() { scanf("%d%d", &n, &Q); for (int i=1, u, v; i<n; ++i) { scanf("%d%d", &u, &v); add(u, v); add(v, u); } dfs(1, 0, 1); for (int i=1; i<=n; ++i) q.push(i); while(Q--) { int opt, x; scanf("%d%d", &opt, &x); if(opt == 1) { int t = 0; while(x--) { t = q.top(); ok[t]=1; q.pop(); } printf("%d\n", ndfn[t]); } else if (opt == 2) { int tx = x; for (int i=logN-1; i>=0; --i) if(fa[tx][i] != 0 && ok[dfn[fa[tx][i]]]) tx = fa[tx][i]; ok[dfn[tx]]=0; q.push(dfn[tx]); printf("%d\n", abs(dep[x] - dep[tx])); } } return 0;} |
2023年4月20日 19:39
With the assistance of the editorial and content teams, we supply you with the best web content on any topic imaginable.Pavzi Post is a startup founded by dedicated webmasters and bloggers who want to produce engaging pavzi.com material that is truthful, fascinating, and worth reading. We are more of a digital community where you can find various information, resources, and subjects about current events or news.