蒟蒻WA#3有详细注释玄关求调!
查看原帖
蒟蒻WA#3有详细注释玄关求调!
950927
_luo_gu楼主2024/7/20 09:16

昨天已经调了一下午了(悲

在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 ;
} 

感谢大佬!!!

好人一生平安!!!

2024/7/20 09:16
加载中...