发布于 由itewqq

[搜索][meet in the middle] CF1006F Xor-Paths

https://cn.vjudge.net/problem/CodeForces-1006F

题意要求从矩形左上角走到右下角的路，满足只能向右/向下走，然后路上的数值以后之后的值等于k。

简单的想的话，所有可能的情况大概是C(20,40)，无疑超时，然后记录下到每个点的所有xor值的数量的话就可以meet in the middle了，另一个搜索从右下角开始，两个都只需要搜一半长度，对于这种指数复杂度的来说就相当于开了根号，复杂度暴降，值得拥有。
注意的点，第一是map的使用，感觉自己这些还是有点不灵活。。。第二是LL，已经不知道因为这个错过多少次了。。包括参数表里的long long和int也是注意的点

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include


using namespace std;
typedef long long LL;
const int maxn=17+5;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;

LL ar[maxn][maxn];
LL half;
LL n,m,k;
mapmp[maxn][maxn];

void dfs1(int x,int y,LL val,int cnt)
{
    
    val^=ar[x][y];
    if(cnt==half)
    {
        ++mp[x][y][val];
        return ;
    }
    if(x<=n)
    {
        dfs1(x+1,y,val,cnt+1);
    }
    if(y<=m)
    {
        dfs1(x,y+1,val,cnt+1);
    }
    return ;
}
LL ans;
void dfs2(int x,int y,LL val,int cnt)//val is LL!
{
    
    if(cnt==n+m-2-half)
    {
        if(mp[x][y].count(val^k))//xor's property!
        ans+=mp[x][y][val^k];
        return ;
    }
    val^=ar[x][y];
    if(x>=1)
    {
        dfs2(x-1,y,val,cnt+1);
    }
    if(y>=1)
    {
        dfs2(x,y-1,val,cnt+1);
    }
    return ;
}

int main()
{
    cin>>n>>m>>k;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        scanf("%lld",&ar[i][j]);
    half=(n+m-2)>>1;
    dfs1(1,1,0,0);
    dfs2(n,m,0,0);
    cout<

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

此站点使用 Akismet 来减少垃圾评论。了解我们如何处理您的评论数据。