- 博客(218)
- 收藏
- 关注
RSS订阅原创 Codeforces Round #394 (Div. 2) D. Dasha and Very Difficult Problem
http://codeforces.com/contest/761/problem/Dc[i] = b[i] - a[i]，而且b[]和a[]都属于[L, R]现在给出a[i]原数组和c[i]的相对大小，要确定b[i]注意c[]数组中没有重复数。首先对a[]按照c[]排序，这样最小的a[0]一定选择L作为b[0]往后每次二分L,R，找到能满足b[i]+a[i]>b[i-
2017-02-01 11:57:08
627
原创 POJ 2528 Mayor's posters （线段树区间更新、离散化）
题目链接：http://poj.org/problem?id=2528题意：题目大意：在墙壁上贴广告，广告的版面有大有小，并且贴广告有先后之分，后面贴的广告会覆盖前面的广告，求解最后能看到的广告面，如下图所示：两种视图，最后从Front View能看见的广告数目是4。#include #include #include #include using na
2016-11-27 21:09:30
743
原创 PAT-A 1034. Head of a Gang （dfs）
题目链接：https://www.patest.cn/contests/pat-a-practise/1034刚开始用并查集发现不太好处理。。用搜索就好做多了。注意虽然路径数最多1000，但节点数可能2000，所以数组要开大不然段错误。#include #include #include #include #include #include using n
2016-11-24 17:12:35
618
原创 Codeforces Round #380 (Div. 2) D. Sea Battle （贪心）
题目链接：http://codeforces.com/contest/738/problem/D题意：看样例吧13 3 2 31000000010001一个游戏，给长度为13的字符串，0表示没炸过，1表示炸过，然后有2个船，每个船长2，炸过3次了（就是有3个1）。问最少炸多少次能至少保证炸到一艘船？输出该炸的位置。贪心，代码写的不太优雅。先预处理出了1
2016-11-20 20:42:41
612
原创 PAT-A 1024. Palindromic Number
题目链接：https://www.patest.cn/contests/pat-a-practise/1024题意：给一个数字，不断加上这个数字所有位反过来的数字，最多k次，问第几次能变成回文串。会爆long long 。用字符串来做就好。#include #include #include #include #include using namespace
2016-11-19 13:58:24
594
原创 PAT-A 1022. Digital Library （字符串模拟）
题目链接：https://www.patest.cn/contests/pat-a-practise/1022题意：题意挺简单的就不说了。用char* 100ms，用string就超时，果然string要慢好多，大量字符串时还是不要用。#include #include #include using namespace std;int n, m;struct
2016-11-18 20:32:12
769
原创 PAT-A 1021. Deepest Root（搜索）
题目链接：https://www.patest.cn/contests/pat-a-practise/1021题意：无环连通图也可以视为一棵树，选定图中任意一点作为根，如果这时候整个树的深度最大，该点称为 deepest root。 给定一个图，按升序输出所有 deepest root。如果给定的图有多个连通分量，则输出连通分量的数量。要想树的深度最大，那么树跟一定是一个度为1的点
2016-11-18 16:22:26
446
原创 PAT-A 1017. Queueing at Bank （模拟）
题目链接：https://www.patest.cn/contests/pat-a-practise/1017题意：7 307:55:00 1617:00:01 207:59:59 1508:01:00 6008:00:00 3008:00:02 208:03:00 107个顾客，3个窗口。到来的时间，办完业务要多少分钟（不超过60）。早8：00到晚17：
2016-11-17 17:35:48
447
原创 HDU 4418 Time travel （概率DP+高斯消元）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4418题意：一个人在数轴上来回走，以pi的概率走i步i∈[1, m]，给定n（数轴长度），m，e（终点），s（起点），d（方向），求从s走到e经过的点数期望参考博客：http://972169909-qq-com.iteye.com/blog/1689107http://bl
2016-11-08 18:22:00
718
原创 HDU 5954 Do not pour out (
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5954参考博客：http://blog.csdn.net/danliwoo/article/details/53002695#include using namespace std;const double eps = 1e-10; //1e-8就会挂....const
2016-11-06 21:47:21
1236
原创 HDU 5963 朋友 （博弈、找规律）
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=5963题意：中文题，题意不说了。就是男生女生玩游戏，无聊.....对于每一条链，第一条边 权值为 1 。那么girl 操作一次肯定会将其变成 0 ，boy 操作一次肯定 会将其变成 1 或者 boy 没办法进行操作。这样的话， girl 必胜。那么相应的， n 条链只需要判断
2016-11-06 19:35:09
748
原创 HDU 2262 Where is the canteen （高斯消元、概率）
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=2262题意：n*m的地图，有一个起点，有多个出口，上下左右走，有的格子不能走，求从起点走到一个出口的期望步数是多少。第一次做浮点数高斯消元求期望的题。 算是复习了一下高斯消元的知识，发现对于以前学过的东西掌握的还是不好...很多地方都想不起来了...要多复习啊。关于本题推
2016-11-05 21:14:18
589
原创 HDU 5572 An Easy Physics Problem (物理、计算几何)
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=5572题意：一个质点球，一个固定的刚性圆柱体 给定圆柱体圆心坐标，半径 小球起点坐标，起始运动方向（向量） 终点坐标 问能否到达终点，小球运动中如果碰到圆柱体会反射（基本物理知识）另外小球的起点和终点不在圆柱体中。这题卡了我很久。。一直以为是精度问题，没想
2016-11-04 16:55:00
702
转载 FFT
1、hihocoder1388（2016 acm 北京网络赛e题）给出等长的A,B序列，求input：293 0 1 4 1 5 9 2 65 3 5 8 9 7 9 3 251 2 3 4 52 3 4 5 1output：800解题思路：这题其实也是2个一维卷积的应用。公式可以化简为
2016-10-29 18:38:00
545
转载 ARM指令英文全称及功能
指令格式： 指令{条件}{S} {目的Register}，{OP1}，{OP2}"{ }"中的内容可选。即，可以不带条件只有目的寄存器，或只有目的寄存器和操作数1，也可以同时包含所有选项。“S” 决定指令的操作是否影响CPSR中条件标志位的值，当没有S时指令不更新CPSR中条件标志位的值 助记符英文
2016-10-27 14:50:34
4029
原创 HDU 4269 Buildings (贪心)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4296题意：有n个砖块，每个砖块有两个属性wi和si，将所有的砖块依次叠放起来，每个砖块得到一个值ti=sigama(W)-si，其中W为在第i块砖上面的砖的总w值之和。要求求一种叠放次序，使得max(ti)最小。一看就是一道贪心题。。可是方法怎么也想不到。。。看了许多写给会
2016-10-27 00:17:43
451
原创 HDU 4417 Super Mario (树状数组、离线处理)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4417题意：给n个数，数中有重复的。还有m个询问，问的是[L,R] 区间内有多少个数小于h,有多次询问。想到是树状数组但是没想出来怎么做。。。也不是第一次做离线处理的题了，可就是没往这里想。。。。不过队友用主席树也过了，应该不太简洁。贴一份比较清晰的解释：① 先把
2016-10-26 18:23:10
565
原创 HDU 4414 Finding crosses (暴力模拟)
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4414题意：在N*N的图中，找出孤立存在的十字架的个数。十字架要求为正十字，孤立表示组成十字架的‘#的周围的一格再无’#‘。这题告诉我们，暴力也是讲究技术的。。。。枚举十字架中心往四个方向看就行了。#include using namespace std;i
2016-10-25 12:46:44
424
原创 HDU 5115 Dire Wolf (区间DP)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5115题意：很多狼排成一排，每只狼有一个攻击值a[i]和附加攻击值b[i]。当你消灭一只狼时，你会受到这只狼的攻击值的伤害和它旁边两只狼的附加攻击值的伤害。求消灭所有狼的最小伤害值。区间DP，容易想，但是要处理好边界条件。dp[x][y] 表示 消灭区间[x, y]的狼最小花
2016-10-22 20:15:57
453
原创 HDU 5113 Black And White （dfs、剪枝）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5113题意：N*M的棋盘，K种颜色，每种颜色有c[i]个(sigma(c[i]) = N*M)，现在给棋盘染色，使得相邻的两个棋盘染成不同的颜色，并且把所有颜色用完。就像数独一样，因为棋盘比较小，可以想到用搜索写。不过爆搜会超时，需要一个强有力的剪枝。容易想到，当现在剩下的空格子数的
2016-10-22 18:49:59
507
原创 codeforces 732D Exams
题目连接：http://codeforces.com/problemset/problem/732/D题意：n天，m个考试，n天中的每一天，0代表该天不能考试，其他表示能考哪一门试。m个考试科目每科都有一定的准备时间，准备完了才能考，但不用连续准备。任意一非0的天可以选择考试或者准备考试，问在n天内完成所有科目所花的最少天数，如果不能考完，则输出-1。二分+贪心。二分枚举天
2016-10-18 18:30:08
718
原创 HDU 5033 Building （单调栈、计算几何）
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=5033题意：一条数轴上，n个建筑物，Q条询问，问所在的位置，看到天空的角度是多少，每条询问的位置左右必定是有建筑物的。参考博客：http://www.cnblogs.com/luyingfeng/p/4015378.html很厉害，有很多巧妙地思维我没想到。。。佩服
2016-10-15 11:11:41
874
原创 HDU 5512 Pagodas （博弈论、找规律）
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=5512题意：有n个庙经过长时间风吹雨打需要修补，只有两座（被标记为a，b）完好无损不需要修补，有两个和尚轮流去修补这n-2个庙，每个和尚每次只能修补一个庙标记为i，并要求i满足i=j+k或者i=j-k，每个庙只能被修建一次；其中j和k代表已经修建好的庙，Yuwgna先开始，问最后谁不能修建谁
2016-10-07 17:57:35
606
原创 HDU 5538 House Building （水）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5538题意：给一个m * n的物体的俯视图，求表面积。当搜索写的....果断超时。很水的一道题....经验不足每个柱子跟四周比较一下就可以了。#include using namespace std;int grid[55][55];int dir[
2016-10-07 17:53:29
421
原创 HDU 5533 Dancing Stars on Me （凸包）
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=5533题意：给n个点，问是否能构成正n多边形。求个凸包然后判断一下就可以了。#include #include #include #include #include #include #include using namespace std;const
2016-10-07 17:48:45
373
原创 PAT A 1013. Battle Over Cities (25)
题目连接：https://www.patest.cn/contests/pat-a-practise/1013并查集。#include #include #include #include using namespace std;const int maxn = 1010;struct node{ int u, v;};node edge[500050]; //边最多（n
2016-10-05 16:22:41
320
原创 codeforce 721C Journey (DAG上的dp)
题目链接：http://codeforces.com/problemset/problem/721/C题意：给一个DAG,问用不超过T的时间从1到n最多可以经过多少个点.要求输出一条路径;输入第一行n, m, t， n个点，m条边，时间为t。下面m行条边。看到是DP加上Graph我就滚去睡觉了....状态转移方程是这样的 dp[i][j]表示在经过了i个城市
2016-10-01 15:21:15
704
原创 POJ A Simple Problem with Integers （线段树区间更新区间查询模板）
题目链接：http://poj.org/problem?id=3468题意：N个数，Q个操作，操作有两种，‘Q a b ’是询问a~b这段数的和，‘C a b c’是把a~b这段数都加上c。#include #include #include #include using namespace std;typedef long long ll;struct nod
2016-09-30 20:03:44
384
原创 POJ 2828 Buy Tickets （线段树，插队问题）
题目链接：http://poj.org/problem?id=2828参考博客：http://blog.csdn.net/u013480600/article/details/22091129题意：n个人排队，他们是按顺序到达的，但是他们乱插队。每个人有两个值pos[i]和val[i]。比如现在第5个人来了，他的pos[5]值为3，那么他就会插队到当前第3个人位置的后面(第0个人是
2016-09-30 12:24:55
427
原创 HDU 1394 Minimum Inversion Number （求逆序对数）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1394题意：一个由0..n-1组成的序列，每次可以把队首的元素移到队尾，求形成的n个序列中最小逆序对数目。求逆序对数。方法就是按序列顺序逐个读取元素，每次读取都要查询当前已读取元素中大于当前元素的个数，加到sum里，最后得到的sum即为原始数列的逆序数。这样就是每读一个就
2016-09-29 17:56:25
426
转载 gnome快捷键
转自：http://blog.chinaunix.net/uid-27004869-id-3228965.html* 打开主菜单 = Alt + F1* 运行 = Alt + F2* 显示桌面 = Ctrl + Alt + d* 最小化当前窗口 = Alt + F9* 最大化当前窗口 = Alt + F10* 关闭当前窗口 = Alt + F4
2016-09-27 19:22:15
1849
原创 HDU 5904 LCIS (dp)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5904题意：给两个序列，要找他们的最长公共递增子序列，并且这个子序列的值必须是连续的(x,x+1,...,y-1,yx,x+1,...,y−1,y)这次BC全场最简单的一道题.....先dp两个序列中易每个数字结尾的最大的连续上升序列的长度。然后比对两
2016-09-26 20:16:17
503
原创 HDU 1724 Ellipse （simpson公式，求积分）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1724题意：题意很简单，给一个椭圆的 a, b。 让求l 到 r之间的面积。就是一个积分。可以用数学方法直接积分出来。 这里也可以用simpson自适应公式来求近似解。借张图：http://blog.csdn.net/linraise/article/details/
2016-09-26 17:19:49
653
原创 vim配置
colo slate set nu set hlsearch set expandtab set syntax=on set tabstop=4 set expandtab set shiftwidth=4 set smarttab set smartindent set showmatch set matchtime=0 s
2016-09-22 18:46:39
353
原创 HDU 5901 Count primes （求1e11内素数个数、模板题....）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5901题意：求不大于n的素数的个数。 n范围是1e11......为什么说是模板题呢？因为代码我看不懂....比赛时找了个模板改了改交上去，中间TLE MLE了好多次.....刚才看到大牛超短的代码....先保存下来....本弱看不懂啊....#i
2016-09-19 20:39:33
1293
原创 Codeforces 715A Plus and Square Root
题目链接：http://codeforces.com/problemset/problem/715/A 参考博客：http://blog.csdn.net/aozil_yang/article/details/52568152公式推的很漂亮。 题意：初始值x是2，按+按钮，数值加上此时的等级数k，也可以进行开方操作，当x是完全平方数时才可以开方，开方后的数值必须要求是等级的整数倍，开方之后就可以
2016-09-18 08:20:23
575
原创 Codeforces 716B Complete the Word
题目链接：http://codeforces.com/problemset/problem/716/B 题意：给一个字符串，问你这个字符串的所有子串中有没有一个长度为26的子串包含所有的26个大写字母。其中问号可以代表任意字符。 没有的话输出-1，有的话吧？补成字母后输出整个字符串。 Special Judge.就枚举瞎暴力，跑出来就随便打，跑不出来就-1.#include <iostre
2016-09-18 08:11:55
598
原创 codeforces 714B Filya and Homework (水）
题目链接：http://codeforces.com/problemset/problem/714/B题意：给一个正整数序列，问是否有一个x，使得一些数加上x，一些数减去x，然后整个序列所有的数相等。排序判断就行了。#include #include #include #include #include #include using namespace s
2016-09-14 21:08:59
667
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人