Wannafly挑战赛14

A.直角三棱锥

枚举推式子

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL gcd(LL a, LL b){
    return a % b ? gcd(b, a % b) : b;
}
int main(){
    int T;
    scanf("%d", &T);
    while(T--) {
        LL K, M, six = 6;
        cin >> K >> M;
        LL a = K + 1, b = K + 2, c = K + 3;
        LL g = gcd(a, six);
        a /= g, six /= g;
        g = gcd(b, six);
        b /= g, six /= g;
        g = gcd(c, six);
        c /= g, six /= g;
        LL ans = a * b % M * c % M;
        cout << ans << endl;
    }
    return 0;
}

B.前缀查询

子树修改子树询问转路径标记

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
typedef long long LL;
 
int node;
LL val[maxn], num[maxn], del[maxn];
LL sum[maxn], tot[maxn];
map<char, int> G[maxn];
void insert(string s, LL v){
    int p = 0;
    for(int i = 0; i < s.length(); ++i){
        if(G[p].find(s[i]) == G[p].end()) G[p][s[i]] = ++node;
        p = G[p][s[i]];
        v -= del[p];
        sum[p] += v;
        tot[p]++;
    }
    val[p] += v;
    num[p]++;
}
void modify(string s, LL v) {
    int p = 0;
    for (int i = 0; i < s.length(); ++i) {
        if (G[p].find(s[i]) == G[p].end()) G[p][s[i]] = ++node;
        p = G[p][s[i]];
    }
    del[p] += v;
    LL tmp = tot[p];
    p = 0;
    for (int i = 0; i < s.length(); ++i) {
        if (G[p].find(s[i]) == G[p].end()) G[p][s[i]] = ++node;
        p = G[p][s[i]];
        if(i != s.length() - 1) sum[p] += tmp * v;
    }
}
LL Q1(string s) {
    int p = 0;
    LL tmp = 0;
    for (int i = 0; i < s.length(); ++i) {
        if (G[p].find(s[i]) == G[p].end()) G[p][s[i]] = ++node;
        p = G[p][s[i]];
        tmp += del[p];
    }
    return val[p] + tmp * num[p];
}
LL Q2(string s) {
    int p = 0;
    LL tmp = 0;
    for (int i = 0; i < s.length(); ++i) {
        if (G[p].find(s[i]) == G[p].end()) G[p][s[i]] = ++node;
        p = G[p][s[i]];
        tmp += del[p];
    }
    return sum[p] + tmp * tot[p];
}
 
char s[maxn];
int main(){
    int N;
    scanf("%d", &N);
    for(int i = 1; i <= N; ++i){
        int o, a, b;
        scanf("%d", &o);
        if(o == 1){
            scanf("%s %d", s, &a);
            insert(string(s), a);
        }
        else if(o == 2){
            scanf("%s %d", s, &a);
            modify(string(s), a);
        }
        else if(o == 3){
            scanf("%s", s);
            printf("%lld\n", Q1(string(s)));
        }
        else{
            scanf("%s", s);
            printf("%lld\n", Q2(string(s)));
        }
    }
    return 0;
}

C.可达性

缩点

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;

// BCC
set<int> SE[maxn], ans;
set<int> :: iterator it;
stack<int> S;
vector<int> G[maxn];
int dfs_clock, dfn[maxn], low[maxn];
int bcc_cnt, bccno[maxn];
void dfs(int u, int fa)
{
    dfn[u] = low[u] = ++dfs_clock;
    S.push(u);
    for(int i = 0; i < G[u].size(); ++i)
    {
        int v = G[u][i];
        if(!dfn[v])
        {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
        }
        else if(!bccno[v]) low[u] = min(low[u], dfn[v]);
    }

    if(low[u] == dfn[u])
    {
        bcc_cnt++;
        while(1)
        {
            int x = S.top(); S.pop();
            bccno[x] = bcc_cnt;
            SE[bcc_cnt].insert(x);
            if(x == u) break;
        }
    }
}

void find_bcc(int n)
{
    memset(dfn, 0, sizeof(dfn));
    memset(bccno, 0, sizeof(bccno));
    dfs_clock = bcc_cnt = 0;
    for(int i = 1; i <= n; i++) if(!dfn[i]) dfs(i, 0);
}

int deg[maxn];
int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; ++i){
        int u, v;
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
    }
    find_bcc(n);
    for(int i = 1; i <= n; ++i){
        for(int j = 0; j < G[i].size(); ++j)
            if(bccno[i] != bccno[G[i][j]]) deg[bccno[G[i][j]]]++;
    }
    for(int i = 1; i <= bcc_cnt; ++i){
        if(deg[i] == 0) ans.insert(*SE[i].begin());
    }
    printf("%d\n", ans.size());
    for(it = ans.begin(); it != ans.end(); it++){
        if(it != ans.begin()) putchar(' ');
        printf("%d", *it);
    }
    puts("");
    return 0;
}

D.codeJan和树

启发式合并

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long LL;
typedef pair<int, int> pii;
vector<pii> G[maxn];
int n, m;

int sz[maxn];
LL bt[maxn];
void dfs(int x, int f){
    bt[x] = 0;
    sz[x] = 1;
    for(int i = 0; i < G[x].size(); ++i){
        int to = G[x][i].first, d = G[x][i].second;
        if(to == f) continue;
        dfs(to, x);
        bt[x] += bt[to] + d * sz[to];
        sz[x] += sz[to];
    }
}

LL ans;
int id[maxn];
map<LL, int> S[maxn];
map<LL, int> :: iterator it;
void add(int x, int f, int y){
    S[y][bt[x]] = 1;
    for(int i = 0; i < G[x].size(); ++i){
        int to = G[x][i].first;
        if(to == f) continue;
        add(to, x, y);
    }
}
void dfs1(int x, int f){
    id[x] = x;
    int M = 0, ms = 0;
    for(int i = 0; i < G[x].size(); ++i){
        int to = G[x][i].first;
        if(to == f) continue;
        dfs1(to, x);
        if(sz[to] > M) M = sz[to], ms = to;
    }
    if(ms) id[x] = id[ms];
    for(int i = 0; i < G[x].size(); ++i){
        int to = G[x][i].first;
        if(to == f || to == ms) continue;
        add(to, x, id[x]);
    }
    it = S[id[x]].lower_bound(bt[x] - m);
    if(it != S[id[x]].end()) ans = max(ans, bt[x] - (*it).first);
    S[id[x]][bt[x]] = 1;
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; ++i) G[i].clear(), S[i].clear();
        for(int i = 1; i < n; ++i){
            int u, v, d;
            scanf("%d %d %d", &u, &v, &d);
            G[u].push_back(pii(v, d));
            G[v].push_back(pii(u, d));
        }
        ans = -1;
        dfs(1, 0);
        dfs1(1, 0);
        printf("%lld\n", ans);
    }
    return 0;
}

E.无效位置

倒着并茶几

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn], b[maxn], ans[maxn];
int base[maxn][33], vis[maxn];

int fa[maxn];
int Find(int x){
    return fa[x] == x ? x : fa[x] = Find(fa[x]);
}
void Union(int x, int y){
    x = Find(x), y = Find(y);
    if(x == y) return;
    for(int i = 29; i >= 0; i--){
        if(!base[x][i]) continue;
        for(int j = 29; j >= 0; j--){
            if((1 << j) & base[x][i]){
                if(base[y][j]) base[x][i] ^= base[y][j];
                else {
                    base[y][j] = base[x][i];
                    break;
                }
            }
        }
    }
    fa[x] = y;
}

int main(){
    int N, M = 0;
    scanf("%d", &N);
    for(int i = 1; i <= N; ++i) fa[i] = i;
    for(int i = 1; i <= N; ++i) scanf("%d", a + i);
    for(int i = 1; i <= N; ++i) scanf("%d", b + i);
    for(int i = N; i >= 1; --i){
        int x = a[b[i]], y = 0;
        for(int j = 29; j >= 0; --j){
            if((1 << j) & x){
                base[b[i]][j] = x;
                break;
            }
        }
        vis[b[i]] = 1;
        if(vis[b[i] - 1]) Union(b[i] - 1, b[i]);
        if(vis[b[i] + 1]) Union(b[i] + 1, b[i]);
        x = Find(b[i]);
        for(int j = 29; j >= 0; --j){
            if((1 << j) & y) continue;
            y ^= base[x][j];
        }
        M = max(M, y);
        ans[i] = M;
    }
    for(int i = 1; i <= N; ++i) printf("%d\n", ans[i]);
    return 0;
}

F.细胞