专栏文章

题解：P14257 嫉妒（jealousy）

VVinstaG173かえで
P14257题解参与者 15已保存评论 15

文章操作

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

当前评论
15 条
当前快照
1 份
快照标识符
@minrsjp8
此快照首次捕获于
2025/12/02 07:18
3 个月前
此快照最后确认于
2025/12/02 07:18
3 个月前
查看原文
tag：模拟。
从 11 到 nn 枚举 ii，判断 (i−1)×s(i-1)\times s 与 i×si\times s 是否均不等于某个 y+j×ty+j\times t。若是，则答案为 Yes；若都不是，则答案为 No。
每次暴力从 00 开始枚举 jj，到 y+j×t>i×sy+j\times t>i\times s 为止，单次判断 O(ns/t)O(ns/t)，总时间复杂度 O(n2s/t)O(n^2s/t)，可以轻松通过。
Code:
CPP
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)O(1)，具体地，如果存在非负整数 jj 使得 x×s=y+j×tx\times s=y+j\times t，则 x×s≥yx\times s\ge y 且 (x×s−y) mod t=0(x\times s-y)\bmod t=0。
只需要实现一个函数 check(x)check(x) 判断以上条件，若找到一个 ii 使得 check(i−1)check(i-1) 与 check(i)check(i) 均返回 false，则答案为 Yes，否则答案为 No。时间复杂度优化为 O(n)O(n)。
Code:
CPP
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";
}
另外此题还有一个性质：将 nn 换为 min⁡{3,n}\min\{3,n\}，得到的结果相同。
这是因为当 n≥3n\ge3 时，如果要使每场面试都被发现，则首先 y=0y=0 或存在 y+j×t=sy+j\times t=s，此时第一场或第二场面试开始时会被发现。对于下一场面试，如果开始时被发现，则一定有 j∣sj\mid s，否则结束时被发现，则有 j∣(2s)j\mid(2s)。
综合以上情况，可以得到 n≥3n\ge3 时，只要答案为 No。则一定 y=0y=0 或存在 y+j×t=sy+j\times t=s，且 j∣(2s)j\mid(2s)。容易验证若这个条件满足，则答案一定为 No，即这是一个等价条件。
这个条件与 nn 无关，也就是说 n≥3n\ge3 时的答案均和 n=3n=3 时相同。时间复杂度优化为 O(1)O(1)，将以上代码 for 循环中的 n 改为 min(3,n) 即可。

评论

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

正在加载评论...