看算法看到恶心了……

阿本

今天听说了POJ这个著名的国内计算机试题网站，然后跑去看题目试试水……：
http://poj.openjudge.cn/practice/R5F/
一开始选了这题试做，做了半天，虽然有了大概的思路但是很多细节不会处理（用什么数据结构存储数据，用什么输入数据——那边已经有好几个上交的答案time out的情况了）……
顿觉这题难度太高，换个题目：
http://poj.openjudge.cn/practice/1009/
这个看起来答题成功率不错的样子？于是开始做……
等等……）尼玛咧我为什么看不懂这题目的输出格式？没奈何，只好去查了半天其他人的答案……
搞半天才弄清楚输出的矩阵横向为背包容量变化，纵向为丢失的物品，内容为放进背包的物品组合可能数量……ok？好像能做了？
不过再等等……这个“放进背包的物品组合可能性”要如何计算啊？那些答案在这方面也都含糊其辞的……啃了半天代码，无法理解啊无法理解……尼玛这玩我呢？！（掀桌
（现状：已然燃尽，化为灰灰了……

时间停止le

矩阵简直sxbk

我正在啃C，还有一周就要考试了，看怎么个作死

BIT

算法是什么？我表示已被算法设计课虐的不能自理

冰冻西瓜

作为曾经的信息学竞赛选手，现在的圈外人士讲一下思路。。
第一题：做法很复杂，我自己不保证写得出来！！
首先按操作分治，写个函数solve(l,r)表示处理第l到第r个操作。那么先分治成solve(l,mid)和solve(mid+1,r)，然后我们就只要考虑l~mid中的加点操作对mid+1~r的询问操作所产生的影响。这样就把问题转化成了离线的：已知若干个点和若干个多边形，问每个多边形中包含了多少点。
首先，对于点在边上的情况不太好搞，特判掉。然后我们发现多边形不太好做，就用竖直线剖成若干个纵向的梯形来做，并保证梯形的个数跟多边形点数是一个级别的。（这一步不太好搞，但是是一个经典的梯形剖分算法，代码实现较为复杂，我自己也没尝试过。）后来想了一想不用这么麻烦，我们只要知道对于每条横向或者斜向线段，是它的上方在多边形内部还是下方在多边形内部，也就相当于求出当前这条线段上方有奇数条还是偶数条线段，这个还是比较好做的。
进一步，还可以把求梯形中点的个数问题转化为给定一条线段，求横坐标在这条线段的横坐标范围内且在这条线段下方的点的个数问题。如果这条线段是平行于x轴的话直接用树状数组解决，否则如果是45度角就通过坐标变换变成平行于x轴的情况解决。

第二题：按照经典的动态规划思路，f[j]代表第1~i个物品凑出质量j的方案总数。那么缺第i个物品，凑出质量j的方案数就等于所有凑出质量j的方案数减去必须放入第i个物品凑出质量j的方案数，后者也等于不放入第i个物品凑出质量j-w的方案数。得到递推公式：count[j]=f[n][j]-count[j-w]。
（很久没做题智商真的掉了好多，第二题这种当年可以秒掉的现在还是感觉有些压力！！）

阿本

其实我主要想吐槽的是……尼玛这些“砖家叫兽”只会出题不会教人怎么做题吗？！这也就罢了，怎么连题目都不会好好说明啊？！都该给我滚回中学重读语文去！！！

冬眠的小德

尼玛。你说的这些是什么
每个字我都认识连在一起这是什么玩意儿
跟我做法语阅读一个赶脚啊，哭了

冰冻西瓜

阿本 发表于 2014-3-23 00:01
其实我主要想吐槽的是……尼玛这些“砖家叫兽”只会出题不会教人怎么做题吗？！这也就罢了，怎么连题 ...

教人做题不是这种题库网站干的事，基本得靠自己google积累。。然后作为一个有几千道题的网站，题目质量不可能都非常高。。最后第二题题目我看了没有问题。。

lixiang5628638

九度什么的，我做的都快吐了

贤狼假寐

我只是刚啃了JAVA一口！这些啥都不懂啊！！！！

Ariados

pku online judge嘛
就是个在线评测平台
不带教学功能的
(能刷动poj就代表有一定水平了加油吧