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

F - Fake Maxpooling

 

题意：nm的矩阵，a[i][j]=lcm(i,j)a[i][j]=lcm(i,j)，经过k*k的最大池化，求最终矩阵的元素和。

求出 lcm 之后观察发现当 k>1 时，最终的矩阵是递增的，所以可以滑动窗口一直滑，也不需要删除已经划过的了，因为后面必定大于前面。

至于求lcm，直接求也不会T，但是题解里用了类似二维埃氏筛的方法，还挺秀的。

不过这样多一个数组，内存会超。。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 5001;
#define ll long long
int a[N][N], g[N][N];
int n, m, k;
ll ans;
int mx[N], tp[N][N];
int main() {
	scanf("%d%d%d", &n, &m, &k);
	int t = max(n, m);
	for (int i = 1; i <= t; i++) {
		for (int j = 1; j <= t; j++) {
			if (!g[i][j]) {
				for (int k = 1; k * i <= t && k * j <= t; k++) {
					g[k*i][k*j] = k;
					a[k*i][k*j] = i * j*k;
				}
			}
		}
	}
	if (k == 1) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++)ans += a[i][j];
		}
		printf("%lld\n", ans);
		return 0;
	}
	int to = max(n, m);
	for (int i = 1; i <= to; i++) {
		for (int j = 1; j <= k; j++)tp[i][1] = max(tp[i][1], a[i][j]);
		for (int j = 2; j <= to - k + 1; j++)tp[i][j] = max(tp[i][j - 1], a[i][j + k - 1]);
	}
	int tmp = 0;
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j <= k; j++) {
			tmp = max(tmp, a[i][j]);
		}
	}
	mx[1] = tmp;
	for (int i = 1; i <= n - k + 1; i++) {
		if (mx[i] == 0)mx[i] = max(mx[i - 1], tp[i + k - 1][1]);
		tmp = mx[i];
		ans += tmp;
		for (int j = 2; j <= m - k + 1; j++) {
			tmp = max(tmp, tp[j + k - 1][i]);
			ans += tmp;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

 

单调队列

还可以单调队列求矩形内的最大值，这也是一种比较常用的方法了。

先对每一行单独求，以 j 为右端点的k个数的最大值。

再对每一列求，以上一次的最大值作为这次的数据求最大值，这样求出的就是一个矩形范围内的最大值。

二维的单调队列。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 2e5 + 10;
int n, m, k;
int gcd(int a, int b) {
	if (a < b)swap(a, b);
	return b == 0 ? a : gcd(b, a%b);
}
typedef pair<int, int>pii;
deque<pii>q;
int mr[5010][5010], a[5010][5010];
ll ans;
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)a[i][j] = i * j / gcd(i, j);
	for (int i = 1; i <= n; i++) {
		while (!q.empty())q.pop_back();
		for (int j = 1; j <= m; j++) {
			while (!q.empty() && (j - q.front().second >= k || q.front().first <= a[i][j]))q.pop_front();
			while (!q.empty() && q.back().first <= a[i][j])q.pop_back();
			q.push_back(pii(a[i][j], j));
			mr[i][j] = q.front().first;
		}
	}
	for (int i = k; i <= m; i++) {
		while (!q.empty())q.pop_back();
		for (int j = 1; j <= n; j++) {
			while (!q.empty() && (j - q.front().second >= k || q.front().first <= mr[j][i]))q.pop_front();
			while (!q.empty() && q.back().first <= mr[j][i])q.pop_back();
			q.push_back(pii(mr[j][i], j));
			if (j >= k)ans += q.front().first;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

 

C - Cover the Tree

 

题意：给定一棵树，要求构造出用最少的链覆盖所有边，可以相交。

构造

显然是要用两个叶子组成链，所以要看怎么配对。

把所有叶子按照dfs序排序，前一半的和后一半的配对。

假设节点 uu 覆盖的叶子节点的dfs序的范围为 [L,R][L,R]，则只要一条链的一端在这个范围内，另一端不在这个范围内，则这条链必定覆盖边 (u,fa[u])(u,fa[u])。可以证明对于上面的构造方法，无论 L，R 的范围多少，都可以找到这样一条链。

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;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 2e5 + 10;
int n;
vector<int>G[N], vc;
void dfs(int u, int _fa) {
    if ((int)G[u].size() == 1)vc.push_back(u);
    for (int v : G[u]) {
        if (v != _fa)dfs(v, u);
    }
}
int main() {
    scanf("%d", &n);
    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(1, 0);
    printf("%d\n", ((int)vc.size() + 1) / 2);
    for (int i = 0; i < ((int)vc.size() + 1) / 2; i++)printf("%d %d\n", vc[i], vc[i + (int)vc.size() / 2]);
    return 0;
}

 

B - Boundary

 

题意：给定平面上n个点，不重复且都不是原点，要画一个圆，经过原点，且经过尽可能多的给定点，求最多经过的点数。

计算几何+高精度

如果一个圆经过原点以及另外某点，则这个圆的圆心所在轨迹是一条直线，即这个点与圆心连线的中垂线。

把每个点对应的直线都画出来，最多的直线相交于同一点，则交点就是圆心。

所以基本上就是解方程，n2n^2 暴力求出每个交点，以及被经过的次数。

这里就要高精度了，存double肯定有乱七八糟的问题，所以用pair表示分数。而且不能求gcd约分，否则会T。

用map存还会T，要用vector存，最后sort再手动计数。

用 pair<pii,pii> 存必须约分，也就会T。所以用自定义的分数类了。

还要注意如果所有直线都平行，就没有交点了，这时最多只能经过一个点，如果有交点，则至少2个。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 2e5 + 10;
int n;
ll x[N], y[N];
ll a[N], b[N], c[N];
int vc[N0];
struct frac
{
	ll x, y;
	bool operator<(const frac& b) const {
		return ll(x)*(b.y) < ll(y)*(b.x);
	}
	frac operator*(const frac& b)
	{
		return frac(x*b.x, y*b.y);
	}
	bool operator==(const frac& b) const {
		return ll(x)*(b.y) == ll(y)*(b.x);
	}
	frac(ll a, ll b) : x(ll(a)), y(ll(b)) {}
};
struct point
{
	frac x, y;
	bool operator<(const point& b) const {
		return x == b.x ? y < b.y : x < b.x;
	}
	bool operator==(const point& b) const {
		return x == b.x && y == b.y;
	}
	point(ll a, ll b, ll c, ll d) : x(a, b), y(c, d)	//x = a / b, y = c / d
	{
		if (x.y < 0) x.x = -x.x, x.y = -x.y;
		if (y.y < 0) y.x = -y.x, y.y = -y.y;
	}
};
vector<point>v;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= 2000; i++)vc[i] = i * (i - 1) / 2;
	for (int i = 1; i <= n; i++)scanf("%lld%lld", &x[i], &y[i]);
	for (int i = 1; i <= n; i++) {
		a[i] = 2 * x[i], b[i] = 2 * y[i];
		c[i] = x[i] * x[i] + y[i] * y[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			ll x1 = c[i] * b[j] - c[j] * b[i];
			ll x2 = a[i] * b[j] - a[j] * b[i];
			if (x2 == 0)continue;

			ll y1 = c[i] * a[j] - c[j] * a[i];
			ll y2 = b[i] * a[j] - b[j] * a[i];
			if (y2 == 0)continue;
			v.push_back(point(x1, x2, y1, y2));
		}
	}
	if (v.empty()) { puts("1"); return 0; }    //所有直线平行，没有交点
	sort(v.begin(), v.end());
	int ans = 1, tmp = 1;
	for (int i = 1; i < (int)v.size(); i++) {
		if (v[i] == v[i - 1])tmp++;
		else tmp = 1;
		ans = max(ans, tmp);
	}
	ans = lower_bound(vc + 1, vc + n + 1, ans) - vc;
	printf("%d\n", ans);
	return 0;
}

 

J - Just Shuffle

 

题意：给定一个 1 到 n 的排列，要求给出一个排列的变换，使得最初的 1，2，···，n 的排列应用 k 次这个变换之后变为给定排列。

刚看到时觉得很像矩阵快速幂，E⋅Ak=BE\cdot A^k=B，要求 A。但如果要矩阵开根号又不会。

由于 E 为最朴素的排列，所以可以作为单位元省略，则 A=B1/k⋅EA=B^{1/k}\cdot E，这样对 E 应用 1k\frac{1}{k} 次 B 变换之后能得到 A，

然后就只能猜测这 1/k1/k 可以视为 k 的逆元。

对于一个变换，每个位置指向它下一次要到的位置，则可以找到几个环，应用一次变换就相当于沿着每个环前进一次，

所以对于一个环，要前进 1/k 次，也就是 k 对于环的长度的逆元。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 2e5 + 10;
inline int exgcd(int a, int b, int &x, int &y){
	if (b == 0){
		x = 1, y = 0;
		return a;
	}
	int ret = exgcd(b, a%b, x, y);
	int t = x; x = y, y = t - (a / b)*y;
	return ret;
}
int n, k;
int a[N], v[N], vis[N], ans[N];
vector<int>vc[N]; int tot;
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		v[a[i]] = i;
	}
	for (int i = 1; i <= n; i++) {
		if (vis[i])continue;
		tot++;
		int u = i;
		while (!vis[u]) {
			vis[u] = 1;
			vc[tot].push_back(u);
			u = v[u];
		}
	}
	for (int i = 1; i <= tot; i++) {
		int m = (int)vc[i].size();
		int x, y;
		exgcd(k, m, x, y);
		x = (x%m + m) % m;
		for (int j = 0; j < m; j++) {
			ans[vc[i][(j + x) % m]] = vc[i][j];
		}
	}
	for (int i = 1; i <= n; i++)printf("%d%s", ans[i], i == n ? "\n" : " ");
	return 0;
}

 

A - All with Pairs

 

题意：给定 n 个字符串，定义 f(s,t)f(s,t) 为最长的 s 串的前缀等于 t 串的后缀的长度。求 ∑i=1n∑j=1nf(si,sj)2(mod  998244353)\sum_{i=1}^n\sum_{j=1}^nf(s_i,s_j)^2(\mod 998244353)。

KMP+字符串hash

由于限定所有串的总长不超过 10610^6，而所有后缀，前缀的数量又是 O（n）的，所以可以枚举所有前后缀。然后去重。

对于一个公共前后缀aba，它的 nxt 一定也是公共前后缀，这就导致重复计算。所以要枚举所有前缀，从它们的nxt 中减去自己的，由于一定是长度越小的越会被重复，所以只要从小到大遍历减去。

首先枚举所有的后缀，并哈希后map计数。再枚举每一个字符串，枚举它的每一个前缀，判断有几个后缀等于这个前缀，再由于可能重复计算，包含这个串时一定包含它的nxt，所以从小到大枚举每一位，并从它的 nxt 的 cnt 中减去自己的 cnt，这样就得到了每个前缀对应的与它相同的后缀的个数。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 1e6 + 10;
int nxt[N];
void getNextVal(const string& p) {
	int n = p.length();
	nxt[0] = -1; nxt[1] = 0;
	for (int i = 2; i <= n; i++) {
		int j = nxt[i - 1];
		while (j != -1 && p[i - 1] != p[j]) j = nxt[j];
		nxt[i] = j + 1;
	}
}
int n;
vector<ll>pre[N], suf[N];
map<ll, ll>mp;
ll p[N], cnt[N];
string s[N];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	p[0] = 1ll;
	for (int i = 1; i < N; i++)p[i] = p[i - 1] * 233;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		ll tmp = 0;
		int m = s[i].length();
		for (int j = 0; j < m; j++) {
			tmp = (tmp * 233 + s[i][j] - 'a' + 1);
			pre[i].push_back(tmp);
		}
		tmp = 0;
		for (int j = m - 1; j >= 0; j--) {
			tmp = tmp + (s[i][j] - 'a' + 1)*p[m - j - 1];
			suf[i].push_back(tmp);
			mp[tmp]++;
		}
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		getNextVal(s[i]);
		int  m = s[i].length();
		for (int j = 0; j < m; j++)cnt[j] = mp[pre[i][j]];
		for (int j = 2; j <= m; j++) {
			if (nxt[j] >= 1)cnt[nxt[j] - 1] -= cnt[j - 1];
		}
		for (int j = 0; j < m; j++) {
			ans = (ans + cnt[j] * (j + 1) % mod*(j + 1) % mod) % mod;
		}
	}
	cout << ans << endl;
	return 0;
}