题解：CF2078D Scammy Game Ad

· · 题解

题解：CF2078D Scammy Game Ad

题目传送门（Luogu）
题目传送门（Codeforces）

思路

前面的大佬说贪心行不通，那我偏要试试。

情况1:两扇门都是加法

在这种情况下怎么分配都一样，相当于答案直接加 a_1+a_2。
那问题就在上一个门新产生的人怎么分配。我们发现这一轮怎么分配对此时的答案没有影响，那就等到下一轮再处理。

情况2:两扇门都是乘法

很明显是把上一轮新产生的人分到乘数大的哪个组。

情况3:一扇门是乘法，另一扇是加法

无论加法那扇门进入的有多少人加数都是不变的。而乘法那扇门是进的人越多，加数越大。所以把上一轮新产生的人分到乘法的哪个组。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,n,ans,x,y,k1,k2,xc;char c1,c2;//xc表示可以随意分配的人，k1表示固定在第一扇门的人，k2表示固定在第二扇门的人
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;while(t--){
        k1=k2=1;ans=2;xc=0;cin>>n;while(n--){
            cin>>c1>>x>>c2>>y;
            if(c1=='+'&&c2=='+')xc+=x+y,ans+=x+y;
            else if(c1=='x'&&c2=='x'){
                x--,y--;int temp=xc;xc=max(x,y)*xc+x*k1+y*k2,ans+=xc;
                if(x>y)k1+=temp;
                else if(x<y)k2+=temp;
                else xc+=temp;//乘数相同那么原来的可以随意分配的人仍然可以随意分配
            }
            else if(c1=='+'&&c2=='x')k2+=xc,xc=x+(y-1)*k2,ans+=xc;
            else k1+=xc,xc=y+(x-1)*k1,ans+=xc;
        }
        cout<<ans<<'\n';
    }
    return 0;
}