网站我们的客户,外包,工商查名字能不能注册,门户网站代码结构登录—专业IT笔试面试备考平台_牛客网
题目大意#xff1a;有一长度为n的数组a#xff0c;有q次询问#xff0c;每次要求将[l,r]的区间分成k个连续区间#xff0c;满足每个区间和都是偶数#xff0c;能满足要求就输出YES
1n,q1e5;0ai1e10;1lr有一长度为n的数组a有q次询问每次要求将[l,r]的区间分成k个连续区间满足每个区间和都是偶数能满足要求就输出YES
1n,q1e5;0ai1e10;1lrn;1k1e5
思路要想和为偶数那么奇数的数量必须是偶数个所以我们把数组中的数都变成%2后的结果也就是整个数组只有0和1构成每个0可以作为一个合法的区间而每个1必须要和其相邻的一个1组合才能构成一个最小的合法区间而如果一个1和其相邻的一个1组成一个区间那这两个1中间的0都不能作为合法的区间。
所以我们要分两种情况讨论一种是数组中从左往右第二个1和第一个1组合另一种是第二个和第三个1组合然后分别对合法区间数求前缀和每个0的贡献都是1每个含有两个1的区间整个区间贡献是1例如对于0 0 1 0 0 1 0 0 1 0 0 1 0这个数组第一个前缀和数组sum1求出来的是1 2 3 3 3 3 4 5 6 6 6 6 7第二个数组sum2是0 0 0 1 2 3 3 3 3 4 5 6 6另外还要特判一下每个区间内1的数量是否是偶数如果是奇数就可以直接输出no了。
对于其他情况我们要看每个询问的区间适用于哪个数组如果a[r]是1那么哪个数组的sum[r]sum[r-1]说明哪个数组是合法的如果a[r]是0那么就看哪个sum[r]!sum[r-1]不等的那个数组提供贡献
#includebits/stdc.h
//#include__msvc_all_public_headers.hpp
using namespace std;
typedef long long ll;
const int N 1e5 5;
const ll MOD 998244353;
ll a[N];
ll sum[N];
ll sum2[N];
ll sum3[N];
void solve()
{int n, q;cin n q;for (int i 1; i n; i){cin a[i];a[i] % 2;//将数组按奇偶转换成1和0sum[i] sum[i - 1] a[i];//统计区间奇偶性sum2[i] sum3[i] 0;}int flag 0;for (int i 1; i n; i){if (!a[i]){if(!flag)sum2[i] 1;//在两个1中间以外的0贡献为1}else{if (!flag){flag i;//记录上一个1的位置}else{sum2[flag];//上一个1到这一个1之间总共贡献1flag 0;}} }if (flag)//末尾没有匹配的1要1贡献与前面的0区分开sum2[flag];flag 0;int fi0;for (int i 1; i n; i){if (!a[i]){if(!fi)//在遇到第一个1之前不记录贡献continue;if (!flag)sum3[i] 1;}else{if(!fi){fii;//遇到第一个1之后后面的统计与上一个数组相同continue;}if (!flag){flag i;}else{sum3[flag];flag 0;}}}if (flag)sum3[flag];for (int i 2; i n; i){//求前缀和得到区间内的合法区间数sum2[i] sum2[i - 1] sum2[i];sum3[i] sum3[i - 1] sum3[i];}for (int i 1; i q; i){int l, r, k;cin l r k;if ((sum[r] - sum[l - 1]) % 2!0){cout NO endl;continue;}ll ans3 sum3[r] - sum3[l - 1];ll ans2 sum2[r] - sum2[l - 1];if (a[r] 1){//右端点是1哪个数组rr-1就说明哪个合法if (sum2[r] sum2[r - 1]){cout (ans2 k ? YES : NO) endl;}else{cout (ans3 k ? YES : NO) endl;}}else{//右端点是0哪个数组r!r-1就说明哪个合法if (sum2[r] ! sum2[r - 1]){cout (ans2 k ? YES : NO) endl;}else{cout (ans3 k ? YES : NO) endl;}}}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin t;while (t--){solve();}return 0;
}
