序列收益

看数据范围和取数方式知肯定是一道区间DP。

设 f(l,r)f(l,r) 为从区间 [l,r][l,r] 中任意取数的最大价值。

若 [l+1,r−1][l+1,r-1] 内的数都被取完，则可以同时取 l,rl, r 处的数。

判断 [l+1,r−1][l+1,r-1] 是否被取完只需判断满不满足 f(l,r)=∑i=lrbif(l,r)=\sum_{i=l}^r b_i。

零一种就是套路的转移: 枚举断点，将区间分成两部分，左右分别加起来就行。

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


typedef long long ll;
const int N = 805;

int n, k;
ll a[N], b[N];
ll f[N][N];
ll sum[N];

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i];
        sum[i] = sum[i-1]+b[i];
    }
    memset(f, 0, sizeof(f));
    ll ans = 0;
    for(int i = 1; i < n; i++)
        if(a[i]+a[i+1] <= k) 
        {
            f[i][i+1] = b[i]+b[i+1];
            ans = max(ans, f[i][i+1]);
        }
    for(int len = 3; len <= n; len++)
    {
        for(int l = 1, r; (r = l+len-1) <= n; l++)
        {
            if(a[l]+a[r] <= k and f[l+1][r-1] == sum[r-1]-sum[l])
                f[l][r] = max(f[l][r], b[l]+f[l+1][r-1]+b[r]);
            
            for(int m = l; m < r; m++)
                f[l][r] = max(f[l][r], f[l][m]+f[m+1][r]);
            
            ans = max(ans, f[l][r]);
        }
    }
    cout << ans << "\n";
}

极速逃生

首先看到 0≤c≤90 \le c \le 9 可知每条边只会对答案的某一位产生贡献。因为要让最终答案最小，所以先保证答案的位数尽量少，再保证答案的高位尽量小，这启示我们进行 bfs 分层。

因为前导 00 不会使答案变大，所以先从 n−1n-1 开始 bfs，只走 00 的边，这些点都可以作为终点，然后从 00 bfs 分层，处理出每个点到 00 的最小距离(贡献在答案的哪一位)，然后从高位到低位开始贪心，每次选一些当前层边权最小的点拓展(边权大的会使答案的当前位更大，后面的低位无法弥补，直接舍弃即可)，如果有多个边权最小的就先拓展到 n−1n-1 边数最少的，每次拓展一层，并记录每个点的前驱边，当到第 00 层时即找到最小方案，此时通过前驱边输出方案即可。

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

const int N = 1e5+10;
const int INF = 0x3f3f3f3f;

struct edge {
    int from, to, cost;
};

int n, m;
int minc[N];
int cnt0[N];
int st[N], pre[N], dep[N];
vector<edge> ver[N];

void solve();
void bfs1(int s);
void bfs2(int s);
void print(int x);

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        ver[a].push_back({a, b, c});
        ver[b].push_back({b, a, c});
    }
    bfs1(n-1);
    bfs2(0);
    solve();
    
    if(cnt0[0] == -1) print(0),cout<<endl;
    else cout<<0<<endl;
    cout<<dep[st[0]]+cnt0[st[0]]+1<<"\n";
}

void bfs1(int s)
{
    memset(cnt0, -1, sizeof(cnt0));
    queue<int> q; int x;
    q.push(s), cnt0[s] = 0;
    while(!q.empty())
    {
        x = q.front(); q.pop();
        for(auto i : ver[x])
        {
            if(cnt0[i.to] == -1 and i.cost == 0)
            {
                cnt0[i.to] = cnt0[x]+1;
                q.push(i.to);
            }
        }
    }
}
void bfs2(int s)
{
    memset(dep,0x3f,sizeof(dep));
    queue<int> q; int x;
    q.push(s), dep[s] = 0;
    while(!q.empty())
    {
        x = q.front(); q.pop();
        if(cnt0[x] != -1) continue;
        for(auto i : ver[x])
        {
            if(dep[i.to] == INF)
            {
                dep[i.to] = dep[x]+1;
                q.push(i.to);
            }
        }
    }
}

bool vis[N];
void solve()
{
    memset(minc, 0x3f, sizeof(minc));
    vector<int> q; int x, nowd = INF;
    for(int i = 0; i <= n-1; i++)
    {
        if(cnt0[i] == -1)
            continue;
        if(dep[i] < nowd)
            q.clear(), nowd = dep[i];
        if(dep[i] == nowd)
        {
            q.push_back(i);
            st[i] = i;
        }
    }
    for(; nowd != 0; nowd--)
    {
        vector<int> tmp;
        sort(q.begin(), q.end(), [&](int a, int b){
            return cnt0[st[a]] < cnt0[st[b]];
        });
        while(!q.empty())
        {
            int x = q.back(); q.pop_back();
            if(vis[x]) continue;
            vis[x] = true;
            for(auto i : ver[x])
            {
                if(dep[i.to] >= nowd) continue;
                if(i.cost < minc[nowd-1])
                    tmp.clear(), minc[nowd-1] = i.cost;
                if(i.cost == minc[nowd-1])
                {
                    tmp.push_back(i.to);
                    pre[i.to] = x;
                    st[i.to] = st[x];
                }
            }
        }
        q = tmp;
    }
}

void print(int x)
{
    if(cnt0[x] != -1) return void();
    print(pre[x]);
    cout << minc[dep[x]];
}

异或操作

我们定义一个点的点权是它连出去的边的异或和。

这样定义可以使一条路径整体异或变为只有两个点异或。

现在我们需要做的就是每次同时给两个数异或一个相同的值，问最少几次能将他们全变成 00。

首先我们发现所有点权的总异或和为 00, 所以答案显然有一个上界: n−1n-1，

如果我们能把所有的点划分成 cc 个点权异或和为 00 的集合，那么答案的上界就变成了 n−cn-c。

想一下可以知道最小答案即为划分出最大的 cc。

首先我们可以把相等的值两两匹配，最终会剩下最多 2162^{16} 种数，我们可以进行一个状压 DP 的做，枚举子集来得到状态为 SS 时最多可以分出多少点权异或和为 00 的集合。

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

const int N = 1e5+10;
const int A = 16;

int n;
int f[N];
bool is[N];
int a[N], t[A];


int main(void)
{
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        a[x] ^= z, a[y] ^= z;
    }
    for(int i = 1; i <= n; i++)
        t[a[i]]++;
    for(int s = 0; s < (1<<A); s++)
    {
        int tmp = 0;
        for(int i = 0; i < A; i++)
            if((s>>i)&1) tmp ^= i;
        if(!tmp) is[s] = true;
    }
    for(int s = 0; s < (1<<A); s++)
        for(int t = s; t; t = (t-1)&s)
            if(is[t]) f[s] = max(f[s], f[s^t]+1);
    int ans = t[0], s = 0;
    for(int i = 1; i < A; i++)
    {
        if(t[i]&1) s |= 1<<i;
        ans += t[i]>>1;
    }
    ans += f[s];
    cout << n-ans << "\n";
}