稍加改动,为何就能过呢?
查看原帖
稍加改动,为何就能过呢?
549521
boy♂Next♂dooor楼主2024/1/6 11:31

麻烦看一下原来这样优化成logm不改就过不了 为什么?thx qwq

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
int t;
pair<string,int> a[100001];
ll v,atk;
int cal(int b,int num)
{
    for(int i=1;i<=n;i++)
    {
        int t=a[i].second>>b&1;
        if(a[i].first=="OR") num|=t;
        else if(a[i].first=="XOR") num^=t;
        else num&=t;
    }
    return num;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        string op1;
        cin>>op1>>t;
        a[i]=make_pair(op1,t);
    }
    double p1=log(m)/log(2);
    int p=floor(p1);//这个p就是logm
    for(int b=p;b>=0;b--)//就是这里若把p换成m=1e9时p的最大值29就可以AC 但如果就这样保留p就不行 为什么呢?
    {
        int r0=cal(b,0);
        int r1=cal(b,1);
        if(v+(1<<b)<=m && r0<r1)//b要是超过p那1<<p不一定大于m了吗?那大于p到29这一部分还有意义吗?
        {
            v+=(1<<b);
            atk+=r1<<b;
        }
        else
        {
            atk+=r0<<b;
        }
    }
    cout<<atk<<endl;
    return 0;
}


2024/1/6 11:31
加载中...