简简单单3篇题解

C

题意

有n堆石头你从第3堆开始依次进行操作：取3x个，给前一堆x个，剩下的给再前面的那一堆。你只能进行一轮操作，且必须按照原有的顺序。求最小的那堆最多有多少个。

题解

显然二分。值得注意的一点是检查的时候可以倒序，这样可以保证每个点给出的最多。还有就是给出的时候不能比当前拥有的更多，要取min。

D

题意

一个\(n\times m\)的棋盘，有一个扫地机器人初始在(x,y)位置。每次移动，他位置会变成(x+dx,y+dy)，初始dx=dy=1. 如果机器人在某个方向不能移动了，它就会尝试在这个方向对应的轴上往相反的方向移动（如右下遇到下边界就变成右上）。当它移动到和位置为(p,q)的脏东西在同一行或者同一列的时候（脏东西只有一个），它有p的概率清理并结束运动，1-p的概率无视并继续移动。求期望多少步之后机器人会清理这个垃圾。

题解

一个重要结论：机器人的运动路径是长为2(n-1)(m-1)的一个因子的包括起点的环。
原因：运动分解。在x轴方向的运动，至多2(n-1)步后，机器人会回到原点，并且方向和开始时一致。同理，y轴方向的运动至多2(m-1)步回到原点。所以至多2(n-1)(m-1)步，机器人必定回到最开始的状态，也就是遇到了环。

然后我们再考虑环上怎么dp。这就是高中数学思路了：设一个点u开始的期望答案是f(u)，其后继的期望答案是f(v)，那么 \[ f(u)=\left\{ \begin{aligned} (1-p)(1+f(v)) & & {x_u==p\ \mathrm{or}\ y_u==q}\\ (1+f(v))& & \mathrm{otherwise}\\ \end{aligned} \right. \]

我们绕着环跑一遍，可以得到一个\(f(s)=a_1(1+(a_2(1+...(1+f(s)))))\)的式子，其中\(a_i\)要么是1要么是1-p。容易看出这是个一次方程，所以可以直接拆开移项解出来。更简单地，我们可以直接迭代2(n-1)(m-1)次，因为它一定是环长的倍数。

代码

#include <cstdio>

const int P=1e9+7;
const int N=1e6+100;

typedef long long int64;

inline int64 qpow(int64 a,int b)
{
    int64 ans=1ll;
    for (;b;b>>=1)
    {
        if (b&1) ans=ans*a%P;
        a=a*a%P;
    }
    return ans%P;
}

int a[N];

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int n,m,rb,cb,rd,cd,p;
        scanf("%d%d%d%d%d%d%d",&n,&m,&rb,&cb,&rd,&cd,&p);
        int p2=((1-p*qpow(100,P-2))%P+P)%P;
        int dx=1,dy=1;
        a[0]=(rb==rd || cb==cd)?p2:1;
        for (int i=1;i<2*(n-1)*(m-1);++i)
        {
            if (rb+dx<=n && rb+dx>0) rb+=dx;
            else dx=-dx,rb+=dx;
            if (cb+dy<=m && cb+dy>0) cb+=dy;
            else dy=-dy,cb+=dy;
            a[i]=(rb==rd || cb==cd)?p2:1;
        }
        int64 coe=1,con=0;
        for (int i=2*(n-1)*(m-1)-1;i>=0;--i)
            coe=coe*a[i]%P,con=(con+1)*a[i]%P;
        int64 denom=qpow((1+P-coe)%P,P-2);
        printf("%lld\n",con*denom%P);
    }
}

_WA自动机的blog

CF1623题解

C

题意

题解

D

题意

题解

代码