2 一粒大榴莲

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 8w+

PTA团体程序设计天梯赛-练习集 L2-031 深入虎穴(BFS)

著名的王牌间谍 007 需要执行一次任务,获取敌方的机密情报。已知情报藏在一个地下迷宫里,迷宫只有一个入口,里面有很多条通路,每条路通向一扇门。每一扇门背后或者是一个房间,或者又有很多条路,同样是每条路通向一扇门…… 他的手里有一张表格,是其他间谍帮他收集到的情报,他们记下了每扇门的编号,以及这扇门背后的每一条通路所到达的门的编号。007 发现不存在两条路通向同一扇门。内线告诉他,情报就藏在迷宫的最深处。但是这个迷宫太大了,他需要你的帮助 —— 请编程帮他找出距离入口最远的那扇门。输入格式:输入首先在

2020-08-07 17:08:25

力扣 1514. 概率最大的路径(Dijkstra+优先队列)

class Solution {public: double maxProbability(int n, vector<vector<int>>& edges, vector<double>& s, int start, int end) { vector<pair<double,int>> e[n]; vector<int> vis(n,0); f...

2020-07-31 12:28:30

PTA团体程序设计天梯赛-练习集 L2-029 特立独行的幸福

对一个十进制数的各位数字做一次平方和,称作一次迭代。如果一个十进制数能通过若干次迭代得到 1,就称该数为幸福数。1 是一个幸福数。此外,例如 19 经过 1 次迭代得到 82,2 次迭代后得到 68,3 次迭代后得到 100,最后得到 1。则 19 就是幸福数。显然,在一个幸福数迭代到 1 的过程中经过的数字都是幸福数,它们的幸福是依附于初始数字的。例如 82、68、100 的幸福是依附于 19 的。而一个特立独行的幸福数,是在一个有限的区间内不依附于任何其它数字的;其独立性就是依附于它的的幸福数的个数。如

2020-07-25 22:11:33

力扣 464. 我能赢吗(c++ bitset记忆化搜索)

class Solution {public: int a,b; unordered_map<unsigned long long,bool> mp; bool dfs(int sum,bitset<25> bs){ if(sum >= b) return true; if(mp.find(bs.to_ullong()) != mp.end()) return mp[bs.to_ullong()]; ..

2020-07-17 21:35:40

力扣 315. 计算右侧小于当前元素的个数(树状数组+离散化)

用map记录以及离散化都是为了应对出现负数的情况,更新树状数组的时候因为是严格小于,所以更新的时候得加1。class Solution { int len;vector<int> arr;public: void update(int n,int k){ for(int i = n;i <= len;i += (i)&(-i)) arr[i] += k; } int getnum(int n){ .

2020-07-11 20:10:41

PTA团体程序设计天梯赛GPLT L3-005. 垃圾箱分布(Dijkstra)

大家倒垃圾的时候,都希望垃圾箱距离自己比较近,但是谁都不愿意守着垃圾箱住。所以垃圾箱的位置必须选在到所有居民点的最短距离最长的地方,同时还要保证每个居民点都在距离它一个不太远的范围内。现给定一个居民区的地图,以及若干垃圾箱的候选地点,请你推荐最合适的地点。如果解不唯一,则输出到所有居民点的平均距离最短的那个解。如果这样的解还是不唯一,则输出编号最小的地点。输入格式:输入第一行给出4个正整数:N(<= 103)是居民点的个数;M(<= 10)是垃圾箱候选地点的个数;K(<= 104)是

2020-07-08 11:22:59

PTA团体程序设计天梯赛-练习集 L2-027 名人堂与代金券(结构体+自定义cmp)

对于在中国大学MOOC学习“数据结构”课程的学生,想要获得一张合格证书,总评成绩必须达到 60 分及以上,并且有另加福利:总评分在 [G, 100] 区间内者,可以得到 50 元 PAT 代金券;在 [60, G) 区间内者,可以得到 20 元PAT代金券。全国考点通用,一年有效。同时任课老师还会把总评成绩前 K 名的学生列入课程“名人堂”。本题就请你编写程序,帮助老师列出名人堂的学生,并统计一共发出了面值多少元的 PAT 代金券。输入格式:输入在第一行给出 3 个整数,分别是 N(不超过 10 000

2020-07-07 15:31:12

PTA团体程序设计天梯赛-练习集 L2-026 小字辈(dfs)

本题给定一个庞大家族的家谱,要请你给出最小一辈的名单。输入格式:输入在第一行给出家族人口总数 N(不超过 100 000 的正整数) —— 简单起见,我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号,其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。输出格式:首先输出最小的辈分(老祖宗的辈分为 1,以下逐级递增)。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔,行首尾不得有多余空格。输入样例:

2020-07-07 00:17:32

PTA团体程序设计天梯赛-练习集 L2-025 分而治之(邻接表)

分而治之,各个击破是兵家常用的策略之一。在战争中,我们希望首先攻下敌方的部分城市,使其剩余的城市变成孤立无援,然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序,判断每个方案的可行性。输入格式:输入在第一行给出两个正整数 N 和 M(均不超过10 000),分别为敌方城市个数(于是默认城市从 1 到 N 编号)和连接两城市的通路条数。随后 M 行,每行给出一条通路所连接的两个城市的编号,其间以一个空格分隔。在城市信息之后给出参谋部的系列方案,即一个正整数 K (<= 100)和随

2020-07-05 21:32:34

力扣 统计全 1 子矩形(前缀和+动态规划)

给你一个只包含 0 和 1 的 rows * columns 矩阵 mat ,请你返回有多少个 子矩形 的元素全部都是 1 。示例 1:输入:mat =[[1,0,1],[1,1,0],[1,1,0]]输出:13解释:有 6 个 1x1 的矩形。有 2 个 1x2 的矩形。有 3 个 2x1 的矩形。有 1 个 2x2 的矩形。有 1 个 3x1 的矩形。矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13 。示例 2:输入:mat =[[0,1,1,0],[0,

2020-07-05 17:59:06

PTA团体程序设计天梯赛-练习集 L2-024 部落(并查集)

在一个社区里,每个人都有自己的小圈子,还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里,于是要请你统计一下,在一个给定社区中,到底有多少个互不相交的部落?并且检查任意两个人是否属于同一个部落。输入格式:输入在第一行给出一个正整数N(<= 104),是已知小圈子的个数。随后N行,每行按下列格式给出一个小圈子里的人:K P[1] P[2] … P[K]其中K是小圈子里的人数,P[i](i=1, …, K)是小圈子里每个人的编号。这里所有人的编号从1开始连续编号,最大编号不会超过1

2020-07-04 15:35:01

力扣 最长有效括号(三种解法)(动态规划+栈)

动态规划:class Solution {public: int longestValidParentheses(string s) { int maxans = 0, n = s.length(); vector<int> dp(n, 0); for (int i = 1; i < n; i++) { if (s[i] == ')') { if (s[i - 1] == .

2020-07-04 10:37:59

PTA团体程序设计天梯赛-练习集 L2-023 图着色问题

图着色问题是一个著名的NP完全问题。给定无向图 G = (V, E),问可否用K种颜色为V中的每一个顶点分配一种颜色,使得不会有两个相邻顶点具有同一种颜色?但本题并不是要你解决这个着色问题,而是对给定的一种颜色分配,请你判断这是否是图着色问题的一个解。输入格式:输入在第一行给出3个整数V(0 < V <= 500)、E(>= 0)和K(0 < K <= V),分别是无向图的顶点数、边数、以及颜色数。顶点和颜色都从1到V编号。随后E行,每行给出一条边的两个端点的编号。在图的

2020-07-03 17:27:12

PTA团体程序设计天梯赛-练习集 L3-004 肿瘤诊断(bfs和dfs解法)

在诊断肿瘤疾病时,计算肿瘤体积是很重要的一环。给定病灶扫描切片中标注出的疑似肿瘤区域,请你计算肿瘤的体积。输入格式:输入第一行给出4个正整数:M、N、L、T,其中M和N是每张切片的尺寸(即每张切片是一个M×N的像素矩阵。最大分辨率是1286×128);L(<=60)是切片的张数;T是一个整数阈值(若疑似肿瘤的连通体体积小于T,则该小块忽略不计)。最后给出L张切片。每张用一个由0和1组成的M×N的矩阵表示,其中1表示疑似肿瘤的像素,0表示正常像素。由于切片厚度可以认为是一个常数,于是我们只要数连通

2020-07-02 21:50:08

PTA团体程序设计天梯赛-练习集 L2-001 紧急救援(Dijkstra)

作为一个城市的应急救援队伍的负责人,你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候,你的任务是带领你的救援队尽快赶往事发地,同时,一路上召集尽可能多的救援队。输入格式:输入第一行给出4个正整数N、M、S、D,其中N(2<=N<=500)是城市的个数,顺便假设城市的编号为0~(N-1);M是快速道路的条数;S是出发地的城市编号;D是目的地的城市编号。第二行给出N

2020-07-01 11:40:31

力扣 最长重复子数组和最长公共子序列(动态规划)

给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。示例 1:输入:A: [1,2,3,2,1]B: [3,2,1,4,7]输出: 3解释:长度最长的公共子数组是 [3, 2, 1]。最长重复子数组是需要连续的,递推公式为dp[i][j] = dp[i-1][j-1] + 1;最长公共子序列是不需要连续的,递推公式为 dp[i][j] = max(dp[i-1][j-1]+(text2[i - 1] == text1[j - 1]?1:0),dp[i-1][j],d

2020-07-01 10:06:58

PTA团体程序设计天梯赛-练习集 L2-021 点赞狂魔(结构体)

微博上有个“点赞”功能,你可以为你喜欢的博文点个赞表示支持。每篇博文都有一些刻画其特性的标签,而你点赞的博文的类型,也间接刻画了你的特性。然而有这么一种人,他们会通过给自己看到的一切内容点赞来狂刷存在感,这种人就被称为“点赞狂魔”。他们点赞的标签非常分散,无法体现出明显的特性。本题就要求你写个程序,通过统计每个人点赞的不同标签的数量,找出前3名点赞狂魔。输入格式:输入在第一行给出一个正整数N(<=100),是待统计的用户数。随后N行,每行列出一位用户的点赞标签。格式为“Name K F1 … FK

2020-06-30 22:04:36

PTA团体程序设计天梯赛-练习集 L1-005 考试座位号(结构体)

#include <bits/stdc++.h>using namespace std;struct STU{ string number; int k;}stu[1010];int main(){ int n; cin>>n; for(int i = 0;i < n;i++){ string a; int b,c; cin>>a>>b>>c;

2020-06-30 21:21:49

PTA团体程序设计天梯赛-练习集 L3-003 社交集群(并查集)

在社交网络平台注册时,用户通常会输入自己的兴趣爱好,以便找到和自己兴趣相投的朋友。有部分兴趣相同的人们就形成了“社交集群”。现请你编写程序,找出所有的集群。输入格式:输入的第一行给出正整数N(<=1000),即社交网络中的用户总数(则用户从1到N编号)。随后N行,每行按下列格式列出每个人的兴趣爱好:Ki: hi[1] hi[2] … hi[Ki]其中Ki(>0)是第i个人的兴趣的数量,hi[j]是第i个人的第j项兴趣的编号,编号范围为[1, 1000]内的整数。输出格式:首先在第一行

2020-06-30 17:41:45

PTA团体程序设计天梯赛-练习集 L3-002 特殊堆栈(树状数组)

大家都知道“堆栈”是一种“先进后出”的线性结构,基本操作有“入栈”(将新元素插入栈顶)和“出栈”(将栈顶元素的值返回并从堆栈中将其删除)。现请你实现一种特殊的堆栈,它多了一种操作叫“查中值”,即返回堆栈中所有元素的中值。对于N个元素,若N是偶数,则中值定义为第N/2个最小元;若N是奇数,则中值定义为第(N+1)/2个最小元。输入格式:输入第一行给出正整数N(<= 105)。随后N行,每行给出一个操作指令,为下列3种指令之一:Push keyPopPeekMedian其中Push表示入栈,k

2020-06-29 23:42:23

查看更多

勋章 我的勋章
  • 签到达人
    签到达人
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 技术圈认证
    技术圈认证
    用户完成年度认证,即可获得
  • 阅读者勋章Lv2
    阅读者勋章Lv2
    授予在CSDN APP累计阅读博文达到7天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 学习力
    学习力
    《原力计划【第二季】》第一期主题勋章 ,第一期活动已经结束啦,小伙伴们可以去参加第二期打卡挑战活动获取更多勋章哦。
  • 原力新人
    原力新人
    在《原力计划【第二季】》打卡挑战活动中,成功参与本活动并发布一篇原创文章的博主,即可获得此勋章。
  • 原力探索 · S
    原力探索 · S
    在《原力计划【第二季】》打卡挑战活动中,发布 12 篇原创文章参与活动的博主,即可获得此勋章。(本次活动结束后统一统计发放)
  • 分享学徒
    分享学徒
    成功上传1个资源即可获取