ZOI Round 1 & 新春联欢赛记录

· · 个人记录

以此纪念从学 OI 开始，第一次赛时 AK 比赛，从看题开始用了 1h。

但是有 129 个 AKer，无语。

A

可以计算出 [1,r] 和 [1,l-1] 的答案，忽略题目的下限要求。

然后 2,3,5,7 是质数，枚举它们的指数就可以了。

B

算出每个站第一次到达时间，接下来每 k 时间后再来一次。

简单分讨。 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int n,k,q;
int a[maxn];
ll pre[maxn];
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>k>>q;
    for(int i=1;i<n;i++){
        cin>>a[i];
    }
    for(int i=2;i<=n;i++){
        pre[i]=pre[i-1]+a[i-1];
    }
    while(q--){
        int x,t;
        cin>>x>>t;
        if(t<=pre[x]){
            cout<<pre[x]-t<<'\n';
        }else{
            t-=pre[x];
            if(t%k==0){
                cout<<"0\n";
            }else{
                cout<<k-t%k<<'\n';
            }
        }
    }
    return 0;
}

C

与最短路板子的区别，就是它必须得以一个大整体运动。
随便选一个红点，枚举出它放在哪个地方，整体随之运动能完成目标。
然后最短路。

D

设距离是 x，时间是 t。
显然需要进行 x 次有效运动。
剩下的 t-x 时间，得想办法消磨掉，同时保证位置最终不变。
很显然其中 \frac{t-x}{2} 时间用来反向运动就 ok 了。

总共运动 t 次，\frac{t-x}{2} 次反向运动，显然答案是 C_{\frac{t-x}{2}}^t

如果 t \lt x，无解。
如果 t = x = 0，无解。
如果 t-x 是奇数，无解。