《C. Even Subarrays》
异或和，前缀和
这道题如果用朴素的暴露解法为O(n^2)，算出每一个子段的异或和，然后看一下这些异或和中哪个的除数是奇数个，但会超时
超时原因明显是因为我们要算出每一个子段的异或和；
在1~n的范围内的数进行异或和，其最大值不会超过2*n(因为2*n等价与n<<1)
想一想在1~2*n的范围内，哪些数是除数为奇数？（即因子数为奇数）
我们知道如果一个数num，其有除数i,那么其必然有另一个除数num/i;
则除数必然是成对出现的，但是有例外：如果num/i==i，那么就对除数个数的贡献为1，而不是2了，这个时候这个数num，必然是除数是奇数个
然后在范围1~2*n，除数是奇数个的数，即开根号能够开出整数的数，最多有sqrt(2*n)个
然后该如何作，即要如何作才能避免O(n^2)地算出每一个子段的异或和？
正难则反，我们想一下如何找出不合法的子段个数，即子段异或和为奇数的个数，然后用总子段个数n*(n+1)/2,减去不合法的子段个数
就是我们要求的除数是偶数的子段个数
但是不合法的子段个数如何找？
我们可以现算出异或和的前缀和
然后我们枚举有奇数个除数（因子）的数，假设这个数为t
在下标1~i中的是否有连续的子段的异或和为这个t;
办法就是利用num1^t=num2
num2是现在1~i异或和，t是1~i某段子段j~i的异或区间和，那么num1就是1~j-1的异或和
看一下num1是否真的存在过,如果存在，说明t也存在过； 1 #include <iostream>
2 #include <algorithm>
3 #include <cstring>
4 using namespace std;
5 typedef long long ll;
6 const int N = 2 * 1e5;
7 int maxn = 0, a[N], cnt[4 * N];
8 int main()
9 {
10 int t;
11 cin >> t;
12 while (t--)
13 {
14 int n;
15 cin >> n;
16 for (int i = 1; i <= n; i++)
17 {
18 int num;
19 scanf("%d", &a[i]);
20 a[i] ^= a[i - 1];
21 }
22 // 初始总共有ans个子段
23 ll ans = (ll)n * (n + 1) / 2;
24 // 其实a[0]就是0
25 cnt[a[0]]++;
26 for (int i = 1; i <= n; i++)
27 {
28 for (int j = 0; j * j <= 2 * n; j++)
29 {
30 // 这个t就是完全平方数,即有奇数个除数（因子）的数,注意0在题目中算有奇数个除数（因子）的数
31 // 然后我现在就是像看一下:在下标1~i中的是否有连续的子段的异或和为这个t;
32 // 办法就是利用num1^t=num2
33 // num2是现在1~i异或和，t是1~i某段子段j~i的异或区间和
34 // 那么num1就是1~j-1的异或和
35 // 看一下num1是否真的存在过,如果存在，说明t也存在过；
36 int t = j * j;
37 ans -= cnt[(a[i] ^ t)];
38 }
39 cnt[a[i]]++;
40 }
41 cout << ans << endl;
42 memset(cnt, 0, sizeof(cnt));
43 }
44 return 0;
45 }
这个还有要注意的地方：t范围是1~2*n,a[i]的范围是1~n，这两个相异或，值<=4*n ，所以cnt[]数组的下标范围开到4*n
否则会爆数组下标
《D. Valiant's New Map》
思维，二维前缀和
这道题没啥难度，但是有个转化十分巧妙，否则作不出（除非会二维区间的最值维护（二维ST表或二维线段树））：
我们二分l的长度，O(log(min(n,m)))
然后如何判断出我们所框定的区间内的数每一个都大于l呢？
我们可以新开一个二维数组b,O（n*m）
b[i][j]=1,当原数组a[i][j]>=l ,否则b[i][j]=0
然后我们二维前缀和b,然后可以查看任意框内数的总和
我们看一下我们所框定的区间内数的总和sum，如何sum==l*l，说明这个框内原数组中每一个数都>=l
总时间O(1e6*log(min(n,m)))
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <vector> 5 using namespace std; 6 const int N = 1e6 + 2; 7 int n, m;
//注意这里写法： 8 void init(vector<vector<int>> &b, vector<vector<int>> &pre, int x, vector<vector<int>> a) 9 { 10 for (int i = 1; i <= n; i++) 11 for (int j = 1; j <= m; j++) 12 { 13 if (a[i][j] >= x) 14 b[i][j] = 1; 15 else 16 b[i][j] = 0; 17 } 18 for (int i = 1; i <= n; i++) 19 for (int j = 1; j <= m; j++) 20 pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + b[i][j]; 21 } 22 bool check(int x, vector<vector<int>> a) 23 { 24 vector<vector<int>> b(n + 1, vector<int>(m + 1)), pre(n + 1, vector<int>(m + 1)); 25 init(b, pre, x, a); 26 for (int i = 1; i + x - 1 <= n; i++) 27 { 28 for (int j = 1; j + x - 1 <= m; j++) 29 { 30 int sy = i, sx = j; 31 int xy = i + x - 1, xx = j + x - 1; 32 int sum = pre[xy][xx] - pre[xy][sx - 1] - pre[sy - 1][xx] + pre[sy - 1][sx - 1]; 33 if (sum >= x * x) 34 return true; 35 } 36 } 37 return false; 38 } 39 int main() 40 { 41 int t; 42 cin >> t; 43 while (t--) 44 { 45 cin >> n >> m;
//注意这里初始化vector,默认每个数都是0，然后可以当做普通数组用，同时不要担心爆数组，十分好用 46 vector<vector<int>> a(n + 1, vector<int>(m + 1)); 47 for (int i = 1; i <= n; i++) 48 for (int j = 1; j <= m; j++) 49 { 50 int num; 51 scanf("%d", &num); 52 a[i][j] = num; 53 } 54 int l = 1, r = min(n, m), ans; 55 while (l <= r) 56 { 57 int mid = (l + r) >> 1; 58 if (check(mid, a)) 59 { 60 l = mid + 1; 61 ans = mid; 62 } 63 else 64 r = mid - 1; 65 } 66 cout << ans << endl; 67 } 68 return 0; 69 }
标签：Divide,841,奇数,int,Codeforces,异或,vector,include,除数 From： https://www.cnblogs.com/cilinmengye/p/17011231.html