Codeforces Round #416 (Div. 2) 题解

A：水题，模拟即可。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    int now=0, cnt=1, ans=0;
    while(a>0&&b>0)
    {
        if(now==0)
        {
            if(a-cnt<0)
            {
                ans=0;
                break;
            }
            else a-=cnt;
        }
        else
        {
            if(b-cnt<0)
            {
                ans=1;
                break;
            }
            else  b-=cnt;
        }
        now^=1;
        cnt++;
    }
    if(now==0)
    {
        if(a-cnt<0)
        {
            ans=0;
        }
        else{
            ans=1;
        }
    }
    else
    {
        if(b-cnt<0)
        {
            ans=1;
        }
        else{
            ans=0;
        }
    }
    if(ans) puts("Valera");
    else puts("Vladik");
}

B:水题，暴力

#include <bits/stdc++.h>
using namespace std;
int a[10010];
int n,m;
int main()
{
    scanf("%d%d", &n,&m);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=1; i<=m; i++){
        int l,r,x;
        scanf("%d%d%d", &l,&r,&x);
        int cnt1=0,cnt2=0;
        for(int i=l; i<=r; i++){
            if(a[i]<=a[x]) cnt1++;
            if(a[i]>a[x]) cnt2++;
        }
        if(cnt1==x-l+1){
            puts("Yes");
        }
        else
            puts("No");
    }
    return 0;
}

C：题意：给一个有n个人排队上车，去相同地方的人要么坐在同一个车厢，要不就不上车，问最大舒适度和是多少。舒适度是车厢内所有数组成的集合的异或值。

解法：对于当前点，我们不断往前看是否能构成一个新的区间，如果能够成dp[i] = max(dp[i],dp[j-1]+res);这里j代表的就是

左端点，res表示新构成的区间的不同的数的异或值。

另外一个情况就是默认不选择当前这个点，那么dp[i] = dp[i-1]。

#include <bits/stdc++.h>
using namespace std;
int n, a[5010], dp[5010], last[5010], afe[5010];
bool vis[5010];
int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
        if(!last[a[i]]) last[a[i]]=i;
        afe[a[i]]=i;
    }
    for(int i=1; i<=n; i++){
        dp[i]=dp[i-1];
        memset(vis,0,sizeof(vis));
        int st=last[a[i]], res=0;
        for(int j=i; j>=1; j--){
            if(!vis[a[j]]){
                if(afe[a[j]]>i) break;
                st=min(st,last[a[j]]);
                res^=a[j];
                vis[a[j]]=1;
            }
            if(j==st) dp[i]=max(dp[i],dp[j-1]+res);
        }
    }
    printf("%d\n", dp[n]);
    return 0;
}

D：

题意：现在给你一个n*m大小的图，你输出一个方向之后，系统反馈给你一个坐标，表示走完这步之后到的位子，我们需要在

2*n*m 步之内走到终点，问怎样走才行（多解输出任意一个即可）。

我们一开始的位子是（1,1），终点位子是“F”，‘*’表示不能走的位子，游戏开始的时候，有一些小伙伴比较调皮，会将U

和D互换，就是说假设我们操作了U，但是实际是走到了D.或者也可能将L和R互换，当然也可能都没有互换过，当然也可能都

互换过。然你模拟整个过程。

解法：交互题。直接先BFS预处理出一个可行的答案，然后按照这个过程去模拟，如果发现下一步走的位置和预期走的位置不

一样，那么这个位置肯定是反的。

#include <bits/stdc++.h>
using namespace std;
bool vis[110][100];
char a[110][110],b[5];
vector<pair<int,int> >v,w;
vector<int>vv;
int n, m;

void dfs(int l, int r){
    vis[l][r]=1;
    v.push_back(make_pair(l,r));
    if(a[l][r]=='F'){
        w=v;
        return;
    }
    if(!vis[l-1][r]&&(a[l-1][r]=='F'||a[l-1][r]=='.')) dfs(l-1,r);
    if(!vis[l+1][r]&&(a[l+1][r]=='F'||a[l+1][r]=='.')) dfs(l+1,r);
    if(!vis[l][r-1]&&(a[l][r-1]=='F'||a[l][r-1]=='.')) dfs(l,r-1);
    if(!vis[l][r+1]&&(a[l][r+1]=='F'||a[l][r+1]=='.')) dfs(l,r+1);
    v.pop_back();
}

int main()
{
    scanf("%d %d", &n,&m);
    for(int i=1; i<=n; i++){
        scanf("%s", a[i]+1);
    }
    b[1]='L';
    b[2]='R';
    b[3]='U';
    b[4]='D';
    dfs(1, 1);
    for(int i=1; i<w.size(); i++){
        if(w[i].first==w[i-1].first){
            if(w[i].second==w[i-1].second-1){
                vv.push_back(1);
            }
            else{
                vv.push_back(2);
            }
        }
        else{
            if(w[i].first==w[i-1].first-1){
                vv.push_back(3);
            }
            else{
                vv.push_back(4);
            }
        }
    }

    int flag1 = 0, flag2 = 0;
    int x=1, y=1;
    for(int i=0; i<vv.size(); i++){
        if(vv[i]==2&&!flag1){
            puts("R");
            int xx,yy;
            cin>>xx>>yy;
            flag1=1;
            if(x==xx&&y==yy){
                swap(b[1],b[2]);
                puts("L");
                cin>>x>>y;
            }
        }
        else if(vv[i]==4&&!flag2){
            puts("D");
            int xx,yy;
            cin>>xx>>yy;
            flag2=1;
            if(x==xx&&y==yy){
                swap(b[3],b[4]);
                puts("U");
                cin>>x>>y;
            }
        }
        else{
            cout<<b[vv[i]]<<endl;
            cin>>x>>y;
        }
    }

}

E：

题意：题目大意：用公共边且颜色相同的两个块属于同一个连通块，每次询问一个区间中有多少个连通块块。

解法：线段树套并查集。

比较基本的思路就是因为行数比较小所以可以对于每个区间的左右两列维护并查集。

维护的东西必须保证在该区间中可以连通的两个位置的编号相同。

两个区间合并的时候，将两个区间左右两列的编号在并查集中的父亲赋值成自己。如果两个区间相邻的位置颜色相同就用并查

集合并起来，然后此时再从并查集中查询区间左右列的编号即可。

也就是说我们每个区间的左右两列维护的是一个连通块的编号，合并的时候用并查集进行合并。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
struct node{
    int ls[11], rs[11], sum;
}tree[maxn*4];
int n, m, q, x, y, mp[11][maxn], tot;
int fa[maxn*10];
int find_set(int x){
    if(x==fa[x]) return x;
    else return fa[x]=find_set(fa[x]);
}
void union_set(int x,int y){
    int fx=find_set(x),fy=find_set(y);
    if(fx!=fy){
        fa[fx]=fy;
    }
}

node pushup(node a, node b, int mid){
    node res;
    res.sum=a.sum+b.sum;
    for(int i=1; i<=n; i++){
        fa[a.ls[i]]=a.ls[i];
        fa[b.ls[i]]=b.ls[i];
        fa[a.rs[i]]=a.rs[i];
        fa[b.rs[i]]=b.rs[i];
    }
    for(int i=1; i<=n; i++){
        if(mp[i][mid]==mp[i][mid+1]){
            if(find_set(a.rs[i])!=find_set(b.ls[i])){
                res.sum--;
                union_set(a.rs[i],b.ls[i]);
            }
        }
    }
    for(int i=1; i<=n; i++){
        res.ls[i]=find_set(a.ls[i]);
        res.rs[i]=find_set(b.rs[i]);
    }
    return res;
}

void build(int l, int r, int rt){
    if(l==r){
        for(int i=1; i<=n; i++){
            if(mp[i-1][l]==mp[i][l]) tree[rt].ls[i]=tree[rt].rs[i]=tree[rt].ls[i-1];
            else tree[rt].ls[i]=tree[rt].rs[i]=++tot,tree[rt].sum++;
        }
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    tree[rt]=pushup(tree[rt<<1],tree[rt<<1|1],mid);
}

node query(int L, int R, int l, int r, int rt)
{
    if(L<=l&&r<=R){
        return tree[rt];
    }
    int mid=(l+r)/2;
    if(R<=mid) return query(L,R,l,mid,rt<<1);
    else if(L>mid) return query(L,R,mid+1,r,rt<<1|1);
    else return pushup(query(L,R,l,mid,rt<<1),query(L,R,mid+1,r,rt<<1|1),mid);
}
int main()
{
    memset(tree, 0, sizeof(tree));
    tot=0;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            scanf("%d",&mp[i][j]);
        }
    }
    build(1,m,1);
    while(q--){
        scanf("%d %d", &x,&y);
        int ans=query(x,y,1,m,1).sum;
        printf("%d\n", ans);
    }
    return 0;
}