大改革 HDU20260820I

HDU20260820I 大改革

拿下首杀！！！！！！！！！

题目描述：

有 $n$ 个变量，第 $i$ 个变量为 $t_i$ ，有权重 $a_i,b_i$ 。有三个变量 $S_1,S_2,A$ ，初始为 $0$ 。

你可以以任意顺序，对于每一个满足 $t_i\ne 0$ 的 $i$ 依次执行以下两个操作：

1. 若 $a_i=t_i$ ，则令 $A\leftarrow A+[S_1\ge c]+[S_1\ge -c]$ ，然后令 $S_1\leftarrow S_1+1$ 。否则令 $A\leftarrow A-[S_1\le c]-[S_1\le -c]$ ，然后令 $S_1\leftarrow S_1-1$ 。
2. 若 $b_i=t_i$ ，则令 $A\leftarrow A+[S_2\ge c]+[S_2\ge -c]$ ，然后令 $S_2\leftarrow S_2+1$ 。否则令 $A\leftarrow A-[S_2\le c]-[S_2\le -c]$ ，然后令 $S_2\leftarrow S_2-1$ 。

求 $A$ 最大值。

$n,c\le 10^4$ 。

$t_i,a_i,b_i\in\{-1,0,1\}$ 。

对于每一个 $t_i\ne 0$ 的 $i$ ，将他们分为三类：

1. $a_i=b_i=t_i$ 。
2. $a_i=t_i\ne b_i$ 或 $b_i=t_i\ne a_i$ 。
3. $a_i\ne t_i$ 且 $b_i\ne t_i$ 。

很明显，如果先执行二类操作，那么由于价值和损失的对称性，可以知道 $A$ 几乎就是 $0$ ，所以我们应该按照一二三的顺序执行操作。

一类和三类的操作是固定的，所以决策主要发生在二类操作。

我们充分发扬人类智慧：

根据数学直觉，最优解必定先让 $S_1$ 或 $S_2$ 疯涨到 $c$ 然后交替操作。

这样做跑的飞快，连 $n=10^4$ 时都可以在 $400ms$ 内搞定。

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int T,n,c,a[N],b[N],t[N];
int get1(int x){return (x>=c)+(x>=-c);}
int get2(int x){return -(x<=c)-(x<=-c);}
void WZH(){
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;i++)scanf("%d%d%d",t+i,a+i,b+i);
    int ans=0,S1=0,S2=0;
    for(int i=1;i<=n;i++)if(t[i]&&a[i]==t[i]&&b[i]==t[i])
        ans+=2*get1(S1),S1++,S2++;
    int cnt1=0,cnt2=0;
    for(int i=1;i<=n;i++)if(t[i]&&a[i]==t[i]&&b[i]!=t[i])cnt1++;
    for(int i=1;i<=n;i++)if(t[i]&&b[i]==t[i]&&a[i]!=t[i])cnt2++;
    int flag=0;
    if(max(cnt1,cnt2)>c-S1){
        int lim=c-S1+1;
      if(lim>0){
        for(int i=1;i<=lim;i++){
            if(cnt1>cnt2)ans+=get1(S1)+get2(S2),S1++,S2--;
            else ans+=get2(S1)+get1(S2),S1--,S2++;
        }
        if(cnt1>cnt2)cnt1-=lim,flag=1;
        else cnt2-=lim,flag=2;
      }
    }
    if(cnt1==cnt2){
        for(int i=1;i<=cnt1*2;i++){
            if(i&1^(flag==2))ans+=get1(S1)+get2(S2),S1++,S2--;
            else ans+=get1(S2)+get2(S1),S1--,S2++;
        }
    }
    else if(cnt1<cnt2){
        for(int i=1;i<=cnt1*2;i++){
            if(i&1^(flag==2))ans+=get1(S1)+get2(S2),S1++,S2--;
            else ans+=get1(S2)+get2(S1),S1--,S2++;
        }
        for(int i=cnt1+1;i<=cnt2;i++)ans+=get1(S2)+get2(S1),S2++,S1--;
    }
    else{
        for(int i=1;i<=cnt2*2;i++){
            if(i&1^(flag==2))ans+=get1(S1)+get2(S2),S1++,S2--;
            else ans+=get1(S2)+get2(S1),S1--,S2++;
        }
        for(int i=cnt2+1;i<=cnt1;i++)ans+=get1(S1)+get2(S2),S1++,S2--;
    }
    for(int i=1;i<=n;i++)if(t[i]&&a[i]!=t[i]&&b[i]!=t[i])
        ans+=get2(S1)+get2(S2),S1--,S2--;
    printf("%d\n",ans);
}
int main(){
    scanf("%d",&T);
    while(T--)WZH();
    return 0;
}