smwqd_yehua_cx-CSDN博客

原创 Gym 100962G Green Day （K个生成树构造1个完全图 -- 找规律）

题意：这道题的题意实际上就是用K个有N个节点的生成树构成一个完全图。思路：N个点的完全图共有N*(N - 1) / 2条边，N个点的生成树共有(N - 1)条边，共K个这样的生成树，故一共需要K * (N - 1)条边，要用这些边构成一个完全图，故需满足K * (N - 1) == N*(N - 1) / 2，解得N = 2 * K，其中不难发现每个节点只能做一次开始或结束的点。场上也想到这里

2017-11-13 17:09:18 448

原创 2017 CCPC西安总结

想了两天，也不知道这次总结该怎么开头，想写自己真实的所思所想又怕跑题，想来想去还是顺遂了自己的内心。深夜的山科万籁俱寂，只有耳机里流淌的音乐和手机屏幕闪现的光亮陪伴着自己。我喜欢夜死一般的寂静，可以什么都不用想什么都不用怕静静地做自己。想想自己这两年多来的经历，有种五味杂陈的感觉。说实话这次去西安对我来说是一场意外，如果不是因为山科突然多了一个名额，如果不是教主出了一场特殊的c类名额选拔赛让更多还

2017-11-01 13:17:34 370

原创 Appearance Analysis UVALive（模拟）

题目链接：https://vjudge.net/problem/UVALive-7747题意：给定r*w的图，包含若干窗户，每个窗户由“.”或“+”组成，每个窗户大小相等（矩形非正方形），相邻窗户间有“#”间隔开，大矩形的外围也是一圈“#”，求一共有多少种不同的窗户。若一个窗户经过旋转0 90 180 270或360度能与另一个窗户完全重合，则认为这两个窗户是同一种窗户。思路：我是直接模拟

2017-08-31 10:45:24 310

原创敌兵布阵（树状数组模板题）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1166中文题，直接套树状数组模板即可。代码如下：#include#include#include#include#include#include#include#include#include#include#include#includeusing namespac

2017-08-30 10:07:51 388

原创 Foreign Postcards Gym - 101190F（概率DP）

题目链接：https://vjudge.net/problem/Gym-101190F题意：一开始共有n个卡片，C代表摆放正确，W代表摆放错误，每次可以选取前k张卡片，如果这k张卡片中的第一张是W，则将这k张卡片全部翻转后放在桌面上（翻转即C变W，W变C），如果第一张是C则不进行任何操作直接将这k张卡片放在桌面上，然后再在剩下的卡片中重复进行上述操作，直至所有卡片都放在桌面上了。思路:场上

2017-08-29 21:40:41 433

原创 Hard Refactoring Gym - 101190H（模拟区间合并）

题目链接：https://vjudge.net/problem/Gym-101190H题意：简单的区间合并，输出合并后的区间，如果合并后区间为空集输出false，若为(-inf, +inf)则输出true，否则输出合并后的区间范围。思路：模拟即可，队友写的代码。代码如下：#include#include#include#include#include#include#i

2017-08-29 19:00:26 300

原创 Abbreviation Gym - 101190A（模拟）

题目链接：https://vjudge.net/problem/Gym-101190A题意：恶心的模拟题，写了两个多小时，最后少写了一行代码就一行！！！！结果一直错，最近真是太浮躁了这样低级的错误都会犯，弄得我一下午心情都很郁闷。题意就是规定一类单词：首字母大写，之后有一个或多个小写字母。如果这类单词之间只由一个空格间隔，则可以用每个单词的大写字母组成这些字母的缩写，输出缩写+空格+(+原来的

2017-08-29 18:38:21 759

原创 Error Curves UVA - 1476 （三分）

题目链接：https://vjudge.net/problem/UVA-1476题意：S(x) = a * x ^ 2 + b * x + c，给定n个a b c的值从而确定n个S(x)方程式，F(x) = max(Si(X)),求F(x)最小值。思路：看到S(x)定义发现其是一个先减后增（凹函数）的函数(0 代码如下：#include#include#include#inc

2017-08-29 09:29:27 236

原创 Argus UVA - 1203（排序优先队列）

题目链接：https://vjudge.net/problem/UVA-1203题意：给定若干行信息，每行包含字符串s，整数ID-number，整数period，代表s在ID-number时刻产生，自此每隔period产生一个s。求前n个信息分别是什么。思路：求出每个s产生的n个信息分别对应哪个时刻，将所有的信息按时刻从早到晚排序，输出前n个#include#include#inclu

2017-08-29 09:15:51 303

原创 Robot Race UVALive - 7020（几何数学判断钝角）

题目链接：https://vjudge.net/problem/UVALive-7020题意：按顺序给定n个点的坐标，问有没有一个点到第三个点的距离小于第二个点到那第三个点的距离，切第二个点在第一个点之后，有存在输出Unfair，反之输出Fair。思路：判断相邻点与他们后面其他点之间会不会组成钝角，若会则Unfair，反之Fair。代码如下：#include#include#i

2017-08-24 20:45:14 302

原创 Dragons UVALive - 7018（二分 + 并查集）

题目链接：https://vjudge.net/problem/UVALive-7018题意：n个城市之间有m条路。共有K条龙，第Ki条龙住在Ci城市，初始有Si个头，只要他活着（头的数目不为0）每分钟会长出Ni个头。现要雇佣x名猎人去杀龙，每分钟每个猎人有两种选择：（1）在当前城市砍去龙的一个头；（2）沿着路去往相邻城市。求x的最小值。思路：二分判断mid是否是最小的可行解。由于城市间共

2017-08-24 20:40:03 232

原创 Elevators UVALive - 7015 （水最短路）

题目链接：https://vjudge.net/problem/UVALive-7014题意：对于一个S条提交记录的榜，判断其最早成为符合要求的榜的时间，即最早从符合要求的榜变成不符合要求的榜的时刻，若没有，输出“--:--:--”。符合要求的榜要求如下：（1）所有队伍都出题了；（2）没有队伍AK；（3）所有题目都有队伍做出来了；（4）没有题目被所有队伍做出来。思路：首先将S条提交记录按时

2017-08-24 20:24:38 457

原创 Elevators UVALive - 7015 （水最短路）

题目链接：https://vjudge.net/problem/UVALive-7015题意：n个电梯，每个电梯只能在特定的楼层停，若不换乘电梯，则从楼层x到楼层y所花费时间为abs(x-y)，在某一楼层换乘电梯不消耗时间。求从当前所在楼层到目的楼层所需最小时间。思路：输入中给的同一电梯相邻楼层建边，floyd求一次最短路，然后直接输出即可。代码：#include#include

2017-08-24 20:19:23 265

原创 Working Hours UVALive - 7017（简单模拟）

题目链接：点击打开链接思路：将所有时间化成分钟进行加减计算，输出时再转化成h:mm的形式即可。代码：#include#include#include#include#include#include#include#include#include#include#include#include#include#include#includeusing na

2017-08-24 20:07:00 207

原创 Web Colors UVALive - 7013（水题带公式）

题目链接:https://vjudge.net/problem/UVALive-7013#include using namespace std;string s[20] = {"White", "Silver","Gray", "Black", "Red", "Maroon", "Yellow", "Olive", "Lime", "Green", "Aqua", "Teal", "Bl

2017-08-24 20:04:29 181

原创 The Closest Pair Problem UVA - 10245（暴力）

题目链接：https://vjudge.net/problem/UVA-10245题意：n个点，求距离最近的两点之间的距离，若没有距离小于10000，则输出INFINITY。思路：直接暴力代码如下：#include#include#include#include#include#include#include#include#include#include#in

2017-08-23 17:16:31 198

原创 Circum Triangle UVA - 11186（n^3暴力或n^2容斥推理）

题目链接：https://vjudge.net/problem/UVA-11186题意：给定一个圆的半径，圆心为(0,0)。给定圆上n个点，圆上任意三个点比不共线，任意三点均可以组成三角形，求能组成的所有三角形的面积之和。思路：直接n^3枚举所有的三角形，对面积求和即可；n^2容斥推理也可以，参考的是这个博客http://blog.csdn.net/shimmer_/article/det

2017-08-23 17:10:31 310

原创 Watering Grass UVA - 10382 （几何图形贪心）

题意：给定一个L*W的矩形和若干圆，求最少用多少圆能够将矩形区域全部覆盖。若无解输出-1，否则输出最小的数目。思路：贪心思路，每次设定当前已覆盖的区域最右侧边界x，每次找l=x中r的最大值，计数加一，x更新为r。写的时候一直出错是一直当圆形看，其实最简单的方法就是求出每个圆占据的L*W大矩形区域的小矩形面积l*W，将n个圆转化成n个矩形。（若圆的直径小于等于W，怎该圆无法占据矩形区域，忽略此圆

2017-08-23 16:52:43 206

原创 Yet Another Median Task Gym - 100741G （nth_element找中位数）

题目链接：https://vjudge.net/contest/181019#problem/G题意：给定一个n*n的矩阵，有q次查询，每次查询给定四个数x1 y1 x2 y2，求矩形区域 x1 思路：若每次对小矩形区域内的所有数进行排序找出中位数，则肯定会超时。STL中有一个函数ntn_element(a, x, a + n)，用于使数组a中n个数中第x大的数位于第x个位置，x左边的数都

2017-08-23 16:09:44 188

原创 Basketball Gym - 100741L （简单dfs）

题目链接：https://vjudge.net/contest/181019#problem/L题意：A队有n个人，给出每个人对应的值；B队有m个人，给出每个人对应的值。能否从AB队各选出若干人使其值的和相等。思路：将A队选或不选每个人得的所有和计算出来，B队也是，最后看有多少相等的即可。代码如下：#include#include#include#include#inclu

2017-08-23 01:31:13 231

原创 $n$-Way Tie Gym - 100741K（水题推结论）

题目链接：https://vjudge.net/contest/181019#problem/K题意：n个人两两进行pk,共进行n*(n-1) / 2场，胜方得1分，败方得0分，问是否能确定每场比赛的结果使得所有比赛结束后n个人得分相同。思路：只有奇数个人时才有可能，此时共进行n*(n-1) / 2场比赛，每个人得分均为(n*(n-1) / 2) / n = (n - 1) / 2。代

2017-08-23 01:20:32 175

原创 Gym - 100741F（二分匹配矩阵斜线线与值进行匹配）

题目链接：https://vjudge.net/contest/181019#problem/F题意：给定一个n*n的矩阵，从左下至右上平行于对角线的斜线共2*n-1条（包括对角线），在每条斜线上选取一个出现的值，要求这2*n-1条斜线选取的值互不相同，求是否能选取，若不能，输出NO，若能，输出YES并按1~2*n-1的顺序输出每条斜线上选取的值。思路：从左下至右上为这些斜线编号为1~2*

2017-08-23 01:15:15 443

原创 Xor Sum Gym - 100741D （异或超水题）

题目链接：https://vjudge.net/problem/Gym-100741D题意：求n个数中出现次数为奇数次的所有数的异或值。思路：水题，同一个值，异或两次相当于没有进行异或，所以不用求出现次数为奇数还是偶数，直接全部异或就行。代码如下：#include#include#include#include#include#include#include#incl

2017-08-23 01:07:48 271

原创 Personal programming language Gym - 100741B（dfs）

题目链接：https://vjudge.net/contest/181019#problem/B题意：定义函数，若 def a = value则a就是value；若def a = valuea def b with a = valueb则b为valueb valuea；若def a = valuea def b with a = valueb def c with b with a =

2017-08-23 01:03:57 165

原创 Queries Gym - 100741A （用结构体存10个树状数组）

题目链接：https://vjudge.net/contest/181019#problem/A题目描述：给定n和m，对于n个数字，进行下列三种操作：（1） + p r ：将p位置的元素加上r，输出此时p位置的值；（2） - p r ：将p位置的元素减去r，若p位置的值小于r则不进行减法，输出此时p位置的值；（3) s l r mod：求区间[ l, r ]中值%m == mod的

2017-08-23 00:51:31 228

原创 Guess UVA - 1423（拓扑排序）

题目链接：https://vjudge.net/contest/180830#problem/F题意：给定一个长度为（n + 1） / 2的串一次表示sum(i,j)的正负，1 思路：对区间和sum进行拓扑排序。设sum[x]为1~x的和，若sum(i,j) > 0则表示sum[j] - sum[i - 1] > 0即sum[j] > sum[i -1]；若sum(i,j) 代码如下：

2017-08-21 20:16:55 241

原创 Guardian of Decency UVA - 12083 （二分匹配）

题目链接：https://vjudge.net/contest/180830#problem/C题意：n个学生，老师想带一部分学生出去但是又怕还有人发展为情侣，满足下列条件之一不会成为情侣：（1）二人身高差大于40cm；（2）二人同性；（3）二人喜欢不同的音乐；（4）二人喜欢相同的运动。求老师最多可以带多少人出去。思路：在男女可能发展为情侣的人之间建边，求出该二分图的最大匹配数，用总人数减

2017-08-21 20:07:19 163

转载树状数组学习

转载自：http://blog.csdn.net/int64ago/article/details/7429868引用请注明出处：http://blog.csdn.net/int64ago/article/details/7429868 写下这个标题，其实心里还是没底的，与其说是写博帖，不如说是做总结。第一个接触树状数组还是两年前，用什么语言来形容当时的感觉呢

2017-08-19 09:55:40 127

原创 Stars POJ 2352（简单树状数组）

题目链接：http://poj.org/problem?id=2352题目描述：给定n个星星的(x,y)坐标，定义每个星星(x,y)的level值为在左下角的星星(x0 思路：输入保证了y值一定是非递减的，这样只要考虑x值就好，对于第i个星星，计算其前面(i - 1)个星星中x值小于它的星星数量就是其level值。用树状数组更新值和求和即可。代码如下：#include#inclu

2017-08-18 23:43:48 183

原创 Movie collection UVA - 1513（树状数组模板题）

学习时参考了这篇文章，看完基本就能弄懂树状数组是怎么回事了：http://blog.csdn.net/int64ago/article/details/7429868题目链接：https://vjudge.net/contest/180021#problem/D题目描述：一开始共有编号1~n共n张影片从上之下排列，每次抽出一张影片x，求抽出时影片x上面有几张影片，每次将抽出的影片放在最上面

2017-08-18 21:13:06 222

原创 Corporative Network UVA - 1329（并查集的修改与查询）

题目链接：https://vjudge.net/problem/UVA-1329题目描述：给定n个点，一开始其父节点都是其自身。两个直接相连的结点uv间的距离是abs(u - v) % 1000。进行两种操作，E i 代表查询i到其父节点的距离，I i j表示将i的前驱结点设为j（i j直接相连）。其实也就是修改了一些父节点的值，求某个结点到根节点的距离。在贴场上写的AC代码前突然想到一组样例

2017-08-18 17:01:36 293 1

原创 Playing with Numbers（Kattis - playingwithnumbers）（预处理瞎搞）

题目链接：https://vjudge.net/problem/Kattis-playingwithnumbers题目描述：给定n组a b的值，每组表示一个数值2^a*3^b，共进行n次操作，第i次操作可以进行i-1次gcd操作和 n - i次lcm操作，求每次操作后所得最大值及最小值对应的ab分别是多少。每次选取任意两个数进行gcd操作时，只将结果放回这些数字中，lcm也是。思路：当至少

2017-08-18 15:37:54 343

原创 Zhu and 772002 HDU - 5833 （高斯消元求异或方程组解的个数）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5833题目描述：给定n个数，每个数所含质因子最大不超过2000，选取任意个（至少为1个）数字相乘，要求所得乘积为完全平方数，求共有多少种选取方案。思路：题目都已经说每个数所含最大质因子不超过2000了，很明显是要分解质因子求解，求的2000以内的素数共303个。要想相乘组成完全平方数，只要所选取

2017-08-18 15:04:34 546

原创开关问题 POJ 1830（高斯消元求解的个数）

题目链接：http://poj.org/problem?id=1830题目描述：中文题，POJ上的描述是：有N个相同的开关，每个开关都与某些开关有着联系，每当你打开或者关闭某个开关的时候，其他的与此开关相关联的开关也会相应地发生变化，即这些相联系的开关的状态如果原来为开就变为关，如果为关就变为开。你的目标是经过若干次开关操作后使得最后N个开关达到一个特定的状态。对于任意一个开关，最多只能进行一

2017-08-17 23:45:22 792

原创 2017杭电女生赛总结（2017/5/11）

2017杭电女生赛总结从离开学校去杭州那天算起到今天已经一个星期了，一个星期前我们六个人冒着雨一大清早便出发了。第一次没有老师的带领自己去那么远的地方，虽然我是个顶级路痴，但是因为有队友在所以我一点都不担心自己丢在半道上回不来，跟她们一起出去很安心。到了杭州后成功入住酒店然后去吃饭报道，一切都挺顺利的。上次来杭州参加cccc时因为不会骑自行车所以打车去的地铁站，回来后我

2017-08-15 12:10:39 545

原创 2017山东省赛总结（2017/5/11）

2017山东省赛总结之前写了一份总结存在U盘里，今天打开想接着写时发现它完美的消失了，唉......我也很绝望啊，总是这么粗心大意的。省赛结束三天了，喜悦也好失落也好这些情绪现在都没那么强烈了，虽然两金两银三铜的成绩与去年学长们四金一铜相比真的不是很好，但1864队的学长们力挽狂澜让冠军的荣耀重回山科还是很振奋人心的，我打心底里敬佩他们三位。由于参加女生赛我们没有打6号的热身赛，6号晚上

2017-08-15 12:09:24 359

原创 2017天梯赛决赛总结（2017/4/19）

cccc决赛总结这次去杭州是我第一次坐火车去那么远的地方，在火车上感觉很新奇很奇妙的感觉。我想如果不是加入了ACM，我应该不会有这么多出门打比赛锻炼自我的机会吧。去的路上还是比较轻松的，跟朋友们打打牌，看会书复习一下数字逻辑睡一觉就到了。和团队在一起的好处就是永远不用担心下一步该怎么办，该做什么，只要做好自己的本分不脱离队伍不给队长和队友添麻烦就行。不过一路看着老师和康神忙前忙

2017-08-15 10:41:24 473

原创天梯赛决赛总结（二）（2017/4/21）

关于比赛过程的回忆与描述在上一篇总结中大概写的差不多了，记得写的时候是在课上，急着写完总结赶紧补这几天的作业，总结虽然写了很多字但是潜意识里还是有应付的想法，这一点让现在的我感到羞愧不已。其实我最近状态不太稳定还是挺容易胡思乱想的，在去的火车上就在想，这次杭州之行我到底是来体验坐硬卧出远门旅行的感觉的，还是来体会一些其他东西的。很显然我绝不仅仅是为了前者

2017-08-15 10:37:00 381

原创 2017天梯赛初赛总结（2017/3/31）

今天下午在青大的天梯赛由于服务器崩溃的原因向后推迟了70分钟，等待期间也认识了旁边两个人，左边是山财15级男生，右边是山理工13级男生，拿过去年区域赛青岛赛区金奖，他当时做了六道题，666，我打心底希望这样的人不要参加今年省赛，否则压力真的很大。等待的那一个小时敲了四五个板子：kruskal、并查集、kpm、dijkstra等，当时想的是反正闲在那就当是练练手熟悉一下键盘吧，

2017-08-15 10:35:23 342

原创 2016区域赛青岛赛区总结（2016/11/15）

区域赛青岛赛区总结第一次作为正式军参加大型比赛，虽然有过省赛的经验，但还是免不了有些激动。出去两天和队友们相互鼓励，互相照应着，虽然打了铁有些遗憾，但是还是很珍惜这次比赛经验。我算是点儿比较背，出去两天有一天多身体不舒服，幸亏队友们还有ZJ, QPF和WS一路对我的照顾，帮我打热水，让我背较轻的包，一路配合我的速度慢慢走……这些虽然不应算比赛总结，但真的让我感受到了集体的温暖与力量，很感谢

2017-08-15 10:24:23 277

空空如也

空空如也