昨天已经调了一下午了(悲
在CF那里看第三个点始终有将No漏判导致输出yes的部分(万恶的多测
我的思路是记录有哪些值出现过,然后通过枚举x,y来枚举对应的区间
出现过的值在数组中用前缀和维护,方便区间查询
但是好像我的判断条件不全(不知道是不是这个原因
以下是代码:
#include <bits/stdc++.h>
using namespace std ;
// 记录原数组(数组a[]) 记录每一个值出现的次数(数组b[])
// maxai:记录出现过的最大的值,方便清空
int a[1000006] , b[1000006] , t , n , c , maxai ;
int main(){
scanf("%d" , &t );
while( t -- ){
//由于后面的判断语句中有break
//所以将清空写在了前面
//对于每一组数据的值域上的前缀和的桶的清空
for( int i = 0 ; i <= maxai ; i ++ ){
b[i] = 0 ;
}
maxai = 0 ;
scanf("%d%d" , &n , &c );
//s输入
for( int i = 1; i <= n ; i ++ ){
scanf("%d" , &a[i] );
//用b数组记录出现值的次数(桶
b[a[i]] ++ ;
//更新出现过的a[i]的最大值
if( maxai < a[i] ){
maxai = a[i] ;
}
}
//特别判断,题目中说的[x/y]中的x,y可以相等,所以每一组中必须有1
if( b[1] == 0 ){
printf("No\n");
continue ;
}
//对b做前缀和
//因为只有maxai之前的数可能存在,也只有他们可能产生贡献
//所以这么写
for( int i = 1 ; i <= maxai ; i ++ ){
b[i] = b[i] + b[i-1] ;
}
for( int i = maxai ; i < c ; i ++ ){
b[i+1] = b[i] ;
}
//记录是否输出过
bool mar = false ;
//i,j为枚举的下标
for( int i = 1 ; i <= n ; i ++ ){
for( int j = i ; j <= n ; j ++ ){
//最里面的min(a[i],a[j])是因为
//x/y中y<=x,所以想要让分数的值加一,是分子加上1*分母
//也就是较小的那一个
//对于b[]中靠外的一个min,是为了保证数组不越界
if( b[min(a[i]*a[j]+min(a[i],a[j])-1 , c )] - b[a[i]*a[j]-1] == 0 ){
//用前缀和判断区间中是否有数
printf("No\n");
//更新标记
mar = true ;
break ;
}
}
if( mar == true ){//如果输出过No
break ;//跳出
}
}
if( mar == false ){//如果没有输出过,也就是没有被判否过
printf("Yes\n");//输出yes
}
}
return 0 ;
}
感谢大佬!!!
好人一生平安!!!