Gym-100883F、Gym-101095B状态压缩小结

　　状态压缩的核心思想就是将数压缩成二进制，用二进制位来表示对应的位能取或者不能取，相比起来很方便。

　　题意：给你两个字符串，要求你将两个字符串合起来，并不改变原先的顺序，一共有多少种情况。

　　首先看到这个想到的是dfs，而我傻傻的用next_permutation华丽丽的T了，我好瓜皮啊，嘻嘻，这个题不仅仅可以用dfs写，还可以用状态压缩。

char a[100], b[100];

map<string, int>mp;

void solve() {

    mp.clear();   int num=0;

    scanf("%s %s", a, b);

    string ans[maxn];

    int lena=strlen(a), lenb=strlen(b);

    for (int i = 0; i < (1<<(lena+lenb)); i++) {

        int num1=0, num0=0;

        int aa=0, bb=0;

        for (int j = 0; j < lena+lenb; j++) {

            if ((1<<j)&i) {　　//表示j位置取不取

                num1++;

            }

        }

        if (num1==lena) {

            for (int j=0; j < lena+lenb; j++) {

                if ((1<<j)&i) {

                    ans[num]+=a[aa++];

                }

                else ans[num]+=b[bb++];

            }

            num++;

        }

    }

    sort(ans, ans+num);

    ans[num] = "A";

    for (int i = 0; i < num; i++) {

        if (ans[i]!=ans[i+1])  cout << ans[i] << endl;

    }

    cout << endl;

}

int main() {

    //cin.sync_with_stdio(false);

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

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

    int t = 1;

    scanf("%d", &t);

    while (t--) {

        solve();

    }

    return 0;

}

　　Gym-101095B

char ma[25][25];

int maa[25][25];

int m[25][25];

int r, c, ans;

int dir[][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};

bool safe(int x, int y) {

    if (x<0||x>=r||y<0||y>=c)  return 0;

    return 1;

}

int deal() {

    int nu=0;

    for (int i = 1; i < r; i++) {

        for (int j=0; j < c; j++) {

            if (maa[i-1][j]==0) {

                nu++;

                maa[i][j]^=1;

                for (int k=0; k<4; k++) {

                    int xx=i+dir[k][0], yy=j+dir[k][1];

                    if (safe(xx, yy)) {

                        maa[xx][yy]^=1;

                    }

                }

            }

        }

    }

    for (int i = 0; i < r; i++) {

        for (int j =0; j < c;j++) {

            if (!maa[i][j])  return -1;

        }

    }

    return nu;

}

void solve() {

    memset(ma, 0, sizeof(ma));

    memset(m, 0, sizeof(m));

    while(scanf("%d%d", &r, &c)) {

        if (!r&&!c)  break;

        ans = inf;

        int flag=0;

        for (int i=0; i < r; i++)

            scanf("%s", ma[i]);

        if (r<c) {

            char mm[25][25];

            for (int i = 0; i < r; i++) {

                for (int j = 0; j < c; j++) {

                    mm[j][i] = ma[i][j];

                }

            }

            swap(r, c);

            for (int i = 0; i < r; i++) {

                for (int j = 0; j < c; j++) {

                    ma[i][j] = mm[i][j];

                }

            }

        }

      //  for (int i=0; i < r; i++)  cout << ma[i] << endl;

        for (int i=0; i < r; i++) {

            for (int j=0; j<c; j++) {

                if (ma[i][j]=='X')  m[i][j]=0;

                else  m[i][j]=1;

            }

        }

        for (int i = 0; i < (1<<c); i++) {

            for (int ii=0; ii<r; ii++) {

                for (int jj=0; jj < c; jj++) {

                    maa[ii][jj] = m[ii][jj];

                }

            }

            int num=0;

            for (int j=0; j < c; j++) {

                if ((1<<j)&i) {

                    num++;

                    maa[0][j]=maa[0][j]^1;

                    for (int ii=0; ii<4; ii++) {

                        int xx=0+dir[ii][0], yy=j+dir[ii][1];

                        if (safe(xx, yy)) {

                            maa[xx][yy] ^= 1;

                        }

                    }

                }

            }

            int tmp = deal();

            if (tmp == -1) continue;

            num += tmp;

            ans = min(ans, num);

            flag=1;

        }

        if (flag)printf("You have to tap %d tiles.\n", ans);

        else  puts("Damaged billboard.");

    }

}

int main() {

    //cin.sync_with_stdio(false);

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

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

    int t = 1;

    while (t--) {

        solve();

    }

    return 0;

}

巴特西

Gym-100883F、Gym-101095B状态压缩小结

最新文章

热门文章