Luogu – 第9页 – Tgotp-Blog

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 【模板】树链剖分

送一组简单数据。

模板没啥好说的吧。

硬币的面值

P1896 [SCOI2005]互不侵犯King

九宫格的话,只要跟上一行对比就好了,用了滚动数组优化,状压dp显而易见,具体看代码注释咯。

玛丽卡

次最短路问题。详情看代码。