Luogu – 第9页 – Tgotp-Blog

水平可见直线 BZOJ 1007 && 洛谷 3194

类型:半平面交

注意:初始情况下 应直接压入;

实现:直接手推 y 相同时 x的情况,进行更新(建议自己过手推一遍)。

算法:排序和单调栈

c++代码如下:

 

BZOJ1057 & 1862 & 洛谷2584 排名系统

splay + trie树。

洛谷上a不掉,但是bzoj两题都能a ,应该不是我的错QAQ

 

bzoj1006 P3196 [HNOI2008]神奇的国度

思路:弦图

算法:mcs,邻接表

具体实现:逆序寻找完美消除序列,然后染成能染的最小颜色,证明参见cdq的弦图与区间课件。

c++代码:

 

BZOJ1046: [HAOI2007]上升序列 Luogu 2215

思路:lis + 二分答案 + 贪心?

过程:之前一直在纠结字典序输出,后来一想,从最前面开始,向后枚,肯定是最优的,还有一个坑点,严格按照格式输出;

另外就是 lis  要注意从后向前找,即f[i]代表从 i 开始,最长的上升序列长度吗,其他的就是基础lis过程。

over[......]

Read more

P1049 装箱问题

应xyf的要求写了纯c;

教学弟的blog。

思路:背包dp;

过程:f[i]表示背包使用i的容量时能装的最大价值,对于v向下处理,更新最大值,ok;

 

P3794 签到题IV

 

 

P1383 高级打字机

这题的IOI挑战就是可持久化结构;

在线的实现用主席树就好了;

undo就是追溯过去sz-1-x的版本(其本身也算作一个版本);

而query就是从上次的版本找到第x个;

至于add就是新建立一个版本,并且在起相应位置插入当前的字符c;

代码仅供参考。

c++代码[......]

Read more

P3369/BZOJ3224 【模板】普通平衡树(Treap/SBT)

平衡树模板

P1000 超级玛丽游戏

水一水更健康,偶尔来一发水题也挺好。

 

P3384 【模板】树链剖分

送一组简单数据。

模板没啥好说的吧。