水题

调一万年，第一次就差三个地方

1. 忘记了for work()

2. assert()里面忘记双等号，写了个单个等号…

3. LCA 写错了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int r(int i,int j){
  if(d[i] > d[j])swap(i,j);
  per(off,0,20){
    if(d[j]-d[i] >= (1<<off) ){
      j=f[j][off];
    }
  }
  if(i == j)return i;
  per(off,0,20){ // <---------------------------- 写成 per(off,1,20) 了
    if(f[i][off] != f[j][off]){
      i=f[i][off];
      j=f[j][off];
    }
  }
  return f[i][0];
}

不过

感觉LCA写得比原来熟很多了

题目

http://codeforces.com/contest/1326/problem/D2

字符串s 去掉其中连续一段，使得剩余的部分构成回文，求最长的方案

范围

|s| <= 10^6

题解

这个题有两个版本，easy的版本|s|<=5000

对于那个版本，先建立r[i][j]表示s[i..j]是否是回文 空间和时间都是O(n^2)

然后枚举 首尾的 长度，和中间循环节的长度,时间复杂度O(n^2)

对于hard版本(当前版本)这样做显然会超时。

竟然是贪心。。。

果然单调性质

假设前后缀最长的对称部分为k，则有两种情况

[0...k][回文].....[k...0]

[0...k].....[回文][k...0]

如果有一个更优的方案(t<k),则它的样式为

[0..t][回文]....[t..0]

[0..t]....[回文][t..0]

因为对称关系，我们只讨论一种剩余回文在左侧的

[0..t][回文]...[t..0]

因为t<k

所以我们可以把回文部分左右减少1个，而把[0..t]变为[0..t+1],它依然是合法的

[0..t+1][回文去首尾]..[t+1..0]

这样新的合法的依然是长度不变

反复操作，最后能得到一个[0...k][回文].....[k...0]

所以任何更优方案能转换成[0...k][回文].....[k...0]

综上,实现变为 移除首位最长对称串，再在剩余的内容中找最长前缀回文或最长后缀回文

最后在中间的找前后缀回文用点kmp之类或者hash之类的就行了

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

#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);

// t = a+b
// t = s[pre] + s[suffix]
// len(t) <= len(s)
// ==>
//
// [preA][...]...[~preA]
// [preA]...[...][~preA]
//
//
// = s 移除连续一段 使得结果变成回文
// s[....]
// ~s[....]

// dp[i][j] [0/1/2][0/1/2]
// n^2 ?
//
// s[...i[ ]i...]
// = max(2*i+ [i+1...]回文 ])
// = max(2*i+ [ ...[...?]回文] )


char s[1'000'010];

char t1[1'000'010];
char t2[1'000'010];
int pre[1'000'010];

int r(char * ch,int sz){
  pre[0] = -1;
  rep(i,1,sz){
    int pos = i-1;
    while(true){
      pos = pre[pos];
      if(ch[pos+1] == ch[i]){
        pre[i] = pos+1;
        break;
      }
      if(pos == -1){
        pre[i] = -1;
        break;
      }
    }
  }
  // rep(i,0,sz){
  //   printf("%d ",pre[i]);
  // }

  int lastans = -1;
  per(i,0,sz){
    // [[0..lastans]..i[..0]...]
    while(true){
      if(ch[i] == ch[lastans+1]){
        if(lastans + 2 >= i){
          return lastans*2+3+ (i!=lastans+1);
        }
        lastans++;
        break;
      }
      if(lastans == -1){
        break;
      }
      lastans = pre[lastans];
    }
  }
  return 0;
}

int main(){
  int t;
  cin>>t;
  while(t--){
    scanf("%s",s);
    int n = strlen(s);
    int k = -1;
    rep(i,0,n){
      if(i<n-1-i){
        if(s[i]==s[n-i-1]){
          k = i;
        }else{
          break;
        }
      }
    }

    rep(i,k+1,n-k-1){
      t1[i-k-1]=s[i];
    }
    int len1 = r(t1,n-2-2*k);
    rep(i,k+1,n-k-1){
      t2[n-k-2-i]=s[i];
    }
    int len2 = r(t2,n-2-2*k);
    // cout<<"?"<<len1<<endl;
    // cout<<"!"<<len2<<endl;
    rep(i,0,k+1){
      printf("%c",s[i]);
    }
    if(len1 > len2){
      rep(i,0,len1){
        printf("%c",t1[i]);
      }
    }else{
      rep(i,0,len2){
        printf("%c",t2[i]);
      }
    }
    rep(i,n-k-1,n){
      printf("%c",s[i]);
    }
    printf("\n");
  }
  return 0;
}

参考

官方题解 http://codeforces.com/blog/entry/74961

总结

估计还是估计到了 O(n)或者O(nlog n)范围的算法，但赛内没有推出更优的性质

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