0%

Codeforces 1006F Xor-Paths 双向dfs

题目链接
题意:简而言之,一个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);
}
-------------这么快就看完啦^ω^谢谢阅读哟-------------