Znzryb's Blog
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;
}
/*

*/

Posted on Edited on

思路讲解

这个第一个贪心做法我觉得有点玄学，当然也敲了一遍，下面的第一个就是二分法

有些时候，你发现一个问题可以排序，这个时候就非常有可能是二分答案了

二分答案就是要剪枝，而且一旦发现rank ≥ m就立即返回，不要犹豫（也算是一种剪枝）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
inline bool check(ll x){
	ll rank=0;
	FOR(i,1,N){
		if(f(i,1,1)<x) break;
		FOR(j,1,N){
			if(f(i,j,1)<x) break;
			FOR(k,1,N){
				if(f(i,j,k)<x) break;
				++rank;
				if(rank>=M) return true;
			}
		}
	}
	// deEnter(rank);
	// if(rank>=M) return true;
	return false;
}

AC代码

https://atcoder.jp/contests/abc391/submissions/62332464

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
#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 unsigned 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>(1e18)+3;

ll N,M,A[5][MAXN];
struct Triple{
	ll val,i,j,k;
};
struct cmp{
	bool operator()(const Triple &a,const Triple &b) const{
		return a.val<b.val;
	}
};
struct cmpSet{
	bool operator()(const Triple &a,const Triple &b) const{
		if(a.val!=b.val) return a.val<b.val;
		if(a.i!=b.i) return a.i<b.i;
		if(a.j!=b.j) return a.j<b.j;
		if(a.k!=b.k) return a.k<b.k;
		return false;
	}
};
priority_queue<Triple,vector<Triple> ,cmp> pq;
set<Triple,cmpSet> vis;

ll f(ll i,ll j,ll k){
	ll res=0;
	res=A[1][i]*A[2][j]+A[1][i]*A[3][k]+A[2][j]*A[3][k];
	return res;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>M;
	FOR(i, 1, 3){
		FOR(j,1,N){
			cin>>A[i][j];
		}
		sort(&A[i][1],&A[i][N+1],greater<ll>());
	}
	ll rank=0;
	pq.push((Triple){f(1,1,1),1,1,1});
	while(!pq.empty()){
		++rank;
		// deSpace(pq.top().val);deSpace(pq.top().i);deSpace(pq.top().j);deEnter(pq.top().k);
		if(rank==M){
			cout<<pq.top().val<<'\n';
			return 0;
		}
		ll i=pq.top().i,j=pq.top().j,k=pq.top().k;
		pq.pop();
		if(vis.find((Triple){f(i+1,j,k),i+1,j,k})==vis.end() && i+1<=N){
			pq.push((Triple){f(i+1,j,k),i+1,j,k});
			vis.insert((Triple){f(i+1,j,k),i+1,j,k});
		}
		if(vis.find((Triple){f(i,j+1,k),i,j+1,k})==vis.end() && j+1<=N){
			pq.push((Triple){f(i,j+1,k),i,j+1,k});
			vis.insert((Triple){f(i,j+1,k),i,j+1,k});
		}
		if(vis.find((Triple){f(i,j,k+1),i,j,k+1})==vis.end() && k+1<=N){
			pq.push((Triple){f(i,j,k+1),i,j,k+1});
			vis.insert((Triple){f(i,j,k+1),i,j,k+1});
		}
		
	}
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc391/submissions/62332464
*/

https://atcoder.jp/contests/abc391/submissions/62335145

二分法

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 <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>(2e5)+10,MAXval=static_cast<ll>(3e18)+3;

ll N,M,A[MAXN],B[MAXN],C[MAXN];

ll f(ll i,ll j,ll k){
	ll res=A[i]*B[j]+A[i]*C[k]+B[j]*C[k];
	return res;
}
inline bool check(ll x){
	ll rank=0;
	FOR(i,1,N){
		if(f(i,1,1)<x) break;
		FOR(j,1,N){
			if(f(i,j,1)<x) break;
			FOR(k,1,N){
				if(f(i,j,k)<x) break;
				++rank;
				if(rank>=M) return true;
			}
		}
	}
	// deEnter(rank);
	// if(rank>=M) return true;
	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>M;
	FOR(i, 1, N){
		cin>>A[i];
	}
	FOR(i, 1, N){
		cin>>B[i];
	}
	FOR(i, 1, N){
		cin>>C[i];
	}
	sort(&A[1],&A[N+1],greater<ll>());
	sort(&B[1],&B[N+1],greater<ll>());
	sort(&C[1],&C[N+1],greater<ll>());
	// 使用二分查找到正好有K(M)个数比它大的数（也就是第K个）
	ll l=0,r=MAXval;
	while(l<r){
		ll mid=l+r+1>>1;
		if(check(mid)){
			l=mid;
		}else{
			r=mid-1;
		}
	}
	cout<<l<<'\n';
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc391/submissions/62335145
*/

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

Posted on Edited on

思路讲解

就是这么说那，还是不要省一些东西，lson简写成 l 容易导致误解使自己写错

然后三分可以这么写

1
2
3
4
5
6
7
8
m1=l+(r-l)/3;
m2=l+2*(r-l)/3;
tr[++tot].st=l,tr[tot].ed=m1;
tr[x].l=tot;
tr[++tot].st=m1+1,tr[tot].ed=m2;
tr[x].m=tot;
tr[++tot].st=m2+1,tr[tot].ed=r;
tr[x].r=tot;

AC代码

AC

https://atcoder.jp/contests/abc391/submissions/62327989

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
#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()

using namespace std;

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

ll N;
ll pow3[18];
// vector<ll> needChange[2][15];
bool stand;
bool A[MAXN];	// 经过修改的字符串（N即是未修改）
ll tot;

struct Tree{
	ll l,m,r;
	// bool val;
	ll st,ed;
}tr[MAXN*4];

inline plb buildTree(ll x){
	if(tr[x].st==tr[x].ed) {
		// cout<<tr[x].st<<' '<<tr[x].ed<<'\n';
		return {1,A[tr[x].st]};
	}
	ll l=tr[x].st,r=tr[x].ed;
	ll m1,m2;
	m1=l+(r-l)/3;
	m2=l+2*(r-l)/3;
	tr[++tot].st=l,tr[tot].ed=m1;
	tr[x].l=tot;
	tr[++tot].st=m1+1,tr[tot].ed=m2;
	tr[x].m=tot;
	tr[++tot].st=m2+1,tr[tot].ed=r;
	tr[x].r=tot;
	// needChange 如果要改动需要改动多少
	vector<ll> needCh[2];
	// cout<<tr[x].st<<' '<<tr[x].ed<<'\n';
	plb rec1=buildTree(tr[x].l);
	needCh[rec1.second].push_back(rec1.first);
	plb rec2=buildTree(tr[x].m);
	needCh[rec2.second].push_back(rec2.first);
	plb rec3=buildTree(tr[x].r);
	needCh[rec3.second].push_back(rec3.first);
	if(needCh[0].size()>needCh[1].size()){
		if(needCh[0].size()-needCh[1].size()==1){
			return {min(needCh[0][0],needCh[0][1]),false};
		}else{
			sort(all(needCh[0]));
			return {needCh[0][0]+needCh[0][1],false};	
		}
	}else{
		if(needCh[1].size()-needCh[0].size()==1){
			//           改动该点值的代价             该点的值
			return {min(needCh[1][0],needCh[1][1]),true};
		}else{
			sort(all(needCh[1]));
			return {needCh[1][0]+needCh[1][1],true};	
		}
	}
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N;
	pow3[0]=1;
	FOR(i, 1, 15){
		pow3[i]=pow3[i-1]*3;
	}
	FOR(i, 1, pow3[N]){
		char a;
		cin>>a;
		if(a=='1') A[i]=true;
		else A[i]=false;
	}
	
	tr[++tot].st=1,tr[tot].ed=pow3[N];
	plb rec=buildTree(tot);
	cout<<rec.first<<'\n';
	// cout<<A[0][1]<<'\n';
	return 0;
}

/*
AC
https://atcoder.jp/contests/abc391/submissions/62327989
*/

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

Posted on Edited on

思路讲解

https://www.luogu.com.cn/discuss/1021064

没什么其他要注意的，就是注意long double才能保证在long long范围内不被卡精度

1
maze[x][y]*1.0l <ans*1.0l/X

AC代码

https://atcoder.jp/contests/abc384/submissions/62254421

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
#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,size) x.begin()+1,x.begin()+size+1
#define all1(x) x.begin(),x.end()

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,MAXval=static_cast<ll>(1e18)+3;

ll N,M,X,sx,sy;
ll maze[MAXN][MAXN];
bool vis[MAXN][MAXN];
struct cmp{
	bool operator()(pll a,pll b){
		return maze[a.first][a.second]>maze[b.first][b.second];
	}
};
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>M>>X>>sx>>sy;
	FOR(i, 1, N){
		FOR(j, 1, M){
			cin>>maze[i][j];
		}
	}
	priority_queue<pll,vector<pll>,cmp> pq;
	pq.push({sx,sy});
	vis[sx][sy]=true;
	ll ans=0;
//	cout<<"Yes\n";
	while (!pq.empty()) {
		ll x=pq.top().first,y=pq.top().second;
		pq.pop();
		if(maze[x][y]*1.0l <ans*1.0l/X || (x==sx && y==sy)){
			ans+=maze[x][y];
//			cout<<ans<< ' '<< x <<' '<< y <<'\n';
			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]) continue;
				vis[fx][fy]=true;
				pq.push({fx,fy});
			}
		}
	}
	cout<<ans<<'\n';
	return 0;
}
/*
3 3 2
2 2
14 6 9
4 9 20
17 15 7

*/

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

Posted on Edited on

思路讲解

图比较简陋，大概就是叙述了为什么可以用双指针，以及问题的转化

我就想多加一段中可不可以？当然可以

多加一段前或后 前&后？也可以

我想全部用双指针嘛，所以说选前后相当于就是把中间扣掉嘛

AC代码

https://atcoder.jp/contests/abc384/submissions/62236712

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 <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,size) x.begin()+1,x.begin()+size+1
#define all1(x) x.begin(),x.end()

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>(1e18)+3;

ll N,S,A[MAXN],sumA[MAXN],sumBack[MAXN],originS;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>originS;
//	ll sumAll=0;
	FOR(i, 1, N){
		cin>>A[i];
		sumA[i]=sumA[i-1]+A[i];
	}
	ROF(i, N, 1){
		sumBack[i]=sumBack[i+1]+A[i];
	}
	S=originS;
	if(originS%sumA[N]==0) {cout<<"Yes\n";return 0;}
	if(S>sumA[N]){	// 大于sumA的问题转化为小于sumA的问题
		S=originS%sumA[N];
		// 双指针
		ll flag=2;
		FOR(i, 1, N){
			ll sum=sumA[flag-1]-sumA[i-1];
			bool needBreak=false;
			FOR(j, flag, N){
				if(sum>S) {flag=j;break;}
				if(sum+A[j]<S && j==N) {needBreak=true;break;}
				if(sum==S){
					cout<<"Yes\n";
					return 0;
				}
				sum+=A[j];
			}
			if(needBreak) break;
		}
		flag=2;
		FOR(i, 1, N){
			ll sum=sumA[flag-1]-sumA[i-1];
			bool needBreak=false;
			FOR(j, flag, N){
				if(sum>sumA[N]-S) {flag=j;break;}
				if(sum+A[j]<sumA[N]-S && j==N) {needBreak=true;break;}
				if(sum==sumA[N]-S){
					cout<<"Yes\n";
					return 0;
				}
				sum+=A[j];
			}
			if(needBreak) break;
		}
	}else{
		ll flag=2;
		FOR(i, 1, N){
			ll sum=sumA[flag-1]-sumA[i-1];
			FOR(j, flag, N){
				if(sum>S) {flag=j;break;}
				if(sum==S){
					cout<<"Yes\n";
					return 0;
				}
				sum+=A[j];
			}
		}
	}
	cout<<"No\n";
	return 0;
}
/*
WA*2
https://atcoder.jp/contests/abc384/submissions/62236467

3 15
3 8 4

*/

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

WA*2
https://atcoder.jp/contests/abc384/submissions/62236467

感谢这个讨论

https://www.luogu.com.cn/discuss/1022682

1
2
3
3 15
3 8 4

其实我之前写过一个这种情况的特判，被我自己删掉了