Znzryb's Blog
0%

Posted on Edited on

思路讲解

就是把D的连续改成了不一定连续

image

这个dp里存的是什么？

这个具体怎么想到这个dp里存的是什么要看这个视频，这个视频这方面讲的很清楚。

这个状态转移到底在干什么？其实是这样的，我们自然是枚举这个状态的最后一位是什么，这样我们才知道现在的状态是从哪里来的。

那么怎么状态转移？定义去掉最后一位的状态为pre，这个最后一位的数字肯定不会出现在dp[pre]之前，因为在dp[pre]之前，必然会截断一个成形的AA序列，无法正确形成这个状态。

image

故就是直接在dp[pre]这个位置后直接看有没有两位B，如果有，就是第二位B的位置，如果没有，就跳过。

1
2
3
4
5
6
7
if(((i>>j)&1)==1){	// 说明该位有一
	ll pre=i-(1<<j);
	ll res=upper_bound(pos[li[j]].begin(), pos[li[j]].end(), dp[pre])-pos[li[j]].begin()+1;
	if(res>=pos[li[j]].size())	// 超界
		continue;
	dp[i]=min(dp[i],pos[li[j]][res]);
}

AC代码

https://atcoder.jp/contests/abc381/submissions/61352128

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
#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,maxStatus=2e6+7;
ll n,T,A[N],kind;
// dp[S] 像这样的S序列需要至少多少个A序列元素（从1开始）才能组成
int dp[maxStatus];
set<ll> diff; 
ll li[25];	// 类离散化数组，代表该索引数代表实际数组是什么
vector<int> pos[25];	// 存该值的出现位置
inline void init(){
	ll idx=0;
	// 实现离散化(使用0-based索引，与状态存储保持一致)
	for(set<ll>::iterator it=diff.begin();it!=diff.end();it++){
		li[idx++]=*it;
	}
	dp[0]=0;
	for(int i=1;i<=1<<kind;++i){
		dp[i]=9999999;
	}
}
inline ll popcount(int x){
	ll cnt=0;
	while (x) {
		x&=x-1;
		++cnt;
	}
	return cnt;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>A[i];
		diff.insert(A[i]);
		pos[A[i]].push_back(i);
	}
	kind=diff.size();
	init();
	for(int i=1;i<=(1<<kind)-1;++i){
		// 
		for(int j=0;j<kind;++j){
			if(((i>>j)&1)==1){	// 说明该位有一
				ll pre=i-(1<<j);
				ll res=upper_bound(pos[li[j]].begin(), pos[li[j]].end(), dp[pre])-pos[li[j]].begin()+1;
				if(res>=pos[li[j]].size())	// 超界
					continue;
				dp[i]=min(dp[i],pos[li[j]][res]);
			}
		}
	}
	ll ans=0;
	for(int i=(1<<kind)-1;i>0;--i){	// 这个顺序不重要
		if(dp[i]==9999999)
			continue;
		ans=max(ans,popcount(i));
	}
	cout<<ans*2<<endl;
	return 0;
}
/*
AC https://atcoder.jp/contests/abc381/submissions/61352128
2
2 2

*/

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

https://atcoder.jp/contests/abc381/submissions/61352084

问题出在这个<号，应该是≤

1
for(int i=1;i<<=(1<<kind)-1;++i){

Posted on Edited on

思路讲解

需要动点脑子的二分，调了比较久

我的方法就是跑两遍二分，这样避免有情况漏考虑

跑两遍二分，因为上面的二分相当于否决了r=x-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
while(l<r){
	ll x=l+r+1>>1;
	ll cnt1=freq1[pos[x]]-freq1[down-1];
	ll cnt2=freq2[up]-freq2[pos[x]];	//这里不用减1
	ans=max(min(cnt1,cnt2)*2+1,ans);
	if(cnt1==cnt2){
		cout<< ans <<endl;
		return;
	}
	if(cnt1<cnt2){
		l=x;
	}else{
		r=x-1;
	}
}
ans=max(min(freq1[pos[l]]-freq1[down-1],freq2[up]-freq2[pos[l]]),ans);
// 跑两遍二分，因为上面的二分相当于否决了r=x-1是最优解的可能
// 下面一个二分与他互补
l=lower_bound(pos.begin(), pos.end(), down)-pos.begin();
r=upper_bound(pos.begin(), pos.end(), up)-pos.begin()-1;
while(l<r){
	ll x=l+r>>1;
	ll cnt1=freq1[pos[x]]-freq1[down-1];
	ll cnt2=freq2[up]-freq2[pos[x]];	//这里不用减1
	ans=max(min(cnt1,cnt2)*2+1,ans);
	if(cnt1==cnt2){
		cout<< ans <<endl;
		return;
	}
	if(cnt1<cnt2){
		l=x+1;
	}else{
		r=x;
	}
}
ans=max(min(freq1[pos[l]]-freq1[down-1],freq2[up]-freq2[pos[l]]),ans);

当然一些常见的优化自不必多说

AC代码

https://atcoder.jp/contests/abc381/submissions/61320459

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
#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,T;
char s[N];
ll freq1[N],freq2[N];
vector<ll> pos;	// /的位置
ll down=0,up=0;
ll ans;

void solve(){
	cin>>down>>up;
	// 二分
	ll l=lower_bound(pos.begin(), pos.end(), down)-pos.begin();
	if(pos[l]>up || l==pos.size()){// 防止pos[l]超界(以这种方法找出来的l都超界，那必然没/在里面)
		cout<<0<<endl;
		return;
	}
	ll r=upper_bound(pos.begin(), pos.end(), up)-pos.begin()-1;
	// 避免起始l==r导致WA
	ans=min(freq1[pos[l+r>>1]]-freq1[down-1],freq2[up]-freq2[pos[l+r>>1]])*2+1;
	while(l<r){
		ll x=l+r+1>>1;
		ll cnt1=freq1[pos[x]]-freq1[down-1];
		ll cnt2=freq2[up]-freq2[pos[x]];	//这里不用减1
		ans=max(min(cnt1,cnt2)*2+1,ans);
		if(cnt1==cnt2){
			cout<< ans <<endl;
			return;
		}
		if(cnt1<cnt2){
			l=x;
		}else{
			r=x-1;
		}
	}
	ans=max(min(freq1[pos[l]]-freq1[down-1],freq2[up]-freq2[pos[l]]),ans);
	// 跑两遍二分，因为上面的二分相当于否决了r=x-1是最优解的可能
	// 下面一个二分与他互补
	l=lower_bound(pos.begin(), pos.end(), down)-pos.begin();
	r=upper_bound(pos.begin(), pos.end(), up)-pos.begin()-1;
	while(l<r){
		ll x=l+r>>1;
		ll cnt1=freq1[pos[x]]-freq1[down-1];
		ll cnt2=freq2[up]-freq2[pos[x]];	//这里不用减1
		ans=max(min(cnt1,cnt2)*2+1,ans);
		if(cnt1==cnt2){
			cout<< ans <<endl;
			return;
		}
		if(cnt1<cnt2){
			l=x+1;
		}else{
			r=x;
		}
	}
	ans=max(min(freq1[pos[l]]-freq1[down-1],freq2[up]-freq2[pos[l]]),ans);
	cout<< ans <<endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>T;
	for(int i=1;i<=n;++i)
		cin>>s[i];
	ll cnt1l =0,cnt2l=0;
	for(int i=1;i<=n;++i){
		if(s[i]=='1')
			cnt1l+=1;
		else if(s[i]=='2')
			cnt2l+=1;
		else
			pos.push_back(i);
		freq1[i]=cnt1l;
		freq2[i]=cnt2l;
	}
	while (T--) {
		if(pos.empty()){
			cout<<0<<endl;
			continue;
		}
		solve();
	}
	return 0;
}
/*
50 10
/211//2///1212/212/12/12/1//11111/12121//22/122221
16 19
27 45
12 32
45 49
33 42
7 9
18 46
1 5
44 45
3 23

*/

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

Posted on Edited on

思路讲解

我是没想到这么简单就AC了

主要思路就是一直遍历，遇到完全不对的直接截断，遇到重复的把之前的去掉重新开始计数，当然有一些小的需要搞一搞的地方，比如

6
1 2 2 2 3 3

这个需要2 2 3 3

所以当步长为2往前发现不行的时候，看看可不可以回退

AC代码

https://atcoder.jp/contests/abc381/submissions/61291304

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
#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,A[N];
ll ans;
// 题意就是找出最长的像1122的序列
ll pos[N];	// 位置数组，该值上次出现的位置

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>A[i];
	}
	if(n==1){
		cout<<0<<endl;
		return 0;
	}
	ll cnt=0,i=2,start=1;	// start 为当前substring的起始位置
	while(i<=n){
		if(A[i-1]!=A[i]){
			ans=max(ans,cnt);
			cnt=0;
			if(A[i-1]==A[i-2]){
				i-=1;
				cnt+=2;
				start=i-1;
			}else{
				i+=1;
				start=i-1;
			}
		}else{
			if(pos[A[i]]>start){
				ans=max(ans,cnt);
				start=pos[A[i]]+1;
				cnt=i-pos[A[i]];
				pos[A[i]]=i;
				i+=2;
			}else if(pos[A[i]]==start){
				ans=max(ans,cnt);
				start=pos[A[i]];
				cnt=i-pos[A[i]]+1;
				pos[A[i]]=i;
				i+=2;
			}else{
				pos[A[i]]=i;
				cnt+=2;
				i+=2;
			}
		}
	}
	ans=max(cnt,ans);
	cout<<ans<<endl;
	return 0;
}
/*
6
1 2 2 2 3 3
AC https://atcoder.jp/contests/abc381/submissions/61291304
*/

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

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了