【水题合集】6.8考试

今天居然考NOIP题。。两小时做完

随便AK

1.ly的农场

一开始还以为是Tarjan什么的

一看数据范围

暴力枚举删除每个点然后BFS即可。。

2.xqz的难题

究竟是谢其哲还是向期中呢?

说是插入一个数到数列的最后+查找删除+区间查询 还以为是Splay

然后发现就是个农民题

并且xor还满足区间减法

直接树状数组

3.ld的棋盘

看到题目:这不是今年PKUSC的D1T1么

看到内存限制吓傻了

试了一下下面这个程序:

告诉我用了3MB

然后去找向总把内存调成32MB了

这题就是迭代加深然后剪剪枝。。俗称IDA*

我的剪枝似乎不够强力被向总机子卡掉一个点。。

还有就是农民标程居然写错了。。

4.jx的游戏

以前只知道一段两段可以做没想到三段也可以做哦?

和两段的差不多,令\(dp_1[i]\)为\(右端点\le i\)的最大区间,\(dp_2[i]\)为\(左端点\ge i\)的最大区间,\(sum\)为前缀和

那么答案为\(max(sum[r]-sum[l-1]+dp_1[l-1]+dp_2[r+1])\)

整理一下发现我们可以枚举\(r\),\(l\)的优劣与\(r\)并没有关系

最优\(l\)边走边算就行了

说点什么

  Subscribe  
提醒