Znzryb's Blog
0%

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……）

Posted on Edited on

思路讲解

哈哈，找规律很难找，找不出来？不妨使用回溯思想，反过来找。

这个操作那其实就是一个倍增操作，我们反过来找我们的这个位置需要倍增几次才能到那？

知道了这个，只需要通过这个（需要倍增几次）%2 进行反转操作就行。

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
#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>(2e5)+10;
ll n,T,len;
string s;

inline char invert(char a) {
	if(a<='z' && a>='a') {
		a-=32;
		return a;
	}else {
		a+=32;
		return a;
	}
}


// 可以用用这种指针写法
ll calLift(ll x, ll &standLen){
	ll cnt=0;
	while(true){
		if(standLen>x){
			standLen/=2;
			return cnt;
		}else if(standLen==x){
			return cnt;
		}else{
			cnt+=1;
			standLen*=2;
		}
	}
//	return cnt;
}

char dfs(ll x,ll cnt){
	ll needLift=0,standLen=len,res=0;
	needLift=calLift(x,standLen);
	if(needLift==0 /*|| (needLift==1 && x==standLen)*/){
		if(cnt%2==0)
			return s[x-1];
		else
			return invert(s[x-1]);
	}
	res= x==standLen ? standLen/2:x-standLen;
	return dfs(res,cnt+1);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	ll q;
	s.clear();
	cin>>s;
	len=s.size();
	cin>>q;
	for(int i=1;i<=q;++i){
		ll k;
		cin>>k;
		char ans=dfs(k,0);
		cout<<ans<<" ";
	}
	cout<<endl;
	return 0;
}
// AC https://atcoder.jp/contests/abc380/submissions/60951665
/*
qWeRtYuIoP
8
1 1 2 3 5 8 13 21

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

*/

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

样例给的强，一次提交就过了

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

其实调调了半天，尽量函数越少越好（用了一个指针优化掉了一个函数）。

Posted on Edited on

思路讲解

总体我感觉没什么难的，就是写起来比较复杂

细节上的问题主要写在注释上，这里讲一下答题思路。

先把所有在应该放2位置的1换成2。（之前是没有这个步骤的，但好像导致策略不够优秀）

接着把所有在应该放2位置的0先换成1，再换成2

最后放一下1就可以了

AC代码

https://codeforces.com/contest/2034/submission/297475528

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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#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>(2e5)+10;
ll n,T;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		cin>>n;
		vector<ll> A(n+10);
		vector<ll> test(n+10);
		ll cnt2=0,cnt1=0;
		// loc1Up指的是所有>n-cnt2的1.
		vector<ll> loc1,loc2;
		deque<ll> loc1Up,loc2Up;
		vector<pair<ll, ll> > op;
		for(int i=1;i<=n;++i){
			cin>>A[i];
			
			test[i]=A[i];
			
			if(A[i]==2){
				cnt2+=1,loc2.push_back(i);
			}else if(A[i]==1)
				cnt1+=1,loc1.push_back(i);
		}
		while(!loc1.empty()){
			if(loc1.back()<=n-cnt2)
				break;
			loc1Up.push_front(loc1.back());
			loc1.pop_back();
		}
		// loc2里装的是不符合要求的2.
		while (!loc2.empty()) {
			if(loc2.back()<=n-cnt2)
				break;
			// push_front 从前面加入，大的一直被往后面挤
			// 保证loc2Up的递增性（idx的递增型）
			loc2Up.push_front(loc2.back());
			loc2.pop_back();
		}
		
//		ll idx=0;
		// 这是排2的程序
		// 先把所有1都搞过去
		for(int i=n;i>n-cnt2;--i){
			if(test[i]==1){	
				op.emplace_back(i,loc2.back());
				
				swap(test[i], test[loc2.back()]);
				
				loc1.push_back(loc2.back());
				loc2.pop_back();
				// loc1Up遵循递增顺序，遍历是递减
				// 遇到先遇到的1必然最大的
				loc1Up.pop_back();
			}
		}
		for(int i=n;i>n-cnt2;--i){
			if(loc2.empty())
				break;
			// A是不可靠的，需要用test
			if(test[i]==2)
				continue;
			if(test[i]==1){	
				op.emplace_back(i,loc2.back());
				
				swap(test[i], test[loc2.back()]);
				
				loc1.push_back(loc2.back());
				loc2.pop_back();
				// loc1Up遵循递增顺序，遍历是递减
				// 遇到先遇到的1必然最大的
				loc1Up.pop_back();
			}else{
				// loc1不是空的时候
				if(!loc1.empty()){
					op.emplace_back(i,loc1.back());
					swap(test[i], test[loc1.back()]);
					op.emplace_back(i,loc2.back());
					swap(test[i],test[loc2.back()]);
					
					loc1.pop_back();
					loc1.push_back(loc2.back());
					loc2.pop_back();
				}else {
					op.emplace_back(i,loc1Up.back());
					swap(test[i], test[loc1Up.back()]);
					op.emplace_back(i,loc2.back());
					swap(test[i], test[loc2.back()]);
					
					loc1Up.pop_back();
					// 	这个1被交换到了loc2的位置
					loc1.push_back(loc2.back());
					loc2.pop_back();
				}
			}
		}
		
		// 这是排1的程序
		vector<ll> is1(n+10,false);
		sort(loc1.begin(), loc1.end());
		while (!loc1.empty()) {
			// n-cnt1-cnt2+1 需要摆1
			// n-cnt1-cnt2 就不需要摆1了，所以break掉
			if(loc1.back() <= n-cnt2-cnt1){
				break;
			}
			is1[loc1.back()]=true;
			loc1.pop_back();
		}
		// 开始正式排1
		for(int i=n-cnt2;i>=n-cnt1-cnt2+1;--i){
			if(loc1.empty())
				break;
			if(is1[i])
				continue;
			op.emplace_back(i,loc1.back());
			swap(test[i], test[loc1.back()]);
			loc1.pop_back();
		}
		
		cout<<op.size()<<endl;
		for(int i=0;i<op.size();++i){
//			if(abs(test[op[i].first]-test[op[i].second])!=1)
//				cout<<"WA on this: ";
			cout<<op[i].first<<" "<<op[i].second<<endl;
//			swap(test[op[i].first], test[op[i].second]);
		}
		
//		cout<<"Outcome: ";
//		for(int i=1;i<=n;++i){
//			cout<<test[i]<<" ";
//		}
//		cout<<endl;
	}
	return 0;
}

/*
4
41 0 2 0
40 1 2 0
41 1 2 0
42 2 1 0

*/

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

WA1:

https://codeforces.com/contest/2034/submission/297451161

判断哪里应该是2，哪里应该是1的判断有点问题

WA2:

https://codeforces.com/contest/2034/submission/297454477

策略不够优，超过了最大允许操作次数