Znzryb's Blog
0%

2078D. Scammy Game Ad

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;
}
/*

*/