CF1721

方杰123 · 2022-08-28 09:37:09 · 个人记录

A. Image

思路

每次选一或两个相同颜色修改，总共四个。除非一种颜色有3个，否则一种颜色可以一次修改。有三个的颜色只有一种，不改它就行了。

所以每种颜色改一次，总共改颜色数-1。

code

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=1;char c=getchar();
    while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
int n,a[45],maxn,cnt;char c;
int main(){
    n=read();
    while(n--){
        memset(a,0,sizeof(a));cnt=0;
        for(int i=1;i<=4;i++){
            cin>>c;
            a[c-'a'+1]++;
            if(a[c-'a'+1]==1)cnt++;
        }
        printf("%d\n",cnt-1);
    }
    return 0;
} 

B. Deadly Laser

思路

障碍是个菱形，既然不能出边界，那么最优路线是右走到底，下走到底，或下走到底，右走到底。那么判断一下障碍有没有遮到顶部，底部，左边，右边就可以了。

code

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=1;char c=getchar();
    while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
int t,n,m,sx,sy,d,up,down,lef,righ;
int main(){
    t=read();
    while(t--){
        up=down=lef=righ=0;
        n=read(),m=read();
        sx=read(),sy=read(),d=read();
        if(sx-d<=1)up=1;
        if(sx+d>=n)down=1;
        if(sy-d<=1)lef=1;
        if(sy+d>=m)righ=1;
        if(!up && !righ || !lef && !down)printf("%d\n",n+m-2);
        else printf("-1\n");
    }
    return 0;
}

C. Min-Max Array Transformation

题意

给你个不降a数组，给每个数加上d_i，再升序排序，形成b数组。 求d_i的最大最小值。

思路

其实就是给a找个匹配的b，使得其他数可以一一对应，找到最小的b，和最大的b，数字对应的条件a_i\le b_i。

找最小值。只要找到第一个大于等于a_i的b_j，假设i与j交换对应的数。因为题目肯定保证a_i\le b_i（不然没法做），所以j\le i。因为a_j\le b_j，b_j\le b_i，所以a_j\le b_i，交换后依然对应。找第一个大于等于a_i的数开两个指针O(n)即可完成。

找最大值。假设i与j交换位置，那么最可能的策略是这样的：

找最大值要j尽量大，但是只要其中一个a_k>b_{k-1}（即图中灰线断裂）就无法匹配，所以找到每个i往右的灰线断裂的位置前一个。这个倒着处理也是O(n)

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+110;
int read(){
    int x=0,f=1;char c=getchar();
    while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
int t,n,a[N],b[N],minn[N],maxn[N],bk[N];
signed main(){
    t=read();
    while(t--){
        n=read();
        for(int i=1;i<=n;i++)a[i]=read();
        for(int i=1;i<=n;i++)b[i]=read();
        int l=1,r=1;
        while(l<=n){
            if(a[l]<=b[r])minn[l]=b[r]-a[l],l++;
            else r++;
        }
        memset(bk,0,sizeof(bk));
        for(int i=1;i<n;i++)if(a[i+1]<=b[i])bk[i]=1;
        int now=n;
        for(int i=n;i>=1;i--){
            maxn[i]=b[now]-a[i];
            if(!bk[i-1])now=i-1;
        }
        for(int i=1;i<=n;i++)printf("%lld ",minn[i]);printf("\n");
        for(int i=1;i<=n;i++)printf("%lld ",maxn[i]);printf("\n");
    }
    return 0;
}

D. Maximum AND

思路

考场最后几分钟才发现看错题目了。。。。。。把&看成|

首先对a，b数组匹配应首先满足答案最高位能形成1，其次是第二高位.......依此类推。

想要在第i位形成1，必须每个a，b异或之后第i位为一（0配1），那么如果能满足，那么考虑i-1位时应满足第i位必须是0配1。所以把这些数中第i位为0和第i位为一的分开处理。

具体来说对于(l,r)这个子问题，如果第i位的a中0的数量与b中1的数量一样的话，并且其他区间也满足这个条件，那么下一位应分为(l,mid)和(mid+1,r)。其中(l,mid)是a第i位为0，b第i位为1的区间；(mid+1,r)是a第i位为1，b第i位为0的区间 。否则不需要限制还是(l,r)。

因为是否分区间要根据整层判断。所以使用bfs，因为最多只有n个区间，不会爆队列。最后记得每个数据之后清空队列，这很重要，因为它已经三杀了。

如果排序是O(n \log n)，那么总复杂度是O(30\times n \log n)。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int read(){
    int x=0,f=1;char c=getchar();
    while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
struct node{
    int l,r;
};
int now,n,T,a[N],b[N],ans;
bool cmp1(int x,int y){return (x&(1<<now))<(y&(1<<now));}
bool cmp2(int x,int y){return (x&(1<<now))>(y&(1<<now));}
queue<node>q,t,bk;
int main(){
    T=read();
    while(T--){
        while(!q.empty())q.pop();
        n=read();
        for(int i=1;i<=n;i++)a[i]=read();
        for(int i=1;i<=n;i++)b[i]=read();
        q.push((node){1,n});
        now=30;ans=0;
        while(now>=0){
            int flag=1;
            while(!q.empty()){
                node tmp=q.front();t.push(tmp);q.pop();
                int l=tmp.l,r=tmp.r;
                sort(a+l,a+r+1,cmp1);
                sort(b+l,b+r+1,cmp2);

                int L=tmp.l,R=tmp.r,ans=R+1;
                while(L<=R){
                    int mid=L+R>>1;
                    if((a[mid]&(1<<now))>0)ans=mid,R=mid-1;
                    else L=mid+1;
                }
                int num0=ans-l;

                L=tmp.l,R=tmp.r,ans=R+1;
                while(L<=R){
                    int mid=L+R>>1;
                    if((b[mid]&(1<<now))==0)ans=mid,R=mid-1;
                    else L=mid+1;
                }
                int num1=ans-l;

                bk.push((node){num0,num1});
                if(num0!=num1)flag=0;
            }
            if(flag){
                ans+=(1<<now);
                while(!t.empty()){
                    if(bk.front().l>=1)q.push((node){t.front().l,t.front().l+bk.front().l-1});
                    if(t.front().l+bk.front().l<=t.front().r)q.push((node){t.front().l+bk.front().l,t.front().r});
                    t.pop();bk.pop();
                }
            }
            else while(!t.empty()){q.push(t.front());t.pop();bk.pop();}
            now--;
        }
        printf("%d\n",ans);
    }
    return 0;
}