Topcoder-OpenTopcoder-Round2A

本来就只打算拿件 T-shirt 的。600 挂了就挂了吧。

或许按照这个趋势下去，我有淡出 ACM 届的趋势？还是专注算法三十年好了。

Solution

300

裸贪是不对的。

于是写 dp 吧。 \(f_{i, j}\) 表示前 \(i\) 个字母中，保留 \(j\) 个字母所组成的最优的 S 串，以及在 S 串最优的前提下最优的 T 串。转移枚举这个字母取不取就好了。

开黑什么的，还是不要搞的为好。

600

考场上写了个莫名其妙的搜索，当然是 FST 的命运。

考后想高斯消元应该可做啊，于是随手写了个高斯消元。连样例都没调，连我自己都觉得这是错的，结果发现居然过了？我勒个去。

首先特殊情况是 \(n > m\) 其中 \(m\) 表示有多少个已确定的元素。在这种情况下，一定存在一行一列使得这一行一列上没有已确定元素。于是除这一行一列外的其余的元素随便填，到最后还剩下这一行一列的时候，再枚举每行每列的和是多少，那么每个元素的值都会确定，并且一定存在一组可行解（显然），所以答案就是 \(10^{n^2 - 2n + 2 - m}\)

\(n \leq m\) 时的情况比较难处理。不过说到高斯消元大家应该就知道这题该怎么做了。为了解决 10 不是质数，我们利用 CRT 分解下就好。一行一列相等，这个可以表示成一个方程。一个变量的值确定了，我们也可以把它表示成一个方程组。那么共有 \(n^2\) 个未知数，有 \(n^2 + m\) 个方程。去掉其中线性相关的方程后，答案就是模的自由元次方。再判判无解什么的就好。

1000

看完题的第一眼觉得这是水题。仔细想想后发现不会做。经过文学巨匠 wzy 教导后觉得这题怎么还是水题，写完后发现这想法是错的，重新想发现是神题，写了好久总是过不了，调啊调调啊调调了一下午终于发现错误了—— LCM 要用 long long 存……我的天啊

看完题的第一想法是对每个不同的基分开统计。于是我们要求当 \(x\) 从 1 取到 \(A\) ， \(y\) 从 1 取到 \(B\) 时，共有多少个不同的 \(xy\) 。其中 \(A\) 的范围很小，只有 30 。 \(B\) 的范围是 \(10^9\) 。

文学巨匠的方法如下：对于一个 \(x\) ，它最小的质因子为 \(d\) ，则 \(x\) 对答案作出的贡献是 \(xB - \frac{xB}{d}\) 。加起来就好。显然这是错的可是我居然没发现。

考虑容斥。暴力 \(2^A\) 的容斥显然是不行的。于是考虑将若干个类似的状态一起表示出来。假设一个数 \(n\) 可以同时被表示成若干个 \(xy\) ，则 \(n\) 一定是所有 \(x\) 的公倍数。于是我们可以设计一个 dp ： \(f_{i, j, k}\) 表示前 \(i\) 个数中，我们选取了 \(j\) 个数，这 \(j\) 个数的 LCM 为 \(k\) 的方案数。 \(f\) 的转移很简单，枚举这个数字选不选就好了。由于 \(n\) 要能被表示出来的话，一定有 \(\frac{n}{\min \{x\}} \leq B\) ，于是我们可以从大往小 dp ，每选中一个数，那么它一定是已选中的数中最小的，在这个时候计算方案数即可。

一个小小的优化是对于只包含前若干个质数的数用 dp ，其余的数仍然爆搜。

然后就可以过了。

situation

开了 300 后感觉这是个水题啊，于是 YY 了个贪心，大概就是把上下的绑在一起，用一个栈处理一下。但是这样做是过不了样例的。瞬间想起了 dp 。然后就只有 260+ 分了。看起来样例蛮有良心的。

penicillo 你 299.80 分是什么心态。

然后开 600 。看完后第一想法是 \(n\) 大的话很好处理， \(n\) 小就不好搞了。于是我决定写搜。我的方法是找一个空格子，使得这个空格子所在的十字内的已选格子尽量少。然后爆搜出一个小矩形的，这个矩形的大小具体有多大我也不知道 = =|| ，但是肯定很小就是了。对于其余的格子，我猜解的数目等于 10 的自由元次方，但是这是错的 T_T 于是光荣 FST 了。

写了正解后发现正解比爆搜还好写些，什么心态。

1000 看完题目就溜了。

最后过了 300 #90 。由于是小号所以仍然可以涨 LOL 。

others

各种奇葩不忍直视。

tourist 前两题都好慢的说，但是靠 cha 人 cha 到了 #3 真是不忍直视……

有人只交了第一题 FST 后仍然有 300 分，丧心病狂。

wuzhengkai 被我怒压 0.03 分……

大部分人是过了第一题，scottai #205 edly #209 xujie #350

target 君 tomek 居然 #375 ，只交了 140+ 分然后怒 cha 错三个。

lyrically 被 cha * 1 FST * 1 最后靠 cha 人没爆零。

cgy4ever FST * 1 加上 cha 错一个导致爆负，太可怕了。

大叔又一次爆零了……但是令人惊悚是……他……居然……涨了……