http://codeforces.com/gym/100443
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4423

首先用一个栈记录操作S后笔的位置,然后在此基础上统计笔之后可能在哪些位置。
定义向左走的「潜力」l为那些已经确定可以到达的点的未达的左儿子个数,类似定义向右走的「潜力」r
那么向左走就是ans+=l,同时更新r+=l;向右走类似。
不在根节点时向上走就是++ans,同时根据向上走的方向来更新lr

继续阅读

http://codeforces.com/contest/460

D题 Little Victor and Set

构造。
关键在于两个相邻元素的异或可能会很小。
当集合中有两个元素时,答案可能是l^(l+1),但l=1011时就不太合适,这种情况下(l+1)^(l+2)就更好,此时异或为1。
当集合中有四个元素时,可能出现异或为0的情况,也要考虑,方法与有两个元素时类似。
当集合中有三个元素时,唯一可以使异或为0的构造是找到一个大于l的2^k数,令其为x。
此时异或的结果已经达到最小,更大的集合大小就不用考虑了。
比如x=10000,那么
x-1=1111,
x+x/2=11000,
x+x/2-1=10111。
此时三者异或恰好为0,并且这组数恰好是所有三元组中最大数(这里为x+x/2)最小的。

附代码:

继续阅读

int solve(int n)
{
    int sqrtn = sqrt(n + 0.5), cnt, ans = 1;
    for (int i = 2; i <= sqrtn; ++i) if (n % i == 0)
        {
            for (n /= i, cnt = 1; n % i == 0; n /= i) ++cnt;
            if ((i & 3) == 1) ans *= cnt << 1 | 1;
        }
    if (n > 1 && (n & 3) == 1) ans += ans << 1;
    return (ans - 1) >> 1;
}

使用 Pollard's rho 算法可以加速到,代码就不贴了。。

参考 A046080 中的 Mathematica 代码:

cnt[n_] := If[n == 1, 0, With[{expList = Select[FactorInteger[n], Mod[#[[1]], 4] == 1 &][[All, 2]]}, ((Times @@ (2 * expList + 1)) - 1) / 2]];

证明待填。。