专栏文章

题解：B4221 [常州市程序设计小能手 2023] 红绿灯

xxinxin2022
B4221题解参与者 3已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@mipxsano
此快照首次捕获于
2025/12/03 19:41
3 个月前
此快照最后确认于
2025/12/03 19:41
3 个月前
查看原文
直接做显然不好做，发现时间长度为 2pq2pq，考虑与解法有何关联。
显然当 p⊥qp\perp q 时，由于存在红灯和绿灯两种状态，可以使两个灯回到同一起点的时间为 2pq2pq。
而若 p,qp,q 不互质，那么相当于有 gcd⁡(p,q)\gcd(p,q) 段连续时间两灯状态会相等，可以先同时除去 gcd⁡(p,q)\gcd(p,q)，计算出答案后再乘上 gcd⁡(p,q)2\gcd(p,q)^2，也就是被除掉的部分。
那么对于 p⊥qp\perp q，计算答案的方式如下：
易知 p,qp,q 不会都是偶数。
考虑分类讨论前 pqpq 秒和后 pqpq 秒。
若存在一个偶数，那么相当于该灯在前 pqpq 秒中奇数次改变了状态，那么前 pqpq 秒和后 pqpq 秒状态显然相反，另一个灯状态确却是相等的，那么相当于该灯补上了前 pqpq 秒的空缺时间，计算出另一个灯在 pqpq 秒内的绿灯时间即可，即 pq2\frac{pq}{2}。
若都为奇数，两灯在前 pqpq 秒和后 pqpq 秒的状态均相反，只需要知道 pqpq 秒内的答案即可。
由于两数均为奇数，pp 改变状态时会覆盖 qq 同色连续段的所有点，而 p→p+1p\to p+1 显然只会使一个同色点改为异色点，一个异色点改为同色点，显然不对答案产生影响。
考虑计算 pqpq 秒内所有 pp 的改变，因所有改变状态点均被扫到，绿灯时长自然为 p(q+1)2\frac{p(q+1)}{2}。
对 qq 的改变计算也同理，时长为 q(p+1)2\frac{q(p+1)}{2}。
由于两数均为奇数，前 pqpq 秒状态与后 pqpq 秒相反，答案如下：
(p+1)(q+1)+(p−1)(q−1)2×2\frac{(p+1)(q+1)+(p-1)(q-1)}{2\times 2}
即：
2q(p+1)−2q+24\frac{2q(p+1)-2q+2}{4}
所以答案为：
pq+12\frac{pq+1}{2}
最后乘上 gcd⁡(p,q)2\gcd(p,q)^2 即可。
代码如下：
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
int p,q,w;
signed main(){
    cin>>p>>q;
    w=__gcd(p,q);
    p/=w;
    q/=w;
    if((p%2)&&(q%2)) cout<<w*w*((p*q+1)/2);
    else cout<<w*w*(p*q)/2;
    return 0;
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...