Codeforces题目泛做计划

找了一些比较水的cf上的题目,然而又不想整套整套的的写了,于是一些散的cf上的题目就放在这里了。

现在做了几题:

30

好弱啊、、

427B.Prison Transfer

题意:给定长度为n的一个序列,和c,t两个数字。问你有多少个连续的长度为c的子串,且序列中最大数不超过t。

题解:直接扫一遍。

475B.Strongly Connected City

给出n条水平的单向道路,m条竖直的单向道路。问形成的n*m个节点是否都可以互相可达。

题解:tarjan求一下整个图是否为一个强连通分量。

510C.Fox And Names

题意:给出n个字符串,问是否存在一个字母表,使得这n个字符串满足字典序。

题解:字典序其实就是一种拓扑关系。那么根据字符串的关系,判断是否可以建立一个拓扑图即可。

437C.The Child and Toy

题意:给出n个节点,m条无向边,删除一个点的代价是与这个点相邻的还未被删除的点的点权和。问删除所有点的最小代价。

题解:贪心。很明显应该先删除点权最大的点。那么从大网小删即可。

500A.New Year Transportation

题意:有n个城市1排,从第i个城市可以走到i+a[i]号城市,给一个城市t,问是否能从1到t?
题解:从1开始扫一遍打标记,比如i打上标记,那么i+a[i]也打上标记。看最后t有没有被打上标记即可。

519B. A and B and Compilation Errors(模拟)

题意:给出三个序列下面的序列是上面的序列去掉一个数得到的。求出两个去掉的数。

煞笔题。。

639B. Bear and Forgotten Tree 3(构造乱搞)

题意:构造一棵个节点,直径为,深度为的树(深度是从1号节点算起)。

题解:判掉一些无解的情况。对于合法的的情况先从1连一条长度为h的链,然后再从1连一条长度为d-h的链,最后把剩下的点都连到根上。(这里有一个坑,如果h=d的话不能连1号节点)。细节挺多的,直接上代码了。

298A. Snow Footprints(模拟+分类讨论)

题意不想说了。。。

只会出现RRLL,RRRR,LLLL这样的序列。而且注意是跨过这个格子,才会留下脚印。然后分类讨论一下。。。做这种字符串的分类讨论题目太恶心了。。。

298B. Sail(模拟+贪心)

题意不想说了。

显然对于当前位置,在一个时刻只有跟着风向走还是不走这两种选择。那么肯定要选择可以让我们离终点更近的选择了。把整个过程模拟一遍。

 

382C. Arithmetic Progression(分类讨论)

题意:给出一个长度为n(n<1e5)的正数序列,每个数不超过1e8,然后你现在可以加入一个数让整个数列变成等差数列。有无数种方案输出-1,无解输出0.别的话输出方案数,以及添加的数。添加的数可以超过1e8或者是负数。

还是分类讨论。。。太恶心了。我们先计算出原数列的间距个数,以及间距大小。

1.如果只有一个数字,那么有无穷多解。

2.如果有三个或者以上间距一定无解。

3.只有一个间距的话。如果间距为0,也就是所有数都相同,那么只有一种方案。如果间距不为0而且这个序列的长度为2而且这个间距可以被2整除,那么有三种方案(因为可以放到中间)。否则只有两种。

4.有两个间距。如果较大的那个间距是较小的那个的两倍,较小的间距不能为0.而且较大间距的个数只有1个,那么有1种方案。

450D. Jzzhu and Cities(最短路)

题目大意:在一个国家中有n个城市(城市编号1~n),m条公路,k条铁路,编号为1的城市为首都,为了节约,不需要的铁路需要关闭,问在保证首都到其余所有城市的最短路不变的条件下,最多有多少条铁路是不需要的。

首先我们可以跑一遍单源最短路(最好dij,spfa的用优先队列卡过去)。然后我们枚举火车线路,如果端点的最短路径大于火车线路,那么肯定要删除。如果端点的最短路径等于火车线路,且最短路径条数大于1,那么也要删除。

451E.Devu and Flowers(组合数学)

题意:有n个盒子,从这n个盒子中选s支花(有的盒子可以不选),每个花坛有f[i]支花,同一个花坛的花颜色相同,不同花坛的花颜色不同,问说可以有多少种方案数。

如果没有f[i]的限制,那么题目相当于问的方案数。那么很明显由隔板法得到方案数为。对于这个题目很明显这个答案会包括超过某些f[i]的答案。发现n才20,所以我们可以枚举一下超过的花坛有哪些组合,然后用容斥原理算出答案。注意如果某次超出的花坛为i,那么相当于把这个式子右边的s减去一个f[i]+1再做插板法。因为模数很大,而项数很小,所以不用lucas,直接循环算出组合数即可。

 

382A. Ksenia and Pan Scales

给出两个字符串S和T。S串中以’|’为分隔符,分成两部分。问你是否可以通过把T全部分成两部分(可以为空)分别给S中的两部分,让他们长度变得相同。

字符串模拟一下,用substr实在是方便。

 

543B. Destroying Roads

给出N个点和M条边,每条边的边权为1。给出S1,T1,len1,S2,T2,len2.问现在最多删去多少条边,可以让S1到T1的距离不超过len1,从S2到T2的距离不超过len2。

,

思路:把问题转化成至少有多少条边才可以满足让S1到T1的距离不超过len1,从S2到T2的距离不超过len2。假设我们找到了S1到T1的最短距离为dis1,S2到T2的最短距离为dis2。假设这两段最短路之间没有公共部分,那答案就是dis1+dis2。如果两段路径中间有重叠部分的话,我们可以通过枚举来得到答案。通过bfs暴力预处理出每个点对之间的最短距离,枚举就是O(1)的了。

 

623A. Graph and String

题意:给出一个n(n<=500)个结点的无向图,每个结点标号”abc”三个字母其中一个。将标号为相同字母的结点连边,将所有标号为b的结点与其它标号的结点连边。给出图的m个连边,求一种合法的标号方案,不存在输出’NO’。

一个b标号的点肯定是和其余点都相连的,我们先把这样的点标上b。然后枚举剩余的点以及他们的相连情况,假设我们枚举到了的还没标号的点都标上’a’,那么和它相连的没标号的就一定是’a’,不相邻的一定是c。这样就可以判断出来了。我最后又判断一下每个点的度。不知道有没有必要。。。反正判一下没什么错吧。。。

650A. Watchmen

给定二维平面的n个坐标,求满足|xixj|+|yiyj|=sqrt((xixj)(xixj)+(yiyj)(yiyj))的点对数

1n1e5,1xi,yi1e9,存在重复点的情况。

发现曼哈顿距离等于欧几里得距离,在二维平面上只有两点的x或者y相同才可能。所以用个map记录一下即可。但是因为有重点的存在,两个重点会被多算一次(x和y各一次)。所以再开个map记录一下点的个数即可。

 

460C. Number of Ways

题意:给你n个数,让你要把序列分成连续的三部分,要求每一部分的和相等。n<=1e5

预处理前缀和,然后扫一遍前缀和,开一个数组记录每个i之前(包括i在内)有多少个前缀和为sum/3的。然后倒着扫一遍后缀和,发现一个为sum/3的后缀和的时候,我们需要知道在i-2的位置及之前有多少个前缀和为sum/3的。因为要保证每一部分都不为空。

229C. Triangles

POI原题啊,考虑反面就可以了。。。

472A. Design Tutorial: Learn from Math

题意:给出一个n(),让你把它分成两个合数之和。

首先这个肯定是可以的。对于奇数的话,拆成9和n-9,因为n-9一定是偶数且大于2,所以这两个一定是两个合数。对于偶数的话,拆成8和n-8,因为n-8是偶数,所以这两个一定是合数。当然这是题解的证明,我们直接预处理出素数表,暴力枚举即可。

472B. Design Tutorial: Learn from Life

题意:在1楼有n个人准备乘坐电梯,电梯每次只能装k个人。如何安排能够使得电梯运送完所有人之后再次停回到1楼时所经过的路程最少。求出这个最小路程。

想了个贪心,我是这么想的,从需要去楼层越高的人开始装人。其实可以这么证明,假如人数n可以整除k,从小开始还是从大开始都无所谓了,因为路程肯定确定了。但是在n不可以整除k的时候,就意味着最后有不足k人,那么这时候假如有人走最高层那肯定是比走较低层的路程大。

472C. Design Tutorial: Make It Nondeterministic

题意:省略吧。。。。

我们按照题目给出的排列,来进行判断是否这个排列可行即可。贪心的扫一遍。

472D. Design Tutorial: Inverse the Problem

题意:给出一个n*n的矩阵(n<=2000),问你这个矩阵是否可能是一棵树的邻接矩阵。

额,一开始想的思路是把这个邻接矩阵求一个MST,这个MST就是那棵树了。然后再一一验证每对点之间的距离是否与邻接矩阵相同。但是这样的话可能需要一个LCA。。。不想写。。。后来问问韩司机,告诉我O(n^2)求一个MST就可以了。

我们先特判掉不符合邻接矩阵的情况,然后接下来对于每个点,都找到与它相邻最近的点为前驱,其实这就相当于求最小生成树的过程了。前驱也就相当于这棵树上的父亲,那么找到一个点u和他的前躯v后,我们再扫一下其余各点,这时候前驱v和该节点u到剩下的点的距离情况就两种了:dis[u]>dis[v]或者dis[u]<dis[v],而两者之间的差值一定是那条边的长度,否则就不合法。

时间复杂度O(n^2)。

611C. New Year and Domino

题意:给出一个h*w(h,w均小于500)的字符矩阵,每次询问一个子矩阵,问其中可以放下一个1*2的骨牌的方案数。’#’不可以放置骨牌。

考虑维护二维前缀和,这样的话每次查询的时候可以在O(h+w)的时间内得到答案。计算的时候按照容斥就可以了。但是需要注意边界上的’.’可能需要减去一些方案。发现二维前缀和比较好的计算方法就是,先处理好第一行和第一列,然后容斥的计算剩余的部分。

 

4C. Registration system

哈希加上map计数。。。水题

732D. Exams

二分答案,然后贪心验证。贪心的思路是,每个考试科目肯定是越晚考越好,这样可以有更多的时间复习。所以保存下来每科的最晚考试时间,然后扫一遍,看每门是否可以在规定的最晚时间内完成即可。

 

732E. Sockets

题意:略。

用map贪心乱搞了一通。因为s不超过1e9,所以每个电源最多被适配器操作31次就会变成0了。那么我们可以每个电源,按照从小到大的顺序,不断操作。当在computer里找到匹配的就标记一下。这样从小到大的顺序可以保证适配器数目最小。因为对于同一个可以被匹配的电脑,小的电源会先匹配上。

 

732A. Buy a Shovel

随便搞搞。。。

 

732B. Cormen — The Best Friend Of a Man

根据题模拟一下。如果出现少于k次的话,尽量放到第二天了,算是一个贪心?

732C. Sanatorium

题意:给出b,d,s分别代表吃了多少天的早饭,中饭和晚饭。你可能忘记吃了一些次的饭,现在需要求出最少可能忘记吃了多少次饭。

首先需要确定一个天数,找出吃了最多次数的饭,那么减去1就是最少过了这么多天。然后和剩下的两个比比,就可以求出答案。

732F. Tourist Reform

题意:给出n个点m条边的一个无向图。保证没有重边。现在对每一条边定向,每个节点都可以有一个值r。代表这个点可以从i到达多少个点。现在需要求出让最少的r值最大的分配方案。

把所有的边双联通分量求出来,那么就形成了一个个连通块,连通块之间有桥边。那么在各个连通块内,我们dfs走出来环就可以给这个连通块内的各个边定向。而且因为是在连通分量内,所以这些边的定向是无所谓的。现在考虑桥边如何定向。其实想一想,把所有连通块缩点后只保留桥边,那么就形成了一个无根树。那么最后剩下来的最小的r一定是在某一个连通块内。这个连通块的桥边都是指向他的没有出边。也就是根节点。那么最大的最少r应该正是最大的连通块中点的个数。其余别的连通块的桥边均指向这个根就可以了。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注