2022-10-16总结

最美森林

随便挑一个节点当根，那么所有的叶子节点的状态是已经确定的，然后又能确定倒数第二层的状态，也就是说，如果有解的话解唯一，所以我们就把每个连通块 dfs 一遍，如果一条边下面连的子树有奇数个黑点，那么这条边就一定选，否则一定不选，最后判一下选出来的方案合不合法即可。

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("painting.in", "r", stdin);
        freopen("painting.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;

const int N = 1e5+10;

struct edge {
    int to, id;
};

int n, m;
int siz[N];
char col[N];
bool vis[N];
int x[N], y[N];
vector<int> ans;
vector<edge> ver[N];

void dfs(int x);
bool check();

int main()
{
    cin >> n >> m;
    cin >> (col+1);
    for(int i = 1; i <= m; i++)
    {
        cin >> x[i] >> y[i];
        ver[x[i]].push_back({y[i], i});
        ver[y[i]].push_back({x[i], i});
    }
    for(int i = 1; i <= n; i++)
        if(!vis[i]) dfs(i);
    if(!check())
        cout << "-1";
    else
    {
        sort(ans.begin(), ans.end());
        cout << ans.size() << '\n';
        for(auto i : ans) cout << i << " ";
    }
}
void dfs(int x)
{
    vis[x] = true;
    siz[x] = (col[x]=='B');
    for(auto i : ver[x])
    {
        if(vis[i.to]) continue;
        dfs(i.to); siz[x] += siz[i.to];
        if(siz[i.to]&1) ans.push_back(i.id);
    }
}

int deg[N];
bool check()
{
    for(auto i : ans)
        deg[x[i]]++, deg[y[i]]++;
    for(int i = 1; i <= n; i++)
    {
        if(col[i] == 'W' and deg[i]%2 != 0) return false;
        if(col[i] == 'B' and deg[i]%2 != 1) return false;
    }
    return true;
}

葡萄庄园

考虑对删掉某种颜色后的联通块统计答案，因为能换颜色，所以就相当于走两个不同颜色的相邻连通块，但是答案不能直接加，需要减去重合部分，设一个连通块不走 $1$ ，另一个连通块不走 $2$ ，那么重合的部分就是只走 $3$ 且两个连通块都包含的部分，这个也可以枚举每个点处理。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("grape.in", "r", stdin);
        freopen("grape.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;

typedef long long ll;
const int N = 1e5+10;

struct edge {
    int to, col;
};

int n, m, cnt;
bool vis[N];
ll ans[N];
ll a[N], sum[N];
int belong[4][N];
vector<edge> ver[N];
map<pair<int,int>, ll> mp;

void bfs1(int s, int col);
void bfs2(int s, int col);

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        ver[x].push_back({y, z});
        ver[y].push_back({x, z});
    }
    
    for(int c = 1; c <= 3; c++)
    {
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= n; i++)
            if(!vis[i]) bfs1(i, c);
    }
    
    for(int c = 1; c <= 3; c++)
    {
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= n; i++)
            if(!vis[i]) bfs2(i, c);
    }
    
    for(int i = 1; i <= n; i++)
    {
        int x = belong[1][i], y = belong[2][i], z = belong[3][i];
        ans[x] = max(ans[x], sum[x] + max(sum[y]-mp[{x,y}], sum[z]-mp[{x,z}]));
        ans[y] = max(ans[y], sum[y] + max(sum[x]-mp[{x,y}], sum[z]-mp[{y,z}]));
        ans[z] = max(ans[z], sum[z] + max(sum[x]-mp[{x,z}], sum[y]-mp[{y,z}]));
    }
    
    int q, k; cin >> q;
    while(q --> 0)
    {
        cin >> k;
        cout << max({ ans[belong[1][k]], ans[belong[2][k]], ans[belong[3][k]] }) << "\n";    }
}

void bfs1(int s, int col)
{
    cnt++;
    queue<int> q;
    q.push(s), vis[s] = true;
    while(q.size())
    {
        int x = q.front(); q.pop();
        sum[cnt] += a[x];
        belong[col][x] = cnt;
        for(auto i : ver[x])
            if(!vis[i.to] and i.col != col)
                q.push(i.to), vis[i.to] = true;
    }
}

void bfs2(int s, int col)
{
    queue<int> q;
    q.push(s), vis[s] = true;
    ll sum = 0;
    while(q.size())
    {
        int x = q.front(); q.pop();
        sum += a[x];
        for(auto i : ver[x])
            if(!vis[i.to] and i.col == col)
                q.push(i.to), vis[i.to] = true;
    }
    
    int x = belong[1][s], y = belong[2][s], z = belong[3][s];
    if(col == 1) mp[{y,z}] += sum;
    if(col == 2) mp[{x,z}] += sum;
    if(col == 3) mp[{x,y}] += sum;
}

树边计数

考虑每条边的贡献，设这条边所连的深度较大的点是 $x$，我们把 $x$ 子树内的点都标记为 $1$，子树外的点都标记为 $0$, 那么这条边的贡献就是所有既包含 $0$ 又包含 $1$ 的区间，可以容斥一下，用总区间数减去只有 $0$ 和只有 $1$ 的区间，这个线段树维护前后缀 $0,1$ 的个数即可，然后再写个线段树合并就可以过了。

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("count.in", "r", stdin);
        freopen("count.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;


typedef long long ll;
const int N = 1e5+10;

namespace tr {
    int ls[N*32], rs[N*32];
    struct node {
        int len; ll sum;
        int pre[2], suf[2];
        node();
        node(int l);
    } a[N*32];
    int root[N], lim, node_cnt;
    void insert(int &i, int pos, int l = 1, int r = lim);
    void merge(int &x, int &y, int l = 1, int r = lim);
}
using namespace tr;

int n; ll ans;
vector<int> ver[N];

void dfs(int x, int fa);

int main()
{
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        int x, y; cin >> x >> y;
        ver[x].push_back(y);
        ver[y].push_back(x);
    }
    
    tr::lim = n;
    dfs(1, 0);
    
    cout << ans << "\n";
}

void dfs(int x, int fa)
{
    for(auto y : ver[x])
    {
        if(y == fa) continue;
        dfs(y, x);
        ans += tr::a[root[y]].sum;
        tr::merge(root[x], root[y]);
    }
    tr::insert(root[x], x);
}

namespace tr {
    #define lmid ((l+r)>>1)
    #define rmid ((l+r+2)>>1)
    node::node(){}
    node::node(int l)
    {
        len = pre[0] = suf[0] = l;
        sum = pre[1] = suf[1] = 0;
    }
    node operator + (node a, node b)
    {
        node ans;
        ans.len = a.len + b.len;
        ans.sum = a.sum + b.sum;
        for(int i = 0; i < 2; i++)
        {
            ans.pre[i] = a.pre[i];
            if(a.pre[i] == a.len) ans.pre[i] += b.pre[i];
            ans.suf[i] = b.suf[i];
            if(b.suf[i] == b.len) ans.suf[i] += a.suf[i];
        }
        int l = max(a.suf[0], a.suf[1]), ltp = (l==a.suf[1]);
        int r = max(b.pre[0], b.pre[1]), rtp = (r==b.pre[1]);
        
        ans.sum += (ll)a.len*b.len;
        if(ltp == rtp) ans.sum -= (ll)l*r;
        return ans;
    }
    
    void pushup(int i, int l, int r)
    {
        if(!ls[i] and !rs[i])
            a[i] = node(lmid-l+1) + node(r-rmid+1);
        else if(!ls[i])
            a[i] = node(lmid-l+1) + a[rs[i]];
        else if(!rs[i])
            a[i] = a[ls[i]] + node(r-rmid+1);
        else
            a[i] = a[ls[i]] + a[rs[i]];
    }
    
    
    void insert(int &i, int pos, int l, int r)
    {
        if(!i) i = ++node_cnt;
        if(l == r)
        {
            a[i].len = 1;
            a[i].pre[0] = a[i].suf[0] = 0;
            a[i].pre[1] = a[i].suf[1] = 1;
            return void();
        }
        if(pos <= lmid) insert(ls[i], pos, l, lmid);
        if(pos >= rmid) insert(rs[i], pos, rmid, r);
        pushup(i, l, r);
    }
    void merge(int &x, int &y, int l, int r)
    {
        if(!x or !y) return void(x |= y);
        if(l == r)
        {
            a[x].pre[1] |= a[y].pre[1];
            a[x].suf[1] |= a[y].suf[1];
            a[x].pre[0] &= a[y].pre[0];
            a[x].suf[0] &= a[y].suf[0];
            return void();
        }
        merge(ls[x], ls[y], l, lmid);
        merge(rs[x], rs[y], rmid, r);
        pushup(x, l, r);
    }
}

赌神洗牌

$\operatorname{shuffle}(S)$ 操作本质上是个置换，而置换可以拆成若干个简单环，答案上界就是 $\operatorname{lcm}(环的大小)$，而每个环的大小都是 $\varphi(n-1)$ 的约数。

每个操作相当于原来为 $i$ 位置的数转移到了 $2i \bmod (n-1)$ 的位置(下标从 $0$ 开始), 我们把每个环单独考虑，那么一次置换只看某个环的话就相当于把这个环循环左移，我们可以算出来循环串的最小循环节，然后算出这个环需要左移几次才能变成 $T$，最后可以用 set 或者解同余方程的方式算出最终答案。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <vector>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("manipulation.in", "r", stdin);
        freopen("manipulation.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;


const int N = 3e6+10;

int n;
set<int> z_z_y;
int nxt[N]; bool vis[N];
char s[N], t[N], str[N];
vector<bool> cant[N];

void get_nxt(char *s, int n);
int get_phi(int n);

int main()
{
    scanf("%s", s);
    scanf("%s", t);
    n = strlen(s);
    
    if(s[0] != t[0] or s[n-1] != t[n-1])
        return cout << "-1", 0;
    
    for(int i = 0; i < n; i++)
    {
        if(vis[i]) continue;
        vector<int> tmp;
        for(int j = i; !vis[j]; j = j*2 % (n-1))
        {
            vis[j] = true;
            tmp.push_back(j);
        }
        
        int m = 0, len = tmp.size();
        for(auto i : tmp) str[m++] = t[i];
        str[m++] = '#';
        for(auto i : tmp) str[m++] = s[i];
        for(auto i : tmp) str[m++] = s[i];
        str[m] = 0;
        
        get_nxt(str, m);
        
        if(cant[len].empty())
            cant[len].resize(len, false);
        for(int i = 0; i < tmp.size(); i++)
        {
            if(nxt[i+len*2] != len-1)
            {
                cant[len][i] = true;
                if(!z_z_y.count(len)) z_z_y.insert(len);
            }
        }
    }
    
    int phi = get_phi(n-1);
    
    for(int i = 0; i < phi; i++)
    {
        bool flag = true;
        for(auto v : z_z_y)
            if(cant[v][i%v])
                { flag = false; break; }
        if(flag) return cout << i, 0;
    }
    cout << -1;
}
void get_nxt(char *s, int n)
{
    nxt[0] = -1;
    for(int i = 1, j = -1; i < n; i++)
    {
        while(j != -1 and s[i] != s[j+1]) j = nxt[j];
        if(s[i] == s[j+1]) j++;
        nxt[i] = j;
    }
}
int get_phi(int n)
{
    int ans = 1, x = n;
    for(int i = 2; i <= n; i++)
    {
        if(x%i == 0)
        {
            ans *= i-1, x /= i;
            while(x%i == 0) x /= i, ans *= i;
        }
    }
    return ans;
}