[数位DP][二进制性质][异或][贪心] 百度之星初赛Round 2 1003 度度熊与运算式1


题意:给一堆1,中间由运算符 $op$ 隔开,$op$ 可能是按位异或 $\oplus$ 或者$?$, 问现在把 $?$ 换成 $\oplus$ 或者 $+$ ,能让整个运算式取最大的方案结果是多少?

题解:首先注意到一点是位运算优先级比异或运算高,这样的话显然我们可以把原来的不能更换的 $\oplus$ 当作分隔,把原式分割成一些段,现在的问题就是怎么处理这些段里的符号使得最后结果最大。

观察1:每个段的奇偶性只跟段内有多少个1有关,由此可得整个算式的奇偶性只跟1的个数有关。

观察2: 若一个段内有奇数个1,设为 $2n+1$, 那么这个段所有可能的情况为 1 3 5 … 2n+1;若一个段内有偶数个1,设为 $2n$ ,那么这个段所有的可能的情况为0 2 4 6 … 2n。

由观察2可得,若我们将答案的最后一位先忽略掉,那么每一小段可以遍比它小的任意一个数,如8可以取 2 4 6 8,去掉最后一位也就是/2之后即为1 2 3 4. 那么不难得到一个贪心的策略:利用类似数位dp的思想,每次合并的时候尽量让答案的每一个二进制位为1。 我们这样不断地处理前i个段,到第i+1段的时候考虑答案为cur,那么当cur与段长度 $cnt[i+1]$ 的第j位其中一个为1的时候,只管异或就行了,当二者均为1的时候,我们将cnt的那一位变成0并且记录借位flag(跟数位dp的full标签一样)为1,当都为0时,若没有借位那么我们无法使cnt的0变小,只能选择0的结果,否则我们可以让0变为1(这是前面分析的任取支撑的结果),如此处理每一个小段即可。

再来考虑上一部分忽略的最后一位,由观察1易知最后一位仅由数字的奇偶性决定,直接算就行了。
附上比赛时候写的很丑的代码。。但是一发yes hhh

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e3+5;
const ll mod=998244353;

int cnt[(1<<21)+5],top;
char str[(1<<21)+5];
int main()
{
    int t;
    cin>>t;
    while(t--){
        top=0;
        scanf(" %s",str);
        int len=strlen(str);
        cnt[++top]=1;
        for(int i=0;i<len;){
            if(str[i]=='^'){
                cnt[++top]=1;
                i++;
            }
            else{
                int j=i;
                while(j<len&&str[j]=='?') j++;
                cnt[top]+=j-i;
                i=j;
            }
        }
        int ans=0,cur=0,co=0;
        for(int i=1;i<=top;i++){
            int flag=0;
            if(cnt[i]&1) co++;
            if(cur<(cnt[i]%2==1?cnt[i]-1:cnt[i])){
                if(cnt[i]%2){
                    int tmp=cnt[i]-1;
                    cnt[i]=cur;
                    cur=tmp;
                }
                else{
                    swap(cnt[i],cur);
                }
            }
            for(int j=23;j>0;j--){
                if(((cur>>j)&1)==((cnt[i]>>j)&1)){
                    if(((cur>>j)&1)){
                        flag=1;
                        cur|=(1<<j);
                    }
                    else if(flag){
                        cur|=(1<<j);
                    }
                }
                else{
                    cur|=(1<<j);
                }
            }
            ans=max(ans,cur);
        }
        if(co&1) ans^=1;
        cout<<ans<<"\n";
    }
    return 0;
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据