ARC152-526互联

ARC152

小偷一个懒?

A

贪心地放即可

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n;
int a[MAXN],L;
signed main()
{
    // freopen("date.in","r",stdin);
    // freopen("date.out","w",stdout);
    scanf("%d %d",&n,&L);
    int Cnt1=0,Cnt2=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]==2)
        {
            if(L<2)
            {
                printf("No");
                return 0;
            }
            L-=3;
        }
        else
        {
            L-=2;
        }
    }
    printf("Yes");
}

B

结论题

如果第一次相遇的地方是\(p\),则第二次相遇理论上应该在\(L-p\)的地方相遇

直接让起点作为第一次相遇的地方即可

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n;
int a[MAXN];
int L;

int main()
{
    // freopen("date.in","r",stdin);
    // freopen("date.out","w",stdout);
    scanf("%d %d",&n,&L);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    int Res=1e9;
    for(int i=1;i<=n;i++)
    {
        int to=L-a[i];
        int Lw=lower_bound(a+1,a+1+n,to)-a;
        if(Lw!=n+1)
        {
            Res=min(Res,a[Lw]-to);
        }
        
        int Up=upper_bound(a+1,a+1+n,to)-a-1;
        if(Up)
        {
            Res=min(Res,to-a[Up]);
        }
    }
    printf("%lld\n",2ll*(L+Res));
}

C

有点意思的题

首先这个问题相当于在数轴上选一个基点反转

因此最大值最小值的距离是不变的

那个不能翻到负数的条件可以多次反转最大值到极远处

考虑反转一次一次\(i\)对答案的增量\(b_i=|a_n+a_1-2a_i|\)

这个可以看作\(a_n-a_1+(a_1+\sum\limits k_ib_i)\),这个式子最小正整数为\(a_n-a_1+(a_1\bmod \gcd(b_i))\)

#include<bits/stdc++.h>
using namespace std;
int Abs(int x)
{
    return x>0?x:-x;
}
const int MAXN=2e5+5;
int n;
int a[MAXN];

int main()
{
    // freopen("date.in","r",stdin);
    // freopen("date.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    int d=0;
    int g=0;
    for(int i=1;i<=n;i++)
    {
        g=__gcd(g,Abs(a[1]+a[n]-2*a[i]));
    }
    printf("%d",a[n]-a[1]+(a[1]%g));
}

D

考虑\(x\rightarrow (x+k)\bmod n\)

这样会连出来\(\gcd(n,k)\)个环

然后一张图一目了然 121

蓝红是选连的边,绿黄是产生的边

特判一下一行的情况

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+5;
int n,k;
signed main()
{
    // freopen("date.in","r",stdin);
    // freopen("date.out","w",stdout);
    scanf("%lld %lld",&n,&k);
    if((n%2==0))
    {
        printf("-1");
        return 0;
    }
    int Cnt=(__gcd(n,k));
    printf("%lld\n",n/2);
    if(Cnt==1)
    {
        for(int i=0;i<n-1;i+=2)
        {
            printf("%lld %lld\n",((long long)i*k)%n,((long long)(i+1)*k)%n);
        }
        return 0;
    }
    int Len=n/Cnt;
    for(int i=0;i<Cnt-1;i++)
    {
        for(int j=0;j<Len-1;j+=2)
        {
            printf("%lld %lld\n",(i+j*k)%n,((i+1)+(j+1)*k)%n);
        }
    }

    for(int i=1;i<Len;i+=2)
    {
        printf("%lld %lld\n",(i*k)%n,(i*k+1)%n);
    }
    for(int i=1;i<Cnt-1;i+=2)
    {
        printf("%lld %lld\n",i%n,(i+1)%n);
    }
    
    
}

beginner atcoder contest 152