HackerRank University Codesprint 3

Bob’s Game

Problem

一个二维棋盘,棋盘上有国王,障碍,以及空格子。两个人轮流操作,每次每个人可以把一个国王移动到,左/上/左上,障碍格子不能有国王。不能操作者败,问是否有必胜策略,如果有,输出第一步有多少种操作方式。

Solution

因为国王与国王之间互相不影响,所以单独的国王可以看做这个棋盘游戏的子游戏,我们很好求出单个国王的$sg$函数,即$sg(i,j) = mex{ sg(i - 1, j), sg(i - 1, j - 1),sg(i, j - 1)}$
然后我们把所有国王的格子异或起来即可。

Code

#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 = max (a, b)
#define cmin(a,b)        a = min (a, b)

const int MAXN = 1005;
const int oo = 0x3f3f3f3f;

int N, M, Q, f[MAXN][MAXN];
bool ok[5];
char s[MAXN][MAXN];

namespace solution{
    void Prepare(){
        scanf("%d%d", &N, &M);
        up (i, 1, N) scanf("%s", s[i] + 1);
    }
    void Solve(){
        int ans = 0, cnt = 0;
        up (i, 1, N) up (j, 1, N) if (s[i][j] != 'X'){
            ok[0] = ok[1] = ok[2] = ok [3] = 1;
            if (i - 1 >= 1 && s[i - 1][j] != 'X') ok[f[i - 1][j]] = 0;
            if (j - 1 >= 1 && s[i][j - 1] != 'X') ok[f[i][j - 1]] = 0;
            if (i - 1 >= 1 && j - 1 >= 1 && s[i - 1][j - 1] != 'X') ok[f[i - 1][j - 1]] = 0;
            up (k, 0, 3) if (ok[k]) {
                f[i][j] = k;
                break;
            }
        }
        up (i, 1, N) up (j, 1, N) if (s[i][j] == 'K') ans ^= f[i][j];
        if (!ans) puts("LOSE");
        else {
            up (i, 1, N) up (j, 1, N) if (s[i][j] == 'K') {
                ans ^= f[i][j];
                if (i - 1 >= 1 && s[i - 1][j] != 'X') cnt += (f[i - 1][j] == ans);
                if (j - 1 >= 1 && s[i][j - 1] != 'X') cnt += (f[i][j - 1] == ans);
                if (i - 1 >= 1 && j - 1 >= 1 && s[i - 1][j - 1] != 'X') cnt += (f[i - 1][j - 1] == ans);
                ans ^= f[i][j];
            }
            printf("WIN %d\n", cnt);
        }
    }
}

int main(){
    using namespace solution;
    scanf("%d", &Q);
    while (Q--) {
        Prepare();
        Solve();
    }
    return 0;
}

Black White Tree

Problem

给定一棵树,每个节点为黑色或白色, 要求选出这个树的一个联通子图,满足不用颜色的节点数最多。

Solution

很基础的树 DP,不再多说。

Code

#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 = max (a, b)
#define cmin(a,b)        a = min (a, b)
#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, c[MAXN], f[MAXN], g[MAXN], ans = 0, root, S[MAXN], cnt = 0, tag;

namespace Graph{
    struct edge {
        int y, next;
    }e[MAXN << 1];
    int LINK[MAXN], len = 0;
    inline void ins(int x, int y){
        e[++len].next = LINK[x]; LINK[x] = len;
        e[len].y = y;
    }
    inline void Ins(int x, int y){
        ins(x, y);
        ins(y, x);
    }
    void DP(int node, int fa){
        cmax (f[node], c[node]);
        cmin (g[node], c[node]);
        int mx = c[node], mn = c[node];
        Auto (i, node) if (e[i].y != fa) {
            DP(e[i].y, node);
            mx += f[e[i].y];
            mn += g[e[i].y];
        }
        cmax (f[node], mx);
        cmin (g[node], mn);
    }
    void reDP(int node, int fa, int Mx, int Mn){
        int mx = c[node], mn = c[node];
        Auto (i, node) if (e[i].y != fa) {
            mx += f[e[i].y];
            mn += g[e[i].y];
        }
        if (Mx + mx > ans) {
            ans = Mx + mx;
            root = node;
            tag = 1;
        }
        if (-(Mn + mn) > ans) {
            ans = -(Mn + mn);
            root = node;
            tag = -1;
        }
        Auto (i, node) if (e[i].y != fa) 
            reDP(e[i].y, node, max (Mx + mx - f[e[i].y], 0), min(Mn + mn - g[e[i].y], 0));
    }
    void DFS(int node, int fa){
        if (f[node] == 0 && tag == 1)     return;
        if (g[node] == 0 && tag == -1)     return;
        S[++cnt] = node;
        Auto (i, node) if (e[i].y != fa) DFS(e[i].y, node);
    }
}using namespace Graph;

namespace solution{
    void Prepare(){
        scanf("%d", &N);
        up (i, 1, N) scanf("%d", &c[i]);
        up (i, 1, N) c[i] = (c[i] == 0 ? -1 : 1);
        up (i, 2, N) {
            int x, y;
            scanf("%d%d", &x, &y);
            Ins(x, y);
        }
    }
    void Solve(){
        DP(1, 0);
        reDP(1, 0, 0, 0);
        printf("%d\n", ans);
        up (i, 1, N) f[i] = g[i] = 0;
        DP(root, 0);
        DFS(root, 0);
        sort (S + 1, S + cnt + 1);
        printf("%d\n", cnt);
        up (i, 1, cnt) printf("%d ", S[i]);
        puts("");
    }
}

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

March of the King

Problem

给定一个$8\times 8$棋盘,每个格子上有一个字母,给定一个单词,询问有多少个不相交的八连通路径,满足其路径所拼接起来的单词是给定的单词。

Solution

首先我们不考虑相交的限制,很明显我们可以把这个词从中间断开,对每个点,对这两半分别爆搜,然后乘法原理一下即可。
有了相交的限制。直接容斥,考虑到棋盘大小非常小。可以直接用一个unsigned long long把所有的状态表示出来,然后用unorderded_map存起来。每次当爆搜到终点时,就可以枚举当前状态的子集。直接容斥就行了。

Code

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define ull            unsigned 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 = max (a, b)
#define cmin(a,b)        a = min (a, b)
#define bin(i)        (1ULL << (i))

const int MAXN = 15;
const int oo = 0x3f3f3f3f;
const int dx[] = {0, 0, 1, 1, 1, -1, -1, -1};
const int dy[] = {1, -1, 1, 0, -1, 1, 0, -1};

int N, L, ID[MAXN][MAXN], cnt = 0;
char a[MAXN], b[MAXN], s[MAXN][MAXN];
unordered_map<ull, int> mark; 
ll ans = 0;

namespace solution{
    bool vaild(int x, int y, int o){return x + dx[o] >= 1 && x + dx[o] <= 8 && y + dy[o] >= 1 && y + dy[o] <= 8;}
    void DFS(int x, int y, int cur, int ed, char *t, ull S, ull ss){
        if (S & bin(ID[x][y]))     return;
        if (t[cur] != s[x][y])    return;
        S |= bin(ID[x][y]);
        if (cur == ed) {
            S ^= ss;
            for (ull s = S; s; s = (s - 1) & S) mark[s]++;
            mark[0]++;
            return;
        }
        up (i, 0, 7) if (vaild(x, y, i))
            DFS(x + dx[i], y + dy[i], cur + 1, ed, t, S, ss);
    }
    void reDFS(int x, int y, int cur, int ed, char *t, ull S, ull ss){
        if (S & bin(ID[x][y]))    return;
        if (t[cur] != s[x][y])  return;
        S |= bin(ID[x][y]);
        if (cur == ed) {
            S ^= ss;
            ans += mark[0];
            for (ull s = S; s; s = (s - 1) & S) {
                ll f = 1;
                up (i, 0, 63) if (bin(i) & s) f *= -1;
                ans += f * mark[s];
            }
            return;
        }
        up (i, 0, 7) if (vaild(x, y, i))
            reDFS(x + dx[i], y + dy[i], cur + 1, ed, t, S, ss);
    }
    void Prepare(){
        scanf("%d%s", &N, a + 1);
        up (i, 1, 8) scanf("%s", s[i] + 1);
        L = (N + 1) >> 1;
        up (i, 1, N - L + 1) b[i] = a[L + i - 1];
        reverse(a + 1, a + L + 1);
        up (i, 1, 8) up (j, 1, 8) ID[i][j] = cnt++;
    }
    void Solve(){
        up (i, 1, 8) up (j, 1, 8) {
            mark.erase(mark.begin(), mark.end());
            DFS(i, j, 1, L, a, 0, bin(ID[i][j]));
            reDFS(i, j, 1, N - L + 1, b, 0, bin(ID[i][j]));
        }     
        printf("%lld\n", ans);
    }
}

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

Simple Tree Counting

Problem

给定一棵树,树上每条边都有一个颜色。如果一个极大联通子图满足所有相邻的点所形成的边颜色相同,并且这个子图有$n$个点,那么他的贡献就是$\frac{n \times(n - 1)}{2}$。要求维护以下几个操作。

  • 更改边的颜色。
  • 询问某条边所属联通块的贡献。
  • 询问颜色在$[L,R]$内的联通块的贡献和。

Solution

LCT + BIT裸题

Code

#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 = max (a, b)
#define cmin(a,b)        a = min (a, b)
#define pii            pair<int, int>
#define fi            first
#define se            second
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

const int MAXN = 2e5 + 5;
const int MAXM = 1e6 + 5;
const int LIM = 1e6;
const int oo = 0x3f3f3f3f;

ll cal(int x){return 1LL * x * (x - 1) / 2;}

int N, Q, cnt = 0;
struct Edges{
    int x, y, v;
}eds[MAXN];

map<pii, int> ID;

namespace LCT{
    struct tree {
        int son[2], siz, fa, sz;
        bool tag;
    }t[MAXM << 4];
    int sta[MAXN];
    inline bool get(int k){
        return k == t[t[k].fa].son[1];
    }
    inline bool isrt(int k){
        if (!k) return 1;
        return k != t[t[k].fa].son[0] && k != t[t[k].fa].son[1];
    }
    inline void rel(int k){
        if (!k) return;
        int s0 = t[k].son[0], s1 = t[k].son[1];
        t[k].siz = t[k].sz;
        if (s0) t[k].siz += t[s0].siz;
        if (s1) t[k].siz += t[s1].siz;
    }
    void rev(int k){
        if (!k) return;
        swap(t[k].son[0], t[k].son[1]);
        t[k].tag ^= 1;
    }
    void Pushdown(int k){
        if (!k || !t[k].tag) return;
        int s0 = t[k].son[0], s1 = t[k].son[1];
        rev(s0); rev(s1);
        t[k].tag ^= 1;
    }
    void rotate(int k){
        int fa = t[k].fa, ffa = t[fa].fa, w = get(k);
        t[fa].son[w] = t[k].son[w ^ 1]; t[t[fa].son[w]].fa = fa;
        if (!isrt(fa)) t[ffa].son[fa == t[ffa].son[1]] = k;
        t[k].son[w ^ 1] = fa; t[fa].fa = k;
        t[k].fa = ffa;
        rel(fa); rel(k);
    }
    void splay(int k){
        int top = 0;
        sta[++top] = k;
        for (int node = k; !isrt(node); node = t[node].fa) sta[++top] = t[node].fa;
        while (top) Pushdown(sta[top--]);
        while (!isrt(k)) {
            int fa = t[k].fa;
            if (!isrt(fa)) rotate(get(fa) == get(k) ? fa : k);
            rotate(k);
        }
    }
    void access(int k){
        int tmp = 0;
        while (k) {
            splay(k);
            int s1 = t[k].son[1];
            if (s1) t[k].sz += t[s1].siz;
            t[k].son[1] = tmp;
            if (tmp) t[k].sz -= t[tmp].siz;
            tmp = k;
            rel(k); 
            k = t[k].fa;
        }
    }
    void mkrt(int k){
        access(k);
        splay(k);
        rev(k);
    }
    int getsiz(int k){
        access(k);
        splay(k);
        return t[k].siz;
    }
    void Link(int x, int y){
        mkrt(x);
        access(x);
        splay(x);
        t[x].fa = y;
        t[y].sz += t[x].siz;
        rel(y);
    }
    void Cut(int x, int y){
        mkrt(x);
        access(y);
        splay(y);
        t[y].son[0] = 0;
        t[x].fa = 0;
        rel(y);
    }
}using namespace LCT;

namespace BIT{
    ll c[MAXM];
    inline int lowbit(int i){return i & (-i);}
    inline void upd(int o, ll v){
        for (int i = o; i <= LIM; i += lowbit(i))
            c[i] += v;
    }
    inline ll calc(int o){
        ll sum = 0;
        for (int i = o; i >= 1; i -= lowbit(i))
            sum += c[i];
        return sum;
    }
}using namespace BIT;

int O(int o, int k){
    if (!ID[make_pair(o, k)]) {
        ID[make_pair(o, k)] = ++cnt;
        t[cnt].siz = t[cnt].sz = 1;
    }
    return ID[make_pair(o, k)];
}

namespace Graph{
    struct edge{
        int y, next, v;
    }e[MAXN << 1];
    int LINK[MAXN], len = 0;
    inline void ins(int x, int y, int v){
        e[++len].next = LINK[x]; LINK[x] = len;
        e[len].y = y; e[len].v = v;
    }
    inline void Ins(int x, int y, int v){
        ins(x, y, v);
        ins(y, x, v);
    }
    void DFS(int node, int fa){
        Auto (i, node) if (e[i].y != fa) {
            DFS(e[i].y, node);
            int x = O(e[i].v, node), y = O(e[i].v, e[i].y);
            upd(e[i].v, -cal(getsiz(x)));
            upd(e[i].v, -cal(getsiz(y)));
            Link(x, y);
            upd(e[i].v, cal(getsiz(x)));
        }    
    }
}using namespace Graph;

namespace solution{
    void Prepare(){
        scanf("%d", &N);
        up (i, 1, N - 1) {
            int x, y, v;
            scanf("%d%d%d", &x, &y, &v);
            Ins(x, y, v);
            eds[i] = (Edges){x, y, v};
        }
        DFS(1, 0);
    }    
    void Solve(){
        scanf("%d", &Q);
        while (Q--) {
            int op;
            scanf("%d", &op);
            if (op == 1) {
                int o, v;
                scanf("%d%d", &o, &v);
                int x = eds[o].x, y = eds[o].y, c = eds[o].v;
                if (c == v) continue;
                upd(c, -cal(getsiz(O(c, x))));
                upd(v, -cal(getsiz(O(v, x))));
                upd(v, -cal(getsiz(O(v, y))));
                Cut(O(c, x), O(c, y));
                upd(c, cal(getsiz(O(c, x))));
                upd(c, cal(getsiz(O(c, y))));
                eds[o].v = v;
                Link(O(v, x), O(v, y));
                upd(v, cal(getsiz(O(v, x))));
            }
            if (op == 2) {
                int le, ri;
                scanf("%d%d", &le, &ri);
                printf("%lld\n", calc(ri) - calc(le - 1));
            }
            if (op == 3) {
                int o;
                scanf("%d", &o);
                int x = eds[o].x, c = eds[o].v; 
                printf("%lld\n", cal(getsiz(O(c, x))));
            }
        }
    }
}

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