专栏文章

P14015 [ICPC 2024 Nanjing R] 生日礼物 题解

JJorisyKuno Kako
P14015题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miny4um9
此快照首次捕获于
2025/12/02 10:15
3 个月前
此快照最后确认于
2025/12/02 10:15
3 个月前
查看原文
在比赛现场，因为我这个题写了一个假做法，浪费了整个队 1h+ 的时间，最终 B 也没调出来，K 也没写完，5 题变 3 题，Ag 变 Cu。最后我为队伍贡献了 0 个题。
最初我只是以为我没见过这个 trick，直到某天翻阅自己写过的题解时，当时发现我在大半年做过一个几乎一模一样的 trick 题。
我再也不会忘记这个 trick 了。
考虑对原串翻转偶数位，这样第二个操作就变成了删去一个子串 01\tt01 或 10\tt10。那么最后整个串一定是全 0\tt0 或全 1\tt1 的形式。
设字符串原来 0,1,2\tt0,1,2 的个数为 c0,c1,c2c_0,c_1,c_2。由于删子串的操作不会改变 ∣c0−c1∣|c_0-c_1|，因此对 c2c_2 和 ∣c0−c1∣|c_0-c_1| 的大小关系讨论即可。
若 c2<∣c0−c1∣c_2<|c_0-c_1|，那么贪心地将 2\tt 2 改为 0,1\tt 0,1 中个数更少的那个，答案即为 ∣c0−c1∣−c2|c_0-c_1|-c_2。
否则，按上述贪心会多下来一些 2\tt 2，自然是 0,1\tt 0,1 交替改，去抵消，答案即为 (∣c0−c1∣+c2) mod 2(|c_0-c_1|+c_2)\bmod 2。
时间复杂度 O(n)O(n)。
CPP
#include<bits/stdc++.h>
using namespace std;

string s;

void sol()
{
    cin>>s;
    for(int i=1;i<s.size();i+=2)
    {
        s[i]=s[i]=='0'?'1':s[i]=='1'?'0':'2';
    }
    int s0=0,s1=0,s2=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='0') s0++;
        else if(s[i]=='1') s1++;
        else s2++;
    }
    int d=abs(s0-s1);
    if(s2>=d) cout<<(s2+d&1)<<endl;
    else cout<<d-s2<<endl;
}

int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int t;
    cin>>t;
    while(t--) sol();
    return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...