Educational Codeforces Round 64 (Rated for Div. 2)题解(DE)

发表于 | 分类于 |

这次CF最终还是unrated了。虽然A题无限WApoint3（包括本菜在内）很容易让大家心态爆炸，但个人认为，B、C题做的好坏更为关键（这次的B和C都不是特别简单，需要仔细思考一下，否则很容易出错）。B题我采用的判断方法是奇偶字母分开，再把整个奇数序列放在偶数序列的前面或者后面，判断两序列交界的两个字母是否不相邻，如果两种方法都不可行就说明无解。C题主要是二分的策略问题，数值小的作为左端点优，数值大的作为右端点优，所以把序列一分为二，二分答案求分界点即可。（等等这篇好像是DE的题解来着？）

D题是一个比较典型的树形dp，但很遗憾本菜在比赛完之后才解决……首先读题要准确，节点对是相对有序的，所以全0序列和全1序列要算两次(因为x到y，y到x各算一次)，而先0后1序列只算一次。首先读图，随便找根节点建树，对于每一个节点，要记录它的子孙节点到它为止的全0、全1、先0后1、先1后0四种序列的数量(分别记为f00,f11,f01,f10)，由它的每一个儿子转移过来：如果儿子连向当前节点的边为0，那么更新f00和f10 （坑点：注意f00要加上儿子直接连接自己的、只有一条边的路径，f10除了由儿子的f10转移，还要由f11转移）；类似处理边为1的情况。然后就是儿子两两组合了（当然真的两两枚举肯定T，所以用当前儿子方案数×(总方案数减去当前儿子方案数)）：设以当前节点为路径中最高节点的路径集合为ans，那么ans要包括00+00，11+11，00+11，00+01，01+11这么多种情况，还要加上当前节点是路径端点、也即只用到一个儿子的情况。细节很 丰富糟糕 ，不知不觉，时间就在调试中消逝了~ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
#define maxn 201000
#define maxm 500100
using namespace std;
typedef long long ll;
struct node{
	vector<int>son;
	int fa,sz,v;
	ll f00,f01,f10,f11,ans;
}te[maxn];
struct ljb{
	
	int firstEdge[maxn],used[maxn],m,n;
	node dist[maxn];
	struct edgeNode{
		int x,v,next;
	}edge[maxm*2];
	
	ljb(){
		memset(this,0,sizeof(ljb));
	}
	inline void append(int op,int ed,int va){
		m++;
		edge[m].v=va;
		edge[m].x=ed;
		edge[m].next=firstEdge[op];
		firstEdge[op]=m;
	}
}graph;
void bt(const int&x,const int&fa){
	te[x].fa=fa;te[x].sz=1;
	for(int q=graph.firstEdge[x];q;q=graph.edge[q].next){
		if(graph.edge[q].x!=fa){
			te[x].son.push_back(graph.edge[q].x);
			te[graph.edge[q].x].v=graph.edge[q].v;
			bt(graph.edge[q].x,x);
			te[x].sz+=te[graph.edge[q].x].sz;
		}
	}
}
void dfs(int x){
	
	for(auto&i:te[x].son){
		dfs(i);
		if(te[i].v){
			te[x].f01+=te[i].f00+te[i].f01;
			te[x].f11+=1+te[i].f11;
		}
		else{
			te[x].f10+=te[i].f10+te[i].f11;
			te[x].f00+=1+te[i].f00;
		}
	}
	te[x].ans=te[x].f00*2+te[x].f11*2+te[x].f00*te[x].f11+te[x].f01+te[x].f10;
	for(auto&i:te[x].son){
		if(te[i].v){
			te[x].ans+=(te[i].f11+1)*(te[x].f01-te[i].f01-te[i].f00);
			te[x].ans+=(te[i].f11+1)*(te[x].f11-te[i].f11-1);
		}
		else{
			te[x].ans+=(te[i].f00+1)*(te[x].f10-te[i].f10-te[i].f11);
			te[x].ans+=(te[i].f00+1)*(te[x].f00-te[i].f00-1);
		}
	}
}
int main (/*int argc, char const* argv[]*/){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int n;cin>>n;
	for(int i=1;i<n;i+=1){
		int x,y,v;cin>>x>>y>>v;
		graph.append(x,y,v);
		graph.append(y,x,v);
	}
	bt(1,0);
	dfs(1);
	ll ans=0;
	for(int i=1;i<=n;i+=1){
		ans+=te[i].ans;
	}
	cout<<ans<<endl;
	return 0;
}

E:蛇皮做法。老规矩，先用单调栈预处理每个点作为最大点的的覆盖范围；注意到输入数据是1~n的一个排列，所以预处理每一个数所在的位置。然后枚举每个点(不妨叫它x)，求出x作为最大点可以满足条件的区间数量，求法很暴力：选取左边区间和右边区间中较短的那个区间，对这个区间的每一个元素y，求出x-y，判断它的位置是否在x覆盖的另一个区间内。累计总数量得到答案。

这个算法显然是正确的，但神奇之处在于它的时间复杂度不是看上去的$Θ(n^2)$，实际上非常快。具体的证明比较难(本菜并不会)，但也许可以这么理解：
x为最大值n时，位置最差时为区间中点，此时需要枚举答案区间端点的数量最多，为n/2，相当于x把区间分成等长的两部分；然后x取n-1和n-2，位置最差时分别为各个部分的中点，此时各自分别需要枚举最多的n/4个端点，总共数量为n/2，相当于区间被分为4等分；再取x为n-3到n-6……这样相当于构造了树形结构，共有$log_2n$层，每层枚举数量为n/2，总共枚举数量为$(nlog_2n)$，对于题目给的数据范围可以接受。
伪证毕。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
int lft[301000],rgt[301000],loc[301000],a[301000];
int main (/*int argc, char const* argv[]*/){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int n;cin>>n;
	for(int i=1;i<=n;i+=1){
		cin>>a[i];
		loc[a[i]]=i;
	}
	stack<int>st1,st2;
	for(int i=1;i<=n;++i){
		while(st1.size()&&a[st1.top()]<a[i])st1.pop();
		if(!st1.size())lft[i]=1;
		else lft[i]=st1.top()+1;
		st1.push(i);
	}
	for(int i=n;i;--i){
		while(st2.size()&&a[st2.top()]<a[i])st2.pop();
		if(!st2.size())rgt[i]=n;
		else rgt[i]=st2.top()-1;
		st2.push(i);
	}
	long long ans=0;
	for(int i=1;i<=n;i+=1){
		int l=lft[i],r=rgt[i];
		if(i-l<=r-i){
			for(int j=lft[i];j<i;++j){
				int k=loc[a[i]-a[j]];
				if(k<=r&&k>i)++ans;
			}
		}
		else{
			for(int j=rgt[i];j>i;--j){
				int k=loc[a[i]-a[j]];
				if(k>=l&&k<i)++ans;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

以上。