代码实现:此题需要发现,ch[1] == ch[k + 1] == ch[2 * k + 1] ..... == ch[n * k + 1]就可以暴力的写出了。
因为,如果前k个满足条件的话也就是 1 ~ k 满足题目要求的话。
那么现在要 i + 1 ~ k + 1满足条件。由于i~k满足条件,则这个时候i ~ k 的所有值是固定的。 我们可以发现 1+ 1 ~ k + 1 也就是删除了第i个字符,增加了第 k + 1 个字符。 所以要满足题目条件,则必须满足第1个字符 == 第 k + 1 个字符。
以此类推,就可以知道,ch[i] == ch[k + i ] == ch[2 * k + i] ....
于是我们就可以把 1~n分成 [1,k + 1 , 2 * k + 1 , .....] ,[2 , k + 2 , 2 * k + 2,...]....[k , k + k , 2 * k + k]这k组。
分别判断每一组当中如果有0或者1,是否会发生冲突。
比如 k + 1 为 '0' , 2 * k + 1为'1' 但它们两个应该相等,于是就冲突了。
如果不冲突。
那么,这个时候再循环一遍1~k的值,统计1的次数,0的次数,以及'?'的次数。
如果1的次数以及0的次数都不大于 k / 2。且 1的次数 + 0 的次数 + '?'的次数 == k则满足。
满足,则前k个可以满足条件,那么后面的也满足条件。于是全部满足条件。
# includeusing namespace std; const int N = 3e5 + 10; int n,k; int t; char ch[N]; int main() { scanf("%d",&t); while(t--) { scanf("%d %d",&n,&k); for(int i = 1 ; i <= n ; i++) { cin >> ch[i]; } bool flag = true; for(int i = 1 ; i <= k; i++) { char t = 't'; for(int j = i ; j <= n ; j += k) { if(ch[j] != '?' && t == 't') { t = ch[j]; continue; } if(ch[j] != '?' && ch[j] != t) { flag = false; break; } } if(!flag) { break; } for(int j = i ; j <= n ; j += k) { ch[j] = t; } } int num0 = 0 , num1 = 0 , numt = 0; for(int i = 1 ; i <= k ; i++) { if(ch[i] == '0') { num0++; } else if(ch[i] == '1') { num1++; } else if(ch[i] == 't') { numt++; } } if(num1 > k / 2) { flag = false; } if(num0 > k / 2) { flag = false; } int total1 = k / 2 - num1; int total0 = k / 2 - num0; if(total1 + total0 != numt) { flag = false; } if(!flag) { printf("NOn"); } else { printf("YESn"); } } return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)