题解：P14257 嫉妒（jealousy）

VinstaG173 · 2025-09-28 00:00:00 · 题解

tag：模拟。

从 1 到 n 枚举 i，判断 (i-1)\times s 与 i\times s 是否均不等于某个 y+j\times t。若是，则答案为 Yes；若都不是，则答案为 No。

每次暴力从 0 开始枚举 j，到 y+j\times t>i\times s 为止，单次判断 O(ns/t)，总时间复杂度 O(n^2s/t)，可以轻松通过。

Code:

int n,y,s,t;
inline void solve(){
    cin>>n>>y>>s>>t;
    int flag=0;
    for(int i=1;i<=n;++i){
        int flag_0=1,flag_1=1;
        for(int j=0;y+j*t<=(i-1)*s;++j)
            if(y+j*t==(i-1)*s)
                flag_0=0;
        for(int j=0;y+j*t<=i*s;++j)
            if(y+j*t==i*s)
                flag_1=0;
        if(flag_0&&flag_1)flag=1;
    }if(flag)cout<<"Yes\n";
    else cout<<"No\n";
}

Bonus

事实上可以用取模将单次判断优化至 O(1)，具体地，如果存在非负整数 j 使得 x\times s=y+j\times t，则 x\times s\ge y 且 (x\times s-y)\bmod t=0。

只需要实现一个函数 check(x) 判断以上条件，若找到一个 i 使得 check(i-1) 与 check(i) 均返回 false，则答案为 Yes，否则答案为 No。时间复杂度优化为 O(n)。

Code:

int n,y,s,t;
bool check(int x){
  return (x*s>=y)&&((x*s-y)%t==0);
}

void solve(){
    cin>>n>>y>>s>>t;
    int flag=0;
    for(int i=1;i<=n;++i)
        if(!check(i-1)&&!check(i))
            flag=1;
    if(flag)cout<<"Yes\n";
    else cout<<"No\n";
}

另外此题还有一个性质：将 n 换为 \min\{3,n\}，得到的结果相同。

这是因为当 n\ge3 时，如果要使每场面试都被发现，则首先 y=0 或存在 y+j\times t=s，此时第一场或第二场面试开始时会被发现。对于下一场面试，如果开始时被发现，则一定有 j\mid s，否则结束时被发现，则有 j\mid(2s)。

综合以上情况，可以得到 n\ge3 时，只要答案为 No。则一定 y=0 或存在 y+j\times t=s，且 j\mid(2s)。容易验证若这个条件满足，则答案一定为 No，即这是一个等价条件。

这个条件与 n 无关，也就是说 n\ge3 时的答案均和 n=3 时相同。时间复杂度优化为 O(1)，将以上代码 for 循环中的 n 改为 min(3,n) 即可。