Codeforces Round #423 (Div. 2) C 思维,并查集 或 线段树 D 树构造,水

线段树 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  second
typedef 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  second
typedef 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;
}

转载于:.html