2022-9-6总结

排列

因为可以任意排列，所以我们可以想到尽量把大于 $0$ 的数放到一起。所以我们可以先把大于 $0$ 的全加起来，再进行一些取舍。

对于一个形如 $a \rightarrow b \rightarrow c$ 的限制，也就是如果选了 $a,c$ 就必须选 $b$。

如果 $x_b < 0$ 的话，要么就选上 $b$ ，要么就不选 $a$ 或不选 $c$，而我们需要一种代价最小的方案，可以想到最小割（一条链的模型）。

而这种情况只有在 $x_a > 0, x_b < 0, x_c > 0$ 时才需要取舍，所以我们可以拆点。

如果 $a_i > 0$，就连两条边: $S \stackrel{x_i}{\longrightarrow} i$ 和 $i' \stackrel{x_i}{\longrightarrow} T$，如果 $x_i < 0$，就连一条 $i \stackrel{-x_i}{\longrightarrow} i'$，的边。

对于一个 $a \rightarrow b$ 的限制，直接连 $a \stackrel{+\infty}{\longrightarrow} b$ 和 $a' \stackrel{+\infty}{\longrightarrow} b'$，的边。

可以看出来，这样连边后需要取舍的情况就会变成一条相应的链，需要从中割去一条边，而一个点的哪条边被割去就相当于在链里的哪个地方没有选。

数据范围 $n \le 500$
$m \le 1000$，直接dinic就可以过了。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int N = 1005;
const int M = 1005;
const int INF = 0x3f3f3f3f;

namespace graph {
	const int SIZE = (N*2+M*2)*4;
	struct edge {
		int to, flow, next;
	} e[M*2];
	int head[N], ecnt = 1;
	int dis[N], cur[N];
	int S, T;
	int dinic();
	bool bfs(int S, int T);
	int dfs(int x, int flow);
	void insert(int u, int v, int f);
}
using namespace graph;

#define l(i) (i)
#define r(i) (i+n)

int n, m, sum;

int main()
{
	read(n, m);
	S = n*2+1, T = n*2+2;
	for(int i = 1, x; i <= n; i++)
	{
		read(x);
		if(x > 0)
		{
			sum += x;
			insert(S, l(i), x);
			insert(r(i), T, x);
		}
		else
			insert(l(i), r(i), -x);
	}
	for(int i = 1; i <= m; i++)
	{
		int a, b; read(a, b);
		insert(l(a), l(b), INF);
		insert(r(a), r(b), INF);
	}
	print(sum-dinic());
}

namespace graph {
	int dinic()
	{
		int maxflow = 0;
		while(bfs(S, T) == true)
			maxflow += dfs(S, INF);
		return maxflow;
	}
	bool bfs(int S, int T)
	{
		memset(dis, 0, sizeof(dis));
		memcpy(cur, head, sizeof(cur));
		queue<int> q; int x;
		q.push(S); dis[S] = 1;
		while(q.size())
		{
			x = q.front(); q.pop();
			for(int i = head[x]; i; i = e[i].next)
			{
				if(e[i].flow and !dis[e[i].to])
				{
					dis[e[i].to] = dis[x]+1;
					q.push(e[i].to);
				}
				
			}
		}
		return dis[T];
	}
	
	int dfs(int x, int flow)
	{
		if(x == T) return flow;
		int rest = flow, k, i;
		for(i = cur[x]; i; i = e[i].next)
		{
			if(e[i].flow and dis[e[i].to] == dis[x]+1)
			{
				k = dfs(e[i].to, min(rest, e[i].flow));
				if(k == 0) dis[e[i].to] = -1;
				e[i].flow -= k, e[i^1].flow += k;
				if(!(rest -= k)) break;
			}
		}
		return flow-rest;
	}
	void insert(int u, int v, int f)
	{
		e[++ecnt] = {v, f, head[u]}; head[u] = ecnt;
		e[++ecnt] = {u, 0, head[v]}; head[v] = ecnt;
	}
}

±AB

原题：ARC127F

#include <iostream>
#include <cmath>
using namespace std;

typedef long long ll;

ll a, b, v, m;

auto calc(ll a, ll b, ll v, ll m) -> ll;
auto get(ll a, ll b, ll l, ll r) -> ll;
main()
{
    int t; cin >> t;
    while(t --> 0)
    {
        cin >> a >> b >> v >> m;
        if(a+b <= m+1) cout << m+1 << "\n";
        else cout << calc(a,b,v,m)+calc(b,a,v,m)+1 << "\n";
    }
}

auto calc(ll a, ll b, ll v, ll m) -> ll
{
    ll v0 = v%b, p = 0;
    if(v0+a <= m) p = get(a, b, m-a-v0+1, b-v0-1);
    return p + (v+p*a)/b;
}
auto get(ll a, ll b, ll l, ll r) -> ll
{
    if(!a) return 0; ll q = 0;
    if((l-1)/a == r/a) q = get(b%a, a, (a-r%a)%a, (a-l%a)%a);
    return (q*b+l+a-1)/a;
}

Keep XOR Low

$\operatorname{xor}$ 题直接做不好做我们考虑建一棵 01-trie，我们发现维护一下子树大小就可以很快的知道一个二进制位下有多少个数，这启示我们在 01-trie 上统计方案数。

我们考虑一个函数 solve(a, b)， 其中 $a,b$ 是 01-trie 上两个相同深度的节点，且它们到根的路径这一部分的异或值不超过 $x$，solve(a,b) 用来求在 $a,b$ 的子树中选择的方案数。

然后就是对选择哪个子树的分类讨论了。

#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;
const int N = 150005;
const int P = 998244353;

namespace trie {
    const int SIZE = N*32;
    int siz[SIZE];
    int son[SIZE][2];
    int root, node_cnt;
    
    void insert(int val, int &i = root, int d = 30)
    {
        if(i == 0) i = ++node_cnt; siz[i]++;
        if(d != -1) insert(val, son[i][(val>>d)&1], d-1);
    }
}
using namespace trie;

int n, x;
ll pw[N];

void prework();
ll solve(int a, int b, int d = 30);

int main()
{
    cin >> n >> x; prework();
    for(int i = 1, a; i <= n; i++)
        cin >> a, trie::insert(a);
    ll ans = solve(root,root)-1;
    cout << (ans+P)%P;
}

ll solve(int a, int b, int d)
{
    if(!a) return pw[siz[b]];
    if(!b) return pw[siz[a]];
    int als = son[a][0], ars = son[a][1];
    int bls = son[b][0], brs = son[b][1];
    if(a == b)
    {
        if(d == -1) return pw[siz[a]];
        if((x>>d)&1)
            return solve(als, ars, d-1);
        else
        {
            ll val = solve(als, als, d-1) + solve(ars, ars, d-1) - 1;
            return (val%P+P)%P;
        }
    }
    else
    {
        if(d == -1) return pw[siz[a]+siz[b]];
        if((x>>d)&1)
            return solve(als, brs, d-1) * solve(ars, bls, d-1) % P;
        else
        {
            ll val = (solve(als, bls, d-1) + solve(ars, brs, d-1)-1+P) % P;
            (val += (pw[siz[als]]-1) * (pw[siz[ars]]-1)) %= P;
            (val += (pw[siz[bls]]-1) * (pw[siz[brs]]-1)) %= P;
            return val;
        }
    }
}
void prework()
{
    pw[0] = 1;
    for(int i = 1; i < N; i++)
        pw[i] = pw[i-1]*2%P;
}