AtCoder Regular Contest 80

C. 4-adjacent

给定序列$a_i$，询问是否存在一个排列，满足$a_{p[i]}* a_{p[i + 1]}$是4的倍数

贪心构造

首先把只是2的倍数的数拿出来，放在最右边

前面把是1的倍数的数和是4的倍数的数交替放置即可

之后随意判断即可

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

extern inline char gc() {

    static char RR[], *S = RR + , *T = RR + ;

    if(S == T) fread(RR, , , stdin), S = RR;

    return *S ++;

}

inline int read() {

    int p = , w = ; char c = gc();

    while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }

    while(c >= '' && c <= '') p = p *  + c - '', c = gc();

    return p * w;

}

#define ri register int

int n, n2, n4, flag;

int main() {

    n = read();

    for(ri i = ; i <= n; i ++) {

        int x = read();

        if(x %  == ) n4 ++;

        else if(x %  == ) n2 ++;

    }

    n -= n2;

    if(n & ) {

        if(n2) flag = (n4 > n / );

        else flag = (n4 >= n / );

    }

    else flag = (n4 >= n / );

    if(flag) printf("Yes\n");

    else printf("No\n");

    return ;

}

D.Grid Coloring

对$R*W$的格子进行染色，需要使颜色$i$的出现次数为$c_i$

且同一颜色形成联通块，询问是否可行并给出一组方案

S形涂色即可

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define ri register int

#define sid 105

int H, W, n, id;

int col[sid][sid], ord[sid * sid];

int main() {

    scanf("%d%d%d", &H, &W, &n);

    for(ri i = ; i <= n; i ++) {

        int x; scanf("%d", &x);

        while(x --) ord[++ id] = i;

    }

    id = ;

    for(ri i = ; i <= H; i ++)

    for(ri j = ; j <= W; j ++)

    col[i][j] = ord[++ id];

    for(ri i = ; i <= H; i += )

    reverse(col[i] + , col[i] + W + );

    for(ri i = ; i <= H; i ++, printf("\n"))

    for(ri j = ; j <= W; j ++)

    printf("%d ", col[i][j]);

    return ;

}

E.Young Maids

题意略复杂，直接看原题面吧...

从前往后去贪心

每次选择的一定是某个区间中的奇（偶）最小值后其后的偶（奇）最小值

注意奇偶的判断即可

复杂度$O(n \log n)$

一开始表示平衡树裸题，然后点开题解，还是打st表吧

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

extern inline char gc() {

    static char RR[], *S = RR + , *T = RR + ;

    if(S == T) fread(RR, , , stdin), S = RR;

    return *S ++;

}

inline int read() {

    int p = , w = ; char c = gc();

    while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }

    while(c >= '' && c <= '') p = p *  + c - '', c = gc();

    return p * w;

}

#define sid 200050

#define inf 1e9

#define ri register int

int n;

int bit[sid], l_g[sid];

int st[sid][][], v[sid][], arc[sid];

void Init() {

    for(ri i = ; i <= ; i ++) bit[i] =  << i;

    for(ri i = ; i <= n; i ++) l_g[i] = l_g[i >> ] + ;

    for(ri o = ; o <= ; o ++)

    for(ri i = ; i <= n; i ++) st[i][][o] = v[i][o];

    for(ri o = ; o <= ; o ++)

    for(ri j = ; bit[j] <= n; j ++)

    for(ri i = ; i + bit[j] -  <= n; i ++)

    st[i][j][o] = min(st[i][j - ][o], st[i + bit[j - ]][j - ][o]);

}

inline int rmq(int l, int r, int o) {

    int lg = l_g[r - l + ];

    return min(st[l][lg][o], st[r - bit[lg] + ][lg][o]);

}

struct Seg {

    int v, l, r;

    friend bool operator < (Seg a, Seg b)

    { return a.v > b.v; }

};

priority_queue <Seg> q;

int main() {

    n = read();

    for(ri i = ; i <= n; i ++) {

        int w = (v[i][(i ^ ) & ] = read());

        v[i][i & ] = inf; arc[w] = i;

    }

    Init();

    q.push({ rmq(, n, ), , n });

    while(!q.empty()) {

        Seg tmp = q.top(); q.pop();

        int w1 = tmp.v, pw1 = arc[w1];

        int w2 = rmq(pw1 + , tmp.r, pw1 & ), pw2 = arc[w2];

        printf("%d %d ", w1, w2);

        if(tmp.l != pw1) q.push({ rmq(tmp.l, pw1 - , (tmp.l + ) & ), tmp.l, pw1 -  });

        if(pw1 +  != pw2) q.push({ rmq(pw1 + , pw2 - , pw1 & ), pw1 + , pw2 -  });

        if(pw2 != tmp.r) q.push({ rmq(pw2 + , tmp.r, pw2 & ), pw2 + , tmp.r });

    }

    return ;

}

F.Prime Flip

有$n$个位置的牌向上，

每次可以选定一段长为$p$($p$为奇质数)的区间，翻转这个区间

询问最少几次能使所有牌向下

考虑构造新序列$e_i = [a_i = a_{i + 1}]$，$a_i$表示向上还是向下

当$e_i$全部为0时，原序列全部向下

那么，原题的区间操作转化为同时对两个点翻转

两个点匹配有3种情况

1.相差为奇质数，需要1次

2.相差为偶数，需要2次

3.否则，需要3次

对于第一种情况，做二分图匹配

第二种情况，讨论

第三种情况，讨论

对我而言是神题，不会做.....

然而有一堆AK的神仙....

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define ri register int

#define ssd 10000010

#define sid 205

int n, N = 1e7;

int pr[ssd / ], tot;

int nj, no, js[sid], os[sid];

bool nop[ssd], e[ssd];

int tim, vis[sid], mat[sid];

bool ex[sid][sid];

inline void Init() {

    nop[] = ;

    for(ri i = ; i <= N + ; i ++) {

        if(!nop[i]) pr[++ tot] = i;

        for(ri j = ; j <= tot; j ++) {

            int nx = i * pr[j]; if(nx > N + ) break;

            nop[nx] = ; if(i % pr[j] == ) break;

        }

    }

    nop[] = ;

}

inline int dfs(int o) {

    for(int i = ; i <= no; i ++)

    if(ex[o][i] && vis[i] != tim) {

        vis[i] = tim;

        if(!mat[i] || dfs(mat[i]))

        return mat[i] = o, ;

    }

    return ;

}

int main() {

    Init();

    cin >> n;

    for(ri i = ; i <= n; i ++) { int x; cin >> x; e[x] = ; }

    for(ri i = ; i <= N + ; i ++)

    if(e[i] != e[i - ]) {

        if(i & ) js[++ nj] = i;

        else os[++ no] = i;

    }

    for(ri i = ; i <= nj; i ++)

    for(ri j = ; j <= no; j ++)

    if(!nop[abs(js[i] - os[j])]) ex[i][j] = ;

    int num = , ans = ;

    for(ri i = ; i <= nj; i ++)

    ++ tim, num += dfs(i);

    nj -= num; no -= num;

    ans = num + nj /  *  + no /  *  + (nj & ) * ;

    printf("%d\n", ans);

    return ;

}

巴特西

AtCoder Regular Contest 80

最新文章

热门文章