- 博客(229)
- 收藏
- 关注
RSS订阅原创 Codeforces Beta Round #7 A. Kalevitch and Chess
题目大意给出一个8*8的矩阵包含黑白色块，问最少操作几次可以恢复白色。解题思路水题，记录下行和列黑块的个数，进行操作即可。
2015-03-01 13:39:18
1527
原创 Codeforces Beta Round #6 (Div. 2 Only) E. Exposition
题目大意给出一个正整数序列包含nn个数的。要求找到一类区间，使得区间内的最大数和最小数之间的差不超过kk。输出区间的最长长度，这样长度的区间有几个，并分别输出各个区间的左右边界。解题思路对序列构造线段树，查询区间的最大值和最小值。遍历确定最长区间的长度和数量
2015-02-21 12:04:38
1801
原创 Codeforces Beta Round #6 (Div. 2 Only) D. Lizards and Basements 2
题目大意有排成一排的nn个弓箭手，第ii个弓箭手有 hih_i 的血量。主角可以使用火球术去攻击弓箭手。被直接攻击的弓箭手ii受到aa点伤害，同时第i−1i-1个和第i+1i+1个弓箭手会受到bb点伤害。当弓箭手的血量小于00时弓箭手死亡。问最少需要释放多少个火球术，每个火球术攻击的是第几个弓箭手。解题思路这是一个动态规划问题。定义一个四维dpdp数组。对于dp[i][j][k][l]dp[i][j
2015-02-20 20:35:59
1339
原创 Codeforces Beta Round #6 (Div. 2 Only) C. Alice, Bob and Chocolate
题目大意有些长度不同的巧克力棒排成一行，A从左往右吃，B从右往左吃。两人吃的速度相同，不允许暂停，不允许手中的还没吃完就吃下一个，当两个人手中的同时吃完并且下一个要吃的是相同的一个时这个巧克力棒归A吃。问他们最终都吃了几个。解题思路两个指针分别从左到右和从右到左。按照题目要求操作即可。
2015-02-20 09:32:11
1893
原创 Codeforces Beta Round #6 (Div. 2 Only) B. President's Office
题目大意给出一个n*m的矩阵 ，描述桌子的布局。总统的桌子和他的副手的桌子相邻，每一个人的桌子有它独有的颜色。问总统有多少个副手。解题思路搜出总统的桌子在矩阵中的边界后判断边界外的其它颜色桌子的数量。
2015-02-20 09:04:38
2025
原创 Codeforces Beta Round #6 (Div. 2 Only) A. Triangle
题目大意给出四条边，问是否可以取三条边组成一个三角形，如果不行的话可否组成一个退化的三角形（两边之和等于第三边）解题思路水题，啥都不说枚举即可。
2015-02-17 21:23:42
2366
原创 Codeforces Beta Round #5 E. Bindian Signalizing
题目大意有N座山组成一个环，两座山互相能看到的要求是相连的圆弧上没有任何其他的山高度比它们高。求能看到的山的组数。解题思路首先要拆环成链，将山的序列改变，第一座山是最高的山。 其次是统计对于这个序列的L数组和
2015-02-17 20:53:36
3066
原创 Facebook Hacker Cup 2015 Round 1 Winning at Sports (附带测试数据)
题目描述：Winning at Sports25 points In the game of Sports, the object is have more points than the other team after a cer
2015-01-21 09:30:42
5348
1
原创 Facebook Hacker Cup 2015 Round 1 Autocomplete (附带测试数据)
题目描述：Autocomplete25 points Since you crave state-of-the-art technology, you've just purchased a phone with a grea
2015-01-21 09:12:18
5723
原创 Facebook Hacker Cup 2015 Round 1 Homework（附带测试数据）
题目描述：Homework10 points Your first-grade math teacher, Mr. Book, has just introduced you to an amazing new co
2015-01-21 08:46:49
5898
原创 Codeforces Beta Round #5 D. Follow Traffic Rules
这个题是个高中的物理公式，只要细节处理好就能过（现在最怕的就是细节啊）~~ 题目大意：城市A、B之间有一条路，长度为l，在距离A城市d的位置放置了限速标志，意味着到那个点的时候速度必须不大于限制速度。现有一车在城市A出发，车的加速度为a，最大速度为v，求通过这条路的最小时间。车出发时的速度为零。解题思路：套物理公式，分类讨论下面
2015-01-15 11:10:04
4143
原创 Codeforces Beta Round #5 C. Longest Regular Bracket Sequence
经过了一个多月的时间，今天终于可以回到正轨了，继续开始刷CF。题目大意：给出一个只有括号的字符串，求最长“匹配”子串的长度和数量。解题思路：设置数组记录匹配括号段的开头。下面是代码：#include #include #include #include #include #include #include #include #incl
2015-01-14 14:02:19
4382
原创 Codeforces Beta Round #5 B. Center Alignment
又是模拟，就当练手吧。题目大意：给出一段文本，输出居中显示的样子。当左右空白数量不能平均时，上一个靠左，下一个靠右。解题思路：见代码~~下面是代码：#include #include #include #include #include #include #include #include #include #include
2014-11-29 15:55:29
4207
原创 Codeforces Beta Round #5 A. Chat Server's Outgoing Traffic
嗯~~ 手感越来越好了，喜欢1A的感觉~~题目大意：给出一些命令，求最大通信量。解题思路：模拟题，需要set来hash人名 。下面是代码：#include #include #include #include #include #include #include #include #include #include #i
2014-11-29 15:07:23
3977
原创 Codeforces Beta Round #4 (Div. 2 Only) D. Mysterious Present
最长上升子序列，这种水题还是一眼就能看出来的。题目大意：主人公想在一张w*h的明信片外套信封。他有n个信封，每个信封的长宽给出，问最多能套多少层。给出从小到大的顺序。解题思路：最长上升子序列，只不过是记忆路径。下面是代码：#include #include #include #include #include #includ
2014-11-29 14:44:39
4445
原创 Codeforces Beta Round #4 (Div. 2 Only) C. Registration system
这个题感觉还不错，以前字典树写的是最顺手的，这几次比赛屡屡挂在字典树上也是有阴影了啊~~题目大意：给出一些字符串，对每个字符串进行查询，若没出现过返回OK，若出现过就生成新字符串,格式为原字符串+数，数为这个字符串第几次重复出现。解题思路：字典树，对于每个字符串的插入次数进行计数。下面是代码：#include #includ
2014-11-29 13:32:23
4170
原创 Codeforces Beta Round #4 (Div. 2 Only) B. Before an Exam
继续刷水题，不能再错了！！题目大意：要求在n天内学习t小时，给出每一天可以学习的最小时间和最大时间。问能不能实现，若可以输出时间表。解题思路：水题一个，保证在区间范围内的情况下直接贪心。下面是代码：#include #include #include #include #include #include #include
2014-11-29 13:11:55
4161
原创 Codeforces Beta Round #4 (Div. 2 Only) A. Watermelon
水题一个，就是记录下已经做过了。题目大意：给出一个数，问是否能分成两个偶数。下面是代码：#include #include #include #include #include #include #include #include #include #include #include #include #define eps 1e-10#
2014-11-28 13:41:14
3983
原创 Codeforces Beta Round #3 D. Least Cost Bracket Sequence
看来最不擅长的就是贪心，这种方法都想不起来是不是专题刷多了？ 也没见得专题做得有多好啊~题目大意：给出一个字符串，包括三种字符'('、')'、'?'，每个问号可以变成其他两种符号，但是需要费用。要求组成一个符合条件的字符串，使括号匹配，求最小费用。解题思路：贪心（发现他比动态规划都难）。不需要在意哪个括号和哪个括号匹配，只需要注意数量就行
2014-11-25 17:19:00
4178
原创 Codeforces Beta Round #3 C. Tic-tac-toe
井字棋 ，这个模拟也是醉了题目大意：给出一个井字棋棋局，判断他是不是合法的。若合法且出现某人赢是谁赢了，没出现某人赢是下一步该谁下，还是平局。解题思路：分类讨论，就是模拟啊 恶心死~~下面是（又臭又长的）代码：#include #include #include #include #include #includ
2014-11-24 13:24:08
4236
原创 Codeforces Beta Round #3 B. Lorry
一个贪心题写成这样也是醉了 ，这种状态注定要打酱油了么 ，不甘心啊~~题目大意：一辆车可以承载体积V的货物，A种物品1个单位体积，B种2个单位体积，某种物品虽然体积相同但是能力却不相同。给出N个物品它的物品类型和能力值。求这辆车可以承载的物品的最大能力值之和是多少。解题思路：排序+贪心+条件判断，排序条件是单位体积的能力大小。下面是代码
2014-11-24 11:01:07
4286
原创 HDU 3126 Nova [2009 Asia Wuhan Regional Contest Online]
题目大意有n个巫妖，m个精灵，k棵树，他们都有自己的坐标表示自己的位置。巫妖有攻击范围和冷却时间，树有覆盖范围。如果某个巫妖攻击精灵的路线（他俩之间的连线）经过树的覆盖范围，表示精灵被树挡住巫妖攻击不到。求巫妖杀死所有精灵的时间，若无法全部杀死输出-1；解题思路：判断巫妖是否能打到精灵用线段与点的最短距离来判断，若最短距离小于树的覆盖范围，就攻击不到。最小时间可
2014-11-09 10:11:24
4741
原创 Codeforces Beta Round #3 A. Shortest path of the king
题目大意：给出国际棋盘上的两个点，求对于允许的操作，最少操作次数是多少，并输出操作过程。解题思路：水题一个，见代码。下面是代码：#include #include #include #include #include #include #include #include #include #include #i
2014-11-03 17:17:45
4343
原创 Codeforces Beta Round #2 C. Commentator problem
模拟退火果然是一个很高端的东西，思路神马的完全搞不懂啊~题目大意：给出三个圆，求一点到这三个圆的两切线的夹角相等。解题思路：对于这个题来说还是有多种思路的 ，不过都搞不明白~~ /害羞脸用模拟退火来解也是一件赌人品的事，因为退火的过程设计的不合理，WA妥妥的。其实我也是学了一点点，还不是太明白啊~~下面是代码：#i
2014-11-02 15:36:02
4722
原创 Codeforces Beta Round #2 B. The least round way
这个2B题还好~~题目大意：给出一个矩阵，从左上走到右下，只能往右或下走。路径中每个格子有一个数，这些数相乘得出一个数。求这个数末尾零最少的一条路径。解题思路：找出一条路径，乘积得数中素因子2的个数最少，再找出一个素因子5最少， 比较两个输出最小的。有意外情况就是有数为零。这种情况把零当成10跑一遍，如果素因子最少为0，输出路径，如果不是，输出经过零
2014-11-01 12:20:10
4977
原创 Codeforces Beta Round #2 A. Winner
果然水到家了，自从回来开始连一道CF的A都做不出来，交了10次WA也是醉了。题目大意：给出n个操作，每个操作是某个名字加多少分。求最后谁是第一名。第一名的定义是：获得分数最高。如果有多个分数最高，谁最先达到这个分数的就是谁。每个人的基础分是0.下面是代码：#include #include #include #include #include
2014-11-01 10:11:10
4443
原创 POJ 2451 Uyuw's Concert
学了ZZY的算法，就要过一下他出的题。题目大意：给出一些直线，求半平面交的面积。解题思路：半平面交求面积。下面是代码：#include #include #include #include #include #include #include #include #include #include #include #d
2014-08-28 15:21:02
4306
原创 POJ 3335 Rotating Scoreboard
题目大意：同 POJ3130解题思路：同 POJ3130POJ3130解题报告：点此进入注意:两个题给出点的顺序不一样。不要老是抄模版（我不会告诉你我就是这么做的）。下面是代码：#include #include #include #include #include #include #include #include #incl
2014-08-28 13:51:59
4645
原创 POJ 3130 How I Mathematician Wonder What You Are!
题目大意：按顺序给出一些点。可以构成一个多边形，问多边形是否有核。解题思路：半平面交。模版题。用的是ZZY的O（Nlogn）的算法。算法大体思路是这样的：step1. 将所有半平面按极角排序，对于极角相同的，选择性的保留一个。 O(nlogn)step2. 使用一个双端队列(deque)，加入最开始2个半平面。step3. 每次考虑一个新的半平面： a.whi
2014-08-28 13:46:02
5123
原创 POJ 3004 && HDU 1922 Subway planning
题目大意：平面直角坐标系中有一些点代表着一些城市。国家要在（0，0）点设置中心车站并向建设地铁线路，但要求线路是直线。某个城市可以使用地铁线路的前提是它与线路的直线距离不超过d。问最少建设多少条线路才能让所有的城市都能使用地铁。解题思路：扫描线+最小区间覆盖。如图所示：对于任何一个点，都有一个铁路允许的设立的角度区间，在d固定的情况下，点距离原点越远区间越小。因
2014-08-26 19:17:58
4736
原创 POJ 2280 && HDU 1661 Amphiphilic Carbon Molecules
题目大意：在平面上有一些点，每个点都有0，1其中一个属性。要求用一条直线将平面分成两部分。其中一部分取属性为0的点，另一部分取属性为1的点。若点在直线上全部取走，问最多能取多少个点。解题思路：扫描线算法。枚举任意一点，其他点依照那一点进行极角排序。扫描获得最大值。注意：1、因为 atan2方式的极角排序有精度误差，在这里需要用叉积方式排序。否则就
2014-08-25 20:47:02
4544
原创 POJ 3277 City Horizon
题目大意：给出各个房子阴影的长度（以区间表示）和高度，求阴影的总面积。解题思路：矩形面积并。下面是代码：#include #include #include //#include #include #include #include #include #include #include #include #define eps 1e-8#d
2014-08-25 08:21:00
4608
原创 POJ 1177 Picture
题目大意：矩形的周长并（够大意了~）解题思路：扫描线，跟面积并一样，只不过处理周长的时候注意边的增加与减少。下面是代码：#include #include #include #include #include #include #include #include #include #include #include #define e
2014-08-24 18:33:40
4466
原创 POJ 1765 November Rain
题目大意：有一些屋顶，相当于一些线段（不想交）。问每一条线段可以接到多少水，相对较低的屋顶可以接到高屋顶留下的水（如题图所示）。由于y1!=y2,所以保证屋顶是斜的。解题思路：扫描线，因为对于同一个x最多有25条线段，所以不需要线段树更新。在扫描线的过程中构造出线段与线段之间的关系，好在最后计算每个屋顶可以接多少水。下面是代码：#include #incl
2014-08-24 10:07:59
4780
原创 POJ 1095 Trees Made to Order
题目大意：按照题意将数用二叉树的形式表示出来。将二叉树按照要求形式输出。解题思路：由于有图示，可以轻易看出这个顺序跟卡特兰数列有关。且对于任意一个树的任意子树来说，右子树相当于分针，左子树相当于秒针。也就是说当右子树要变换到下一种状态时，左子树要将它所能变换的状态全变换完才可以。下面是代码：#include #include #include #inclu
2014-08-18 08:50:47
4610
原创 POJ 3286 How many 0's?
题目大意：计算[m,n]之间所有数字有多少个零。解题思路：可以用[0,m）之间和[0,n]之间有多少个零然后作差。规律是计算所有位置在到当前数时有多少个零。下面是代码： #include #include #include #include #include #include #include #include #include #
2014-08-17 11:02:08
4421
原创 POJ 3296 Rinse
果然是杂题，都没有人做啊，这解题报告独一份~~题目大意：Granny有一个罐子里有Vw的酒，她有Vb的雨水来冲这个罐子，由于表面张力的原因当罐子往外倒液体时，会有Vr的液体倒不出来。罐子的容量是Vc。她最多有K次拿水冲洗罐子的机会，每一次它可以取一些雨水倒入罐子充分混合之后在将罐子里的液体倒出来。问怎样冲洗可以使罐子内残留的酒的数量最少。解题思路：对于操
2014-08-16 14:41:17
4636
原创 POJ 1870 Bee Breeding
这种烂题我再也不想见到了！！比模拟题还讨厌！！题目大意：根据题目给出的各个数的位置，求某两个数之间的位置。解题思路：由给出的位置可以找到一个规律，二维的六个象限的坐标系，计算坐标然后计算距离就行。下面是代码：#include #include #include #include #include #include #include
2014-08-13 19:32:16
4774
原创 POJ 2454 Jersey Politics
题目大意：给出3*k个数，将它们分成三分，每份k个数，要求至少有两份之和大于500*k。解题思路：随机化，对于这道题来说这是个好想法~将所有数从大到小排序后将前2*k个数再随机调整直到满足条件。下面是代码：#include #include #include #include #include #include #include #includ
2014-08-13 13:28:24
5023
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人