Topcoder-OpenTopcoder-Round1C

终于没有 hole 这个 tag 了～

Solution

250 pts

做这个 250 不要 250 了……

枚举最大值在这个序列的位置，可以根据位置及 d 算出这个数是多少，然后取遍 max 即可。

500 pts

二分答案，没了。

1000 pts

感觉这个题好囧啊。

令 S 表示随便放一个马，除自己这个格子外，期望能够攻击到多少个格子；令 P 表示同时能被两个马攻击到的期望格子数。经过一定的推理后，我们可以发现如下公式：

ans = 2S + 2 - 2S/(n^2-1) - P

于是我们只要求出 S 和 P 即可。求 S 的话可以考虑统计每个方向上可以放的马的数目， P 的话我们就枚举同时被攻击到的马的位置。

首先考虑 a == b 的情况。 S 倒是很好求， P 的话可以推出一个公式来的。

再考虑 a /= b 的情况， S 照样很好求， P 就不一定了。我 YY 了一个很奇葩的方法。首先找到边界上的若干个分界点： {0, a, b, n - b, n - a, n} 。这若干个点把大矩形分成了 25 个小矩形。矩形内部的 P 是一定的，随便找一个点（例如找中点）即可判断出某矩形内的点的 P 。然后再用组合数乱搞一下即可。

situation

怒刷小号～从此我也是有 TC 小号的人了～

一进 room 一看，cherudim9 是 room 内 rating 最高的，我是最低的，高下立判。

一打开 250 pts，插件自动帮我生成了……Java 模板？我勒个去果断自己手写 C++ 。

随便一想觉得这题蛮水的啊，写完后样例都没测（因为没插件不好测），直接在 Arena 里面测了。觉得没啥问题就交了。这题真心水啊怎么 room 里第二个交的才 230+ 呢？

果断重新配置插件。把默认语言改为 C++ 一切就好了。

然后开 500 pts，这不是一个绝世大水题吗……怒写然后过掉。

现在时间还多的很呢，于是开始 YY 1k pts 。一开始的时候根本就没想到还有 P 这种干扰，后来才想起来……

感觉样例很强的啊，于是感觉是可过的。

cha 人的时候看到 500 pts 有人没用 long long 来保存中间结果，就想着这是不是一个 cha 点。我看到有人程序和我的特别像，于是在 cha 之前用自己代码测了一遍，发现过了？继续 YY 发现就是过了。自己一想发现中间结果至多是 2k 怎么可能会爆 int ……

最后的 FST 是什么情况啊！发现是 a == b 时的特判写挂了 T_T

所以最后是 #60 。如果 1k pts 不 FST 的话前二十没压力的 T_T

others

这次做的人不多，很多人都做前两次去了。

cherudim9 本来还好的，可是被 500 pts 的那个不是 cha 点的 bug 搞错了于是 +0/-2 囧…… #174

秋锅 #72 。令人惊悚的是他现在 rating 还没我小号高 = =||

看到了 DL.uhT 分布式哈希堕落？其实是某盾啦 #93

lydrainbowcat 1k pts 的被 cha 于是 #107 。

至于大叔……哇过了两道诶，虽然速度比较慢但是没爆零了啊～#227 不过 rating 还没他的第一次高……

cjsyj 的 250 pts FST 了？ 这不科学 ！ #425

This_poet 居然 FST 了 500 pts ？#685 momo

nonsense

今晚 CF 欢迎各位参加～