首页 > 代码库 > Codeforces Round #423 (Div. 2) C 思维,并查集 或 线段树 D 树构造,水
Codeforces Round #423 (Div. 2) C 思维,并查集 或 线段树 D 树构造,水
Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals)
C. String Reconstruction 思维,并查集 或 线段树
题意：一个字符串被删除了，但给出 n条信息，要还原出可能的字典序最小的字符串。信息有：字符串ti，ki个位置xi，表明原本的字符串在xi位置是以字符串ti开头的。
tags：惨遭 fst，一开始把所有字符串都存下来，排序做的，结果爆内存了。。
方法1： 考虑并查集，对于字符串 ti，在位置xi，字符串长度为len，更新之后，ti~(ti+len-1)位置的祖先就都指向ti+len。
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a;i<=b;i++)#define per(i,b,a) for (int i=b;i>=a;i--)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define MP make_pair#define PB push_back#define fi first#define se secondtypedef long long ll;const int N = 2000005;int n, fa[N], ki, xi;char si[N], ans[N];int Find(int x) { return fa[x]==x ? x : fa[x]=Find(fa[x]); }int main(){ scanf("%d", &n); rep(i,1,N-1) fa[i]=i, ans[i]=‘a‘; int mx=0; rep(cn,1,n) { scanf("%s %d", si+1, &ki); int len=strlen(si+1); rep(ck,1,ki) { scanf("%d", &xi); mx=max(mx, xi+len-1); int y=xi; while((y=Find(y)) <= xi+len-1) { ans[y]=si[y-xi+1]; fa[y]=y+1; } } } rep(i,1,mx) putchar(ans[i]); return 0;}
方法2： 直接树状数组或线段树更新
#include <bits/stdc++.h>using namespace std;const int maxn = 2001000;char ans[maxn];char c[maxn];long long t[maxn];void add(int k){ while(k < maxn) { t[k]++; k += k & -k; }}int sum(int x){ long long sum = 0; while(x) { sum += t[x]; x -= x & -x; } return sum;}void updata(int l, int r, int k){ if(l == r) { if(!ans[l]) { add(l); ans[l] = c[k]; } return ; } int mid = (l + r) >> 1; if(sum(mid)-sum(l-1) != mid - l + 1) updata(l, mid, k); if(sum(r)-sum(mid) != r - mid) updata(mid + 1, r, k + mid - l + 1);}int main(){ int n; while(scanf("%d", &n) != EOF) { int lans = 0; memset(ans,0,sizeof(ans)); memset(t,0,sizeof(t)); while(n--) { int m = 0; scanf("%s%d", c, &m); int len = strlen(c); for(int i = 0; i < m; i++) { int l; scanf("%d", &l); lans = max(lans, l + len); updata(l, l + len-1, 0); } } for(int i = 1; i < lans; i++) { putchar(ans[i]? ans[i]: ‘a‘); } printf("\n"); } return 0;}
D. High Load 树构造,水,dfs
题意：n个点的树，已知有k个叶子节点，要使得树上的最长链最短，构造出这树。
tags：大水题，比赛的时候竟然没去看。。
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a;i<=b;i++)#define per(i,b,a) for (int i=b;i>=a;i--)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define MP make_pair#define PB push_back#define fi first#define se secondtypedef long long ll;const int N = 200005;ll n, k;vector<ll > G[N];void dfs(int u, int fa){ for(auto to : G[u]) if(to!=fa) { printf("%d %d\n", u, to); dfs(to, u); }}int main(){ scanf("%lld %lld", &n, &k); ll cnt=1, j; while(cnt<n) { for(j=1; j<=k, cnt+j<=n; ++j) { ll u=max(1LL, cnt+j-k); G[u].PB(cnt+j); G[cnt+j].PB(u); } cnt=cnt+j; } ll ans=(n-1+k-1)/k*2; if(n-1-k*(ans/2-1)==1) --ans; printf("%lld\n", ans); dfs(1, 0); return 0;}
Codeforces Round #423 (Div. 2) C 思维,并查集 或 线段树 D 树构造,水
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。