\(T1\) 觉得很弱小的字符串， \(Trick\) 也比较明显。
\(\texttt{T2}\)
神仙题。
输入 \(n\) 个数 \(\{a\}\)，问在 \(\{a\}\) 中，每个 \(a_i\) 至多可以减去 \(k\)（不能减成 \(0\) ），至多删去 \(f\) 个数，求最后合法的公约数 \(g\) 的全部方案。
60
考虑如果 \(g\) 是 \(a_i\) 的约数，那么 \(a_i-k=cg\ (c\in N).\)
而 \(k\) 已经给定，所以当且仅当 \(cg \leq a_i \leq cg+k\) 才行，也就是 \(a_i \bmod g \leq c.\)
计算 \(a_i\bmod g >c\) 这样的 \(a_i\) 数量，最后与 \(f\) 比较就好了。
100
考虑一种可以快速统计值出现在 \(l,r\) 的数的个数的方法。显然可以桶 \(+\) 前缀和处理。
而枚举提到的 \(d=cg\) ，然后统计出现在 \(d+k+1,d+g-1\) 的数的个数，最后与 \(f\) 比较就好了。
而 \(d\) 枚举次数出现在 \(n/1,n/2,n/3,\cdots,n/n\)，加起来是调和级数，最后复杂度明显是 \(\mathcal{O[T(\alpha\log \alpha+n)]}.\) 足以通过本题。
程式
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int T,n,k,f,maxi=0,dlt,ans;
int a[N],t[N],q[N];
inline int re(void){
int res=0; char ch=0;
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48), ch=getchar();
return res;
}
int main(){
freopen("tsuki.in","r",stdin);
freopen("tsuki.out","w",stdout);
T=re();
while(T--){
maxi=0;
memset(t,0,sizeof t);
memset(q,0,sizeof q);
n=re(),k=re(),f=re();
for(int i=1;i<=n;++i) a[i]=re(),t[a[i]]++,maxi=max(maxi,a[i]);
for(int i=1;i<=maxi;++i) q[i]=q[i-1]+t[i];
for(int g=1;g<=maxi;++g){
dlt=q[g-1];
for(int i=g;dlt<=f&&i+k+1<=maxi;i+=g) {
int l=i+k+1,rgt=min(maxi,i+g-1);
if(l<=rgt) dlt+=q[rgt]-q[l-1];
}
if(dlt<=f) printf("%d ",g);
}
puts("");
}
return 0;
}
觉得这种东西在考场上根本不能想到耶。
标签：ch,NOIP,int,res,cg,2024,leq,个数,模拟 From： https://www.cnblogs.com/chihirofujisaki/p/18169403/2024_5_1Contect