首页 > 其他分享 >AT_abc306_h 题解

AT_abc306_h 题解

时间:2023-07-11 14:13:26浏览次数:45  
标签:int 题解 void abc306 砝码 max 集合 dp

AT_abc306_h Balance Scale 题解

洛谷

AtCoder

Description

有 \(N\) 个编号为 \(1,2,\dots,N\) 的砝码。有 \(M\) 次比较操作,每次比较砝码 \(A_{i}\) 和 \(B_{i}\),\(A_{i}\) 在左侧。

分为三种情况:

  1. 左边的砝码更重。
  2. 右边的砝码更重。
  3. 两边的砝码重量相同。

将每次比较的结果使用字符 ">"、"=" 或 "<" 记录下来,形成一个长度为 \(M\) 的字符串 \(S\)。求一共有多少种可能的\(S\)。答案对 \(998\,244\,353\) 取模。

Solution

考虑如何对一组确定的砝码判断是否可行,若 \(A_{i} < B_{i}\) 从 \(A_{i}\) 所在集合向 \(B_{i}\) 所在集合连边,若 \(A_{i} > B_{i}\) 从 \(B_{i}\) 所在集合向 \(A_{i}\) 所在集合连边,相等利用并查集合并。如果出现环了无解。

但每条边的方向不知道,考虑到数据范围很小,可以使用状压 dp 枚举一个独立集,表示初始度数为 \(0\) 的点。当我们删去其中度数为 \(0\) 的点时,仍满足条件,因此我们有转移状态:

\[dp_{i} = \sum_{s \subset i,s \neq \emptyset} dp_{i \setminus s} \]

但这样是错误的,某个集合本身被计算了,但他同时会作为另一个集合的子集被计算。我们容斥掉这些情况即可,考虑集合被算的次数与集合大小有关,简单的推出下面正确的转移方程。

\[dp_{i} = \sum_{s \subset i,s \neq \emptyset} dp_{i \setminus s} \times {(−1)^{ \left ( \left |s \right |+1 \right )}} \]

其中 \(\left |s \right |\) 表示集合 \(s\) 的元素个数。

Codes

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define max_n 410101
#define mo 998244353
void read(int &p)
{
    int k = 1;
    p = 0;
    char c = getchar();
    while(c < '0' || c > '9')
    {
        if(c == '-')
        {
            k =  -1;
        }
        c = getchar();
    }
    while(c >='0' && c <= '9')
    {
        p = p * 10 + c - '0';
        c = getchar();
    }
    p *= k;
    return ;
}
void write_(int x)
{
    if(x < 0)
    {
        putchar('-');
        x = -x;
    }
    if(x > 9)
    {
        write_(x / 10);
    }
    putchar(x % 10 + '0');
}
void writesp(int x)
{
    write_(x);
    putchar(' ');
}
void writeln(int x)
{
    write_(x);
    puts("");
}
int n,m;
int fa[max_n],dp[max_n];
pair<int,int> edge[max_n];
int can[max_n];
int find(int x)
{
    if(fa[x] == x)
    {
        return x;
    }
    return fa[x] = find(fa[x]);
}
void init()
{
    for(int i = 1;i <= n;i++)
    {
        fa[i] = i;
    }
}
int lowbit(int x)
{
    return (-x) & x;
}
int popcount(int x)
{
    int cnt = 0;
    while(x)
    {
        ++cnt;
        x -= lowbit(x);
    }
    return cnt;
}
signed main()
{
    read(n),read(m);
    for(int i = 1;i <= m;i++)
    {
        read(edge[i].first),read(edge[i].second);
    }
    for(int i = 0;i < (1LL << n);i++)
    {
        can[i] = popcount(i);
        init();
        for(int j = 1;j <= m;j++)
        {
            // 两个点都在集合中
            if((i & (1 << edge[j].first - 1)) && (i & (1 << edge[j].second - 1)))
            {
                // 合并
                if(find(edge[j].first) != find(edge[j].second))
                {
                    fa[find(edge[j].first)] = find(edge[j].second);
                    // 注意集合大小要减 1
                    --can[i];
                }
            }
        }
    }
    dp[0] = 1;
    for(int i = 1;i < (1 << n);i++)
    {
        for(int j = i;j;j = i &(j - 1))
        {
            if(can[j] & 1)
            {
                dp[i] += dp[i ^ j];
            }
            else
            {
                dp[i] += mo - dp[i ^ j];
            }
            (dp[i] += mo)%= mo;
        }
    }
    writeln(dp[(1 << n) - 1]);
    return 0;
}

标签:int,题解,void,abc306,砝码,max,集合,dp
From: https://www.cnblogs.com/yuhang-ren/p/17544470.html

相关文章

  • CF878E 题解
    CF878ENumbersontheblackboard题解Links洛谷CodeforcesDescription给出\(n\)个数字,每次询问一个区间\([l,r]\),对这个区间内部的点进行如下操作。每次操作可以合并相邻两个数\(x,y\),用\(x+2y\)替换它们。对于每次询问,输出当最后只剩下一个数字时,这个数字的最大......
  • CODE FESTIVAL 2017 Final J 题解
    problem&blog。萌萌点分治,积累个trick/qq。对于完全图\((V,E)\),将\(E\)分成\(E_1,E_2,\cdots,E_k\)(\(E_1\cupE_2\cup\cdots\cupE_k=E\))。对每个边集求MST,得到新边集\(E_1^{'},E_2^{'},\cdots,E_k^{'}\),再求MST。最终剩下的边集,等同于原边集的MST。......
  • P4016题解
    本题是一个比较经典的问题(环形均分纸牌问题),我也不知道为什么它在网络流24题里面出现。但是作为一道比较典的排序算法的题,还是放出来讲一下。solution假设\(a_1\)给\(a_n\)了\(x_1\)张纸牌,\(a_2\)给\(a_1\)了\(x_2\)张纸牌......(\(x_i\)可正可负)。因此操作数量为......
  • P2886题解
    题目大意给定起点\(S\)和终点\(T\),求从起点到终点恰好经过\(N\)(\(N\)给定)条边的最短路径。solution发现本题点数巨多,但是边数小到可怜,我们可以只保留了一部分点,先判断连通性,不连通直接输出即可。当\(S\)和\(T\)连通时,我们设\(G^k\)为经过\(k\)条边后最短路的邻......
  • Largest-Smallest-Cyclic-Shift题解
    题目链接本题码量不大,但是事实上是一道极其难想的思维题。题目描述你有\(a\)个a,\(b\)个b,\(c\)个c。要求用这\(a+b+c\)个字母拼接成一个字符串,使得这个字符串的最小表示法在所有能拼成的字符串中最大。补充:最小表示法,将一个字符串的最后一个字符放到首位,重复这个操作,......
  • AT-abc214-g题解
    题目描述给定两个排列\(p,q\),要求统计满足\(\foralli,r_i\not=p_i,r_i\not=q_i\)的排列\(r\)的数量。对\(1000000007\)取模数据范围\(n\le3000\)。solution本题要求统计数量,反正我想了半天没想到怎么正向统计(bushi),因此我们考虑容斥。设\(h_i\)为只看其中......
  • P3599题解
    本题是一道比较典的构造题,拿来扩宽扩宽大家的眼界吧。Task1试判断能否构造并构造一个长度为\(n\)的\(1\simn\)的排列,满足其\(n\)个前缀和在模\(n\)的意义下互不相同。很容易想到的一点是:\(n\)一定排在第一位,因为如果排在别的位,加上\(n\)后在模\(n\)意义下是不......
  • CF1421E题解
    题目链接本题作为一道本人思考了50分钟没想出来的大思维题,我觉得可以用来扩宽一下大家的视野。本题中,我们每次都会选取两个相邻的数\(a_i\)和\(a_{i+1}\),同时将这两位变为一位,这一位上填的数为\(-(a_i+a_{i+1})\)。很容易想到的一个\(O(n^3)\)的dp做法是区间dp,设\(f[......
  • NOIP2013-2023题解
    本文章主要是为了不想卷题的时候不是特别颓废而准备本文章是为了总结NOIP最近的题目(为了今年NOIP做准备),目前还没写完,尽量做的全面一些。2013积木大赛给定一个长度为\(n\)的序列\(h_i\),初始有一个全为\(0\)的序列,每次操作可以任意选择\(L,R\),使得\([L,R]\)这段区......
  • CF1545D-题解
    题目链接题目描述有\(n\)个人和\(k\)个间隔相同时间的时刻,每个人都向正方向做匀速直线运动。给出每个时刻(\(0\simk-1\))的所有人的坐标集合(无序),在这\(nk\)个数中有一个数是错误的,找出这个错误的数并将其改正。数据范围:\(5\len\le1000\),\(7\lek\le1000\)。加......