首页 Tests

预期: 100 + 100 + 100 + 60 = 360
实际: 100 + 50 + 100 + 60 + 310
最高: 100 + 100 + 100 + 60 = 360

挂分挂在了 cout 上 /sad

T1 考场上 1min 就猜到了结论，没开 ll 吃了 1min 罚时，于 9min AC

如果是正式比赛可能会花个 20 分钟打个表验证一下

T2 大概知道了答案的上界，构造的下一步就是找到上界何时取到了，然后被摆王秒切了

T3 开始走进了 dp 的死胡同，总感觉如果二分 + 贪心就是傻逼题了… 事实证明的确是傻逼题。

T4 不会啊，一边摆一边写了 60 跑路

# Solutions

# a

考虑四个因数的话，11 和本身肯定算两个，然后你上两个与 11 相差 nn 以上的素数。

大胆猜想这是对的，打表验证发现确实是对的。

# b

完全图每个点度数为 nn ，每消去一棵生成树至少也会在一个点上消去 22 的度数，于是猜想答案上界是 n2n\over 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
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &a){
	T w=1; a=0;
	char ch=getchar();
	for(;ch < '0' || ch > '9';ch=getchar()) if(ch == '-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) a=(a<<3)+(a<<1)+(ch^48);
	a*=w;
}
template <typename T> inline void ckmax(T &a, T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a, T b){a = a < b ? a : b;}
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mii map<int, int> 
#define pii pair<int, int> 
#define vi vector<int> 
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i) 
#define foR(i,l,r) for (int i = l; i >= r; --i)
const int N = 1e6 + 10;
pii Ans[N];
int id[N]; 
int cnt;
int l, r, n;
inline void solve () {
	int cur = 0;
	For (i, 1, n - 1) {
		if (i & 1) 
			Ans[++cnt] = mp(id[l - cur], id[l + cur + 1]);
		else {
			Ans[++cnt] = mp(id[l + cur + 1], id[l - cur - 1]),
			cur++;
		}
	}
}

int main() {
	int cases, cas = 0; read(cases);
	while (cases--) {
		read(n);
		int ret = n / 2;
		printf ("Case #%d: %d\n", ++cas, ret);
		cnt = 0;
		For (i, 1, n) id[i] = i;
		For (i, 1, n) id[i + n] = id[i];
		For (i, 1, n) id[i + 2 * n] = id[i];
		l = n + 1, r = 2 * n;
		For (i, 1, ret) {
			solve();
			l++, r++; 
		}
		For (i, 1, cnt) cout << Ans[i].fi << " " << Ans[i].se << endl;
	}
}

因为 cout ，我挂掉了 50pts

# c

二分一个答案，然后贪心即可

# d

考虑转换一步题意，使用一个 preipre_i 数组表示与第 ii 个位置相同的字符上一个出现的位置，那若两个子串拿出来 prepre 数组相等则表示这两个子串同构。

然后我们考虑到每次从前 / 后加入一个字符， 只有一个地方的 prepre 值会变化，又它要统计不同的子串数，于是我们可以想到利用 SA 统计本质不同子串的思想，从后往前每次加一个字符，记录每次的后缀 prepre ，然后后缀排序一下求出相邻 LCPLCP 从而得出答案。

然后考虑每次的后缀 prepre 咋求，主席树是 2log⁡2\log 的，考虑使用 YSH 超级可持久化数组可持久化块状数组，即正常的主席树是一个二叉树的结构新加一个点就共产共妻继承一连串的儿子关系，于是伟大的 YSH 就想到放在分块上，普通的分块相当于是一个 n\sqrt n 叉树，你可以类似的编出一个做法。

然后相邻的 LCPLCP 咋算，就用把后缀 prepre 在放在 hash 上，二分一个 LCPLCP 若 hash 值相同就挪个端点之类的

然后后缀数字咋比较大小，你就把 LCPLCP 后一位比较一下就好了

还是个挺有意思的题目

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
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &a){
	T w=1; a=0;
	char ch=getchar();
	for(;ch < '0' || ch > '9';ch=getchar()) if(ch == '-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) a=(a<<3)+(a<<1)+(ch^48);
	a*=w;
}
template <typename T> inline void ckmax(T &a, T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a, T b){a = a < b ? a : b;}
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mii map<int, int> 
#define pii pair<int, int> 
#define vi vector<int> 
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i) 
#define foR(i,l,r) for (int i = l; i >= r; --i)
#define ll long long
const int N = 5e4 + 10, Blo = 256, Base = 1e6 + 3, Mod = 1e9 + 7;//
int pw[N];
struct Block {
	int h[Blo + 10], v[Blo + 10];
	void upd (int x, int y) {
		v[x] = y;
		For (i, 1, Blo) h[i] = (1ll * h[i - 1] * Base + v[i]) % Mod;
	}
} c[N << 1];
int tot, n, m; 
struct CanStill {
	int id[Blo + 10], s[Blo + 10];
	void Init() {
		memset (id, 0, sizeof id);
		memset (s, 0, sizeof s);
	}
	void upd (int u, int y) {
		int p = (u - 1) / Blo + 1, x = u - (p - 1) * Blo;
		c[++tot] = c[id[p]];
		c[tot].upd(x, y), id[p] = tot;
		For (i, 1, Blo) s[i] = (1ll * s[i - 1] * pw[Blo] + c[id[i]].h[Blo]) % Mod;
	}
	int ask (int u) {
		int p = (u - 1) / Blo + 1, x = u - (p - 1) * Blo;
		return (1ll * s[p - 1] * pw[x] + c[id[p]].h[x]) % Mod;	
	} // Get the pre hash
	int get (int u) {
		if (u > n) return -1;
		int p = (u - 1) / Blo + 1, x = u - (p - 1) * Blo;
		return c[id[p]].v[x];
	}
} a[N];
int b[N];
int LCP (int x, int y) {
	if (x == y) return n - x + 1;
	if (x > y) swap(x, y);
	int l = 0, r = n - y + 1;
	while ( l < r ) {
		int mid = (l + r + 1) >> 1;
		if (a[x].ask(x + mid - 1) == a[y].ask(y + mid - 1))
			l = mid;
		else r = mid - 1;
	}
	return l;
}
int sa[N];
int las[N]; 
bool cmp (int x, int y) {
	int w = LCP(x, y);
	return a[x].get(x + w) < a[y].get(y + w); 
}

signed main() {
	while ( ~scanf ("%lld", &n) ) {
		pw[0] = 1, tot = 0;  
		ll Ans = 0;
		For (i, 1, n) {
			read(b[i]); 
			pw[i] = 1ll * pw[i - 1] * Base % Mod;
			las[i] = 0;
		}
		a[n + 1].Init();
		foR (i, n, 1) {
			Ans += i; 
			a[i] = a[i + 1], sa[i] = i;
			if (las[b[i]])
				a[i].upd(las[b[i]], las[b[i]] - i); 
			las[b[i]] = i;
		}
		sort (sa + 1, sa + n + 1, cmp);
		For (i, 1, n - 1) Ans -= LCP(sa[i], sa[i + 1]);
		printf ("%lld\n", Ans); 
	}
}