论弱逼的自我修养——2014集训队CF试题泛做_cf253e-程序员宅基地

技术标签: 其他OJ  试题泛做  Codeforces  OIer刷题记录  自我修养  

为了增长姿势水平提高思考能力,我决定跟着神犇膜一膜2014的集训队作业;

似乎大多数是CF上的DE题,应该比较有含金量(然而博主是个div2连D都没做上过的**);

感觉不久就会弃坑吧,大家来猜猜窝能坚持几道题吧!


现在做了45/102


仿照各位神犇的风格写写一句话题解吧,如果我想详细写的话大概会扔个链接骗访问量吧= =;


2015/12/9 UPD:目前22题

最近开始复习文化课啦,回去补习文综理综啥的这边的效率基本是完了的;

总之能做一些就做一些吧。。。哪怕是都膜题解出也大概有点用吧(笑);


2015/12/21 UPD:目前28题

文化课暂且圆满滚粗,回来刷刷题啦~

不过感觉这个节奏药丸,并不能自己做出来题,智商果然还是掉没了(原来就没有哇!);


2015/12/24 UPD:目前36题

感觉这个节奏已完哦,似乎离上次UPD这些题都不能自己做出来。。

似乎也有好多不太难的题因为惯性就去看题解了= =,这可不好是吧。。。

我什么时候能达到会做几道题的程度呢[捂脸熊];


1.CF263E

先暴力算出来一个菱形,然后向旁边转移,转移就是加两个三角形减两个三角形,用三个前缀和算;


2.CF293B

首先n,m都不会太大,然后搜索;

用状压维护这个点不能选哪些颜色,并且对于没被输入固定过的颜色每个点只取最小的颜色,然后搜索出来的方案之后累加一个奇怪的组合数;


3.CF235E

WJMZBMR场的神题,rng_58的这个公式简直感人至深;

总之我还是膜题解搞了个公式。。

然后就枚举i反演一下照着题解搞一搞就可以了,时间复杂度O(n^2logn);


4.CF325E

找规律发现奇数一定无解,然后考虑从0倒着找,那么每次的前驱可能是(x+n)/2或者x/2,;

观察大样例发现优先找(x+n)/2靠谱,写一发A了;


5.CF260E

首先暴枚排列⑨!然后在前缀和二分找到四条直线,但是这四条直线仅仅满足了条件的一部分;

然后再利用可持久化线段树维护矩阵元素个数,check一下这些直线是否合法就可以了;


6.CF325D

先将矩形复制一次,然后就是查询复制之后的点是否与原点连通,用并查集维护即可;


7.CF335E

http://blog.csdn.net/ww140142/article/details/50109689


8.CF360E

首先可以利用任意次操作拼出a的k*gcd(b1,b2...bm,p-1)幂次的数(k为任意非负整数);

然后令ai=g^ri,g为mod p 意义下的原根,那么原问题转化成了求k*ri*gcd(b1,b2...bm,p-1)的集合大小;

DP一下:

累加所有的f[i]即为答案;


9.CF339E

似乎有一种神奇的构造姿势能做到O(n),不过看不懂我选择爆搜。。每次找出一段abs(a[l]-a[r+1])==1||abs(a[r]-a[l-1])==1的区间反转然后递归搜索就可以了;

原因就是任何方案都一定将连在一起的元素又接回一起去,这样可以剪枝掉很多情况;


10.CF286E

http://blog.csdn.net/ww140142/article/details/50128923


11.CF332D

因为数据保证这样的点只有一个,那么对每条边计算贡献就可以了;

对一个度数为D点的某条权值为val的边,贡献是C[D-1][k-1]*val,最后一起除C[n][k],用double型存储精度似乎就够了;


12.CF335D

预处理格子的前缀和,以及在矩形内部小线段的前缀和,对于一个正方形只要判断它是否被填满,并且边界上没有矩形内部的小线段即可;

枚举每一个矩形的左下角,枚举长度然后O(1)判断这个正方形,注意枚举过程中的剪枝;


13.CF261D

首先让t=min(t,n,bmax),因为答案最大也不会超过min(n,bmax),然后整个序列长度就不会超过2*10^7了,枚举每一个数然后DP,f[i]表示DP到当前位置最后一个数字不超过i的最长长度;

显然f[i]单调递增,于是每次更新只是更新连续的一段,又因为每次f[i]值至少+1,所以更新次数不会很大,时间复杂度就有保证了;

(说起来似乎还有一道用倍增floyd解决不下降子序列的CF题吧。。很久以前坑下的一道题还没填。。)


14.CF235C

http://blog.csdn.net/ww140142/article/details/50151235


15.CF311E

最小割模型,考虑将每个点划分到S集为公,到T集为母,那么按此连一条流量为这个狗手术代价的边;

对每个人新建一个点,如果他希望将狗变公,从S到这个点连一条流量wi+这个人是否是好友*g的边,并且向每个他希望的狗连INF的边;

将所有的wi加起来减去最小割即为答案;


16.CF306D

n<=4的时候无解,其他情况因为角度已经确定,我们只要构造一个离正n边形差一点的图形即可;

调整长度,第i条边的长度为500+0.01i,最后两条边求交就是最后一个点啦;

(过不去的时候调调参数是很机智的选择)(学习了一下python输出图像的姿势)


17.CF249E

公式题,转化成矩形前缀和之后把前面的小正方形和后面的剩下的东西搞一搞就行了;

然而这题取模啥的比较变态。。所以我选择python被卡常,然后膜了一下杜教的公式A了= =;


18.CF295D

题意很难的题。。。我真心看不懂题意去看了题解= =然后发现就是挖一个洞。。

然后DP一下就好了,f[i][j]为高度为i长度从j开始的半个洞的方案数,sum1[i][j]为f[i]数组对第二维的前缀和,sum2[i][j]为f[i]数组对第二维*j的前缀和;

利用前缀和转移再统计一下就可以了,两个前缀和主要是为了解决上一层长度k比这一层长度j小,所以方案要乘一个(j-k+1);


19.CF264E

这个东西感觉并不能用数据结构优雅的维护,但是题中有两个重要的条件xi,hi<=10,提示我们可以暴力搞一搞;

于是反向求LIS,每次把最下面/最左面的十个拿出来暴力重构就可以了,开两个线段树维护,时间复杂度O(nlogn*10);


20.CF286D

http://blog.csdn.net/ww140142/article/details/50173971


21.CF258D

考虑这个状态:f[i][j]表示pi>pj的概率,初始值扫一遍,每次操作交换x,y,那么就是f[i][x]=f[i][y]=(f[i][x]+f[i][y])/2,f[x][i]=f[y][i]=(f[x][i]+f[y][i])/2,f[x][y]=f[y][x]=0.5;

这个可以O(nm)的算出来,算出来之后根据定义,∑f[i][j]  (i<j)就是答案了;


22.CF273D

将问题转化一下,变成染一个区域,使其左边界和右边界都是凸的,按照vfk的题解,我们可以像判定合法性一样,用一条线从上往下扫,然后DP;

f[i][l][r][j][k]表示DP到第i行,这行染黑的区间是[l,r],j=左边界是否下降过,k=右边界是否下降过,这个方程可以用前缀和优化,时间复杂度就是O(n^3)的了;


23.CF283E

http://blog.csdn.net/ww140142/article/details/50241077


24.CF305D

首先这个图中不可以存在x连向x+1或x+k+1以外的边,并且对于所有的x<n都有x连向x+1;

那么考虑能放多少x+k+1的边,然后记录所有这样边的前缀和搞一搞就好了;


25.CF354D

考虑如果选了一个高度h的金字塔,那么一定满足h*(h+1)/2+2<3*m,因此选的高度一定小于O(√m);

那么直接在高度较低的地方DP就可以了,具体方法我去膜了ydc的代码感受一下啦。。。


26.CF261E

以前NOIP模拟赛的时候做过,就是发现能组成的数不超过3*10^5个,于是搜出这些数;

然后枚举右侧加的次数i,计算每个数最少用多少次乘法算出,f[x]+i<=n的话就可以被表示出,时间复杂度O(3*10^5 * n);

有点卡常。。


27.CF253E

首先这东西可以二分。。然后就是模拟啦。。。复杂度O(nlog^2n)不虚哦;

注意这个权值不可以重复,所以我预先处理了所有的可选值,还有二分之后要再调用一次check函数,算一遍任务完成的时间;

别忘了是读取文件哦;


28.CF309E

二分+贪心,然而我并不会证明所以就说一下做法吧:二分之后,我们考虑如何构造一组解或判断不存在;

定义一个数组lim[x]表示x这个区间最晚在排列的什么位置,这个每次暴力维护,然后对于要填的每个位置,统计lim小于等于某个数的区间数;

找到一个最小的t满足恰好能将这些区间一一对应前t个排列的位置,然后在其中找一个右端点最小的放在i处就可以了,如果放不下就是无解,时间复杂度O(n^2logn);


29.CF316E3

有一个神奇的式子呢:

fib[0]=0,fib[1]=1,以下递推(和题中不一样),证明脑补吧。。

然后根据这个式子,就得到了线段树结点信息合并的方法,预处理fib数列及其前缀和,在线段树上做修改就可以了;


30.CF243C

搞一个离散化然后暴力就可以了,复杂度O(n^2);

乱写然后就A啦。。然而调代码的时候output和answer看反调了半天= =;


31.CF316G3

以前学习后缀自动机的时候研究了一下这道题然后跑了,现在滚回来把它搞完;

就是将所有的串建立一个广义后缀自动机,对于每个后缀结点记录它在每个串中的出现次数;

然后扫一遍所有的点,将满足条件的并且在原串中的子串累加答案就可以了;


32.CF256D

考虑DP,设f[i][j][k]表示前i个数已经用了j个人,并且其中k个人一定说谎的方案数;

转移枚举多少人说这个数:有f[i+1][j+l][k+(i+1==l?0:l)]+=f[i][j][k]*C[j+l][l],C[n][m]表示组合数;

因为O(n^4)过不去所以后面的打表= =,这思路什么鬼啊。。。


33.CF303D

结论题。。看起来有点像数位DP之类的东西结果居然是数论?

总之当长度n>=2时,进制b下有且仅有一个循环数的充要条件是n+1是质数,且b是n+1的原根(证明在vfk的集训队作业里);

然后直接暴力求原根就可以了,注意一些边界情况如n==1,x==2什么的= =;


34.CF338D

首先考虑这个数列会出现在第几行,设数列的LCM为h,那么一定会出现在k*h行上,而实际上,h行的循环节一定是在k*h行循环节的子串,所以我们可以确定它出现在h行;

考虑列的话,设从第l列开始可以列出方程l=1-i (mod a[i])    (1<=i<=n),求解这个方程组即可,同样是取最小的l;

那之后暴力判断即可,时间复杂度O(nlogn),注意l可能解出等于0的情况,这时应加一个LCM调整;


35.CF266E

将公式二项式展开之后用6个线段树分别维护即可,修改可以预处理前缀和来完成,时间复杂度O(6nlogn);


36.CF332E

考虑枚举那个01串中有多少1,这样就确定了s串中每隔几个字符是受一个1控制的,然后贪心;

从后往前枚举01串,如果这一位填1可以就填1,否则填0,之后更新答案的最小字典序;

好神的做法啊。。。时间复杂度大概是O(k^2*|s|*logk)吧。。然而跑的飞快哦。。


37.CF273E

首先转化博弈模型,因为实际上胜负只与线段长度有关,所以可以定义SG(x)为长度为x线段的SG函数值,有转移SG(x)=mex(SG(x/3),SG(x-x/3));

因为x很大,我们不能直接推导,但是发现它的值域只有{0,1,2},并且打表后发现相同的SG值连成了一大段(在10^9内只有100多段),那么考虑对于每一段处理就可以了;

利用SG函数预处理cnt[x]为SG值为x的线段个数,然后就是一个DP,f[i][j]表示前i个线段异或和为j的方案数,答案就是f[n][1]+f[n][2]+f[n][3];


38.CF333C

构造题,考虑枚举左面的四个数,然后搜索用加减乘能组成什么数,再用右面的四个来凑;

注意可能有多种方案凑出同一个数,不要重复了,因为方案实际上很多,所以不必搜全所有的方案,随便搞搞就能AC了;


39.CF240F

考虑一个区间最小字典序的回文串,我们只需要知道区间内字符个数就能构造出来;

因为字符集很小,所以可以用线段树维护区间某字符的个数,然后一个回文串就能转化成两段单调区间来处理了;

时间复杂度O(nlogn*26);


40.CF305E

考虑转化一下这个游戏,我们将左右字符相同的点视为黑点,对于每个黑点的连通块是一个完全独立的游戏;

那么每次操作就变成了选择一个黑点,将它和左右三个点染白,这样就得到了SG函数的O(n^2)递推式;

求出SG函数之后将所有游戏加起来就能得到是否胜利了,枚举第一步的走法然后验证也是O(n^2)的;


41.CF235D

考虑树上两个点对答案的贡献,如果一个点被分治时另一个点计入了答案,那么这个概率相当于是这两个点路径上所有的点都没有被选中,概率为1/dis,因为这样会对Totalval作出1的贡献所以期望也为1/dis;

转化的到基环树上也是一样的,只是概率要用一个容斥,1/dis1+1/dis2+1/dis1和dis2总点数就可以了;


42.CF301C

诡异的一道题。。。考虑一种对所有数字都通用的算法;

一图流:



43.CF309D

论CF的量子计算机与CCF老爷机的差距;

O(n^2)卡常数,枚举两个点,利用单调性得到另一个点的取值范围;

注意判断钝角时用浮点会TLE,要利用余弦定理直接整型来判断;


44.CF325C

对于最小的可能,考虑每一个不会产出新怪兽的怪兽,利用钻石数的单调性来跑dij转移,转移不到的即是-1;

那么我们已经知道哪些是停不下来的了,对于最大的答案,就直接记忆化搜索,如果不是-1并且出现了环的话,那就是-2了;


45.CF316D3

这显然是一个置换计数问题,考虑其中的一个循环,其中只能有两个扔一次的人存在;

考虑一次的人,我们先求出有cnt1个一次的人的分组方案数,递推为g[i]=g[i-1]+(i-1)*g[i-2],要么自己一组,要么和(i-1)个人中的一个一组;

考虑加入一个两次的人,他可能和一次的人一组,或者和之前两次的人或者自己一组,那么插入第i个人给答案乘(cnt1+i)就可以了;


弃疗*2

CF317E这个构造。。

先判掉无解,然后就是一直向影子的最短路走,然后可以发现最终一定能走到无界区域或者重合;

既然走到了无界区域然后绕圈搞一搞就能将两个人蹭到一起了;

说着容易然而调了两天调不出来就弃疗吧先= =。。


CF280E

边界有点蛋疼了。。。理解了一下然后写了一发调不出来啊。。

这个证明凸函数的思路确实很有意思嘛。。


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/ww140142/article/details/50060407

智能推荐

分布式光纤传感器的全球与中国市场2022-2028年:技术、参与者、趋势、市场规模及占有率研究报告_预计2026年中国分布式传感器市场规模有多大-程序员宅基地

文章浏览阅读3.2k次。本文研究全球与中国市场分布式光纤传感器的发展现状及未来发展趋势,分别从生产和消费的角度分析分布式光纤传感器的主要生产地区、主要消费地区以及主要的生产商。重点分析全球与中国市场的主要厂商产品特点、产品规格、不同规格产品的价格、产量、产值及全球和中国市场主要生产商的市场份额。主要生产商包括:FISO TechnologiesBrugg KabelSensor HighwayOmnisensAFL GlobalQinetiQ GroupLockheed MartinOSENSA Innovati_预计2026年中国分布式传感器市场规模有多大

07_08 常用组合逻辑电路结构——为IC设计的延时估计铺垫_基4布斯算法代码-程序员宅基地

文章浏览阅读1.1k次,点赞2次,收藏12次。常用组合逻辑电路结构——为IC设计的延时估计铺垫学习目的:估计模块间的delay,确保写的代码的timing 综合能给到多少HZ,以满足需求!_基4布斯算法代码

OpenAI Manager助手(基于SpringBoot和Vue)_chatgpt网页版-程序员宅基地

文章浏览阅读3.3k次,点赞3次,收藏5次。OpenAI Manager助手(基于SpringBoot和Vue)_chatgpt网页版

关于美国计算机奥赛USACO,你想知道的都在这_usaco可以多次提交吗-程序员宅基地

文章浏览阅读2.2k次。USACO自1992年举办,到目前为止已经举办了27届,目的是为了帮助美国信息学国家队选拔IOI的队员,目前逐渐发展为全球热门的线上赛事,成为美国大学申请条件下,含金量相当高的官方竞赛。USACO的比赛成绩可以助力计算机专业留学,越来越多的学生进入了康奈尔,麻省理工,普林斯顿,哈佛和耶鲁等大学,这些同学的共同点是他们都参加了美国计算机科学竞赛(USACO),并且取得过非常好的成绩。适合参赛人群USACO适合国内在读学生有意向申请美国大学的或者想锻炼自己编程能力的同学,高三学生也可以参加12月的第_usaco可以多次提交吗

MySQL存储过程和自定义函数_mysql自定义函数和存储过程-程序员宅基地

文章浏览阅读394次。1.1 存储程序1.2 创建存储过程1.3 创建自定义函数1.3.1 示例1.4 自定义函数和存储过程的区别1.5 变量的使用1.6 定义条件和处理程序1.6.1 定义条件1.6.1.1 示例1.6.2 定义处理程序1.6.2.1 示例1.7 光标的使用1.7.1 声明光标1.7.2 打开光标1.7.3 使用光标1.7.4 关闭光标1.8 流程控制的使用1.8.1 IF语句1.8.2 CASE语句1.8.3 LOOP语句1.8.4 LEAVE语句1.8.5 ITERATE语句1.8.6 REPEAT语句。_mysql自定义函数和存储过程

半导体基础知识与PN结_本征半导体电流为0-程序员宅基地

文章浏览阅读188次。半导体二极管——集成电路最小组成单元。_本征半导体电流为0

随便推点

【Unity3d Shader】水面和岩浆效果_unity 岩浆shader-程序员宅基地

文章浏览阅读2.8k次,点赞3次,收藏18次。游戏水面特效实现方式太多。咱们这边介绍的是一最简单的UV动画(无顶点位移),整个mesh由4个顶点构成。实现了水面效果(左图),不动代码稍微修改下参数和贴图可以实现岩浆效果(右图)。有要思路是1,uv按时间去做正弦波移动2,在1的基础上加个凹凸图混合uv3,在1、2的基础上加个水流方向4,加上对雾效的支持,如没必要请自行删除雾效代码(把包含fog的几行代码删除)S..._unity 岩浆shader

广义线性模型——Logistic回归模型(1)_广义线性回归模型-程序员宅基地

文章浏览阅读5k次。广义线性模型是线性模型的扩展,它通过连接函数建立响应变量的数学期望值与线性组合的预测变量之间的关系。广义线性模型拟合的形式为:其中g(μY)是条件均值的函数(称为连接函数)。另外,你可放松Y为正态分布的假设,改为Y 服从指数分布族中的一种分布即可。设定好连接函数和概率分布后,便可以通过最大似然估计的多次迭代推导出各参数值。在大部分情况下,线性模型就可以通过一系列连续型或类别型预测变量来预测正态分布的响应变量的工作。但是,有时候我们要进行非正态因变量的分析,例如:(1)类别型.._广义线性回归模型

HTML+CSS大作业 环境网页设计与实现(垃圾分类) web前端开发技术 web课程设计 网页规划与设计_垃圾分类网页设计目标怎么写-程序员宅基地

文章浏览阅读69次。环境保护、 保护地球、 校园环保、垃圾分类、绿色家园、等网站的设计与制作。 总结了一些学生网页制作的经验:一般的网页需要融入以下知识点:div+css布局、浮动、定位、高级css、表格、表单及验证、js轮播图、音频 视频 Flash的应用、ul li、下拉导航栏、鼠标划过效果等知识点,网页的风格主题也很全面:如爱好、风景、校园、美食、动漫、游戏、咖啡、音乐、家乡、电影、名人、商城以及个人主页等主题,学生、新手可参考下方页面的布局和设计和HTML源码(有用点赞△) 一套A+的网_垃圾分类网页设计目标怎么写

C# .Net 发布后,把dll全部放在一个文件夹中,让软件目录更整洁_.net dll 全局目录-程序员宅基地

文章浏览阅读614次,点赞7次,收藏11次。之前找到一个修改 exe 中 DLL地址 的方法, 不太好使,虽然能正确启动, 但无法改变 exe 的工作目录,这就影响了.Net 中很多获取 exe 执行目录来拼接的地址 ( 相对路径 ),比如 wwwroot 和 代码中相对目录还有一些复制到目录的普通文件 等等,它们的地址都会指向原来 exe 的目录, 而不是自定义的 “lib” 目录,根本原因就是没有修改 exe 的工作目录这次来搞一个启动程序,把 .net 的所有东西都放在一个文件夹,在文件夹同级的目录制作一个 exe._.net dll 全局目录

BRIEF特征点描述算法_breif description calculation 特征点-程序员宅基地

文章浏览阅读1.5k次。本文为转载,原博客地址:http://blog.csdn.net/hujingshuang/article/details/46910259简介 BRIEF是2010年的一篇名为《BRIEF:Binary Robust Independent Elementary Features》的文章中提出,BRIEF是对已检测到的特征点进行描述,它是一种二进制编码的描述子,摈弃了利用区域灰度..._breif description calculation 特征点

房屋租赁管理系统的设计和实现,SpringBoot计算机毕业设计论文_基于spring boot的房屋租赁系统论文-程序员宅基地

文章浏览阅读4.1k次,点赞21次,收藏79次。本文是《基于SpringBoot的房屋租赁管理系统》的配套原创说明文档,可以给应届毕业生提供格式撰写参考,也可以给开发类似系统的朋友们提供功能业务设计思路。_基于spring boot的房屋租赁系统论文