ComplexPug

分类

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

/ 注册

全部文章（共277篇）

hdu 3698 UVA1490 Let the light guide us 线段树优化DP

题目链接 and 题目大意 hdu3698 但是 hdu的数据比较弱，所以在这luogu提交吧UVA1490 Let the light guide us 有一个\(n*m\)的平原，要求每行选一个点，选\(n\)个点建造塔楼。平原上每个点都有他自己的花费时间和魔法值。为了正确控制塔楼，我们...

线段树 DP

2018-10-12

1 517

#10078. 「一本通 3.2 练习 4」新年好

题目链接 loj 思路亲戚很少，可以每个点都算一遍单源最短路然后dfs 错误原因算错复杂度 #include <iostream> #include <cstring> #include <queue> #include <cstdio&g...

2018-10-10

0 547

#10178. 「一本通 5.5 例 4」旅行问题

题目 loj链接思路 ***写，考试最后5min找到bug，考玩10minAC，成功GG 这题没啥算法(感觉跟dp有点关系?) 他们说正解是单调队列，鬼知道咋用，反正我是O(n) 题目数据最大好像是1e5，大家也可以写个O(nlogn)的水一水拉就是预处理个 f1 ,f2，代码里的...

2018-10-10

0 629

luoguP2572 [SCOI2010]序列操作

题目&&链接反正数据都是一样的，luogu比较友好 luogu bzoj lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作： 0 a b 把[a, b]区间内的所有数全变成0 1 a b 把[a,...

线段树

2018-10-10

1 468

BZOJ 1044: [HAOI2008]木棍分割 DP 前缀和优化

题目链接咳咳咳，第一次没大看题解做DP 以前的我应该是这样的哇咔咔，这tm咋做，不管了，先看个题解，再写代码终于看懂了，卧槽咋写啊，算了还是抄吧第一问类似于noip的那个跳房子，随便做这里重点讲第二问首先，不会做，那就先写暴力 dp当然得写dp暴力了 \(f[k][i]\...

DP 优化

2018-10-09

1 579

luogu P2184 贪婪大陆

乍一不咋会 ╭(╯3╰)╮ 把地雷L到R看成一条线段要求的就是区间内有多少条线段经过很明显是要用[1,R]内的起点个数-[1,L-1]的终点个数然后这起点和终点个数可以用简单的差分线段树来维护一下其实树状数组更适合一些 #include <iostream> #in...

线段树

2018-10-09

0 456

CF620E New Year Tree 线段树 dfs序

luogu链接题目大意: 有一个节点有颜色的树操作1.修改子树的颜色操作2.查询子树颜色的种类注意，颜色种类小于60种只有子树的操作，dfs序当然是最好的选择 dfs序列是什么，懒得讲了，自己搜吧然后开两个数组，begin_和end_记录节点子树在dfs序数组中的开头和结...

线段树

2018-10-09

0 439

最大子段和SP1716GSS3 线段树

前言 spoj需要FQ注册，比较麻烦，大家就在luogu评测吧题目大意: $n$ 个数，$q$ 次操作操作$0 _ x_ y$把$A_x$ 修改为$y$ 操作$1 _ l _r$询问区间$[l, r]$ 的最大子段和思路维护一个区间的\(sum,lmax,rmax,max\)...

线段树

2018-10-08

0 522

hdu Naive Operations 线段树

题目大意题目链接Naive Operations 题目大意: 区间加1(在a数组中) 区间求ai/bi的和 ai初值全部为0，bi给出，且为n的排列，多组数据(<=5),n,q<=1e5 axmorz 思路因为是整除，所以一次加法可以对ans 没有影响...

线段树

2018-10-08

1 464

P2894 [USACO08FEB]酒店Hotel 线段树

题目大意多次操作查询并修改区间内长度==len的第一次出现位置修改区间，变为空思路类似于求区间最大子段和(应该是这个吧，反正我没做过) 维护区间rt的从l开始向右的最长长度从r开始向左的最长长度 l到r内的最长长度反正维护的是个01序列, 随便做又是小错误，第一遍就...

线段树

2018-10-08

1 920