Educational Codeforces Round 139（CF1766）

令人震撼。

E.Decomposition

题目描述：

对于 $n$ 个数 $x_1,x_2,...,x_n$，定义其拆分为：

从 $1$ 到 $n$ 的顺序遍历 $x_1,x_2,...,x_n$。

设当前遍历到 $x_i$：

• 如果当前没有序列或者任何一个序列的结尾 $\operatorname{AND}$（按位与）$x_i$ 都为 $0$，那么新开一个序列，新序列中只包含这一个值。

• 否则找到第一个结尾 $\operatorname{AND}\space x_i$ 不为 $0$ 的序列，把 $x_i$ 加在其结尾。

设 $f([x_1,x_2,...,x_n])$ 为拆分得到序列的个数。给出 $a_1,a_2,...,a_n$，求 $\sum_{i=1}^n\sum_{j=i}^nf([a_i,a_{i+1},...,a_j])$。

$1 \le n \le 3 \cdot 10^5$，$0 \le a_i \le 3$

题目分析：

一眼看过去没啥头绪，观察到 $a$ 的范围很小，所以考虑在这么小的范围内会有什么性质。

首先若 $a_i = 0$，则其与任何一个数的 $\text{AND}$ 均为 $0$，也就是说必然会新开一个序列，所以其不会对其它的数的形成序列的情况产生影响，可以在处理其他的数的时候忽略掉 $a_i = 0$ 的位置产生的序列，最后再对于每个 $a_i = 0$ 的位置判断一下会造成多少影响即可。

注意到我们只有三个数，所以显然序列个数不会超过 $3$ 个，因为最多也就是一个数占一个序列，这样的话后来的数就必然可以找到对应的序列的位置了。

当然这样并不是很严谨，因为 $3$ 与 $1,2$ 的按位与均不为 $0$ 所以可能会有一些其他的情况，手模一下的话就会发现大部分情况就是只有两个序列，只有少部分情况能造出来三个序列。

因为只有三个序列所以我们可以直接 $dp$ 记录下三个序列结尾是什么即可。

具体来说就是设 $dp[i][a][b][c]$ 表示以 $i$ 为右端点的区间，形成的三个序列的最后一个数分别为 $a,b,c$ 的方案数，注意这里序列为空我们定义为最后一个数为 $0$，然后每次新加入一个数就暴力模拟一下加入哪里即可。

$dp$ 的初值其实就是 $dp[i][a_i][0][0] = 1$。

时间复杂度 $O(n)$。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5+5;
int a[N];
int dp[N][5][5][5];
void add(int &a,int b){
	a = a + b;
}
signed main(){
	int n;scanf("%lld",&n);
	for(int i=1; i<=n; i++)	scanf("%lld",&a[i]);
	for(int i=0; i<n; i++){
		int p[4];
		for(p[1]=0; p[1]<=3; p[1]++){
			for(p[2]=0; p[2]<=3; p[2]++){
				for(p[3]=0; p[3]<=3; p[3]++){
					if(!dp[i][p[1]][p[2]][p[3]])	continue;
					if(!a[i+1]){
						dp[i+1][p[1]][p[2]][p[3]] = dp[i][p[1]][p[2]][p[3]];
						continue;
					}
					if((p[1] & a[i+1]) || !p[1]){
						add(dp[i+1][a[i+1]][p[2]][p[3]],dp[i][p[1]][p[2]][p[3]]);
					}
					else if((p[2] & a[i+1]) || !p[2]){
						add(dp[i+1][p[1]][a[i+1]][p[3]],dp[i][p[1]][p[2]][p[3]]);
					}
					else if((p[3] & a[i+1]) || !p[3]){
						add(dp[i+1][p[1]][p[2]][a[i+1]],dp[i][p[1]][p[2]][p[3]]);
					}
				}
			}
		}
		add(dp[i+1][a[i+1]][0][0],1);
	}
	int ans=0;
	for(int i=1; i<=n; i++){
		for(int A=0; A<=3; A++){
			for(int B=0; B<=3; B++){
				for(int C=0; C<=3; C++){
					if(dp[i][A][B][C]){
						add(ans,((A != 0) + (B != 0) + (C != 0)) * dp[i][A][B][C]);
					}
				}
			}
		}
	}
	for(int i=1; i<=n; i++){
		if(!a[i])	add(ans,i*(n-i+1));
	}
	printf("%lld\n",ans);
	return 0;
}

F.MCF

题目描述：

你需要解决一个有源汇最小费用可行流问题，但是，容量与流量的奇偶性必须相同。

点数在 $2\sim100$ 范围内，边数在 $1\sim200$ 范围内，容量在 $1\sim100$ 范围内，费用在 $-100\sim100$ 范围内。

图中没有负环。

题目分析：

最难受的也就是这个奇偶性必须相同的限制，想想怎么去了。

可以考虑先将所有容量为奇数的边强制流 $1$ 的流量，然后这样的话我们就可以让所有的边容量变成 $\lfloor \frac{c}{2} \rfloor$，就是一个正常的最小费用可行流的问题，然后将跑出来的流量乘以 $2$ 即可。

那么对于这些强制流的 $1$ 该如何处理呢，我们假设只考虑这些强制流 $1$ 的边，点 $i$ 的流入流量减流出流量为 $f_i$，显然若 $f_i$ 为奇数则无解，当然如果 $f_1,f_n$ 为奇数也是有解的因为源汇可以不满足流量守恒。

否则的话如果 $f_i > 0$，我们就可以从 $S$ 到 $i$ 连流量为 $\frac{f_i}{2}$ 费用为 $-\infty$ 的边来强制让这个流量也流过去，所以如果最后的残量网络中，这些边还有一些剩余流量则无解。

对于 $f_i < 0$ 的情况也是同理的。

但是如果按照正常可行流的做法从 $T$ 到 $S$ 连边的话就会造成负环比较寄，可以造一个虚拟的源汇 $S',T'$，并且连边 $S' \to S$ 和 $T \to T'$，由 $S',T'$ 来承担强制流某些流量的任务即可。

最小费用可行流其实就是如果我们跑出来的最短路的费用小于 $0$ 则增广，否则不增广。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 200+5;
const int MAXM = 1000+5;
const int INF = 1e9+5;
struct edge{
	int nxt,to,val,cost;
	edge(){}
	edge(int _nxt,int _to,int _val,int _cost){
		nxt = _nxt,to = _to,val = _val,cost = _cost;
	}
}e[MAXM];
int n,m,cnt = 1,flow[MAXN],dis[MAXN],pos[MAXN],mark[MAXN],head[MAXN],s,t,cur[MAXN],a[100][100];
bool vis[MAXN],in_que[MAXN];
bool spfa(){
	for(int i=1; i<=t; i++){
		dis[i] = INF;vis[i] =false;in_que[i]=false;cur[i]=head[i];
	}
	queue<int> q;
	q.push(s);dis[s] = 0;in_que[s] = true;
	bool flag = false;
	while(!q.empty()){
		int now = q.front();q.pop();in_que[now] = false;
		for(int i = head[now]; i;i = e[i].nxt){
			int to = e[i].to;
			if(e[i].val && dis[to] > dis[now] + e[i].cost){
				if(to == t)	flag = true;
				dis[to] = dis[now] + e[i].cost;
				if(!in_que[to]){
					q.push(to);
					in_que[to] = true;
				}
			}
		}
	}
	return flag;
}
int dfs(int now,int limit){
	if(now == t)	return limit;
	int flow = 0;vis[now] = true;
	for(int i = cur[now]; i && flow < limit; i = e[i].nxt){
		int to = e[i].to;
		cur[now] = i;
		if(e[i].val && dis[to] == dis[now] + e[i].cost && !vis[to]){
			int h = dfs(to,min(limit - flow,e[i].val));
			e[i].val -= h;e[i^1].val+=h;flow+=h;
			if(!h)	dis[to] = -INF;
		}
	}
	return flow;
}
void dinic(){
	while(spfa()){
		if(dis[t] >= 0)	break;
		dfs(s,INF);
	}
}
void add_edge(int from,int to,int val,int cost){
	e[++cnt] = edge(head[from],to,val,cost);
	head[from] = cnt;
	e[++cnt] = edge(head[to],from,0,-cost);
	head[to] = cnt;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(int i=1; i<=m; i++){
		int from,to,val,cost;scanf("%lld%lld%lld%lld",&from,&to,&val,&cost);
		add_edge(from,to,val/2,cost);
		pos[i] = cnt;
		if(val & 1){
			mark[i] = 1;
			flow[from]--,flow[to]++;
		}
	}
	bool flag = true;
	s = n + 1,t = s + 1;
	for(int i=2; i<n; i++){
		if(flow[i] % 2 != 0)	flag = false;
		if(flow[i] > 0)	add_edge(s,i,flow[i]/2,-INF);
		if(flow[i] < 0)	add_edge(i,t,-flow[i]/2,-INF);
	}
	add_edge(s,1,INF,0);add_edge(n,t,INF,0);
	dinic();
	for(int i=2; i<=cnt; i++){
		if(e[i].cost == -INF && e[i].val != 0){
			flag = false;
		}
	}
	if(!flag){
		printf("Impossible\n");
		return 0;
	}
	printf("Possible\n");
	for(int i=1; i<=m; i++){
		printf("%lld ",e[pos[i]].val * 2 + mark[i]);
	}
	return 0;
}