- 博客(41)
- 收藏
- 关注
RSS订阅原创 2019_GDUT_专题训练 数论 C---A/B
C—A/B原题链接：https://vjudge.net/problem/HDU-1576/origin题目大意：题目分析：模运算中，有加的：(a+b)%c == a%c + b%c减的：(a-b)%c == a%c - b%c乘的：(a*b)%c == a%c * b%c就是 没有 除的：(a/b)%c == (a%c)/(b%c) … …(错误！错误！错误！)但定义了逆元：...
2020-03-14 19:31:18
161
原创 2019_GDUT_新生专题 数论---B Fedya and Maths
B—Fedya and Maths原题链接：https://vjudge.net/problem/59949/origin题目大意：题目分析：(1n+2n+3n+4n) mod 5 == (1n mod 5 + 2n mod 5 + 3n mod 5 + 4n mod 5) mod 5所以运用 费马小定理：p为质数，a不是p的倍数时，ap-1mod p == 1这里距离 2n mod...
2020-03-14 16:13:56
235
原创 2019_GDUT_新生专题 数论---A
A — k-rounding原题链接：https://vjudge.net/problem/1077397/origin题目大意：题目分析：首先，n*10k 肯定是满足的，但是它不一定是最小的。由于10k == 2k*5k，n==m*2p*5q，所以答案就是：m*2max(k,p)*5max(k,q) ==n*10k/gcd(n,10k)。代码实现：#include <iost...
2020-03-14 15:05:26
154
原创 2020.2.25GDUT寒假训练排位赛3-B
B — Loan Repayment题目大意：农场约翰欠贝西N加仑的牛奶(1≤N≤1012)。他必须在K天内给她牛奶。然而，他不想过早地把牛奶送人。然而，他必须有点进展，所以他必须每天至少给贝西M加仑牛奶(1≤M≤1012)。农夫约翰决定如何偿还贝西。他首先选择一个正整数X，然后每天重复以下步骤:假设农民约翰已经给了贝西G加仑，计算(N - G)/X四舍五入，记为Y。如果Y小于M，则Y为M。...
2020-03-02 10:56:56
288
原创 2020.2.25GDUT寒假训练排位赛3-A
A — Wormhole Sort题目大意：农夫约翰的奶牛已经厌倦了他每天早上离开牲口棚前要它们自己整理的要求。奶牛他们刚刚完成了量子物理学博士学位，准备加快速度。今天早上，和往常一样，农夫John的N头奶牛(1≤N≤105)，编号为1…N，分散在谷仓的N个不同的位置，也编号为1…N，这样奶牛i就在pi的位置。但今天上午有M个虫洞(1≤M≤105)，编号1…M，其中虫洞i双向连接位置ai和位...
2020-03-02 10:37:58
207
原创 2020.2.25GDUT寒假训练排位赛3-E
E — Word Processor题目大意：奶牛贝西正在为她的写作课写论文。由于她的字写得很糟，她决定用文字处理机把这篇文章打出来。文章包含N个单词(1≤N≤100)，以空格分隔。每个单词的长度在1到15个字符之间，所有字符只包含大写或小写字母。根据作业要求，论文的格式为：每行不超过K(1≤K≤80)个字符，不包括空格。幸运的是，贝西的文字处理软件可以满足这一要求，它采用了以下策略：如果...
2020-02-27 16:37:15
238
原创 2020.2.25GDUT寒假训练排位赛3-D
D — Race题目大意：贝西正在进行一场长度为K(1≤K≤109)米的赛跑。她刚开始以每秒0米的速度跑。在给定的一秒内，她可以把速度提高1米/秒，或者保持不变，或者降低1米/秒。例如，在第一秒，她可以把速度提高到1米/秒，然后跑1米，或者保持0米每秒，然后跑0米。贝西的速度永远不会降到0以下。贝西总是跑向终点线，她希望在整数秒后完成(在这个整数秒内结束或超过终点线)。此外，她不想在终点线跑...
2020-02-27 16:36:52
272
原创 2020.2.25GDUT寒假训练排位赛3-H
H — PhotoShoot题目大意：Farm John正在给他的N头奶牛排队(2≤N≤103)，编号1…N，以便拍照。FJ最初计划将左边的第i只牛作为编号为ai的牛，并在一张纸上写下了排列a1、a2、……、aN。不幸的是，那张纸最近被农民Nhoj偷走了!幸运的是，FJ仍然有可能恢复他最初写下的排列。在被窃前，贝西记录了b1、b2、…、bN−1的序列，对于1≤i<N满足bi=ai+ai...
2020-02-27 16:36:13
484
原创 2020.2.22GDUT寒假训练排位赛2-H
H — I Would Walk 500 Miles题目大意：农民John想把他的N头奶牛(N≤7500)，方便地编号为1…N，分成K个非空的组(2≤K≤N)，这样两个不同组的奶牛在不走几英里的情况下就不能互相交流。奶牛x和奶牛y(其中1≤x<y≤N)愿意走 (2019201913x+2019201949y) mod 2019201997 英里去见对方。假设将N头牛分成K个非空的组，M为...
2020-02-27 00:34:37
195
原创 2020.2.22GDUT寒假训练排位赛2-G
G — Bucket Brigade题目大意：农场失火了，牛都跑去把火扑灭!农场是由一个10×10的网格来描述的，就像这样:字母“B”代表刚刚着火的谷仓。“L”代表一个湖，“R”代表一块大石头的位置。奶牛们想要组成一个“水桶旅”，把自己安置在湖和谷仓之间的一条小路上，这样它们就可以沿着小路传递一桶桶的水来帮助灭火。如果牛在北、南、东、西四个方向相邻，那么桶可以在它们之间移动。奶牛只有在紧挨...
2020-02-27 00:34:27
133
原创 2020.2.22GDUT寒假训练排位赛2-F
F — Milk Factory题目大意：牛奶生意兴隆!农夫约翰牛奶加工厂由N个加工站组成，方便地编号为1…N(1≤N≤100)和N - 1条走道，每条走道连接两个加工站。(人行道很贵，所以农民约翰选择使用最少的人行道，这样人们最终可以从其他车站出发到达任意车站)。为了提高效率，农夫约翰在每个走道上安装了一个传送带。不幸的是，他太晚意识到每个传送带只能单向移动，所以现在沿着每个通道只能单向移动...
2020-02-27 00:34:18
169
原创 2020.2.22GDUT寒假训练排位赛2-B
B — Snakes题目大意：根据传说，一千多年前，圣帕特里克驱逐了穆尔兰的所有蛇。然而，从那以后，蛇又回到了穆尔兰!圣帕特里克节是在3月17日，所以贝西要永远地从穆尔兰赶走所有的蛇来纪念圣帕特里克。贝西配备有网，可以捕捉N组分布在一条线上的蛇(1≤N≤400)。贝西必须按照每组蛇出现在这条线上的顺序，把每条蛇都抓起来。每次贝西抓住一群蛇，她可以把蛇放在笼子里，然后用空网开始下一群。大小为s的...
2020-02-27 00:34:06
165
原创 2020.2.22GDUT寒假训练排位赛2-A
A — Fence Planning题目大意：农民约翰的N头奶牛，方便地编号为1…N(2≤N≤105)，有一个复杂的社会结构，围绕着“moo网络”——小群的奶牛，它们在自己的群体中交流，但不与其他群体交流。每头奶牛位于2D的农场地图上不同的(x,y)位置，我们知道有M对奶牛(1≤M<105)在互相moo叫。互相moo叫的两头牛属于同一个moo网络。为了更新他的农场，农民约翰想要建一个长方...
2020-02-27 00:33:47
358
原创 2020.2.19GDUT寒假训练排位赛1-I
I — Livestock Lineup题目大意：农夫约翰出去在路上散步，他想他可能迷路了!沿路有N个农场(1个≤N≤100个)不幸的是，农场没有门牌号，这使得农场主约翰很难确定他在路边的位置。然而，每个农场的路边都有一个彩色的邮筒，所以农民约翰希望，如果他看到离他最近的邮筒的颜色，他可以唯一地确定他在哪里。每个邮箱的颜色由大写字母A到Z指定。因此，这条路的N个邮箱的序列可以由一个长度为N的字...
2020-02-24 17:51:26
342
原创 2020.2.19GDUT寒假训练排位赛1-G
G — Livestock Lineup题目大意：农民约翰每天都要给他的8头奶牛挤奶，它们分别叫Bessie, Buttercup, Belinda, Beatrice, Bella, Blue, Betsy, Sue。不幸的是，奶牛相当挑剔，要求农夫约翰按照N个约束条件(1≤N≤7)的顺序给它们挤奶。每个约束的形式是“X必须在Y旁边挤奶”，即奶牛X要么直接在奶牛Y后面，要么直接在奶牛Y前面。...
2020-02-24 17:51:11
497
原创 2020.2.19GDUT寒假训练排位赛1-E
E — Milk Visits题目大意：农民约翰计划建造N个(1≤N≤105)个农场，通过N−1条道路连接，形成一棵树(即在美国，所有农场都可以彼此连通，而且没有循环)。每个农场都有一种奶牛，其品种不是 Guernsey 就是 Holstein。农夫约翰的M个朋友(1≤M≤105)经常来看他。在拜访时，农夫约翰会和他的朋友沿着一条唯一的道路从一个农场走到另一个农场，同时他们喝到沿路的牛奶。因为...
2020-02-24 17:50:56
436
原创 2020.2.19GDUT寒假训练排位赛1-D
D — Circular Dance题目大意：两个谷仓位于一维数轴上的位置0和L(1≤L≤109)。也有N头牛(1≤N≤5*104)在不同的地点在数轴上的。每头奶牛i最初位于xi的某个位置，以每秒1单位的速度向正或负方向移动，用整数di表示，di为1或- 1。每头奶牛的体重wi也在范围[1,103]内。所有的奶牛总是以恒定的速度移动，直到下列事件之一发生:如果奶牛i到达谷仓，那么奶牛i停止移动...
2020-02-24 17:50:37
251
原创 2020.2.19GDUT寒假训练排位赛1-B
B — MooBuzz题目大意：农夫约翰的奶牛玩数字游戏“FizzBuzz”。这个游戏的规则很简单:站成一圈，奶牛依次从一开始向上数，每头奶牛轮到自己时说一个数字。如果一头奶牛达到了3的倍数，她应该说“Fizz”而不是这个数字。如果一头奶牛达到了5的倍数，她应该说“Buzz”而不是这个数字。如果一头牛达到15的倍数，她应该说“FizzBuzz”而不是这个数字。因此，游戏的第一部分是:1、2、F...
2020-02-24 17:50:17
139
原创 2020.2.19GDUT寒假训练排位赛1-A
A— Cow Gymnastics题目大意：为了提高身体素质，奶牛们开始练体操了!在每K个训练阶段(1≤K≤10)，根据奶牛的表现(1≤N≤20)对N头奶牛进行排名。之后，她对这些排名的一致性感到好奇。如果一头牛在每次训练中都比另一头牛做得好，那么这一对两只不同的牛孰胜孰败是确定的。计算这样确定的对的总数。输入第一行包含两个正整数K和N，接下来的K行将以某种顺序包含整数1…N，表示奶牛的...
2020-02-24 17:50:02
257
原创 2020 GDUT Winter Personal Training ContestⅠ(div.2) --- J
J — Circular Dance原题链接：https://codeforces.com/group/5yyKg9gx7m/contest/265863/problem/J题目大意：有一群围着圣诞树跳舞的孩子，每个人跳完舞分开后只记得前面的两个人（理解成每个孩子看着前面人的后背吧，排成一个环形吧）。依据他们所记得的人，还原他们的顺序（谁开头都无所谓）。题目分析：这题的思想很简单，但是实...
2020-01-18 11:33:43
158
原创 2020 GDUT Winter Personal Training ContestⅠ(div.2) --- I
I — Powers Of Two原题链接：https://codeforces.com/group/5yyKg9gx7m/contest/265863/problem/I题目大意：一个正整数x被称为2的幂，如果它可以被表示为x=2y，其中y是非负整数。所以，2的幂是1、2、4、8、16……有2个正整数n和k，任务是把这个正整数n表示成恰好k个2次幂的和。如果无法将n表示K个2的幂的和，则输...
2020-01-18 10:52:41
143
原创 2020 GDUT Winter Personal Training ContestⅠ(div.2) --- G
G — Array Stabilization原题链接：https://codeforces.com/group/5yyKg9gx7m/contest/265863/problem/G题目大意：有一个元素是整数的数组，其中最大值与最小值的有一个差值。去掉这个数组里其中一个整数后，得到新的最大值与最小值的差值。问题是对于给出的数组，去掉某个数字后，其最大值与最小值的差值最小，输出这个最小值。...
2020-01-18 10:07:05
91
原创 2020 GDUT Winter Personal Training ContestⅠ(div.2) --- E
E — Repeating Ciphe原题链接：https://codeforces.com/group/5yyKg9gx7m/contest/265863/problem/E题目大意：有几个字符s1，s2，s3，…，si，（1<i<10）可以这样加密，对于第i个字符重复i次，形成新的字符串。比如coop可加密成 c oo ooo pppp（中间空格是让读者可观，实际并不存在）。...
2020-01-18 09:48:18
101
原创 2020 GDUT Winter Personal Training ContestⅠ(div.2) --- C，D
C — Nice Garland原题链接：https://codeforces.com/group/5yyKg9gx7m/contest/265863/problem/C题目大意：只含有’R’，‘G’，'B’的字符串，要使它是nice的，就得满足其中相同的字符的距离是3的倍数，也就是每两个相同的字符中间有两个与他们不同的字符。给出一个字符串，通过修改最少的字符，使它是nice的字符串，求这个...
2020-01-18 09:29:26
98
原创 2020 GDUT Winter Personal Training ContestⅠ(div.2) --- B
B — Divisors of Two Integers题目大意：给出一个串数字，他们是两个数x和y的因子集合，x和y相同的因子可以重复出现，题目要求的就是满足这串数字的一对x和y。题目分析：刚开始愣愣的，不知道怎么做，后来想到因子中就包括了自身，也就是答案就在这串数字里。又想了想，这串数，最大的肯定是一个答案，那只要把这个最大的因子筛选掉，剩下的数中最大的就是另一个答案。代码实现：#...
2020-01-18 00:18:12
98
原创 2020 GDUT Winter Personal Training ContestⅠ(div.2) --- A
A — Two distinct points原题链接：https://codeforces.com/group/5yyKg9gx7m/contest/265863/problem/A题目大意：给出2个区间，分别输出一个在区间内的整数，这2个数不能相等。题目分析：要选的整数分别从2个区间的左边开始，两数相同则其中一个整数取对应区间的下一个整数。（水题）代码实现：#include &l...
2020-01-17 23:55:33
89
原创 2019_GDUT_新生专题 图论 --- L
L — Til the Cows Come Home原题链接：https://vjudge.net/contest/351234#problem/L题目大意：有很多标志性的东西或者建筑，树是起点，谷仓是终点。一些不同的标志建筑或东西之间一些小路，求从起点到终点的最短距离。题目分析：这是单源最短路径，用dijkstra算法。我是参考了他人的算法资料完成的，我觉得他的思路十分清晰易懂，链接...
2020-01-16 19:21:42
141
原创 2019_GDUT_新生专题 图论 --- H，I，J，K
H — 畅通工程原题链接：https://vjudge.net/contest/351234#problem/H题目大意：给出城镇数目和已经修完的路的起始点，为使城镇相互可直接或间接通达，最少还需要修建多少的路。题目分析：这是连通图问题，一般用并查集。找出相连点的代表点（代表根），代表点不同，则互不相通，n个不同的代表点只需要n-1条路就可以相互通达。并查集可以找到不同的代表点。代码...
2020-01-16 18:43:55
223
原创 2019_GDUT_新生专题 图论 --- E
E — 最短路原题链接：https://vjudge.net/contest/351234#problem/E题目大意：有多个哨站，每个哨站都有一部视频联络机，一些哨站还同时配有卫星联络。配有卫星联络的哨站可不限距离相互联系，而只有视频联络机的只能在一定范围内联系（限制距离），距离越大，花费越大。给出哨站的数目、坐标和配有卫星联络的数目，求最小的限制距离。题目分析：这是最小生成树问题，一...
2020-01-16 17:21:25
128
原创 2019_GDUT_新生专题 图论 --- C
C — 六度分离原题链接：https://vjudge.net/contest/351234#problem/C题目大意：给出一些人的关系，问是否满足“六度分离”：任何2个素不相识的人中间最多只隔着6个人，即只用6个人就可以将他们联系在一起。题目分析：这是连通问题。是否每个点都可直接或间接可达，不过加上了限制，间接可达的两个点之间的点数不能大于6，所以需要加上判断。由于数据量比较小，我使...
2020-01-16 16:53:10
103
原创 2019_GDUT_新生专题 图论 --- B
B — 最短路原题链接：https://vjudge.net/contest/351234#problem/B题目大意：有多个路口，一些路口间有多条路可通，走每条路都有一个通过时间，求起点到终点的最短时间。题目分析：这是单源最短路问题，一般用Bellman-Ford算法、Dijkstra算法，由于数据比较小，我使用了Floyd算法实现（因为最先接触）。代码实现：#include<...
2020-01-16 16:39:24
112
原创 2019_GDUT_新生专题 图论 --- A
A — Cow Contest原题链接：https://vjudge.net/contest/351234#problem/A题目大意：很多cow进行两两pk，给出cow的数目和一些pk的结果，问能确定排名的cow的数目。题目分析：这是一道图论，出度和入度的问题。如果 某cow 打败过 a个（出度数），而被b个打败过（入度数），且满足a+b就是除了本身的所以其他cow的数目，那么就可以...
2020-01-16 16:19:33
220
原创 2019_GDUT_新生专题 I --- K
[HDU] 3714 — Error Curves 三分原题链接：https://vjudge.net/problem/18677/origin题目大意：给出多条二次或一次曲线（Si(x) = ax^2 + bx + c，a>=0)；构造一条能代表所以曲线的曲线F(x) = max{Si(x)}；求出这条曲线的题目分析：数据太大，直接遍历所有的最小距离肯定不行。先排序，再运用二分，...
2020-01-16 16:02:30
107
原创 2019_GDUT_新生专题 I --- J
[POJ] 1905 — Expanding Rods 二分原题链接：https://vjudge.net/problem/17093/origin题目大意：两端固定的杆被加热变形成一段圆弧，求出杆的中点相比原来的偏移距离。题目分析：刚开始我看完题是丈二和尚摸不着头脑，无从下手。后面想到它的圆心角应该不会超过pi（圆周率），着手尝试发现很复杂还错了，所以换了一个思路，就是所求的偏移距离不...
2020-01-16 15:30:10
107
原创 2019_GDUT_新生专题 I --- L
[CodeForces] 1260B — Obtain Two Zeroes原题链接：https://vjudge.net/problem/2953420/origin题目大意：给定两个数a，b，判断是否可以通过若干个操作1：选择一个数x，a = a - 2x，b = b - x；或操作2：选择一个数x，a = a - x，b = b - 2x；使a，b都等于0题目分析：无论进行多...
2020-01-14 08:56:36
120
原创 2019_GDUT_新生专题 I --- I
[HYSBZ] 1734 — Aggressive cows 愤怒的牛原题链接：https://vjudge.net/problem/1642056/origin题目大意：有N个隔间x1,…,xN，给C头牛分配隔间，使任意两头牛之间的最小距离尽可能的大，求这个最大的最小距离。题目分析：数据太大，直接遍历所有的最小距离肯定不行。先排序，再运用二分，一步步逼近最大距离。代码实现：#inc...
2020-01-13 22:16:59
151
原创 2019_GDUT_新生专题 I --- H
[GYM] 101375H — MaratonIME gets candies原题链接：https://vjudge.net/problem/863420/origin题目大意：猜Renzo的饼干数目。题目分析：这是道比较简单的二分题目，注意不要漏了区间的头和尾即可，直接上代码。代码实现：#include <iostream>#include <cstdio>...
2020-01-13 19:43:34
122
原创 2019_GDUT_新生专题 I --- G
[GYM] 101755H — Safe Path原题链接：https://vjudge.net/problem/1435606/origin题目大意：给出N*M一个地图，一共最少有2个格，最多有200000格。有起点，终点，怪兽及其攻击的范围，输出从起点到终点的最短距离，如果无法到达终点，则输出“-1”。题目分析：难点：无法直接建立二维数组存储地图（数组空间太大），需要用一维间接变成二...
2020-01-13 19:38:33
132
原创 2019_GDUT_新生专题 I --- D，F
[POJ] 1979 — Red and Black原题链接：https://vjudge.net/problem/26084/origin题目大意：给出W*H的地图，’ . ‘代表着黑瓷砖，’ # ‘代表着红瓷砖，’ @ '代表着人的位置，人的脚下也是黑瓷砖。要求的就是人所能走的最多的黑瓷砖的数目。题目分析：通过深度优先搜索，从人的位置开始对相邻的黑瓷砖进行遍历，被遍历过的黑瓷砖被标记...
2020-01-13 19:38:10
139
原创 2019_GDUT_新生专题 I --- B，C
[POJ] 2386 — Lake Counting原题链接：https://vjudge.net/problem/14167/origin题目大意：给出N*M的一个地图，’ . ‘代表着没有水的陆地，’ W '代表着水洼，所以相邻的水洼，包括对角相邻，形成一个池塘，要求的就是池塘的数目。题目分析：通过深度优先搜索，对每一个水洼进行遍历，被遍历过的水洼被标记为陆地，防止被再次遍历或者进入...
2020-01-13 19:37:43
464
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人