首页 > 其他分享 >2024.11.6 鲜花

2024.11.6 鲜花

时间:2024-11-06 21:33:21浏览次数:3  
标签:2024.11 前缀 鲜花 trance 复杂度 枚举 子集 考虑

アイデン貞貞メルトダウン
アリ!?ナシ!? ナシ!?アリ!?
ついてる ついてない あれどっち?どっち?Trance, trance, trance
蟻!?梨!? nAシ!?ァ理!?
自我 字が 崩壊!
インドア警備隊 紫外線さよなら
(バイバイ alright! 一級在宅 allday!)
やる気の“や”の字 どっかにいっちゃったんだ
ナイナイ 心技体 実家に帰ります)
ああ 未知なる世界と目があったよ
微笑んで 手招きしてるの
ねえ こっちの水はスウィーツパラダイス
おしゃれ メイク ヘアアレンジ
乙女の園で ダンスした
あれ わたし(Who!)
誰(Are!)
オレOleお?((It’s me!)
知らない 何 壊れそうな アイデン貞貞
産まれたばかり a sense of wonder
そのまま maybe 溶けてゆく 深層心理
目覚め
たまえ
眠れるアイツ
いくとこまで いってみようか ハッピーエンド?
アリ!?ナシ!? ナシ!?アリ!?
ついてる ついてない あれどっち?どっち?Trance, trance, trance
蟻!?梨!? nAシ!?ァ理!?
自我 字が 崩壊!
おさんぽ調査団 瀕死でおかえり
へイへイ fall down! 三流散策 weekend!)
やる気を出した 結果が大変だった
(累々 死屍die! ファイト一発)
ああ マジカルウルトラスーパーミラクル
抱きしめて 慰めてくれよ
ええ そんなの夢さ ドリームワンダーランド
地道 努力 コツコツ
正論マンが パンチした
やれ右(Uh!)
右(Hah!)
左右!(ワンツー!)
いらない 愛つよがりな アイデン貞貞
素直になりなさい catch on fire
わがまま baby 解けてゆく 固定観念
ふるい
たまえ
内なるケモノ
自分自身を知るための 決闘だ
白か黒かで決めた(オセロ!)
0か100しかないの?(極論!)
生きづらい俗世だね(娑婆ばい!)
神様 仏様 この私目にお導きを...
それでいいのか(YES! NO!) アイデンティティよ
目を覚ませ!

今天才知道这个词这么逆天,还是别放中文了。

sosdp,FMT,FWT 上

FWT 和一些难点的题放到下次写。

sosdp

首先考虑最基本的问题:

定义集合 \(U\subseteq R,X=\{S|S\subseteq U\}\),定义函数 \(f:X\to R,g(S)=\sum\limits_{T\subseteq S} f(S)\),对于所有的 \(S\in U\) 求 \(g(S)\),\(n=|U|\le22\)

首先暴力枚举 \(S,T\) 是 \(n^4\) 的,考虑优化。

  1. 子集枚举:

    考虑将集合抽象成二进制,求 \(S\) 的子集相当于枚举其所有掩码,有代码:

    for(int t=s;t;t=(t-1)&s)
    

    这里 \(t\) 是 \(s\) 的子集。解释就是 t-1 每次将 t 最后一个一置零,后面全置一,与上 \(s\) 可以去除掉多余部分,显然 \(t\) 降序遍历 \(s\) 掩码。

    暴力枚举 \(s\),复杂度是 \(3^n\) 的。

  2. 高维前缀和:

    我们发现子集枚举并没有很好的利用信息之间的可合并性,发现将二进制每位拆成一维,其相当是高维前缀和,有代码:

    for(int i=0;i<n;++i) for(int j=0;j<1<<n;++j) if(j>>i&1) f[j]+=f[j^1<<i];
    

    解释:考虑求二维,三维,四维前缀和时,有简单的做法是每次枚举一维做前缀和,其实代码就是在枚举第 \(i\) 维和当前状态 \(j\),在加上去。

    复杂度 \(n2^n\)

没错,这就是 sosdp,其实就是递推求前缀和。

会了前缀和还要会差分,容易想到将循环变向,加变减即可,考虑到每维的大小只有 \(2\),所以循环反不反向都无所谓啦。

高维后缀和、差分也类似,考虑其是把 \(1\) 加到零上,将 if(j>>i&1) 改成 if(!(j>>i&1)) 就好了。

先就此打住,做一个还算有点意思的板子:CF449D Jzzhu and Numbers

solution

考虑恰好都是 \(0\) 不好做,考虑容斥,求钦定有 \(x\) 个一的方案数。

考虑转而枚举 \(k\) 满足 \(k\) 是最后 \(\And\) 的结果一个子集,会发现其相当于是每个数的子集,求二维后缀和即可。

快速莫比乌斯变换(FMT)

注意和莫比乌斯变换区分。

板子:

给定两个集合上的函数 \(f,g\) 求 \(h(S)=\sum\limits_{I\circ J = S} f(I)*g(J)\),其中 \(\circ\) 可以是 \(\cup\) 和 \(\cap\)。

考虑先做并,先对 \(f,g\) 做前缀和,在计算 \(h'(S)=f(S)*g(S)\),然后对 \(h'\) 做前缀差分,根据定义,其就是 \(h\)。

虽然我并不会 FTT,但不影响题解让我发现,这个操作和 FTT 的 DFT 很像——同样是对一个函数作运算得到另一个函数,然后用运算完的操作进行按位求积,最后再进行反向操作将其变换为原函数。而整套流程下来,实现了卷积的效果,所以这个也叫 OR 卷积,在原函数和新函数间建立双射的操作,被称作“快速莫比乌斯变换 Fast Mobius Transform(FMT)”。

类似可以做 AND 卷积,用后缀操作代替前缀,可以解决交的问题。

复杂度是 \(n2^n\),但是考虑设 \(n\) 表示 \(S\) 的总方案数,在一般的二进制中就是原数的大小,复杂度是 \(n\log n\) 的——和 FFT 一样。

与 AND 和 OR 类似的,其实 XOR 的卷积也是可以做的,但是要用到 FWT,并且因为其结构更像 FFT,因此更难写。

P(没图了,谁想放给我推点呗~

标签:2024.11,前缀,鲜花,trance,复杂度,枚举,子集,考虑
From: https://www.cnblogs.com/xrlong/p/18531072

相关文章

  • 2024.11.6随笔
    前言半期考试第一天?停课!前一天晚上提前做好了这几天的计划,本来以为晚上要回班自习,结果不用,于是计划就奇妙的往前平移了!CSP后我也反思了自己近期的学习情况,无论是whk还是竞赛。只能说有目标但是缺乏决心和长远的目光,且自己的日常习惯做的还不够好,有的东西没有坚持好。然后就......
  • 2024.11.6训练记录
    今天主要是做的单个题。下次打模拟赛就是放假了。怕会有段时间没打手感下降/ll。csp-J2024Ddp。f[i][j]表示,第i轮结束后,最终颜色是j的结束位置。f[i][j]=-1:状态不能达到。f[i][j]=0:可以在多个人处结束。(即有大于等于2个序列中的j颜色可以被转到)f[i][j]=l:只有在第l......
  • GJ Round (2024.11) Round 22~?
    前言:点此返回GJRound目录Round22(11.4)唯一一次快速补完了题AAT_arc077_a[ABC066C]pushpush不懂这原题标号咋这么奇怪给你一个序列\(a_1\dotsa_n\),按照如下规则构造新序列:将\(a_i\)插入序列末尾将整个序列反转模拟/打表找规律:当\(n\)为奇数时......
  • [2024.11.06]NOIP 模拟赛
    不会tarjan不会广义串并联图……赛时T1看上去很可做。看到中位数首先想到二分。在二分的背景下,问题转化为求当前最多能使多少个元素大于等于某个定值。我们不妨先让所有的元素都选择\(a\)值,然后相当于要选择一段连续的\(b\)替换一些\(a\),要求最后总和最大。所以可以新设......
  • 2024.11.5 鲜花
    放点屁话大家多交hack。有的人觉得没意义,这也无可厚非,有的人怕被骂,我一直认为这是多余的,但竟然真的有人骂?这是无法理解的,所以发文声讨一下。叠甲:本文仅代表个人观点,可能有过激言论,不针对任何人。不是你们骂交hack的人是什么心态啊。你站在道德制高点上,谴责人家交hack,你首......
  • 2024.11.5 闲话
    别人的闲话都推图or歌,我的鲜花啥也没有。我也没啥可推的啊,求图or歌高维前缀和常见的柿子是\(s_{i,j}=s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}+a_{i,j}\)。但是还可以一维一维求。点此查看代码rep(i,1,n,1)rep(j,1,m,1)a[i][j]+=a[i-1][j];rep(i,1,n,1)rep(j,1,m,1)a[i]......
  • 2024.11.05 刷题训练
    2024.11.05刷题训练P7054NWRRC2015Graph构造题,把拓扑序中的队列换成小根堆是最小字典序,此时设置一个大根堆,用于处理连边问题。设\(lst\)是上一个拓扑序中的节点。小根堆堆顶大于大根堆,当前位置最优解,不耗费连边数量。小根堆堆顶小于大根堆,若\(k\)不为\(0\)加入到大......
  • 2024.11 做题笔记
    2024.11做题笔记其实是CSP后到NOIP前的部分10.28怎么KTSC这么困难啊……B.P11237「KTSC2024R1」警察与小偷把警察、小偷所在路径拎出来,此时警察一定往小偷所在方向走,而小偷可以在警察到路径上的某点之前从这点走向路径外,想选尽量长的路径,让警察走的尽量多但可能......
  • 2024.11.4~2024.11.9
    2024.11.4今天早上没有醒来,一抬表发现7:03了直接破防(悲上午模拟赛T1直接一个没思路,想了1h都没想出来,打了10分遗憾离场,T2直接就是死磕1h也没有丝毫思路,然后最后10分非常惨下午都在调T1,直到4点才调完,晚上情绪状态比较不稳定,但是调整的很好,还是坚持做了5到题,比较可以csp-s160分完......
  • 2024.11.04
    今天心情不好,不写模拟赛了模拟赛的内容在学校写完得了,回家写小作文睡觉模拟赛没怎么好好打。第二次打构造题,这种题和其他的是真的不一样。看来我不仅要恶补各种算法,还要锻炼一下我的思维。猜猜今天有没有题目小链接T1【串】题目大意:给出n,k(1<=n,k<=1e5),要求构造出长度为n......