P9687 Maps.题解

· · 题解

P9687 Maps.题解

题目意思：

每组数据里，0 代表白色，而 1 代表黑色，要保证正好有 p 个白色在两个黑色之间。要保证一定是字典序最好的，长度为 n，如果没有满足要求的，那么输出 -1，一共有 T 组数据！

大致思路：

我们先不来管不能满足要求的，看满足条件，我们可以先判断长度 n，是不是偶数，如果是那么我们可以发现第一位一定要为 0，奇数第一位就要是 1，所以我们建一个变量来算，接着我们可以先把它变成一种序列，那么就是由 0 和 1 交错组成的序列，根据 n 的奇偶性，来生成序列，因为要使字典序最小，所以我们可以从后往前看，找出前 p 个 101 组合，如果有多的，找出第一个多出的地方，记录它的编号 i，记录到 t 里，为了让它正好有 p 个，所以我们把前 t 个字符都改成字典序小的 0，输出即可，注意的是如果正好是 p 个，那就不要变化，最后输出，不加空格。接着就是不能满足要求的，当我发现规律是 n 的一半小于 p 时，兴奋地提交了上去，喜提 70 分 当我先要放弃时，找到了反例，那么又是奇偶性，所以只需要再加上一种可能，p × 2 等于 n 时，也是 - 1。至于为什么造成这种情况，因为计算时如果除不尽那么会自动向下取整。

代码实现：

#include<bits/stdc++.h>
using namespace std;
long long t,a[1000001],l;
long long n,p,cnt;
int main(){
    cin>>t;
    for(int i=1;i<=t;i++){
        cin>>n>>p;
        int o=n;
        if(p*2>=n){//没有满足条件的
            cout<<-1<<endl;
        }else{
            memset(a,0,sizeof a);
            l=0;
            int k=1;//判断奇偶性的
            if(n%2==0){
                a[1]=0;
                k++;
            }
            for(int j=k;j<=n;j++){
                if(a[j-1]==0){
                    a[j]=1;//10交错
                }else{
                    a[j]=0;//10交错
                }
            }
            cnt=0;
            for(int j=n;j>=1;j--){
                if(j==n||j==1) continue;//防止越界
                if(a[j]==0&&a[j-1]==1&&a[j+1]==1){//看看满不满足101子串条件
                    cnt++;//数量加1
                    if(cnt>p){
                        l=j;
                        break;//直接结束
                    }
                }
            }
            for(int j=1;j<=n;j++){
                if(l==0){//特判，如果没有多余
                    cout<<a[j];
                    continue;
                }
                if(j<=l){
                    cout<<0;//输出
                }else{
                    cout<<a[j];//输出
                }
            }
            cout<<endl;//换行
        }
    }
    return 0;
}

这样，一道普及的题目就解决啦！

希望能给大家带来一些好的思路！！！