Cydiater

Codeforces Round #443 (Div. 1)

A. Short Program

我们发现不管操作多少次,因为位运算中位与位之间独立,所以我们只要对于每个转移构造一下就好了。代码就不贴了。

B. Teams Formation

没啥好说的吧,挺简单的。只要不写挂就行了,然后吸取一个经验就是 div1 一定要随手准备一个对拍的板子。一旦查不出错就赶紧写暴力拍。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cmax(a,b)        a = ((a) > (b) ? (a) : (b))
#define cmin(a,b)        a = ((a) < (b) ? (a) : (b))
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pii            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

const int MAXN = 1e5 + 5;

int a[MAXN], N, M, K, b[MAXN], c[MAXN], top = 0;
ll ans = 0;

int main(){
    scanf("%d%d%d", &N, &K, &M);
    up (i, 1, N) scanf("%d", &a[i]);
    int cnt = 0; 
    up (i, 1, N) {
         if (!top || a[i] != b[top]) {
            b[++top] = a[i];
            cnt = 1;
         }else if (a[i] == b[top]) {
             cnt++;
            b[++top] = a[i];
            while (cnt == K) {
                top -= K;
                cnt = c[top];
            }
         }
         c[top] = cnt;
    }
    N = top;
    up (i, 1, N) a[i] = b[i];
    int le, ri, o;
    for (le = 1, ri = N; le <= ri; le = o + 1, ri--) {
        if (a[le] != a[ri]) break;
        cnt = 0;
        up (i, le, ri) {
            if (a[i] != a[le]) break;
            o = i;
        }
        cnt = o - le + 1;
        if (ri > o) cnt++;
        while (ri - 1 >= o && a[ri - 1] == a[le]) {
            ri--;
            cnt++;
        }
        if (o == ri) {
            if (1LL * cnt * M % K == 0) {
                puts("0");
                return 0;
            }
            ans += 1LL * cnt * M % K;
            printf("%lld\n", ans);
            return 0;
        }
        if (cnt < K) {
            ans += 1LL * cnt * M;
            le = o + 1;
            ri--;
            break;
        }
        if (cnt % K != 0) {
            ans += 1LL * (cnt % K) * (M - 1);
            ans += cnt;
            le = o + 1;
            ri--;
            break;
        }else ans += cnt;
    }
    if (le <= ri) ans += 1LL * (ri - le + 1) * M;
    printf("%lld\n", ans);
    return 0;
}

C. Tournament

考虑任意两个点,如果一个点可以打败另一个点,那么连一条边。对于任意两个点,一定满足至少有一条边。
接着,我们发现,如果我们把这个图的所有强连通分量给缩成成一个点,然后对于每个点的每个维度的权值维护一个$lower$和$upper$,那么一定满足所有点的维度递增且不相交。

于是我们用一个std::set维护所有的点,对于每次加入的点,考虑在$set$里找到他的lower_boundupper_bound,对于在这个区间内的所有元素一定可以全部合并成一个强连通分量。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cmax(a,b)        a = ((a) > (b) ? (a) : (b))
#define cmin(a,b)        a = ((a) < (b) ? (a) : (b))
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pii            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

const int MAXN = 5e4 + 5;
const int MAXM = 15;
const int oo = 0x3f3f3f3f;

int N, K, c[MAXM];

struct G{
    int lower[MAXM], upper[MAXM], siz;
    bool operator < (const G &o) const {
        up (i, 0, K - 1) if (upper[i] >= o.lower[i]) return 0;
        return 1;
    }
    void merge(const G &o){
        siz += o.siz;
        up (i, 0, K - 1) {
            cmin(lower[i], o.lower[i]);
            cmax(upper[i], o.upper[i]);
        }
    }
};

set<G> S;

namespace solution{
    void Solve(){
        scanf("%d%d", &N, &K);
        up (i, 1, N) {
            up (i, 0, K - 1) scanf("%d", &c[i]);    
            G cur;
            cur.siz = 1;
            up (i, 0, K - 1) cur.lower[i] = cur.upper[i] = c[i]; 
            set<G>::iterator now, le = S.lower_bound(cur), ri = S.upper_bound(cur);
            now = le;
            while (now != ri) {
                cur.merge(*now);
                now++;
            }
            if (le != ri) S.erase(le, ri);
            S.insert(cur);
            printf("%d\n", S.rbegin() -> siz);
        }
    }    
}

int main(){
    using namespace solution;
    Solve();
    return 0;
}

D. Magic Breeding

考虑暴力做法,我们对于每个点暴力维护,这个是$O(NQ)$的。然后我们发现,对于不同的维度而言,如果那些点之间的偏序关系是一样的,那么他们答案的排名也一定是相同的。但是不同的偏序关系是阶乘级别的。考虑优化。
因为我们只在乎大小关系,所以可以假定一个数$d$,对于这$k$个数,如果小于$d$,就置为$0$,否则$1$,然后这个的数量级就非常好了。对于对于每次询问,我们只要把所有的数从大到小拿出来以此看是否为$1$即可。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cmax(a,b)        a = ((a) > (b) ? (a) : (b))
#define cmin(a,b)        a = ((a) < (b) ? (a) : (b))
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pii            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

const int MAXN = 1e5 + 5;
const int oo = 0x3f3f3f3f;

int N, K, Q, a[15][MAXN], num[15], cnt = 0;
bool S[MAXN][bin(12)];

namespace solution{
    inline int get(int x, int y){return (x >> y) & 1;}
    void Prepare(){
        scanf("%d%d%d", &N, &K, &Q);
        up (i, 0, K - 1) up (j, 0, N - 1) scanf("%d", &a[i][j]);
        up (i, 0, K - 1) up (j, 0, bin(K) - 1) S[i][j] = get(j, i);
        cnt = K;
    }
    void Solve(){
        up (i, K, K + Q - 1) {
            int o, x, y;
            scanf("%d%d%d", &o, &x, &y);
            x--; y--;
            if (o <= 2) {
                up (s, 0, bin(K) - 1) {
                    if (o == 1) S[cnt][s] = S[x][s] | S[y][s];
                    else         S[cnt][s] = S[x][s] & S[y][s];
                }
                cnt++;
            }else {
                up (j, 0, K - 1) num[j] = a[j][y];
                sort(num, num + K);
                int ss = 0;
                down (j, K - 1, 0) {
                    up (k, 0, K - 1) if (a[k][y] >= num[j]) ss |= bin(k);
                    if (S[x][ss]) {
                        printf("%d\n", num[j]);
                        break;
                    }
                }
            }
        }    
    }
}

int main(){
    using namespace solution;
    Prepare();
    Solve();
    return 0;
}