Codeforces Round #468 div2题解

比赛链接：http://codeforces.com/contest/931
A：Friends Meeting
题意：在x轴上有2个点，一个为x,一个为y,现在这两个人要走到一个位置使得代价和终于小，其中代价计算为(step+1)*step/2
解法：直接枚举中间点，取最小值。

#include <bits/stdc++.h>
using namespace std;
int cal(int x){
    return x*(x+1)/2;
}
int main(){
    int a,b;
    cin>>a>>b;
    int ans = 0x3f3f3f3f;
    for(int i=min(a,b);i<=max(a,b);i++){
        ans = min(ans, cal(max(a,b)-i)+cal(i-min(a,b)));
    }
    cout<<ans<<endl;
}

B. World Cup
题意：在“world cup”足球比赛中，遵循两两进行比赛（按编号）的规则，给出两只球队的编号，假设这两只球队常胜，问他们会在第几轮相遇，如果是决赛，输出“Final！”
解法：容易发现，按照一直除2到2个数相等的轮数就是所需要的轮数。

#include <bits/stdc++.h>
using namespace std;
int mi[9]={1,2,4,8,16,32,64,128,256};
int main(){
    int n,a,b;
    scanf("%d%d%d",&n,&a,&b);
    a--,b--;
    int cnt=0;
    while(a!=b){
        cnt++;
        a/=2;
        b/=2;
    }
    if((1<<cnt)==n){
        puts("Final!");
    }else{
        printf("%d\n",cnt);
    }
}

C. Laboratory Work
题意：给定一个数列，要求构造一个等长的数列，使得数列的平均值等于给定数列，并且使得构造出的数列中与原数列相同的数字个数最小，输出最小相同数字个数与构造的数列。数列长度不超过100000，给定数列中最大的数字与最小的数字相差不超过2。要求构造出的数列中最大值与最小值不能大于或小于原数列中的最大值与最小值。
解法：按照最大值减去最小值等于0,1,分别讨论
1，如果最大-最小=0，那只能使用原数列
2，如果最大-最小=1，也还是只能使用原数列
3，如果最大-最小=2 要么把每2个次大的改成一个最小和一个最大，要么把一个最大和一个最小改成2个次大两种情况取最优

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, a[maxn];
int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;i++) scanf("%d", &a[i]);
    sort(a+1,a+n+1);
    if(a[n]-a[1]<=1){
        printf("%d\n", n);
        for(int i=1;i<=n;i++) printf("%d ",a[i]);
        return 0;
    }
    int cnt1=0,cnt2=0,cnt3=0;
    for(int i=1;i<=n;i++){
        if(a[i]==a[1]) cnt1++;
        else if(a[i]==a[n]) cnt3++;
        else cnt2++;
    }
    int t=min(cnt1,cnt3), k=cnt2/2;
    int m=a[1];
    if(t>k){
        for(int i=1;i<=t;i++) a[i]=m+1;
        for(int i=1;i<=t;i++) a[n-i+1]=m+1;
        printf("%d\n", n-t*2);
        for(int i=1;i<=n;i++) printf("%d ", a[i]);
    }
    else{
        for(int i=1;i<=k;i++) a[cnt1+i*2-1]=m,a[cnt1+i*2]=m+2;
        printf("%d\n",n-k*2);
        for(int i=1;i<=n;i++) printf("%d ", a[i]);
    }
}

D. Peculiar apple-tree
题意：给你一颗树，然后每个分支上有一个苹果，如果每个分支上两个苹果落下来，那么这两个苹果就没了，然后问你最后剩下了几个苹果
解法：确认过题意，实际上就是每一层的苹果数总数为奇数的层数。直接DFS记录一下就可以了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
struct node{
    int to,next;
}E[maxn*2];
int n, head[maxn], num[maxn], edgecnt, maxdep;
void init(){
    memset(head,-1,sizeof(head));
    edgecnt=0;
}
void add(int u, int v){
    E[edgecnt].to=v,E[edgecnt].next=head[u],head[u]=edgecnt++;
}
void dfs(int x, int fa, int d){
    num[d]++;
    if(d>maxdep) maxdep = d;
    for(int i=head[x];~i;i=E[i].next){
        int v=E[i].to;
        if(v==fa) continue;
        dfs(v, x, d+1);
    }
}
int main(){
    scanf("%d", &n);
    init();
    maxdep = 0;
    for(int i=2;i<=n;i++){
        int x;
        scanf("%d", &x);
        add(i, x);
        add(x, i);
    }
    dfs(1, -1, 1);
    int ans = 0;
    for(int i=1; i<=maxdep; i++){
        ans += num[i]%2;
    }
    printf("%d\n", ans);
    return 0;
}

E. Game with String
题意：有一个字符串，一个人可以随机选择一个位置，然后把这个位置之后的所有字符提前，这个位置之前的所有字符向后移动，你最多再选择一个。然后一个人被告知了转变后的串的第一个字符是啥，现在他有机会再选择任意一个位置被告知字符是啥，问这个人能唯一确定k的概率多大？
解法：官方题解。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5010;
char s[maxn*2];
int dp[26][26][maxn];

int main(){
    scanf("%s", s+1);
    int len = strlen(s+1);
    for(int i=1; i<=len; i++) s[len+i]=s[i];
    for(int i=1; i<=len; i++){
        for(int j=i+1; j<i+len; j++){
            dp[s[i]-'a'][s[j]-'a'][j-i+1]++;
        }
    }
    int cnt = 0;
    for(int i=0; i<26; i++){
        int p = 0;
        for(int j=1; j<=len; j++){
            int sum = 0;
            for(int k=0; k<26; k++){
                if(dp[i][k][j]==1) sum++;
            }
            p = max(p, sum);
        }
        cnt += p;
    }
    double ans = 1.0*cnt/len;
    printf("%.10f\n", ans);
}

F. Teodor is not a liar!
题意：给出一堆线段。询问者每次可以询问一个整数点，回答者告诉询问者这个点被多少根线段包括。问询问者最多问多少次，还不能确定任意一个整数点都不可能被所有的线段包含。
解法：首先用O(n)的方法计算出来每个点被多少条线段包含。然后思考一下，当存在一个点被所有线段包含了那么必定有，所以实际上我们需要做的就是找到一个最长的凸函数，前半段递增后半段递减，这个可以用树状数组来做，更新树状数组不能更为0，所以默认所有点初始都+1。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n,m,a[maxn],c[maxn];
int f1[maxn], f2[maxn];
int lowbit(int x){return x&(-x);}
void update(int x, int v){
    while(x<=n){
        c[x]=max(c[x],v);
        x+=lowbit(x);
    }
}
int query(int x){
    int ret=0;
    while(x){
        ret=max(ret,c[x]);
        x-=lowbit(x);
    }
    return ret;
}
int main(){
    scanf("%d%d", &n,&m);
    for(int i=1; i<=n; i++){
        int l,r;
        scanf("%d%d",&l,&r);
        a[l]++;
        a[r+1]--;
    }
    int sum=0;
    for(int i=1;i<=m;i++){
        sum+=a[i];
        a[i]=sum+1;
    }
    //
    for(int i=1;i<=m;i++){
        f1[i]=query(a[i])+1;
        update(a[i], f1[i]);
    }
    memset(c, 0, sizeof(c));
    for(int i=m;i>=1;i--){
        f2[i]=query(a[i])+1;
        update(a[i],f2[i]);
    }
    int ans=0;
    for(int i=1; i<=m; i++){
        ans = max(ans, f1[i]+f2[i]-1);
    }
    printf("%d\n", ans);
}