• Codeforces Round #383 Div 1题解

    Codeforces Round #383 Div 1题解

    第一次打Div1,感觉还是挺难的。。把基础题打完就日常划水了。。。。A.Arpa'sloudOwfandMehrdad'sevilplan题目大意:有n个人,每个人有一个后继,求在进行多少次传递后第i个人跟第j个人对话的同时,第j个人也能跟第i个人对话(允许自己与自己对话)。$1\leqn\leq100$这题意花了我好多时间啊。。说白了就是要找环咯,把每条环求出来然后看环长度是不是偶数,是的话就除2,然后就个最大公约数就行了。Code:[crayon-5bc76325f2...

  • BZOJ 4089:[Sdoi2015]graft(SDOI 2015 Round 2 Day 2)

    BZOJ 4089:[Sdoi2015]graft(SDOI 2015 Round 2 Day 2)

    别人家的神选系列,我只会做这道题QAQ题目描述:给定一颗树,加上k条边,将n个点染色,相邻两点不同,记颜色为i的又ti个,求$$\frac{\sum_{i=1}^{n}\frac{ti}{i}}{1+p\sum_{i=1}^{n}iti}$$(擦擦擦我今天才知道能用Tex公式QAQ害得我以前写的好辛苦QAQ)的最大值。(k<=2)这是分数规划嘛,那么我们就可以二分答案x。然后我们每种颜色的值就变为$\frac{1}{i}-pxi$啦,然后就可以直接上DP啦。dp我们每个点记录3个值:...

    02015年6月18日830二分,树形动规,老的存档
  • Codeforce 水题报告(2)

    Codeforce 水题报告(2)

    又水了一发Codeforce,这次继续发发题解顺便给自己PKUSC攒攒人品吧CodeForces438C:TheChildandPolygon:描述:给出一个多边形,求三角剖分的方案数(n<=200)。首先很明显可能是区间dp,我们可以记f[i][j]为从i到j的这个多边形的三角剖分数,那么f[i][j]=f[i][k]f[j][k](i,j,k是否为1个合格的三角形)Code:[crayon-5bc76325f29a7745537560/]CodeForces438D:TheChildandSequence描述:给一个序列,要求支持区...