首页 > 其他分享 >HDU 2873 Bomb Game

HDU 2873 Bomb Game

时间:2024-08-16 15:50:49浏览次数:12  
标签:2873 HDU Bomb vis Game SG

题目链接:HDU 2873【Bomb Game】



思路

       数据范围较小,直接暴力求所有状态的SG值,然后将棋盘上所有炸弹的对应位置的SG值异或起来就可以得到当前局面的结果。对于相同位置的上有两个炸弹会自动爆炸,本来他们的SG值的异或和就为0,所以可以不用管。


代码

int n, m, vis[N * N], sg[N][N], test;
char mp[N][N];
void SG() {
  memset(sg, 0, sizeof sg);
  memset(vis, 0, sizeof vis);
  for (int i = 1; i <= 50; i++) {
    sg[i][1] = sg[1][i] = i - 1;
  }

  for (int i = 2; i <= 50; i++) {
    for (int j = 2; j <= 50; j++) {
      for (int a = 1; a < i; a++) {
        for (int b = 1; b < j; b++) {
          vis[sg[i][b] ^ sg[a][j]] = i * 100 + j;
        }
      }
      int temp = i * 100 + j;
      while (vis[sg[i][j]] == temp) {
        sg[i][j]++;
      }
    }
  }
}

void solve() {
  while (~scanf("%d%d", &n, &m)) {
    if (n == 0 || m == 0) {
      break;
    }
    ll res = 0;
    for (int i = 1; i <= n; i++) {
      scanf("%s", mp[i] + 1);
      for (int j = 1; j <= m; j++) {
        if (mp[i][j] == '#')
          res ^= sg[i][j];
      }
    }
    if (res == 0) {
      cout << "Jack" << endl;
    } else {
      cout << "John" << endl;
    }
  }
}

int main() {
  SG();
  solve();
  return 0;
}

标签:2873,HDU,Bomb,vis,Game,SG
From: https://www.cnblogs.com/againss/p/18362994

相关文章

  • HDU 3980 Paint Chain
    题目链接:HDU3980【PaintChain】思路    第一次操作,无论从哪个珠子开始染色,都会得到相同的长度为n-m的链,然后就是在这条链中取一段长度为m的珠子染色,当这一段珠子在链条中间的时候,就会把链条分成两段,就是一个简单的两段连续珠子的长度的sg值异或一下,求出sg[n-m]的......
  • HDU 2999 Stone Game, Why are you always there?
    题目链接:HDU2999【StoneGame,Whyareyoualwaysthere?】思路    由于只能取连续的一段石子,当取出的石子是这段石子的中间一部分时就相当于将一段石子分成两段石子,简单异或一下求SG值就行了代码intsg[N],vis[N],a[N];intn,m,k;voidgetsg(){memset......
  • HDU-ACM 2024 Day3
    T1004游戏(HDU7460)注意到对于两个人,他们\(t\)轮后能力值相同的概率只与他们初始时的能力差有关,所以我们先\(\text{FFT}\)求出\(|a_i-a_j|=k\)的\((i,j)\)对数。构造多项式\(F(x)=(p_1x^2+p_2+p_3x)\),其中\(p_1,p_2,p_3\),分别表示在一轮中两个人相对......
  • hdu7462-字符串【SAM,二分】
    正题题目链接:https://acm.hdu.edu.cn/showproblem.php?pid=7462题目大意你有一个由\(a,b\)组成的字符串\(s\)。有\(m\)个操作:询问有多少个本质不同的串\(t\)使得\(s[l,r]\)是\(t\)的子串且两个串在\(s\)中的出现次数相同。询问有多少个本质不同的串\(t\)......
  • [题解 hduoj-7522] 2024HDU 暑假多校7 - cats 的最小生成树
    原题链接题意有一个有重边的无向图,每次找到它的最小生成树,并删除生成树的边,直到不存在最小生成树,问被每条边在第几次被删除.思路考虑用类似Kruskal算法,但是是遍历一遍所有边,同时处理出来所有的生成树.具体这样做:如Kruskal一样,把所有边按边权排序,......
  • HDU 不要62 题解
    题目传送门思路数位dp数位dp数位dp模版题。依次考虑每一位,满足题目给出的限制,统计数量,是一些较简单的数位dp题目的过程。数位dp运用了差分的思想,即求\(ans(l-r)\)的答案用\(ans(1-r)-ans(1-(l-1))\)来表示.对于本题,我们需要满足的性质很简单:使数不超......
  • HDU-ACM 2024 Day2
    T1004a*bproblem(HDU7448)不会。T1005小塔的养成游戏之梦(HDU7449)不会。T1009强攻计策(HDU7453)容易发现初始速度是多少对答案没有影响,所以我们默认初始速度为\(0\)。题意相当于在平面直角坐标系上(横轴为时间,纵轴为速度),有一个目标高度,维护一条尽量接近目标的直线,但......
  • HDU6567 Cotree
    题意有两颗树,在每棵树中选择一个结点并将它们两相连使得对于新的树的任意两点的距离总和最小。思路设\(sz[u]\)表示子树\(u\)的大小。显然,将两数重心连接结果最优秀(根据树的重心定义)。对于每条边,取它两端\(sz\)较小的那一个点\(u\),那么这条边贡献为\(sz[u]*(n-sz......
  • 2024HDU 6th
    T1显然我们选择的点度数为2。考虑若答案为Yes,则原图最多有5个度数为2的点。多于5个直接判为No。因此可以枚举所有度数为2的点,暴力判断以该点为根,两个儿子的子树是否为菊花图。这是简单的,因为树为菊花图当且仅当点数不超过2或者一度点的个数等于点数-1。时间复杂度\(O(n)\)。......
  • HDU 多校 2024 Round 2
    A-鸡爪肯定是希望\(1,2,3\)的度数尽可能多。考虑答案一定是\(\lfloor\dfrac{n}{3}\rfloor\),所以把前面\(1\sim\lfloor\dfrac{n}{3}\rfloor\)都作为鸡爪的中心,并且向\(1,2,3\)连边。剩下一些再连到\(1,2\)上面去。B-梦中的地牢战斗建分层图跑最长路,由于没有正环,所......