Codeforces Round #470 (rated, Div. 2, based on VK Cup 2018 Round 1) 题解报告

题目链接http://codeforces.com/contest/948

A

  • 羊被狼吃掉只有当羊跟狼相邻的时候才有可能,否则我们在羊的周围一圈放狗就好了。
const int N=500+10;
int n,m,i,j,k,a[N];
int dir_x[]={0,1,0,-1};
int dir_y[]={1,0,-1,0};
char maze[N][N];
int main(){
    read(n),read(m);
    bool flag=true;
    for (i=1;i<=n;i++) scanf("%s",maze[i]+1);
    for (i=1;i<=n;i++){
        for (j=1;j<=m;j++){
            if (maze[i][j]=='S'){
                for (k=0;k<4;k++){
                    int tx=i+dir_x[k];
                    int ty=j+dir_y[k];
                    if (tx<1||tx>n||ty<1||ty>m) continue;
                    if (maze[tx][ty]=='W'){
                        flag=false;
                    }
                    else if (maze[tx][ty]=='.') maze[tx][ty]='D';
                }
            }
        }
    }
    if (flag){
        puts("Yes");
        for (i=1;i<=n;i++){
            puts(maze[i]+1);
        }
    }
    else puts("No");
    return 0;
}

B

  • 找出X_2最大的质因子将X_1的范围限制在[X_2-p+1,X_2]里然后枚举X_1去找最小的可能的X_0即可,最大的质因子是因为我们要让X_1的可选范围尽可能的大,才能找到最小的满足条件的X_0
const int N=(int)1e6+10;
int i,j,tot,Prime[N];
bool isPrime[N];
void init(){
    int i,j;
    for (i=2;i<=N-10;i++){
        if (!isPrime[i]){
            Prime[++Prime[0]]=i;
            if (!tot&&i>1000) tot=Prime[0]-1;
        }
        for (j=1;i*Prime[j]<=N-10 && j<=Prime[0];j++){
            isPrime[i*Prime[j]]=true;
            if (i%Prime[j]==0) break;
        }
    }
}
int get(int x){
    if (i==1) return 1;
    for (int i=1;i<=tot;i++){
        if (x%Prime[i]==0){
            while (x%Prime[i]==0){
                x/=Prime[i];
            }
            if (x==1){
                return Prime[i];
            }
        }
    }
    return x;
}
int main(){
    init();
    int x;
    read(x);
    int tmp=x,tmp2=x,y;
    for (i=1;i<=tot;i++){
        if (x%Prime[i]==0){
            while (x%Prime[i]==0){
                x/=Prime[i];
            }
            if (x==1){
                y=Prime[i];
                break;
            }
        }
    }
    if (x!=1) y=x;
    x=tmp-y+1;
    tmp=x;
    int ans=0;
    for (i=x;i<=tmp2;i++){
        int res,ttt;
        if (!isPrime[i]) ttt=i;
        else res=get(i),ttt=i-res+1;
        if (ttt<3) continue;
        if (ans==0) ans=ttt;
        else ans=min(ans,ttt);
    }
    cout<<ans<<endl;
    return 0;
}

C

  • 考场上写崩了然后掉分GG...题解的方法有待研究,自己的方法是用线段树维护区间最小值和不为0的个数,如果一个区间全部变成零了那就不往下找了,是把线段树当作一颗树来搜索的思想,大半夜思绪混乱代码写的乱七八糟。。。今天缕了一下思路重写了一下。
const int N=1e5+10;
int n,i,cnt[N<<2];
ll mn[N<<2],flag[N<<2],res=0;
void pushup(int root){
    mn[root]=min(mn[root<<1],mn[root<<1|1]);
    cnt[root]=cnt[root<<1]+cnt[root<<1|1];
}
void pushdown(int root){
    if (flag[root]){
        mn[root<<1]-=flag[root];
        mn[root<<1|1]-=flag[root];
        flag[root<<1]+=flag[root];
        flag[root<<1|1]+=flag[root];
        flag[root]=0;
    }
}
void build(int root,int l,int r){
    if (l==r){
        read(mn[root]);
        if (mn[root]==0) mn[root]=INF,cnt[root]=0;
        else cnt[root]=1;
        return;
    }
    int mid=l+((r-l)>>1);
    build(lson);
    build(rson);
    pushup(root);
}
void update(int root,int l,int r,int L,int R,int val){
    if (mn[root]>1LL*1e9) return;
    if (l==r){
        if (mn[root]<=val){
            res+=mn[root];
            cnt[root]=0;
            mn[root]=INF;
        }
        else{
            res+=1LL*val;
            mn[root]-=val;
        }
        return;
    }
    if (L<=l&&r<=R&&mn[root]>val){
        res+=1LL*cnt[root]*val;
        flag[root]+=val;
        mn[root]-=val;
        return;
    }
    pushdown(root);
    int mid=l+((r-l)>>1);
    if (L<=mid) update(lson,L,R,val);
    if (mid<R) update(rson,L,R,val);
    pushup(root);
}
int main(){
    read(n);
    build(1,1,n);
    for (i=1;i<=n;i++){
        int x;read(x);
        res=0;
        if (x) update(1,1,n,1,i,x);
        printf("%lld ",res);
    }
    return 0;
}

D

  • 以后一定要先把题看完。。。这题过于水。。把P_i全部扔进01字典树,然后对a_i进行贪心的找异或最小的值即可,查询完后删除用过的数。
#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9')f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=300000+10;
int n,i,x,a[N];
struct Trie{
    int tot,i,ch[N*30][2],cnt[N*30];
    void Insert(int x){
        int p=0;
        for (i=29;i>=0;i--){
            int c=((x>>i)&1);
            if (!ch[p][c]) ch[p][c]=++tot;
            p=ch[p][c];
            cnt[p]++;
        }
    }
    void Remove(int x){
        int p=0;
        for (i=29;i>=0;i--){
            int c=((x>>i)&1);
            int pre=p;
            p=ch[p][c];
            if (--cnt[p]==0) ch[pre][c]=0;
        }
    }
    int Find(int x){
        int p=0,val=0;
        for (i=29;i>=0;i--){
            int c=((x>>i)&1);
            if (ch[p][c]) p=ch[p][c];
            else{
                p=ch[p][c^1];
                val+=(1<<i);
            }
        }
        Remove(val^x);
        return val;
    }
}T;
int main(){
    read(n);
    for (i=1;i<=n;i++) read(a[i]);
    for (i=1;i<=n;i++){
        read(x);
        T.Insert(x);
    }
    for (i=1;i<=n;i++){
        printf("%d%c",T.Find(a[i]),i==n?'\n':' ');
    }
    return 0;
}

E

  • 观察发现C经过一些变换都能变成B,所以BC可以看做同一个字母,且对于BA存在变换:B->AB,AB->B,B->AB,A->BB,可以知道B结尾的话前面的A可以任意添加和减少,而B每次的增加都是偶数次的,所以这启发我们通过序列中B的数目和以A结尾的长度进行分类讨论,因为这两者是决定问题的关键,B没法减少,结尾的A因为没有B所以只能减少,具体分类讨论见代码。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100000+10;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
int n,m,Q,i,l1,r1,l2,r2,cnt,sum1[N],sum2[N],a1[N],a2[N];
char s[N],t[N],ans[N];
int main(){
    scanf("%s%s",s+1,t+1);
    n=strlen(s+1),m=strlen(t+1);
    for (i=1;i<=n;i++){
        sum1[i]=sum1[i-1]+(s[i]!='A');
        if (s[i]=='A') a1[i]=a1[i-1]+1;
        else a1[i]=0;
    }
    for (i=1;i<=m;i++){
        sum2[i]=sum2[i-1]+(t[i]!='A');
        if (t[i]=='A') a2[i]=a2[i-1]+1;
        else a2[i]=0;
    }
    for (read(Q);Q--;cnt++){
        read(l1),read(r1),read(l2),read(r2);
        int suffa1=min(a1[r1],r1-l1+1),suffa2=min(a2[r2],r2-l2+1);
        int cntb1=sum1[r1]-sum1[l1-1],cntb2=sum2[r2]-sum2[l2-1];
        if (cntb1>cntb2) ans[cnt]='0';
        else if (cntb1==cntb2){
            if (suffa1>=suffa2&&(suffa1-suffa2)%3==0) ans[cnt]='1';
            else ans[cnt]='0';
        }
        else{
            if ((cntb2-cntb1)&1) ans[cnt]='0';
            else if (suffa2>suffa1) ans[cnt]='0';
            else if (suffa2==suffa1&&!cntb1) ans[cnt]='0';
            else ans[cnt]='1';
        }
    }
    puts(ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注