题目链接
题意：简而言之，一个mn（2020）的数组，每个点有个权值，从（1,1）出发，每次可以向下/右走一个格，取路径所有权值的异或和^，求有几条路使从起点到到（m,n）的时候异或和为K(1e18)。
思路：
第一反应是裸dp，然后发现dp[i][j][k] = dp[i-1][j][ k^map[i][j] ] + dp[i][j-1][ k^map[i][j] ]但是第三维度显然存不下。
然后想了想mn不大，用vector<pair<long long, long long>>试试，i*m+j标号，把转移的（k,time）对都存在数组里，使用完清空，MLE。然后想遍历vector如果有first相同的元素更新second, TLE。然后想想好像跟暴力也没啥大区别。
然后想用map<pair<pair<int, int >, long long > >或者map<pair<int, int>, map >，发现不会stl嵌套。
然后看了看大神的代码，dfs超时，但是只有一个双向搜索就能搞定，连剪纸都不太要，感觉自己十分愚蠢。异或是满足结合律的。而且这个搜索只要先搜一半再对比一半就ok了，连动态左一下右一下都不要。
meet-in-the-middle。对于这个二维数组，一端的扫描从（1,1）开始，到达x+y = *在从左下到右上的那条先作为中轴线停止，x+y固定，下标只需要知道x就能取得y，map[long long]记录。然后从另一端找过来，也是到了中轴线就可以判断次数。这样极限条件下到达中线时两边搜索层数都在10-20层，时间复杂度很够用。
特别注意一下中线位置的x+y应该等于多少的细节问题
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include <bits/stdc++.h>
using namespace std;
const int MAXN = 22;
long long a[MAXN][MAXN];
int n, m;
long long KK, ans;
map<long long, long long>mp[MAXN];
void dfs_down(int x, int y, long long maxn)
{
if(x + y == (n + m - 1) / 2){mp[x][maxn]++;return;}
if(x < n-1)dfs_down(x+1, y, maxn^a[x+1][y]);
if(y < m-1)dfs_down(x, y+1, maxn^a[x][y+1]);
}
void dfs_up(int x, int y, long long maxn)
{
if(x + y == (n + m - 1) / 2){
if(mp[x].find(maxn ^ KK ^ a[x][y]) != mp[x].end()){
ans += mp[x][maxn ^ KK ^ a[x][y]];
}
return;
}
if(x > 0)dfs_up(x-1, y, maxn^a[x-1][y]);
if(y > 0)dfs_up(x, y-1, maxn^a[x][y-1]);
}
int main()
{
scanf("%d%d%lld", &n, &m, &KK);
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
scanf("%lld", &a[i][j]);
}
}
dfs_down(0,0, a[0][0]);
dfs_up(n-1, m-1, a[n-1][m-1]);
printf("%lld\n", ans);
}
|