首页 > 其他分享 >题解:[XIX Open Cup, Grand Prix of Korea] Dev, Please Add This!

题解:[XIX Open Cup, Grand Prix of Korea] Dev, Please Add This!

时间:2024-11-12 19:43:02浏览次数:1  
标签:tmp Korea Cup int 题解 vis low id 极长

前置知识:2-SAT

题意

[XIX Open Cup, Grand Prix of Korea] Dev, Please Add This!

在一张网格上有以下几种物品:

  • 空地(.
  • 墙(#
  • 星星(*
  • 一个球(O

现在你要玩一个游戏。你可以让球朝上下左右某一个方向移动,但是一旦移动就必须走到底,也就是说直到前面是墙或者边界才能停。另外,如果你走到了带有星星的格子上,你可以获得它。

你的任务是,判断一张网格是否有吃完所有星星的方案。

样例1

输入:
3 7
#..O..#
#.###.#
*..#..*

输出:
NO

不难发现没有两个星星都吃到的方案。因为一旦吃到一个星星就回不到起点了。

输入:
6 6
*..*##
..O...
*..*#.
####*.
......
.....#

输出:
YES

可以按照以下的步骤:右、下、左、下、右、上、右、上、左、上、右、下、左。

思路

首先,根据题目列出条件:

  1. 起点走不到的点不可能走到(合法性);
  2. 若两个位置不能相互可达,则这两个位置不可能都走到(合法性);
  3. 每个星星要么横着走到,要么竖着走到,不能不经过(目标)。

没了。显然,满足它们的路径存在,等价于有方案吃完所有星星。

那看到上面的加粗部分,就容易想到 2-SAT 了:

我们对所有「一段横向或纵向的极长可行走区间」编一个号作为图上的节点,u 表示该节点走,pre + u 表示该节点不走。然后从节点每个点跑一遍 dfs(或 bfs),令 vis[u][v] 表示可以从 u 到达 v。然后那么可以转为:

  1. !vis[起点所属极长横区间][i] && !vis[起点所属极长纵区间][i],则走不到,连边 i -> pre + i
  2. !vis[u][v] && !vis[v][u],则不能互相走到,连边 u -> pre + vv -> pre + u
  3. 若某一个格子是星星,令所属极长横区间的编号为 u,所属极长纵区间的编号为 v,则连边 pre + u -> vpre + v -> u

然后跑 2-SAT 即可。时间复杂度 \(\mathcal{O}(能过并且绰绰有余)\)。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 55, D = N * N * 2;
struct two_sat
{
    int n;
    vector<int> g[D];
    void addEdge(int u, int v)
    {
        g[u].push_back(v);
    }
    int dfncnt, dfn[D], low[D], stk[D], tp;
    bool instk[D];
    int scccnt, id[D];
    void tarjan(int u)
    {
        dfn[u] = low[u] = ++dfncnt;
        stk[++tp] = u;
        instk[u] = true;
        for (int v : g[u])
        {
            if (!dfn[v])
            {
                tarjan(v);
                low[u] = min(low[u], low[v]);
            }
            else if (instk[v])
                low[u] = min(low[u], dfn[v]);
        }
        if (dfn[u] == low[u])
        {
            ++scccnt;
            int v;
            do
            {
                v = stk[tp--];
                instk[v] = false;
                id[v] = scccnt;
            } while (v != u);
        }
    }
} t;
int n, m, id[2][N][N], st;
// id[0][x][y]表示(x,y)所属的横向极长区间
// id[1][x][y]表示(x,y)所属的纵向极长区间
char s[N][N];
pair<int, int> l[D], r[D], S;    // 每个极长区间的左右/上下端点
bool vis[D][D];                  // vis[u][v]表示u能走到v

void dfs(int u)
{
    vis[st][u] = true;
    auto tmp = l[u];
    int v = u ^ id[0][tmp.first][tmp.second] ^ id[1][tmp.first][tmp.second];
    /*
    上面那行代码等价于:
    if (u == id[0][tmp.first][tmp.second])
    	v = id[1][tmp.first][tmp.second];
    else
		v = id[0][tmp.first][tmp.second];
	下面同理。作用是分别从两个端点走,但要跟当前的方向不一样。
    */
    if (!vis[st][v])
        dfs(v);
    tmp = r[u];
    v = u ^ id[0][tmp.first][tmp.second] ^ id[1][tmp.first][tmp.second];
    if (!vis[st][v])
        dfs(v);
}

int main()
{
#ifdef aquazhao
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        scanf("%s", s[i] + 1);
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (s[i][j] == '#')
                continue;
            if (j == 1 || s[i][j - 1] == '#')
                l[++cnt] = {i, j};
            id[0][i][j] = cnt;
            if (j == m || s[i][j + 1] == '#')
                r[cnt] = {i, j};
        }
    for (int j = 1; j <= m; j++)
        for (int i = 1; i <= n; i++)
        {
            if (s[i][j] == '#')
                continue;
            if (i == 1 || s[i - 1][j] == '#')
                l[++cnt] = {i, j};
            id[1][i][j] = cnt;
            if (i == n || s[i + 1][j] == '#')
                r[cnt] = {i, j};
        }
    for (st = 1; st <= cnt; st++)
        dfs(st);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (s[i][j] == '*')
            {
                t.addEdge(id[0][i][j] + cnt, id[1][i][j]);
                t.addEdge(id[1][i][j] + cnt, id[0][i][j]);
            }
            else if (s[i][j] == 'O')
                S = {i, j};
        }
    for (int i = 1; i <= cnt; i++)
        if (!vis[id[0][S.first][S.second]][i] && !vis[id[1][S.first][S.second]][i])
            t.addEdge(i, i + cnt);
    for (int i = 1; i <= cnt; i++)
        for (int j = i + 1; j <= cnt; j++)
            if (!vis[i][j] && !vis[j][i])
            {
                t.addEdge(i, j + cnt);
                t.addEdge(j, i + cnt);
            }
    for (int i = 1; i <= cnt + cnt; i++)
        if (!t.dfn[i])
            t.tarjan(i);
    bool ans = true;
    for (int i = 1; i <= cnt; i++)
        if (t.id[i] == t.id[i + cnt])
        {
            ans = false;
            break;
        }
    puts(ans ? "YES" : "NO");
    return 0;
}

标签:tmp,Korea,Cup,int,题解,vis,low,id,极长
From: https://www.cnblogs.com/avalaunch/p/18542515

相关文章

  • 【题解】洛谷P7286:「EZEC-5」人赢
    P7286「EZEC-5」人赢可以想到对于每个数要找到比他大的数中下标最大的数,我们按照数的大小排序,我们维护原序列的一个指针,对于每个数如果比指针大那么就左移指针,可以思考下为什么:指针上的数比现在这个数要小那比后面的数都小,于是我们左移指针直到大于这个数,可以发现我们也在一直......
  • 【题解】洛谷P8346:最澄澈的空与海
    【题解】洛谷P8346:最澄澈的空与海猜结论题,本身其实很简单,在纸上画个差不多就能想出来,我一开始想二分图最大匹配,但是还是太大了,不可以。当一个二分图有且仅有一种解时,必定有节点的入度为\(1\)。我们想到有多种匹配的情况,可以想到如果这是一个环的情况,一个左边的点将他右边的点......
  • MX-S5 T1~T2 题解
    MX-S5题解A.王国边缘题目链接见到循环结构,先把下标转成从\(0\)开始,以方便用同余描述位置。倍增。用二元组来表示位置:\((u,v)\)表示第\(u\)个循环节的第\(v\)个位置。设\(f(i,j)\)表示从位置\((0,i)\)开始跳\(2^j\)次以后的位置。假设已经可以初始化\(f(i,......
  • CF 705 题解
    CF705题解AHulk模拟即可.BSpiderMan打sg表可以发现,奇数个球先手必败(sg=0),偶数先手必胜(sg=1).多个组合只要把sg值异或起来就好.CThor暴力模拟就可以了,用队列模拟.DAntMan结论:按照编号由小到大加入链表,每次尽量让答案最小贪心就是对的.若原来是......
  • 题解:洛谷 P5180 【模板】支配树
    在图论模拟赛被T4的有向图必经点硬控了\(10^9+7s\),写篇题解纪念一下。其实,求有向图的必经点,通法就是支配树。一些定义:支配点:在确定起点\(S\)的情况下,对于一个点\(k\),若存在\(x\),使得删除\(x\)以及与\(x\)连接的边后,\(x\)与\(k\),不再强连通,那么就称\(k\)为\(x......
  • 【题解】洛谷P3118: Moovie Mooving G
    洛谷P3118:MoovieMoovingG看到数据范围考虑状压,题目要求看的电影最少那就维护时间最大,我们设\(f_{i}\)为\(i\)状态最多可以看多久的电影,对于不在集合的点我们枚举转移。我们每个开始时间都对应一个截至时间,问能加入这个点,每个点花费时间是固定的,我们又要不间断所以我们找......
  • CF785D 题解
    CF题目luogu题目题解似乎清一色是同一个做法,这里给一个容斥的做法。首先枚举一个位置\(i\),设\([1,i]\)的左括号个数为\(p\),\([i+1,n]\)的右括号个数为\(q\),那么以\(i\)这个位置为分界点的合法括号数有\(\sum_{i=1}^{\min(p,q)}C_p^iC_q^i\)个。通过范德蒙德卷......
  • CF 1325 题解
    CF1325题解AEhAbAnDgCd有\(\gcd(1,x)=1,\text{lcm}(1,x)=x\),因此输出\(1x\).BCopyCopyCopyCopyCopy要求严格上升子序列,那么答案的上界当然是去重后的元素个数.能否取到上界呢?当然可以,每一段内选一个你想要的就可以了.CEhabandPath-eticMEXs发现\(0,......
  • 历年CSP-J初赛真题解析 | 2020年CSP-J初赛完善程序(34-43)
    学习C++从娃娃抓起!记录下CSP-J备考学习过程中的题目,记录每一个瞬间。附上汇总贴:历年CSP-J初赛真题解析|汇总_热爱编程的通信人的博客-CSDN博客(质因数分解)给出正整数n,请输出将n质因数分解的结果,结果从小到大输出。例如:输入n=120,程序应该输出22235,表示120=2×2×2×......
  • 博弈论(零和博弈)英文版题解
    翻译:   假设我们有一个两人零和游戏,每个玩家有两种行动,行收益矩阵如下:计算行和列玩家的最小最大最优策略以及游戏的价值。      X     YA    a11   a12B    a21   a22选项:1.行玩家:第一种行动的概率为三分之二,第......