Znzryb's Blog
0%

Posted on Edited on

思路讲解

哥德巴赫猜想是吧

image

image

哈哈，我们只管用这个结论就对了

AC代码

https://codeforces.com/problemset/submission/735/310500929

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
// Problem: CF735D Taxes
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF735D
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long 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
#define pb push_back
#define SZ(a) ((int) a.size())

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;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T,A[MAXN];

inline void solve(){
	cin>>N;
	if(N==2){
		cout<<1<<"\n";
		return;
	}
	if(N%2==0){
		cout<<2<<"\n";
	}else{
		bool isPrime=true;
		for(int i=2;i<=floor(sqrt(N));++i){
			if(N%i==0){
				isPrime=false;
				break;
			}
		}
		if(isPrime){
			cout<<1<<"\n";
			return;
		}
		bool isPrime2=true;
		for(int i=2;i<=floor(sqrt(N-2));++i){
			if((N-2)%i==0){
				isPrime2=false;
				break;
			}
		}
		if(isPrime2){
			cout<<2<<"\n";
			return;
		}
		cout<<3<<"\n";
		return;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	solve();
	return 0;
}
/*
AC
https://codeforces.com/problemset/submission/735/310500929
*/

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

Posted on Edited on

思路讲解

当发现裸的暴搜和状压不行了，这个时候就要开始想贪心了。（我怎么感觉这道题目的数据范围在误导我那）

参考以下题解，竟然是个贪心，佛了。

【Codeforces Round 1008 (Div. 2) 题目讲解 ABCDEF (CF2078)】 【精准空降到 19:54】 https://www.bilibili.com/video/BV13WQVYxEPC/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=1194

主要思路就是可以通过贪心，+和x相比，肯定x划算，x2和x3相比，肯定x3划算，然后就可以了。注意是一段一段，因为每次增加的可以重新分配。每次增加的多了，经过重新分配，总量也就多了。

AC代码

https://codeforces.com/contest/2078/submission/310089733

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
// Problem: D. Scammy Game Ad
// Contest: Codeforces - Codeforces Round 1008 (Div. 2)
// URL: https://codeforces.com/contest/2078/problem/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long 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
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

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

ll N,M,T;
// ll sum1[MAXN],mul1[MAXN],sum2[MAXN],mul2[MAXN];
struct OPER{
	char op1,op2;ll num1,num2;
}oper[MAXN];

inline void solve(){
	cin>>N;
	// sum1[0]=0;
	// mul1[0]=1;
	// sum2[0]=0;
	// mul2[0]=1;
	for(int i=1;i<=N;++i){
		cin>>oper[i].op1>>oper[i].num1>>oper[i].op2>>oper[i].num2;
	}
	ll lans=1,rans=1;
	for(int i=1;i<=N;++i){
		bool goLeft=true;
		for(int j=i+1;j<=N;++j){
			char op1=oper[j].op1,op2=oper[j].op2;
			ll num1=oper[j].num1,num2=oper[j].num2;
			if(op1=='+' && op2=='x'){
				goLeft=false;
				break;
			}else if(op1=='x' && op2=='x' && num2>num1){
				goLeft=false;
				break;
			}else if(op1=='x' && op2=='+'){
				goLeft=true;
				break;
			}else if(op1=='x' && op2=='x' && num2<num1){
				goLeft=true;
				break;
			}
		}
		char op1=oper[i].op1,op2=oper[i].op2;
		ll num1=oper[i].num1,num2=oper[i].num2;
		ll t1=0,t2=0;
		if(op1=='x') t1=num1*lans-lans;
		else t1=num1;
		if(op2=='x') t2=num2*rans-rans;
		else t2=num2;
		if(goLeft){
			lans+=(t1+t2);
		}else{
			rans+=(t1+t2);
		}
// #ifdef LOCAL
    // cerr << lans<<" "<<rans << '\n';
// #endif
	}
	cout<<lans+rans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
/*
AC
https://codeforces.com/contest/2078/submission/310089733
*/

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

注意，不仅遇到goRight的要停，goLeft的也要停。

这个算法其实问题在于虽然说后面乘数越多，你这个人的贡献就越大。但是问题在于如果一个人可以在比较早的时候变为多个人，然后再反哺回去，可能贡献更大？（如样例的第二个测试数据）

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: D. Scammy Game Ad
// Contest: Codeforces - Codeforces Round 1008 (Div. 2)
// URL: https://codeforces.com/contest/2078/problem/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long 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
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

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

ll N,M,T,A[MAXN];
ll sum1[MAXN],mul1[MAXN],sum2[MAXN],mul2[MAXN];
struct OPER{
	char op1,op2;ll num1,num2;
}oper[MAXN];

inline void solve(){
	cin>>N;
	// sum1[0]=0;
	// mul1[0]=1;
	// sum2[0]=0;
	// mul2[0]=1;
	for(int i=1;i<=N;++i){
		cin>>oper[i].op1>>oper[i].num1>>oper[i].op2>>oper[i].num2;
	}
	mul1[N+1]=1;
	mul2[N+1]=1;
	for(int i=N;i>=1;--i){
		if(oper[i].op1=='x'){
			mul1[i]=mul1[i+1]*oper[i].num1;
		}else{
			mul1[i]=mul1[i+1];
		}
		if(oper[i].op2=='x'){
			mul2[i]=mul2[i+1]*oper[i].num2;
		}else{
			mul2[i]=mul2[i+1];
		}
	}
	ll lans=1,rans=1;
	for(int i=1;i<=N;++i){
		ll num1=oper[i].num1,num2=oper[i].num2;
		ll lres=0,rres=0;	// 本次l和r需要增加的次数
		if(oper[i].op1=='x'){
			ll t=lans*num1-lans;
			if(mul1[i+1]>=mul2[i+1]){
				lres+=t;
			}else{
				rres+=t;
			}
		}else{
			ll t=num1;
			if(mul1[i+1]>=mul2[i+1]){
				lres+=t;
			}else{
				rres+=t;
			}		
		}
		
		if(oper[i].op2=='x'){
			ll t=rans*num2-rans;
			if(mul1[i+1]>=mul2[i+1]){
				lres+=t;
			}else{
				rres+=t;
			}			
		}else{
			ll t=num2;
			if(mul1[i+1]>=mul2[i+1]){
				lres+=t;
			}else{
				rres+=t;
			}		
		}
		lans+=lres;
		rans+=rres;
	}
	cout<<lans+rans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
/*

*/

Posted on Edited on

思路讲解

题意还是比较简单的，告诉你两数之和以及两数之积，问你在A数组中有几个对满足这个条件。

感觉是数据结构，但没想到要对题目条件进行转化。

看了一眼题解，好像是要转化题目条件。有点像下面这道题目，但没有那么明显。

2072E. Do You Love Your Hero and His Two-Hit Multi-Target Attacks?

又看了一眼，竟然是韦达定理？

image

离谱，我是完全没想到啊，这个我都已经不太记得了。

韦达定理+求根公式

image

AC代码

https://codeforces.com/problemset/submission/1857/310498477

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
// Problem: F. Sum and Product
// Contest: Codeforces - Codeforces Round 891 (Div. 3)
// URL: https://codeforces.com/problemset/problem/1857/F
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long 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
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,4> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;
constexpr double eps=1e-10;

ll N,T,A[MAXN];

inline void solve(){
	cin>>N;
	for(int i=1;i<=N;++i){
		cin>>A[i];
	}
	sort(A+1,A+1+N);
	ll Q;
	cin>>Q;
	for(int i=1;i<=Q;++i){
		ll b,c;
		cin>>b>>c;
		b=-b;
		ll D=b*b-4*1*c;
		if(D<0){
			cout<<0<<" ";
			continue;
		}
		long double sqD=sqrt(D);
// #ifdef LOCAL
	// cerr<<D<<"\n";
    // cerr <<setprecision(15)<< sqD << '\n';
// #endif
		// if(fabs(sqD-floor(sqD))>eps){	// 判断D是不是平方数
			// cout<<0<<" ";
			// continue;
		// }
		ll fsqD=floor(sqD);
		if(fsqD*fsqD!=D){
			cout<<0<<" ";
			continue;
		}
		if(D!=0){
			if((-b+fsqD)%2!=0 || (-b-fsqD)%2!=0){
				cout<<0<<" ";
				continue;
			}
			ll x1=(-b+fsqD)/(2);
			ll x2=(-b-fsqD)/(2);
			ll num1=upper_bound(A+1,A+1+N,x1)-lower_bound(A+1,A+1+N,x1);
			ll num2=upper_bound(A+1,A+1+N,x2)-lower_bound(A+1,A+1+N,x2);
			cout<<num1*num2<<" ";
// #ifdef LOCAL
    // cerr << num1<<" "<<num2<<" "<<x1<<" "<<x2 << '\n';
// #endif
		}else{
			ll needFind=(-b)/(2);
			ll num=upper_bound(A+1,A+1+N,needFind)-lower_bound(A+1,A+1+N,needFind);
			cout<<num*(num-1)/2<<" ";
		}
	}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
/*
AC
https://codeforces.com/problemset/submission/1857/310498477
*/

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

WA

https://codeforces.com/problemset/submission/1857/310497474

被卡了精度，无视精度，直接用整数比较好。

1
2
3
4
5
ll fsqD=floor(sqD);
if(fsqD*fsqD!=D){
	cout<<0<<" ";
	continue;
}

Posted on Edited on

思路讲解

题目说了一堆花里胡哨的，其实意思很简单，就是把你这个点，和所有点（包括你这个点）组成的线段的长度总和就是答案。

那么想要知道这个，我就想到了前缀和。但前缀和的话短的-长的是负值怎么办？可以对前缀和进行分段，具体的，其实就是这段代码。

1
2
3
4
5
for(int i=1;i<=N;++i){
	ll idx=upper_bound(X+1,X+1+N,(arr){X[i][0],INF,INF})-X;
	ll lsum=sum[idx-1],rsum=sum[N]-sum[idx-1];
	X[i][2]=(X[i][0]+1)*(idx-1)-lsum+rsum+N-idx+1-X[i][0]*(N-idx+1);
}

AC代码

https://codeforces.com/problemset/submission/1857/309735803

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
// Problem: E. Power of Points
// Contest: Codeforces - Codeforces Round 891 (Div. 3)
// URL: https://codeforces.com/problemset/problem/1857/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long 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
#define pb push_back
#define SZ(a) ((int) a.size())

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;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T;
arr X[MAXN];
ll	sum[MAXN];

inline bool cmpi(const arr &a,const arr &b){
	return a[1]<b[1];
}

inline void solve(){
	cin>>N;
	for(int i=1;i<=N;++i){
		cin>>X[i][0];
		X[i][1]=i;
	}
	sort(X+1,X+1+N);
	sum[0]=0;
	for(int i=1;i<=N;++i){
		sum[i]=X[i][0]+sum[i-1];
	}
	for(int i=1;i<=N;++i){
		ll idx=upper_bound(X+1,X+1+N,(arr){X[i][0],INF,INF})-X;
		ll lsum=sum[idx-1],rsum=sum[N]-sum[idx-1];
		X[i][2]=(X[i][0]+1)*(idx-1)-lsum+rsum+N-idx+1-X[i][0]*(N-idx+1);
	}
	// 输出答案阶段
	sort(X+1,X+1+N,cmpi);
	for(int i=1;i<=N;++i){
		cout<<X[i][2]<<" ";
	}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
/*
AC
https://codeforces.com/problemset/submission/1857/309735803
*/

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

Posted on Edited on

思路讲解

总体思路就是一个贪心，想办法省最多的钱。首先，这一天他没有去，那这钱他是省不了了，因为后面的天他去，肯定省后面的多的钱，前面的天也没法买他，因此，我们把这个人加到que0里（实际是一个栈，这种我应该用deque，代码里是vector）。

然后可以省钱的，必须要给他找个搭档，先在que0里找，再在rem（A[i]==’1’的i的set）里找，找小的（通过删除rem.begin()实现）。

AC代码

https://codeforces.com/contest/2026/submission/309701489

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
// Problem: C. Action Figures
// Contest: Codeforces - Educational Codeforces Round 171 (Rated for Div. 2)
// URL: https://codeforces.com/problemset/problem/2026/C
// Memory Limit: 512 MB
// Time Limit: 2500 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long 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
#define pb push_back
#define SZ(a) ((int) a.size())

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;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(4e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T;
char A[MAXN];

inline void solve(){
	cin>>N;
	ll ans=(1+N)*N/2;
	vector<ll> seq0;
	set<ll> rem;
	for(int i=1;i<=N;++i){
		cin>>A[i];
		if(A[i]=='0') seq0.push_back(i);
		if(A[i]=='1') rem.insert(i);
	}
	ll idx=0;
	// for(int i=N;i>=1;--i){
		// if(i<=idx) break;
		// if(A[i]=='1' && vis[i]){
// 			
			// ans-=i;
			// ++idx;
		// }
	// }
// #ifdef LOCAL
    // cerr << "OK "<<T << '\n';
// #endif
	while(!rem.empty()){
		set<ll>::iterator it=prev(rem.end());
		while(!seq0.empty() && seq0.back()>*it ){
			seq0.pop_back();
		}
// #ifdef LOCAL
    // cerr << seq0.back() << '\n';
// #endif
		if(!seq0.empty()){
			seq0.pop_back();
			ans-=*it;
		}else{
			if(rem.size()>=2){
				rem.erase(rem.begin());
				ans-=*it;
// #ifdef LOCAL
    // cerr << ans <<" "<< *it << '\n';
// #endif
			}
		}
		rem.erase(it);
	}
	cout<<ans<<"\n";

}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();

	}
	return 0;
}
/*
AC
https://codeforces.com/contest/2026/submission/309701489
*/

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