JZYshuraK

未归档

/ 注册

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

[bzoj2287][poj Challenge]消失之物_背包dp_容斥原理

消失之物 bzoj-2287 Poj Challenge 题目大意：给定$n$个物品，第$i$个物品的权值为$W_i$。记$Count(x,i)$为第$i$个物品不允许使用的情况下拿到重量为$x$的方案数。注释：$1\le n,val_i\le 2\cdot 10^3$。想法：只需要用...

2018-12-10

0 332

[bzoj3252]攻略_dfs序_线段树_贪心

攻略 bzoj-3252 题目大意：给定一棵n个节点的有根树，点有点权。让你选出至多k个节点，使得他们到根的链的并最大。注释：$1\le n\le 2\cdot 10^5$，$1\le val_i\le 2^{31}-1$。想法：这题模拟赛T2，正解可并堆，我用的$dfs$序加线段树。...

2018-12-10

0 385

[bzoj4712]洪水_动态dp

洪水 bzoj-4712 题目大意：给定一棵$n$个节点的有根树。每次询问以一棵节点为根的子树内，选取一些节点使得这个被询问的节点包含的叶子节点都有一个父亲被选中，求最小权值。支持单点修改。注释：$1\le n\le 2\cdot 10^5$。保证任意时刻所有节点的权值为正整数。想法：...

2018-11-26

0 357

[bzoj4827][Hnoi2017]礼物_FFT

礼物 bzoj-4827 Hnoi-2017 题目大意：给定两个长度为$n$的手环，第一个手环上的$n$个权值为$x_i$，第二个为$y_i$。现在我可以同时将所有的$x_i$同时加上自然数$c$。我也可以将第一个手环任意旋转。旋转后每一个$x$对应一个$y$，那么代价为$\sum\limits_...

2018-11-24

0 275

[bzoj3527][Zjoi2014]力_FFT

力 bzoj-3527 Zjoi-2014 题目大意：给定长度为$n$的$q$序列，定义$F_i=\sum\limits_{i<j}\frac{q_iq_j}{(i-j)^2}-\sum\limits_{i>j}\frac{q_iq_j}{(i-j)^2}$。求所有的$E_i=\fra...

2018-11-24

0 305

[bzoj2194]快速傅立叶之二_FFT

快速傅立叶之二 bzoj-2194 题目大意：给定两个长度为$n$的序列$a$和$b$。求$c$序列，其中：$c_i=\sum\limits_{j=i}^{n-1} a_j\times b_{j-i}$。注释：$1\le n\le 10^5$，$0\le a_i,b_i\le 100$。 ...

2018-11-24

0 399

[bzoj2179]FFT快速傅立叶_FFT

FFT快速傅立叶 bzoj-2179 题目大意：给出两个n位10进制整数x和y，你需要计算x*y。注释：$1\le n\le 6\times 10^4$。想法： $FFT$入门题。 $FFT$实现的就是多项式乘法，进而我们可以通过它优化卷积。但是有一点：$FFT$优化的卷积是所...

2018-11-24

0 354

[bzoj3196][Tyvj1730]二逼平衡树_树套树_位置线段树套非旋转Treap/树状数组套主席树/权值线段树套位置线段树

二逼平衡树 bzoj-3196 Tyvj-1730 题目大意：请写出一个维护序列的数据结构支持：查询给定权值排名；查询区间k小值；单点修改；查询区间内定值前驱；查询区间内定值后继。注释：$1\le n,m\le 5\times 10^4$。想法：在这里给予三种题解： 1)首先，最...

2018-11-19

0 353

[bzoj3436]小K的农场_差分约束

小K的农场 bzoj-3436 题目大意：给定n个点，每个节点有一个未知权值。现在有m个限制条件，形如：点i比点j至少大c，点i比点j至多大c或点i和点j相等。问是否可以通过给所有点赋值满足所有限制条件。注释：$1\le n,m\le 10^4$。想法：差分约束裸题。我们将限制条件...

2018-11-01

0 335

[bzoj3910]火车_并查集_倍增LCA

火车 bzoj-3910 题目大意：给定一棵n个节点的树，你需要顺次经过m个互不相同的节点，如果一个节点在之前的路径上被经过过，它不必再被特意经过。问走过的路径长度。注释：$1\le n\le 5\cdot 10^5$，$1\le m\le 4\cdot 10^5$。想法：考场上切...

2018-11-01

0 486