Codeforces Round #632 (Div. 2)

A.Little Artem
构建一个n*m的矩阵,填充上B和W,使得四周存在W的B的数量=四周存在B的W的数量+1。
解 如果n*m为奇数,那么BW交换填充即可,否则把第一个W改成B即可。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
const int MAXN=1e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
char a[205][205];
void work()
{
    int n,m;
    scanf("%d%d",&n,&m);
    if(n%2==1&&m%2==1){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if((i+j)%2==0){
                    printf("B");
                }else{
                    printf("W");
                }
            }
            printf("\n");
        }
    }else{
        bool f=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if((i+j)%2==0){
                    printf("B");
                }else{
                    if(!f){
                        printf("B");
                        f=1;
                    }else
                        printf("W");
                }
            }
            printf("\n");
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

B.Kind Anton
给2个数组,a数组只有-1,0,1,你可以进行一系列操作,add(i,j)= a[j]+=a[i],j>i。
问能够使得a数组=b数组。
解 如果在这个点的前面存在1,那么b[i]>a[i]的情况可以解决,如果在这个点的前面存在-1,那么b[i]<a[i]的情况可以解决,所以找到第一个1,判断从开头到这个位置是否存在b[i]>a[i]那么就是不行的;同理-1。要注意找不到的情况。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
const int MAXN=1e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int a[MAXN];
int b[MAXN];
void work()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
    }
    int f1=0;
    int f2=0;
    for(int i=1;i<=n;i++){
        if(f1==0){
            if(a[i]==1){
                f1=i;
            }
        }
        if(f2==0){
            if(a[i]==-1){
                f2=i;
            }
        }
    }
    if(f1==0){
        f1=n;
    }
    if(f2==0){
        f2=n;
    }
    for(int i=1;i<=f1;i++){
        if(b[i]>a[i]){
            printf("NO\n");return;
        }
    }
    for(int i=1;i<=f2;i++){
        if(b[i]<a[i]){
            printf("NO\n");return;
        }
    }
    printf("YES\n");
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

C.Eugene and an array
给一个序列,问有多少个子区间,他们没有和为0的子区间。
解:即要求选择的区间的前缀和各不相同,使用map记录前缀和,再用一个变量记录当前最远能到哪里(指从该位置往前),计算即可。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
const int MAXN=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
ll a[MAXN];
void work()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    map<ll,int>m;
    ll sum=0;
    ll ans=0;
    m[0]=1;
    int last=0;
    for(int i=1;i<=n;i++){
        sum+=a[i];
        if(m[sum]==0){
            ans+=i-last;
            m[sum]=i+1;
        }else{
            last=max(m[sum],last);
            ans+=i-last;
            m[sum]=i+1;
        }
    }
    printf("%lld\n",ans);
 
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

D.Challenges in school №41
给定n和k,然后给一个长度为n的字符串,如果相邻的2个数为”RL”时,可以将其变成”LR”,要求刚好k次操作使得该字符串无法再变。
解 使用vector去尽量每次多的改变,然后就可以得到最多的操作次数sum和最少的操作次数cnt,然后去拟合k即可。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
const int MAXN=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
char a[3005];
vector<int>v[10005];
void work()
{
    int n,k;
    scanf("%d%d",&n,&k);
    scanf("%s",a+1);
    int sum=0;
    int cnt=0;
    for(int i=1;;i++){
        bool f=0;
        for(int j=1;j<n;j++){
            if(a[j]=='R'&&a[j+1]=='L'){
                f=1;
                swap(a[j],a[j+1]);
                v[i].push_back(j);
                sum++;
                j++;
            }
        }
        if(!f){
            cnt=i-1;
            break;
        }
    }
    if(sum<k||k<cnt){
        printf("-1\n");return;
    }
    int tmp=sum-k;
    for(int i=1;i<=cnt;i++){
        if(tmp==0){
            for(int j=0;j<v[i].size();j++){
                printf("1 %d\n",v[i][j]);
            }
        }else if(tmp<v[i].size()){
            printf("%d",tmp+1);
            for(int j=0;j<tmp+1;j++){
                printf(" %d",v[i][j]);
            }
            printf("\n");
            for(int j=tmp+1;j<v[i].size();j++){
                printf("1 %d\n",v[i][j]);
            }
            tmp=0;
        }else{
            printf("%d",v[i].size());
            for(int j=0;j<v[i].size();j++){
                printf(" %d",v[i][j]);
            }
            printf("\n");
            tmp-=v[i].size()-1;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

E.Road to 1600
给一个国际象棋的车(能上下左右走)和皇后(能上下左右+45度走),都从(1,1)开始,每次前往能走到的没经过的最小的点,如果不存在能走到的没经过的点,那么花费1到达当前没走过的最小的点,要求皇后的花费比车多,构造一个n*n的矩阵。
解 3*3是可以构造出来的,那么只要把n*n缩到3*3即可,即剩下的部分直接从1开始长蛇形排列。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
const int MAXN=5e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int a[505][505];
int b[3][3]={1,8,2,
             5,4,3,
             9,7,6,};
void work()
{
    int n;
    scanf("%d",&n);
    if(n<=2){
        printf("-1\n");return;
    }
    int cnt=0;
    for(int i=1;i<=n-3;i++){
        if(i&1){
            for(int j=1;j<=n;j++){
                a[i][j]=++cnt;
            }
        }else{
            for(int j=n;j>=1;j--){
                a[i][j]=++cnt;
            }
        }
        
    }
    if(n%2==0){
        for(int i=n;i>3;i--){
            if(i&1){
                for(int j=n;j>=n-2;j--){
                    a[j][i]=++cnt;
                }
            }else{
                for(int j=n-2;j<=n;j++){
                    a[j][i]=++cnt;
                }
            }
        }
        for(int i=n-2;i<=n;i++){
            for(int j=1;j<=3;j++){
                a[i][j]=b[n-i][3-j]+cnt;
            }
        }
    }else{
        for(int i=1;i<=n-3;i++){
            if(i&1){
                for(int j=n-2;j<=n;j++){
                    a[j][i]=++cnt;
                }
            }else{
                for(int j=n;j>=n-2;j--){
                    a[j][i]=++cnt;
                }
            }
        }
        for(int i=n-2;i<=n;i++){
            for(int j=n-2;j<=n;j++){
                a[i][j]=b[i-n+2][j-n+2]+cnt;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

 

F.Kate and imperfection
要求从1-n中取出k个数(k从2-n),使得取出的集合两两数的gcd的最大值最小。
解 首先将素数筛出来,前面的数一定是取素数,答案为1,然后素数取完之后,枚举答案从2到n/2(n/2是n个数的时候的答案),判断再加入一个数能否满足答案为该值,因为当前所有素数都已经被取了,那么在取一个合数的时候(注意只是1个的时候),答案是这个数的素因子中最大的那一个,所以枚举素数乘上当前答案判断是否小于n即可。要注意的是 枚举的素数不能超过当前答案,同时枚举的素数不能超过答案的最小非1因子。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
const int MAXN=5e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int prime[MAXN];
int vis[MAXN];
int x=0;
void oulasai(int n)  //欧拉筛
{
    for(int i=2;i<=n;i++)
    {
        if(!vis[i]) prime[x++]=i;
        for(int j=0;j<x;j++)
        {
            if(i*prime[j]>n) break;
            vis[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}
void work()
{
    int n;
    scanf("%d",&n);
    oulasai(n);
    for(int i=1;i<=x;i++){
        printf("%d ",1);
    }
    if(n>=4){
        for(int now=2;now<=n/2;now++){
            int tmp;
            for(int i=0;i<x;i++){
                if(now%prime[i]==0){
                    tmp=prime[i];break;
                }
            }
            for(int i=0;i<x;i++){
                if(now*prime[i]<=n&&prime[i]<=tmp){
                    printf("%d ",now);
                }else{
                    break;
                }
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

再写一个正常的做法,每个合数的贡献是他的最大因子。
证明:首先会将所有素数加入,然后对于答案2的情况,我们可以加入4,6,8,10等等中的任意一个,当然我们贪心的选择4,那么我们在选入每个合数的时候,我们可以保证,他的因子必定已经被选入,那么这个数的贡献就是他的最大因子,所以求每个数的最大因子,sort排序即可。
附上wcy的代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5+10;
int p[N],flg[N],tot,n;
bool cmp(int x,int y){
    if(flg[x]!=flg[y]) return flg[x]<flg[y];
    else return x<y;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        p[i]=i;
        for(int j=i*2;j<=n;j+=i) flg[j]=i;
    }
    sort(p+1,p+1+n,cmp);
    for(int i=2;i<=n;++i) printf("%d ",flg[p[i]]);
}

 

发表评论

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