技术标签: 其他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
边界有点蛋疼了。。。理解了一下然后写了一发调不出来啊。。
这个证明凸函数的思路确实很有意思嘛。。
文章浏览阅读118次。通过正确连接硬件、进行PLC设置、编写PLC程序并上传到PLC,你可以成功将杰佛伦Profinet位移传感器与S PLC进行连接和组态。根据实际情况,你可能需要调整上述步骤中的细节和代码,以适应你所使用的具体设备和软件环境。在实际应用中,你需要根据传感器的通信协议和PLC编程语言进行适当的编码。完成PLC程序的编写后,将其上传到S PLC。确保PLC和计算机通过适当的通信接口连接,并使用PLC编程软件将程序上传到PLC。在PLC工程中创建一个新的程序块,并编写适当的逻辑来处理从传感器接收的数据。_profinet位移传感器
文章浏览阅读1.1k次。在现实生活中,一对一关联关系是十分常见的。例如,一个人只能有一个身份证,同时一个身份证也只会对应一个人,它们之间的关系模型图,如图1所示。图1 人与身份证的关联关系那么使用MyBatis是怎么处理图1中的这种一对一关联关系的呢?在元素中,包含了一个子元素,MyBatis就是通过该元素来处理一对一关联关系的。在元素中,通常可以配置以下属性:● property:指定映射到的实体类对象属性,与表字段一一对应;● column:指定表中对应的字段;● javaType:指定映射到实体对象属性的类型;_对个人和身份证这种一对一关联关系,来演示mybatis的关联映射查询的使用;
文章浏览阅读203次。我在列表中的N(例如3个)元素之后添加换行符时遇到问题:我试图像这个Q/A解决方案那样做(使用:nth-child(3):after { content:"\A"; white-space:pre; })告诉但是id didn对我有用。这是我的css.lk-color-chooser {list-style-type: none;padding-left: 0;}.lk-color-chooser..._虎扑网页版 换行
文章浏览阅读121次。Linux系统中终端设备种类终端是一种字符型设备,有多种类型,通常使用tty来简称各种类型的终端设备。终端特殊设备文件一般有以下几种: 串行端口终端(/dev/ttySn) ,伪终端(/dev/pty/),控制终端(/dev/tty) ,控制台终端(/dev/ttyn, /dev/console)。1.串行端口终端(Serial Port Terminal)是使用计算机串行..._unsigned charx_char;/* xon/xoff char */
文章浏览阅读5.1k次。问题:在低版本的安卓手机中使用window.location.href跳转失效解决思路1:分析:在跳转链接后面添加时间戳,因为考虑到是低版本可能存在缓存的问题所以采用在跳转链接后面添加动态的参数时间戳来刷新缓存的数据// 在跳转链接后面添加时间戳,因为考虑到是低版本可能存在缓存的问题所以采用在跳转链接后面添加动态的参数时间戳来刷新缓存的数据window.location.href = url+'?time='+((new Date()).getTime());解决思路2:分析: 在采用上面的方_安卓手机无法在吃触发 window.location.href
文章浏览阅读1.3k次。本次搭建环境 svn + Jenkins + Docker + git + Rancher + Maven服务器配置,根据个人爱好分配服务器,只需要拓扑图中相邻的两个服务器保证通信即可,也可以放在一台服务器中上拓扑图跟着我的思路来一遍: 1、开发写代码,上传到svn服务器上,相信这个很容易理解。 2、使用Jenkins 拉取svn 代码,并结合maven插件转换成jar ..._项目部署运维文档怎么写
文章浏览阅读2.7k次。技术特征:1.一种批量提取基因组基因信息并翻译比对分析序列的方法,其特征在于,将某一物种的转录本id或者基因id,依据供试基因组cds文件、蛋白质文件、gff文件和染色体fasta文件信息,通过6个perl脚本程序,实现目标转录本或基因在基因组上的位置、长度、正反义链结构信息的提取,并在染色体fasta文件上提取该转录本或基因的cds或基因序列,在基因组蛋白文件上提取该转录本的蛋白质序列;最后对所..._linux 翻译cds
文章浏览阅读1w次,点赞23次,收藏57次。ServiceMesh和Serverless转载声明本文大量内容系转载自以下文章,有删改,并参考其他文档资料加入了一些内容:微服务 | 我为啥不看好 ServiceMesh作者:芋道源码出处:CSDN1 前言今年,ServiceMesh(服务网格)概念在社区里头非常火,有人提出2018年是ServiceMesh年,还有人提出ServiceMesh是下一代的微服务架构基础。作为架构师,如果你现在还不了解ServiceMesh的话,是否感觉有点落伍了?那么到底什么是ServiceMesh?它_servermesh和serverless
文章浏览阅读1.8k次。做个记录,备查。原文:http://blog.csdn.net/xiaojiao661025/article/details/43449795http://www.xuebuyuan.com/1707596.html1、下载SuperLU文件:这里下载的是 Version 4.12、生成库文件:生成SuperL_superlu6.0.0
文章浏览阅读75次。使用Jquery的DataTable进行数据表处理非常方便,常遇到的一个问题就是删除一行后页面必须进行更新,需要注意的方法如下:前台页面中初始化table时注意:var table = $('#sorting-advanced');table.dataTable({'bServerSide': true,'sAjaxSource': 'servlet/UserList','bProcessing'..._fnpagechange(1, true)
文章浏览阅读1.1w次,点赞8次,收藏70次。快速开发:Spring Boot提供了一系列的开箱即用的功能和特性,使得开发人员可以快速构建和部署应用程序。简化配置:Spring Boot自动配置了许多常见的配置,如数据源、Web服务器、安全等等,这样开发人员可以专注于业务逻辑的实现,而不是配置。易于部署:Spring Boot可以将应用程序打包成可执行的JAR或WAR文件,这样可以方便地部署到任何支持Java的平台上。易于测试:Spring Boot提供了一系列的测试工具和框架,可以方便地进行单元测试、集成测试和端到端测试。_springboot连接数据库
文章浏览阅读9.3k次,点赞11次,收藏50次。目录前言第一个flask程序GET类接口POST类接口PUT类接口前言看到这篇文章我就默认你已经在你的电脑上使用 pipenv搭建好了虚拟环境并且设置好了开发环境(pycharm)。如果没有,请参照这篇文章。文章传送门第一个flask程序from flask import Flask #导入Flask类app = Flask(__name__) # 实例化[email protected]('/') # 使用路由,给 hello 函数定义一个路由,然后游览器通过http 请求得到相对应的数_python flask post