【插头dp】 hdu4285 找bug

时间：2021-03-15 20:10:09

打模板的经验：

1.变量名取一样，换行也一样，不要宏定义

2.大小写，少写，大括号

#include<algorithm>

#include<iostream>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<stdio.h>

#include<vector>

#include<queue>

#include<string>

#include<ctime>

#include<stack>

#include<map>

#include<set>

#include<list>

using namespace std;

#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)

#define per(i,j,k) for(int i = (int)j;i >= (int)k;i --)

#define debug(x) cerr<<#x<<" = "<<(x)<<endl

#define mmm(a,b) memset(a,b,sizeof(a))

#define pb push_back

//#define x first

//#define y second

typedef double db;

typedef long long ll;

const int MAXD = 15;

const int STATE = 1e6 + 5;

const int HASH = 3e5 + 7;

const int MOD = 1e9 + 7;

int N, M, K;

int maze[MAXD][MAXD];

int code[MAXD];

int ch[MAXD];

int num;

struct HASHMAP

{

	int head[HASH], next[STATE], size;

	ll state[STATE];

	int f[STATE];

	void init()

	{

		size = 0;

		mmm(head, -1);

	}

	void push(ll st, int ans)

	{

		int i;

		int h = st % HASH;

		for (i = head[h]; i != -1; i = next[i])

			if (state[i] == st)

			{

				f[i] += ans;

				f[i] %= MOD;

				return;

			}

		state[size] = st;

		f[size] = ans;

		next[size] = head[h];

		head[h] = size++;

	}

}hm[2];

void decode(int *code, int m, long long st)

{

	num = st & 63;

	st >>= 6;

	for (int i = m; i >= 0; i--)

	{

		code[i] = st & 7;

		st >>= 3;

	}

}

ll encode(int *code, int m)

{

	int cnt = 1;

	mmm(ch, -1);

	ch[0] = 0;

	ll st = 0;

	rep(i, 0, m)

	{

		if (ch[code[i]] == -1)ch[code[i]] = cnt++;

		code[i] = ch[code[i]];

		st <<= 3;

		st |= code[i];

	}

	st <<= 6;

	st |= num;

	return st;

}

void shift(int *code, int m)

{

	for (int i = m; i > 0; i--)code[i] = code[i - 1];

	code[0] = 0;

}

void dpblank(int i, int j, int cur)

{

	int k, left, up;

	for (k = 0; k < hm[cur].size; k++)

	{

		decode(code, M, hm[cur].state[k]);

		left = code[j - 1];

		up = code[j];

		if (left&&up)

		{

			if (left == up)

			{

				if (num >= K)continue;

				int t = 0;

				for (int p = 0; p < j - 1; p++)

					if (code[p])t++;

				if (t & 1)continue;

				if (num < K)

				{

					num++;

					code[j - 1] = code[j] = 0;

					hm[cur ^ 1].push(encode(code, j == M ? M - 1 : M), hm[cur].f[k]);

				}

			}

			else

			{

				code[j - 1] = code[j] = 0;

				for (int t = 0; t <= M; t++)

					if (code[t] == up)

						code[t] = left;

				hm[cur ^ 1].push(encode(code, j == M ? M - 1 : M), hm[cur].f[k]);

			}

		}

		else if (left || up)

		{

			int t;

			if (left) t = left;

			else t = up;

			if (maze[i][j + 1])

			{

				code[j - 1] = 0;

				code[j] = t;

				hm[cur ^ 1].push(encode(code, M), hm[cur].f[k]);

			}

			if (maze[i + 1][j])

			{

				code[j] = 0;

				code[j - 1] = t;

				hm[cur ^ 1].push(encode(code, j == M ? M - 1 : M), hm[cur].f[k]);

			}

		}

		else

		{

			if (maze[i][j + 1] && maze[i + 1][j])

			{

				code[j - 1] = code[j] = 13;

				hm[cur ^ 1].push(encode(code, j == M ? M - 1 : M), hm[cur].f[k]);

			}

		}

	}

}

void dplock(int i, int j, int cur)

{

	int k;

	for (k = 0; k < hm[cur].size; k++)

	{

		decode(code, M, hm[cur].state[k]);

		code[j - 1] = code[j] = 0;

		hm[cur ^ 1].push(encode(code, j == M ? M - 1 : M), hm[cur].f[k]);

	}

}

char str[20];

void init()

{

	cin >> N >> M >> K;

	mmm(maze, 0);

	rep(i, 1, N)

	{

		scanf("%s", &str);

		for (int j = 1; j <= M; j++)

			if (str[j - 1] == '.')

				maze[i][j] = 1;

	}

}

void solve()

{

	int  cur = 0;

	hm[cur].init();

	hm[cur].push(0, 1);

	rep(i, 1, N)

		rep(j, 1, M)

	{

		hm[cur ^ 1].init();

		if (maze[i][j])dpblank(i, j, cur);

		else dplock(i, j, cur);

		cur ^= 1;

	}

	int ans = 0;

	for (int i = 0; i < hm[cur].size; i++)

		if (hm[cur].state[i] == K)

		{

			ans += hm[cur].f[i];

			ans %= MOD;

		}

	printf("%d\n", ans);

}

int main()

{

	int t;

	cin >> t;

	while (t--)

	{

		init();

		solve();

	}

	//cin >> t;

}

/*

2

4 4 1

**..

....

....

....

4 1

....

....

....

....

*/
/*

HDU 4285

要形成刚好K条回路的方法数

要避免环套环的情况。

所以形成回路时，要保证两边的插头数是偶数

G++ 11265ms  11820K

C++ 10656ms  11764K

*/

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string.h>

using namespace std;

const int MAXD=;

const int STATE=;

const int HASH=;//这个大一点可以防止TLE,但是容易MLE

const int MOD=;

int N,M,K;

int maze[MAXD][MAXD];

int code[MAXD];

int ch[MAXD];

int num;//圈的个数

struct HASHMAP

{

    int head[HASH],next[STATE],size;

    long long state[STATE];

    int f[STATE];

    void init()

    {

        size=;

        memset(head,-,sizeof(head));

    }

    void push(long long st,int ans)

    {

        int i;

        int h=st%HASH;

        for(i=head[h];i!=-;i=next[i])

          if(state[i]==st)

          {

              f[i]+=ans;

              f[i]%=MOD;

              return;

          }

        state[size]=st;

        f[size]=ans;

        next[size]=head[h];

        head[h]=size++;

    }

}hm[];

void decode(int *code,int m,long long  st)

{

    num=st&;

    st>>=;

    for(int i=m;i>=;i--)

    {

        code[i]=st&;

        st>>=;

    }

}

long long encode(int *code,int m)//最小表示法

{

    int cnt=;

    memset(ch,-,sizeof(ch));

    ch[]=;

    long long st=;

    for(int i=;i<=m;i++)

    {

        if(ch[code[i]]==-)ch[code[i]]=cnt++;

        code[i]=ch[code[i]];

        st<<=;

        st|=code[i];

    }

    st<<=;

    st|=num;

    return st;

}

void shift(int *code,int m)

{

    for(int i=m;i>;i--)code[i]=code[i-];

    code[]=;

}

void dpblank(int i,int j,int cur)

{

    int k,left,up;

    for(k=;k<hm[cur].size;k++)

    {

        decode(code,M,hm[cur].state[k]);

        left=code[j-];

        up=code[j];

        if(left&&up)

        {

            if(left==up)

            {

                if(num>=K)continue;

                int t=;

                //要避免环套环的情况，需要两边插头数为偶数

                for(int p=;p<j-;p++)

                  if(code[p])t++;

                if(t&)continue;

                if(num<K)

                {

                    num++;

                    code[j-]=code[j]=;

                    hm[cur^].push(encode(code,j==M?M-:M),hm[cur].f[k]);

                }

            }

            else

            {

                code[j-]=code[j]=;

                for(int t=;t<=M;t++)

                  if(code[t]==up)

                    code[t]=left;

                hm[cur^].push(encode(code,j==M?M-:M),hm[cur].f[k]);

            }

        }

        else if(left||up)

        {

            int t;

            if(left)t=left;

            else t=up;

            if(maze[i][j+])

            {

                code[j-]=;

                code[j]=t;

                hm[cur^].push(encode(code,M),hm[cur].f[k]);

            }

            if(maze[i+][j])

            {

                code[j]=;

                code[j-]=t;

                hm[cur^].push(encode(code,j==M?M-:M),hm[cur].f[k]);

            }

        }

        else

        {

            if(maze[i][j+]&&maze[i+][j])

            {

                code[j-]=code[j]=;

                hm[cur^].push(encode(code,j==M?M-:M),hm[cur].f[k]);

            }

        }

    }

}

void dpblock(int i,int j,int cur)

{

    int k;

    for(k=;k<hm[cur].size;k++)

    {

        decode(code,M,hm[cur].state[k]);

        code[j-]=code[j]=;

        hm[cur^].push(encode(code,j==M?M-:M),hm[cur].f[k]);

    }

}

char str[];

void init()

{

    scanf("%d%d%d",&N,&M,&K);

    memset(maze,,sizeof(maze));

    for(int i=;i<=N;i++)

    {

        scanf("%s",&str);

        for(int j=;j<=M;j++)

          if(str[j-]=='.')

            maze[i][j]=;

    }

}

void solve()

{

    int i,j,cur=;

    hm[cur].init();

    hm[cur].push(,);

    for(i=;i<=N;i++)

      for(j=;j<=M;j++)

      {

          hm[cur^].init();

          if(maze[i][j])dpblank(i,j,cur);

          else dpblock(i,j,cur);

          cur^=;

      }

    int ans=;

    for(i=;i<hm[cur].size;i++)

      if(hm[cur].state[i]==K)

      {

          ans+=hm[cur].f[i];

          ans%=MOD;

      }

    printf("%d\n",ans);

}

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int T;

    scanf("%d",&T);

    while(T--)

    {

        init();

        solve();

    }

    return ;

}

/*

Sample Input

4 4 1

**..

....

....

....

4 1

....

....

....

....

Sample Output

6

*/

#include<algorithm>#include<iostream>#include<stdlib.h>#include<string.h>#include<math.h>#include<stdio.h>#include<vector>#include<queue>#include<string>#include<ctime>#include<stack>#include<map>#include<set>#include<list>using namespace std;#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)#define per(i,j,k) for(int i = (int)j;i >= (int)k;i --)#define debug(x) cerr<<#x<<" = "<<(x)<<endl#define mmm(a,b) memset(a,b,sizeof(a))#define pb push_back//#define x first//#define y second
typedef double db;typedef long long ll;

const int MAXD = 15;const int STATE = 1e6 + 5;const int HASH = 3e5 + 7;const int MOD = 1e9 + 7;int N, M, K;int maze[MAXD][MAXD];int code[MAXD];int ch[MAXD];int num;struct HASHMAP{int head[HASH], next[STATE], size;ll state[STATE];int f[STATE];void init(){size = 0;mmm(head, -1);}void push(ll st, int ans){int i;int h = st % HASH;for (i = head[h]; i != -1; i = next[i])if (state[i] == st){f[i] += ans;f[i] %= MOD;return;}state[size] = st;f[size] = ans;next[size] = head[h];head[h] = size++;}}hm[2];void decode(int *code, int m, long long st){num = st & 63;st >>= 6;for (int i = m; i >= 0; i--){code[i] = st & 7;st >>= 3;}}ll encode(int *code, int m){int cnt = 1;mmm(ch, -1);ch[0] = 0;ll st = 0;rep(i, 0, m){if (ch[code[i]] == -1)ch[code[i]] = cnt++;code[i] = ch[code[i]];st <<= 3;st |= code[i];}st <<= 6;st |= num;return st;}void shift(int *code, int m){for (int i = m; i > 0; i--)code[i] = code[i - 1];code[0] = 0;}void dpblank(int i, int j, int cur){int k, left, up;for (k = 0; k < hm[cur].size; k++){decode(code, M, hm[cur].state[k]);left = code[j - 1];up = code[j];if (left&&up){if (left == up){if (num >= K)continue;int t = 0;
for (int p = 0; p < j - 1; p++)if (code[p])t++;if (t & 1)continue;if (num < K){num++;code[j - 1] = code[j] = 0;hm[cur ^ 1].push(encode(code, j == M ? M - 1 : M), hm[cur].f[k]);}}else{code[j - 1] = code[j] = 0;for (int t = 0; t <= M; t++)if (code[t] == up)code[t] = left;hm[cur ^ 1].push(encode(code, j == M ? M - 1 : M), hm[cur].f[k]);}}else if (left || up){int t;if (left) t = left;else t = up;if (maze[i][j + 1]){code[j - 1] = 0;code[j] = t;hm[cur ^ 1].push(encode(code, M), hm[cur].f[k]);}if (maze[i + 1][j]){code[j] = 0;code[j - 1] = t;hm[cur ^ 1].push(encode(code, j == M ? M - 1 : M), hm[cur].f[k]);}}else{if (maze[i][j + 1] && maze[i + 1][j]){code[j - 1] = code[j] = 13;hm[cur ^ 1].push(encode(code, j == M ? M - 1 : M), hm[cur].f[k]);}}}}void dplock(int i, int j, int cur){int k;for (k = 0; k < hm[cur].size; k++){decode(code, M, hm[cur].state[k]);code[j - 1] = code[j] = 0;hm[cur ^ 1].push(encode(code, j == M ? M - 1 : M), hm[cur].f[k]);}}char str[20];void init(){cin >> N >> M >> K;mmm(maze, 0);rep(i, 1, N){scanf("%s", &str);for (int j = 1; j <= M; j++)if (str[j - 1] == '.')maze[i][j] = 1;}}void solve(){int  cur = 0;hm[cur].init();hm[cur].push(0, 1);rep(i, 1, N)rep(j, 1, M){hm[cur ^ 1].init();if (maze[i][j])dpblank(i, j, cur);else dplock(i, j, cur);cur ^= 1;}int ans = 0;for (int i = 0; i < hm[cur].size; i++)if (hm[cur].state[i] == K){ans += hm[cur].f[i];ans %= MOD;}printf("%d\n", ans);
}int main(){int t;cin >> t;while (t--){init();solve();}//cin >> t;}/*24 4 1**..............4 1................*/

相关文章