文章目录

• A. * Break
• B. Repainting Street
• C. Bouncing Ball
• D. XOR-gun

A. * Break

取该点和四个角的曼哈顿距离最大值即可。

#include <bits/stdc++.h>
using namespace std;
int t;
int main()
{
    cin>>t;
    while(t--)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        int x=abs(1-c)+abs(1-d);
        int y=abs(1-c)+abs(b-d);
        int z=abs(a-c)+abs(1-d);
        int q=abs(a-c)+abs(b-d);
        cout<<max(max(x,y),max(z,q))<<endl;
    }
    return 0;
}

B. Repainting Street

最多只有一百种颜色，所以直接枚举每种颜色，看需要多少次，取最少的即可。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int inf=0x3f3f3f3f;
int t;
int k,n;
int c[N];
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        for(int i=1;i<=n;++i)
            cin>>c[i];
        int mi=inf;
        for(int i=1;i<=100;++i)
        {
            int ans=0;
            int cnt=0;
            for(int j=1;j<=n;++j)
            {
                if(c[j]!=i||cnt)
                {
                    cnt++;
                    if(cnt==k)
                    {
                        ans++;
                        cnt=0;
                    }
                }
            }
            if(cnt)
                ans++;
            mi=min(mi,ans);
        }
        printf("%d\n",mi);
    }
    return 0;
}

C. Bouncing Ball

从后往前，预处理 nxt 数组，nxt[i] 表示从 i 开始，i+k，i+2k…有多少是没有平台的。

之后就可以O(n)的计算出从每一个开始跳的花费是多少，取最小值即可。(当然选择某个平台作为开始，有时需要删除前面的某些平台，这部分花费也要算上)。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int inf=0x3f3f3f3f;
int t;
char a[N];
int nxt[N];
int n,p,k;
int x,y;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&p,&k);
        scanf("%s",a);
        scanf("%d%d",&x,&y);
        int len=strlen(a);
        nxt[len]=0;
        for(int i=len-1;i>=0;i--)
        {
            if(a[i]=='0')
            {
                nxt[i]=nxt[min(len,i+k)]+1;
            }
            else
            {
                nxt[i]=nxt[min(len,i+k)];
            }
        }
        int mi=inf;
        for(int i=p;i<=n;++i)
        {
            int ans=(i-p)*y;
            ans+=nxt[i-1]*x;
            mi=min(ans,mi);
        }
        printf("%d\n",mi);
    }
    return 0;
}

D. XOR-gun

我们知道，对于一个非减序列，如果有连续三个最高位1的位置相同的话，异或后两个，必定会产生一个比第一个数要小的数。又因为a_i>=1，所以如果有>64个数组成的非减序列，必定会有产生连续三个最高位1的位置是相同的(因为a_i<=1e9，所以最多也就32位数)。知道这个后，我们对于n>64，就可以直接输出1即可。那么对于n<=64的，因为n很小，所以O(n³)完全没问题。这里我是随便取一段连续序列，然后一分为2，前面异或后和后面异或后比较，如果前面大于后面就满足。为什么一定是连续的序列一分为2，不是可以两个不挨着的部分比较呢。原因是这样的，如果是两个不挨着的部分产生了前面大于后面，那么对于中间的数，其如果比后面的小，那就可以直接和前面的产生前面大于后面。如果比后面的大，那也可以直接和后面的产生前面大于后面。(这样肯定会贡献更小的答案)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105;
int n;
ll a[N];
ll sum[N];
int main()
{
    cin>>n;
    if(n>64)
    puts("1");
    else
    {
        for(int i=1;i<=n;++i)
        {
            cin>>a[i];
            sum[i]=sum[i-1]^a[i];
        }
        int ans=n;
        for(int i=1;i<=n;++i)
            for(int j=i;j<=n;++j)
                for(int k=j+1;k<=n;++k)
                    if((sum[j]^sum[i-1])>(sum[k]^sum[j]))
                        ans=min(k-i-1,ans);
        if(ans==n)
        puts("-1");
        else
        printf("%d\n",ans);
    }
    return 0;
}