发布于

CF1072

CF1072A
一道简单题。
可以不断地切割成子问题。
然后统计计算即可。

CF1072B
一道猜结论题。
我们猜测，对于\([0,3]\)当\(t_i\)确定的时候，\(t_i | t_{i+1}==a_i\)与\(t_i \& t_{i+1}==b_i\)可以推导出唯一确定的\(t_{i+1}\)
证明很复杂，但是正确性很显然。
那么依据这个结论，可以简单\(DFS\)，从而得出结果。

CF1072C
一道复杂题。
它再一次警醒了我——
你tm不会二分。

做法很显然，因为答案显然具有单调性，所以二分\(k\)，然后\(O(n)\)检验即可。
检验的时候贪心地排布即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
#define Abs(_A) ((_A)?(_A):(-(_A))
#define INF 0x3f3f3f3f
/*
CF1072A
*/
int w,h,k;
void init(){
    int ans=0;
    scanf("%d%d%d",&w,&h,&k);
    while(k){
        ans+=((w<<1)+(h<<1)-4);
        --k;
        h-=4,w-=4;
    }
    printf("%d",ans);
}
int main(){
	init();
	return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
#define Abs(_A) ((_A)?(_A):(-(_A))
#define INF 0x3f3f3f3f
/*
CF1072B
*/
int n,a[100005],b[100005],t[100005];
void init(){
    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]);
    }
    for(int i=0;i<=4;++i){
        if(i==4){
            puts("NO");
            return;
        }
        t[1]=i;
        for(int j=1;j<n;++j){
            for(int k=0;k<=4;++k){
                if(k==4){
                    goto loop;
                }
                if((t[j]|k)==a[j]&&(t[j]&k)==b[j]){
                    t[j+1]=k;
                    break;
                }
            }
            if(j==n-1){
                puts("YES");
                for(int i=1;i<=n;++i){
                    printf("%d ",t[i]);
                }
                return;
            }
        }
        loop:;
    }
    
}
int main(){
	init();
	return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
#define Abs(_A) ((_A)?(_A):(-(_A))
#define INF 0x3f3f3f3f
/*
CF1072C
*/
bool bo[100005];
int a,b,at,bt,al[50005],bl[50005];
inline bool chck(int k){
    memset(bo,0,sizeof(bo));
    int nw=k,att=0,btt=0;
    at=0,bt=0;
    while(nw){
        if(att+nw<=a){
            att+=nw;
            bo[nw]=1;
            al[at++]=nw;
        }
        --nw;
    }
    nw=k;
    while(nw){
        if((!bo[nw])&&(btt+nw<=b)){
            btt+=nw;
            bo[nw]=1;
            bl[bt++]=nw;
        }
        --nw;
    }
    for(int i=1;i<=k;++i){
        if(!bo[i]){
            return 0;
        }
    }
    return 1;
}

void init(){
    scanf("%d%d",&a,&b);
    int l=0,r=100000,mid,ans=0;
    while(l<=r){
        mid=((l+r)>>1);
        if(chck(mid)){
            ans=Max(ans,mid);
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    chck(ans);
    printf("%d\n",at);
    for(int i=0;i<at;++i){
        printf("%d ",al[i]);
    }
    puts("");
    printf("%d\n",bt);
    for(int i=0;i<bt;++i){
        printf("%d ",bl[i]);
    }
    puts("");
}
int main(){
	init();
	return 0;
}