abc346

D - Gomamayo Sequence

给定 \(N\) 长的01字符串，使其满足，只有一个下标 \(i,S_{i}=S_{i+1}\)
对于 \(S_i\)，他改变的花费为 \(C_i\) ，若 \(S_i=0,则它变为1，否则变为0\)

因为只有一对相同的字符组(i,i+1)
维护 \(1-i\) 以 \(j\in{0,1}\) 结尾的 01交替 串 的花费
维护 \(i-结尾\) 以 \(j\in{0,1}\) 开头的 01交替串 的花费

再枚举i，有 \(S_i=S_{i+1}=0 \ or \ 1\)

def solve():
    N=I()
    S=list(map(int,input()))
    C=LI()
    dp_pre=[[0,0] for _ in range(N+1)]
    dp_suf=[[0,0] for _ in range(N+1)]
    for i in range(N):
        for j in range(2):
            dp_pre[i+1][j]=dp_pre[i][j^1]+(S[i]^j)*C[i]
    for i in range(N-1,-1,-1):
        for j in range(2):
            dp_suf[i][j]=dp_suf[i+1][j^1]+(S[i]^j)*C[i]
    ans=10**18
    for i in range(1,N):
        ans=min(ans,dp_pre[i][0]+dp_suf[i][0],dp_pre[i][1]+dp_suf[i][1])
    print(ans)

E - Paint

\(有H行W列的网格，M次操作\)
\(按顺序操作,将A行或A列的方块染色为X，最初方块颜色为0\)

可以发现如果顺着操作前面有些方块的颜色会被后面操作所覆盖掉
反之后面方块的颜色不会被前面的操作影响
也就是说倒着操作即可

void solve()
{
    int H,W,M;
    std::cin>>H>>W>>M;
    using ti = std::tuple<int, int, int>;
    std::vector<ti> qs(M);
    for(auto&[o,a,x]:qs){
        std::cin>>o>>a>>x;
    }
    std::reverse(qs.begin(),qs.end());

    std::set<int>r,c;
    const int N=2e5+1;
    std::vector<i64>ans(N);
    ans[0]=1LL*H*W;

    auto op1=[&](int a,int x){
        if(!r.insert(a).second){
            return;
        }
        int res = W - int(c.size());
        ans[x]+=res;
        ans[0]-=res;
    };
    auto op2 = [&](int a, int x) {
        if (!c.insert(a).second) {
            return;
        }
        int res = H - int(r.size());
        ans[x] += res;
        ans[0] -= res;
    };
    for(const auto&[o,a,x]:qs){
        if(o==1){
            op1(a,x);
        }
        else{
            op2(a,x);
        }
    }
    int cnt=0;
    for(int i=0;i<N;i++){
        cnt+=(ans[i]!=0);
    }
    std::cout<<cnt<<'\n';
    for(int i=0;i<N;i++){
        if(not ans[i]){
            continue;
        }
        std::cout<<i<<' '<<ans[i]<<'\n';
    }
}