笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

「水」CF768C Jon Snow and his Favourite Number

posted on 2020-05-28 19:37:38 | under 题解 |

打个表发现有循环节,然后我就 naive 地觉得循环节大小一定是 $2$ 导致爆了 OJ。

发现循环节的长度不会超过 $200$。于是就可以暴力 $200$ 次找出循环节来然后做。这样的复杂度是 $O(200\cdot n)$ 的。

关于循环节,个人的理解仅限于 xor 运算有自反性,所以显然循环节应该是偶数长度的。

…不会编了。就当是一个乱搞吧= =

话说我确实没怎么写过乱搞,业务生疏.jpg


int cnt ;
int p, q ;
int n, k, m ;

int rec[M][N] ;
int base[N] ;
int buc[N] ;
int cycle ;

bool cmp(int *a, int *b){
    for (int i = 1 ; i <= n ; ++ i)
        if (a[i] != b[i]) return 0 ;
    return 1 ;
}
int cmp_rec(int *a){
    for (int i = 0 ; i < cnt ; ++ i)
        if (cmp(rec[i], a)) return i ;
    return -1 ;
}
int main(){
    cin >> n >> k >> m ;
    for (int i = 1 ; i <= n ; ++ i)
        base[i] = qr() ; p = -1, q = P ;
    sort(base + 1, base + n + 1) ;
    memcpy(rec[0], base, sizeof(base)) ;
    if (!k){
        for (int i = 1 ; i <= n ; ++ i)
            chkmax(p, base[i]), chkmin(q, base[i]) ;
        cout << p << " " << q << '\n' ;
        return 0 ;
    }
    while (k){
        -- k ; ++ cnt ; //debug(cnt) ;
        for (int i = 1 ; i <= n ; ++ i)
            rec[cnt][i] = rec[cnt - 1][i] ^ (i & 1) * m ;
        sort(rec[cnt] + 1, rec[cnt] + n + 1) ; //debug(rec[cnt], 1, n) ;
        if ((cycle = cnt - cmp_rec(rec[cnt])) <= cnt) break ;
    }
    if (k)
        k %= cycle, cnt -= cycle - k ;
    for (int i = 1 ; i <= n ; ++ i){
        chkmax(p, rec[cnt][i]) ;
        chkmin(q, rec[cnt][i]) ;
    }
    cout << p << " " << q << '\n' ;
}