Tag Archives: C++

这题算是个数论题。 其实也没用到什么数论结论，首先手算找找规律。发现，对于 [tex]\forall x\in (\frac{n}{i+1},\frac{n}{i+1}],x\in {\mathbb Z}[/tex] 有 [tex]n ~{\mathtt div}~ x[/tex] 为常数[tex]i - 1[/tex]，于是这一区间内的数就可以只算一次，然后将结果乘以区间内整数的个数就行了。但当[tex]i>\sqrt{n}[/tex]时，每个区间的长度[tex]\frac{n}{i}-\frac{n}{i-1}\sqrt{n}[/tex]时，进行朴素的计算。 时间复杂度 [tex]O(\sqrt{n})[/tex]，空间复杂度 O(1)。 算法就是这样了，刚开始写的时候 TLE 了，原因是作为循环条件的 sqrt(n) 没有提前计算出来，于是导致了很多不必要的运算，多么低级的错误…… C++ 代码在这里。 P.S. 突然想做编号是大家生日的题目，这题编号是我一个朋友的生日，自己的生日编号的题目的状态是暂不提供…… Tags:algorithm,C++,OI,Vijos

一年没写代码了，这周又开始拿起我那二把刀，开始切题了…… 看到我们的小妹妹写了积木城堡这个题，于是我也从这题开始了…… 简单的 0/1 背包，渐进时间复杂度（大概）是 O(N*n*n)，渐进空间复杂度（大概）是 O(N*n*n)，其中 N 为城堡数量， n 为组成每个城堡的积木数。 这题有着 Vijos 的一贯传统，就是题目描述令人 confused，就这题来说，从中间抽取积木还能使城堡不倒，不得不说是有一定功力，抽出的积木就扔在一边，不能不说是浪费。其实这都可以在题目中说清楚的。 开始做，一开始用了 bitset （在 NOIP 中允许使用），结果 TLE ；后来优化了读入，还是 TLE，后来砍掉了 bitset ，用 boolean array，提交无数次后（Vijos 最近服务器有问题，运行程序忽快忽慢，随机 TLE 的现象时有发生），终于 AC 了。 代码可以看这里，其他 vijos 的代码也在那里。 事实证明， bitset 的效率并不高，竞赛的时候应远离 bitset …… … Continue reading →