Znzryb's Blog
0%

Posted on Edited on

思路讲解

ABC-390-E - Vitamin Balance

我感觉很像这道题，因为我就只要背包分成几块就好了

但是又有点问题，合起来的过程需要枚举非常多次，那道题只要合并3个背包就好了，我们要合并500个背包，想想就TLE

所以这种问题一般就别想裸的背包合并，需要使用类似于向斜下方走的dp

image

比较简单的来讲，类似于CF-994-D. Shift + Esc （多变量优化dp）

需要关注一下颜色之间的转移以及最优状态

image

1
2
3
4
5
6
7
8
9
10
11
12
13
FOR(i,1,idx){
	FOR(j,Len[i].fi,Len[i].se){
		ll yen=T[j].yen,val=T[j].u;
		ROF(k,Vol,1){
			if(k<yen){
				dp[i][k]=max(dp[i-1][k],dp[i][k]);
			}else{
				dp[i][k]=max({dp[i][k],dp[i][k-yen]+val,dp[i-1][k-yen]+K+val,dp[i-1][k]});
			}
		}
	}
}
cout<<dp[idx][Vol]<<'\n';

AC代码

AC

https://atcoder.jp/contests/abc383/submissions/62392605

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
// Problem: F - Diversity
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_f
// Memory Limit: 1024 MB
// Time Limit: 2500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=510,INF=static_cast<ll>(5e18)+3;

ll N,Vol,K;
arr A[MAXN];
//   color   volume
ll dp[MAXN][50010];	// most utility

inline bool cmp(arr a,arr b){	// 按照颜色排序
	return a[2]<b[2];
}
struct Things{
	ll yen,u,c;
}T[MAXN];
pll Len[MAXN];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>Vol>>K;
	// SumUtility+TdifferentColor*K
	FOR(i, 1, N){	// yen Utility color
		cin>>A[i][0]>>A[i][1]>>A[i][2];
	}
	sort(&A[1],&A[N+1],cmp);
	ll idx=0;
	
	T[1].yen=A[1][0],T[1].u=A[1][1],T[1].c=++idx;
	FOR(i,2,N){
		if(A[i-1][2]!=A[i][2]){	// 重新映射颜色
			T[i].c=++idx;
		}else{
			T[i].c=idx;
		}
		T[i].yen=A[i][0],T[i].u=A[i][1];
	}
	Len[1].fi=1;
	Len[idx].se=N;
	FOR(i,2,N){
		if(T[i].c!=T[i-1].c){
			Len[T[i-1].c].se=i-1;
			Len[T[i].c].fi=i;
		}
	}
	
	FOR(i,1,idx){
		FOR(j,Len[i].fi,Len[i].se){
			ll yen=T[j].yen,val=T[j].u;
			ROF(k,Vol,1){
				if(k<yen){
					dp[i][k]=max(dp[i-1][k],dp[i][k]);
				}else{
					dp[i][k]=max({dp[i][k],dp[i][k-yen]+val,dp[i-1][k-yen]+K+val,dp[i-1][k]});
				}
			}
		}
	}
	cout<<dp[idx][Vol]<<'\n';
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc383/submissions/62392605
*/

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

记忆化搜索超时

这个时间复杂度可以这么估计，每个combDp都是由 ROF(i,Vol-usedVol,0) 生成的，空间乘以这个循环次数自然就是时间复杂度了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// memorized search
ll dfs(ll curCol,ll usedVol){
	if(curCol>colLim) return 0;
	if(usedVol>=Vol) return 0;
	if(combDp[curCol][usedVol]!=-1) return combDp[curCol][usedVol];
	ll res=0;
	ROF(i,Vol-usedVol,0){
		ll lres=0;
		if(dp[curCol][i]==0){
			lres=dfs(curCol+1,usedVol);
			res=max(lres,res);
			break;
		}
		lres=dp[curCol][i]+K;
		lres+=dfs(curCol+1,usedVol+i);
		res=max(lres,res);
	}
	combDp[curCol][usedVol]=res;
	return res;
}

https://atcoder.jp/contests/abc383/submissions/62385966

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
// Problem: F - Diversity
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_f
// Memory Limit: 1024 MB
// Time Limit: 2500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=510,INF=static_cast<ll>(5e18)+3;

ll N,Vol,K;
arr A[MAXN];
//   color   volume
ll dp[MAXN][50010];	// most utility

inline bool cmp(arr a,arr b){	// 按照颜色排序
	return a[2]<b[2];
}
struct Things{
	ll yen,u,c;
}T[MAXN];
pll Len[MAXN];
ll combDp[MAXN][50010];
ll colLim;
// memorized search
ll dfs(ll curCol,ll usedVol){
	if(curCol>colLim) return 0;
	if(usedVol>=Vol) return 0;
	if(combDp[curCol][usedVol]!=-1) return combDp[curCol][usedVol];
	ll res=0;
	ROF(i,Vol-usedVol,0){
		ll lres=0;
		if(dp[curCol][i]==0){
			lres=dfs(curCol+1,usedVol);
			res=max(lres,res);
			break;
		}
		lres=dp[curCol][i]+K;
		lres+=dfs(curCol+1,usedVol+i);
		res=max(lres,res);
	}
	combDp[curCol][usedVol]=res;
	return res;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>Vol>>K;
	// SumUtility+TdifferentColor*K
	FOR(i, 1, N){	// yen Utility color
		cin>>A[i][0]>>A[i][1]>>A[i][2];
	}
	sort(&A[1],&A[N+1],cmp);
	ll idx=0;
	
	T[1].yen=A[1][0],T[1].u=A[1][1],T[1].c=++idx;
	FOR(i,2,N){
		if(A[i-1][2]!=A[i][2]){	// 重新映射颜色
			T[i].c=++idx;
		}else{
			T[i].c=idx;
		}
		T[i].yen=A[i][0],T[i].u=A[i][1];
	}
	Len[1].fi=1;
	Len[idx].se=N;
	FOR(i,2,N){
		if(T[i].c!=T[i-1].c){
			Len[T[i-1].c].se=i-1;
			Len[T[i].c].fi=i;
		}
	}
	
	// FOR(i,1,idx){
		// cerr<<Len[i].fi<<' '<<Len[i].se<<'\n';
	// }
	// cerr<<T[3].yen<<' '<<T[3].c<<'\n';
	
	FOR(i,1,idx){
		FOR(j,Len[i].fi,Len[i].se){
			ll yen=T[j].yen,val=T[j].u;
			ROF(k,Vol,1){
				if(k<yen) break;
				dp[i][k]=max(dp[i][k],dp[i][k-yen]+val);
			}
		}
	}
	
	// FOR(i,1,idx){
		// FOR(j,1,Vol){
			// cerr<<dp[i][j]<<' ';
		// }
		// cerr<<'\n';
	// }
	
	colLim=idx;
	FOR(i,0,idx){	// 初始化combDp
		FOR(j,0,Vol){
			combDp[i][j]=-1;
		}
	}
	
	FOR(i,1,idx){
		cerr<<dp[i][0]<<'\n';
	}
	
	cout<<dfs(1,0)<<'\n';
	return 0;
}
/*

*/

用二分稍微优化了一点，多过了一些点

http://atcoder.jp/contests/abc383/submissions/62387360

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
// Problem: F - Diversity
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_f
// Memory Limit: 1024 MB
// Time Limit: 2500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=510,INF=static_cast<ll>(5e18)+3;

ll N,Vol,K;
arr A[MAXN];
//   color   volume
ll dp[MAXN][50010];	// most utility

inline bool cmp(arr a,arr b){	// 按照颜色排序
	return a[2]<b[2];
}
struct Things{
	ll yen,u,c;
}T[MAXN];
pll Len[MAXN];
ll combDp[MAXN][50010];
ll colLim;
// memorized search
ll dfs(ll curCol,ll usedVol){
	if(curCol>colLim) return 0;
	if(usedVol>=Vol) return 0;
	if(combDp[curCol][usedVol]!=-1) return combDp[curCol][usedVol];
	ll res=0;
	res=dfs(curCol+1,usedVol);	// 直接跳过该颜色
	ll flag=1;
	while(true){
		ll idx=lower_bound(&dp[curCol][1],&dp[curCol][Vol-usedVol+1],flag)-&dp[curCol][0];
		if(idx==Vol-usedVol+1) break;
		ll lres=dp[curCol][idx]+K;
		lres+=dfs(curCol+1,usedVol+idx);
		res=max(res,lres);
		flag=dp[curCol][idx+1]+1;
	}
	combDp[curCol][usedVol]=res;
	return res;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>Vol>>K;
	// SumUtility+TdifferentColor*K
	FOR(i, 1, N){	// yen Utility color
		cin>>A[i][0]>>A[i][1]>>A[i][2];
	}
	sort(&A[1],&A[N+1],cmp);
	ll idx=0;
	
	T[1].yen=A[1][0],T[1].u=A[1][1],T[1].c=++idx;
	FOR(i,2,N){
		if(A[i-1][2]!=A[i][2]){	// 重新映射颜色
			T[i].c=++idx;
		}else{
			T[i].c=idx;
		}
		T[i].yen=A[i][0],T[i].u=A[i][1];
	}
	Len[1].fi=1;
	Len[idx].se=N;
	FOR(i,2,N){
		if(T[i].c!=T[i-1].c){
			Len[T[i-1].c].se=i-1;
			Len[T[i].c].fi=i;
		}
	}
	
	FOR(i,1,idx){
		FOR(j,Len[i].fi,Len[i].se){
			ll yen=T[j].yen,val=T[j].u;
			ROF(k,Vol,1){
				if(k<yen) break;
				dp[i][k]=max(dp[i][k],dp[i][k-yen]+val);
			}
		}
	}
	
	colLim=idx;
	FOR(i,0,idx){	// 初始化combDp
		FOR(j,0,Vol){
			combDp[i][j]=-1;
		}
	}
	
	cout<<dfs(1,0)<<'\n';
	return 0;
}
/*

*/

无法通过样例三

这个代码的问题在于dp[j-yen].c==0时，都会+K，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
FOR(i,1,N){	// 枚举物品
	ll yen=T[i].yen,c=T[i].c,val=T[i].u;	// 养成好习惯
	ROF(j,Vol,1){
		if(j<yen) break;
		if(dp[j-yen].c<c){	// 这个代码的问题在于dp[j-yen].c==0
			if(dp[j-yen].val+val+K>dp[j].val){
				dp[j].val=dp[j-yen].val+val+K;
				dp[j].c=c;
			}
		}else{
			dp[j].val=max(dp[j-yen].val+val,dp[j].val);
		}
		
		// cerr<<j<<' '<<T[i].yen<<' '<<T[i].u<<' '<<T[i].c<<' '<<dp[j].val<<' '<<dp[j].c<<'\n';
		
	}
}
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
// Problem: F - Diversity
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_f
// Memory Limit: 1024 MB
// Time Limit: 2500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define debug(x) cerr<<x<<'\n'
#define CLR(i,a) memset(i,a,sizeof(i))

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=510,INF=static_cast<ll>(5e18)+3;

ll N,Vol,K;
arr A[MAXN];
struct DP{
	ll val,c;
};
//      volume 
DP dp[50010];

inline bool cmp(arr a,arr b){	// 按照颜色排序
	return a[2]<b[2];
}
struct Things{
	ll yen,u,c;
}T[MAXN];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>Vol>>K;
	// SumUtility+TdifferentColor*K
	FOR(i, 1, N){	// yen Utility color
		cin>>A[i][0]>>A[i][1]>>A[i][2];
	}
	sort(&A[1],&A[N+1],cmp);
	// ll idx=0;
	// T[1].yen=A[1][0],T[1].u=A[1][1],T[1].c=++idx;
	// FOR(i,2,N){
		// if(A[i-1][2]!=A[i][2]){	// 重新映射颜色
			// T[i].c=++idx;
		// }else{
			// T[i].c=idx;
		// }
		// T[i].yen=A[i][0],T[i].u=A[i][1];
	// }
	CLR(dp,0);
	// FOR(i,1,N){
		// cerr<<A[i][0]<<' '<<A[i][1]<<' '<<A[i][2]<<'\n';
	// }
	FOR(i,1,N){	// 枚举物品
		ll yen=A[i][0],c=A[i][2],val=A[i][1];	// 养成好习惯
		ROF(j,Vol,1){
			if(j<yen) break;
			if(dp[j-yen].c<c){	
				if(dp[j-yen].val+val+K>dp[j].val){
					dp[j].val=dp[j-yen].val+val+K;
					dp[j].c=c;
				}
			}else{
				if(dp[j-yen].val+val>dp[j].val){
					dp[j].val=dp[j-yen].val+val;
					dp[j].c=c;
				}
			}
			// cerr<<j<<' '<<T[i].yen<<' '<<T[i].u<<' '<<T[i].c<<' '<<dp[j].val<<' '<<dp[j].c<<'\n';
			
		}
	}
	FOR(i,0,Vol){
		cerr<<i<<' '<<dp[i].val<<' '<<dp[i].c<<'\n';
	}
	cout<<dp[Vol].val<<'\n';
	return 0;
}
/*

*/

Posted on Edited on

思路讲解

多源广搜经典套路，如果该点到达时间没有别的点早，就可以不用走了

然后把所有点加入q，实现多源广搜

1
2
3
4
5
6
7
8
FOR(i,1,N){
	FOR(j,1,M){
		if(maze[i][j]!='H') continue;
		q.push({i,j,0});
		vis[i][j]=0;
	}
}
bfs();

AC代码

https://atcoder.jp/contests/abc383/submissions/62366428

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
// Problem: C - Humidifier 3
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define debug(x) cerr<<x<<' '
#define CLR(i,a) memset(i,a,sizeof(i))

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=static_cast<ll>(1e3)+10,MAXval=static_cast<ll>(5e18)+3;

ll N,M,D;
char maze[MAXN][MAXN];
ll vis[MAXN][MAXN];

ll dx[4]={1,0,-1,0};
ll dy[4]={0,-1,0,1};

queue<arr> q;

inline void bfs(){	// 需要对之前所有加入q的点做好vis=true的处理
	while(!q.empty()){
		ll x=q.front()[0],y=q.front()[1],d=q.front()[2];
		q.pop();
		if(d>=D) continue;
		FOR(i,0,3){
			ll fx=x+dx[i],fy=y+dy[i];
			if(fx<1 || fx>N) continue;
			if(fy<1 || fy>M) continue;
			if(vis[fx][fy]<d+1) continue;
			if(maze[fx][fy]=='#') continue;
			vis[fx][fy]=d+1;
			q.push({fx,fy,d+1});
			// cerr<<fx<<' '<<fy<<'\n';
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>N>>M>>D;
	FOR(i, 1, N){
		FOR(j,1,M){
			cin>>maze[i][j];
		}
	}
	CLR(vis,0x3f);
	ll stand=vis[0][0];
	FOR(i,1,N){
		FOR(j,1,M){
			if(maze[i][j]!='H') continue;
			q.push({i,j,0});
			vis[i][j]=0;
		}
	}
	bfs();
	ll ans=0;
	FOR(i,1,N){
		FOR(j,1,M){
			if(vis[i][j]!=stand) ++ans;
		}
	}
	cout<<ans<<endl;
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc383/submissions/62366428
*/

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

Posted on Edited on

思路讲解

AC代码

https://atcoder.jp/contests/abc383/submissions/62366428

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
// Problem: C - Humidifier 3
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define debug(x) cerr<<x<<' '
#define CLR(i,a) memset(i,a,sizeof(i))

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=static_cast<ll>(1e3)+10,MAXval=static_cast<ll>(5e18)+3;

ll N,M,D;
char maze[MAXN][MAXN];
ll vis[MAXN][MAXN];

ll dx[4]={1,0,-1,0};
ll dy[4]={0,-1,0,1};

queue<arr> q;

inline void bfs(){	// 需要对之前所有加入q的点做好vis=true的处理
	while(!q.empty()){
		ll x=q.front()[0],y=q.front()[1],d=q.front()[2];
		q.pop();
		if(d>=D) continue;
		FOR(i,0,3){
			ll fx=x+dx[i],fy=y+dy[i];
			if(fx<1 || fx>N) continue;
			if(fy<1 || fy>M) continue;
			if(vis[fx][fy]<d+1) continue;
			if(maze[fx][fy]=='#') continue;
			vis[fx][fy]=d+1;
			q.push({fx,fy,d+1});
			// cerr<<fx<<' '<<fy<<'\n';
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>N>>M>>D;
	FOR(i, 1, N){
		FOR(j,1,M){
			cin>>maze[i][j];
		}
	}
	CLR(vis,0x3f);
	ll stand=vis[0][0];
	FOR(i,1,N){
		FOR(j,1,M){
			if(maze[i][j]!='H') continue;
			q.push({i,j,0});
			vis[i][j]=0;
		}
	}
	bfs();
	ll ans=0;
	FOR(i,1,N){
		FOR(j,1,M){
			if(vis[i][j]!=stand) ++ans;
		}
	}
	cout<<ans<<endl;
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc383/submissions/62366428
*/

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

Posted on Edited on

思路讲解

参考洛谷题解

在kruskal的过程中求解这个问题，然后如果发现合并的复杂度太高，看看用数量代替set的合并可不可以？

然后记得结构体的全部数组要初始化

AC代码

https://atcoder.jp/contests/abc383/submissions/62364335

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
// Problem: E - Sum of Max Matching
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_e
// Memory Limit: 1024 MB
// Time Limit: 2500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define debug(x) cerr<<x<<'\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=static_cast<ll>(2e5)+10,MAXval=static_cast<ll>(5e18)+3;

ll N,M,K;
vector<pll> G[MAXN];
struct Triple{
	ll u,v,w;
};
struct cmp{
	bool operator()(const Triple &a,const Triple &b)const{
		return a.w>b.w;
	}
};
priority_queue<Triple,vector<Triple>,cmp> pq;

struct FA{
	                 // 初始每个点的未匹配点数量
	ll fa[MAXN],size,numa[MAXN],numb[MAXN];
	inline void init(ll range){
		size=range;
		FOR(i,1,size){	// 初始化并查集
			fa[i]=i;
			numa[i]=0;
			numb[i]=0;
		}
	}
	ll find(ll x){
		if(fa[x]==x) return x;
		return fa[x]=find(fa[x]);
	}
	inline void merge(ll a,ll b){
		ll faA=find(a),faB=find(b);
		fa[faA]=faB;
		// 将a合并入b
		numa[faB]+=numa[faA];
		numb[faB]+=numb[faA];
		// debug(numa[faB]);
		// debug(numb[faB]);
	}
	inline ll match(ll a,ll b){
		ll faA=find(a),faB=find(b);
		ll aOption=min(numa[faA],numb[faB]),bOption=min(numb[faA],numa[faB]);
		numa[faA]-=aOption;
		numb[faB]-=aOption;
		numb[faA]-=bOption;
		numa[faB]-=bOption;
		return aOption+bOption;
	}
};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>M>>K;
	FA fa;
	fa.init(N); 
	FOR(i, 1, M){
		ll u,v,w;
		cin>>u>>v>>w;
		G[u].push_back({v,w});
		G[v].push_back({u,w});
		pq.push((Triple){u,v,w});
	}
	FOR(i,1,K){
		ll a;
		cin>>a;
		fa.numa[a]+=1;
	}
	FOR(i,1,K){
		ll b;
		cin>>b;
		fa.numb[b]+=1;
	}
	// FOR(i,1,N){
		// cerr<<fa.numa[i]<<' ';
	// }
	// cerr<<'\n';
	// FOR(i,1,N){
		// cerr<<fa.numb[i]<<' ';
	// }
	// cerr<<'\n';
	ll ans=0;
	// kruskal（最小生成树+无向图判环）
	while(!pq.empty()){
		ll u=pq.top().u,v=pq.top().v,w=pq.top().w;
		pq.pop();
		if(fa.find(u)!=fa.find(v)){
			ans+=w*fa.match(u,v);
			// cerr<<u<<' '<<v<<' '<<w<<' '<<ans<<' '<<'\n';
			fa.merge(u,v);
		}
	}
	cout<<ans<<'\n';
	return 0;
}
/*

*/

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

https://atcoder.jp/contests/abc383/submissions/62364233

类的数组记得要init（）

1
2
3
4
5
6
7
8
inline void init(ll range){
	size=range;
	FOR(i,1,size){	// 初始化并查集
		fa[i]=i;
		numa[i]=0;
		numb[i]=0;
	}
}

Posted on Edited on

题目大意

给定正整数 NN，求不超过 NN 的正整数中，恰好有 9 个正约数的数的个数。

输入格式：

  • 一行一个整数 NN （ 1≤N≤4×10121 \leq N \leq 4 \times 10^{12} ）

输出格式：

  • 一个整数，表示答案

样例说明：

  • 当 N=200N = 200 时，满足条件的正整数有 36, 100, 196 共 3 个

思路讲解

约数个数定理（因数个数定理）

这篇解释了该定理

image

AC代码

https://atcoder.jp/contests/abc383/submissions/62341051

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
// Problem: D - 9 Divisors
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define deSpace(x) cerr<<x<<' '
#define deEnter(x) cerr<<x<<'\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=static_cast<ll>(4e6)+10,MAXval=static_cast<ll>(5e18)+3;

ll N;
bool isprime[MAXN];
ll prime[MAXN];
inline void genPrimels(ll range){
	FOR(i,2,range){	// 0,1 比较特殊
		isprime[i]=true;
	}
	for(int i=2;i*i<=range;++i){
		for(int j=i*2;j<=range;j+=i){
			isprime[j]=false;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N;
	ll ans=0;
	ll sqrtN=floor(sqrt(N));
	genPrimels(sqrtN);
	ll idx=0;
	FOR(i,2,sqrtN){
		if(isprime[i]) prime[++idx]=i;
	}
	// deEnter(idx);
	ll flag=idx;
	FOR(i,1,idx){
		ROF(j,flag,1){
			if(prime[i]*prime[j]<=sqrtN){
				flag=j;
				break;
			}
		}
		if(flag<=i) break;
		ans+=flag-i;
	}
	FOR(i,1,idx){
		if(prime[i]*prime[i]*prime[i]*prime[i]*prime[i]*prime[i]*prime[i]*prime[i]<=N){
			++ans;
		}else{
			break;
		}
	}
	cout<<ans<<'\n';
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc383/submissions/62341051
*/

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

暴力，TLE

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
// Problem: D - 9 Divisors
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define deSpace(x) cerr<<x<<' '
#define deEnter(x) cerr<<x<<'\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=static_cast<ll>(1e6)+10,MAXval=static_cast<ll>(5e18)+3;

ll N;
inline bool check(ll x){
	ll res=0;
	for(int i=1;i*i<=x;++i){
		if(i*i==x){
			++res;
		}else if(x%i==0){
			res+=2;
		}
		if(res>9) return false;
	}
	if(res==9) return true;
	else return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N;
	ll ans=0;
	for(int i=1;i*i<=N;++i){
		if(check(i*i)){
			++ans;
			deEnter(i*i);
		}
	}
	cout<<ans<<'\n';
	return 0;
}
/*

*/