codeforces #305 div1 done

总算搞定了这一场比赛的题目,感觉收获蛮大

其中A,B,C都能通过自己的思考解决掉

D题思路好神,E题仔细想想也能想出来

以后坚持每两天或者一天做一场CF的div1的全套题目

除非有实在无法做出来的题目,每道题目还是都要写题解的

(我这算不算立flag?

本蒟蒻写的题解的链接:

A:http://www.cnblogs.com/joyouth/p/5352953.html

B:http://www.cnblogs.com/joyouth/p/5352932.html

C:http://www.cnblogs.com/joyouth/p/5352916.html

D:http://www.cnblogs.com/joyouth/p/5352888.html

E:http://www.cnblogs.com/joyouth/p/5352844.html

时间: 04-03

codeforces #305 div1 done的相关文章

codeforces #334 div1 603C Lieges of Legendre(博弈)

题目链接: codeforces 603C 题目大意: 有两个人做游戏,游戏规则如下: 有n堆石子,每次可以对一堆石子进行操作,如果当前石子是偶数,那么可以选择将这2*x个石子分成k堆石子数为x的石子堆,还有一种没有前提的操作是取走当前堆的一个石子,问先手赢还是后手赢,先手和后手都足够聪明的情况下. 题目分析: 首先对于这种组合游戏的题目,很容易想到利用SG函数来解.我们对于游戏的局势进行分类讨论: 当k是偶数的情况下, 我们可以知道如果要把一个偶数堆分成k个堆,相当于将局势转到一个新的组合游戏

codeforces #305 A Mike and Frog

挺简单的题目,但是有一堆恶心的边界 在刨去恶心的边界之后: 假定我们知道两边的循环节为b1,b2 其中h第一次到达目标的时间为a1,a2 又知道对于答案t t=a1+b1*t1=a2+b2*t2 不妨枚举t1,判断是否存在可行解即可 又因为LCM(b1,b2)就开始循环了 且b1*b2<=b1*mod 所以我们枚举t1的范围在[0,mod]即可 如果在这个范围内无解,则一定无解 #include<cstdio> #include<cstdlib> #include<cs

codeforces #305 B Mike and Feet

跟之前做过的51Nod的移数博弈是一样的QAQ 我们考虑每个数的贡献 定义其左边第一个比他小的数的位置为L 定义其右边第一个比他小的数的位置为R 这个可以用排序+链表 或者 单调队列 搞定 那么对于区间长度1->(R-L-1),该数都可以作为最小值出现 我们在R-L-1上打上标记,最后从后往前来更新答案即可 至此问题得解 #include<cstdio> #include<cstring> #include<iostream> #include<algori

codeforces #305 D Mike and Fish

正解貌似是大暴搜? 首先我们考虑这是一个二分图,建立网络流模型后很容易得出一个算法 S->行 容量为Num[X]/2; 行->列 容量为1 且要求(x,y)这个点存在 列->T 容量为Num[Y]/2 这样子跑网络流之后我们就得到了一组解 但是我们考虑输出方案 对于每一行,如果Num[X]为偶数,那么显然输出方案是正确的 但是如果Num[x]为奇数,多出的那个显然既有可能是红的也可能是蓝的 但关键是我们不能确定他是红的或者蓝的,因为他的状态也会影响对应的列 同样,列的考虑也是同理 所以我

codeforces#426(div1) B - The Bakery (线段树 + dp)

题意:把 n 个数划分成 m 段,要求每组数不相等的数的数量最大之和. 思路: dp方程 : dp[i][j] = max( dp[k][j-1] + v(k, i) );( j<=k<i , k = j, j+1, +...+ i-1) dp[i][j]表示第 i 个数分到第 j 段的最大值. v(k, i) 表示k~i中不同数的个数,此处用hash记录每个数上一次出现的位置,从上一次出现的位置到当前位置的 dp[i][j-1] 值均可+1. 此时时间复杂度 O(n*m*log(n)). 线

codeforces #313 div1 D

好神的题目! 首先我们运用pick定理A=S-B/2+1将要求的东西转化掉 之后分离变量,我们变成了求选取凸包面积的期望和求选取凸包在边界上的点的期望 我们先考虑求选取凸包面积的期望 如何计算凸多边形的面积,我们可以原点为划分点,计算凸包上的每个向量的叉积的和 如何计算凸包边界上的点,我们可以计算凸包上的每个向量上的点 那么我们可以考虑每个向量被计算的概率 显然p(i)-p(i+k)这个向量被计算的概率为(2^(n-k-1)-1)/(2^n-1-n-n*(n-1)/2)次 这样我们就可以O(n^

codeforces #310 div1 E

算得上是比较水的E题了吧,自己想了想写了写居然1A了 对于这道题,我们很容易想到对于原图的一个边双,定向后任意两点间一定可达 那么我们可以求出原图的边双并将每个边双缩成一个点 那么原图就变成了无环的无向图,也就是一片森林 之后我们考虑每个任务: 1.如果S和T处于一个边双里,显然是可行的 2.如果S和T处于两棵树中,显然不连通不可行 3.S和T处于一棵树中,那么S->lca的所有边都是向上的,lca->T的所有边的都是向下的 对于第三种情况,我们可以在S上打一个up标记,在T上打一个down标

codeforces #305 E Mike and friends

原问题可以转化为:给定第k个字符串,求它在L-R的字符串里作为子串出现了多少次 定义子串为字符串的某个前缀的某个后缀(废话) 等价于我们把一个字符串插入到trie里,其过程中每个经过的节点和其向上的fail链上的点都是该字符串的子串 又因为对于一条fail链,u向上能访问到v当前仅当u在v的子树内 那么原问题又变成了: 将L-R个字符串按照上述方法插入到trie中并将经过的节点的val值增加 求第k个字符串对应的单词节点在fail树上的子树的权值和 又因为查询的信息满足区间可减性,所以我们可以建

【codeforces #275(div1)】AB题解

A. Diverse Permutation time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Permutation p is an ordered set of integers p1,???p2,???...,???pn, consisting of n distinct positive integers not larg