COCI 2015/2016 部分题目题解2

B. SLON

前言

这是一道很考验耐心与代码实现的问题。

思路

其实思路可以说没有丝毫难点，完全就是题目怎么说我们怎么做，具体来说，就是先将题中给的字符串化成 $kx+b$ 这样的表达式，然后求使得 $kx+b \equiv p \pmod{m}$ 的最小的 $x$。前面的部分考验用常见的弹栈来写，但这次的代码中用到了 $ai$ 给的一种递归写法（个人觉得更简洁易读一些），具体实现看代码应该能看懂。不过需要注意的一点是，这道题用递归写法可能会更好的原因是运算符简单而少，所以不需要怎么扩展，代码也短一些，在一些运算符多的题目中还是用弹栈比较稳定安全。后面的部分可以用扩展欧几里得来求解。

扩展欧几里得部分

表达式解析后可以表示为：

$$ax+b$$

题目要求：

$$ax+b\equiv P\pmod M$$

移项得：

$$ax\equiv P-b\pmod M$$

令：

$$r=(P-b)\bmod M$$

设：

$$g=\gcd(a,M)$$

同余方程有解当且仅当：

$$g\mid r$$

扩展欧几里得算法可以求出：

$$ax_0+My_0=g$$

若：

$$r\not\equiv0\pmod g$$

则无解。

否则，将方程约去 $g$，得到：

$$\frac agx+\frac Mg y=\frac rg$$

此时 $x_0$ 是 $\frac ag$ 在模 $\frac Mg$ 意义下的逆元，因此答案为：

$$x\equiv\frac rg\cdot x_0 \pmod{\frac Mg}$$

最后将答案调整到最小非负整数范围即可。

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string>
#include<cctype>
using namespace std;
typedef long long ll;

string s;
int pos;
ll P,M;
struct Val{ll a,b;};

int priority(char op)
{
    if(op=='+'||op=='-') return 1;
    if(op=='*') return 2;
    return 0;
}

Val calculate(Val left,Val right,char op)
{
    if(op=='+'){
        return {(left.a+right.a)%M,(left.b+right.b)%M};
    }
    if(op=='-'){
        return {(left.a-right.a+M)%M,(left.b-right.b+M)%M};
    }
    return {(left.a*right.b+left.b*right.a)%M,left.b*right.b%M};
}

Val parse(int minPriority=1)
{
    Val left;
    if(s[pos]=='x'){
        pos++;
        left={1,0};
    }else if(s[pos]=='('){
        pos++;
        left=parse();
        pos++;
    }else{
        ll num=0;
        while(pos<(int)s.size()&&isdigit(s[pos])){
            num=(num*10+s[pos]-'0')%M;
            pos++;
        }
        left={0,num};
    }
    while(pos<(int)s.size()&&s[pos]!=')'){
        char op=s[pos];
        int currentPriority=priority(op);
        if(currentPriority<minPriority) break;
        pos++;
        Val right=parse(currentPriority+1);
        left=calculate(left,right,op);
    }
    return left;
}

ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll x1,y1;
    ll g=exgcd(b,a%b,x1,y1);
    x=y1;
    y=x1-a/b*y1;
    return g;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>s>>P>>M;
    Val res=parse();
    ll rhs=(P-res.b+M)%M;
    ll x,y;
    ll g=exgcd(res.a,M,x,y);
    if(rhs%g!=0){
        cout<<-1<<'\n';
        return 0;
    }
    rhs/=g;
    M/=g;
    if(M==1){
        cout<<0<<'\n';
        return 0;
    }
    x=(x%M+M)%M;
    cout<<rhs%M*x%M<<'\n';

    return 0;
}

D. ENDOR

题目大意

在一根长度为 $L$ 的棍子上有 $n$ 只变色龙。

每只变色龙有：

• 初始位置 $d$
• 初始颜色 $b$
• 初始移动方向

所有变色龙的速度均为 $1$。

当一只向左移动、颜色为 $a$ 的变色龙，与一只向右移动、颜色为 $b$ 的变色龙相撞时：

• 原本向左移动的变色龙反向向右，并变为颜色 $b$；
• 原本向右移动的变色龙反向向左，并变为颜色 $(a+b)\bmod k$。

求所有变色龙离开棍子后，对于每种颜色，所有变色龙在呈现该颜色时走过的总距离。

直接模拟的问题

如果按照题意直接模拟变色龙的运动过程，每次相撞后都需要：

• 修改两只变色龙的方向；
• 修改两只变色龙的颜色；
• 继续处理之后可能发生的碰撞。

这样不仅需要维护大量运动状态，而且一只变色龙可能和很多其他变色龙相撞，最坏情况下碰撞次数达到 $O(n^2)$，无法接受。

因此，需要换一种方式描述碰撞。

将相撞转化为穿过

考虑两只相向而行的变色龙：

• 一只向左移动，颜色为 $a$；
• 一只向右移动，颜色为 $b$。

相撞之后，两只变色龙都会反向。观察它们的运动轨迹可以发现：

• 原本向左的变色龙，碰撞后沿着原本向右的轨迹继续移动；
• 原本向右的变色龙，碰撞后沿着原本向左的轨迹继续移动。

因此，从轨迹的角度看，可以把“相撞后反向”理解为“两条轨迹互相穿过”。

接下来不再让变色龙真正反向，而是让所有变色龙始终沿着初始方向移动：

• 初始向右的轨迹始终向右移动，颜色不变；
• 初始向左的轨迹始终向左移动；
• 每当一条向左轨迹与一条向右轨迹相交时，向左轨迹的颜色加上向右轨迹的颜色。

也就是说，原来的碰撞规则可以等价地改写为：

两条轨迹直接穿过；
向右轨迹的颜色保持不变；
向左轨迹经过向右轨迹时，颜色增加向右轨迹的颜色。

所有颜色运算均在模 $k$ 意义下进行。

这样转换之后，每条轨迹的方向都固定不变，问题就容易处理很多了。

先统计每条轨迹的总路程

如果暂时不考虑颜色变化，那么每只变色龙最终都会走到棍子的一端：

• 初始向右移动的变色龙，从 $d_i$ 走到 $L$，路程为

$$L-d_i$$

• 初始向左移动的变色龙，从 $d_i$ 走到 $0$，路程为

$$d_i$$

因此，可以先把每只变色龙的全部路程都计入它的初始颜色。

题目中的路程可能为整数或半整数。为了避免浮点数误差，下面统一将所有答案乘以 $2$：

• 向右移动的变色龙贡献

$$2(L-d_i)$$

• 向左移动的变色龙贡献

$$2d_i$$

之后，只需要处理向左轨迹在与向右轨迹相交时发生的颜色变化。

一次相交需要转移多少路程

设：

• 向左轨迹的初始位置为 $d_j$；
• 向右轨迹的初始位置为 $d_i$；
• 并且 $d_i<d_j$。

两条轨迹相向而行。设它们经过 $t$ 秒后相交，则有：

$$d_i+t=d_j-t$$

所以：

$$t=\frac{d_j-d_i}{2}$$

相交的位置为：

$$p=d_i+t=\frac{d_i+d_j}{2}$$

在相交之后，向左轨迹还会从位置 $p$ 移动到位置 $0$，因此相交之后的剩余路程为：

$$\frac{d_i+d_j}{2}$$

由于我们把答案统一乘以 $2$，所以需要转移的路程为：

$$d_i+d_j$$

假设相交之前，向左轨迹的颜色为 oldColor，相交之后变为 newColor，那么这次相交对应的答案变化为：

ans[oldColor] -= d_i + d_j;
ans[newColor] += d_i + d_j;

如果当前向右轨迹会与很多条向左轨迹相交，那么只需要把这些转移量加起来即可。

计算向左轨迹的颜色

接下来考虑如何快速计算每条向左轨迹在不同相交时的颜色。

按照初始位置从左到右给所有变色龙编号。

定义前缀和：

$$pref[i] = \text{前 }i\text{ 个位置中所有初始向右轨迹的颜色之和}\pmod k$$

这里没有统计向左轨迹，因为在转换后的模型中，向右轨迹的颜色始终不变，而向左轨迹的颜色会随着相交过程变化。

考虑一条初始向左、编号为 $j$ 的轨迹。

在它与左侧所有向右轨迹相交之后，它的颜色为：

$$b_j+pref[j-1]\pmod k$$

为了方便，将这个值定义为这条向左轨迹的类别：

$$type[j]=(b_j+pref[j-1])\bmod k$$

类别只有 $k$ 种，因此可以按照类别对向左轨迹进行分组。

当前向右轨迹经过时的颜色变化

现在考虑一条初始向右、编号为 $i$ 的轨迹。

它只会与右侧的向左轨迹相交，也就是编号大于 $i$ 的向左轨迹。

假设某条右侧向左轨迹的类别为 type。

类别 type 表示这条向左轨迹在经过其左侧所有向右轨迹之后的颜色总和。当前向右轨迹 $i$ 的颜色已经包含在这个总和中，因此在与当前向右轨迹相交之前，这条向左轨迹的颜色为：

$$oldColor=(type-pref[i])\bmod k$$

相交时，它还需要加上当前向右轨迹的颜色 $b_i$，所以相交之后的颜色为：

$$newColor=(oldColor+b_i)\bmod k$$

又因为：

$$pref[i]=pref[i-1]+b_i\pmod k$$

所以：

$$newColor=(type-pref[i-1])\bmod k$$

这说明，对于当前向右轨迹来说，同一个 type 类别中的所有向左轨迹：

• 相交前的颜色相同；
• 相交后的颜色相同；
• 只需要知道它们的数量和初始位置之和。

因此，可以将它们批量处理。

从右向左扫描

我们从右向左扫描所有变色龙，并维护每种类别的信息：

cnt[type]：当前已经扫描到的、位于右侧的向左轨迹数量
sum[type]：这些向左轨迹初始位置之和

扫描到一条向左轨迹 $j$ 时，计算它的类别：

$$type=(b_j+pref[j-1])\bmod k$$

然后将它加入对应的类别：

cnt[type]++;
sum[type] += d_j;

扫描到一条向右轨迹 $i$ 时，当前已经加入的数据正好是它右侧的所有向左轨迹。

对于某个类别 type，每条向左轨迹 $j$ 需要转移的路程为：

$$d_i+d_j$$

因此，该类别所有向左轨迹需要转移的总路程为：

$$\begin{aligned} W &=\sum(d_i+d_j)\\ &=cnt[type]\cdot d_i+sum[type] \end{aligned}$$

于是：

• 从颜色 $(type-pref[i])\bmod k$ 中减去 $W$；
• 向颜色 $(type-pref[i-1])\bmod k$ 中加上 $W$。

每条向右轨迹枚举 $k$ 个类别，因此总复杂度为 $O(nk)$。

由于题目中 $k$ 很小，这个复杂度可以通过。

正确性分析

前面的轨迹转换不会改变实际的运动轨迹，只是把“碰撞后反向”改成了“轨迹穿过”，并将颜色变化转移到了向左轨迹上。因此，每条轨迹经过每一段路程时对应的颜色保持不变。

初始时，我们先把每条轨迹的全部路程计入它的初始颜色。对于每次向左轨迹和向右轨迹的相交，再将相交之后的剩余路程从相交前的颜色转移到相交后的颜色。

对于初始位置分别为 $d_i$ 和 $d_j$ 的两条轨迹，相交之后向左轨迹的剩余路程乘以 $2$ 后正好是：

$$d_i+d_j$$

因此，每次颜色转移的路程计算是正确的。

此外，同一类别的向左轨迹在当前向右轨迹处具有相同的相交前颜色和相交后颜色，所以可以通过数量和位置总和批量计算，不会遗漏或重复处理任何轨迹。

复杂度分析

• 预处理前缀和和初始答案：$O(n)$
• 从右向左扫描：
  • 每条向左轨迹处理一次；
  • 每条向右轨迹枚举 $k$ 种类别；
• 总时间复杂度：

$$O(nk)$$

• 空间复杂度：

$$O(n+k)$$

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string.h>

using namespace std; 
typedef long long ll; 

const int N=1e5+5,K=45; 

int n,k,L; 
int pre[N]; 

ll cnt[K],sum[K],ans[K]; 

struct node{ 
    int d,b; 
    char c; 
}a[N]; 

int main() 
{ 
    cin>>n>>k>>L; 

    for(int i=1;i<=n;i++) 
        cin>>a[i].d>>a[i].b>>a[i].c; 

    for(int i=1;i<=n;i++){ 
        pre[i]=pre[i-1]; 

        if(a[i].c=='D') 
            pre[i]=(pre[i]+a[i].b)%k; 

        if(a[i].c=='D') 
            ans[a[i].b]+=2ll*(ll)(L-a[i].d); 
        else 
            ans[a[i].b]+=2ll*(ll)(a[i].d); 
    } 

    for(int i=n;i;i--){ 
        if(a[i].c=='L'){ 
            int type=(pre[i-1]+a[i].b)%k; 

            cnt[type]++; 
            sum[type]+=a[i].d; 
        }else{ 
            for(int j=0;j<k;j++){ 
                if(!cnt[j]) 
                    continue; 

                ll w=cnt[j]*(ll)a[i].d+sum[j]; 

                ans[(j-pre[i]+k)%k]-=w; 
                ans[(j-pre[i-1]+k)%k]+=w; 
            } 
        } 
    } 

    for(int i=0;i<k;i++){ 
        if(ans[i]&1) 
            cout<<ans[i]/2<<".5\n"; 
        else 
            cout<<ans[i]/2<<".0\n"; 
    } 

    return 0; 
}