Codeforces Round 885 (Div. 2) A–E

~~感受数学的威力吧~~

A. Vika and Her Friends

题意

在一个 $n\times m$ 的棋盘上，小 A 站在位置 $(x,y)$ ，还有 $k$ 个小 A 的朋友，分别在 $(x_1,x_2),\ldots,(x_k,y_k)$ 。

每一秒，小 A 先向四周走一步，然后每个朋友根据小 A 的行动自己走一步。当在某一秒末尾，小 A 和某个朋友的坐标重合，那么这个朋友就抓到了小 A。

求是否有朋友能抓到小 A。

解法

朋友能抓到小 A 的充要条件是初始状态下，他们的曼哈顿距离为偶数。我们来说明一下：

不难发现，无论朋友和小 A 怎么动，他们的曼哈顿距离都只会变化偶数，所以若初始曼哈顿距离为奇数，则一定抓不到。

接下来只需要证明当曼哈顿距离是偶数的时候一定能抓到。
由于这个场地有边界，直观感受小 A 和朋友的距离不可能保持无限不变（我不会证明，但这就是 OI 的特点，能猜就行了），因此偶数一定有解。 $\square$

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int x,y;
void solve(int kase){
    int n=read(),m=read(),k=read();
    x=read(),y=read();

    bool ans = 0;
    for(int i=0;i<k;i++){
        int xx=read(),yy=read();
        if((abs(xx-x)+abs(yy-y))%2==0){
            ans=1;
        }
    }
    if(ans)NO;
    else YES;
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

B. Vika and the Bridge

题意

在一座桥上有 $n\ (1\le n \le 2\cdot 10^5)$ 块木板，每块木板都有自己的颜色 $c_i\ (1\le c_i \le k \le n)$ ，现在小 A 可以把一块木板染成任意颜色。

小 A 要过桥，但是他只能踏在同一种颜色的木板上，求在染色后，他在过桥过程中需要最大连续跳过的木板数的最小值。

解法

阅读理解。虽然可能有一点点像二分答案，但其实不是。

我们可以枚举小 A 到底要走哪个颜色的木板，不难发现，这个染色的机会一定是放在空隙最大的两个木板的正中间的。因此，我们维护每个颜色的空隙前二大（因为染色后可能最大的空隙没有第二大空隙大了），然后枚举每个颜色，取最小值即可。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 2e5+5;
int val[N][2]; // 空隙前 2 大
int lastpos[N]; // 颜色最后出现的位置

void solve(int kase){
    int n=read(),k=read();
    for(int i=1;i<=k;i++){
        lastpos[i]=0;
        val[i][0]=val[i][1]=0;
    }

    for(int i=1;i<=n;i++){
        int c=read();
        int dis = i-lastpos[c]-1;
        lastpos[c]=i;

        if(dis>val[c][0]){
            val[c][1]=val[c][0];
            val[c][0]=dis;
        }
        else if(dis>val[c][1]){
            val[c][1]=dis;
        }
    }
    for(int i=1;i<=k;i++){
        if(!lastpos[i])continue;

        int pos = n+1;
        int dis = pos-lastpos[i]-1;

        if(dis>val[i][0]){
            val[i][1]=val[i][0];
            val[i][0]=dis;
        }
        else if(dis>val[i][1]){
            val[i][1]=dis;
        }
    }

    int ans = INT_MAX;
    for(int i=1;i<=k;i++){
        if(!lastpos[i])continue;
        ans = min(ans, max(val[i][0]/2,val[i][1]));
    }
    printf("%d\n",ans);
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

C. Vika and Price Tags

题意

有长度为 $n\ (1\le n\le 10^5)$ 的序列 $a,b\ (0\le a_i,b_i\le 10^9)$ 。每次可以进行一次操作，使得 $c_i=|a_i-b_i|$ ，然后 $b$ 成为新的 $a$ ， $c$ 成为新的 $b$ ，如此循环往复。请问能否在进行有限次操作后使得 $a$ 全为 $0$ 。

解法

首先，不难发现这 $2n$ 个数在序列内部是没有关联的，我们只需要考虑 $n$ 对二元组 $(a_i,b_i)$ 即可。

我们先证明第一个命题：不论 $a_i,b_i$ 如何取值，最后都能成为 $0$ 。
证明：若 $a_i,b_i$ 中有 $0$ ，则命题成立，否则 $c_i=|a_i-b_i|<\max(a_i,b_i)$ ，因此两个数的最大值是严格递减的，因此在有限次操作后一定会减到 $0$ 。 $\square$

我们再证明第二个命题，若 $a_i,b_i$ 不同为 $0$ ，则进行操作到后面 $0$ 一定以 $3$ 为周期出现。
证明：如果现在 $(a,b)=(a,0)$ ，那之后就会变为 $\{a,0,a,a,0,a,a,0,a,a,0\}$ ，所以 $3$ 为周期出现。 $\square$

由这两个命题，我们可以推出本题的结论：有解当且仅当 $a_i,b_i$ 不同为 $0$ 的二元组中， $0$ 的出现位置对 $3$ 求余全部相同。

则问题就转化为，给定 $a,b$ ，求进行几次操作之后可以得到 $0$ 。如果直接模拟，复杂度是 $O(\max\{a,b\})$ 的。

怎么做——找规律：

不妨以 $100,1$ 作为开始，写出这个序列。 $\{100,1,99,98,1,97,96,1,95,94,\ldots\}$ ，你是不是发现了什么规律？
反正我发现了：当 $a>b$ 时，序列可以看作 $\{a,b,a-b,a-2b,b,a-3b,a-4b,b,\ldots\}$ 。
若 $a<b$ ，进行一次操作后就可以转化为 $a>b$ 的情况。

于是我们考虑递归求解。设 $a=kb+r$ ，则在进行几部操作后，就会变成 $(r,b)$ 或者 $(b,r)$ ，这和欧几里得算法一样，复杂度是 $O(\log a)$ 的。因此本题可以在 $O(n\log a_i)$ 复杂度完成，这是足够的。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int solve(int a,int b){ // 递归求解
    if(a==0)return 0;
    if(b==0)return 1;
    if(a<b)return (solve(b,abs(a-b))+1)%3;

    int k=a/b, r=a%b;

    int step=k+k/2;
    if(k%2==0)step+=solve(r,b);
    else step+=solve(b,r);
    return step%3;
}

const int N = 1e5+5;
int a[N],b[N];
int res[N];
void solve(int kase){
    int n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)b[i]=read();

    for(int i=1;i<=n;i++){
        if(a[i]==0 && b[i]==0)res[i]=-1;
        else res[i] = solve(a[i],b[i]);
    }

    int ans = -1;
    for(int i=1;i<=n;i++){
        if(res[i]==-1)continue;
        if(ans==-1)ans=res[i];
        else if(ans!=res[i]){
            puts("NO");
            return;
        }
    }
    puts("YES");
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

线性解法

找规律找出来的，但是我不会证明，仅供参考。函数 xxx 实现了对 $(a_i,b_i)$ 中 $0$ 的位置的求解。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int lowbit(int x){return x&(-x);}
int xxx(int a,int b){
    if(b%2==1){
        if(a%2==0)return 0;
        return 2;
    }

    int cnt1=lowbit(b)-1;
    int len=cnt1*2+1+1;

    a = (a-1)%len+1;
    if(a<=cnt1)return 1;
    if(a==cnt1+1)return 2;
    if(a<=cnt1*2+1)return 1;
    return 0;
}

const int N = 1e5+5;
int a[N],b[N];
int res[N];
void solve(int kase){
    int n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)b[i]=read();

    for(int i=1;i<=n;i++){
        if(a[i]==0 && b[i]==0){
            res[i]=-1;
        }else if(a[i]==0){
            res[i]=0;
        }else if(b[i]==0){
            res[i]=1;
        }
        else res[i] = xxx(a[i],b[i]);
    }

    int ans = -1;
    for(int i=1;i<=n;i++){
        if(res[i]==-1)continue;
        if(ans==-1)ans=res[i];
        else if(ans!=res[i]){
            puts("NO");
            return;
        }
    }
    puts("YES");
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

D. Vika and Bonuses

简单题。比 C 简单。

题意

有一个正整数 $s(s\le 10^9)$ ，你可以执行 $n\ (1\le n \le 10^9)$ 次操作。
初始答案为 0，每次操作可以两个中选择一个：

$s\leftarrow s+s\bmod 10$ 。
往答案加上 $s$ 。

求答案的最大值。

解法

不难证明最优解一定是先执行若干次操作 1，然后再全部执行操作 2。因为如果执行操作 2 再执行了操作 1，是亏的，不如先执行操作 1。

接下来考虑 $s\leftarrow s+s\bmod 10$ ，有关整数的尾数可以看作两个大的循环，一个循环是 5->0->0->0->...。
另一个循环是 2->4->8->6。其他数都可以挂上这个循环 3->6,7->4, 9->8。

所以先特判：

$s$ 的尾数是 $0$ ，答案一定是 $sn$ 。（因为操作 1 没有意义）
$s$ 的尾数是 $5$ ，答案是 $\max(sn,(s-5)(n-1))$ 。（因为操作 1 最多执行一次）

接下来，我们将 $n \le 100$ 的全部模拟掉，这样就不用处理 $n$ 极小的 corner-case 了。

接下来， $n$ 已经保证足够大了，我们先不断执行操作，直到 $s$ 的尾数变为 $6$ 。这样执行操作 $1$ ，增加的数以 $4$ 为周期。

执行了 $4k\ (k\ge 0)$ 次操作：答案为 $(s+20k)(n-4k)$ 。
执行了 $4k+1\ (k\ge 0)$ 次操作：答案为 $(s+6+20k)(n-1-4k)$ 。
执行了 $4k+2\ (k\ge 0)$ 次操作：答案为 $(s+8+20k)(n-2-4k)$ 。
执行了 $4k+3\ (k\ge 0)$ 次操作：答案为 $(s+14+20k)(n-3-4k)$ 。

我们只需要求出这四个关于 $k$ 的二次函数极值即可。直接求出对称轴，暴力取对称轴周围 5 个整数，一定能取到最大值。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

ll max_2func(ll a,ll b,ll c){
    // printf("%lld %lld %lld\n",a,b,c);

    ll k = -b/(a*2); // 对称轴

    ll around=2; // 由于浮点舍入会有误差，我们取对称轴周围(2*around+1)个点
    k=max(k,around); // 如果对称轴在左边，强行拉到右边，因为x>=0
    ll maxn = 0;
    for(ll x=k-around;x<=k+around;x++){
        maxn=max(maxn,a*x*x+b*x+c);
    }   
    return maxn;
}

void solve(int kase){
    ll x=read(),n=read();
    if(x%10==5){
        printf("%lld\n",max(x*n,(x+5)*(n-1)));
        return;
    }
    else if(x%10==0){
        printf("%lld\n",x*n);
        return;
    }

    if(n<=100){
        ll ans = 0;
        while(n){
            ans = max(ans,x*n);
            x+=x%10;n--;
        }
        printf("%lld\n",ans);
        return;
    }   
    
    ll ans = 0;
    while(x%10!=6){
        ans = max(ans,x*n);
        x+=x%10;n--;
    }


    // 执行 4k 次操作 (k>=0) val = (x+20k)*(n-4k)
    ans = max(ans,max_2func(-80,-4*x+20*n,x*n));
    // 执行 4k+1 次操作 (k>=0) val = (x+20k+6)*(n-1-4k)
    ans = max(ans,max_2func(-80,-4*(x+6)+20*(n-1),(x+6)*(n-1)));
    // 执行 4k+2 次操作 (k>=0) val = (x+20k+8)*(n-2-4k)
    ans = max(ans,max_2func(-80,-4*(x+8)+20*(n-2),(x+8)*(n-2)));
    // 执行 4k+3 次操作 (k>=0) val = (x+20k+12)*(n-3-4k)
    ans = max(ans,max_2func(-80,-4*(x+12)+20*(n-3),(x+12)*(n-3)));

    printf("%lld\n",ans);
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}