好久没有写整套题的题解了呢……主要是这两天考试题愈发神仙实在是超出了垃圾博主的能力范围啊QAQ

A.异或

不难想到，如果我们得到了$[L,R]$中每一位上0和1的个数，那么答案即为$2 \times \sum \limits _{i=0} ^{\log R} num0[i]\times num1[i] \times 2^i$

所以可以得到一个暴力的思路，枚举$[L,R]$中的每个数按位统计。

现在瓶颈在于区间每一位的0/1个数的统计。如果我们把连续的数写成二进制表示，可以发现一些规律：

000000000000 //0

000000000001 //1

000000000010 //2

000000000011 //3

000000000100 //4

000000000101 //5

000000000110 //6

000000000111 //7

000000001000 //8

000000001001 //...

000000001010

000000001011

000000001100

000000001101

000000001110

000000001111

纵向对比。显然，对于一段连续的整数，它们每一位上的0/1分布是有循环节的，并且循环节内部前一半是0，后一半是1，且循环节长度为$2^{i+1}$。

所以我们可以轻松地求出从0到某个数这段区间里每一位的0/1 个数，相当与一个前缀和，$sum[R]-sum[L-1]$一下就好了。

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

typedef long long ll;

const ll mod=1e9+7;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

int T,L,R;

int bit[35][3];

void work()

{

    int L=read(),R=read();

    for(int i=0;i<31;i++)

    {

        bit[i][0]=bit[i][1]=0;

        int cir=(R+1)/(1<<i+1);

        bit[i][0]+=cir*(1<<i);

        bit[i][1]+=cir*(1<<i);

        int rest=(R+1)%(1<<i+1);

        bit[i][0]+=min(rest,1<<i);

        bit[i][1]+=max(0,rest-(1<<i));

        cir=(L)/(1<<i+1);

        bit[i][0]-=cir*(1<<i);

        bit[i][1]-=cir*(1<<i);

        rest=(L)%(1<<i+1);

        bit[i][0]-=min(rest,1<<i);

        bit[i][1]-=max(0,rest-(1<<i));

    }

    ll ans=0;

    for(int i=0;i<31;i++)

        (ans+=1LL*bit[i][0]*bit[i][1]%mod*(1LL<<i)%mod)%=mod;

    printf("%lld\n",ans*2%mod);

}

int main()

{

    T=read();

    while(T--)work();

    return 0;

}

B.取石子

首先，最优策略下，先手必败的下一步一定是先手必胜。

可以用类似于筛法(或者说dp也一样)得到所有先手必败的局面，从而得到答案。直接转移是$O(n^4)$的。

不难想到，给定$x,y$之后，使得$(x,y,z)$为先手必败态的$z$只有一个。

然后就可以$O(n^3)$了。

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

const int N=605,base=300;

bool win[base+5][base+5][base+5];

bool f[4][N][N],g[4][N][N],a[N][N];

int read()

{

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

	return x*f;

}

int T,x,y,z;

bool judge(int i,int j,int k)

{

	if(a[j-i+base][k-j+base])return 1;

	if(f[0][j][k])return 1;

	if(f[1][i][k])return 1;

	if(f[2][i][j])return 1;

	if(g[0][i][k-j+base])return 1;

	if(g[1][j][k-i+base])return 1;

	if(g[2][k][j-i+base])return 1;

	return 0;

}

void ini()

{

	for(int i=0;i<=base;i++)

		for(int j=0;j<=base;j++)

			for(int k=0;k<=base;k++)

			{

				if(judge(i,j,k))win[i][j][k]=1;

				else

				{

					a[j-i+base][k-j+base]=1;

					f[0][j][k]=f[1][i][k]=f[2][i][j]=1;

					g[0][i][k-j+base]=g[1][j][k-i+base]=g[2][k][j-i+base]=1;

				}

				//cout<<i<<' '<<j<<' '<<k<<' '<<win[i][j][k]<<endl;

			}

}

void work()

{

	x=read();y=read();z=read();

	if(win[x][y][z])puts("Yes");

	else puts("No");

}

int main()

{

	//freopen("my.out","w",stdout);

	ini();

	T=read();

	while(T--)work();

	return 0;

}

C.优化

性质1：绝对值可以直接拆，不会使答案变差。

性质2：除了开头和结尾，中间几段都紧密相连显然最优。

先把绝对值扔了，然后把每个$s_i$单独拿出来，考虑它的贡献。

除了$s_1,s_k$之外，每个$s$产生的系数只能为0或2或-2。

进一步观察还可以发现，两个系数为2的$s$之间，必然存在一段系数为-2的$s$。

系数为0的可以自由穿插在2和-2之间，所以我们可以把阶段划分成4种。最高点(2)，最低点(-2)，上升段(-2~2)，下降段(2~-2)。

那么就可以转移了，看似要$O(n^2 k)$或者$O(n^3 k)$，但考虑到每一段内部每个数的系数都是一样的，所以直接对于每个点判断它在不在这里断段就好了。

$a[]$中可能有负数，所以初始化需要$-inf$。

$O(nk)$。

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

const int N=3e4+5;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

int n,a[N],K;

int dp[N][202][5];

int main()

{

    n=read();K=read();

    for(int i=1;i<=n;i++)

        a[i]=read();

    memset(dp,-0x3f,sizeof(dp));

    for(int i=0;i<=n;i++)

        for(int j=0;j<4;j++)

            dp[i][0][j]=0;

    for(int i=1;i<=n;i++)

    {

        for(int j=1;j<=min(K,i);j++)

        {

            int p=(j==1||j==K)?1:2;

            dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j-1][2])+p*a[i];

            dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][3])-p*a[i];

            dp[i][j][2]=max(dp[i-1][j][2],dp[i][j][1]);

            if(j!=1&&j!=K)dp[i][j][2]=max(dp[i][j][2],dp[i-1][j-1][2]);

            dp[i][j][3]=max(dp[i-1][j][3],dp[i][j][0]);

            if(j!=1&&j!=K)dp[i][j][3]=max(dp[i][j][3],dp[i-1][j-1][3]);

            /*cout<<i<<' '<<j<<endl;

            for(int k=0;k<4;k++)cout<<dp[i][j][k]<<' ';

            puts(" ");*/

        }

    }

    int ans=max(dp[n][K][2],dp[n][K][3]);

    printf("%d\n",ans);

    return 0;

}

巴特西

[CSP-S模拟测试86]题解

A.异或

B.取石子

C.优化

最新文章

热门文章