2019银川Regional 补题

statement:https://www.jisuanke.com/contest/5527

赛中过题: B D F G H I K N

A.Girls Band Party

处理完输入后似乎就是一个简单的01背包，写的时候弱智了..

#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define empb emplace_back
#define all(x) (x).begin(),(x).end()
const int N = 100010;

int a[N][3], w[N][2];
int b[5], c;
map<string, int> id;
int tot;
string s;
int getid() {
    cin >> s;
    if(id.count(s)) return id[s];
    return id[s] = ++tot;
}

int dp[6][6][6];

int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int _; cin >> _;
    while(_--) {
        int n; cin >> n;
        id.clear(); tot = 0;
        for(int i = 0; i < n; i++) {
            a[i][0] = getid();
            a[i][1] = getid();
            cin >> a[i][2];
        }
        for(int i = 0; i < 5; i++) {
            b[i] = getid();
        }
        c = getid();
        memset(w, 0, (tot + 1) * sizeof(w[0]));
        for (int i = 0; i < n; i++) {
            int f = a[i][1] == c;
            w[a[i][0]][f] = max(w[a[i][0]][f], a[i][2]);
        }
        memset(dp, -1, sizeof dp);
        dp[0][0][0] = 0;
        for(int i = 1; i <= tot; i++) {
            if(!w[i][0] && !w[i][1]) continue;
            int x = 0;
            for(int j = 0; j < 5; j++) {
                if(i == b[j]) x = 1;
            }
            for(int j = 5; j >= 1; j--)
                for(int k = j; k >= x; k--)
                    for(int l = j; l >= 0; l--)
                        for(int y = 0; y < 2; y++) {
                            if(!w[i][y] || l < y || dp[j-1][k-x][l-y]==-1) continue;
                            dp[j][k][l] = max(dp[j][k][l], dp[j-1][k-x][l-y]+w[i][y]);
                        }
        }
        int ans = 0;
        for(int i = 0; i <= 5; i++) {
            for(int j = 0; j <= 5; j++) {
                ans = max(ans, dp[5][i][j]*(10+i+j*2)/10);
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

E.Xor tree

设 ,则.
枚举套用长链剖分，总复杂度为,其中.
计蒜客评测机非常不稳定，卡了很久才过.

#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define fi first
#define se second
#define empb emplace_back
#define all(x) (x).begin(),(x).end()
const int N = 100010;

struct node_t {
    int a[4];
    int &operator [](int i) { return a[i];}
    void init(int msk) {
        memset(a, 0, sizeof a);
        a[msk] = 1;
    }
    node_t& operator += (const node_t &rhs) {
        for(int i = 0; i < 4; i++) a[i] += rhs.a[i];
        return *this;
    }
    node_t& operator -= (const node_t &rhs) {
        for(int i = 0; i < 4; i++) a[i] -= rhs.a[i];
        return *this;
    }
};
vector<int> E[N];
int n, k;
int a[N], dep[N], son[N];
void prepare(int u) {
    for(auto &v : E[u]) {
        prepare(v);
        if(dep[son[u]] < dep[v]) son[u] = v;
    }
    dep[u] = dep[son[u]] + 1;
}
node_t pool[N], *pt = pool, *dp[N];
ull res[N];
void dfs(int u, int i, int j) {
    dp[u] = pt++;
    int msk = (a[u]>>i&1)<<1|(a[u]>>j&1);
    dp[u]->init(msk);
    if(son[u]) dfs(son[u], i, j);
    for(auto &v : E[u]) {
        if(v == son[u]) continue;
        dfs(v, i, j);
        for(int l = 0; l <= dep[v]; l++) {
            dp[u][l + 1] += dp[v][l];
        }
    }
    if(dep[u] > 0) dp[u][0] += dp[u][1];
    node_t ans = dp[u][0];
    if(dep[u] > k) ans -= dp[u][k + 1];
    res[u] += (1ull << i + j + (i != j)) * ((ll)ans[0] * ans[3] + (ll)ans[1] * ans[2]);
}
int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    dep[0] = -1;
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 2, f; i <= n; i++) {
        cin >> f;
        E[f].push_back(i);
    }
    prepare(1);
    for(int i = 0; i < 30; i++) {
        for(int j = 0; j <= i; j++) {
            pt = pool;
            dfs(1, i, j);
        }
    }
    for(int i = 1; i <= n; i++) {
        cout << res[i] << '\n';
    }
    return 0;
}