给用unordered_map的后人提供代码

· · 个人记录

P3190 [HNOI2007]神奇游乐园

题解里面没有用unordered\_map代替哈希表的代码，容易掉进一个陷阱

（本人自闭了两天）

刚好改完之后去考古讨论区发现也有人栽坑里了

这里提醒一下

(本文几乎不讲思路，代码中有思路的注释，主要是给用STL的一个提醒和参考)

先贴一段错误代码：

if(!ctl&&!ctr)//第一个位置和第二个位置无插头进入 
{
    f[nxt][S]=max(f[nxt][S],val); 
    if(j!=m&&i!=n)//可以新建两个插头 
    f[nxt][S^Get_s(1,j-1)^Get_s(2,j)]=max(f[nxt][S^Get_s(1,j-1)^Get_s(2,j)],val+g[i][j]);
}

本人习惯对于轮廓线上的与当前点相邻的两个位置叫第一个位置和第二个位置

若为1，则叫左插头，2叫右插头。（学的时候有些人括号表示法和上下左右插头乱叫属实是让我学的很崩溃)

错误原因：若val+g[i][j]此时的值为负数,由于f未初始化，导致默认为0，因此发生了错误的转移，导致答案会偏大。

比如样例你会发现你输出4100，找了半天发现是(2,2)(2,3)这里val+g[i][j]的值为-100，但是被错误搞成了0，导致答案变成了4100

改正方法：先查找是否存在值，分类讨论

新建一个插入函数

void Insert(int pos,int S,int val)
{
    if(f[pos].find(S)==f[pos].end())
        f[pos][S]=val;
    else
        f[pos][S]=max(f[pos][S],val);
}

完整代码：

#include<bits/stdc++.h>
#include<unordered_map>
#define int long long
#define inf 1e18
#define inc 0xcfcfcfcf
#define N 107
#define M 17
#define mod 1000000007
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
using namespace std;
int T=1,n,m,ex,ey;
int ans=-inf; 
int g[N][M];
unordered_map<int,int> f[2];
inline int Read()
{
    char ch=getchar();bool f=0;int x=0;
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
    for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    if(f==1)x=-x;return x;
}
int Get_s(int num,int pos){return (num<<(pos<<1));}//得到第pos位为num的四进制 
void Insert(int pos,int S,int val)
{
    if(f[pos].find(S)==f[pos].end())
        f[pos][S]=val;
    else
        f[pos][S]=max(f[pos][S],val);
}
void Ctdp()
{
    int now=0;
    int mxn=(1<<((m+1)<<1))-1;//m+1位全为3的四进制码，方便后面截去m+1位之后的数 
    f[now][0]=0; 
    f[now^1].clear();
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            int nxt=now^1;
            for(auto k:f[now])
            {
            //printf("(%lld,%lld)qwq\n",i,j);
                int S=k.first,val=k.second;  
                int ctl=(S>>((j-1)<<1))&3,ctr=(S>>(j<<1))&3;//ctl表示当前格子第一个插头，为1表示左插头，2为右插头，ctr类似
                //下面为当前格子必须放置插头
                if(!ctl&&!ctr)//若本来无插头进入 
                {
                    Insert(nxt,S,val);
                    if(j!=m&&i!=n)//可以新建两个插头 
                        Insert(nxt,S^Get_s(1,j-1)^Get_s(2,j),val+g[i][j]);
                }
                if(!ctl&&ctr)//若只有第二个插头，可转移到下方和右方 
                {
                    if(i!=n)
                        Insert(nxt,S^Get_s(ctr,j-1)^Get_s(ctr,j),val+g[i][j]);
                    if(j!=m)
                        Insert(nxt,S,val+g[i][j]);
                }
                if(ctl&&!ctr)//若只有第一个插头，也类似地可转移到下方和右方 
                {
                    if(j!=m)
                        Insert(nxt,S^Get_s(ctl,j-1)^Get_s(ctl,j),val+g[i][j]);
                    if(i!=n)
                        Insert(nxt,S,val+g[i][j]);
                }
                //下面为两个插头都存在 
                if(ctl==ctr)//两个插头性质相同 
                {
                    if(ctl==1)//如果都为左插头，则右边最近的一个右插头要变为左插头 
                    {
                        int cnt=1;
                        for(int p=j+1;;++p)
                        {
                            int pos=(S>>(p<<1))&3;
                            if(pos==1) ++cnt;
                            if(pos==2) --cnt;
                            if(cnt==0)
                            {
                                Insert(nxt,S^Get_s(ctl,j-1)^Get_s(ctr,j)^Get_s(2,p)^Get_s(1,p),val+g[i][j]);
                                break;
                            }   
                        }
                    }
                    if(ctl==2)//如果都是右插头，则左边最近的左插头要变为右插头 
                    {
                        int cnt=1;
                        for(int p=j-2;;--p)
                        {
                            int pos=(S>>(p<<1))&3;
                            if(pos==2) ++cnt;
                            if(pos==1) --cnt;
                            if(cnt==0)
                            {
                                Insert(nxt,S^Get_s(ctl,j-1)^Get_s(ctr,j)^Get_s(2,p)^Get_s(1,p),val+g[i][j]);
                                break;
                            }   
                        }
                    }
                }
                if(ctl==1&&ctr==2)//如果第一个为左插头，第二个为右插头，则形成回路
                    ans=max(ans,val+g[i][j]);
                if(ctl==2&&ctr==1)//如果第一个为右插头，第二个为左插头，则形成一条线段，不影响其他线段，消除两个插头转移 
                    Insert(nxt,S^Get_s(2,j-1)^Get_s(1,j),val+g[i][j]);

            }
            f[now].clear();
            now^=1;
        }
        for(auto k:f[now])//当转移到下一行的时候要注意所有状态应该四进制右移一位，然后截去最高的那位四进制，原理靠图理解 
        {
            int S=k.first,val=k.second;
            f[now^1][(S<<2)&mxn]+=val;
        }
        f[now].clear();
        now^=1;
    }
}
bool Solve()
{
    //freopen("test.in","r",stdin);
    n=Read(); m=Read();
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            g[i][j]=Read();     
    Ctdp();
    printf("%lld\n",ans);
    return true;
}
signed main()
{
    //T=Read();
    while(T--)
        if(!Solve())
            printf("-1\n");
    return 0;
}
/*
-std=c++11
-std=c99
*/