9
25
2015
0

集训队作业的记录

并不知道自己能做多少有多少写多少咯

【EASYEX】 2015July

    感觉这道题目是我在CC里面看到最水的hard?

    答案可以看成一些变量和的F-阶乘的积,这样很容易想到一个等价类,那么答案就是∑P(n,r)*[r]f(x)/k^r。

    对于每一个变量和的F-阶乘内我们要选一些数,这样我们可以定义way(i,j)表示选i个变量其中至少一个变量在第j轮,way可以通过递推得到。

    这样就是求一个L-阶乘的生成函数用快速幂+FFT就可以完成复杂度是O(n^2+T*nlog^2n)

Category: 未分类 | Tags:
6
18
2015
0

弱×的自我修养——BZOJ乱做计划

都是因为现在是期末,我都没法填坑辣...所以我又来开一个坑,主要来填下以前想要做的题目的坑

 

//upd 7.5 跟朋友和他的女朋友出去玩了一下整个人都不太好,推了几天gal妹子,才来级继续打题目

//好像50题也到了...懒得记录了...先坑掉吧

【BZOJ2219】数论之神 其实并不难,学过数学应该都很好做。对[tex]B[/tex]进行分类,用些简单数论姿势就能做了。

【BZOJ4173】数学 挺好玩...感觉应该是高考难度吧...所以就写下答案[tex]\varphi(n)\varphi(m)mn[/tex]。

【BZOJ3309】DZY loves Math 化简后就是[tex]\sum_{D} \lfloor \frac{a}{D}\rfloor\lfloor \frac{b}{D}\rfloor\sum_{d|D}f(d)\miu(\frac{D}{d})[/tex],后面是个卷积可以在[tex]O(nlogn)[/tex]解决,由[tex]f[/tex]性质可以知道后面的卷积只有[tex]1,0,-1[/tex]三种值。

【BZOJ3851】2048 显然的不是[tex]2^{i}[/tex]的数是不用考虑的,由于所有集合是好求的,那么来求不能组成的集合,考虑[tex]dp(i,j)[/tex]表示[tex]2^{0},..,2^{i}[/tex]组成[tex][j*2^{i},(j+1)*2^{i})[/tex]的方案数,那么答案[tex]dp(11,0)[/tex]就是答案咯。

【BZOJ3852】Area of Mushroom 显然的我们只需要v_max那些点,之后就是一个Voronoi图,那么可以知道无穷区域的就是凸包上的点,注意边界特判。

【BZOJ4143】The Lawyer 求下最大最小。

【BZOJ4144】Petrol 对每个点求离它最近的距离,然后就是一个瓶颈树求个MST就可以了哦,至于查询在线离线可以。

【BZOJ4145】The Prices 暴力DP。

【BZOJ4146】Divisors 按照筛法[tex]O(nlogn)[/tex]做就可以了。

【BZOJ3211】花神游离各国 想到sqrt搞5次肯定变成1,直接上线段树跑到最底层就好了。

【BZOJ4152】The Captain 考虑以|x1-x2|为答案就是排序下,那么只有相邻肯定提供答案,这样就是一个4n条边的最短路。

【BZOJ4034】T2 想了一会哦,肯定上dfs序,线段树部分维护两个量就可以了。

【BZOJ4149】Global Warming 一个傻逼题居然这么点人A了。用线段树的话,我们很容易想到枚举最小值那么就只用考虑在前后查找最大值来扩宽,其中有点细节需要想想。然而我看到nbdhhzh又短又快,就膜了一番告诉我能用单调队列+二分做,可以参考http://nbdhhzh.is-programmer.com/posts/97542.html

【BZOJ4147】Euclidean Nim 很好玩的一道博弈题目哦。

    对于[tex]up+vq=n[/tex]存在[tex](u,v)[/tex]整数解仅当[tex](p,q)|n[/tex],这样就能判断游戏是否会停止了。

    ①如果[tex]p=q[/tex],那么先手必胜。②如果[tex]p>q,n<p[/tex],因为先手肯定是采取[tex]+p[/tex]操作,那么经过后手的石子数必定小于p,又因为[tex](p,q)=1[/tex]故肯定有解,那么就是先手败。③如果[tex]p>q,n>=p[/tex],那么先手必须操作成[tex]n\mod\ p[/tex],且需要满足[tex]n\mod\ p<q[/tex],否则就变成上面的状态了,那么经过先后操作石子变成了[tex]x-p+q[/tex]。这样,就能知道先手胜条件是[tex]n\mod\ p<q,p-q|n\mod\ p[/tex]。④如果[tex]p<q,n<p[/tex]可以同理转化成上面的样子。⑤最后一种[tex]p<q,n>=p[/tex]则是先手胜。

【BZOJ4033】T1 不会做噢,考虑dp[u][k]表示以u为根且染k个子树内贡献和延伸出去的那条边对整体的贡献,这样就能够转移了,仔细分析复杂度是[tex]O(n^{2})[/tex]。

【BZOJ4151】The Cave 我们可以选个点[tex]p[/tex],考虑它离正确解的距离就是[tex]max{0,\frac{dist(p,a[i])+dist(p,b[i])-d[i]}{2}[/tex],这样得到就是最紧的限制,那么就只用找出最紧限制下离p的最近点,这个点就是最可能是答案的点,那么就只用检验这个点即可。

【BZOJ4001】概率论 打一发表就能发现[tex]\frac{n^{2}+n}{4n-2}[/tex]。

【BZOJ3856】Monster 仔细讨论哦。

【BZOJ2599】Race 点分治就可以了。

【BZOJ4104&2408】 同一道题目,thusc居然也会出原题哦。找一发规律可以发现,对于一个串[tex]s[/tex],按规则做好最后一列和最前面一列会有一个环的关系,可以发现0一定是在最后面,所以走走环就好了。

【BZOJ4059】Non-boring sequence 先预处理出每个点到两侧的最远距离,然后递归判断,复杂度是[tex]T(n)=max(T(k)+T(n-k)+2\times min(k,n-k))=O(nlogn)[/tex]。

【BZOJ4052】Magical GCD 已经被前人玩烂的idea。

【BZOJ3884】上帝与集合的正确用法 http://blog.csdn.net/popoqqq/article/details/43951401

【BZOJ3531】旅行 树链剖分,每个LL教开一个线段树

【BZOJ4058】Who wants to live foever 可以发现如果是全0肯定DIES了,如果[tex]n[/tex]为偶数则肯定LIVES。那么只用考虑奇数。我们对于一个S操作两次可以发现,它们的答案只跟S的要么奇数位有关、要么偶数位有关,那么每次就能分治为原序列的一半,只有当两个序列都DIES整个序列才DIES。

【BZOJ1576】Travel 因为有题目给定限制,所以最短路树是一定的。考虑扔进去一条[tex](u,v)[/tex],我们只有可能用[tex]d[u]+d[v]+dist(u,v)[/tex]更新[tex]u->v[/tex]的这个环,其中[tex]lca(u,v)[/tex]不进行更新,因为不会这样走。这样用树链剖分维护下即可

Category: 未分类 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com