1 条题解

  • 0
    @ 2024-6-19 15:20:37

    30分:n20n\leq 20

    爆搜即可。

    30分:n1000,ai<128n\leq 1000,a_i< 128

    dpi,j,kdp_{i,j,k}表示我考虑了前ii个位置,用了jj|,能否让结果为kk,记录决策后,沿着决策进行bfs最小字典序即可。

    或者我们也可以反过来,记dpi,j,kdp_{i,j,k}表示从ii开始向后,当前的值是kk,一共用了jj|,最终答案最大是多少。然后从起点开始贪心。

    (这个部分实际上不好拿)

    10分:k=1k=1

    我们枚举kk放在哪个位置,通过计算区间内每一位上有多少个11,就可以快速得到答案。

    正解

    首先,考虑这样一个结论:任意时刻,肯定都是把&\&放前面,|放后面,结果能取得最大的。

    原因很简单:假设有三个相邻的位置x,y,zx,y,z,左边是|,右边是&\&,那么结果最大是zz,假设左边是&\&,右边是|,那么结果最小是zz。所以我们调整使得整个序列不存在&\&|后,一定不会使得答案变差。

    那么我们就可以考虑按位贪心了:

    对于当前位置来说,如果能放|,且放了|之后,后续的最大答案依旧是理论最大值,则放|,否则放&\&

    #include<bits/stdc++.h>
    #define ll long long
    #define maxn 200005
    using namespace std;
    int n,k;
    ll a[maxn],sum[maxn][63];
    ll check(int l,ll now,int k)
    {
    	//[n-k+1,n]这一段是|,[l,n-k]这一段是&
    	if (l<=n-k)
    	{
    		ll tt[63]={0};
    		for (int i=0;i<60;i++) tt[i]=sum[n-k][i]-sum[l-1][i];
    		for (int i=0;i<60;i++) if (tt[i]!=(n-k-l+1) && ((now>>i)&1)) now^=(1ll<<i);
    	} 
    	if (n-k+1<=n)
    	{
    		ll tt[63]={0};
    		for (int i=0;i<60;i++) tt[i]=sum[n][i]-sum[n-k][i];
    		for (int i=0;i<60;i++) if (tt[i]) now|=(1ll<<i);
    	}
    	return now;
    }
    int main()
    {
    	cin>>n>>k;
    	for (int i=1;i<=n;i++) cin>>a[i];
    	for (int i=1;i<=n;i++)
    	{
    		for (int j=0;j<60;j++) sum[i][j]=sum[i-1][j];
    		for (int j=0;j<60;j++) if ((a[i]>>j)&1) sum[i][j]++;
    	}
    	//2往后最后k个是|,其他是&,初始时候是a[1]的结果
    	ll zd=check(2,a[1],k); 
    	cout<<zd<<endl;
    	int nowk=k; ll ans=a[1];
    	for (int i=2;i<=n;i++)
    	{
    		if (nowk>=1 && check(i+1,ans|a[i],nowk-1)==zd)
    		{
    			cout<<"|";
    			ans=ans|a[i]; nowk--;
    		}
    		else
    		{
    			cout<<"&";
    			ans=ans&a[i];
    		}
    //		cout<<i<<" "<<ans<<" "<<nowk<<endl;
    	}
    	cout<<endl;
    	if (ans!=zd) while (1);
    }
    
    • 1

    信息

    ID
    1427
    时间
    1000ms
    内存
    512MiB
    难度
    9
    标签
    (无)
    递交数
    178
    已通过
    12
    上传者