求问uoj有哪些表情能用啊？有没有一个表情包的list呢？

虽然知道版刷uoj是不现实的（何况对于一个只能业余时间来陶冶情操的人），但还是看到#4空着有点不爽，毕竟这里是个打游戏总想着集全成就的强迫症患者。

这是我当年进队的那场NOI，考完后很快就把几道传统题做了，但这题一直没做。其实搞OI时，我从来就没管过提答题，觉得费时费力（事实上做这道应该不算太难的提答题就花了我好多时间orz）。

也是退役了之后心态变得不那么功利了，单纯为觉得好玩而刷。（划掉）

网上翻了一圈也没翻到较详细的题解（更别说代码），就来写个题解造福一波。（还会放代码）

解锁成就：AC提答题！

测试点一

观察发现，正好有一个超长回文数和一个超大质数构成，手玩！

测试点十

找规律了好久，感觉并不擅长提答。从输入可以猜出想让你回文串干掉所有数。发现第一行是回文，但二三行并不是。发现每9列会进行一次循环。

所以其实做法就是，如果我能把每个$3 \times 9$给干掉，由于循环节的特性，所以就能一次性干完了。

然后试图干掉前9列的27个数。分成9个$3 \times 3$的块，块与块构成回文。

最关键的是，从左上角(1,1)出发，按照RDLDRRUUR这个策略，会让每个块构成一个回文。

所以事实上……你不断重复这个策略。。。就做完了！

测试点二

随机，每次随机一个质数或回文串，多次得分取最高。

一个优化是串的开头，本来是随的，效果不好，改成了第一个非-1元。可能是这样更容易消完吧。

测试点三，测试点四

这两个点就是要你搜质数。

我们发现事实上测试点二还能更进一步，质数的密度是很高的$1/\ln n$。我们即使强行要求每个数必须是长为18，从一个点出发，上下左右4个方向走，将会有几乎$4^18$个数字串可以选，而这当中几乎肯定有质数。

所以你写个DFS，很快能搜完一个“由500个18位质数”组成的解。

测试点五

数据范围不大，暴力搜！

搜的结果发现并没有找到既是质数又回文的8位串。

由于数据范围实在不大，所以我每次搜数字串的流程如下：每次枚举串长（从8到2），找到长度等于该串长的分值最高串（程序同时考虑了质数与回文的情况，尽管好像回文没有用）。这个枚举是真纯暴力，就是起点是枚举的，然后枚举$4^8$种情况。最后在所有情况中取max。

交了一发这个点9分，但是我已经纯暴力了。想了想发现，我现在是“若目前最优值小于当前答案，更新解，否则不更新”。我改为“否则，若相等则以0.5的概率更新解”，然后外面套了10次迭代，于是10分了。

测试点六

接下来就是搜回文串了。

这个点很水，直接搜。

测试点七

我用6的程序怎么搜都搜不出来，绝望了一阵。

睡了一觉之后做了点小改动。

随机起点变为将起点设为中心，700+变900+。

然后让两端分别按逆序枚举（比如一个往左另一个就先试着往右）

结果秒出。。。卧槽

测试点八

关键在于方向的搜索顺序！

奇技淫巧：奇数轮顺着搜，偶数轮逆着搜。

然后我本来是，随机一个中心点，以他为中心搜若干条回文串。这个“若干”本来定的较大。

经实践发现，定很大和定个10000，结果差不多。而将这个“若干”改为10000后，枚举一个中心点的时间就很低了——低到可以爆枚所有中心点。

实践又发现，枚举前10行作为中心点后，程序已经能跑出很优的解了。

测试点九

虽然$K=5$，但只要和之前一样，找一个超长回文串就很优了。

观察发现，他“几乎”是对称的。打印一下发现100000个数里仅仅36个不对称的数。

我们将不对称的数置为0，将问题转化为，从左侧某个点出发，找一条全不为0的以第64列为终点的尽可能长的路径，然后翻倍——如果能经过所有点那就太好了。

于是试图去弄一个加了剪枝的求哈密顿路径的算法，没啥进展。

最后我启发式的想出这么一个策略：

从(1,1)出发，右，下，左，下，右，下，左，下……直到最后一行，右，右，现在到了(n,3)。然后右，上，左，上，右，上，左，上……直到第一行，然后右，右，如此循环。“尽可能”地按这个策略。

什么叫“尽可能”的呢？就是DFS时，搜索的最优先顺序是这样的即可。接下来“不能这么做的”，就会自动被回溯过程中弄掉。

于是我将DFS的规则定义如下：假设列%2=0，除了在顶端底端外不能往右；假设列%2=1，他就不允许往左。

        int tmp[6],cand=0;
        if(y%2==0)
        {
            if(x==n&&y%4==2)
                tmp[++cand]=DIR_R;
            if(x==1&&y%4==0)
                tmp[++cand]=DIR_R;
            tmp[++cand]=DIR_L;
            tmp[++cand]=DIR_D;
            tmp[++cand]=DIR_U;
        }
        else
        {
            tmp[++cand]=DIR_R;
            tmp[++cand]=DIR_D;
            tmp[++cand]=DIR_U;
        }
      for(int i=1;i<=cand;++i)
        {
            int px=x+movex[tmp[i]],py=y+movey[tmp[i]];
            if(check(px,py))
                DFS(px,py,lcor,rcor);
        }

大家可以根据上述代码理解一下~然后发现很快就出了个非常优的解（不确定有没有经过所有非对称数，反正能拿10分就对了！）

代码可以参见这里！

大家好，这里是想必已经没有人记得的ydc。

OI时光真的是我高中生涯里一段难忘的时光。即使当年的记忆早已尘封在记忆深处，可当我又一次打开uoj时，当我偶尔与当年的朋友一起吃个饭时，当偶尔有人来问我oi题时，这些记忆都会涌上心头。

如今我已经大四了，大学期间没有任何ACM的经验，科研压力愈发变大，这个时候回来刷题已经成为完完全全没有任何利益的行为。

但是A题还是那么好玩啊！

不需要考虑考试成绩，不需要考虑保送降分，只是单纯地点开一个题来思考有空时来写写代码（准确的说是发现不会做被虐然后看题解）

偶尔上博客写写吐槽，回忆一下往昔，想想当初uoj还只有1,2道题的情形以及那段日子里我的生活

感觉在接下来五年的博士生涯或者更久远的人生里偶尔过点这样的生活似乎很不错

今晚刷了一波UER1，虽然这场比赛当初是我办的，但我只出了#12（最水的那道送分题233）。点开DZY Loves Graph，发现被狠狠地虐了（捂脸）

以后将不定期写点题解和近况吐槽~

写在前面

这场考试我参与了出题

大概是这样的，有三题是某横竖哥出的，我参与了验题，其中有两道正解一道暴力

然后我抄了ZJOI一道题，并向vfk借了一道题

所以我会做4道题

我不知道每道题目的题目名……所以，咳咳咳

一个树形dp题

题意

有一棵$n$个点的边代权树，每个点都是白点，然后你要选择$k$个点将其染黑

一棵树的价值是白点两两间的距离和加黑点两两间的距离和

最大化价值

$n \le 2000$

题解

首先我们要知道的是，这么一份伪代码的复杂度是$O(n^2)$的

void Tree_Dp(int p)
{
    size[p]=1;
    each(x,son[p])
    {
        Tree_Dp(x);
        for(int i=0;i<=size[p];++i)
            for(int j=0;j<=size[x];++j)
                update dp[p][i+j];
        size[p]+=size[x];
    }
}

复杂度的证明？考虑那个二重循环，可以看做分别枚举两棵子树的每个点。你会发现，点对$(u,v)$，只会在Tree_Dp($lca(u,v)$)处被考虑到，所以复杂度是$O(n^2)$

换句话说，$i$所考虑到的点的DFS序一定小于$j$所考虑到的点

于是我们就可以$dp_{i,j}$表示子树$i$选了$j$个黑点，然后转移暴力枚举子树里选了几个黑点，复杂度还是$O(n^2)$的，关键是怎么转移

其实说白了还是设状态的问题，如果设他是子树$i$选了$j$个黑点，子树内的同色点对距离和的话，是不好转移的对吧……所以我们要把他们往子树外连的也考虑进来

这么讲吧，假设我们把任意一对同色点之间的路径给标一下，那么$dp_{i,j}$记录的就是，子树$i$选了$j$个黑点，子树内的所有被标过的路径权值和，这样就能转移了

简单地说，就是改变一下状态定义，就能让他不仅考虑子树$i$内部的和，把子树外的延伸到子树内的那些边也考虑了

这是我验题的代码

void update(LL &a,LL b)
{
    if(a<b)
        a=b;
}
void DFS(int p,int fa)
{
    static LL tmp[maxn];
    fill(dp[p]+2,dp[p]+n+1,-INF);
    size[p]=1;
    for(int i=start[p];i;i=next[i])
        if(to[i]!=fa)
        {
            int q=to[i];
            DFS(to[i],p);
            fill(tmp,tmp+size[p]+size[q]+1,-INF);
            for(int j=0;j<=size[p];++j)
                for(int k=0;k<=size[q];++k)
                    update(tmp[j+k],dp[p][j]+dp[q][k]+len[i]*(k*(m-k)+(size[q]-k)*(n-m-(size[q]-k))));
            size[p]+=size[q];
            for(int j=0;j<=size[p];++j)
                dp[p][j]=tmp[j];
        }
}

一个数据结构题

题意

一棵$n$个点带权的树，$m$个操作，分别是：单点加、子树加、查询点到根的链的权值和

题解

这题是超级良心送分题啦~考验基础数据结构水平

（算了还是卖卖萌把这题讲讲）

算贡献

假设点$u$的子树加了$x$，点$v$在点$u$的子树内，那么对$v$到根的链的权值和会带来$(dep_v-dep_u+1)x$的贡献

假设点$u$加了$x$，点$v$在点$u$的子树内，那么对$v$到根的链的权值和会带来$x$的贡献

$dep$数组是常量，我们设一个点$i$到根的链的权值和为$k_idep_i+b_i$

那么子树加操作就是把整棵子树里每个点的$k$值和$b$值加上同一个数，单点加操作就是把整棵子树的$b$值加上同一个数

子树可以转为DFS序的一段区间，所以用两个树状数组分别维护每个点的$k,b$数组就行了

str

题意

你有一个长度为$n$的数字串。

定义$f(S)$为将$S$拆分成若干个$1 \sim m$的数的和的方案数，比如$m=2$时，$f(4)=5$，分别为：

$4=1+1+2,4=1+2+1,4=2+1+1,4=2+2,4=1+1+1+1$

你要将这个数字串分割成若干个数字（允许前导0），将他们加起来，求$f$，并求和，和为$g$。

比如$g(123)=f(1+2+3)+f(1+23)+f(12+3)+f(123)$。

已知字符串和$m$后求答案对$998244353(7×17×223+1$，一个质数$)$取模后的值。

字符串长度不超过$500$，$m \le 5$

题解

ydc从ZJOI上抄的原题，来源是ZJOI2011年的细胞

首先考虑$f$怎么求，很容易发现$f(n)=\sum\limits_{i=\max(0,n-m)}^{n-1} f(i)$。由于$m$只有$5$，我们可以用一个$m \times m$的矩阵表示转移矩阵，记作$A$。

那么答案就是一堆$A$的若干次方的和（两个$m \times m$的矩阵是可以相加的）。

假设我们把数字串分成$k$个数，分别是$a_1,a_2,a_3,\cdots,a_k$，那么答案是$A^{a_1+a_2+a_3+\cdots+a_k}$，他恰好等于$A^{a_1} \times A^{a_2} \times A^{a_3} \cdots \times A^{a_k}$。

一堆$m \times m$的矩阵，不仅能乘，还能加，还有分配律，我们就能$dp$了

$dp$当然就是$dp_i$表示$1 \sim i$这部分的答案矩阵，转移显然，贴下标程的代码吧

    for(int i=1;i<=n;++i)
    {
        now=pw[0][a[i]-'0'];
        F[i].n=F[i].m=m;
        for(int j=i-1;j>=0;--j)
        {
            F[i]+=now*F[j];
            if(j)
                now=now*pw[i-j][a[j]-'0'];
        }
    }

复杂度是$O(n^2m^3)$

set

题意

一个有$n$个元素的集合，你有一个空集，每次你会选择集合的一个子集，与当前集合进行取并集操作，问期望多少次后第一次变成全集，选中每个子集的概率是输入给你的

$n \le 20$

题解

vfk教ydc做人

先来普及一点科技

定义一种乘法为$c[n]=\sum\limits_x\sum\limits_y a[x]b[y] [x \mid y=n]$

定义一种子集和变换，即$f(n)=\sum\limits_{x \subseteq n}g(x)$

我们用子集和变换来考虑上面的乘法

左边自然是$\sum\limits_{x \subseteq n}c_x$，右边应该是$\sum\limits_{x \subseteq n}\sum\limits_{y \subseteq n} a[x]b[y]=\sum\limits_{x \subseteq n}a[x]\sum\limits_{y \subseteq n}b[y]$

有没有发现什么？进行了子集和变换之后，之前的奇怪乘法，变成了人们熟知的点积

那么我们只要把$a,b$给子集和变换一下，点积得到$c$，再把$c$变回来

说到这里，介绍一点科技：如何巧妙地子集和变换与变回来

    for(int i=0;i<n;++i)
        for(int j=0;j<N;++j)
            if(j>>i&1)
                a[j]+=a[j^(1<<i)];
    for(int i=0;i<n;++i)
        for(int j=0;j<N;++j)
            if(j>>i&1)
                a[j]-=a[j^(1<<i)];

分别是变换与变回

好吧回归正题

读入的数组是$p$，将它看作多项式，先用定义的乘法来考虑，那么$p^k$的第$i$项就代表$k$轮之后得到$i$的概率

答案是$\sum\limits_{k}k \times (p^k-p^{k-1})[2^n-1]$。我们设$f(x)=\sum\limits_{k}k \times (p^k-p^{k-1})[x]$

由于定义的那个乘法太麻烦，就子集和变换一下，就变成了我们所熟知的点积了（不是多项式乘法）

$(p^k)[x]$就是$p[x]^k$

$f$的子集和变换后的结果，是$\sum\limits_{k}k \times (p^k-p^{k-1})=-(1+p+p^2+p^3+\cdots)$

由于$p$所有元素加起来才是$1$，那么子集和变换后的$p$里每个值，肯定也是在$[0,1]$之间的

于是$-(1+p+p^2+p^3+\cdots)$可以$O(1)$算出，得到了$f$的子集和变换结果，变回去即可

时间复杂度：$O(n2^n)$

弃疗大法好。

虽然自称自己想要通关，最终还是认输了。

现在想来我的确也没有通关过什么东西。

淡淡地忧伤。真不知道我这多出的52题是用来干嘛的。

完成量152/158。希望可以帮助到大家。有题解甚至是代码。

未完成题目：

Codeforces 335F buy one, get one free

GCJ 2012 Final E Shifting Paths

GCJ 2010 Final E Ninjutsu

GCJ 2011 Final D Ace in the Hole

GCJ 2011 Final E Google Royale

GCJ 2012 Final C Xeno-archaeology

我的集训队作业

OI中有很多排序算法，冒泡排序，插入排序，快速排序，基数排序，以及神一般的bogo排序等等等等。

在这门不断追求速度的学科里，最快的排序方法是什么一直是信息学皇冠上的明珠。基数排序是线性的，但是却有非常大的局限性，仅仅基于比较的排序复杂度的下限是多少呢？

有一天，一个人出来妖言惑众：“基于比较的排序复杂度下限是$O(n \log n)$的。”并且提出了伪证。

他用一棵二叉树来建立模型，通过对树的深度进行探究，从而推出排序的复杂度下限。于是人类停滞不前，再也没有人试图创新。

然而事实上，他的行为有着一个巨大的漏洞：那人试图利用大家对树的不甚了解以及其巧妙地误导，愚弄了大家。在此，我们来重新分析树的深度。

我们来真正思考真正的树要具有什么样的性质：根据生物课上所讲的，一棵树不可能无限的生长下去，也就是说一棵树的深度应该是常数；然而他的假树却不同，随着叶子的不断增加，树的深度是会跟着不断增加的——是一个发散的数列！这显然与树的深度不能无限增长这个生物知识相矛盾！虽然由于他巧妙地文字以及我智商的程度至今我还不清楚他是在哪一步偷天换日，将树的深度由有上限变成了没有上限，但既然我们已经知道他认为树的深度是$O(\log n)$这点绝对是错的，我们就有理由继续深入思考。

然而，由于智商所限，我再也没有过一丝成果。我清楚地意识到我尚未领悟人类智慧的力量，于是我开始四处遍寻高人。为了能抹去这个多年笼罩在大家头上的乌云，让人类文明进入新的时代，我曾以囚徒身份进了北京八十监狱寻找至今没人知道身份的黄半仙，曾请教过湖北一位统领全宇宙跳蚤的国王，却一直没能得到满意的结果。终于有一次，我跟随着黄半仙，来到了帝都航天大学吃特色菜（CTSC），在吃特色菜的过程中，我见到了人类智慧之神——Mato_No1。

Mato_No1上台讲述了自己的研究成果，他告诉了我一个惊天动地的消息：开了O2的set是$O(1)$的！

顿时，我感到一道曙光冲破了乌云：是不是只要我们将元素插入开了O2的set，再遍历输出，就能得到$O(n)$的排序方法了呢？这样子的话，那棵树的深度也是$O(1)$的啊。

然而事实却再一次给了我打击，我学习了set这个数据结构，然而我很不解的是他明明是一种叫做平衡树的东西进行维护，但是trajan告诉我，平衡树是$O(\log n)$的。trajan大神与Mato_No1大神的思维产生了碰撞，我一遍遍的回忆，终于意识到了真相：开了O2的set！

O2是什么？氧气啊。众所周知，树在有氧气的情况下，会进行呼吸作用！学科的知识再一次产生了交叉，生物学的知识推进了信息学的发展！我们必须明白，平衡树遇上O2进行呼吸作用后，究竟会有怎样惊人的效果！

然而我却再也没有见到Mato_No1，据说他已经进了五道口男子职业技术学校，那里有更多更多的大神，我想，要知道信息学与生物学本质上的联系，也许只有那里的大神才能回答。为此，我于同年七月踏上了南下的火车，得到了进入五道口的机会，从而于明年暑假结束后去寻求真相。然而，没有想到的是，这个真相来的比我预料中的更早。

在昨天，通过一个偶然的机会，我看到了一个叫猪猪侠的大神所写的神奇数据结构Spaly。短短几行代码，却显示了其超高的水平，让我捉摸不透。由于智商差异过大，我只能体会其神奇却不知其原理。可没过多久，noip吧的前吧主却对数据结构Spaly进行了解答

看了这段话，人类多年的疑惑在前吧主轻描淡写的话语中，已得到了解答。真相只有一个！

是的，单旋的Spaly，可以$O(1)$的完成平衡树的操作！这也与树的深度是常数这个科学道理是吻合的！我们可以想象，当set里的那棵平衡树遇到了氧气后，他进行着呼吸作用，每次再也不需要费力的进行双旋，深度也瞬间变成常数！无论树的叶子再怎么多，他的深度永远是常数！

至此，$O(n)$的排序方法诞生了。我们要感谢Mato_No1大神与猪猪侠大神，当然还有对其进行了最终的总结的前吧主Foreseeable！此外还要感谢CCTV，感谢MTV，感谢父母，感谢祖国！

参考文献：

• Mato_No1在吃特色菜过程中的讲话
• 猪猪侠公开出来的代码
• Foreseeable在贴吧里的发言