- 博客(52)
- 资源 (2)
- 收藏
- 关注
原创 村村通--洛谷(并查集的运用)
P1536 村村通题目描述某市调查城镇交通状况,得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 “村村通工程” 的目标是使全市任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要相互之间可达即可)。请你计算出最少还需要建设多少条道路?输入格式输入包含若干组测试测试数据,每组测试数据的第一行给出两个用空格隔开的正整数,分别是城镇数目 n 和道路数目 m ;随后的 m 行对应 m 条道路,每行给出一对用空格隔开的正整数,分别是该条道路直接相连的两个城镇的编号。简单起见,城镇从
2020-10-25 18:30:10 1384 4
原创 快速求b的多少次幂是a(一天一个小细节(¬◡¬)✧)
快速求b的多少次幂是a循环判断出来多慢(¬◡¬)✧,直接用数学公式求出来。int m=int(log(a)/log(b));
2021-07-29 14:43:19 180
原创 牛客竞赛--LCS(2021牛客暑期多校训练营4)
题目链接:LCS题目大意:就是有三个长度为n的字符串,a,b,c。分别给你a和b,b和c,a和c之间的最长公共子序列,判断是否可以构造出来,若能,则输出任意可以的三个字符串,不能则输出"NO"。思路:若(lena+lenb+lenc-2t>n)则不能构造出来(t是三个字符串的最小长度)。若果能构造,先把三个字符串每个都加上t个相同的字符,然后a-=t,b-=t,c-=t。其中a,b,c必定有一个为0,之后剩下的两个分别给特定的两个字符串加上x个字符,最后再判断三个字符串分别有没有到达长度n,如
2021-07-29 11:13:33 259
原创 C. A-B Palindrome
C. A-B PalindromeYou are given a string s consisting of the characters ‘0’, ‘1’, and ‘?’. You need to replace all the characters with ‘?’ in the string s by ‘0’ or ‘1’ so that the string becomes a palindrome and has exactly a characters ‘0’ and exactly b
2021-07-14 16:51:37 263 1
原创 序列自动机
序列自动机非常好用的算法,可以在O(1)的时间复杂度判断i后面x第一次出现的位置。#include <iostream>#include <algorithm>#include <string.h>using namespace std;int a[50],nxt[100010][50],pre[50];int main(){ int i,j,n; cin>>n; for(i=0;i<n;i++) { cin>>a
2021-07-12 10:29:29 122
原创 有关图的入门讲解
图什么是图图在现实生活中非常重要,遍布于诸多学科诸多领域,从285年前的哥尼斯堡的七桥,到现代手机上的智能导航,图论一直在推进着人类的进步,便利人们的生活。可以说是与我们密切相关了。最常见的应用,例如当前城市规模越来越大,交通路线越来越复杂,寻找最短路径或者最优路线等问题都与图论密不可分。而到底什么是一个图,用最简单的话来描述,就是若干节点相连,形成的闭合回路,就是一个图, 图分为有向图和无向图,有向图就是节点与节点之间有着单向路径,例如A能到B但B不一定能到A。而无向图则两点之间有路,两点都到达对方。
2021-07-12 10:18:32 168 2
原创 蛇形矩阵--模拟/递归(洛谷)
蛇形矩阵思路: 方法有很多,这里用的是模拟跑一边,判断什么时候改变方向就可以了,重要的是思路。代码如下:#include <iostream>#include <stdio.h>using namespace std;int n,a[1005][1005],book[1005][1005];int nest[4][2]={{0,1},{1,0},{0,-1},{-1,0}},fx=0,now=1;void work(int x,int y){ int tx,ty
2021-04-26 19:53:03 347
原创 第十一届蓝桥杯省赛(七段码)--排列组合/DFS的应用
【问题描述】小蓝要用七段码数码管来表示一种特殊的文字。在这里插入图片描述上图给出了七段码数码管的一个图示,数码管中一共有 7 段可以发光的二 极管,分别标记为 a, b, c, d, e, f, g。小蓝要选择一部分二极管(至少要有一个)发光来表达字符。在设计字符 的表达时,要求所有发光的二极管是连成一片的。例如: b 发光,其他二极管不发光可以用来表达一种字符。例如: c 发光,其他二极管不发光可以用来表达一种字符。这种 方案与上 一行的方案可以用来表示不同的字符,尽管看上去比较相似。例如
2021-04-12 20:37:52 415
原创 已知某二叉树的先序和后序遍历,求有几种中序遍历的情况(有多少种二叉树的可能)
已知某二叉树的先序和后序遍历,求有几种中序遍历的情况(有多少种二叉树的可能)思路:找左子树或者右子树在一边的情况,也就是二重循环遍历,先序遍历的序列从0到size()-2,后序从1到size-1,有先序的某值等于后序的某值,再进一步判断是否先序的后一个值等于后序当前值的前一个,则sum++。最后二叉树的所有可能有sum^2种。代码如下:#include <iostream>#include <string.h>using namespace std;int main(
2021-04-09 14:03:23 1194
原创 已知先序中序求后序,已知中序后序求先序,小白一看就会,二叉树重建
二叉树的重构先序遍历:根 -> 左 -> 右中序遍历:左. -> 根 -> 右后序遍历:左 -> 右 -> 根知道任何一棵二叉树的先序和中序遍历的序列或者中序和后序的遍历序列,都能构造出唯一的一棵二叉树下面先看一道PTA上的题引入思考因为知道了先序遍历的特点,从第一个开始,都先从根开始。把先序的根在中序中找到,以此分两分,左边是左子树,右边是右子树。递归分治重新生成一棵二叉树
2021-04-09 13:56:10 916
原创 N个数求和--(PTA天梯赛练习)
N个数求和 (20 分)本题的要求很简单,就是求N个数字的和。麻烦的是,这些数字是以有理数分子/分母的形式给出的,你输出的和也必须是有理数的形式。输入格式:输入第一行给出一个正整数N(≤100)。随后一行按格式a1/b1 a2/b2 …给出N个有理数。题目保证所有分子和分母都在长整型范围内。另外,负数的符号一定出现在分子前面。输出格式:输出上述数字和的最简形式 —— 即将结果写成整数部分 分数部分,其中分数部分写成分子/分母,要求分子小于分母,且它们没有公因子。如果结果的整数部分为0,则只输出分数
2021-03-31 20:24:01 2433 1
原创 PTA--连续因子(天梯赛练习)
L1-006 连续因子 (20 分)一个正整数 N 的因子中可能存在若干连续的数字。例如 630 可以分解为 3×5×6×7,其中 5、6、7 就是 3 个连续的数字。给定任一正整数 N,要求编写程序求出最长连续因子的个数,并输出最小的连续因子序列。输入格式:输入在一行中给出一个正整数 N(1<N<2^31)。输出格式:首先在第 1 行输出最长连续因子的个数;然后在第 2 行中按 因子1因子2……*因子k 的格式输出最小的连续因子序列,其中因子按递增顺序输出,1 不算在内。输入
2021-03-30 21:05:44 477 1
原创 DFS/BFS--(深度优先搜索/广度优先搜索)入门讲解
DFS首先先看下面这个有关迷宫的问题引入思考。密室逃脱Description每天刷题太枯燥了,为了放松一下自己,你,zjx和hhy约好了周末一起去玩密室逃脱。一般的密室逃脱对你们没有什么吸引力了,所以你们找到了一个更好玩的密室逃脱。我们可以把整个密室看成一个 n * m 的网格图(包含很多房间),其中每个房间都是一个1 * 1的单元格, 有一些房间有机关,进入后会失去游戏资格。我们将没有机关的房间用0表示,有机关的房间用1表示。迷宫的规则是开局的时候zjx和hhy被随机放到一个房间里(保证被放房
2021-03-17 20:59:37 365 6
原创 B.签订协议------牛客IOI周赛22-普及组
签订协议来源:牛客网题目描述一共有n个国家来到了停战点,在协议停战签订的会场里,环形排布着n个位置, 位置从1开始编号,一直到n号,每个位置上有一个国家。签订停战协议的仪式开始了,停战协议书从1号位置开始传递,一直传递到n号位置, 传到n号时,n号会再传回给1号,从而开始新的一轮传递。 停战协议签订的顺序必须按照国家的战力来排序,战力最高的最先签订停战协议。也就是说,如果停战协议轮到了某个国家,但该国家并不是在场还未签订协议的国家中战力最强的,那么他这轮只能轮空,传给下一个国家。 协议只能单向传递
2021-01-23 11:29:47 117
原创 A.校园活动--牛客练习赛76
链接:https://ac.nowcoder.com/acm/contest/10845/A来源:牛客网校园活动题目描述牛牛中学为了给本校的OIer放松心情,决定举报一场校园活动。现在学校的共有 个OIer,学校想把他们分为一些小组进行一个团队游戏。学校先了解了一下每个同学对这个团队游戏的了解程度。为了游戏的公平,学校需要使分组后的每一个小组内所有人对游戏的了解程度之和相等,但同学们并不希望完全由学校来给他们分组,所以这 个人站为了一行,学校只能将队列中一段完整的子队列作为一个小组。换句话说
2021-01-16 12:59:51 231
Sequence Transformation--div.3(模拟+map,vector容器嵌套)
Sequence TransformationYou are given a sequence a, initially consisting of n integers.You want to transform this sequence so that all elements in it are equal (i. e. it contains several occurrences of the same element).To achieve this, you choose some i
2020-11-25 20:38:41 217
原创 C.Dominant Piranha--(div.3)
There are n piranhas with sizes a1,a2,…,an in the aquarium. Piranhas are numbered from left to right in order they live in the aquarium.Scientists of the Berland State University want to find if there is dominant piranha in the aquarium. The piranha is ca
2020-11-22 21:36:29 234
原创 家谱--并查集&&map容器的应用
题目背景现代的人对于本家族血统越来越感兴趣。题目描述给出充足的父子关系,请你编写程序找到某个人的最早的祖先。输入格式输入由多行组成,首先是一系列有关父子关系的描述,其中每一组父子关系中父亲只有一行,儿子可能有若干行,用 #name 的形式描写一组父子关系中的父亲的名字,用 +name 的形式描写一组父子关系中的儿子的名字;接下来用 ?name 的形式表示要求该人的最早的祖先;最后用单独的一个 $ 表示文件结束。输出格式按照输入文件的要求顺序,求出每一个要找祖先的人的祖先,格式为:本人的名字 +
2020-11-08 12:45:17 151
原创 A-B 数对--map映射(洛谷)
题目描述出题是一件痛苦的事情!相同的题目看多了也会有审美疲劳,于是我舍弃了大家所熟悉的 A+B Problem,改用 A-B 了哈哈!好吧,题目是这样的:给出一串数以及一个数字 C,要求计算出所有 A−B=C 的数对的个数(不同位置的数字一样的数对算不同的数对)。输入格式输入共两行。第一行,两个整数 N,C。第二行,N 个整数,作为要求处理的那串数。输出格式一行,表示该串数中包含的满足 A−B=C 的数对的个数。思路: 题目要表达的意思就是一堆数中寻找所有满足任意一个数减去C要正好等于另
2020-11-07 18:44:19 296
原创 两只塔姆沃斯牛 The Tamworth Two-模拟
题目描述两只牛逃跑到了森林里。Farmer John 开始用他的专家技术追捕这两头牛。你的任务是模拟他们的行为(牛和 John)。追击在 10×10 的平面网格内进行。一个格子可以是:一个障碍物,两头牛(它们总在一起),或者 Farmer John。两头牛和 Farmer John 可以在同一个格子内(当他们相遇时),但是他们都不能进入有障碍的格子。一个格子可以是:.空地*障碍物C两头牛FFarmer John这里有一个地图的例子:*...*.....
2020-11-01 20:12:36 219
原创 三连击(升级版)--洛谷
P1618–三连击(升级版)题目描述将 1,2,…,9 共 9 个数分成三组,分别组成三个三位数,且使这三个三位数的比例是 A:B:C,试求出所有满足条件的三个三位数,若无解,输出 No!!!。//感谢黄小U饮品完善题意输入格式三个数,A,B,C。输出格式若干行,每行 3个数字。按照每行第一个数字升序排列。输入输出样例:输入#1:1 2 3输出#1192 384 576219 438 657273 546 819327 654 981暴力出奇迹,简单粗暴。#inc
2020-10-25 11:53:47 282
原创 洛谷--回文质数 Prime Palindromes
题目描述因为 151 既是一个质数又是一个回文数(从左到右和从右到左是看一样的),所以 151 是回文质数。写一个程序来找出范围 [a,b] (5≤a<b≤100,000,000)( 一亿)间的所有回文质数。输入格式第 1 行: 二个整数 a 和 b .输出格式输出一个回文质数的列表,一行一个。输入输出样例输入#1输出#15 500571110113115118119131335337
2020-10-23 11:17:08 523
原创 质因数分解
质因数分解题目 :已知正整数nnn是两个不同的质数的乘积,试求出两者中较大的那个质数。输入格式:一个正整数nnn。输出格式 :一个正整数ppp,即较大的那个质数。#include <iostream>#include <cmath>using namespace std;int main(){ int i,n; cin>>n; for(i=2;i<=n;i++) { if(n%i==0) { cout<<n/i
2020-10-14 21:18:42 116
原创 数字反转(升级版)
数字反转(升级版)题目:给定一个数,请将该数各个位上数字反转得到一个新数。这次与NOIp2011普及组第一题不同的是:这个数可以是小数,分数,百分数,整数。整数反转是将所有数位对调;小数反转是把整数部分的数反转,再将小数部分的数反转,不交换整数部分与小数部分;分数反转是把分母的数反转,再把分子的数反转,不交换分子与分母;百分数的分子一定是整数,百分数只改变数字部分。整数新数也应满足整数的常见形式,即除非给定的原数为零,否则反转后得到的新数的最高位数字不应为零;小数新数的末尾不为0(除非小数部分除了0没
2020-10-13 18:12:52 881
原创 第十一届蓝桥杯(七月)--跑步训练
跑步训练思路:模拟实现,注意输出的要求是秒数。代码:#include <iostream>using namespace std;int main(){ int flag=1,s=0,sum=10000; while(sum!=0) { s++; if(s%60!=0) { if(flag==1) { sum=sum-10; } else { sum=sum+5; } } else { if(flag==1
2020-10-12 20:48:56 447
原创 马的遍历--BFS的运用
马的遍历思路:根据马走的方向在地图上搜索,找到每个点的步数。#include <iostream>#include <stdio.h>using namespace std;int n,m,map[401][401]={0},book[401][401]={0};struct node{ int x; int y; int step;};int nest[8][2]={{2,1},{-2,1},{2,-1},{-2,-1},{1,2},{-1,
2020-09-22 19:29:44 147 1
原创 第k小数--牛客
题目:给你一个长度为n的序列,求序列中第k小数的多少。输入描述:链接:第k小数–牛客来源:牛客网多组输入,第一行读入一个整数T表示有T组数据。每组数据占两行,第一行为两个整数n,k,表示数列长度和k。第二行为n个用空格隔开的整数。输出描述:对于每组数据,输出它的第k小数是多少。每组数据之间用空格隔开。示例1输入:25 21 4 2 3 43 33 2 1输出:23思路: 这道题可能会有大量的输入数据,普通的输入可能会超时,这道题需要用到快读和nth_element()函
2020-09-02 19:44:20 463
原创 模拟练习--序列计数(蓝桥杯)
【问题描述】 小明想知道,满足以下条件的正整数序列的数量:第一项为 n;第二项不超过 n;从第三项开始,每一项小于前两项的差的绝对值。 请计算,对于给定的 n,有多少种满足条件的序列。【输入格式】 输入一行包含一个整数 n。【输出格式】 输出一个整数,表示答案。答案可能很大,请输出答案除以10000的余数。【样例输入】4【样例输出】7【样例说明】以下是满足条件的序列:4 14 1 14 1 24 24 2 14 34 4最开始做这道题的时候,最先想到的是用递归的.
2020-07-26 15:16:59 328
原创 包子凑数--递推
题目:小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 N种蒸笼,其中第i种蒸笼恰好能放 Ai个包子。每种蒸笼都有非常多笼,可以认为是无限笼。每当有顾客想买X个包子,卖包子的大叔就会迅速选出若干笼包子来,使得这若干笼中恰好一共有 X个包子。比如一共有 3种蒸笼,分别能放 3,4和5个包子。当顾客想买 11个包子时,大叔就会选 2笼3个的再加 1笼 5个的(也可能选出 1笼 3个的再加 2笼 4个的)。当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有 3种蒸笼,分别能放 4、5和
2020-07-23 19:16:33 147
原创 Infinite String Comparision --2020牛客暑期多校训练营(第一场)
Infinite String Comparision思路:这道题看起来不是很难,但是里面omparing a∞-b∞,所以需要注意两个字符串比较的方式。在比较的时候用循环,并不需要将不同长度的字符串重复,延长类似无穷长进行比较,只需要将两者各自循环重复一次若无答案便说明二者“=”,否则会出现a[i]>a[j]或a[i]<a[j]的。代码如下:#include <iostream>#include <string>using namespace std;in
2020-07-19 17:55:17 265
原创 动态规划--完全背包
完全背包问题#include <iostream>#include <algorithm>using namespace std;int main(){ int i,j,n,bagv,v[1001],w[1001],dp[1001][1001]; cin>>n>>bagv; for(i=1;i<=n;i++) { cin>>v[i]>>w[i]; } for(i=1;i<=n;i++) { f
2020-07-12 20:17:21 127
原创 蓝桥杯练习--分考场(回溯递归)
蓝桥杯练习–分考场(回溯递归)题目:n个人参加某项特殊考试。为了公平,要求任何两个认识的人不能分在同一个考场。求至少需要分几个考场才能满足条件。输入格式: 第一行,一个整数n(1<n<100),表示参加考试的人数。第二行,一个整数m,表示接下来有m行数据以下m行每行的格式为:两个整数a,b,用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。输出格式: 一行一个整数,表示最少分几个考场。思路:这道题是一道看起来不太简单的题,但只要有了明白的解题思
2020-07-10 17:16:34 733
原创 三角形判断--牛客
题目:链接:牛客练习赛来源:牛客网KiKi想知道已经给出的三条边a,b,c能否构成三角形,如果能构成三角形,判断三角形的类型(等边三角形、等腰三角形或普通三角形)。输入:题目有多组输入数据,每一行输入三个a,b,c(0<a,b,c<1000),作为三角形的三个边,用空格分隔。输出:针对每组输入数据,输出占一行,如果能构成三角形,等边三角形则输出“Equilateral triangle!”,等腰三角形则输出“Isosceles triangle!”,其余的三角形则输出“Ordina
2020-07-06 08:51:49 700
原创 平方数--(牛客)
题目: 牛妹是一个喜欢完全平方数的女孩子。牛妹每次看到一个数 x,都想求出离 x 最近的完全平方数 y。每次手算太麻烦,所以牛妹希望你能写个程序帮她解决这个问题。形式化地讲,你需要求出一个正整数 y,满足 y 可以表示成 a2(a 是正整数),使得 |x-y| 的值最小。可以证明这样的 y 是唯一的。链接:https://ac.nowcoder.com/acm/problem/205350来源:牛客网输入: 一行,一个整数 x (1≤x≤1012)x\ (1\le x\le 10^{12})x
2020-07-05 12:07:34 500
原创 基础练习 分解质因数--(蓝桥练习)
求出区间[a,b]中所有整数的质因数分解。输入格式 输入两个整数a,b。输出格式 每行输出一个数的分解,形如k=a1a2a3…(a1<=a2<=a3…,k也是从小到大的)(具体可看样例)样例输入3 10样例输出3=34=225=56=237=78=2229=3310=25#include <iostream>#include <vector>using namespace std;vector <int> prime[
2020-07-03 10:56:09 239
原创 十六进制转八进制--蓝桥练习
问题描述给定n个十六进制正整数,输出它们对应的八进制数。输入格式输入的第一行为一个正整数n (1<=n<=10)。接下来n行,每行一个由09、大写字母AF组成的字符串,表示要转换的十六进制正整数,每个十六进制数长度不超过100000。输出格式输出n行,每行为输入对应的八进制正整数。【注意】输入的十六进制数不会有前导0,比如012A。输出的八进制数也不能有前导0。样例输入239123ABC样例输出714435274【提示】先将十六进制数转换成某进制数,再由某进制
2020-06-30 15:24:44 306
原创 矩阵乘法——蓝桥练习
题目:给定一个N阶矩阵A,输出A的M次幂(M是非负整数)例如: A = 1 2 3 4 A的2次幂 7 10 15 22 输入格式 第一行是一个正整数N、M(1<=N<=30, 0<=M<=5),表示矩阵A的阶数和要求的幂数接下来N行,每行N个绝对值不超过10的非负整数,描述矩阵A的值 输出格式 输出共N行,每行N个整数,表示A的M次幂所对应的矩阵。相邻的数之间用一个空格隔开#include <iostream>#includ
2020-06-29 09:31:20 472
原创 快速读入(快读)
在一些题目中,需要输入很多的数据,而时间却还限制着,这是我们就需要考虑提高输入效率。scanf的输入效率要高于cin,一般来说cin不能过的用scanf也许就能过,但总有情况需要更高的输入效率,而getchar的输入效率又高于scanf,于是就用这个方法输入数据。代码如下:#include <iostream>using namespace std;#define re registerinline int read(){ re int x=0,f=1; re cha
2020-06-28 09:21:53 273
原创 蓝桥杯——Sticks(搜索)
题目:George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please hel
2020-06-28 09:13:43 849
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人