E

https://codeforces.com/contest/1303/problem/E

T组测试

t和s是字符串

s中能否找两个不共用下标的子序列(不要求连续),t=concat(s1,s2)

范围

T<=100

|s|,|t| <= 400

提解

枚举t的分割位置

dfs(s中当前匹配位置i,t前段匹配位置j,t后半匹配位置k)

很明显超时。

注意到上面dfs仅返回true/false

也就是dfs(i,j,k)=1/0这种

可以改为(也有贪心关系),dp[i][j]=最多匹配的k

总结

dfs(i,j,k)=1/0可以考虑 dp[i][j]=max/min(k)

题目

https://codeforces.com/contest/1292/problem/C

2300评分

大意

给树的形状,你需要把0到n-2分别填在边上。

求 sum{mex{所有简单边}}的最大期望值

数据范围

节点数小于3000

3s

512MB

题解

官方题解

感觉对mex的题始终不会

$S = \sum_{1 \leq u < v \leq n} mex(u, v) = \sum_{1 \leq x \leq n} \left( \sum_{mex(u, v) = x} mex(u,v) \right) = \sum_{1 \leq x \leq n} \left( \sum_{mex(u, v) = x} x \right) = \sum_{1 \leq x \leq n} \left( \sum_{mex(u, v) \geq x} 1 \right) = \sum_{1 \leq x \leq n} f(x)$

直接解读这个公式。

第一个等式是定义

第二个第三个等式是按照mex的值进行拆分,

第四个等式的转换是 $x = \sum_{1\leq y \leq x} 1$,也就是原来在x时增加 $sum mex$ 倍 $x$,改为 从1 到x,各增加 sum mex倍 1

最后一个等式是定义 f(x)函数

$f(x) = count(mex(u,v) \ge x) =$ 包含 [0 ->x-1]的简单路径数量


证明叶子到叶子包含0到len-1

考虑一个树的形成过程如果是从0到n-2的放置,如果当前0到x-1已经固定,准备放x,那么只有把它放在0到x-1所有都在的路径上(如果可能),才能产生更大的mex,如果不这样,那么x以及所有大于x的最后的mex都已经固定。

因此放置时如果能够放到0到x-1的路径上,则一定是放在路径上。

也就意为这 一定有一条从叶子到叶子的简单路径 放了 0到length-1, 并且剩余的无论怎么放(因为已经叶子到叶子,不可能再集齐0到i了,mex也就不会变了) 对结果都没有影响


证明这条路径上赋值山谷形状

现在假设固定了简单路径的位置,下面要证明最优值的放置 是山谷形状,也就是 a1>a2>…>ap<…<al−1<al.

假设,[0->x-1]是连续的一段,x和这一段不连续 不妨设x在这一段的右侧(否则就左侧)

? ? ? ? [0到x-1连续的一段] vali ? ? ? ? ? x ? ? ? ?

我们交换 vali和x的位置

显然,对于f(0->x-1)不会变 因为 连续段的位置没有改动,也就是包含[0->x-1]的简单路径数量不变

对于f(x)变大,因为包含[0->x]的 简单路径数量 = 连续段左侧分支数量 * x右侧分支数量,乘法第一个值不变,第二个值变大,总的值一定变大

对于f(>x) 不减, 对于左侧点位置不变,对于右侧点不变或者有更进的右侧点,所以包含[0->(>x)]的 简单路径数量 = 连续段左侧分支数量 * x右侧分支数量,乘法第一个值不变,第二个值不减,总的值一定不减

总的来说,如果不满足上述状态,则一定有一个更优的摆放方法。综上,一定是山谷形


然后就有了dp[u][v] = $\sum_{1 \leq x \leq l} f(x)$的最大值,且u到v 填写的是0到l-1

定义(方便描述)

par(r,u): 以r为树的根节点,u的父节点

sub(r,u), 以r为树的根节点,u的子树的节点个数

官方题解的解释图

官方题解解释图


计算dp[u][v],根据我们的山谷原理,和dp的定义,dp[u][v]的最大值一定在两端的某一端

所以 剩余的部分为dp[u][par(u,v)] 或者 dp[par(v,u)][v],又dp只关心f(<=l),所以剩余只有f(l)要计算

这显然 f(l) = sub(u,v) * sub(v,u)

$dp[u][v] = sub(u, v) \times sub(v, u) + \max(dp[par(v, u)][v], dp[u][par(u, v)])$

一个点的所有分支子节点 直接dfs,对于父方向的= 总量-1-子分支即可,也就是每个点各个分支子节点数O(n)计算完,要计算一个具体sub时可以O(1)计算

对于par,我们可以把dp改为递推即可,

代码

TLE14

去掉map WA17

int 改 long long Accept

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

typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
const double pi = acos(-1.0);

// 树,边被赋值[0,n-2]
// 输入n 3000
// 树状

int n;
vector<int>p2[3010];

map<int,int>chcnt[3010];// child cnt [idx][p2] = childcnt

vector<pair<int,int> > cur; // [u<v] = [par,par,sum]
tuple<int,int,ll>cost[3010][3010]; // [u<v] = [par,par,sum]

int initchcnt(int idx,int fa){
int cnt = 1;
for(auto item:p2[idx]){
if(item == fa)continue;
cnt+= (chcnt[idx][item] = initchcnt(item,idx));
}
if(fa){
chcnt[idx][fa] = n - cnt;
}
return cnt;
}

ll cnt(int u,int paru){
return n-chcnt[u][paru];
}
ll ans = 0;

// u pvu .... puv v
void addrel(int u,int v,int pvu,int puv,ll count){
if(u > v){
swap(u,v);
swap(pvu,puv);
}
ll newcount = count + cnt(u,pvu)*cnt(v,puv);
ans=max(ans,newcount);
if(get<2>(cost[u][v])==0){
cur.pb({u,v});
}
if(get<2>(cost[u][v]) < newcount ){
cost[u][v] = {pvu,puv,newcount};
}
}

int main(){
cin>>n;
rep(i,0,n-1){
int u,v;
scanf("%d %d",&u,&v);
p2[u].pb(v);
p2[v].pb(u);
}
initchcnt(1,0);
// 减少重复运算u<v
// 按照length递增 广搜
rep(i,1,n+1){
for(auto item:p2[i]){
if(item < i)continue;
addrel(i,item,item,i,0);
}
}
rep(i,0,cur.size()){
auto [u,v] = cur[i];
auto [pvu,puv,count] = cost[u][v];
// u pvu .... puv v
// 扩展u
for(auto nu:p2[u]){
if(nu == pvu)continue;
addrel(nu,v,u,puv,count);
}
// 扩展v
for(auto nv:p2[v]){
if(nv == puv)continue;
addrel(u,nv,pvu,v,count);
}
}
printf("%lld\n",ans);

return 0;
}

总结

看到max,min有可能去考虑贪心或者说局部最优,比如这里的 山谷形状

mex是真的自闭

n看到了3000就算想到了n方dp,没想到上面这些证明也没卵用

入门题目(Bash Game)

有一堆物品,两人轮流取,每次只能$[1,a]$个,最后取空的赢/输,求对策

假设你的对手取$x$个,有$1\le x \le a$,也就有$1 \le a+1-x \le a$,保证不论对手怎么取$x$,只要你取对应的$a+1-x$个就能保证剩余的个数 对$a+1$ 取模不变

控制到了不变量(对$a+1$取模不变)也就找到了解题的关键

NIM(Nim Game)

NIM 1

现在是两堆石头(可能相同个数,可能不同),每轮任选一堆,从该堆取任意正数个,最后取空的人赢/输

如果两堆相等,则对方任意取多少,你取相同的,总能维持一个不变两堆的差值为0

NIM 2

变为n堆石头(每堆数量独立),取法和上题一致,最后取空的人赢/输

假设有偶数堆,且成对的相等,那么用上题的结论,然而,这里我们发现,上题无论初始状态如何,我们都能通过0步或者1步达到我们的平衡的状态/不变的状态,而这里如果假设是偶数堆和成对的相等,这样的状态并不是任意可达的。

对于数据小,又想不到“数学”方法去找平衡态,可以用递归搜索去做,不过不是本文要讲的内容。

然后是枚举,发现并不是只有上面的状态是必胜/必败

例如有石堆$1 2 3$,也是能做到最后取空的控制,说明 偶数堆且成对相等 和 必胜必败没 不全等只有被包含关系。

先直接上结论

所有石头堆的异或值为$0$,显然如果当前为$0$,那么任意操作会使异或值变成非0

假设异或值为$k \neq 0$,从数量为$a$的堆中取走,最后剩下$b$个,

那么取走的个数为$a-b \ge 0$,$k \oplus a \oplus b = 0$(原来的异或 去掉a 新增b)

所以$b = a \oplus k$也就是要证明存在a使得$a \ge a \oplus k$

$k$是所有数量的异或结果,所以$k$的最高位$1$一定存在于某个$v[i]$中

$v[i]$ 和 $v[i]\oplus k$在高于$k$的最高位的位,值是相等的,在$k$的最高位$v[i]$为1,而$v[i]\oplus k$为$0$,所以存在$a = v[i]$使得$a \ge a \oplus k$,所以任意异或非$0$的$k$可以一步操作转化为$0$。

综上任意状态,能够通过0步或者1步转化为异或和为0。并且异或和为0是一个可以交替进行并被控制的平衡态。

至于为什么是想到异或和,我说不出,这个结论我也是从其它地方拿来,只会证明。

反过来再看NIM 1,会发现,虽然说是控制值相等,同时也就是控制异或和相等。

SG 函数

有向无环图上

$ \operatorname{mex}(S)=\min(\{x\}) \quad (x \notin S, x \in N) $

$\operatorname{mex}(S) = $集合$S$中不包含的最小非负整数

$ \operatorname{SG}(x)=\operatorname{mex}( \{ \operatorname{SG}(y) | y是x的后继 \} ) $

边界也就是没有出度的点,$\operatorname{SG}(\emptyset)=0$

显然如果$SG(x) = 0$,那么它的所有后继$\ne 0$,如果$SG(x) \ne 0$, 那么一定存在一个后继$SG(y) = 0$

换句话说$SG(x) = 0$的任意操作走向一个$SG(y) \ne 0$ , 而$SG(x) \ne 0$ 你总可以找到一个操作$SG(y) = 0$

所以一定能控制$SG(x) = 0$ 的平衡态,也一定能通过0步,或1步达到这个平衡态。

所以如果我们用$SG(失败状态) = 0$, 然后状态之间加上有向边, 那么以此计算$SG$ 就可以知道每个状态是成功还是失败了

应用在NIM 2中

考虑单个石堆游戏

有 $SG(个数) = 个数$

于是$SG(state(c_1,c_2,c_3,\cdots)) = c_1 \oplus c_2 \oplus c_3 \oplus \cdots= SG(c_1) \oplus SG(c_2) \oplus SG(c_3) \oplus \cdots$

对于多个游戏的组合(n个有向图)

结论, 一个游戏的$SG$函数值等于各个游戏的$SG$函数值的$Nim$ 和(异或和)

$\operatorname{SG}(s_1) \oplus \operatorname{SG}(s_2) \oplus \ldots \oplus \operatorname{SG}(s_n)$

同上面证明NIM 2的过程,假设所有异或和为$k$ (总状态),我们能得到

存在至少一个$i$满足$SG(s_i) > SG(s_i)\oplus k$,对于第$i$个游戏,$SG(s_i)\oplus k$是$SG(s_i)$ 的后继状态

因为注意到$SG$ 是通过$\operatorname{mex}$定义的意味着, 如果$SG(x) = w$, 那么 它一步是可以走到$0..w-1$的任意$SG$状态的, 这就是NIM二中的一堆里面任意取个数的意义一样

所以 $SG(state(s_1,s_2,s_3, \cdots)) = SG(s_1)\oplus SG(s_2)\oplus SG(s_3)\oplus \cdots $

参考

game theory

Sprague–Grundy_theorem

E

原题链接

2500评分

大意

平面上n个点,不存在3个共线,

对于所有(点p,另外四个点),如果另外四个点能包围点p则计数+1,对于同样的p和选中的4个点,不论有几种方式,只要能包围就计数+1

求p依次取遍所有点的计数和

范围

5<=n<=2500,

3s

1024MB

官方题解

https://codeforces.com/blog/entry/72804

题解

计算几何我就开始自闭了

最终要求的为sum{是否包围(p,另外四个点)},反向问题为

sum{是否不包围(p,另外四个点)}

考虑选取总方案为

$n*C_{n-1}^4$

如果选取的4个点,对于点p在同一个半圆内,那么选取的4个点无法包围,如果不在同一个半圆内则能包围

如果选取的4个点在同一个半圆内,则它们以p为顶点,构成的夹角小于180度,则这个夹角上存在顺时针的起始和结束点

假设选取点p和起始点q1,那么剩余三个点q2,q3,q4,与p和q1构成的夹角应该在0 到180度之间(且保证方向,也就是-0到-180度是不可取的)

这样对于每一个不包围的4个点,能做到不重不漏的计算

O(p枚举 * 计算几何排序和遍历)

然后 计算几何和浮点数和test9杀我,我浮点数+计算几何 就是过不了,然后换成纯整数处理过了,自闭

代码

accept

68473398 Wrong answer on test 9

68473313 Wrong answer on test 9

68473215 Runtime error on test 9

68473189 Runtime error on test 9

68473103 Runtime error on test 9

68473021 Runtime error on test 9

68471693 Runtime error on test 9

68471651 Runtime error on test 9

68471600 Wrong answer on test 9

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

typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
const long double pi = acos(-1.0);

pair<ll,ll>xy[3010];
pair<ll,ll>xysort[3010];
int n;

template<class T1, class T2>
inline const pair<T1, T2> operator-(const pair<T1, T2>&p1, const pair<T1, T2>&p2) {
return {
p1.first - p2.first,
p1.second - p2.second
};
}

ll cross(pair<ll,ll> vec1,pair<ll,ll> vec2){
auto [x1,y1] = vec1;
auto [x2,y2] = vec2;
return x1*y2-x2*y1;
}

int main() {
ll n;
scanf("%lld",&n);
rep(i,0,n){
ll x,y;
scanf("%lld %lld",&x,&y);
xy[i] = {x,y};
}
ll res = n * ((n-1) * (n-2) * (n-3) * (n-4) / (1*2*3*4));
rep(i,0,n){
rep(j,0,n){
if(i == j)continue;
xysort[j>i?j-1:j] = xy[j];
}
sort(xysort+1,xysort+n-1,
[i](const pair<ll,ll>p0,const pair<ll,ll>p1) -> bool{
ll cross0 = cross(p0-xy[i],xysort[0]-xy[i]);
ll cross1 = cross(p1-xy[i],xysort[0]-xy[i]);
if(cross0 >=0 && cross1 < 0){
return true;
}else if(cross0 < 0 && cross1 >= 0){
return false;
}
ll cross01=cross(p0-xy[i],p1-xy[i]);
return cross01 <= 0;
});
int index = 1;
// 四个点的起始点,首尾游标
rep(j,0,n-1){
while(index < j + n-1){
ll crossij = cross(xysort[index%(n-1)]-xy[i],xysort[j]-xy[i]);
if(crossij >= 0 ){
index++;
}else{
break;
}
}
// C_cnt^3
ll cnt = index - j - 1;
res -= (cnt * (cnt - 1) * (cnt - 2)) / (1*2*3);
}
}
printf("%lld\n",res);
return 0;
}

总结

1是想到反向计算,我一直在想算三角形然后带其它点,再容斥,就没想出来

2是浮点数精度,哎自闭,还是整数香

F

原题链接

2600评分

大意

0/1构成的字符串, 如果s[l,r]长度为len,其中1的个数为n(n>0)len%n == 0,那么这个子字符串为awesome

awesome子字符串的个数

范围

原字符串长度[1,200'000]

官方题解

https://codeforces.com/blog/entry/72611

题解

首先 想到的就是前缀和+暴力

预处理O(n),计算每个[l->r],只需要O(1)

总的时间代价O(n^2)

显然过不了,然后我赛内想来想去没想到方法了


pref表示前缀和

如果 $r - l + 1 = k \cdot (pref[r] - pref[l - 1])$,那么就是awesome的

变形 $r - k \cdot pref[r] = l - 1 - k \cdot pref[l - 1]$

所以对于k=1->n,计算上面成立有多少对

假设取一个给定的值T

对于 k>T, $r - k \cdot pref[r] = l - 1 - k \cdot pref[l - 1]$ , 也就是这类成立的子字符串包含1的个数比较少,我们遍历 前缀,然后找比它1个数大的值小于等于n/T的,对于所有k>T,总时间代价为O(n * n/T)

对于 k<=T , $-nT \le i - k \cdot pref[i] \le n$ , 对于给定k,遍历O(n) ,总时间代价O(nT)

所以理论上 T=sqrt(n)时,总的时间代价为O(n^(3/2))

代码

这里T取的死值300,没有取sqrt

6224 ms

我自闭了这个TLE11: https://codeforces.com/contest/1270/submission/68136316

然后这个过了: https://codeforces.com/contest/1270/submission/68136440

点compare就换了一下map的位置

另外 我把T设置为450(sqrt(200'000)=447.21359549995793)也TLE11: https://codeforces.com/contest/1270/submission/68136641

这个慢的是后一部分,原因基本就是(map/unordered_map)的代价,优化方案 例如有 数组+pair,最后 sort一下统计(没写)

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

typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
const double pi = acos(-1.0);

// len % (num of 1) == 0

// fft?

// 10010010
// n/1 has only 1
// n-1 has only 2 of 1

// kmp?

char s[200010]; // 0->n-1

int onecnt = 0;
int onepos[200010]; // 0->n-1
unordered_map<int,int> v2cnt;

int n;
int main(){
scanf("%s",s);
n = strlen(s);
rep(i,0,n){
if(s[i]=='1'){
onepos[onecnt++]=i;
}
}
int T = 300;
if(onecnt == 0){
printf("0\n");
return 0;
}
ll ans = 0;
int stj = 0;

// ans ==15612){ // n =1000
//
// k>T -> precnt <= n/T
rep(i,0,n){
int cnt = 0;
rep(j,stj,onecnt){
cnt++;
if(!(cnt<=n/T))break; // 注意 这个是上界,不是精确范围,
// 0-index
// i 010 pos 01100 posnext
// [i -> [pos -> posnext-1] ]
int pos = onepos[j];
int posnext = 0;
if(j == onecnt -1){
posnext = n;
}else{
posnext = onepos[j+1];
}
// [lenst+1->lenend] = lenend/cnt-lenst/cnt
int lenst = pos-i;
int lenend = posnext-i;
// printf("%d,[%d,%d]=%d , len:[%d->%d] \n",i,pos,posnext,cnt,lenst,lenend);
if( (lenend/cnt) >= T){ // 精确的范围
ans+=(lenend/cnt)- max((lenst/cnt),T);
}
// printf("ans=%lld\n",ans);
}

if(stj < onecnt && onepos[stj] <= i){
stj++;
}
}
// cout<<" ans="<<ans<<endl;
// k<=T, k=1->T,i=0->n
rep(k,1,min(T,n)+1){
v2cnt.clear();
// i - k * pre[i];
v2cnt[0]++;
ll cnt = 0;
rep(i,0,n){
cnt+=(s[i] == '1');
v2cnt[i+1-k*cnt]++;
}
for(auto item:v2cnt){
ll c = item.second;
ans+=c*(c-1)/2;
// if(c>1){
// printf("k=%d: [%lld,%lld]\n",k,v,c);
// }
}
}
// ans
printf("%lld\n",ans);
return 0;
}

总结

这种分块 首先要看出是分块

然后分块除了实现和算法本身,一个需要注意的就是划分边界的处理,做到不重不漏,不要把理论最大最小上下界当成精确边界,另外因为实现是分块,所以理论上改变划分界限,代码应该有相同输出,可以作为测试方法。

0%