数位过程类题目的一般算法

何为数位过程类题目呢?(我瞎编的名词)
就比如说我和谐社会模拟赛的第一题(其实是SGU390)
跟数位有关。还是一个过程。。(汗一个)
题目一:
http://www.orzoj.org/ 上的father
解决这个题目的话。我们需要对这个题目究竟在干神马丽洁清楚。。
这个题目本质上是一个过程,从l进行到r,直接暴力模拟显然是会TLE的。
因此我们需要寻找一种加速的办法。
首先对于无规律的区间[l,r]显然很难加速。
注意到我们可以把区间[l,r]分解成一堆个数不超过O(LogR)的xxxxxx00000-xxxxxx99999这样的区间。。
同时我们可以发现xxx000-xxx999
可以分成10个更小的区间xxx000-xxx099+xxx100-xxx199….balabala
然后我们就可以考虑这个更加规范化的问题了。。
首先我们需要计算出一个子过程的结果,必须知道神马。。
考虑xxx000-xxx999
如果xxx都要知道,显然就知道的太多了~~
实际显然上xxx有意义的只有它的数位和。。于是需要知道一个prefix_sum。。
同时在前面的过程中,可能给现在的过程留下了一些票的价值。。rest
同时要知道序列的长度,都是10的幂次,用10的多少幂表示。。。pow
那么prefix_sum,rest,pow就可以确定一个状态,
计算一下。。发现空间够的。。
求解这个状态可以枚举从0到9一个个进行下一位。。
为了继续过程的进行,状态需要返回两个结果,一个是过程中的答案cnt,一个是剩下来的票数rest。。
接下就明了了。。自己想吧。。orzoj上面也有标程可以参考。。

题目二: SPOJ 2421. Incrementing The Integer
https://www.spoj.pl/problems/ININT/
这个题目的大意就是给两个数a和b,然后对于a可以让它加上它的一个数位。
比如123可以加上1或2或3
要用最少的次数到达b,同时要求方案数(mod一个大数)
看到这个题目。。。数据范围很大。。没法暴力。。。
运用上面的办法。。。我们考虑xxx000-xxx999这样的区间。。
首先开始的位置不一定是xxx000,也可能是xxx008。。所以需要知道开始位置
结束位置也一样。。从991-999。。。
同时如果我们xxx全都知道,显然知道的太多了~~
仔细一想。。其实只需要知道0-9这10个数位有没有出现过。。
0有没有出现过毫无用处。。。所以只要知道1-9是否出现。。有2^9个状态。。
然后用同样的办法分解成10个自区间。。一个个瞎搞过去。。
就差不多了yeah。。。

CF#11 Problem E

凑数的文章。。请鄙视。。
这个题目http://www.codeforces.com/contest/11/problem/E
看了一会儿没有感觉到可做性。。囧。。。
。。。然后研究别人的代码。。发现可以二分答案。。。
首先把连续的L和R之间先添上X。。
然后设Dp[i]是前i个数中,个数-长度*答案的最大值同时当前是L。。。。这个玩意非常NB。。
如果Dp[N]>=0那么当前的答案就是可行的。。
然后考虑Dp[i]。。有两个操作可以用,一个是前面+个X,一种是不加X直接搞。。
可以更新掉。。
然后二分乱搞。。。

和谐社会模拟赛题解

////////////////////////////我是分割线///////////////////////////////////
////////////////////////////我是分割线///////////////////////////////////
////////////////////////////我是分割线///////////////////////////////////
////////////////////////////我是分割线///////////////////////////////////
////////////////////////////我是分割线///////////////////////////////////
////////////////////////////我是分割线///////////////////////////////////
////////////////////////////我是分割线///////////////////////////////////
////////////////////////////我是分割线///////////////////////////////////
////////////////////////////我是分割线///////////////////////////////////
////////////////////////////我是分割线///////////////////////////////////
////////////////////////////我是分割线///////////////////////////////////
o(∩∩)o…哈哈。。你被耍了。。没有题解

愿望群光棍节模拟赛题解。

似乎没人发的样子。。我写个吧囧。。。神犇请鄙视。。。
第一题似乎是IOI的原题的改编版。。只要看过今年IOI的题目应该都会的。。
首先二分答案X,我们需要判断能否有一个长度在L到R之间的奇数的序列中位数大于等于X。。
我们定义一个新序列Ci,若Ai>=x,Ci=1否则Ci=-1。。那么可以发现只要一个序列的C值和>=1。。
这个序列的中位数就大于X。。那么我们只需要算出C序列长度位在L到R之间的奇数的子序列的最大值就行了。。单调队列。。。
第二题首先可以发现每一位是独立的,那么对每一位都可以维护一个线段树进行经典的翻转和求和打标记等操作。。(实现的时候为了不TLE。。最好放在一起。。)
第三题网上有详细的题解。。我就不多说了。。是查分约束的题目。。。
第四题。。。题目的子树是子连通图的意思。。。
设两棵树为A和B
设Dp[a][b]为A中以a为根的子树,B中以b为根的子树同时a和b必须选的答案。
那么我们可以发现计算Dp[a][b]的过程就是给a的孩子跟b的孩子一一配对,他们配对的价值正是Dp的子结果。。
那么我们其实要做的就是求出最优匹配。。用KM或费用流就可以了。。(我居然不会KM。。临场写费用流。。。)

一点小总结吧..

最近做了N场模拟赛囧。。。
Orz6:
感觉还不错。。前3题都会了。。但是第四题始终不会做。。只好骗分。。。感觉发挥的还可以。。唯一要记住的就是第一没有看清范围。。居然用了long long的。。
USACO NOV:
题目还不错。。但是我傻叉到第二题的dp想了非常久。。因为我一开始就想到的是凸包优化的模型。然后没有发现其实单调队列就差不多了。。这提醒我一定要简单化问题啊。。不能想复杂T_T。。还有第一题算法很麻烦。写错一个就可能WA。。这样的题目一定要狂对拍+仔细检查啊。。。
愿望群:
题目显然不属于NOIP范畴这。。。第一题是IOI某题的加强版。。第二题时间卡的太囧了。。我看了题目没多想就用了16*NLogN的线段树。。被卡的只有30分。。标程是5*NLogN的。。太神了T_T。。因为异或的运算每一位是独立的。。一定要记住这一点啊。。第三题不会做。。本来可以骗个40分的。。结果因为我被第四题的一个傻叉编写错误卡住没来得及写。。第四题看了题目之后错误的以为是hash。。想了半天还是悲剧了。。。最后才发现是KM+DP。。但是写了半天之后发现居然忘了KM怎么写!!!这。。。算法不够熟练啊。。只好赶紧改成费用流。。不知道为神马只有80分。。
总结:
我就是个大弱菜。我怎么这么弱啊这么弱啊这么弱啊T_T。。。

和谐社会模拟赛。。正式通告

额。。下周就要比赛了。。做个正式的通告。。
首先比赛放到orzoj上了。。这个oj界面非常漂亮。。。
网址是http://www.orzoj.org/
我已经把上次模拟赛的题目放上去了。。这次的也一样吧。。
然后如果OJ挂掉的话(只是以防万一。。一般是不可能挂的。。)
交到WJMZBMR@gmail.com这个邮箱
同时我也会提前半小时放出比赛的pdf版本。。。并加密。。到时候公布密码
(gaoxin你破不掉的破不掉的破不掉的)。。
比赛会分成两部分。。第一部分是晚上6点到10点的模拟赛(题目有点xx。。。加长一小时好了。。)
第二部分是整个周末的娱乐赛。。。(题目非常xx。。一个周末好了。。)
然后是奖品的问题。。两部分分开评奖吧。。
第一部分前5名+10QB
第一部分AK +10QB
第二部分前5名+10QB
第二部分AK +30QB
可以重叠。如果你双AK又双前5就有60QB了嘻嘻。。。
审题人退散~~~~~不许抢钱
这。。为了让大家欢乐一点。。每题都会有点暴力分。。
全暴力估计也可以200分。。。

PS。题目描述精选:

LC同学在2011年的浙江省选中轻松虐爆了WJMZBMR,无压力进入省队并参加了NOI 2011,在1个小时之后,A光了所有题目的LC同学轻松的喝着茶,哼着小曲。
由于在信息学方面的杰出表现以及LC同学的父亲是伟大的LG同志。
LC同学轻松获得了2012年诺亚方舟的船票。并且得到了卖票员这一肥差。

GX同学由于风流倜傥玉树凌风貌似刘德华神似陈冠希酷似tourist,受到了众多小女生的倒追,从杭州排到北京又排回来。GX同学感到压力非常大,就请WJMZBMR同学帮助他把关。WJMZBMR把99.999%的女同学都赶走了。。还是有N个人。。

GYZ和CYX同学在IOI上见到了tourist,GYZ和CYX虎躯一震,散发王者之气,tourist纳头便拜,在秒杀了tourist之后,GYZ和CYX开始了IOI第一的争夺。。。。

JZP开发出了贾氏图表为了爱秒杀一切NPC问题之后,由于世人过于愚昧无知,没几个人学的会,JZP倍感神犇寂寞,于是又开发了一个简化1000000^1000000倍的贾氏小图表,然后大家还是不会。。再重复了1000000^100000之后。。终于有人能学会了。。JZP图标能O(1)解决以下问题。。。你能吗?

最近做的一些SGU题目。。。

384.Country
唬人题。。可以发现给定图肯定是一个root下面挂着N个三角形。。。
然后就随便搞搞了。。
369.Game
这个题目也差不多。。若两个点x和y分量中有一个是一样的,在他们间连一条边。。然后求连通分量。。
可以发现每个联通分量必然会变成一个矩形。。算出长和宽就OK了。。。
//我模拟赛题目的来源~~
389.Strange Planet
考虑每个位,结合3个串的话有8种可能性。。可以根据对称性之考虑4种。
就是
0   0   0   0
0   1   0   1
0   0   1   1
A1A2A3A4
。。。然后设Ai中有Bi结果串选了0.。
就可以列个方程。。
就可以发现B1确定了。。everything 确定了。。。
枚举B1就可以了。。。
394.空间点维护问题。。直接二维线段树硬搞。也可以离散掉之后用一维线段树搞。/
393.各种搜索。。。

Page 2 of 212