首页 > 其他分享 >YC262A [ 20240321 CQYC省选模拟赛 T1 ] 多边形(polygon)

YC262A [ 20240321 CQYC省选模拟赛 T1 ] 多边形(polygon)

时间:2024-03-25 14:34:26浏览次数:25  
标签:状态 le polygon 省选 T1 int include 20240321 define

题意

有一个由 \(0/1\) 组成的字符串 \(S\)。

给你 \(m\) 次操作。

假如 \(S_{u} = 1\) 且 \(S_{v} = 0\),则交换 \(S_{u}, S_{v}\)。

假如对于所有的 \(S\),使得最终字符串 \(S'\) 的所有 \(1\) 相邻。

请输出 \(1\) 的个数为 \([1, n]\) 的 \(S\) 的方案数。

答案对 \(2\) 取模。

\(n \le 35, m \le 1000\)

Sol

有一个很明显的 \(2 ^ n \times m\) 做法。

枚举 \(S\) 的最初状态,暴力操作 \(m\) 次。

套路地,考虑用 \(0, 1, 2\) 来表示当前的状态。

分类讨论。

  • 若 \(S_u\) 与 \(S_v\) 都为 \(2\)。

注意到对于 \(S_u \neq S_v\) 时。

\(0\) 和 \(1\) 与 \(1\) 和 \(0\) 在操作过后都会变成 \(0\) 和 \(1\) 这个状态。

也就是说,当前的两种情况对于答案的贡献为 \(0\)。

直接不考虑即可。

只需要考虑 \(S_u = S_v = 0\) 和 \(S_u = S_v = 1\) 即可。

  • 若 \(S_u\) 与 \(S_v\) 有一个为 \(2\)。

手摸一下可以发现,只要带 \(1\) 就会变成 \(2\) 和 \(1\)。

只要带 \(0\) 就会变成 \(0\) 和 \(2\)。

  • 若 \(S_u\) 与 \(S_v\) 都不为 \(2\)。

两个都确定了,直接转移即可。

冷静一下。

发现状态变多的同时会使 \(2\) 的个数减 \(2\),剩下所有情况都不会使状态变多。

状态数的级别为 \(O(2 ^ {n / 2})\)。

做完了。

最后统计一个状态是否合法。

总复杂度:\(O(2 ^ {n / 2} m + 2 ^ {n / 2} n ^ 2)\)。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <bitset>
#include <vector>
#define int long long
#define il inline
#define pii pair <int, int>
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
il int read() {
    int p = 0, flg = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') flg = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        p = p * 10 + c - '0';
        c = getchar();
    }
    return p * flg;
}
void write(int x) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if (x > 9) {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}
bool _stmer;

#define fi first
#define se second

const int N = 36, M = 1005;

array <int, N> ans;
array <pii, M> s;

il void dfs(int n, int m, int isl1, int isl2, int x, int val) {
    if (x > m) {
        int tp0 = 0;
        for (int i = 1; i <= n; i++)
            if (isl1 & (1ll << (i - 1))) tp0++;
        for (int i = 1; i <= n; i++) {
            int tp1 = 0;
            for (int j = i; j <= n; j++) {
                if (!(isl1 & (1ll << (j - 1))) && !(isl2 & (1ll << (j - 1)))) break;
                tp1 += (bool)(isl1 & (1ll << (j - 1)));
                if (tp0 == tp1) ans[j - i + 1]++;
            }
        }
        return;
    }
    int u = 1ll << (s[x].fi - 1), v = 1ll << (s[x].se - 1);
    if ((isl2 & u) && (isl2 & v)) {
        dfs(n, m, isl1, isl2 ^ u ^ v, x + 1, val - 2);
        dfs(n, m, isl1 ^ u ^ v, isl2 ^ u ^ v, x + 1, val - 2);
    }
    else if (!(isl2 & u) && !(isl2 & v)) {
        if ((isl1 & u) && !(isl1 & v))
            isl1 ^= u, isl1 ^= v;
        dfs(n, m, isl1, isl2, x + 1, val);
    }
    else {
        if ((isl1 & u) || (isl1 & v)) {
            if (isl1 & u) isl1 ^= u ^ v, isl2 ^= u ^ v;
            dfs(n, m, isl1, isl2, x + 1, val);
        }
        else {
            if (isl2 & u) isl2 ^= u ^ v;
            dfs(n, m, isl1, isl2, x + 1, val);
        }
    }
}

bool _edmer;
signed main() {
    cerr << (&_stmer - &_edmer) / 1024.0 / 1024.0 << "MB\n";
    int n = read(), m = read();
    for (int i = 1; i <= m; i++)
        s[i].fi = read(), s[i].se = read();
    dfs(n, m, 0, (1ll << n) - 1, 1, n);
    for (int i = 1; i <= n; i++)
        write(ans[i] % 2), putchar(32);
    puts("");
    cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
    return 0;
}

标签:状态,le,polygon,省选,T1,int,include,20240321,define
From: https://www.cnblogs.com/cxqghzj/p/18094325

相关文章

  • 联合省选2024游记
    联合省选2024游记因为这是省选后114514三周后,为了庆祝我的笔记本电脑到了而写的,所以有很多东西都记不清了(因为在赶稿,总之先写到这,后面如果想起什么再补day-1下午五点放学,回家!顺便把机房前几天中午吃乡村基时外卖的两个大盒子给薅走了,给家里的两只猫猫\(CQ\)就是好,考省选也......
  • IT15527: IN SPECIFIC TIMING CONDITIONS WITH MULTIPLE DB2READLOG API CALLERS(CDC,
    IT15527:INSPECIFICTIMINGCONDITIONSWITHMULTIPLEDB2READLOGAPICALLERS(CDC,ETC),"NOROOMFORRETRIEVEDLOG"occursindb2diag.loghttps://www.ibm.com/mysupport/s/defect/aCI0z000000TOfW/dt010963?language=en_USDescription 1.  Proble......
  • 省选2024
    省选2024day1先看T1,哇,一个绝对值式子,拆绝对值然后分讨即可,猛猛冲!过了一个小时写出来就赢麻了,猛猛冲!过了一个小时小样例过了,大样例调不出来了,先看看其他题,好,正解不会,暴力好写,继续猛猛冲!过了一个小时猛猛冲!猛猛冲!猛猛冲!最后30分钟冲不动了,去写T2暴力了。写了一会......
  • LeetCodeHot100 栈 155. 最小栈 394. 字符串解码
    155.最小栈https://leetcode.cn/problems/min-stack/description/?envType=study-plan-v2&envId=top-100-likedclassMinStack{Deque<Integer>deque;PriorityQueue<Integer>priorityQueue;publicMinStack(){de......
  • 力扣HOT100 - 49. 字母异位词分组
    解题思路:排序注意:返回时不能用List,因为List是抽象类,return的必须是List的具体实现,如ArrayListclassSolution{publicList<List<String>>groupAnagrams(String[]strs){Map<String,List<String>>map=newHashMap<>();for(Stringstr......
  • 【STM32+HAL库】---- 驱动DHT11温湿度传感器
    硬件开发板:STM32F407VET6软件平台:cubemax+keil+VScode1DHT11工作原理1.1简介DHT11数字温湿度传感器是一款含有已校准数字信号输出的温湿度复合传感器。它应用专用的数字模块采集技术和温湿度传感技术,确保产品具有极高的可靠性与卓越的长期稳定性。传感器包括一个电阻式感湿......
  • LeetCodeHot100 二分查找 35. 搜索插入位置 74. 搜索二维矩阵 34. 在排序数组中查
    35.搜索插入位置https://leetcode.cn/problems/search-insert-position/description/?envType=study-plan-v2&envId=top-100-likedpublicintsearchInsert(int[]nums,inttarget){intleft=0;intright=nums.length-1;while(left<......
  • 2024 省选游记
    前言本来真的太烂了不想写,后来想想还有一年呢,算是留个教训吧。Day-1有位高三学长来祝福,送了一盒巧克力。算了一下参加省选的一人和教练一块还多两块。但是有不要脸的学长借着填综评和送行的名义在机房吃饭&大喊大叫,后来被教练赶走了,还抢走了两块巧克力。但是教练不要巧克......
  • LY1169 [ 20230328 CQYC省选模拟赛 T1 ] 传奇特级超空间
    题意设\(f_{n,m}\)表示\(m\)维空间能被\(n\)个\(m-1\)维空间划分的最大区域数。求\(\sum_{i=0}^mf_{n,i}\)\(n,m\le10^{18},p\le2\times10^7\)Sol注意到:\(f_{n,m}=f_{n-1,m-1}+f_{n-1,m}\)。不难想到\(f\)应该是组合数的前缀......
  • 【力扣hot100】49. 字母异位词分组
    题目给你一个字符串数组,请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的所有字母得到的一个新单词。示例1:输入:strs=[“eat”,“tea”,“tan”,“ate”,“nat”,“bat”]输出:[[“bat”],[“nat”,“tan”],[......