JZYshuraK

分类

未归档(392)

/ 注册

全部文章（共392篇）

[bzoj4066/2683]简单题_KD-Tree

简单题 bzoj-4066 题目大意：n*n的棋盘，开始为均为0，支持：单点加权值，查询矩阵权值和，强制在线。注释：$1\le n\le 5\cdot 10^5$，$1\le m \le 2\cdot 10^5$。想法：KD-Tree裸题。所谓KD-Tree，就是一个看起来贼牛逼实...

2018-07-28

0 347

[bzoj1926][Sdoi2010]粟粟的书架_二分_主席树

粟粟的书架 bzoj-1926 Sdoi-2010 题目大意：题目链接注释：略想法：分成两个题前面的我们可以二分，直接二分出来检验即可。对于R=1的，相当一个数列，我们在上面建立主席树。然后查询时，我们通过优先遍历右子树的方式使得拿的书最少。最后，附上丑陋的代码... ...

2018-07-28

0 305

[bzoj3872][Poi2014]Ant colony_树形dp

Ant colony bzoj-3872 Poi-2014 题目大意：说不明白.....题目链接注释：略。想法：两个思路都行。反正我们就是要求出每个叶子节点到根节点的每个路径权值积。可以将边做为代理根。或者将边断掉。最后，附上丑陋的代码... ... #includ...

2018-07-28

0 394

[bzoj3524/2223][Poi2014]Couriers_主席树

Couriers bzoj-3524 Poi-2014 题目大意：给定n个数的序列，询问区间内是否存在一个在区间内至少出现了（区间长度>>1）次的数。如果有，输出该数，反之输出0。注释：$1\le n,m\le 5\cdot 10^5$。想法：主席树裸题。主流做法就是弄...

2018-07-28

0 306

[bzoj1812][IOI2006]riv_多叉树转二叉树_树形dp

riv bzoj-1812 IOI-2006 题目大意：给定一棵n个点树，要求在上面建立k个收集站。点有点权，边有边权，整棵树的代价是每个点的点权乘以它和它的最近的祖先收集站的距离积的和。注释：$1\le n \le 100$，$1\le k \le 50$。想法：显然，这是一道树形d...

2018-07-28

0 369

[bzoj1879][Sdoi2009]Bill的挑战_动态规划_状压dp

Bill的挑战 bzoj-1879 Sdoi-2009 题目大意：注释：$1\le t \le 5$，$1\le m \le 15$，$1\le length \le 50$。想法：又是一个看数据范围想做法的题，我们想到状压dp。看了题解... ...网上给的状态是f[le...

2018-07-27

0 256

[bzoj3529][Sdoi2014]数表_树状数组_莫比乌斯反演

数表 bzoj-3529 Sdoi-2014 题目大意：n*m的数表，第i行第j列的数是同时整除i和j的所有自然数之和。给定a，求数表中所有不超过a的和。注释：$1\le n,m \le 10^5$。想法：我们先不考虑那个a的限制：我们设f(i)表示整除i的自然数之和。 $...

2018-07-27

0 329

[bzoj3717][PA2014]Pakowanie_动态规划_状压dp

Pakowanie bzoj-3717 PA-2014 题目大意：给你n个物品m个包，物品有体积包有容量，问装下这些物品最少用几个包。注释：$1\le n\le 24$，$1\le m\le 100$ 想法：以为是什么超级牛逼的背包dp，结果就是状压dp 状态：f[s]表示装s状态的物...

2018-07-26

0 384

[bzoj2259][Oibh]新型计算机_Dijkstra

新型计算机 bzoj-2259 Oibh 题目大意：给定一个n个数的数列，第i个数为a[i]，更改第i个数至x的代价为|x-a[i]|。求最小代价，使得：读入一个数s1后，向后连着读s1个数，然后如s2，再向后读s2个数。保证最后恰好读到第n个数。注释：$1\le n\le 10^6$ ...

2018-07-26

0 425

[bzoj1660][Usaco2006 Nov]Bad Hair Day_单调栈

Bad Hair Day bzoj-1660 Usaco-2006 Nov 题目大意：n头牛站成一列，每头牛向后看。f[i]表示第i头牛到第n头牛之间有多少牛，使得这些牛都比i矮，且中间没有比i高的牛阻隔。求$\sum\limits_{i=1}nf[i]$。注释：$1\le n\le 8\cd...

2018-07-26

0 319