首页 > 其他分享 >[CF383E] Vowels 题解

[CF383E] Vowels 题解

时间:2024-02-04 17:46:34浏览次数:27  
标签:int 题解 Vowels 单词 元音 CF383E

[CF383E] Vowels 题解

思路

要求的这个东西一看就没什么性质,考虑枚举所有元音子集。

如果我们能够求出 \(f_s\) 表示 \(s\) 集合作为元音时有多少个单词至少包含一个元音。

难求,正难则反,考虑 \(f_s\) 表示 \(s\) 集合作为元音时有多少个单词全都由非元音字母组成,由于对称性,我们只需要求出 \(s\) 集合作为非元音时有多少个单词全都由非元音字母组成,这个就是权值为 01 的子集和,SOSDP 即可。

时间复杂度:\(O(2^{\Sigma}\Sigma)\)。

// Problem: Vowels
// Author: Moyou
// Copyright (c) 2024 Moyou All rights reserved.
// Date: 2024-02-04 16:29:01

#include <iostream>
#define int long long
using namespace std;
const int N = 1e4 + 10, M = 24;

int n, f[(1 << M)];
string s;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1, x; i <= n; i ++) {
        cin >> s, x = 0;
        for(auto c : s) x |= (1 << (c - 'a'));
        f[x] ++;
    }
    for(int j = 0; j < 24; j ++)
        for(int i = 1; i < (1 << 24); i ++)
            if(i >> j & 1) f[i] += f[i ^ (1 << j)];
    int ans = 0;
    for(int i = 0; i < (1 << 24); i ++)
        ans ^= (n - f[i]) * (n - f[i]);
    cout << ans << '\n';

    return 0;
}

标签:int,题解,Vowels,单词,元音,CF383E
From: https://www.cnblogs.com/MoyouSayuki/p/18006671

相关文章

  • Luogu「Daily OI Round 3」Simple 题解
    #include<iostream>#include<cstdio>#include<queue>#include<algorithm>#include<cstring>#include<string>#include<string.h>#include<vector>#defineintlonglong#definerep(a,b,c)for(autoa=b;a......
  • [ARC114D] Moving Pieces on Line 题解
    题目链接点击打开链接题目解法有点牛的题,前面的转化感觉很妙首先一个显然的性质是:一个棋子不可能走回头路,不然前面的路就白走了下面是最妙的一步:我们令\(st_i\)为\(i-1\toi\)和\(i\toi+1\)的颜色是否相同,那么问题可以转化成:选择\(\{p_i\}\),一开始所有点颜色为\(0\)......
  • ABC339 F Product Equality 题解
    QuestionABC339FProductEquality给出一个序列\(A_1,A_2,\cdots,A_N\)计算数对\((i,j,k)\)满足\(A_i\timesA_j=A_k\)的个数\(A_i\le10^{1000}\)Solution思考\(A_i\)比较小的情况如果\(A_i\le1e9\)的,暴力枚举\(i,j\)然后用\(map\)查找\(A_i\timesA_j......
  • gitlab 502问题解决
    问题现象: Whoops,GitLabistakingtoomuchtimetorespond.Tryrefreshingthepage,orgoingbackandattemptingtheactionagain.PleasecontactyourGitLabadministratorifthisproblempersists. 问题定位分析:一、查看系统资源使用情况磁盘满了g......
  • Linux服务器升级GLIBC失败导致shell不可用的问题解决经历
    转自https://blog.csdn.net/u010549608/article/details/126281354?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522170696599716800182728626%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=170696599716800182728626&biz_i......
  • ABC339_g Smaller Sum 题解
    题目链接:Atcoder或者洛谷比价朴素的题,首先有暴力的想法就是树套树或者分块。这两种就不再赘述,这里来正式提提主xi树(应该不能打出来这玩意)的本质而不再停留在板题找第\(k\)大上。对于可差性问题和传统问题不同,我们对于可差性问题往往都有更好的优化方案。例如对于树类问......
  • AcWing 5466. 随机排列 题解
    讲解都在代码里了#include<bits/stdc++.h>//可以发现不管n怎么取,3n和7n+1都是一个奇数一个偶数//那么那么我们用最多n-1次交换将数组复原看一看用了奇数次还是偶数次就可以看出来了//这种交换方式常见于基础课内容,是两个数组互为双向usingnamespacestd;constintN=1e......
  • ABC339 题解
    AK了。A-TLD给出一个字符串\(s\),输出最后一个.后面的内容。\(|s|\le100\)。\(\text{2sec/1024MB}\)。按照题意模拟即可,时空复杂度均为\(\mathcal{O}(|s|)\)。ACCodeB-Langton'sTakahashi给出\(H\timesW\)的网格。初始你在\((1,1)\),方向......
  • ABC339 题解(A~G)
    A从后向前找到第一个.就行了。B按照题意模拟,设当前位置\(x,y\)移动方向\(dx,dy\)。那么下一步为\((x+dx,y+dy)\)设新的移动方向为\(dx',dy'\)如果顺时针旋转,则有\(dy'\gets-dx,dx'\getsdy\);如果逆时针,则有\(dx'\gets-dy,dy'\getsdx\)。C鉴定为除A以外......
  • P7119 Mivik 的游戏 题解
    先从一个例子开始假如硬币开始是这样的:HHHHHTHH然后就可以将这个反面硬币\(T\)左边的硬币全都反过来,共需\(5\)步。然后就变成了:TTTTTTHH最后再将最右边两个反过来就可以了,共需\(5+2=7\)步。如果\(p\)为这个反面的硬币位置的话,那么答案\(as=2p-1\)。推导......