CSP模拟6

yszy / 2023-07-29 / 原文

CF怎么这么多构造。。。。。。

A.排序

考试是排列原题不是排列。

排列的话直接每次以x为第一位y中最大值就好了。直接莽了1000棵线段树。考完一看别人都是\(n ^{2}\)......

原题把序列改成排列就好。

Xorum
昨天考了数位DP，以为今天又来了。神仙随机化直接100。

神奇构造。

x为奇数最低位一定是1,把x除最低位的其他数都消掉就好。

    while(n){
        pos=lowbit(n);
        n-=lowbit(n);
    }
    while(lowbit(y)!=pos){
        ans[++anstot]=(Node){1,y,y};
        y<<=1;
    }//把y最低位与x最高位冲齐。
	
    int z=(x^y);
    ans[++anstot]=(Node){2,x,y};
    int a=y+z;
    ans[++anstot]=(Node){1,y,z};
    int b=(y<<1);
    ans[++anstot]=(Node){1,y,y};
    int c=a^b;
    ans[++anstot]=(Node){2,a,b};
    int d=c^x;
    ans[++anstot]=(Node){2,c,x};

    while(y!=pos){
        if((y&d)==d){
            ans[++anstot]=(Node){2,y,d};
            y=y^d;
        }
        ans[++anstot]=(Node){1,d,d};
        d=d<<1;
    }//把y消掉只剩下1位。
    ans[++anstot]=(Node){2,x,y};
    x=x^y;//消去x的一位。

有趣的区间问题
扫描线/分治。
~~数据结构狗都不写。~~
考试的时候单调栈+线段树写挂了。

处理每一位作为最大值和最小值的控制区间，染色。当值为2的时候记录答案。

码量又大又难调还要卡常，直接被分治嘲讽。但加上Flandres的小工具跑的飞快给我看傻了
Code

无聊的卡牌问题
构造
鸽了