施工中。。。

1146C Tree Diameter

题意

交互题。有一棵 \(n(n\le 100)\) 个点的树，你可以进行不超过 \(9\) 次询问，每次询问两个点集中两个不在同一点集的点的最大距离。求树的直径。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题解

和 GXOI2019旅行者 基本类似，二进制分组，对于每一位，编号当前位为 \(0\) 的分到一组，当前位为 \(1\) 的分到另一组。最大询问次数为 \(\log 100 = 7\)

code

#include<cstdio>
int v1[105],v2[105];
int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        int n,ans=0; scanf("%d",&n);
        for(int i=0;i<=6;++i)
        {
            int id1=0,id2=0;
            for(int j=1;j<=n;++j) (j&(1<<i))?v1[++id1]=j:v2[++id2]=j;
            if(id1&&id2)
            {
                printf("%d %d ",id1,id2);
                for(int i=1;i<=id1;++i) printf("%d ",v1[i]);
                for(int i=1;i<=id2;++i) printf("%d ",v2[i]);
                puts(""); fflush(stdout);
                int x; scanf("%d",&x);
                if(x>ans) ans=x;
            }
        }
        printf("-1 %d\n",ans);
        fflush(stdout);
    }
}

1146D Frog Jumping

题意

有一条数轴，一只青蛙在原点，可以向前跳 \(a\) 步或向后跳 \(b\) 步。

定义 \(f(x)\) 表示青蛙在 \([0,x]\) 里跳，能跳到的点数。

求 \(\sum_{i=0}^m f(i)\) 。 \(m\le 10^9, a,b\le 10^5\) 。

题解

能到达的点 \(c\) 能被表示为 \(ax-by=c\) 。

根据裴蜀定理，能到达的点一定是 \(\gcd(a,b)\) 的倍数。

但是，当 \(i<a+b\) 时，\(f(i)\) 由于跳的点不能超过 \(i\) ，有的点可能会无法跳到。故 \(f(0)\sim f(a+b)\) 的答案我们要另外计算。

我们考虑贪心的去跳，当跳的步数 \(>b\) 就减去 \(b\) 。暴力枚举 \(i\) 统计有多少个点能到达即可。

注意不要重复统计答案。

code

#include<cstdio>
int gcd(int x, int y) {
    return y?gcd(y,x%y):x;
}
const int N=2e5+5;
bool vis[N];
int step[N],tot;
int main()
{
#ifndef ONLINE_JUDGE
    freopen("sol.in","r",stdin);
#endif
    int m,a,b;
    scanf("%d%d%d",&m,&a,&b);
    const int g=gcd(a,b);
    long long ans=1ll*(1+m/g+1)*(m/g+1)/2ll*g-1ll*(1ll*(m/g+1)*g-m-1)*(m/g+1);
    vis[step[++tot]=0]=true;
    while(true)
    {
        ++tot;
        step[tot]=step[tot-1]>=b?step[tot-1]-b:step[tot-1]+a;
        if(vis[step[tot]]) break;
        vis[step[tot]]=true;
    } --tot;
    for(int i=0,j=1;i<a+b&&i<=m;++i)
    {
        ans-=i/g+1;
        while(step[j]<=i&&j<=tot) ++j;
        ans+=j-1;
    }
    printf("%lld",ans);
}

1146E Hot is Cold

题意

给你一个长度为 \(n\) 的序列和 \(q\) 个操作，每次操作将 \(<x_i\) 的取反或 \(>x_i\) 的数取反。求最后的序列。\(n,q\le 10^5\)

题解

排序后直接线段树维护取反标记即可。

有神仙线性做法，待补充……

code

咕咕咕。

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄