ComplexPug

未归档

做题记录(1)

/ 注册

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

FFT 快速傅里叶变换学习笔记

FFT 快速傅里叶变换前言 lmc,ikka,attack等众多大佬都没教会的我终于要自己填坑了。又是机房里最后一个学fft的人用处多项式乘法卷积 \(g(x)=a_0+a_1x+a_2x^2\) \(f(x)=b_0+b_1x+b_2x^2\) 他们的乘积c(x)就是 \(c...

fft

2019-04-11

0 588

十二省联考爆0记

十二省联考爆0记 day0 早上早来了还差点走迷糊了。先去山师大报道，感觉大学没啥特别的。就是地方大点，楼多点，人多一点。然后老师们领着去小吃街的隔壁街吃饭(没错，领叉屁了)。顺便去山师大，山师附中，山师附小转了转一天就这样过去了。 day1 山师大饭堂居然还用粮票、、、然后去...

游记

2019-04-07

0 532

# NOI.AC省选赛第五场T1 子集，与&最大值

NOI.AC省选赛第五场T1 A. Mas的童年题目链接 http://noi.ac/problem/309 思路 0x00 \(n^2\)的暴力挺简单的。 ans=max(ans,xor[j-1]+xor[j-1]^xor[i]); 01trie树求最大异或和相信大家都会。不会...

2019-03-30

0 477

luoguP1850 换教室

luoguP1850 换教室链接 https://www.luogu.org/problemnew/show/P1850 思路状态很显然就是f[n][k][0/1] 前i次，用了k次机会,当前是在哪个教室转移就很、、了。每次转移i的时候，一定是从i的两个可能的教室来的。那就有四种可...

DP 期望

2019-03-30

0 523

bzoj2091: [Poi2010]The Minima Game DP

2091: [Poi2010]The Minima Game DP 链接 https://www.lydsy.com/JudgeOnline/problem.php?id=2091 思路这类问题好迷呀。我们先从小到大sort 先手一定是个后缀。因为你不能留下大数让对手选呀。然后后手就...

DP

2019-03-29

0 723

luoguP1281 书的复制 DP，贪心

luoguP1281 书的复制链接 https://www.luogu.org/problemnew/show/P1281 思路简单dp，输出方案。很明显dp记录路径对不对？恭喜你死了。求出dp值，倒叙贪心取最长错误好久之前咕咕的题目下载数据才看出来不能记录路径代码 ...

DP 贪心

2019-03-29

0 514

loj6068. 「2017 山东一轮集训 Day4」棋盘二分图，网络流

loj6068. 「2017 山东一轮集训 Day4」棋盘链接 https://loj.ac/problem/6068 思路上来没头绪，后来套算法，套了个网络流经典二分图左边横，右边列先重新算一下行和列，就是他们x相通的的算一个然后就去掉了障碍的作用然后每一行贡献是递增的(0,...

网络流二分图

2019-03-29

0 576

bzoj1133: [POI2009]Kon

bzoj1133: [POI2009]Kon 链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1133 思路 f[i][k]表示前i个，选了k个，其中必选i的最大值 f[i][k]=f[j][k-1]+贡献这个贡献就是j到i之间的边界...

DP

2019-03-28

0 552

luogu3426 [POI2005]SZA-Template 后缀树

链接 bzoj不能auto https://www.luogu.org/problemnew/show/P3426 思路这个要求的串一定是S的前缀和S的后缀。转化一下建立出来fail树（fail[i]->i的树）答案就在0和n之间的链条上，且答案在分界点上(上面全不可以，下面全可...

fail树

2019-03-28

0 666

loj#2483. 「CEOI2017」Building Bridges 斜率优化 cdq分治

loj#2483. 「CEOI2017」Building Bridges 链接 https://loj.ac/problem/2483 思路 \[f[i]=f[j]+(h[i]-h[j])^2+(sum[i-1]-sum[j])\] \[f[i]=f[j]+h[i]^2+h[j]^2-2*h...

斜率优化 cdq

2019-03-22

0 506