Codeforces Round #443 (Div. 2) 题解

比赛链接：http://codeforces.com/contest/879

A. Borya's Diagnosis

题意：一个人去看医生，这n个医生分别在s[i],s[i]+2*d[i]...这些天上班，这个人必须按照顺序拜访医生，问这个人拜访最后一个医生的最早时间。

解法：按顺序模拟。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
struct node{
    int s,d;
}a[maxn];
bool vis[2000010];
int n;
int main(){
    scanf("%d",&n);
    for(int i=1; i<=n; i++){
        scanf("%d %d", &a[i].s, &a[i].d);
    }
    int curpos = 0;
    for(int i=1; i<n; i++){
        int t = a[i].s;
        while(1){
            if(!vis[t]&&t>curpos){
                curpos = t;
                vis[t] = 1;
                break;
            }
            t = t + a[i].d;
        }
    }
    int t = a[n].s;
    while(1){
        if(!vis[t]&&t>curpos){
            vis[t] = 1;
            break;
        }
        t = t + a[n].d;
    }
    printf("%d\n", t);
    return 0;
}

B. Table Tennis

题意：有1-n组成的一个排列，每个数代表一个人的power，两个人比赛时power大的人会获胜比赛从左到右比，输了的人移到末尾，赢的人和下一个人比，当有一个人赢了k盘时输出该人的power

解法：只有power为n的人才能赢>=n盘，所以k>=n时输出n。k<n时从左到右进行遍历，遇到可以赢k盘的人就结束。我用vector直接模拟这个过程。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 550;
int a[maxn];
vector <int> b;
int main(){
    int n;
    LL k;
    scanf("%d %lld", &n,&k);
    int mx = 0;
    for(int i=1; i<=n; i++) scanf("%d", &a[i]), mx = max(mx, a[i]);
    if(k >= n){
        return 0*printf("%d\n", mx);
    }
    for(int i=1; i<=n; i++) b.push_back(a[i]);
    for(int i=0; i<b.size(); i++){
        int now = 0;
        int mx = 0;
        for(int j=0; j<i; j++) mx = max(mx, b[j]);
        if(mx<b[i]&&i>0) now=1;
        for(int j=i+1; j<b.size(); j++){
            if(b[j]>b[i]) break;
            else now++;
        }
        if(now==0) b.push_back(b[i]);
        else if(now>=k){
            return 0*printf("%d\n", b[i]);
        }else b.push_back(b[i]);
    }
    return 0;
}

C. Short Program

题意：就是给你n个操作，然后化简，在5步之内输出跟n步操作同样效果的操作。

解法：很容易想到，最后一定用三种操作 &|^能表示完所有的操作。然而x不知道是0还是1，那么最后就看假如x是0，x变成什么值，y是1，y变成什么值，由什么操作可以得来就好了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5+10;

int main(){
    int n;
    scanf("%d", &n);
    int x=1023, y=0;
    for(int i=0; i<n; i++){
        char s[2];
        int d;
        scanf("%s%d",s,&d);
        if(s[0]=='|') x|=d,y|=d;
        else if(s[0]=='&') x&=d,y&=d;
        else if(s[0]=='^') x^=d,y^=d;
    }
    int a=-1,b=-1;
    for(int i=0; i<10; i++){
        int xx = (x&(1<<i))>0?1:0;
        int yy = (y&(1<<i))>0?1:0;
        if(xx==1&&yy==1){
            if(a==-1) a=1<<i;
            else a+=(1<<i);
        }
        if(xx==0&&yy==0){
            if(a==-1) a=1<<i;
            else a=a|(1<<i);
            if(b==-1) b=1<<i;
            else b=b|(1<<i);
        }
        if(xx==0&&yy==1){
            if(b==-1) b=1<<i;
            else b=b|(1<<i);
        }
    }
    int ans=0;
    if(a!=-1) ans++;
    if(b!=-1) ans++;
    printf("%d\n", ans);
    if(a!=-1) printf("| %d\n", a);
    if(b!=-1) printf("^ %d\n", b);
    return 0;
}

D. Teams Formation

题意：有一辆车每次运送n个人，这n个人分别来自于不同的城市。一共运送m趟，现在题目要求你将每次排队的n个人进行分队，每一队的人数要求是k个，也就是说如果相邻的人来自于同一个城市，同时满足加在一起的人数是大于或等于K的，那么就可以减少k个人，问你最后能能够剩下多少人？类似于祖玛。。

解法：对于一个长度为n的序列，先将这个序列压缩一下，就是如果相同的数连在一起那我们就记一个并记下他连续的个数，之后我们先考虑他的内部是否已经存在连续k个一样的数字，如果已经存在，那么先将这些消去，否则我们用两个指针，一个指向序列开头，另一个指向尾部，表示当相邻两个串合并起来的时候是否有连续k个相同的数字，如果有那么删掉，最后就直接暴力做下去，直到不存在满足要求的数。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100010;
LL n, m, k, x, s[maxn][2], cnt;

int main(){
    scanf("%d %d %d", &n,&k,&m);
    for(int i=1; i<=n; i++){
        scanf("%d", &x);
        if(!cnt||s[cnt][0]!=x){
            s[++cnt][0]=x;
            s[cnt][1]=1;
        }else s[cnt][1]++;
        if(s[cnt][1]==k){
            s[cnt][1]=0;
            cnt--;
        }
    }
    LL tot=0;
    for(int i=1; i<=cnt; i++) tot+=s[i][1];
    int head=1,tail=cnt;
    while(head<tail&&s[head][0]==s[tail][0]){
        if((s[head][1]+s[tail][1])%k==0){
            head++;
            tail--;
        }
        else{
            s[head][1]=(s[head][1]+s[tail][1])%k;
            s[tail][1]=0;
            break;
        }
    }
    LL ans = 0;
    if(head<tail){
        for(int i=head;i<=tail;i++) ans+=s[i][1];
        ans = ans*(m-1);
        ans+=tot;
    }else if(head==tail){
        if((s[head][1]*m)%k==0) ans=0;
        else{
            ans = tot+s[head][1]*(m-1);
            ans -= s[head][1]*m-s[head][1]*m%k;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

E. Tournament

题意：现在有n个人参加比赛，每个人都有k项能力值，每个能力值表示这个人在这个技能上面的能力。现在这些人会两两进行比赛，他们会挑选一个技能进行比较，分值高的获胜，胜利者留下来，失败者离开。你需要回答，最后究竟会有多少个人可能成为冠军。

解法：http://www.cnblogs.com/qscqesze/p/7762484.html

假设现在有一群人都可能获得冠军，那么必须满足任何一个人，都能找到一个人的某项技能小于等于他，也能找到一个人的某项技能强于他。那么对于这个集合，对于每个人都能存在一个比赛方案，使得他成为冠军。然后我们动态维护这个集群就好了，用set去维护。你可以用图论的方式去理解。如果A能够打败B，那么连一条A->B的边，显然胜利者的含义就是如果A能够达到其他的所有点，那么A就是胜利者。最后的胜利者集合，里面的任何两个点都能互相到达，如果已经成为了团，我们就进行缩点就好了，我们用set去缩点。然后维护每一个团就行。

#include <bits/stdc++.h>
using namespace std;
int n, x, k;
struct people{
    int mx[15], mi[15], sz;
    bool operator<(const people &rhs) const{
        for(int j=1; j<=k; j++) if(mx[j]>rhs.mi[j]) return 0; return 1;
    }
}tmp;
set <people> s;

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        tmp.sz=1;
        for(int j=1;j<=k;j++){
            scanf("%d", &x);
            tmp.mi[j]=tmp.mx[j]=x;
        }
        auto x=s.lower_bound(tmp), y=s.upper_bound(tmp);
        while(x!=y){
            tmp.sz+=x->sz;
            for(int j=1;j<=k;j++) tmp.mi[j]=min(tmp.mi[j],x->mi[j]), tmp.mx[j]=max(tmp.mx[j],x->mx[j]);
            s.erase(x++);
        }
        s.insert(tmp);
        printf("%d\n", s.rbegin()->sz);
    }
    return 0;
}