T20201120

Posted on Edited on In Word count in article: 2.7k Reading time ≈ 10 mins.
大东辰的测试

T1

显然是从右向左贪心的处理，就是说要让右边的尽可能不选，来达到这个全局最小的目的。

那么就可以把所有的 A 看成 -1，而把 B 看成是 1， 那么就可以把后缀和小于等于 0 的部分忽略掉了，因为这个时候的主导因素是前面的元素了。然后如果某个时候这个后缀和大于 k 了，就是说这个点一定得选了。

Code

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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
char s[maxn];
int tw[maxn] = {1}, n, k, cnt, ans;

int main()
{
	freopen ("elect.in", "r", stdin);
	freopen ("elect.out", "w", stdout);
	scanf ("%d %d", &n, &k);
	scanf ("%s", s + 1);
	for (int i = 1; i <= n; ++i) tw[i] = (tw[i - 1] << 1) % mod;
	for (int i = n; i; --i) {
		if (s[i] == 'B') {
			++cnt;
			if (cnt > k) {
				ans = (ans + tw[i]) % mod;
				--cnt;
			} else continue;
		}
		cnt = max(0, cnt - 1);
	}
	printf ("%d\n", ans);
}

T2

容易发现，这个 \(k\) 太小了，完全可以暴力跳。

\(k\le10\)

这一部分就是送分的了，那么这个可以做一些什么呢？

考虑维护这样一个数组：sum[u][len] 表示 u 的子树中距离 u 小于等于 len 的所有点的点权之和。 所以对于一次查询，可以用非常简单的容斥往上跳 \(k\) 次，然后减去上来的子树的贡献。

时间复杂度 \(O(n+qk)\)，空间复杂度 \(O(nk)\)

Code

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 2e6 + 5;
int head[maxn], edge[maxn << 1], nxt[maxn << 1], cur;
ll sum[maxn][11], val[maxn];
int f[maxn][11];

inline void dfs(int u, int p)
{
	f[u][1] = p, sum[u][0] = val[u];
	sum[p][1] += val[u];
	for (int i = 2; i <= 10 && f[u][i - 1]; ++i) {
		f[u][i] = f[f[u][i - 1]][1];
		sum[f[u][i]][i] += val[u];
	}

	for (int i = head[u]; i; i = nxt[i]) {
		if (edge[i] == p) continue;
		dfs(edge[i], u);
	}
}

inline ll read()
{
	ll x(0);
	char o(getchar());
	while (o < '0' || o > '9') o = getchar();
	for (; o >= '0' && o <= '9'; o = getchar())
		x = (x << 1) + (x << 3) + (o ^ 48);
	return x;
}

inline void addedge(int u, int v)
{
	nxt[++cur] = head[u];
	head[u] = cur;
	edge[cur] = v;
}

inline ll solve(int p, int k)
{
	int nw = f[p][1], up = 1;
	ll res(sum[p][k]);
	while (nw && up <= k) {
		res += sum[nw][k - up];
		if (k > up) res -= sum[p][k - up - 1];
		++up, nw = f[nw][1], p = f[p][1];
	}
	return res;
}

int main()
{
	freopen ("tree.in", "r", stdin);
	freopen ("tree.out", "w", stdout);
	int n = read(), q, u, v;
	for (int i = 1; i <= n; ++i) val[i] = read();
	for (int i = 1; i < n; ++i) {
		u = read(), v = read();
		addedge(u, v), addedge(v, u);
	}
	
	dfs(1, 0);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= 10; ++j) 
			sum[i][j] += sum[i][j - 1];

	q = read();
	while (q--) {
		u = read(), v = read();
		printf ("%lld\n", solve(u, v));
	}
}

正解

上述算法，问题就是空间开不下，那么如果说可以用 \(O(n)\) 的空间来做这件事情，这道题就可以过了。

那么就可以考虑长链剖分，用这一条链来辅助整棵树的操作。

那么就可以用 f[id[v]] 表示当前以 u 为子树时，所有深度严格低于该点的所有点的点权和的相反数。

所以当我们想要得到以 u 为子树，所有距离 u 小于等于 k 的点权和，就可以有这样的表示：ans = sum[u] + f[id[u] + k]。

这可以说是利用这长链剖分的性质：每一条链的编号的映射都是连续的。

所以就可以把所有的询问离线，把每一个操作变成 \(k\) 个，然后在把这 \(k\) 次操作按照这个容斥系数加起来就是索要求的的答案。

时间复杂度 \(O(n+qk)\)，空间复杂度 \(O(n)\)

Code

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

inline ll read()
{
	ll x(0);
	char o(getchar());
	while (o < '0' || o > '9') o = getchar();
	for (; o >= '0' && o <= '9'; o = getchar())
		x = (x << 1) + (x << 3) + (o ^ 48);
	return x;
}

const int maxn = 2e6 + 10;
ll f[maxn], val[maxn], ans[maxn], sum[maxn];
int head[maxn], edge[maxn << 1], nxt[maxn << 1], cur, cnt;
int id[maxn], mx[maxn], pr[maxn], son[maxn], dep[maxn];
int hd[maxn], ed[maxn], nx[maxn], fc[maxn], dis[maxn], top;

inline void addedge(int u, int v)
{
	nxt[++cur] = head[u];
	head[u] = cur;
	edge[cur] = v;
}

void dfs(int u, int f, int depth)
{
	pr[u] = f, mx[u] = dep[u] = depth;

	for (int i = head[u], v; i && (v = edge[i]); i = nxt[i]) {
		if (v == f) continue;
		dfs(v, u, depth + 1);

		if (mx[v] > mx[u]) {
			mx[u] = mx[v];
			son[u] = v;
		}
	}
}

void dfs(int u, int top) 
{
	if (u == top)
		id[u] = cnt + 1, cnt += mx[u] - dep[u] + 1;
	else id[u] = id[pr[u]] + 1;

	if (son[u]) dfs(son[u], top);
	for (int i = head[u], v; i && (v = edge[i]); i = nxt[i])
		if (v != pr[u] && v != son[u])
			dfs(v, v);
}

inline void addopt(int u, int v, int f, int k)
{
	nx[++top] = hd[u], fc[top] = f;
	dis[top] = k, ed[top] = v, hd[u] = top;
}

void solve (int u)
{
	if (son[u]) {
		solve(son[u]);
		sum[u] = sum[son[u]];
	}

	for (int i = head[u], v; i && (v = edge[i]); i = nxt[i]) {
		if (v == son[u] || v == pr[u]) continue;
		solve (v);
		int len = mx[v] - dep[v];
		sum[u] += sum[v];
		for (int j = 0; j <= len; ++j)
			f[id[u] + j + 1] += f[id[v] + j];
	}

	f[id[u]] = -sum[u];
	sum[u] += val[u];
	for (int i = hd[u]; i; i = nx[i])
		ans[ed[i]] += fc[i] * (sum[u] + f[id[u] + min(dis[i], mx[u] - dep[u])]);
}

int main()
{
	freopen ("tree.in", "r", stdin);
	freopen ("tree.out", "w", stdout);
	int n = read(), u, v;
	for (int i = 1; i <= n; ++i) val[i] = read();
	for (int i = 1; i < n; ++i) {
		u = read(), v = read();
		addedge (u, v);
		addedge (v, u);
	}

	dfs(1, 0, 1), dfs(1, 1);
	int q = read(), pre;
	for (int i = 1; i <= q; ++i) {
		u = read(), v = read();
		addopt (u, i, 1, v);
		while (pr[u] && v) {
			pre = u, u = pr[u], --v;
			addopt(u, i, 1, v);
			if (v > 0) addopt(pre, i, -1, v - 1);
		}
	}

	solve (1);

	for (int i = 1; i <= q; ++i) 
		printf ("%lld\n", ans[i]);
}

T3

首先注意到一个结论:给定一堆射线，一个起点，一个终点，则存在以起终点为两端点的曲线不与任何 射线相交，当且仅当对于任意两条射线，存在以起终点为两端点的曲线不与这两条射线相交。

证明有较大难度。考虑不连通时，起点所在的连通块一定是一个多边形(平面可以视作由4条射线围成的 有限区域)，然后考虑证明一定可以选出多边形上相邻两条边对应的射线分割起点和终点。这个问题亦即 对于多边形内任意一点和多边形外任意一点都可以选出多边形上相邻两条边对应的射线分割这两个点。

下面考虑归纳证明。

当多边形点数 = 3 时，可以枚举所有情况证明(实际上本质不同的情况只有 2 种)。

当多边形点数 = n (n > 3) 时，若多边形为凸多边形，可以任选连续的三条边，引出两条辅助线，考虑这样得到的 n - 1 边形，一定满足条件；那么现在相当于少了一对边，多了两对边，分类讨论这三条边的方向，共 8 种情况(实际上本质不同的情况只有 4 种)，即可证明。

若多边形为凹多边形，选出那个 > 180 度的角，显然这个角的两条边的方向是确定的(如下图所示)，作 出辅助线，同理这样得到的 n - 1 边形，一定满足条件;现在相当于删去两对边加入三对边，分类讨论 三条边的方向和起点所在的位置，即可证明。

现在回到原问题，我们将起点记作 S，终点记作 T。不妨假设 S 的纵坐标 T 的纵坐标，否则对所有点的纵坐标取反即可。将所有点分成三类:

  1. 纵坐标 > T 的。
  2. 纵坐标在 S, T 之间的。
  3. 纵坐标 < S 的。

对于交点为第一类的，无解等价于有向下的射线和向左或右的射线相交;对于交点为第二类的，无解等价于有向下的射线(端点可能是第一类的)和向左的射线相交，或向上的射线(端点可能是第三类的)和向右 的射线相交; 对于交点为第三类的，无解等价于有向上的射线和向左或右的射线相交。

对于第一类的端点，我们从上到下做一遍 dp， dp[i][l][r] 表示考虑纵坐标 >= i 的点，向下的射线横坐标的最小值为 l，最大值为 r 的方案数。第三类同理。

对于第二类端点，我们先枚举端点为第一类的向下的射线的横坐标的最小值 d，和端点为第三类的向上 的射线的横坐标的最大值 u，这样，所有横坐标 > d 的第二类端点不能向左，所有横坐标 < u 的第二类端点不能向右。然后从左到右 dp，dp[i][x][y] 表示考虑横坐标 <= i 的点，向下的射线的端点的纵坐标的最大值为 x，向右的射线的端点的纵坐标的最大值为 y 的方案数。时间复杂度 \(O(n^5)\)。

Code(%std)

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<bits/stdc++.h>
using namespace std;

typedef long long s64;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)

const int N=55,D=1e9+7;
int x[N],y[N];

namespace LISAN
{
void work(int a[],int n)
{
	static int b[N];
	rep(i,0,n)b[i]=a[i];
	sort(b,b+n+1);
	rep(i,0,n)a[i]=lower_bound(b,b+n+1,a[i])-b;
}
};

vector<s64> work(int n,int x[],int y[])
{
	static s64 dp[N][N][N];
	static int dy[N];
	rep(i,0,n+1)dy[y[i]]=x[i];
	memset(dp,0,sizeof(dp));
	dp[n+2][n+1][0]=1;
	per(i,n+1,y[n+1]+1)
	{
		int j=dy[i];
		rep(l,0,n+1)
		rep(r,0,n+1)
		{
			s64 f=dp[i+1][l][r];
			if(!f)continue;
			(dp[i][l][r]+=f*(1+(j<l)+(j>r)))%=D;
			(dp[i][min(l,j)][max(r,j)]+=f)%=D;
		}
	}
	vector<s64>ans(n+2);
	rep(l,0,n+1)
	rep(r,0,n+1)(ans[l]+=dp[y[n+1]+1][l][r])%=D;
	return ans;
}
void Kcz()
{
	int n;
	cin>>n;
	cin>>y[0]>>y[n+1]; 
	x[n+1]=1e9;
	rep(i,1,n)cin>>x[i]>>y[i];
	LISAN::work(x,n+1);
	LISAN::work(y,n+1);
	if(y[0]>y[n+1])rep(i,0,n+1)y[i]=n+1-y[i];
	
	vector<s64>ans1=work(n,x,y),ans2;
	rep(tmp,0,1)
	{
		swap(x[0],x[n+1]);
		swap(y[0],y[n+1]);
		rep(i,0,n+1){x[i]=n+1-x[i];y[i]=n+1-y[i];}
		if(!tmp)
		{
			ans2=work(n,x,y);
			reverse(ans2.begin(),ans2.end());
		}
	}
	
	static int dy[N];
	rep(i,0,n+1)dy[x[i]]=y[i];
	//rep(i,0,n+1)cerr<<dy[i]<<endl;
	s64 ans=0;
	rep(d,0,n+1)
	rep(u,0,n+1)
	{
		static s64 dp[N][N][N];
		memset(dp,0,sizeof(dp));
		dp[0][0][0]=1;
		rep(i,1,n)
		{
			int j=dy[i];
			if(j<y[0]||j>y[n+1])
			{
				memcpy(dp[i],dp[i-1],sizeof(dp[i]));
				continue;
			}
			rep(l,0,n+1)
			rep(r,0,n+1)
			{
				s64 f=dp[i-1][l][r];
				if(!f)continue;
				if(j>r)(dp[i][l][r]+=f)%=D;//up
				(dp[i][max(l,j)][r]+=f)%=D;//down
				if(i<=d&&j>l)(dp[i][l][r]+=f)%=D;//left
				if(i>=u)(dp[i][l][max(r,j)]+=f)%=D;//right
			}
		}
		s64 sum=0;
		rep(l,0,n+1)
		rep(r,0,n+1)sum+=dp[n][l][r];
		sum%=D;
		(ans+=ans1[d]*ans2[u]%D*sum)%=D;
	//	if(ans1[d]&&ans2[u])
	//		cerr<<d<<" "<<u<<" "<<ans1[d]<<" "<<ans2[u]<<" "<<sum<<endl;
	}
	s64 p4=1;
	rep(i,1,n)(p4*=4)%=D;
	cout<<((p4-ans)%D+D)%D<<endl;
}

int main()
{
	freopen("path.in","r",stdin);freopen("path.out","w",stdout);
	Kcz();
}