[更新1.0.1]T^T20160424之吐槽

嗯……今天是忧桑的一天。

今天是LNOI2016 Day2,到中午LNOI2016正式结束,好多可爱的学长都要退役了,因此感到十分悲伤TAT。

还是先说下题吧,T1是这样的。

给定一个字符串A(长度小于等于10000),和他的n(小于等于4)个子串 \({B_i}\) (长度小于等于1000),现在可以用这些子串去覆盖原字符串,要求每个子串恰好使用一次,求最多和最少覆盖多少个字符。(输入包含小于等于10组数据)。

我的做法是先乱搞出每个子串在原串中结束的位置,然后用一个奇怪的dp搞一下,大概是dp[i][S]表示对于A[i]及以前的部分用集合S中的子串覆盖的最小值,然后状态转移是O(n)的,总复杂度 \(O(C{n^2})\) ,其中C是一个常数。

前五个点A长度都是小于等于1000的,然而由于dp写的有点问题WA了4个,得分10分。

T2好像是一道奇怪的数据结构题。

(此题3秒)给定平面上n(小于等于100000?或许加个0)个无公共点的圆(也就是任意两个圆的关系非外离即内含),以圆心坐标和半径(均为非负整数,半径为正)的形式给出,求它们的异或面积并。

异或面积并就是对于某个部分,如果它在奇数个圆内则算面积,在偶数个圆内则不算。

前3个点保证n小于等于3000所以应该很容易写出 \(O({n^2})\) 暴力,然而我这次状态相当不好于是暴力都没想出来,交了一个0分的程序=。=得分0分。

T3是一道提交答案题。

说呢某学渣要期末考试了,他现在有n个学科(数据中小于等于60),距离考试还有d天(数据中小于等于100?300?忘了),然后呢他每天可以复习一个学科,对于每一天,他复习的学科将会增加多少多少分(忘了,应该是个常数),然而他没复习的学科将会减少多少多少分(此分数随连续没复习天数线性递增),然后对于每个学科考一个常数以下的分视为不及格。

你的目标就是给出一个复习方案,使得没有不及格的情况下总学分最多(总学分的计算公式大概是把所有科的得分百分比乘一个常数并求和)。

如果没有不及格的能保证得1分,然后根据你的答案和最优解的相对差值计算得分。

我的做法很简单,由于给了一个checker程序,能对于你的一个输出告诉你是否合法和总学分是多少,于是我就写了个随机生成解并且调用checker看多少分的程序,复制10份然后不断随机并更新最优答案,最后有7个算出来了,有3个一直没跑出来任何合法答案,估计是手造的数据,得手动推,然而由于我今天状态极差时间安排不当最后才做这道题导致没时间手推然后直接交了那7个跑出来的随机答案(而且随机的时间也很短,大概只有半小时)。得分42分。


总之就是这样,一共得了52分=。=

单看这次考试成绩进省队是没问题=。=然而我noip没考(内时候我还不知道OI是啥呢),所以具体情况待定。

就是这样,最后祝福一下高二的前辈们。

发表评论