ComplexPug

分类

做题记录(1) 未归档(274)

/ 注册

全部文章（共277篇）

CF685B Kay and Snowflake 贪心

CF685B Kay and Snowflake 链接 CF 题目大意给你一颗树，询问子树的重心思路贪心？重心肯定是向上走的，所以直接向上跳就好了。不优秀的时候就不要跳了，因为以后也不能更新了。复杂度O（n）（没大仔细想过）代码 #include <bits/s...

贪心

2019-04-28

0 531

[FJOI2018]领导集团问题 mulitset合并

P4577 [FJOI2018]领导集团问题链接 luogu bzoj 他是个重题 bzoj4919: [Lydsy1706月赛]大根堆代码改改就过了思路求树上的lis，要好好读题目的！！！类似于一条链子的思路，把大于w[u]的改掉代码 #include <bits/s...

set合并

2019-04-26

0 585

hiho#1513 : 小Hi的烦恼五维偏序

hiho#1513 : 小Hi的烦恼五维偏序链接 hiho 思路高维偏序用bitset,复杂度\((\frac{n^2}{32})\) 代码 #include <bits/stdc++.h> using namespace std; const int N=3e4+7;...

高维偏序

2019-04-25

0 647

CF Round #551 (Div. 2) D

CF Round #551 (Div. 2) D 链接 https://codeforces.com/contest/1153/problem/D 思路不考虑赋值和贪心，考虑排名。设\(dp_i\)是子树i中的i是第dp_i大的(相同大小放在后面)。 \(opt=1,dp_u=max(d...

DP

2019-04-19

0 514

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