CF339

C. Xenia and Weights
1...10 kの分銅は、天秤の上に、左右に順番に分銅を置き、その後、左右の順番が反対側の重量よりも大きく、隣接する2回の分銅が同じではないことを要求します.
解題報告は(i,j,k)はbalance,jは最後の分銅重量,kは数歩目,次いで点(0,0)->(x,y,m)からの図論問題を示し,動的計画と等価であり,複雑度はO(w^3*m)である.
上記のアルゴリズムよりも優れたアルゴリズムを与え,iステップbalanceがjに達したときの可能なすべての分銅をdp[i][j]で表すバイナリmaskであり,複雑度はO(w^2*m)であるがw<32が要求される.

#include <cstdio>

#include <vector>

#include <cstring>

#include <iostream>

using namespace std;



int dp[1005][25];

char w[15];



int main() {

    int m;

    scanf("%s%d", w, &m);



    memset(dp, 0, sizeof(dp));

    dp[0][10] = 1;



    for (int i = 1; i <= m; i++) {

        for (int j = 0; j <= 20; j++) {

            if (dp[i - 1][j] > 0) {

                for (int k = 1; k <= 10; k++) if (w[k - 1] == '1') {

                    if (dp[i - 1][j] ^ (1 << k)) {

                        if (j >= 10 && j - k < 10) {

                            dp[i][j - k] |= (1 << k);

                        } else if (j < 10 && j + k > 10) {

                            dp[i][j + k] |= (1 << k);

                        } 

                    }

                }

            }

        } 

    }



    int ans_j = -1;

    for (int j = 0; j <= 20; j++) if (dp[m][j] > 0)

        ans_j = j;



    if (ans_j == -1) {

        printf("NO
");

    } else {

        printf("YES
"); 

        int i = m;

        vector<int> ans;

        int last = 0;

        while (i > 0) {

            for (int j = 1; j <= 10; j++) {

                if (dp[i][ans_j] & (1 << j)) {

                    if (j == last) continue;



                    ans.push_back(j);

                    

                    if (ans_j >= 10) ans_j -= j;

                    else ans_j += j;



                    last = j;



                    break;

                }

            }

            i--;

        }

        for (i = ans.size() - 1; i >= 0; i--) {

            printf("%d ", ans[i]);

        }

        printf("
");

    }

}

 
D. Xenia and Bit Operations
裸の線分の木になりました.

#include <cstdio>

#include <iostream>

using namespace std;



const int MAXN = 1 << 17;



int num[MAXN];



class SegNode {

public:

    int L, R;

    int level, sum;

} node[MAXN * 4];



class SegTree {

public:

    void build(int r, int L, int R) {

        node[r].L = L;

        node[r].R = R;



        if (L == R) {

            // leaf

            node[r].level = 0;

            node[r].sum = num[L];

        } else {

            // non leaf 

            int M = (L + R) / 2;

            build(2 * r, L, M);

            build(2 * r + 1, M + 1, R);

            node[r].level = node[2 * r].level + 1;

            if (node[r].level & 1) {

                node[r].sum = node[2 * r].sum | node[2 * r + 1].sum;

            } else {

                node[r].sum = node[2 * r].sum ^ node[2 * r + 1].sum;

            }

        }

    }

    void update(int r, int p, int b) {

        if (node[r].L == node[r].R) {

            node[r].sum = b; 

        } else {

            if (p <= node[2 * r].R) {

                // left

                update(2 * r, p, b);

            } else if (p >= node[2 * r + 1].L) {

                // right 

                update(2 * r + 1, p, b);

            }

            if (node[r].level & 1) {

                node[r].sum = node[2 * r].sum | node[2 * r + 1].sum;

            } else {

                node[r].sum = node[2 * r].sum ^ node[2 * r + 1].sum;

            }

        } 

    }

} tree;



int main() {

    int n, m;

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= (1 << n); i++) {

        scanf("%d", &num[i]);

    }

    tree.build(1, 1, 1 << n);

    for (int i = 0; i < m; i++) {

        int p, b;

        scanf("%d%d", &p, &b);

        tree.update(1, p, b);

        printf("%d
", node[1].sum);

    }

}