=。=20160423之吐槽

=。=不知道起什么题目好于是就起了一个这么样的奇怪的题目。

嗯,今天是LNOI Day 1,蒟蒻雪舞喵水了50分(觉得题好难QAQ)。

首先看到题就有种似曾相识的感觉(似乎和某ryz有说不清道不明的关系)。

T1看起来似乎是一道树dp,题大概是这样的。

(此题2秒)现在有一棵n个点 \((n \le 500000)\) (大概是?或许加个0)的树,然后呢,现在可以在一些个点上插眼,在i号点上插眼的代价是w[i] \(({w_i} \le 1000)\) ,每插个眼可以覆盖d的距离 \((d \le 20)\) (即到该点树上距离小于等于d的店都被覆盖),要求覆盖m个点 \((m \le n)\) ,求最小代价。

第一个点很水,直接暴力哪些点插眼就可以了=。=,于是我就得了10分。

T2是这样一道题。

(此题1.5秒)现在有一个n*m的棋盘型网格 \((1 \le n, m \le 100000)\) (即n行m列,或许加个0),一共(n+1)*(m+1)个格点,现在要求在棋盘上选择4个格点组成一个正方形,然而给定了k个不相同的点 \((k \le 2000)\) (?)不能作为顶点,求一共有多少种组成正方形的方案(%1e8+7),需要注意的是正方形可以斜着放。

(此题20个点)前4个点都很水,直接暴力左上角和右下角,然后判断是否合法就可以了。

下两个点保证k==0,然后我就打了个excel(考场有Excel好评),暴力推出了dp方程,线性解决。

于是得了30分。

T3就更奇怪了。

(此题2秒)是这样的,小R的室友B神说能碾压他们系的k个人(他们系一共n个人,m个科目,第一个是B神) \((n,m \le 100)\) ,所谓碾压就是对于每一科的成绩B神都大于等于对方。已知B神在第i科的排名为 \({r_i}(1 \le {r_i} \le n)\) ,即恰好有 \({r_i}-1\) 个人的得分大于他,另 \(n-{r_i}\) 个人成绩小于等于他。给定每一科的满分 \({u_i}(1 \le {u_i} \le {10^9})\) ,每个人每科最少得1分,最多得 \({u_i}\) 分,求有多少种得分情况满足恰好k个人被B神碾压,另n-k-1个人不被B神碾压。(方案数%1e9+7)

第一个点保证n, m, k <= 3,直接暴搜。于是获得10分。


于是就是酱紫,明天继续加油!

\sico

发表评论