题解：P10524 [XJTUPC 2024] 循环移位

wangyizhi · 2025-03-12 21:12:00 · 题解

题目传送门

很神奇的一个题目！

但感觉可以蓝？

题目分析

固定原序列，则就是序列 0,1,...,2^n-1 在上面滚动

考虑对于第 i 位，原序列就是：

其中，每个循环节长 2^{i+1}。

我们可以先暴力计算出第一串 0 从 0 开始的值，然后开始滚动这串数。

注意到滚动一次之后，只会有 2^{n-i} 个数发生了改变，这几个数我们也可以暴力更新答案。

但是我们发现，事实上我们只需要求出第一串 0 在第一个循环节内的结果就行了。

因此总的时间复杂的只有 O(2^{n+1})。

最后做个类似前缀和的东西就做完了。

AC Code

可能常数有点大。。。

//by wangyizhi(571247)
#include<bits/stdc++.h>
//#include<bits/extc++.h>
using namespace std;
using ll=long long;
using ld=long double;
#define int ll
using pii=pair<int,int>;
//bool Mst;
int n,a[1<<20],f[20][1<<20];
int solve1()
{
    memset(f,0,sizeof(f));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<(1<<n);j++) f[i][0]+=((a[j]^j)&(1<<i));
        for(int j=1;j<(1<<(i+1));j++)
        {
            f[i][j]=f[i][j-1];
            for(int k=j-1;k<(1<<n);k+=(1<<(i+1))) f[i][j]-=(a[k]&(1<<i)),f[i][j]+=(a[k]&(1<<i))^(1<<i);//将0改为1
            for(int k=(j-1)^(1<<i);k<(1<<n);k+=(1<<(i+1))) f[i][j]-=(a[k]&(1<<i))^(1<<i),f[i][j]+=(a[k]&(1<<i));//将1该为0
        }
    }
    int ans=0;
    for(int i=1;i<n;i++) for(int j=0;j<(1<<(i+1));j++) f[i][j]+=f[i-1][j&((1<<i)-1)];
    for(int i=0;i<(1<<n);i++) ans=max(ans,f[n-1][i]);
    return ans;
}
int solve2()
{
    memset(f,0,sizeof(f));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<(1<<n);j++) f[i][0]+=((a[j]&j)&(1<<i));
        for(int j=1;j<(1<<(i+1));j++)
        {
            f[i][j]=f[i][j-1];
            for(int k=j-1;k<(1<<n);k+=(1<<(i+1))) f[i][j]+=(a[k]&(1<<i));
            for(int k=(j-1)^(1<<i);k<(1<<n);k+=(1<<(i+1))) f[i][j]-=(a[k]&(1<<i));
        }
    }
    int ans=0;
    for(int i=1;i<n;i++) for(int j=0;j<(1<<(i+1));j++) f[i][j]+=f[i-1][j&((1<<i)-1)];
    for(int i=0;i<(1<<n);i++) ans=max(ans,f[n-1][i]);
    return ans;
}
int solve3()
{
    memset(f,0,sizeof(f));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<(1<<n);j++) f[i][0]+=((a[j]|j)&(1<<i));
        for(int j=1;j<(1<<(i+1));j++)
        {
            f[i][j]=f[i][j-1];
            for(int k=j-1;k<(1<<n);k+=(1<<(i+1))) f[i][j]+=(a[k]&(1<<i))^(1<<i);
            for(int k=(j-1)^(1<<i);k<(1<<n);k+=(1<<(i+1))) f[i][j]-=(a[k]&(1<<i))^(1<<i);
        }
    }
    int ans=0;
    for(int i=1;i<n;i++) for(int j=0;j<(1<<(i+1));j++) f[i][j]+=f[i-1][j&((1<<i)-1)];
    for(int i=0;i<(1<<n);i++) ans=max(ans,f[n-1][i]);
    return ans;
}
//bool Med;
signed main()
{
//  cerr<<"Memory Size: "<<abs((&Med)-(&Mst))/1024.0/1024<<" MB\n";
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=0;i<(1<<n);i++) cin>>a[i];
    cout<<solve1()<<" "<<solve2()<<" "<<solve3()<<"\n";
    return 0;
}