Znzryb's Blog
0%

Posted on Edited on

思路讲解

状压dp最好都用0-based

这道题就是三进制状态压缩的板子题

之所以使用三进制，是因为2进制只能表示这个东西选没选，如这个经典的吃奶酪。

三进制可以表示这个城市来过一次or两次

AC代码

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
// https://vjudge.net/problem/HDU-3001
using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,m;
ll road[15][15];
ll dp[60000][12];	// 状态i以j收尾的最少费用
ll three[12];
ll digit[60000][12];	// 状态i的第j位数字是什么
const ll INF=99999999;

void init(){
	three[0]=1;
	for(int i=1;i<=10;++i)
		three[i]=three[i-1]*3;
	for(int i=0;i<three[10];++i){
		int temp=i;
		for(int j=0;j<10;++j){
			digit[i][j]=temp%3;
			temp/=3;
		}
	}
}

void init2(){
	memset(road, 0x3f, sizeof(road));
	memset(dp, 0x3f, sizeof(dp));
	for(int i=1;i<=n;++i)	// 自己到自己的距离为0
		road[i][i]=0;
	for(int i=0; i<n; i++)
		dp[three[i]][i]=0;	///dp的初始化，将起点都找出来
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	init();
	while(cin>>n>>m){
		init2();
		for(int i=1;i<=m;++i){
			ll a,b,c;
			cin>>a>>b>>c;
			road[a][b]=min(c,road[a][b]);
			road[b][a]=min(c,road[b][a]);
		}
		ll ans=INF;
		for(int i=1;i<three[n];++i){
			bool flag=true;
			for(int j=0;j<n;++j){	// 枚举i状态以j结尾
				if(!digit[i][j]){
					continue;
				}
				for(int k=0;k<n;++k){	
					// 枚举i状态是从k结尾状态转移到j结尾状态的
					if(!digit[i][k]){
						flag=false;
						continue;
					}
					dp[i][j]=min(dp[i-three[j]][k]+road[k+1][j+1],dp[i][j]);
				}
				if(flag)
					ans=min(ans,dp[i][j]);
			}
		}
		
//		for(int i=0;i<n;++i)
//			ans=min(ans,dp[three[n]-1][i]);
		cout<<(ans==INF ? -1:ans)<<endl;
	}
	return 0;
}
/*
AC https://vjudge.net/solution/57067144
2 1
1 2 100
3 2
1 2 40
2 3 50
3 3
1 2 3
1 3 4
2 3 10
c

*/

心路历程（WA，TLE，MLE……）

前面调了半天，以为是我的写法有问题，但其实是因为

dp[i][j]=min(dp[i-three[j]][k]+road[k+1][j+1],dp[i][j]);

写成了road[k-1][j-1]

路程匹配错误导致了这个问题

C语言也是的，这个index都超范围了也不给个提示，6。

Posted on Edited on

思路讲解

看这数据量，直接暴搜或者状态压缩好吧

看来一眼题解，说是状态压缩？这分数比那道并查集分还低

好吧，题解也是状压dp，那暴搜大抵凉凉。

说白了，思路就是一个先手的人输赢取决于把一对合法牌去掉的情况下他是赢还是输，要是是赢，那这种状态就输了，要是输，那么这种状态就赢了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for(int i=1;i<=(1<<n)-1;++i){
	if(popcnt(i)<=1)	// 只有一个牌自然是不可以的
		continue;
	for(int j=0;j<n;++j){
		if(!((i>>j)&1))
			continue;
		for(int k=j+1;k<n;++k){
			if(((i>>k)&1) && (A[j]==A[k] || B[j]==B[k])){
				dp[i]=1-dp[i-(1<<k)-(1<<j)];
				if(dp[i])
					break;
			}
		}
		if(dp[i])
			break;
	}
}

AC代码

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
// https://atcoder.jp/contests/abc354/tasks/abc354_e
using namespace std;
typedef long long ll;
const ll N=20,MaxStatus=static_cast<ll> (1<<20);//(2**20)
ll n,T;
ll A[N],B[N];
inline ll popcnt(ll x){
	ll cnt=0;
	for(cnt;x;++cnt){
		x&=x-1;
	}
	return cnt;
}

int main()	
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=0;i<n;++i)
		cin>>A[i]>>B[i];
	vector<int> dp(MaxStatus,0);	// 先全部初始化为takahashi输的
	for(int i=1;i<=(1<<n)-1;++i){
		if(popcnt(i)<=1)	// 只有一个牌自然是不可以的
			continue;
		for(int j=0;j<n;++j){
			if(!((i>>j)&1))
				continue;
			for(int k=j+1;k<n;++k){
				if(((i>>k)&1) && (A[j]==A[k] || B[j]==B[k])){
					dp[i]=1-dp[i-(1<<k)-(1<<j)];
					if(dp[i])
						break;
				}
			}
			if(dp[i])
				break;
		}
	}
	cout<<(dp[(1<<n)-1] ? "Takahashi":"Aoki")<<endl;
	return 0;
}
// AC https://atcoder.jp/contests/abc354/submissions/61042226
// AC https://www.luogu.com.cn/record/195869767

心路历程（WA，TLE，MLE……）

一次提交过了，当然，归功于样例比较强。

前面稍微调了一下是因为要加一下

1
2
if(dp[i])
	break;

都true了就不要再跑了，跑着跑着有可能又变成false了

Posted on Edited on

思路讲解

好像和上面这道有点关系

还是需要用到三进制状态压缩dp

0表示这张牌在A手里，1表示这张牌在B手里，2表示这张牌在C手里

然后问题就回到了怎么样状态转移了

答案是不用管怎么转移，暴搜（记忆化搜索）就完了

注意理解题意

AC代码

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
127
128
129
130
131
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>

using namespace std;
typedef long long ll;
const ll N=15,MaxSatus=600000;	// 3**12=531441
ll A[N];	// A为牌的权值
ll n,m,l;
ll digit[MaxSatus][N];
ll three[N];
int dp[MaxSatus][4];	// dp就是记忆化搜索里的缓存
ll initialStatus;
bool vis[MaxSatus][4];	// 表示走过
// 0 表示这张牌在桌子上，1表示这张牌在Takahashi手里
// 2表示在Aoki手里
// dp里存0就是指Takahashi输,反之则为他赢

void init(){
	three[0]=1;
	for(int i=1;i<=n+m+l;++i)
		three[i]=three[i-1]*3;
	for(int i=1;i<=three[n+m+l]-1;++i){
		ll temp=i;
		for(int j=0;j<=n+m+l;++j){
			digit[i][j]=temp%3;
			temp/=3;
		}
	}
	// 生成初始状态码（initialStatus）
	for(int i=0;i<n+m+l;++i){
		initialStatus*=3;
		if(i>=l && i<l+m)
			initialStatus+=2;
		else if(i>=m+l && i<m+n+l)
			initialStatus+=1;
	}
}
// who=1代表takahashi，who=2代表Aoki
// 然后就是要记忆化搜索，注意要记录此时是谁操作，因为有可能出现两个人手牌一样但是操作方不一样。
int dfs(int x,int who){
	if(vis[x][who])
		return dp[x][who];
	int res=0;	// res为这个状态是赢还是输
	for(int i=0;i<n+m+l;++i){
		// 模拟takahashi/Aoki换牌过程
		if(digit[x][i]!=who){
			continue;
		}
		// 模拟直接把i牌丢掉
		res=max(1-dfs(x-three[i]*who, 3-who),res);
		for(int j=0;j<n+m+l;++j){
			if(digit[x][j]!=0)
				continue;
			
			if(A[i]>A[j]){
				// 为什么要!dfs(x-three[i]*who, 3-who)？
				// 可以这么理解，返回的是你对手接下来是赢还是输，你对手输了，你自然就赢了
				// 如果对手赢了，你自然就输了
				// 当然，你输了,你的对手自然就赢了
				
				// 模拟拿这i牌换j牌
				res=max(1-dfs(x-three[i]*who+three[j]*who, 3-who),res);
			}
			if(res)
				break;
		}
		if(res)
			break;
	}
	dp[x][who]=res;
	vis[x][who]=true;
	return res;
}

//void out(){
//	for(int i=0;i<three[n+m+l];++i){
//		if(dp[i]){
//			for(int j=0;j<n+m+l;++j)
//				cout<<digit[i][j];
//			cout<<endl;
//		}
//	}
//}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>l;
	init();	// 初始化
	// 0-based
	for(int i=0;i<n+m+l;++i)
		cin>>A[i];
	bool ans=dfs(initialStatus,1);
	if(ans)
		cout<<"Takahashi"<<endl;
	else
		cout<<"Aoki"<<endl;
//	out();
}
// 暴搜
/*
AC https://atcoder.jp/contests/abc380/submissions/61130785
Takahashi and Aoki 
4 4 4
98 98765 987654 987654321
987 9876 9876543 98765432
123 12345 1234567 123456789

4 3 3
1233 1223 6767 5657
5657 5657 1
1212 2221 5656

1 0 0
0

*/

心路历程（WA，TLE，MLE……）

注意，题目是说可以直接把自己的一张牌打出来，不用管桌子上的牌，只是拿牌只能拿桌子上大的牌

Posted on Edited on

思路讲解

前置知识：并查集，以及如何维护联通块数量和上下限

主要思路就是我们把颜色相同且连在一起的作为一个联通块，如果对这个联通块进行染色，就把根节点染一下颜色，然后看左界-1颜色和右界+1颜色，看看要不要合并。

至于数颜色数量嘛，需要用到维护的该联通块数量

1
2
3
4
5
6
7
8
9
inline void changeColor(ll x,ll c){
	ll fax=find(x);
	// 现在把这个联通块改成c这个颜色
	// 所以c现在这个颜色有的块数量加上该联通块块数量
	colorCnt[c]+=Cnt[fax];
	// 原来的这一颜色拥有的块数量自然是要减的
	colorCnt[color[fax]]-=Cnt[fax];
	color[fax]=c;
}

AC代码

https://atcoder.jp/contests/abc380/submissions/61033055

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(5e5)+10;
ll n,T,q;
ll color[N],fa[N];
// color是这个联通块的颜色，只有始祖节点有意义
// fa是并查集的数组
// Cnt 记的是这个联通块的数量
ll Cnt[N];	// 当然，只有始祖节点的Cnt才是有意义的
// colorCnt记载的是这个颜色的数量
ll colorCnt[N];
// lr 记载该联通块的左右界,同样只有始祖节点的才有意义
struct upBoundLowBound{
	ll l,r;
}lr[N];

inline ll find(ll x){
	if(x>n || x<1)
		return 0;
	if(fa[x]==x)
		return x;
	fa[x]=find(fa[x]);
	return fa[x];
}

inline void merge(ll x,ll y){
	ll fax=find(x),fay=find(y);
	if(fax==fay)
		return;
	fa[fax]=fay;
	// 处理联通块子节点数量合并
	Cnt[fay]+=Cnt[fax];
	// 处理上下界合并
	lr[fay].l=min(lr[fax].l,lr[fay].l);
	lr[fay].r=max(lr[fax].r,lr[fay].r);
}

inline void changeColor(ll x,ll c){
	ll fax=find(x);
	// 现在把这个联通块改成c这个颜色
	// 所以c现在这个颜色有的块数量加上该联通块块数量
	colorCnt[c]+=Cnt[fax];
	// 原来的这一颜色拥有的块数量自然是要减的
	colorCnt[color[fax]]-=Cnt[fax];
	color[fax]=c;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>q;
	// 初始化
	for(int i=1;i<=n;++i){
		color[i]=i;
		fa[i]=i;
		Cnt[i]=1;
		colorCnt[i]=1;
		lr[i].l=i;
		lr[i].r=i;
	}
	for(int _=1;_<=q;++_){
		ll op,x,c;
		cin>>op;
		if(op==1){
			cin>>x>>c;
			changeColor(x, c);
			ll lowfa,upfa,fax;
			fax=find(x);
			lowfa=find(lr[fax].l-1);
			upfa=find(lr[fax].r+1);
			if(color[upfa]==c)
				merge(x,upfa);
			if(color[lowfa]==c)
				merge(x,lowfa);
		}else{
			cin>>c;
			cout<<colorCnt[c]<<endl;
		}
	}
	return 0;
}

/*
WA https://atcoder.jp/contests/abc380/submissions/61030202
wa了8个，等等看看问题出在哪
5 6
1 5 4
1 4 2
2 2
1 3 2
1 2 3
2 3

*/

心路历程（WA，TLE，MLE……）

WA https://atcoder.jp/contests/abc380/submissions/61030202

原因是我们还要维护一个块的上界和下界，以确定他是否和其他联通块因为颜色相同而相连。

Posted on Edited on

思路讲解

unionn的时候把Cnt加过去就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
inline ll findFa(ll x){
	if(fa[x]==x){
		return x;
	}
	fa[x]=findFa(fa[x]);
	return fa[x];
}
inline void unionn(ll a,ll b){
	if(findFa(a)==findFa(b))
		return;
	Cnt[findFa(b)]+=Cnt[findFa(a)];
	fa[findFa(a)]=findFa(b);
}

AC代码

https://www.acwing.com/problem/content/submission/code_detail/38538368/

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(1e5)+10;
ll n,m;
ll fa[N],Cnt[N];

inline ll findFa(ll x){
	if(fa[x]==x){
		return x;
	}
	fa[x]=findFa(fa[x]);
	return fa[x];
}
inline void unionn(ll a,ll b){
	if(findFa(a)==findFa(b))
		return;
	Cnt[findFa(b)]+=Cnt[findFa(a)];
	fa[findFa(a)]=findFa(b);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		fa[i]=i;	// 初始化fa的祖先为自己
		Cnt[i]=1;	// 初始化计数数组为1
	}
	for(int _=1;_<=m;++_){
		string op;
		ll a,b;
		cin>>op;
		if(op[0]=='C'){	// 合并 a b
			cin>>a>>b;
			unionn(a, b);
		}else if(op[1]=='1'){
			cin>>a>>b;
			if(findFa(a)==findFa(b)){
				cout<<"Yes"<<endl;
			}else{
				cout<<"No"<<endl;
			}
		}else{	// 询问a所在联通块点的数量
			cin>>a;
			cout<<Cnt[findFa(a)]<<endl;
		}
	}
	return 0;
}
/*
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

*/

心路历程（WA，TLE，MLE……）