https://ac.nowcoder.com/acm/contest/5674

F - Groundhog Looking Dowdy

 

题意：给定 n 个数列，要求从其中 m 个数列中各取一个数，使得取出的数最大值与最小值的差最小。

尺取法

把所有数放在一起从小到大排序，并且要记录好每个数属于哪个数组。

维护首尾两个指针，满足中间包含 m 个不同的数组（如果一个数组被包含多次也是可以的），从头开始向后蠕动，每次更新答案。

因为尾指针不会回头，所以每点最多遍历两次。

其实很像单调队列。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 1e9 + 7;
int n, m;
typedef pair<int, int>pii;
int cnt[N];
vector<pii>vc;
int ans = INF;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		int k, x;
		scanf("%d", &k);
		for (int j = 0; j < k; j++) {
			scanf("%d", &x);
			vc.push_back(pii(x, i));
		}
	}
	sort(vc.begin(), vc.end());
	int p = 0, tmp = 0;
	for (int i = 0; i < (int)vc.size(); i++) {
		while (p != vc.size() && tmp < m) {
			int x = vc[p].second;
			cnt[x]++;
			if (cnt[x] == 1)tmp++;
			p++;
		}
		if (tmp == m)ans = min(ans, vc[p - 1].first - vc[i].first);
		int x = vc[i].second;
		cnt[x]--;
		if (!cnt[x])tmp--;
	}
	printf("%d\n", ans);
	return 0;
}

 

K - The Flee Plan of Groundhog

 

题意：给定一棵树，A 先从 1 向 n 移动 t 个点，B 这时从 n 开始以一秒 2 点 的速度追 A，B开始以 一秒 1 点的速度逃跑，问最多多久追上。

服了，搞自己有一手的。

如果开始追的时候 A 就在 n，则时间为 0 ！！

设开始追时 A 在点 u。

做法一：先处理出以 n 为根时各点深度，再处理出以 u 为根时个点深度，再从小到大枚举时间，可以得到与 u 距离 i 的所有点，如果 n 到这些点距离更小，则说明会被追上，则不能再继续枚举。对于所有被枚举到的点，用它与 n 的距离更新答案。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 998244353;
int n, t;
vector<int>G[N];
int d1[N], fa[N], d2[N];
void dfs(int u, int _fa) {
	fa[u] = _fa;
	for (int v : G[u]) {
		if (v == _fa)continue;
		d1[v] = d1[u] + 1;
		dfs(v, u);
	}
}
void dfs2(int u, int _fa) {
	for (int v : G[u]) {
		if (v == _fa)continue;
		d2[v] = d2[u] + 1;
		dfs2(v, u);
	}
}
vector<int>vc[N];
int main() {
	scanf("%d%d", &n, &t);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(n, 0);
	int u = 1;
	while (t--&&u != n) {
		u = fa[u];
	}
	dfs2(u, 0);
	for (int i = 1; i <= n; i++)vc[d2[i]].push_back(i);
	int ans = 0;
	for (int i = 0; i < n; i++) {
		bool flg = 0;
		for (int u : vc[i]) {
            ans = max(ans, (d1[u] + 1) / 2);
			if ((d1[u] + 1) / 2 > i) {
				flg = 1;
			}
		}
		if (!flg)break;
	}
	printf("%d\n", ans);
	return 0;
}

 

做法二：bfs

第一种做法只在速度为1，2时可行，并不推荐。

要找到一条从 u 出发，并且每一步都不会被追到的最长路径（每一步距离 n 比 距离 u 更远），用bfs找合法路径是很基本的了。

bfs 每次只延伸合法的点，所以显然找出的每条路径都是完全合法的。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 998244353;
int n, t;
vector<int>G[N];
int d1[N], fa[N], d2[N];
void dfs(int u, int _fa) {
	fa[u] = _fa;
	for (int v : G[u]) {
		if (v == _fa)continue;
		d1[v] = d1[u] + 1;
		dfs(v, u);
	}
}
typedef pair<int, int>pii;
int d[N];
int ans;
void bfs(int s) {
	priority_queue<pii, vector<pii>, greater<pii> >q;
	memset(d, 0x3f, sizeof(d));
	q.push(pii(0, s));
	d[s] = 0;
	while (!q.empty()) {
		int u = q.top().second, di = q.top().first; q.pop();
		if (di > d[u])continue;
		ans = max(ans, (d1[u] + 1) / 2);
		if ((d1[u] + 1) / 2 <= di)continue;
		for (int v : G[u]) {
			if (d[v] > d[u] + 1) {
				d[v] = d[u] + 1;
				q.push(pii(d[v], v));
			}
		}
	}
}
int main() {
	scanf("%d%d", &n, &t);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(n, 0);
	int u = 1;
	while (t--&&u != n) {
		u = fa[u];
	}
	bfs(u);
	printf("%d\n", ans);
	return 0;
}

 

E - Groundhog Chasing Death

题意：给定 a,b,c,d,x,ya,b,c,d,x,y，求 ∏i=ab∏j=cdgcd⁡(xi,yj)\prod_{i=a}^b\prod_{j=c}^d \gcd(x^i,y^j)，0⩽a,b,c,d⩽3×106,0<x,y⩽109,a⩽b,c⩽d0⩽a,b,c,d⩽3×10^6,0<x,y⩽10^9,a⩽b,c⩽d。

服了，搞自己有一手的。

发现 x，y 的范围完全可以先预处理质因数分解，再枚举质因数即可。

对于每个质因数，设 x=pn,y=pmx=p^n,y=p^m，则 gcd⁡(xi,yj)=pmin⁡(ni,mj)\gcd(x^i,y^j)=p^{\min(ni,mj)}，所以问题变为求 ∑i=ab∑j=cdmin⁡(ni,mj)\sum_{i=a}^b\sum_{j=c}^d \min(ni,mj)，这是个简单的分段函数。枚举 ii，则 nini 确定了，则 j≤⌊nim⌋j\le \lfloor\frac{ni}{m}\rfloor 时最小值取 mjmj，否则最小值取 nini。取 mjmj 时是一个等差数列，公式求和；取 nini 时是几个常数相加。都可以直接求和。

要注意的是上面求出来的是 指数位置的值，取 mod 时要对 ϕ(mod)\phi(mod) 取模！！！

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 998244353;
const ll phi = mod - 1;
ll prime[N];     //记录质数
int is_prime[N];
int vis[N];      //记录最小质因子
int euler_sieve(int n) {
	int cnt = 0;
	memset(vis, 0, sizeof(vis));
	memset(prime, 0, sizeof(prime));
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) { vis[i] = i; prime[cnt++] = i; is_prime[i] = true; }    //vis[]记录x的最小质因子
		for (int j = 0; j < cnt; j++) {
			if (i*prime[j] > n)  break;
			vis[i*prime[j]] = prime[j];              //vis[]记录x的最小质因子
			if (i%prime[j] == 0)
				break;
		}
	}
	return cnt;
}
map<ll, ll>px, py;
ll a, b, c, d, x, y;
ll Pow(ll a, ll b) {
	ll res = 1ll;
	while (b) {
		if (b & 1)res = res * a%mod;
		a = a * a%mod;
		b >>= 1;
	}
	return res;
}
ll n, m;
ll cal(ll a, ll b, ll c, ll d) {
	if (b <= 0 || d <= 0)return 0;
	ll res = 0ll;
	for (ll i = a; i <= b; i++) {
		ll tmp = n * i;
		ll j = min(d, tmp / m);
		if (j >= c)res = (res + (j + c)*(j - c + 1) / 2 % phi*m%phi) % phi;
		if (j < d) {
			ll t = min(d - c + 1, d - j);
			res = (res + t % phi*n%phi*i%phi) % phi;
		}
	}
	return res;
}
int main() {
	int tot = euler_sieve(100000);
	scanf("%lld%lld%lld%lld%lld%lld", &a, &b, &c, &d, &x, &y);
	for (int i = 0; i < tot && prime[i] * prime[i] <= x; i++) {
		if (x%prime[i] != 0)continue;
		int cnt = 0;
		while (x%prime[i] == 0) {
			x /= prime[i];
			cnt++;
		}
		px[prime[i]] = cnt;
	}
	if (x != 1)px[x] = 1;
	for (int i = 0; i < tot && prime[i] * prime[i] <= y; i++) {
		if (y%prime[i] != 0)continue;
		int cnt = 0;
		while (y%prime[i] == 0) {
			y /= prime[i];
			cnt++;
		}
		py[prime[i]] = cnt;
	}
	if (y != 1)py[y] = 1;
	ll ans = 1ll;
	for (auto p : px) {
		if (!py.count(p.first))continue;
		n = p.second, m = py[p.first];
		ll cnt = cal(a, b, c, d);
		ans = ans * Pow(p.first, cnt) % mod;
	}
	printf("%lld\n", ans);
	return 0;
}

 

J - The Escape Plan of Groundhog

 

题意：给定一个 01 矩阵，要找到一个子矩阵，满足：四边都是 1，除四边外 1 的个数与 0 的个数差值不超过 1，长宽都大于 1。问合法的子矩阵个数。

前缀和

看到数据范围考虑 O(n3)O(n^3)。

枚举上边界所在行，下边界所在行，右边界所在列。

对于每一个确定了的上，下，右 边界，需要找到合法的左边界个数，这就很像二维偏序，一边插入一边统计，维护一个队列，队列中存所有与当前列可能配对的列，即上下边界都是 1 ，且队列中列也都是 1。则只需要再满足01个数差不超过 1。

把 0 变成 -1，1 还是 1，则得到的就是范围内 1 的个数减 0 的个数。维护前缀和，如果两个前缀和的值相差不超过 1，则中间区域满足条件。对每个前缀和值计数，需要时直接取。

由于前缀和可能为负，所有要加上base。当然如果用C写则不是必要的，但是由于可能不稳定，所以还是建议+base。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 998244353;
int n, m;
int a[510][510];
int s1[510][510], s2[510][510], s3[510];
int mp[N];
queue<int>q;
int base = 250000;
ll ans;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)scanf("%d", &a[i][j]);
	}
	for (int j = 1; j <= m; j++) {
		for (int i = 1; i <= n; i++) {
			if (a[i][j] == 0)s1[j][i] = s1[j][i - 1] - 1;
			else s1[j][i] = s1[j][i - 1] + 1;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)s2[i][j] = s2[i][j - 1] + a[i][j];
	}
	for (int u = 1; u < n; u++) {
		for (int d = u + 1; d <= n; d++) {
			while (!q.empty())q.pop();
			for (int j = 1; j <= m; j++) {
				if (s1[j][d] - s1[j][u - 1] != d - u + 1) {
					s3[j] = s3[j - 1] + s1[j][d - 1] - s1[j][u];
					continue;
				}
				while (!q.empty() && (s2[u][j] - s2[u][q.front() - 1] != j - q.front() + 1 || s2[d][j] - s2[d][q.front() - 1] != j - q.front() + 1)) {
					mp[s3[q.front()] + base]--;
					q.pop();
				}
				s3[j] = s3[j - 1] + s1[j][d - 1] - s1[j][u];
				ans += mp[s3[j - 1] + base] + mp[s3[j - 1] - 1 + base] + mp[s3[j - 1] + 1 + base];
				q.push(j);
				mp[s3[j] + base]++;
			}
			for (int j = 1; j <= m; j++)mp[s3[j] + base] = 0;
		}
	}
	printf("%lld\n", ans);
	return 0;
}