Codeforces Round #527 (Div. 3) 题解
题目总链接：https://codeforces.com/contest/1092
A. Uniform String
题意：
输入n,k，n表示字符串的长度，k表示从1-k的小写字符（1即是a），现在要求最大化最少字符的数量。
题解：
贪心搞一搞就行了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int T;
int n,k;
int main(){
cin>>T;
char s[];
for(int i=;i<+;i++) s[i-]=char(i);
while(T--){
cin>>n>>k;
int len = n/k;
int cnt = ;
for(int i=;i<=len*k;i++){
cout<<s[cnt];
if(i%len==) cnt++;
} for(int i=;i<=n%k;i++){
cout<<s[cnt-];
}
cout<<endl;
}
return ;
}
B. Teams Forming
题意：
给出n个点以及其权值ai，要求两两配对，可以给每个点的权值加上一定数，配对的两个点满足权值相等，现在问权值增加的总量最小是多少。
题意:
还是贪心搞一搞，排个序搞一下就行了，正确性应该比较明显吧...
代码如下：
#include <bits/stdc++.h>
using namespace std; const int N = ;
int n;
int a[N];
int main(){
int ans = ;
cin>>n;
for(int i=;i<=n;i++) cin>>a[i];
sort(a+,a+n+);
for(int i=;i<=n;i+=){
ans+=a[i]-a[i-];
}
cout<<ans;
return ;
}
C. Prefixes and Suffixes
题意:
给出2*n-2个字符串，有n-1个代表前缀，有n-1个代表后缀，现在问哪些是前缀，哪些是后缀，这题是speacial judge。
题解：
枚举就够了...我们先对这些字符串按其长度排序，然后选定一个长度为n-1的串作为前缀，再选定另外一个长度为n-1的串作为后缀，然后往前匹配就行了。
如果此时不行，那么就把两个长度为n-1的字符串互换一下，前缀变后缀，后缀变前缀，再来匹配一次就行了...
代码如下:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#define mp make_pair
#define INF 1e9
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = ;
int n,k,T;
int head[N],vis[N],d[N],a[N],pa[N],pre[N];
struct Edge{
int v,next,c,w;
}e[N*N];
int tot ;
void adde(int u,int v,int c,int w){
e[tot].v=v;e[tot].next=head[u];e[tot].w=w;e[tot].c=c;head[u]=tot++;
e[tot].v=v;e[tot].next=head[v];e[tot].w=-w;e[tot].c=;head[v]=tot++;
}
int spfa(int s,int t,int &flow,int &cost){
for(int i=;i<=t+;i++) d[i]=a[i]=INF;d[s]=;
memset(vis,,sizeof(vis));vis[s]=;
memset(pre,-,sizeof(pre));memset(pa,-,sizeof(pa));
queue <int> q;q.push(s);
while(!q.empty()){
int u=q.front();q.pop();vis[u]=;
for(int i=head[u];i!=-;i=e[i].next){
int v=e[i].v;
if(e[i].c> && d[v]>d[u]+e[i].w){
d[v]=d[u]+e[i].w;
pa[v]=u;pre[v]=i;
a[v]=min(a[v],e[i].c);
if(!vis[v]){
vis[v]=;
q.push(v);
}
}
}
}
if(d[t]==INF) return ;
flow+=a[t];
cost+=a[t]*d[t];
for(int i=t;i!=-;i=pa[i]){
int edge = pre[i];
e[edge].c-=a[t];
e[edge^].c+=a[t];
}
return ;
}
int Min_cost(int s,int t){
int flow=,cost=;
while(spfa(s,t,flow,cost));
return cost;
}
int main(){
cin>>T;
while(T--){
tot=;memset(head,-,sizeof(head));
scanf("%d%d",&n,&k);
vector <int> x;
vector <pair<pii,int> > g[];
for(int i=;i<=n;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
x.push_back(u);
x.push_back(v);
g[i].push_back(mp(mp(u,v),w));
}
sort(x.begin(),x.end());
x.erase(unique(x.begin(),x.end()),x.end());
int len = x.size();
for(int i=;i<len-;i++) adde(i,i+,k,);
for(int i=;i<=n;i++){
int u=g[i].first.first,v=g[i].first.second,w=g[i].second;
int p1 = lower_bound(x.begin(),x.end(),u)-x.begin();
int p2 = lower_bound(x.begin(),x.end(),v)-x.begin();
adde(p1,p2,,-w);
}
printf("%d\n",Min_cost(,len-));
}
return ;
}
D1. Great Vova Wall (Version 1)
题意:
给出n个权值为ai的点，权值代表他们的高度，现在有个1*2的矩形，可以横着放，也可以竖着放，问可不可以满足下面的条件：
1.所有点高度相同；2.中间没有空隙。
题解：
我们知道两个点同为奇数或同为偶数即可填补为相同的高度并且高度可以随意增加。
我们利用一个栈，当栈内的top与当前要加进去的数同奇偶时，我们就可以把他弹出来意味这两个配对。不行就把当前这个数加进去。
为什么这是正确的？我们知道当这两个点相邻时，显然正确；当这两个点不相邻但同奇偶时，我们也可以通过竖着放1*2的矩形使其高度相等。
最后总能使已匹配的高度相等（相邻匹配点的高度可以随意增加）。
最后栈内个数小于等于1则必定有解，因为已匹配的点高度是可以随意增加的。
当个数大于1时就无解了。
代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =2e5+;
int n;
int a[N]; int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
a[i]&=;
}
vector <int> s;
for(int i=;i<=n;i++){
if(!s.empty()&&a[i]==s.back()){
s.pop_back();
}else s.push_back(a[i]);
}
if(s.size()<=) cout<<"YES";
else cout<<"NO";
return ;
}
D2. Great Vova Wall (Version 2)
题意：
D1里面砖可以竖着横着放，这题只能横着放，其余都一样。
题解：
我们还是用栈这个数据结构，当高度相同时就可以匹配。
但是，在这里如果两个点不相邻则不一定可以匹配成功。当两个点不相邻时，如果他们中间点的高度比他们小，那么可以通过中间点高度的增加使其匹配成功。
所以我们在匹配之前要判断一下之前匹配的数的大小（中间匹配的高度值）。
另外在最后的时候，D1留下一个即可行，但这里不行，因为不能竖着放，这里留下的那个应该为最高的那个才行。
这两个题挺有意思的，注意一下他们的差别以及思路的差异。
代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =2e5+;
int n;
int a[N];
int main(){
scanf("%d",&n);
int mx=;
for(int i=;i<=n;i++) scanf("%d",&a[i]),mx=max(mx,a[i]);
stack <int> S;
int pre = -;
for(int i=;i<=n;i++){
int now ;
if(!S.empty()) now = S.top();
else{
S.push(a[i]);
pre = -;
continue ;
}
if(now == a[i] && now>=pre){
S.pop();
pre = now;
}else S.push(a[i]),pre=-;
}
int cnt = ,now = mx;
while(!S.empty()){
cnt++;
now = S.top();
S.pop();
}
if(cnt> || now!=mx){
cout<<"NO";
}else cout<<"YES";
return ;
}
E. Minimal Diameter Forest
题意：
给出一个森林，现在要对这些森林连边使其变成一颗树，求最后树的最小直径。
题解：
我们考虑一下怎么去连边使森林变成树并且直径最短。
这棵树的总体架构应该是中间一个，其余的树都与其相连，并且中间的那棵树的直径应该最长（贪心的思想）。
那怎么连呢？我们还是采用贪心的想法，尽力将每棵树的直径中点连接起来，这样可以让最后树的直径最小。
考虑到这样的连接方式，那么我们就需要对于每棵单独的树求其直径以及中点就行了。
但最后要更新答案，答案可能来源于三种情况：
1.中心树连接四周的树产生的直径；2.单个树的直径（就是中心树的直径）；3.四周树相连产生的直径。
最后根据这三种情况统计一下答案，求三种情况的最大值就好了。
也可以根据最后建成的模型再跑两次dfs/bfs求树的直径~
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = ;
int n,m,scc,best;
vector <int> g[N];
int in[N],mx[N],len[N],pre[N],center[N];
void dfs1(int u,int belong){
in[u]=belong;
for(auto v :g[u])
if(!in[v]) dfs1(v,belong);
}
int maxn;
int dfs(int u,int pa,int d){
int node=;
pre[u]=pa;
if(d>=maxn){
maxn=d;
node = u;
}
for(auto v:g[u]){
int f;
if(v!=pa){
f=dfs(v,u,d+);
if(f>) node = f;
}
}
return node;
}
void find_max(int num){
int s,d=;
for(int i=;i<=n;i++)
if(in[i]==num){
s=i;break ;
}
maxn=;
s=dfs(s,-,d);
maxn=;d=;
memset(pre,-,sizeof(pre));
s=dfs(s,-,d);
mx[num]=maxn;
if(maxn>best) best = maxn ;
len[num]=(maxn+)/;
int cnt = ;
for(int i=s;i!=-;i=pre[i]){
cnt++;
if(cnt-==len[num]){
center[num]=i;
break ;
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
g[u].push_back(v);g[v].push_back(u);
}
for(int i=;i<=n;i++){
if(!in[i]){
scc++;
dfs1(i,scc);
find_max(scc);
}
}
int s;
for(int i=;i<=scc;i++){
if(mx[i]==best){
s=i;
break ;
}
}
int ans = best;
for(int i=;i<=scc;i++){
if(i==s) continue ;
ans= max(len[s]+len[i]+,ans);
}
for(int i=;i<=scc;i++){
for(int j=;j<=scc;j++){
if(i==s || j==s || i==j) continue ;
ans=max(ans,len[i]+len[j]+);
}
}
cout<<ans<<endl;
for(int i=;i<=scc;i++){
if(i==s) continue ;
cout<<center[i]<<" "<<center[s]<<endl;
}
return ;
}
F. Tree with Maximum Cost
题意：
给出一颗树，然后选定一个点v，对于所有其余的点u，求Σau*d(u,v)，d(u,v)代表u和v的距离。现在要求选定一个点，求出表达式的最大值。
题解：
由于我们选择的点不同，得出来的结果也不同。我们考虑对于不同的点dp一次，但复杂度显然太高了。
这里我们先对1号结点进行一次dp，并且维护对于每个点，维护以它为根节点的子树的点权值的和。并且求出f(1)，即选定一号点后Σau*d(u,1)的值。
然后我们进行换根dfs，这里很巧妙，我们不用对每一个点进行一次dp，而是直接从1号点向下dfs，并且在dfs的途中进行换根然后求出结果。
我们要完成根的转移，就需要知道，哪些量是怎么变的，以及需要维护哪些量。
假如我们现在从根从u到v，且以及求出了f(u)。那么对于v而言，它若成为根节点，那么f(u)要减去dp(v)并且加上dp(1)-dp(v)。
解释下这里的含义：减去dp(v)是因为换根后以v为根的子树离根的距离减少了1（从u到v）；dp(1)-dp(v)就代表除开以v为根节点的子树的权值和，这些点到根的距离都会因为根的转移而加1，所以我们最后加上dp(1)-dp(v)。最后在dfs里面维护一下就得出答案了。
代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+ ;
int n;
int a[N];
ll dp[N];
vector <int> g[N];
ll sum,ans;
void dfs1(int u,int pa,int d){
sum+=(ll)d*a[u];
dp[u]=a[u];
for(auto v:g[u]){
if(v!=pa){
dfs1(v,u,d+);
dp[u]+=dp[v];
}
}
return ;
}
void go(int u,int pa,ll k){
ans=max(ans,k);
for(auto v:g[u]){
if(v!=pa) go(v,u,k-dp[v]+dp[]-dp[v]);
}
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
g[u].push_back(v);g[v].push_back(u);
}
dfs1(,-,);
go(,-,sum);
cout<<ans<<endl;
return ;
}