【2021天梯赛训练-1】7-7 抢红包
没有人没抢过红包吧…… 这里给出N个人之间互相发红包、抢红包的记录,请你统计一下他们抢红包的收获。
输入格式:输入第一行给出一个正整数N(≤104),即参与发红包和抢红包的总人数,则这些人从1到N编号。随后N行,第i行给出编号为i的人发红包的记录,格式如下:
123456789KN1 P1 ⋯NK PK
其中K(0≤K≤20)是发出去的红包个数,Ni 是抢到红包的人的编号,Pi (>0)是其抢到的红包金额(以分为单位)。注意:对于同一个人发出的红包,每人最多只能抢1次,不能重复抢。
输出格式:按照收入金额从高到低的递减顺序输出每个人的编号和收入金额(以元为单位,输出小数点后2位)。每个人的信息占一行,两数字间有1个空格。如果收入金额有并列,则按抢到红包的个数递减输出;如果还有并列,则按个人编号递增输出。
输入样例:1234567891011103 2 22 10 58 8 1255 1 345 3 211 5 233 7 13 8 1011 7 88002 1 1000 2 10002 4 250 10 3206 5 11 9 22 8 3 ...
【2021天梯赛训练-1】7-6 连续因子
一个正整数 N 的因子中可能存在若干连续的数字。例如 630 可以分解为 3×5×6×7,其中 5、6、7 就是 3 个连续的数字。给定任一正整数 N,要求编写程序求出最长连续因子的个数,并输出最小的连续因子序列。
输入格式:输入在一行中给出一个正整数 N(1<N<231 )。
输出格式:首先在第 1 行输出最长连续因子的个数;然后在第 2 行中按 因子1因子2……*因子k 的格式输出最小的连续因子序列,其中因子按递增顺序输出,1 不算在内。
输入样例:630
输出样例:3567
123456789101112131415161718192021222324252627282930//将[2,sqrt(n)]内的每一个数均作为一次起点,遍历所有情况#include<bits/stdc++.h>using namespace std;int len=0,start=2;//len记录长度,start记录开始位置int main(){ int n; scanf(&quo ...
【2021天梯赛训练-1】7-4 最长对称子串
对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最长对称子串为s PAT&TAP s,于是你应该输出11。
输入格式:输入在一行中给出长度不超过1000的非空字符串。
输出格式:在一行中输出最长对称子串的长度。
输入样例:1Is PAT&TAP symmetric?
输出样例:111
解题思路考虑两种对称情况
奇对称
偶对称
123456789101112131415161718192021222324252627282930313233343536#include<iostream>using namespace std;int main(){ string s; getline(cin,s); int max=-1; for(int i=0;i<s.size();i++){ int count = -1; for(int a=0;i+a<s.size()& ...
【2021天梯赛训练-1】7-11 人以群分
社交网络中我们给每个人定义了一个“活跃度”,现希望根据这个指标把人群分为两大类,即外向型(outgoing,即活跃度高的)和内向型(introverted,即活跃度低的)。要求两类人群的规模尽可能接近,而他们的总活跃度差距尽可能拉开。
输入格式:输入第一行给出一个正整数N(2≤N≤105)。随后一行给出N个正整数,分别是每个人的活跃度,其间以空格分隔。题目保证这些数字以及它们的和都不会超过231。
输出格式:按下列格式输出:
123Outgoing #: N1Introverted #: N2Diff = N3
其中N1是外向型人的个数;N2是内向型人的个数;N3是两群人总活跃度之差的绝对值。
输入样例1:121023 8 10 99 46 2333 46 1 666 555
输出样例1:123Outgoing #: 5Introverted #: 5Diff = 3611
输入样例2:1213110 79 218 69 3721 100 29 135 2 6 13 5188 85
输出样例2:123Outgoing #: 7Introverted #: 6 ...
天梯赛经验分享-曹晨
天梯赛经验分享-曹晨
author: 曹晨
date: 2020-11-21 20:44:40
无序列表(加号和嵌套)Unordered Lists (+)
String类型操作
insert
erase()
substr()
compare()
find()
replace()
基本算法
dfs和bfs
并查集
单/多源最短路问题
最小生成树
二叉树的遍历
拓扑图
优先队列
最近公共祖先
01背包
kmp思维能力和编写代码能力
思维能力主要考察对算法的理解,但是实际代码比较的短小。比如01背包,并查集,优先队列等,这一部分主要需要大家对算法有比较深入的理解,比如01背包等需要你搞懂内部的原理
代码的编写能力则需要大量的训练,思维可能比较的简单但是代码量比较的多,应该从平时尽量的养成规范的编写代码习惯,背会各种代码模板:DFS。琐碎的知识点
char *,string,const char *之间的转化
字符串和数字之间的转化
stringstream的使用
getline(cin,x) getchar()等等对缓冲区最后一个回车的影响
分割字符串strtok函数
C++ ...
天梯赛经验分享-李振浩
天梯赛经验分享-李振浩
author: 李振浩
date: 2020-11-21 20:44:40注意事项
不要读题,直接看数据,找思路。
先特殊 在一般
事先配置好环境
dev / codeblocks 主题
freopen(“1.txt”, ‘r’, stdin)
不要使用<bits/stdc++.h> 变异很慢
尽量不要使用cin, cout … 用scanf printf
做题经验
pair<T,T>自带排序
dis数组 特殊判断
链表存储 h[N], tot, struct Edge{int to,nxt,w,….}
综合 :https://pintia.cn/problem-sets/994805046380707840/problems/994805051153825792
不要使用map 包括unordered_map 复杂度很玄学
csp 认证:http://118.190.20.162/view.page?gpid=T104
树形化处理dfs 找出口
+1 -1 注意细节
https://pinti ...
PAT乙级题目分享-19计科王伯成
author: 19计科王伯成
date: 2020-11-22 10:44:400、说一些话
开始时间:2020. 4. 9
完成时间:2020. 4. 27
PAT乙级题目集
总的来说,乙级题目刚开始做可能会感觉困难,不太好适应这种编程风格,慢慢的就习惯了,做题的思路也来得越来越快,好多题都是思路很简单但代码十分繁琐。学会C++的基础语法,不需要面向对象的部分,在学会STL几种容器的使用方法和它们的操作函数,刷乙级题的知识储备就足够了。(部分题涉及到了排序算法,但题中有解释)
Java做题也可以,也有许多便利的函数(方法),但Java效率太低,超时是一大问题
1001 害死人不偿命的(3n+1)猜想123456789101112131415161718#include <iostream>using namespace std;int main() { int step=0; int n; cin >> n; for(;n!=1;step++){ if(n%2==0){ ...
C++ 使用分享
C++ 使用分享
author: 樊萌萌
date: 2020-11-20 20:44:40一、常用集合
1.vector也称为单端数组,不同之处在于数组是静态空间,而vector可以动态扩展12345678910111.push_back(ele); 向尾部插入值2.pop_back(); 删除最后一个元素3.insert(,) 迭代器指向pos位置破损插入元素ele,例如 v1.insert(v1.begin(),100);头部(最前边)插入100,第一个参数是迭代器4.insert(,,) 迭代器指向位置pos插入count个元素elev例如 v1.insert(v1.begin(),2,100);在开头插入2个1005.erase(..) 删除迭代器指向的元素6.erase(strat,end) 删除迭代器从start到end之间的元素(左闭右开)7.clear() 删除容器中的所有元素//获取一些特殊位置的值获取第一个元素:v1.front(); 最后一个:v1.back();
相当于二维数组用法,容器嵌套1234567891011121314151617181 ...
天梯赛经验分享-尚梦川
天梯赛经验分享-尚梦川
author: 尚梦川
date: 2020-11-21 20:44:40
day41 7-6 城市间紧急救援
markdown 文章内容作为一个城市的应急救援队伍的负责人,你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候,你的任务是带领你的救援队尽快赶往事发地,同时,一路上召集尽可能多的救援队。
输入格式:
输入第一行给出4个正整数N、M、S、D,其中N(2≤N≤500)是城市的个数,顺便假设城市的编号为0 ~ (N−1);M是快速道路的条数;S是出发地的城市编号;D是目的地的城市编号。第二行给出N个正整数,其中第i个数是第i个城市的救援队的数目,数字间以空格分隔。随后的M行中,每行给出一条快速道路的信息,分别是:城市1、城市2、快速道路的长度,中间用空格分开,数字均为整数且不超过500。输入保证救援可行且最优解唯一。
输出格式:
第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔,输出结尾不能有多余空格。
输入样例:
4 5 0 320 30 40 100 1 11 3 20 3 30 2 ...