牛客多校第一场

发表于 阅读次数： Changyan：

多校牛客第一场&杭电第一场

牛客

I.Chiitoitsu

题解

首先第一步我们应该要想到一个贪心策略，那就是一定是还原原来在手上的那副牌。因为交换手中没有成双的单牌一定会使得期望大。

因此倒着写一个期望DP即可，期望DP表示dp[i][j]牌堆还剩i张牌手上有j个对子的摸到7个对子的期望步数。

$dp[i][j]=\frac{(13-2j)\cdot 3}{i}d[i+1][j+1]+\frac{i-(13-2j)\cdot3}{i}dp[i+1][j+1]$

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
#define int LL
const int N=200010,M=N*2,mod=1e9+7;
int n,m,k,a[N],inv[N];
LL f[34*4+1][9];
string p;

void init(){
	inv[0]=1;
	for(int i=1;i<=34*4;++i)
		inv[i]=fpower(i,mod-2,mod);
    memset(f,-1,sizeof f);
    f[3][6]=1;
    for(int i=4;i<=123;++i){
        for(int j=0;j<=5;++j){
            if((7-j)*3>i) continue;
            int p=(13-2ll*j)*3ll*inv[i]%mod;
            f[i][j]=0;
            if(f[i-1][j+1]!=-1){
                f[i][j]+=(f[i-1][j+1]+1)*p%mod;
                f[i][j]%=mod;
            }
            if(f[i-1][j]!=-1){
                f[i][j]+=(f[i-1][j]+1)*(1-p+mod)%mod;
                f[i][j]%=mod;
            }
        }
        f[i][6]=3*inv[i]%mod;
        if(f[i-1][6]!=-1){
            f[i][6]+=(f[i-1][6]+1)*((1-3*inv[i])%mod+mod)%mod;
            f[i][6]%=mod;
        }
    }
}

void solve(int Case) {
    cout << "Case #" << Case << ": ";
    cin >> p;
    map<string, int> mp;
    for (int i = 0; i < p.size(); i += 2) {
        string q = p.substr(i, 2);
        mp[q]++;
    }
    int c1 = 0, c2 = 0;
    for (auto u : mp) {
        if (u.y == 1) c1++;
        else   c2++;
    } 
    cout << f[123][c2] << '\n';
}

E. LTCS

首先给出了一个定义：一颗有根树Ta是Tb的子序列当且仅当存在单身F()使得$u \in T_a$ 有 $F(u) \in T_b$且$u$和$F(u)$在两棵树内分别保持同祖同子孙的关系。

题解

然后我们定义DP状态：

f[u][v][1]表示分别以u和v为根节点的两棵树的最长公共子序列的大小，且公共子序列中包含了u和v点有t1[u]=t2[v]

f[u][v][0]表示了涵盖了第一种情况下的，即以u为根和以v为根的最大公共子序列。

有转移f[u][v][0]=max{f[u1][v1][1]}，其中$u1 \in {son_of_u_and_u}$，$v1 \in {son_of_v_and_v}$

对于f[u][v][1]的处理我们可以发现相当于在t1[u]==t2[v]的条件下做一个二分图最优匹配：

$T_a$中的某个点可以映射向$T_b$中的某些点，每两个点对之间都有一定的权值，表示匹配之后的最大公共节点个数。要求求整个的最大公共个数。

因此我们对于每一层的节点直接用KM进行转移就行了。

复杂度分析

我枚举两个节点是$O(n^2)$的，然后在枚举的时候可以顺便把图给建出来，KM复杂度是$O(n^3)$,但是总的时间复杂度并不是$O(n^5)$,因为每次做KM的时候实际上并不是对n个点做，KM实际上可以在上一次的基础上进行增广，每次增广较小的那一坨点，因此我们可以用一个类似于启发式的合并方式每次增广较小的子树。

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
// #define int LL
const int N=510,M=N*2,mod=1e9+7;
int n,m,k,a[N];
int f[N][N][2];  //f[i][j][0/1] 第一棵树以i为根第二棵树以j为根u和v不/一定匹配的答案
int t1[N],t2[N]; //点权
bool vis[N][N];
vector<int> edge1[N],edge2[N];
vector<int> son1,son2; //每次小的往大的合并
#define INF 1e8

int match[N], pre[N];
LL mp[N][N], ex[N], ey[N], slack[N]; 
bool st[N];

//KM板子=======================
void check(int u);  LL KM();//=
//=============================

void dfs(int u,int fa1,int v,int fa2){
	if(vis[u][v]) return ; 
	for(auto u1:edge1[u]) if(u1!=fa1) 
		for(auto v1:edge2[v]) if(v1!=fa2) 
            if(!vis[u1][v1]) 
				dfs(u1, u, v1, v);
    
	for(auto u1:edge1[u]) if(u1!=fa1&&!vis[u1][v]) dfs(u1, u, v, fa2);
	for(auto v1:edge2[v]) if(v1!=fa2&&!vis[u][v1]) dfs(u, fa1, v1, v);
	
	son1.clear();
	for(auto u1:edge1[u])
		if(u1!=fa1)
			son1.push_back(u1),f[u][v][0]=max(f[u][v][0], f[u1][v][0]);
	son2.clear();
	for(auto v1:edge2[v])
		if(v1!=fa2)
			son2.push_back(v1),f[u][v][0]=max(f[u][v][0], f[u][v1][0]);
	
	bool flag=0;
	if(son1.size()>son2.size()) son1.swap(son2),flag=1;
	for(auto u1:edge1[u]) if(u1!=fa1)
		for(auto v1:edge2[v]) if(v1!=fa2) 
			flag?mp[v1][u1]=f[u1][v1][0]:mp[u1][v1]=f[u1][v1][0];

	
	vis[u][v]=1;
	f[u][v][1]=t1[u]==t2[v]?KM()+1:0;
	f[u][v][0]=max(f[u][v][0], f[u][v][1]); //不一定匹配包含了匹配
	//清空这一层的
	for(auto u1:edge1[u]) if(u1!=fa1)
		for(auto v1:edge2[v]) if(u1!=fa2)
			flag?mp[v1][u1]=0:mp[u1][v1]=0;		
}

void solve(){
	n=read(),m=read();
	rep(i,1,n) t1[i]=read(); rep(i,1,m) t2[i]=read();
	rep(i,1,n-1){
		int u=read(),v=read();
		edge1[u].push_back(v),edge1[v].push_back(u);
	}
	rep(i,1,m-1){
		int u=read(),v=read();
		edge2[u].push_back(v),edge2[v].push_back(u);
	}
	dfs(1, 0, 1, 0);  //记忆化
	print(f[1][1][0]); 
}
//=================================
signed main(){
    solve();
    return 0;
}

void check(int u){
	LL x, y = 0, yy = 0, delta;
	pre[0] = 0;
    for(auto i: son2) pre[i] = 0;
    for(auto i: son2) slack[i] = INF;
    match[y] = u;
    while(1){	
        x = match[y], delta = INF, st[y] = 1;
        for(auto i: son2){	
            if(st[i])continue;
            if(slack[i] > ex[x] + ey[i] - mp[x][i]){	
                slack[i] = ex[x] + ey[i] - mp[x][i];
                pre[i] = y;
            }
            if(slack[i] < delta) {delta = slack[i];yy = i;}
        }if(st[0]) ex[match[0]] -= delta, ey[0] += delta;
            else slack[0] -= delta;
        for(auto i: son2){	
            if(st[i]) ex[match[i]] -= delta, ey[i] += delta;
            else slack[i] -= delta;
        }
        y = yy;
        if(match[y]==-1)break;
    }
    while(y){match[y] = match[pre[y]];y = pre[y];}
}

LL KM()
{	
	for(auto i: son2) match[i] = -1;
	match[0] = -1;
    for(auto i: son1) ex[i] = ey[i] = 0;
    for(auto i: son2) ex[i] = ey[i] = 0;
    ex[0] = ey[0] = 0;
    for(auto i: son1){
		st[0] = 0;	
        for(auto j: son2) st[j] = 0;
        check(i);
    }
    LL res = 0;
    for(auto i: son2)
        if(match[i] != -1) res += mp[match[i]][i];
    return res;
}