2022.10.1模拟赛

  FSYo Orz orz orz orz %%%%%

  国庆节限定模拟赛

A

100pts $O(n\log n)$

  二维偏序升级版，不等式变形一下，分 $4$ 种情况讨论：

1. $a_j=0$，那么 $a_i>0$，贡献就是所有大于 $0$ 的数的个数
2. $a_j=1$，那么 $a_i<a_i+1$，贡献就是前面所有数的个数
3. $a_j\ge 2$，那么 $a_i<\frac{a_j}{a_j-1}$，然后树状数组数数就可以了
4. $a_j<0$，那么 $a_i>\frac{a_j}{a_j-1}$，和上一种情况一样了

namespace gene {
	int c[MAXN << 2] = { 0 };
	inline int lowbit(int x) { return x & -x; }
	void add(int x, int val) { for(; x <= 2 * n; x += lowbit(x)) c[x] += val; }
	int query(int x) {
		int ans = 0;
		for(; x; x -= lowbit(x)) ans += c[x];
		return ans;
	}
	double ori[MAXN << 1], de[MAXN << 1];
	void solve() {
		int ans = 0;
		for(int i = 1; i <= n; i++)
			de[i] = ori[i] = a[i], de[i + n] = ori[i + n] = 1.0 * a[i] / (a[i] - 1);
		sort(de + 1, de + 2 * n + 1);
		int m = unique(de + 1, de + 2 * n + 1) - de - 1;
		double mx = de[m]; int dmx = lower_bound(de + 1, de + m + 1, mx) - de;
		for(int j = 1; j <= n; j++) {
			int dai = lower_bound(de + 1, de + m + 1, ori[j]) - de;
			int dfr = lower_bound(de + 1, de + m + 1, ori[j + n]) - de;
			if(a[j] == 0) {
				int dze = lower_bound(de + 1, de + m + 1, 0) - de; ans += query(dmx) - query(dze); }
			else if(a[j] == 1) ans += j - 1;
			else if(a[j] >= 2) ans += query(dfr - 1);
			else ans += query(dmx) - query(dfr);
			add(dai, 1); 
		}
		cout << ans << '\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

100pts $O(n)$

  把式子化简一下 $(a_i-1)(a_j-1)<1$，于是就变成了几种情况：

1. $a_j-1=0$，贡献前面的所有数
2. $a_j-1<0$，贡献前面所有满足 $a_i-1\ge 0$ 的数
3. $a_j-1>0$，贡献前面所有满足 $a_i-1\le 0$ 的数

  然后正这扫一遍就结束了。

B

10 pts

  直接暴搜，没什么好说的。

namespace sub1{
	int res = 0, m = 0;
	int pos[MAXN] = { 0 };
	int vis[MAXN] = { 0 };
	void de(){
		for(int i = 1; i <= n; i++) b[i] = ranges[i].l, b[i + n] = ranges[i].r;
		sort(b + 1, b + 2 * n + 1); m = unique(b + 1, b + 2 * n + 1) - b - 1;
	}
	int cal(){
		memset(c, 0, sizeof c);
		for(int i = 1; i <= n; i++){
			int dl = lower_bound(b + 1, b + m + 1, ranges[pos[i]].l) - b;
			int dr = lower_bound(b + 1, b + m + 1, ranges[pos[i]].r) - b;
//			printf("l = %d r = %d\n", dl, dr);
			for(int j = dl; j <= dr; j++) a[j] = i;
		} int ans = 0;
// 		for(int i = 1; i <= 2 * n; i++) cout << a[i] << ' '; puts("");
		for(int i = 1; i <= m; i++) if(!c[a[i]]) ans++, c[a[i]] = 1;
		return ans;
	}
	void dfs(int now){
		if(now == n + 1) { res = max(res, cal()); return; }
		for(int i = 1; i <= n; i++){
			if(vis[i]) continue;
			vis[i] = 1, pos[now] = i;
			dfs(now + 1);
			vis[i] = 0, pos[now] = 0;
		}
	}
	void solve(){
		de(); dfs(1);
		cout << res << '\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

30 pts

  可以退火（大概

  某机房大佬打的爬山，似乎比退火还更优一些，有一次爬了 $50pts$ 出来，但不是很理解为什么可以排山，难道是单峰的？

namespace sub2{
	#define ESP 1e-17
	const double T0 = 1e8, MAX_TIME = 1.95 * CLOCKS_PER_SEC, dT = 0.99244353;
	int res = 0, m = 0;
	int pos[MAXN] = { 0 };
	void de(){
		for(int i = 1; i <= n; i++) b[i] = ranges[i].l, b[i + n] = ranges[i].r;
		sort(b + 1, b + 2 * n + 1); m = unique(b + 1, b + 2 * n + 1) - b - 1;
	}
	int cal(){
		memset(c, 0, sizeof c);
		for(int i = 1; i <= n; i++){
			int dl = lower_bound(b + 1, b + m + 1, ranges[pos[i]].l) - b;
			int dr = lower_bound(b + 1, b + m + 1, ranges[pos[i]].r) - b;
//			printf("l = %d r = %d\n", dl, dr);
			for(int j = dl; j <= dr; j++) a[j] = i;
		} int ans = 0;
// 		for(int i = 1; i <= 2 * n; i++) cout << a[i] << ' '; puts("");
		for(int i = 1; i <= m; i++) if(!c[a[i]]) ans++, c[a[i]] = 1;
		return ans;
	}
	void SA(){
		srand(time(0) + clock());
		double T = T0; int nowans = res;
		while(T > ESP){
			int xx = rand() % n + 1, yy = rand() % n + 1;
			swap(pos[xx], pos[yy]);
			int temp = cal();
			if(temp > nowans) nowans = temp;
			else if(exp(1.0 * (temp - nowans) / T) * RAND_MAX < rand()) swap(pos[xx], pos[yy]);
			T *= dT;
		}
//		printf("nowans = %d\n", nowans);
		res = max(res, nowans);
	}
	void solve(){
		de();
		for(int i = 1; i <= n; i++) pos[i] = i;
		res = cal();
//		printf("res = %d\n", res);
		while(clock() < MAX_TIME) SA();
		cout << res << '\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

100 pts

  区间 $dp$，把区间段点离散化，显然不影响答案。然后记录 $f_{l,r}$ 为第 $l$ 个端点到第 $r$ 个端点的颜色最大值，然后就区间 $dp$ 传统艺能，枚举中间点 $k$，并且考虑 $[k,k+1]$ 涂上了某一个颜色，然后显然这样就必须满足 $\exists$ 区间 $[l_i,r_i]$ 使得 $l\le l_i\le k\le r_i\le r$，如果有这样的区间我们就可以这样转移：

$$f_{l,k}+f_{k+1,r}+1\to f_{l,r}$$

  那么现在考虑怎么做到这个限制条件，这个地方 $std$ 就做的很巧妙了，记录一个 $si{z}_{l,r}$ 表示 $[l,r]$ 里面有多少个被完全包含的区间，这个玩意儿也可以用区间 $dp$ 弄出来，也就是容斥一下：

$$si{z}_{l,r}\text{+=}si{z}_{l+1,r}+si{z}_{l,r-1}-si{z}_{l+1,r-1}$$

  然后对于一个 $k$，如果有 $si{z}_{l,k}+si{z}_{k+1,r}<si{z}_{l,r}$，那么就说明存在满足上述条件的区间，然后就是愉快的转移了。

namespace sub3DP{
	int m = 0;
	int s[MAXN][MAXN] = { 0 };
	int f[MAXN][MAXN] = { 0 };
	void de(){
		for(int i = 1; i <= n; i++) b[i] = ranges[i].l, b[i + n] = ranges[i].r;
		sort(b + 1, b + 2 * n + 1); m = unique(b + 1, b + 2 * n + 1) - b - 1;
	}
	void solve(){
		de();
		for(int i = 1; i <= n; i++){
			ranges[i].l = lower_bound(b + 1, b + m + 1, ranges[i].l) - b;
			ranges[i].r = lower_bound(b + 1, b + m + 1, ranges[i].r) - b;
			s[ranges[i].l][ranges[i].r]++;
		}
		for(int len = 1; len <= m; len++)
			for(int l = 1; len + l - 1 <= m; l++){
				int r = len + l - 1;
				s[l][r] += s[l + 1][r] + s[l][r - 1] - s[l + 1][r - 1];
			}
		for(int len = 1; len <= m; len++)
			for(int l = 1; len + l - 1 <= m; l++){
				int r = len + l - 1;
				for(int k = l; k < r; k++) if(s[l][k] + s[k + 1][r] < s[l][r])
					f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + 1);
			}
		cout << f[1][m] << '\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

C

  114514

10 pts

  字符串就是 $a+a+c+d+a+c$，所以显然可以枚举 $a$，枚举 $c$，枚举 $d$，然后再枚举所有子串，于是就有了一个 $O(n^6)$ 的神器算法：

namespace sub1{
	int cal(string num){                                                          // num = a + a + c + d + a + c  
		/* num : a : [0 ~ (len1 - 1)], 
	         a : [len1 ~ (2len1 - 1)],
	         c : [2len1 ~ (2len1 + len2 - 1)], 
			 d : [(2len1 + len2) ~ (2len1 + len2 + len3 - 1)], 
			 a : [(2len1 + len2 + len3) ~ (3len1 + len2 + len3 - 1)], 
			 c : [(3len1 + len2 + len3) ~ (3len1 + 2len2 + len3 - 1)]
		*/ 
		int n = num.size(), ans = 0;
		if(n < 6) return 0;
		for(int len1 = 1; len1 < n; len1++){                                      // 枚举 a 的长度 
	//		printf("len1 = %d\n", len1); 
			string a;
			for(int i = 0; i < len1; i++) a += num[i];
			for(int len2 = 1; 2 * len1 + len2 < n; len2++){                       // 枚举 c 的长度 
				string c;
				for(int i = 2 * len1; i < 2 * len1 + len2; i++) c += num[i];
				for(int len3 = 1; 2 * len1 + len2 + len3 < n; len3++){            // 枚举 d 的长度 
					string d;
					for(int i = 2 * len1 + len2; i < 2 * len1 + len2 + len3; i++) d += num[i];
					string pat = a + a + c + d + a + c; bool f = 1;
					for(int i = 0; i < n; i++) if(num[i] != pat[i]) f = 0;
					if(pat.size() != n) f = 0;
	//				cout << "  pat = " << pat << '\n';
	//				cout << "  a = " << a << '\n' << "  c = " << c << '\n' << "  d = " << d << '\n'; puts("");
					if(f) ans++;
				}
			}
		}
		return ans;
	}
	void solve(){
		int n = pp.size(), ans = 0;
		for(int i = 0; i < n; i++)
			for(int j = 0; j < i; j++){
				string temp;
				for(int k = j; k <= i; k++) temp += pp[k];
				ans += cal(temp);
			}
		cout << ans << '\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

60 pts

  就是在 $O(n^6)$ 的基础上优化了一下，就不枚举 $d$ 了，然后弄了一个 $hash$ 搞到了 $O(n^4)$，然后就有 $60pts$ 了。

namespace sub2{
	const int base = 13331;
	ull pw[MAXN] = { 0 };
	ull hs[MAXN] = { 0 };
	inline ull get(int l, int r) { return hs[r] - hs[l - 1] * pw[r - l + 1]; }
	inline bool equal(int s1, int s2, int l) { return get(s1, s1 + l - 1) == get(s2, s2 + l - 1); }
	inline bool check(int l, int r, int len1, int len2){
		if(!equal(l, l + len1, len1)) return false;
		if(!equal(l, r - len2 - len1 + 1, len1)) return false;
		if(!equal(l + 2 * len1, r - len2 + 1, len2)) return false;
		return true;
	}
	void solve(){
		int ans = 0; pw[0] = 1;
		for(int i = 1; i <= len; i++)
			hs[i] = hs[i - 1] * base + pp[i - 1], pw[i] = pw[i - 1] * base;
		for(int l = 1; l <= len; l++)
			for(int r = l; r <= len; r++){
				int mx1 = (r - l + 1) / 3;
				for(int len1 = 1; len1 <= mx1; len1++){                                 // 枚举 a 的长度 
					int mx2 = (r - l + 2 - 3 * len1) >> 1;
					for(int len2 = 1; len2 < mx2; len2++)                               // 枚举 c 的长度 
						if(check(l, r, len1, len2)) ans++;
				}
			}
		cout << ans << '\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

100 pts

  这里我们再考虑一下一些显然的性质，字符串写出来是形如这样的 $AACDAC$，我们可以发现，如果令 $T=ACDAC$，那么 $AC$ 就是 $T$ 的一个长度小于等于 $\frac{|T|-1}{2}$ 的 $\text{border}$，并且 $A$ 是一个长度小于 $\text{border}$ 长度的 $T$ 的前缀，还要满足前面能匹配上。

  于是我们考虑枚举一个子串 $T=S[i\sim j]$，然后在这个子串上做 $kmp$，变枚举边做，所以是 $O(n^2)$ 的。然后找到这个字符串的所有长度小于等于 $\frac{|T|-1}{2}$ 的 $\text{border}$，对答案的贡献就是：

$$\sum _{\text{border}\wedge \text{|border|}\le \frac{|T|-1}{2}}\sum _{|p|=1}^{|\text{border}|-1}[S[i-|p|\sim i-1]=S[i\sim |p|+i+1]]$$

  于是我们可以考虑在枚举 $i$ 且处理 $\text{next}$ 之前的时候就先枚举一下 $|p|$ 做一个前缀和 $su{m}_k$ 表示满足关于 $i$ 对称的长度小于等于 $k$ 的字符串的数量。然后再记一个 $f$ 数组表示 $\text{border}$ 的前缀，然后每次加上最长的满足条件的 $\text{border}$ 的 $f$ 就好了，总复杂度是 $O(n^2)$ 的。

namespace sub3{
	const int base = 13331;
	ull pw[MAXN] = { 0 };
	ull hs[MAXN] = { 0 };
	inline ull get(int l, int r) { return hs[r] - hs[l - 1] * pw[r - l + 1]; }
	inline bool equal(int s1, int s2, int l) { return get(s1, s1 + l - 1) == get(s2, s2 + l - 1); }
	int   f[MAXN] = { 0 };
	int nxt[MAXN] = { 0 };
	int sum[MAXN] = { 0 };                                                           // l 对称相等的数量的前缀和 
	void solve(){
		ll ans = 0; pw[0] = 1;
		for(int i = 1; i <= len; i++)
			hs[i] = hs[i - 1] * base + pp[i - 1], pw[i] = pw[i - 1] * base;
		for(int l = 1; l <= len; l++){                                               // 枚举第二个 A 的起始位置 
			sum[0] = nxt[1] = 0; int kb = 0, ks = 0;                                 // 跳 next 的时候的指针 
			for(int len1 = 1; len1 + l - 1 <= len; len1++){                          // 枚举 A 的长度 
				int sa = l - len1;                                                   // 第一个 A 的起点
				sum[len1] = sum[len1 - 1];
				if(sa > 0 and equal(sa, l, len1)) sum[len1]++; 
			}
			for(int r = l + 1; r <= len; r++){                                       // 枚举终止位置 
				int len2 = r - l + 1;                                                // 字符串长度 
				while(kb and pp[r - 1] != pp[l + kb - 1]) kb = nxt[kb];
				if(pp[r - 1] == pp[l + kb - 1]) kb++; nxt[len2] = kb;
				f[len2] = sum[len2 - 1] + f[nxt[len2]];
				while(ks and pp[r - 1] != pp[l + ks - 1]) ks = nxt[ks];
				if(pp[r - 1] == pp[l + ks - 1]) ks++;
				while(ks > (len2 - 1) / 2) ks = nxt[ks];
				if(ks > 1) ans += f[ks];
			}
		}
		cout << ans << '\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

D