Codefores
关注
分享
扫一扫
月黑风高叶
你看到一条个人简介~
展开
-
Codeforces 622C Not Equal on a Segment
题目链接：http://codeforces.com/problemset/problem/622/C题意：给出一个大小为n的序列，给出一个区间[l,r]和c要求找出一个该区间内和c不一样的数，没有则输出-1思路：将序列中相邻的数合并，因为是找不同的数，所以时间一下就得到了优化……#include #include #include #include u原创 2016-06-02 12:18:19 · 420 阅读 · 0 评论 -
Codeforces 616D Longest k-Good Segment
题目链接：http://codeforces.com/problemset/problem/616/D题意： 给出一个序列，要求找出一个最大连续的子序列，要求子序列中不同的数不可以超过k思路：因为是连续的序列，所以可以用"移尺法"(听别人说的名字)，类似于维护一个符合题目要求的队列，这个方法似乎经常用到的，详细看代码#include #include #in原创 2016-05-29 20:48:16 · 459 阅读 · 0 评论 -
Codeforces 612C Replace To Make Regular Bracket Sequence
题目链接：http://codeforces.com/problemset/problem/612/C题意：有4对类型的括号，可以将左括号变成另一类型的左括号，可以将右括号变成另一类型的右括号，问最少变多少次可以括号可以匹配，不可以输出-1思路：利用栈做括号匹配就可以了，失配的时候将一个右括号转换下类型res++，最后栈清空了就匹配完成#include #include原创 2016-05-25 20:13:22 · 366 阅读 · 0 评论 -
Codeforces 610C Harmony Analysis(构造)
题目链接：http://codeforces.com/problemset/problem/610/C题意：‘+’代表1，‘*’代表-1，要求构造2^k个两两正交的串思路：k=1时，s[1][1]=‘+’ k=2时，s[2][1]., =s[2][2]=s[1][1]=‘+’原创 2016-05-24 21:24:02 · 610 阅读 · 0 评论 -
Codeforces 616C The Labyrinth
题目链接：http://codeforces.com/problemset/problem/616/C题意：给出n*m的矩阵，问和每一个‘*’连通的'.'有多少个(包括自己)思路：每一个'.'连通块分配一个编号并求出连通块大小，每一个'*'号加上四周的连通块就好，注意去重#include #include #include #inc原创 2016-05-24 20:26:02 · 459 阅读 · 0 评论 -
Codeforces 618C Constellation
题目链接：http://codeforces.com/problemset/problem/618/C题意：给出n个点，要求以这些点构造一个三角形，三角形的边不能有其他点，三角形内也不可以有其他点思路：用点的x坐标或者y坐标排序，以第一个和第二个点为三角形2个点，寻找第三个点，排序过后就排除了有其他点还在边上的情况了#include #in原创 2016-05-24 20:19:52 · 382 阅读 · 0 评论 -
Codeforces 620C Pearls in a Row(贪心)
题目链接：http://codeforces.com/problemset/problem/620/C题意：给出一个n大小的序列，截取一段，如果这一段有2个相同的数字，那么就是好的子序列，问最多有几个好子序列思路：从头开始遍历，碰到第一个出现2次的数字就把这段数字截取，我感觉第3个样例输出1 3，5 7应该也符合题意，但是wa了……注意的是LL要用map进行原创 2016-05-22 19:33:14 · 745 阅读 · 2 评论 -
Codeforces 623A Graph and String (构造)
题目链接：http://codeforces.com/problemset/problem/623/A题意：一个仅包含abc这3个字母的字符串，a与b和自身相连，b与ac和自身相连，c与b与自身相连，给出字符串每一位的相连情况，要求构造出这样一个字符串思路：b与ac和自己都相连，所以连有n-1个点的位置必定是b，其他的点我们找一点和与该点相连的点设为a，其他设为c，最后n^原创 2016-05-22 19:21:34 · 678 阅读 · 0 评论 -
Codeforces 607A Chain Reaction (dp+二分)
题目链接：http://codeforces.com/problemset/problem/607/A题意：有n个灯塔，点亮一个灯塔会摧毁该灯塔左边距离x以内的灯塔，现在可以在最右边放置一个位置和摧毁距离任意的灯塔，问最少可以摧毁多少个灯塔思路：dp[i]表示i为最右边的灯塔时剩下的灯塔数，利用二分查询找到离灯塔i最近存活的灯塔j，dp[i]=dp[j]+1，n减去存活最多原创 2016-04-29 17:06:23 · 394 阅读 · 0 评论 -
Codeforces 599C Day at the Beach
题目链接：http://codeforces.com/problemset/problem/599/C题意：给出大小为n的序列，要求将该序列分成连续的若干个部分，每个部分各自升序排序后组成的序列与原序列升序排序后一样，问最多分成几个部分思路： 一开始可以想到要满足max(h1,h2,h3……,hx)max(h1,h2,h3……,hx)，所以max[1,x]必定小于max[x原创 2016-03-10 17:46:28 · 628 阅读 · 0 评论 -
Codeforces 593A 2Char
#include #include #include #include using namespace std;int num[30][30],vis[30];char s[100030];int main(){ int n; while (scanf("%d",&n)!=EOF) { int cnt=0,ch原创 2016-03-09 18:54:57 · 244 阅读 · 0 评论 -
Codeforces 593B Anton and Lines
题目链接：http://codeforces.com/problemset/problem/593/B题意：直线：y=kx+b，给出n个(k,b)，问这n条直线是否在(x1,x2)中有交点思路：处理处每条直线与x1，x2的交点l和r，存储结构体数组s中，如果li rj则相交，由于数据比较大，需要有更好的查询方式，我们先以l从小到大排一遍序，先以s[0]为基准tmp进行比较，原创 2016-01-17 12:27:46 · 375 阅读 · 0 评论 -
Codeforces 469D Unbearable Controversy of Being
题目链接：http://codeforces.com/problemset/problem/489/D题意：给出一个有向图，求有多少个如下的棱形(2个点之间可以有多个棱形)思路：枚举2个点A,B然后找出所有与A相连的点是否与B相，相连则s++，这2个点之间的棱形就是s*(s-1)/2#include #include #include #inclu原创 2015-11-17 18:59:53 · 481 阅读 · 0 评论 -
Codeforces 526C Om Nom and Candies
题目链接：http://codeforces.com/problemset/problem/526/C提议：有2种糖果，分别可以提供w1和w2的快乐值，但是要消耗c1和c2的能量，问在限定的能量tol内如何获得最大的快乐值思路：如果数据范围够小的话我们是可以通过枚举某一种糖果的数量来得到结果，但这道题的数据范围比较大，但c1大于sqrt(tol)的时候，糖果a的课购买数量一原创 2015-11-02 18:56:31 · 567 阅读 · 0 评论 -
Codeforces 489D Unbearable Controversy of Being
题目链接：http://codeforces.com/problemset/problem/489/D题意：给出n点，m条有向边，问有多少个如下图的菱形思路：枚举2点，以及与第一个点的边，若是该边的终点与第二个点相连，则第一个点和第二个点有一条菱形边，算出2点间所有的菱形边则可以求出有多少个菱形，看起来时间复杂度是o(n*n*m)但是用了vecter动态数组，其原创 2015-10-14 19:12:44 · 380 阅读 · 0 评论 -
Codeforces 500C New Year Book Reading
题目链接：http://codeforces.com/problemset/problem/500/C题意：有n天，一共有m本书，每一本书有各自的重量，每一天要看一本书(n可以>m，就是可以多天看同一本)，放书的地方像一个栈，假如要取第二本书的话，必须将第一本书拿出来，最后将当天看完的书放在顶端，问如何摆放使得举起的重量最小思路：因为每次看完的书都必须放在顶端，每一次取书都原创 2015-10-14 19:01:29 · 845 阅读 · 0 评论 -
Codeforces 492D Vanya and Computer Game
题目链接：http://codeforces.com/problemset/problem/492/D题意：游戏里，有2个玩家，a玩家1s内攻击x次，b玩家1s内攻击y次，给出若干个怪物的血量，问谁补得刀思路：a玩家第i次攻击，b玩家第j次攻击，i/x > j/y(化简为i*y >j*x)，i+j次是b的，若相等则i+j次攻击和i+j+1次攻击都视为同时攻击#i原创 2015-10-01 19:16:08 · 401 阅读 · 0 评论 -
Codeforces 514C Watto and Mechanism （字典树+dfs）
题目链接：http://codeforces.com/problemset/problem/514/C题意：给出n个模式串，给出m个字符串，问字符串能否通过变换一次成为模式串(必须变换)思路：利用模式串建立字典树，dfs查询是否有何m个字符串相差一位的模式串(每一个字符都有可能变换，开始写的时候以为只有当前字符不符合才进行变换，无法处理一些情况)#include原创 2015-09-29 19:25:42 · 459 阅读 · 0 评论 -
Codeforces 550 Regular Bridge
题目链接：http://codeforces.com/problemset/problem/550/D题意：构建一个图，每一个点的最大度数k，至少有一条桥边(去掉该边后图不连通)思路：很难描述，配合图解释k为奇数的时候以一条桥边来构建一个对称的图，为了满足黑点度数k构建了k-1个红点，同时为了满足红点的度数构建了1个蓝点，但只有一个蓝点时无法满足蓝点度数k的要求，因原创 2015-09-23 00:14:04 · 368 阅读 · 0 评论 -
Codefrces 388C Fox and Card Game
题目链接：http://codeforces.com/problemset/problem/388/C题意：桌上有n副牌，每张牌有个权值，一人可以从牌堆顶取一张，一认可以从牌堆底取一张，轮流下去直到牌没有了，都选择最优的策略，问最后他们各自的牌权值和思路：刚开始想……每次都取最大的牌不就好了么，然后打脸了，按照博弈论的策略因为双方都要抑制对方，每一套牌他们各取一半，如果有剩原创 2015-09-16 16:21:56 · 480 阅读 · 0 评论 -
Codeforces 144D Missile Silos
题目链接：http://codeforces.com/problemset/problem/144/D题意：给出n个点，m条边，以及原点，导弹发射井在离原点len(必须是最短路径)，有可能在点上或者在边上，问有几个导弹发射井思路：首先最短路求出各点到原点的距离，判断出在点上的导弹井，然后在判断在边上的导弹井(边要存放在另一个数组里方便判断……而且不这么做会出莫名的错误，wa原创 2015-09-15 17:39:59 · 559 阅读 · 0 评论 -
Codeforces 316B2 EKG
题目链接：http://codeforces.com/problemset/problem/316/B2题意：一共有n个人，给出你的位置k，以及每一个人前面的人的编号(0代表不知道)，问你排在第几个思路：相连的人可以构成一条链，预处理出除了自己所在链外每一条的长度以及自己位置在所在链的位置，然后通过dp，把可以接自己所在链的位置标为1就可以了#include原创 2015-09-09 23:22:16 · 542 阅读 · 0 评论 -
Codeforces 404C Restore Graph
题目链接：http://codeforces.com/problemset/problem/404/C题意：一个图有n个点，每一个点最多链接m条直线，给出所有点到顶点的距离(没有环)，输出所有直接相连的点思路：构造，0距离的为顶点，1距离的接在0距离后面，2距离的接在1距离的后面，用了栈保存可以链接的点，如果栈空了构造失败，输出-1，有多个顶点或者没有顶点同样输出-1原创 2015-09-09 23:15:08 · 712 阅读 · 0 评论 -
Codeforces 350B Resort
题目链接：http://codeforces.com/problemset/problem/350/B题意：有n个地方，给出n大小的序列a，0代表ai是山地，1代表ai是旅馆，再给出个n大小的序列v，第i的序列表示ai可以冲vi到达，问怎么走才能使路途最长(终点要是旅馆，而且路中途没有分叉)思路：预处理每一个点的入度，每一个旅馆开始进行bfs(dfs应该也可以)，直到该点有原创 2015-09-09 11:24:13 · 1004 阅读 · 0 评论 -
Codeforces 371C Hamburgers
题目链接：http://codeforces.com/problemset/problem/371/C题意：做汉堡要3种材料，给出一个字符串表示每种材料要多少，给出每种材料有多少，给出每种材料价格有多少，给出你现在有多少钱，问你最多可以做几个汉堡思路：最近看到这种题目就立刻想到二分了，二分最多做几个汉堡然后判断钱够不够就可以了，注意有的材料可能不被用到，直接模拟也行，先把原原创 2015-09-06 23:13:59 · 1164 阅读 · 0 评论 -
Codeforces 466B Wonder Room
题目链接：http://codeforces.com/problemset/problem/466/B题意：有一个a*b大小的房间，有n的学生，每一个学生需要6单位的面积，也就是要一个6*n大小的房间，可以将任意增大a和b，问如何使a*b大于6*n且差值最小思路：因为知道最后面积一定是大于6*n，所以只要分别枚举a和b的大小就可以求出另一个参数的大小，如果求出另一个参数不是原创 2015-09-04 13:52:30 · 429 阅读 · 0 评论 -
Codeforces 493D Vasya and Chess
题目链接：http://codeforces.com/problemset/problem/493/D题意：有一个n*n的棋盘，(1,1)和(1,n)处分别放置黑白2色的皇后，其余格子放置绿色的棋子，白色皇后先移动，每次移动必须吃掉一个棋子，如果己方皇后被吃掉和无法移动则输，问那方一定会赢，如果白方赢了输出第一步思路：好久没看到过这么简单的博弈论了……首先确定2种情况，n=原创 2015-09-03 14:10:26 · 479 阅读 · 0 评论 -
Codeforces 436C Gargari and Bishops
题目链接：http://codeforces.com/problemset/problem/463/C题意：给出一个棋盘，每一个格子有一个权值，有2个主教棋子(攻击范围是2条对角线)，要让棋子无法相互攻击(包括攻击范围不可以重叠),棋子可以获得一开始的攻击范围所有格子的权值，并且在攻击范围内自由移动，问如何摆放获得的权值最大思路：利用像皇后问题的方式(i+j 和 i-j)标原创 2015-08-30 10:50:51 · 393 阅读 · 0 评论 -
Codeforces 460C Present
题目链接：题意：有n朵花，有m天，每一天可以对第i朵花浇水，会影响到[i,i+w-1]区间里的花，使他们长高1长度，求m天后所有花里最矮的花的高度最大值(写的好绕口啊……)思路：因为求得是所有花里最矮的最大值……所以区间一定在[min,max+m]里所以用二分就可以了，然后对每一朵高度不够的花进行浇水操作，利用hei数组记录停止影响的花朵，变量day记录浇水的天数原创 2015-08-27 10:30:18 · 362 阅读 · 0 评论 -
Codeforces 459D Pashmak and Parmida's problem
题目链接：http://codeforces.com/problemset/problem/459/D题意：给出一个数列，定义f(1, i, ai) 为区间[1,i]中所有大小等于ai的数的个数，求有多少对i,j满足f(1, i, ai) > f(j, n, aj)思路:看了半天没看懂f(1, i, ai) 的定义……预处理好每一个f(1, i, ai) 与 f(j, n,原创 2015-08-25 16:58:31 · 407 阅读 · 0 评论 -
Codeforces 455B
题目链接:http://codeforces.com/problemset/problem/455/B题意：给出N个字符串，有2名选手，s一开始是个空串，每回合轮流往里面填字母，使得s为N个字符串其中一个的字串，若不能再往里面填字母则输，输了的下回合先手，问最后一回合谁赢思路：完全不会……参考了别人的题解，先用字典树保存N个字符串，在用深搜索把每一个节点的状态标记，状态原创 2015-08-18 19:53:00 · 730 阅读 · 0 评论 -
Codeforces 439C Devu and Partitioning of the Array
题目链接：http://codeforces.com/contest/439/problem/C题意：给出n个数，要求将其分为k份，k有p份之和是偶数，p-k份之和是奇数，给出分配方案思路：2个奇数可以组成一个偶数，一个奇数一个偶数可以组成一个奇数，这样构造就行，一开始用数组保存方案数，结果超内存了，后来直接构造好就输出，最后一组数的和可能要求是奇数也可能要求是偶数，所以奇原创 2015-08-15 12:11:11 · 390 阅读 · 0 评论 -
Codeforces 432C Prime Swaps
题目链接：http://codeforces.com/problemset/problem/432/C题意：给出一个大小为n无序数列s，1思路：一个数可以分拆为k个质数（k#include #include #include #include #define maxn 100030using namespace std;int s[100030原创 2015-08-14 19:27:12 · 596 阅读 · 0 评论 -
Codeforces 443B Kuriyama Mirai's Stones
题意：给大小为N的序列，M次查询，有2种查询方式，一种是给出区间L和R，问序列中L与R之间所有成员的和，一种是给出L和R，求序列第L大的数到第R大的数之间的成员的和。思路：刚开始用树状数组解决，然后发现数据太大无法保存，然后发现该题是不用更新维护的，只要做一遍预处理就可以了，然后很蠢的针对第一种询问做了预处理，发现超时，然后才发现要再对第2种查询进行预处理#in原创 2015-08-05 09:48:58 · 824 阅读 · 0 评论