- 博客(149)
- 收藏
- 关注
RSS订阅
原创 Codeforces Round #524 (Div. 2) C. Masha and two friends(思维)
C. Masha and two friendstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputRecently, Masha was presented with a chessboard with a he...
2019-08-06 10:43:17
271
1
原创 关于BZOJ如何注册问题
更新于2019年5月26号。貌似现在BZOJ开放注册了______________________________________________________下载 Notepad++ 下载地址，https://notepad-plus-plus.org/完了之后 进入目录C:\Windows\System32\drivers\etc 用Notepad++打开hosts文件...
2018-12-16 21:26:17
1429
原创 编辑器的选择 西安电子科技大学第二届程序设计新生赛(同步赛)
链接：https://ac.nowcoder.com/acm/contest/316/C来源：牛客网题解:模拟；主要用到stringstream，可以分割字符串，然后还有一个换行读入，有了这些比较好处理一些，先看这段代码(简单解释)。 string one; while(getline(cin,one)){ stringstream a; ...
2018-12-09 09:07:43
357
5
原创 遇强则强 中北大学2018年新生赛
题解:傻逼单调栈。补充一下，利用单调栈，简单来说就是：可以找到从左/右遍历第一个比它小/大的元素的位置。具体看这个博客写的挺好的 还有相关的例题可以试着做一下https://blog.csdn.net/wubaizhe/article/details/70136174（最典型的单调栈例题就是求矩形面积的 POJ2559）。代码：#include <iostrea...
2018-12-02 19:13:11
511
原创 Wannafly挑战赛29 御坂美琴(递归，模拟)
链接：https://ac.nowcoder.com/acm/contest/271/A来源：牛客网御坂美琴时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 131072K，其他语言262144K64bit IO Format: %lld题解:对每一个数进行题述操作就ok,直到不能拆为止，对操作得到的数字，用map 标记一下(1表示可以得到，0表示得不到)，最后再...
2018-11-24 08:39:59
474
3
原创 2018NOIP复赛-普及组（民间数据）对称二叉树(递归)
链接：https://ac.nowcoder.com/acm/contest/277/D来源：牛客网时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262144K，其他语言524288K64bit IO Format: %lld题目描述一棵有点权的有根树如果满足以下条件，则被轩轩称为对称二叉树:1. 二叉树;2. 将这棵树所有节点的左右子树交换，新树和原树对...
2018-11-11 14:52:26
859
原创 2018NOIP复赛-普及组（民间数据）龙虎斗(简单模拟)
链接：https://ac.nowcoder.com/acm/contest/277/B来源：牛客网时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262144K，其他语言524288K64bit IO Format: %lld题解:模拟即可，更新最小值，记下下标。需要注意的是刚开始应该默认把士兵派到中立阵营，即s2=m。因为即便是小于也有可能派出去使得双方...
2018-11-11 10:06:12
4149
原创 关于flashfxp死活连不上服务器的解决方案(可能是这个问题，比较冷门)
大胆的试一试！！第一次连上了后来重装了次系统，什么也没了。下载了flashfxp死活连不上。后来换了个软件（xfpt）就连上了。下载地址：https://www.fixdown.com/soft/966.html在此之前，怀疑过用户名，密码，url，是否正确。21 端口是否打开。。弄了半天，终于。。用xfpt连上了，想起第一次也是用的xfpt连的，但是后来找xfpt下载，百度...
2018-11-10 20:59:44
7148
5
原创 道路铺设(NOIP2018)
链接：https://ac.nowcoder.com/acm/contest/273/A来源：牛客网题目描述春春是一名道路工程师，负责铺设一条长度为 n 的道路。铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 n 块首尾相连的区 域，一开始，第 i 块区域下陷的深度为 di 。春春每天可以选择一段连续区间 [L, R] ，填充这段区间中的每块区域，让其下陷深 度减少 1。...
2018-11-10 20:37:05
1731
原创 队列Q(Wannafly挑战赛19)
链接：https://ac.nowcoder.com/acm/contest/131/A来源：牛客网题目描述ZZT 创造了一个队列 Q。这个队列包含了 N 个元素，队列中的第 i 个元素用 Qi 表示。Q1 表示队头元素，QN 表示队尾元素。队列中的元素是 N 的一个全排列。ZZT 需要在这个队列上执行 P 次操作，操作分两种：FIRST X: 将元素 X 移到队头。LAST ...
2018-11-10 10:01:03
341
原创 Bubble Cup 11 - Finals [Online Mirror, Div. 2] C. Space Formula
传送门： C. Space Formulatime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputFormula 1 officials decided to introduce new competition....
2018-09-24 15:08:59
387
原创 ACM超时问题（Codeforces Round #442 (Div. 2)D. Olya and Energy Drinks）
上次听学长说，关于标记数组最好换成布尔型的，节约空间时间，一直不以为然，直到做到Codeforces Round #442 (Div. 2)D. Olya and Energy Drinks的时候一直在44组测试数据超时，花了超长时间才发现是标记数组类型这里拉长了时间QAQ。这次一定记住了！！！（跟普通走迷宫的不同之处在于能走多步而已）附上代码#include <iostrea...
2018-08-24 15:02:06
1255
原创 ZOJ 1450(最小圆覆盖)
题目链接：https://zoj.pintia.cn/problem-sets/91827364500/problems/91827364949上交NB！代码：# define _CRT_SECURE_NO_WARNINGS#include <cstdio>#include <cmath>#include <algorithm>#inclu...
2019-09-21 19:49:38
239
原创 poj2069/2018南京（最小球覆盖）
上交NB！POJ2069 题目链接：http://poj.org/problem?id=20692018南京（gym101981D） 题目链接：https://codeforces.com/gym/101981POJ2069 题意：比较裸，给你n个恒星在三维空间的位置，让你找到包含所有恒星的最小球体（每个恒星看成一个点），输出球体的半径。gym101981 D 题意：给你n个城市...
2019-09-21 10:55:29
255
原创 牛客小白月赛17 F小黄鸭(计算几何+积分+二分)
题目链接：https://ac.nowcoder.com/acm/contest/1085/F题解：根据，，可得①球的正视图是个圆心为（0，r），半径为r的圆，方程为②侵入水中的体积：体积公式是底面积×高，我们把圆形作为底面积，那么底面积为,即,可通过②式移项得，那么侵入水中的体积为,z是侵入水中的深度，上界的,即是我们要求的答案。积下来答案为，我们对z进行二分...
2019-09-14 21:14:22
885
原创 Codeforces 1217 D. Coloring Edges
题目链接：https://codeforces.com/contest/1217/problem/D题意：n个点m条边的有向图，没有重边，没有自环，用尽可能少的颜色给每个边涂色，使得所有环内的颜色不能为同一个颜色，这里的环是循环的环，即环上的每个点都能走到环上任意一点。题解：先判断是否存在环，直接用拓朴排序就行，对于能出现环的，只会存在两种边，小顶点指向大顶点，和大顶点指向小顶点，那么...
2019-09-11 20:17:58
472
原创 VK Cup 2017 - Round 2 -Voltage Keepsake（二分）
题目链接：https://codeforces.com/contest/772/my题意：有n个装置，每个装置每秒会消耗a能量，初始自带b能量，你可以在任意时间点，为任意一个机器充值能量，每秒能充值p能量，如果有一个装置能量为0，则游戏结束，问游戏最长持续时间，如果游戏不可能结束，那么输出-1。题解：二分时间，具体看代码。~代码：# define _CRT_SECURE_NO_W...
2019-09-06 20:50:43
150
原创 VK Cup 2017 - Round 2 B. Volatile Kite（假几何）
题目链接：https://codeforces.com/contest/772/problem/B题意：按顺序给出凸多边形的顶点，每个顶点都可以在区间[0，D]里任意移动，移动完之后使得这个图形还是一个凸多边形，求出最大的D值。题解：看图，显然答案为代码：# define _CRT_SECURE_NO_WARNINGS#include <iomanip>...
2019-09-06 19:27:17
208
原创 2018年ICPC徐州现场赛M - Rikka with Illuminations（计算几何+贪心）
菜鸡终于写出来了题目链接：https://codeforces.com/gym/102012/problem/M题意：按逆时针方向给你n个凸多边形的顶点，在凸多边形的外侧给你m个点光源，用最小的点光源照射到所有的边，输出光源序号。题解：每个点光源照射的边的一定是连续的，那么就可以转化为区间覆盖问题，先处理每个点光源的最大覆盖区间（可以用叉积解决），然后贪心做就行啦。时间复杂度p...
2019-09-03 21:23:51
865
原创 Codeforces 934 E. A Colourful Prospect（计算几何+并查集+欧拉定理）
题目链接：https://codeforces.com/contest/934/problem/E题意：给你若干个圆形，求出平面区域被分成多少部分？题解：根据欧拉定理 F=E-V+C+1，E是边数， V是交点，C是连通块的数量，1是常数，等于没说，E是每个圆上的交点数，V是去重之后的交点数，C通过并查集可的，具体看代码。从我的代码debug的注释中，可以得知这是一个悲伤...
2019-08-31 20:09:31
449
原创 Codeforces 1207 D. Number Of Permutations（组合数学+容斥）
话说csdn什么时候把文章标签强制换成专栏了？题目链接：https://codeforces.com/contest/1207/problem/D题意：有n个pair，只要这个序列的第一个元素或者第二个元素是非降有序的，那么这个序列就是bad的，你可以打乱顺序，问这个序列是good的个数，输出这个个数。题解：艹，总的是，假设是num，满足第一个关键字是非严格递增有序的序列的个数为所有...
2019-08-29 22:37:35
479
原创 Codeforces 1207 C. Gas Pipelin（线性DP）
C. Gas Pipeline题意：略题解：艹，表示到第根柱子，且柱子高度为的最小花费，为0代表柱子高度为1，为1表示柱子高度为2，字符串的长度为n，一共有n+1根柱子，柱子编号为1到n，则有初始条件，其余初始化为,考虑是否为‘0’，是的话两种高度的柱子都可建造，否则只可建造高度为2的柱子，答案为，时间复杂度为代码：# define _CRT_SECURE_NO_WAR...
2019-08-29 20:14:14
224
原创 That Nice Euler Circuit UVALive - 3263（线段规范相交+欧拉定理）
题目链接：https://cn.vjudge.net/problem/UVALive-3263题意：平面上有一个包含n个端点的一笔画，第n个端点总是和第一个端点重合，组成的一笔画的线段可以相交，但是不会部分重叠，求这些线段将平面分成多少个部分（封闭区域，无限大区域）。题解：原先有n个顶点，n条边， 求出所有线段的规范交交点，这些交点和原先的顶点去重之后就是图形所有顶点，然后判断规范交的交点...
2019-08-24 20:44:18
133
原创 Corporative Network UVALive - 3027 （并查集）
题目链接：https://cn.vjudge.net/problem/UVALive-3027题意：有n个结点，初始时每个结点的父节点都不存在，有两种操作，I，u，v把节点u的父结点设为v，距离为|u-v|%1000，E，u输出u到根节点的距离。题解：并查集，每次查询需重新更新距离。代码：# define _CRT_SECURE_NO_WARNINGS#pragma G...
2019-08-24 14:37:05
114
原创 X-Plosives UVALive - 3644（并查集）
题目链接：https://cn.vjudge.net/problem/UVALive-3644题意：每个化合物由两个元素组成，装箱工人按顺序装化合物，当车上存在k个化合物，正好k种元素时，那么他们组成易爆混合物，那么不能装车，求出不能装车的化合物的数量。题解：休闲，一个元素是一个点，一个化合物就是一个边，当形成环的时候不能装。代码：# define _CRT_SECURE_NO_...
2019-08-24 10:29:09
125
原创 Art Gallery UVALive - 2512（半平面交）
題目鏈接：https://cn.vjudge.net/problem/UVALive-2512題意：有一个n边形，管理者想在里面放一个监视摄像机，能够看到整个画廊，计算有多大面积的区域能放这个摄像机。題解：自闭了，写一道休闲题，给自己一点信心，半平面交的面积就是答案。代码：# define _CRT_SECURE_NO_WARNINGS#pragma GCC optim...
2019-08-23 21:49:05
161
原创 Wall UVALive - 2453（凸包周长）
题目链接：https://cn.vjudge.net/problem/UVALive-2453题意：给定一个N边形城堡，在他的外部建造一个总长度尽量小的围墙，使得围墙的任何一部分离城堡的距离不小于L，如图题解：休闲题，凸包周长加一个半径为L的圆的周长。因为长度要尽可能小，所以每个凸包的顶点都是一个圆弧，顶点到圆弧的最边上的点与顶点的连线必然与凸包的边垂直，那么有凸包顶点...
2019-08-23 20:26:35
186
1
原创 Surround the Trees HDU1392（二维凸包周长）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1392题意：求凸包周长题解：休闲题代码：# define _CRT_SECURE_NO_WARNINGS#pragma GCC optimize(2)#include <iostream>#include <algorithm>#include <...
2019-08-23 10:48:52
116
原创 Lifting the Stone HDU1115（凸包重心）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1115题意：凸包重心。题解：罗永军牛逼代码：# define _CRT_SECURE_NO_WARNINGS#pragma GCC optimize(2)#include <iostream>#include <algorithm>#include &l...
2019-08-22 22:13:05
207
1
原创 Triangle Fun UVA - 11437（二维几何基础）
题目链接：https://cn.vjudge.net/problem/UVA-11437题意：给三角形ABC,在边BC，CA，AB上分别取点D,E,F，使得CD=2BD，AE=2CE，BF=2AF，求三角形PQR的面积。题解：通过直线交，求出交点，P，Q，R，然后通过叉积公式，求出三角形面积，水一篇代码：# define _CRT_SECURE_NO_WARNINGS#pr...
2019-08-22 20:32:55
105
原创 2019牛客暑期多校训练营（第三场） J LRU management（模拟）
题目链接：https://ac.nowcoder.com/acm/contest/883/J题意：略题解：map 加 list 模拟代码：#include <bits/stdc++.h>#define inf 0x3f3f3f3f#define Pair pair<int, int>#define int long long#define fir...
2019-08-22 15:18:47
135
原创 2017ICPC北京现场赛G Liaoning Ship’s Voyage（BFS+点在多边形内判定）
题目链接：https://cn.vjudge.net/problem/HihoCoder-1633题意：有一个nxn的海域，海域上有两类点，一种是点，一种是#，#不可以走，还有给你三个顶点坐标（可能是小数），表示百慕大三角，百慕大三角上的边和顶点可以走，里面不能走，小船可以走8个方向，上下左右，还有四个角，问从左下角走到右上角的最小步数。题解：普通的一个跑图，加一点几何，我们发现，如果某一...
2019-08-22 10:17:05
292
原创 2018年沈阳现场赛 L. Machining Disc Rotors（二维凸包+旋转卡壳）
题目链接：https://codeforces.com/gym/101955/problem/L题意：圆心处有一个大圆，用若干个圆去切割这个大圆，问剩下的图形的直径，也就是图形上的点的最大距离。如图紫线就是所求。题解：一眼看上去，凸包绝对可做，可能别的方法也可做，但会更快。一眼看上去，我们不考虑特殊情况下，那么先求出所有交点，然后对交点作凸包，在凸包上求最大距离，求凸包的...
2019-08-20 20:32:41
309
原创 Treblecross UVA - 10561（博弈论-SG函数）
题目链接：https://cn.vjudge.net/problem/UVA-10561题意：有n个格子排成一排，其中一些格子里面有字符X，两个游戏者轮流操作，每次可以选一个空格，在里面放字符X，如果此时有3个X连续X出现，则该游戏者赢得比赛，判断先手必胜还是必败，如果必胜输出所有毕生策略。题解：初始局面下，一个X的左两个到右2个都不能放，这些都是禁区，一旦放，那么先手必败，这样我们先处理...
2019-08-19 20:10:00
155
原创 Playing With Stones UVALive - 5059（博弈论-SG函数）
题目链接：https://cn.vjudge.net/problem/UVALive-5059题意：有堆石子，两个游戏者轮流操作，每次可以选一堆，拿走至少一个石子，但不能拿走超过一半的石子，先手胜，输出，否则输出。题解：跟游戏，很相似，我们的第一思路是想求出单堆的函数，但由于每一堆的石子数量达到了，无法求出直接求出单堆的函数，但是通过打表可以发现，当单堆石子数量为偶数时候,数量为奇数时，得...
2019-08-19 10:58:01
159
原创 Cheerleaders UVA - 11806 （组合数学+容斥原理）
题目链接：https://cn.vjudge.net/problem/UVA-11806题意：有一个n行m列的矩形网格里放k个相同的石子，问有多少种方法，每个格子最多放一个石子，所有石子都要用完，并且第一行，最后一行，第一列，最后一列，都得有石子。题解：容斥，用二进制表示所有的状态，每一位分别代表第一行，最后一行，第一列，最后一列的状态，0代表放，1代表不放，有0000到1111个...
2019-08-16 22:18:17
191
原创 Exploring Pyramids UVALive - 3516/AcWing 284. 金字塔（区间DP）
题目链接：https://cn.vjudge.net/problem/UVALive-3516https://www.acwing.com/problem/content/286/题意：一颗多叉树，从根节点出开始，每次尽量往左走，走不通就回溯，把遇到的字母顺次记录下，可以得到一个序列，问你有多少种棵树与之对应。题解：表示对用的子树的个数，边界条件是因为子树的入口和出口必然相同，...
2019-08-16 21:53:48
141
原创 2019杭电多校训练营第一场 M - Code HDU - 6590 （凸包，凸包交）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6590题意：由于这道题题面很长，说了一堆花里胡哨的东西，脱掉华丽的外表就是一个二维凸包判断是否有交集。简单题意：有两类点，每个点有三个参数，，就是一般的,也就是,用区分两类点，问是否有一条直线把这两类点划分成两个区域，直线不能穿过任意一个点。详细解释一下。样本长这样，其中是一个维...
2019-08-16 09:54:06
238
原创 The Great Divide UVA - 10256（二维凸包，凸包交）
题目链接：https://cn.vjudge.net/problem/UVA-10256题意：平面上有n个红点，m个黑点，是否存在一条直线，使得任取一对红点和蓝点都在直线的异侧，这条直线不能穿过红点或者黑点。题解：分成两个点集，分别求凸包，然后判断两个凸包是否有交集，判断如下：任取红凸包上一条线段和蓝凸包上的一条线段，判断两者是否相交，端点交也算交。任取一个红点，判断是否在蓝凸包的...
2019-08-15 22:27:51
238
原创 Jungle Outpost UVALive - 4992（贪心+二分+半平面交）
题目链接：https://cn.vjudge.net/problem/UVALive-4992题意：有n个瞭望台，形成一个凸多边形，这些瞭望台的保护范围就是凸边形内的任意一点，敌人进攻时，会炸毁一些了瞭望台，使得总部暴露在那些剩下的瞭望台的凸包之外，要求选择一个点作为总部，是的敌人需要炸毁的瞭望台数量尽可能的多，题解：这是一个最小值最大化的问题，考虑敌人如何能用最少的炸弹，使得剩下的瞭...
2019-08-15 10:35:25
153
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人