palax0-CSDN博客

原创 Codeforces Round #669 (Div. 2) C. Chocolate Bunny

C. Chocolate Bunny题目链接题目描述给一个长度为nnn的排列pnp_npn，由从111到nnn的整数组成。要求通过询问猜出排列的顺寻，有最多2n2n2n次询问机会。询问方式如下："?xy"(1≤x,y≤n,x≠y)"?\quad x \quad y"(1\leq x,y\leq n,x\neq y)"?xy"(1≤x,y≤n,x=y)系统将会返回pxmod pyp_xmod\ p_ypxmod py的值。题目分析细节问题暂不讨论，主要讨论如何询问：

2020-09-09 13:27:11 94

原创 2020 GDUT Rating Contest I A. Cow Gymnastics

A. Cow Gymnastics链接题目描述有n头牛一起参加了k次比赛，给出k次比赛的排名，问共有几组牛满足其中一头牛每次比赛都比另一头厉害。题目分析由于数据量比较小（1<=k<=10）（1<=n<=20）,直接多层循环计算出每两头牛之间的胜负情况即可。代码#include <bits/stdc++.h>using namespace st...

2020-03-13 03:03:00 110

原创 2020 GDUT Rating Contest I (3.08) C. 积木

C. 积木链接题目描述用积木块来搭房子。给出最长的积木块的长度，该积木块只能当作地基。如果当前搭建的房子的最顶端的积木块的长度为k，可以选择一个长度属于[1,k/2]的积木放在房子的最顶端，或者选择不再继续放置积木。求一共能搭建几种房子。题目分析f(n)代表地基长度为n时的房子数量，先列举前几种情况看一看：f(1)=1,f(2)=1+f(1)f(3)=1+f(1),f(4)=1...

2020-03-13 02:34:46 97

原创 2020 GDUT Rating Contest IV D. Mixing Milk

D. Mixing Milk链接题目描述有三个桶，给出每个桶的容量和里面装有的牛奶量，然后进行将A中牛奶倒入B，B中牛奶倒入C，C中牛奶倒入A的操作（如果另一个桶满了就不倒了），共100次（倒一次算一次）。求最后每个桶各有多少牛奶。题目分析因为倒的次数（100次）与操作类型（3种）都很少，直接循环100次就完事了。代码#include <bits/stdc++.h>u...

2020-03-13 02:09:12 91

原创 2020 GDUT Rating Contest I I. Where Am I?

I. Where Am I?链接题目描述给出一个长度为n（1<=n<=100）的字符串，现从中连续的取出一个长度为k的子序列，问k要为多少才能保证取出来的子序列在原字符串中是独一无二的。题目分析因为n的数值范围很小，不妨直接取出各种子序列，与原字符串进行比较。代码#include <bits/stdc++.h> using namespace std; ...

2020-03-13 01:48:56 108

原创 2020 GDUT Rating Contest III A. Wormhole Sort

A. Wormhole Sortcf链接洛谷链接题目描述(还是看洛谷的中文题面吧)题目分析#参考了博客（参考了博客后发现）原题可看作位置不对的牛想通过虫洞走到正确的位置，而且希望虫洞的宽度尽可能大（路的长度尽可能长），有kruskal内味了，而套用kruskal也就解决了。貌似还有二分的做法，以后补上。。。代码#include <bits/stdc++.h>...

2020-03-13 00:59:41 119

原创 2020 GDUT Rating Contest I B. MooBuzz

B. MooBuzz链接题目描述输出第n个既不是3的倍数又不是5的倍数的数。题目分析水题。。。我还以为要用数论知识啥的，后来才发现是找规律题，以 15为一个循环分析即可。代码#include <bits/stdc++.h> using namespace std; int a[8]={-1,1,2,4,7,8,11,13}; int main(){ in...

2020-03-12 22:14:22 119

原创 2020 GDUT Rating Contest IV F. News Distribution

F. News Distribution链接题目描述有n个人，他们各加入了一些群。给出m条关于某个群有谁的信息。若一个人的群友加入了另一个群，这个人也算加入了另一个群。输出每个人加入的群数（给出信息之前默认每个人已经加入一个群）题目分析因为是人与人直接有传递性的关系，套用并查集模板即可。代码#include <bits/stdc++.h>using namespace...

2020-03-12 21:59:47 442

原创 2020 GDUT Rating Contest III H. Photoshoot

H. Photoshoot链接题目描述有n头牛，他们的序号从为1-n，现在他们按一定顺序排好，给出每对相邻的两头牛的序号之和，求出牛现在的序号。题目分析因为确定其中一头牛的序号，就可以得出所有牛的序号，又因为不存在两头牛序号相同，因此试出第一头牛的序号即可。代码#include <bits/stdc++.h>using namespace std;int ans=...

2020-03-12 21:20:53 205

原创 2020 GDUT Rating Contest III E. Word Processor

E. Word Processor链接题目描述给出一个含n个单词的句子，要求输出这个句子，且每行字母数超过k个时换行，若输入某单词的过程中该行字母数超过k个，将该单词输到下一行。题目分析按照题目要求，在输入字符串的时候把句子分割成符合要求的几块，再输出即可。注意题目说There should be no space at the end of any line.代码#include ...

2020-03-12 21:08:15 123

原创 2020 GDUT Rating Contest Ⅱ B. Snakes

B. Snakes链接题目描述Bessie打算用网来捕n组蛇，且只能从第一组开始捕。一开始她可以设置网的容量，且她有k次修改容量的机会，求浪费的容量的最小值。题目分析#参考了博客代码#include <bits/stdc++.h>using namespace std;typedef long long ll;const int INF=0x3F3F3F3F;...

2020-03-12 20:50:55 116

原创 2020 GDUT Rating Contest Ⅱ G. Bucket Brigade

G. Bucket Brigade链接题目描述给一个10*10的图，由’B’、‘R’、‘L’、’.‘构成，分别代指着火的谷仓、石头(无法经过)、湖、与路。现在让牛用肉身从谷仓(B)旁边搭桥到湖(L)旁边（上下左右方向的接触才算），每个牛占一个’.’，求最少需要几头牛。题目分析标准的bfs题，求最短距离，用队列进行bfs即可。代码#include <bits/stdc++.h&g...

2020-03-12 15:32:08 111

原创 2020 GDUT Rating Contest Ⅱ A. Fence Planning

A. Fence Planning链接题目描述给出 n 头牛的二维坐标和 m对牛之间的关系，而有关系的牛算作同一组。这个关系可以传递，如给出关系1-2、2-3，则1、2、3为一组。现在想用一个矩形围栏将其中一个组围住，求围栏周长的最小值。题目分析先用并查集处理牛的关系，得出各牛属于哪一组，再遍历每头牛的横纵坐标，找出每组横坐标与纵坐标的最大最小值，即可算出每组最少需要的围栏周长，最后比...

2020-03-12 15:11:29 156

原创 2019 GDUT 新生专题Ⅳ选集 E题 Revenge of GCD

E - Revenge of GCD链接题目描述给你两个数x和y，求它们的第k大公约数。题目分析由算术基本定理知x=(a1x1)(a2x2)…(anxn)y=(a1y1)(a2y2)…(anyn)gcd(x,y)=(a1min(x1,y1))(a2min(x2,y2) )…(anmin(xn,yn))x和y的第k大公约数离不开gcd(x,y)的因子，因此，题目可转化为求gcd(x...

2020-03-09 17:12:16 104

原创 2020 GDUT Rating Contest Ⅱ H. I Would Walk 500 Miles

H. I Would Walk 500 Miles链接题目描述某农场主想将他的N头牛分成K个非空的组，使得距离M尽可能大。距离M指的是不同组别的两头牛的距离的最小值，两头牛x,y的距离计算方法是(2019201913x+2019201949y) mod 2019201997 (x<y)题目分析观察发现模数和x、y前的系数很接近，而原式又可以写成：(2019201913x ...

2020-02-24 17:07:07 103

原创 2020 GDUT Rating Contest Ⅱ F.Milk Factory

F. Milk Factory链接题目描述有n个站台和n-1条只能单向通行的路，问是否存在一个站台，满足所有路都能到达这个站台，没有则输出-1。题目分析题意很简单，直接用二维数组表示两处单向连通，再搜索每个站，看看是不是其他站都能到这个站。不过可能会漏掉类似3->2->1这种两点之间有多段路的情况（可能只有我漏了。。），所以还得把这种多段的路搭起来。代码#include ...

2020-02-23 15:53:23 257

原创 2020 GDUT Rating Contest Ⅰ G.Livestock Lineup

G.Livestock Lineup链接题目描述有八头有名字的牛，要求在满足限制条件的同时尽可能按照字典序从小到大输出他们的名字，限制条件的格式类似“ a牛要在 b牛旁边”这样。题目分析参考dl的代码后发现，有一个神奇的函数next_permutation()，可以让原序列变成离原序列最近而字典序又大于原序列的序列(语文能力有限见谅，想了解可看看大佬的博客)。这题只有8头牛，最多也...

2020-02-19 22:06:55 155

原创 2020牛客寒假算法基础集训营3 H题牛牛的k合因子数

H - 牛牛的k合因子数链接题目描述（题目已经很简单就不再描述了）合数是指自然数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。牛牛最近在研究“k合因子数”，所谓“k合数”是指一个数的所有因子中，是合数的因子共有k个。例如20的因子有1,2,4,5,10,20，其中4,10,20为合数，它有3个合数因子，就称20是一个 “3合因子数”牛牛想要知道1~n中给定k的情况下k合因...

2020-02-11 11:49:33 231

原创 Array Sharpening (Codeforces Round #616 Div.2 B)

B. Array Sharpening链接题目描述给你一个数列，问能否使这个数列变成先单调递增再单调递减的数列（单调递增或单调递减的项数可以为0项）。你可以使用的操作为：让数列中的任意一项减去n，但要保证减完后仍大于等于0。题目分析假设单调递增与单调递减的分界点为第i项，共n项。若将 i 以前的每一项都化到最小，第一项最小为0，第二项最小为1，以此类推知道第 i 项最小为 i-1 ，因...

2020-02-04 22:21:44 233

原创 2019 GDUT 新生专题Ⅲ选集 J题畅通工程续

J - 畅通工程续链接题目描述给出若干个城镇与若干条城镇间的道路，求从指定城镇A到指定城镇B的最短路。题目分析由题意可知，这是一道多源最短路问题，套用Floyd算法即可。值得注意的是，题目没有说两个城镇之间只建一条路，因此输入时要注意。代码#include <cstdio>#include <cstring>#include <iostream&g...

2020-01-17 11:38:39 108

原创 2019 GDUT 新生专题Ⅲ选集 I题还是畅通工程

I - 还是畅通工程链接题目描述有若干个城镇，给出这些城镇两两之间的距离。为使任意两个城镇间都可以实现公路交通(不一定要直连)，求修建公路长度的最小值。题目分析由题意可知，该题为最小生成树问题，套用Kruskal算法模板即可。代码#include <cstdio>#include <iostream>#include <algorithm>...

2020-01-17 11:31:29 113

原创 2019 GDUT 新生专题Ⅲ选集 H题畅通工程

链接题目描述给若干个城市与若干条已经建设好的道路，问最少还需建设多少条才能使任意两个城市之间可以实现交通(不一定要直接相连)。题目分析由题意可知，这题是并查集模板题，按照并查集题目的做法做就完事了。代码#include <iostream>#include <cstdio>#include <cstring>using namespace st...

2020-01-17 11:22:09 97

原创 2019 GDUT 新生专题Ⅳ选集 B题 Fedya and Maths

B - Fedya and Maths链接题目描述求(1n + 2n + 3n + 4n) mod 5的值，n最大可以达到10的105次方。题目分析n为这么大的数字，显然不能用常规方法，猜想有规律可循。一个数 mod5 等于多少只需看个位是多少 (证明：(10*(前n-1位数)+(个位))%5=(个位)%4)。由此可猜想 1n + 2n + 3n + 4n 的个位是有规律的。代入几组数...

2020-01-15 09:53:18 127

原创 2019 GDUT 新生专题I选集 G题 Safe Path(Gym - 101755H)

G - BFS链接来源：Safe Path(Gym - 101755H)题目描述你在玩一个rpg游戏，需要让主角从起点走到终点。地图由一个个小房间组成，有的房间有怪兽，他们的攻击范围都为d。如果怪兽走到你现在的格子所需要的步数少于等于d，gg。请你判断主角能否走到终点，如果能，输出到终点的最短路径长度。题目分析先把怪兽所在的房间以及怪兽能攻击的房间标记为已访问，再从起点开始进行正常的d...

2020-01-14 13:00:01 160

原创 2019 GDUT 新生专题I选集 D题 Accepted Necklace(HDU-2660)

D - DFS链接来源：HDU-2660题目描述给一些宝石，每个宝石都有自己的重量和价值，要求选取一定数量的宝石组成一条项链，使项链的重量不超过佩戴者能接受的最大重量，且价值最高。题目分析本来比较像一道dp题，但数据比较少，直接dfs即可。代码#include <cstdio>using namespace std;int value[1000];int wei...

2020-01-14 10:47:29 117

原创 2019 GDUT 新生专题I选集 H题(Gym - 101375H)

H - 二分+交互链接来源：Gym - 101375H题目描述给一个数，通过询问的方式猜它是多少，可以询问最多50次，每次询问会给出">","<“或”="的回答。题目分析要在比较少的次数找出这个数，所以用二分，且这个数最大为1e9，可以在50次内找出。记得"flush the output"。代码#include <cstdio>using namespa...

2020-01-14 10:06:41 157

原创 2019 GDUT 新生专题I选集 F题(POJ - 1426)

F - BFS/DFS链接来源：POJ - 1426 题目描述给定一个正整数n，找n的一个非零的倍数m，这个m应当在十进制表示时每一位上只包含0或者1。解题思路因为感觉dfs可能一去不复返，我选用了bfs。先取操作数为1，然后将操作数×10，分为0、1两条路，加入队列，后面的操作亦如此。(温馨提示：提交language选G++比较容易ac，本菜鸡的代码选C++无法通过。。若有高见请您...

2020-01-13 17:31:42 117

原创 2019 GDUT 新生专题I选集 C题(POJ - 1979)

C - DFS/BFS链接来源：POJ - 1979题目描述房间里有两种地砖，一种为黑色，一种为红色。一个人在黑色砖上，他只能从黑色砖移动到黑色砖上，不能移动到红色砖上。给出房间地砖的布局，求这个人能走过多少块黑色砖。题目分析根据题目要求，从起点开始进行bfs即可，主要是练习bfs如何用代码实现。代码//bfs做法#include <cstdio>#include ...

2020-01-13 17:15:27 118

原创 2019 GDUT 新生专题I选集 B题(POJ - 2386)

B - DFS/BFS链接来源：POJ-2386题目描述给出一份由’W’和’.'组成的图，算出其中水池的个数。其中水池由满足八个方向(上下、左右、对角线方向)至少有一个方向上有’W’的’W’组成。题目分析遍历图中的每一个点，遇到’W’就开始dfs，当周围没有未访问过的’W’就停止。为了便于判断其他的水池，将访问过的’W’都换成’.’(参考了白书)代码#include <std...

2020-01-13 17:02:27 137

原创 2019 GDUT 新生专题I选集 A题(POJ-3061)

A-尺取链接来源：POJ-3061题目描述给一串序列，求其中一段满足各元素的总和大于等于数S的连续子序列的最短长度。题目分析因为专题名字是尺取要求满足条件的连续子序列的最短长度，由缩短长度的过程可联想到使用尺取法。注意是大于等于而不是只有等于。注意边界的处理以免答案差1。代码#include <stdio.h>int main(){ int ca; sc...

2020-01-13 16:41:04 124

原创 2019 GDUT 新生专题I选集 L题(CodeForces - 1260B)

L-二分？？？链接来源：CodeForces - 1260B题目描述给两个数a、b，可以对其进行 ①a=a-x,b=b-2x②a=a-2x,b=b-x 两种操作(其中x为任意正整数)，问能否通过这两种操作使a,b同时为0？题目分析设操作①选择的x为i，操作②选择的x为j，若数a，b满足条件，则有：a-i-2j=0 b-2i-j=0∴2a-b=3i 2b-a=3j由此可知必要条...

2020-01-13 16:01:53 188

palax0的博客