ComplexPug

未归档

做题记录(1)

/ 注册

全部文章 / 未归档（共273篇）

UVA - 12298 Super Poker II NTT

UVA - 12298 Super Poker II NTT 链接 Vjudge 思路暴力开个桶，然后统计，不过会T，用ntt或者fft，ntt用个大模数就行了，百度搜索"NTT大模数"。错误我也不知道，改着改着自己就A了思路 #include <b...

ntt

2019-04-18

0 539

CF 528D. Fuzzy Search NTT

CF 528D. Fuzzy Search NTT 题目大意给出文本串S和模式串T和k，S,T为DNA序列(只含ATGC)。对于S中的每个位置\(i\)，只要中[i-k,i+k]有一个位置匹配了字符\(i\)，那么就认为\(i\)可以匹配。求S中有多少位置匹配了T。思路一共有四个字母，...

ntt

2019-04-14

0 685

bzoj 3513: [MUTC2013]idiots FFT

bzoj 3513: [MUTC2013]idiots FFT 链接 bzoj 思路参考了学姐TRTTG的题解统计合法方案,最后除以总方案。合法方案要不好统计，统计不合法方案。 \(a+b<=c\)的个数 f[i]是i出现的个数 g[i]表示a+b=i的个数，a<=b 这个...

fft

2019-04-14

0 640

loj#2020 「AHOI / HNOI2017」礼物 ntt

loj#2020 「AHOI / HNOI2017」礼物链接 bzoj没\(letex\),差评 loj luogu 思路最小化\(\sum\limits_1^n(a_i-b_i)^2\) 设改变量为k \(\sum\limits_1^n(a_i-(b_i+k))^2\) \(\sum\...

ntt

2019-04-13

0 567

bzoj3527: [Zjoi2014]力 fft

bzoj3527: [Zjoi2014]力 fft 链接 bzoj 思路但是我们求得是 \(\sum\limits _{i<j} \frac{q_i}{(i-j)^2}-\sum_{i>j}\frac{q_i}{(i-j)^2}\) \(\sum\limits _{i<...

fft

2019-04-13

0 539

[十二省联考2019]异或粽子 01trie

[十二省联考2019]异或粽子 01trie 链接 luogu 思路首先求前k大的(xo[i]^xo[j])（i<j）。考场上只想到01trie,不怎么会写可持久，就写了n个01trie，和直接sort一样、、咳咳，官方题解是。一个堆维护i为终点，可以取得位置为\([L,R]\...

可持久化贪心 01trie

2019-04-13

0 560

bzoj2194 快速傅立叶之二 ntt

bzoj2194 快速傅立叶之二链接 bzoj 思路对我这种和式不强的人，直接转二维看。发现对\(C_k\)贡献的数对(i,j),都是右斜对角线。既然贡献是对角线，我们可以利用对角线的性质了。不过右斜角线不太好，我们把每一行都reverse一下，换成左斜角线。对角线上\(i+j\...

ntt

2019-04-12

0 564

[十二省联考2019]春节十二响贪心，启发式合并

[十二省联考2019]春节十二响链接 loj luogu 思路考试的75分的\(O(n^2)\)谢瓜了，菜的一批。直接堆启发式合并。反正就是随便写就过的那种。好菜啊代码 // luogu-judger-enable-o2 #include <bits/stdc++.h&g...

贪心启发式合并

2019-04-12

0 533

luoguP1919 A*B Problem升级版 ntt

luoguP1919 A*B Problem升级版链接 luogu 思路 ntt模板题代码 #include <bits/stdc++.h> #define ll long long using namespace std; const int N=3e5+7,mod=9...

ntt

2019-04-12

0 583

luogu[愚人节题目3]现代妖怪殖民地 NTT

U34272 [愚人节题目3]现代妖怪殖民地 fft 题目链接 https://www.luogu.org/problemnew/show/U34272 思路虽然是个py题。 ntt(或者fft)模板题,可能稍不注意就会T 代码 #include <bits/stdc++.h&g...

ntt

2019-04-12

0 562