- 博客(68)
- 收藏
- 关注
原创 P5638 【CSGRound2】光骓者的荣耀(前缀和+模拟)
题目链接解题思路:总时间减去最大的k段路程时间和,直接模拟就可以(我代码写的有点太烂了。。。)AC代码:#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<string>using namespace std;long long a[1000005],res[1000005],f[1000005];int main(){
2021-04-14 19:05:07 120
原创 P1387 最大正方形(二维前缀和、DP)
题目链接解题思路:动态规划,二维前缀和(相关知识可以看OI-Wiki关于前缀和这一部分知识)。res[i][j]表示以点i,j为右下角的点能够构成的最大正方形的边长。当a[i][j]==1时,点i,j才能作为正方形的右下角;对于一个已经确定的res[i][j]=x,它表明包括节点i,j在内向上和向左扫过的x个点所构成的正方形中所有的a值都为1;可以当作先看向上向做扫最多到多少,即取二者最小值min(res[i-1][j],res[i][j-1]),然后看左上角点是否可行即min(min(res[
2021-04-14 18:59:15 221
原创 洛谷 P1219 [USACO1.5]八皇后 Checker Challenge(dfs)
题目链接解题思路:b1和b2分别保证每行、每列有且只有一个,b3表示每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子,采用dfs进行搜索即可。AC代码#include<cstdio>#include<iostream>#include<cmath>#include<algorithm>#define maxn 100using namespace std;int a[maxn],n,ans;int b1[maxn],b2[max
2020-11-15 01:19:52 130
原创 P3371 【模板】单源最短路径(弱化版)P4779 【模板】单源最短路径(标准版)(链式前向星存图+dijkstra求单源最短路+堆优化+)
P3371题目链接P4779题目链接解题思路:链式前向星存图+dijkstra求单源最短路+堆优化AC代码#include<iostream>#include<cstdio>#include<map>#include<vector>#include<algorithm>#include<cstring>#include<cmath>#include<queue>#include<m
2020-11-02 09:28:26 125
原创 7-14 公路村村通 (30分)
题目链接解题思路:并查集变形AC代码:#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<string>#include<map>#include<stack>#include<queue>using namespace std;int n,
2020-10-28 00:46:35 199
原创 7-13 最长对称子串 (25分)
题目链接解题思路:字符串处理AC代码:#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<string>#include<map>#include<stack>#include<queue>using namespace std;int ma
2020-10-28 00:45:36 139
原创 7-12 朋友圈 (25分)(并查集)
题目链接解题思路:并查集AC代码:#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;int fa[30005],res[30005];inline bool cmp(int a,int b){ return a>b;}void init(){ for(int i=1;i<=300
2020-10-28 00:44:36 190
原创 7-6 树的遍历 (25分)(树的后序、中序、前序、层序遍历)
题目链接解题思路:根据后序和中序序列在构建前序序列的同时用map记录想对应值AC代码:#include<iostream>#include<cstdio>#include<vector>#include<map>using namespace std;vector<int>in,post;map<int,int> mp;void pre(int root,int start,int end,int index){
2020-10-28 00:42:28 206
原创 7-5 列出连通集 (25分)(简单搜索 dfs+bfs)
题目链接解题思路:模板题,简单搜索,根据数据建图然后分别dfs和bfs输出即可AC代码:#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<string>#include<map>#include<stack>#include<queue>us
2020-10-28 00:40:14 509 1
原创 7-10 猴子选大王 (20分)
题目链接解题思路:水题,用vis表示是否被淘汰,用res遍历所有猴子,如果vis就ans++,否则下一个猴子。AC代码:#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<string>#include<map>#include<stack>using na
2020-10-27 17:43:38 237
原创 7-8 最长连续递增子序列 (20分)
题目链接解题思路:水题,从前往后找,每遇到更长连续递增子序列就保存下该子序列地址并记录长度。AC代码:#include<cstdio>#include<iostream>#include<algorithm>#include<cmath>#include<cstring>using namespace std;int a[100005];int main(){ int n,id=0,len=1,mi=0,ml=1;//
2020-10-27 17:37:51 303
原创 7-11 小于m的最大的10个素数 (15分)
题目链接解题思路:水题,从大向小找够十个,最朴素的方法判断素数即可AC代码:#include<cstdio>#include<iostream>#include<algorithm>#include<cmath>#include<cstring>using namespace std;int main(){ int m,ans=0,i,j; scanf("%d",&m); for(i=m-1;i&
2020-10-27 17:34:17 1614
原创 7-9 猴子吃桃问题 (15分)
题目链接解题思路:水题AC代码:#include<stdio.h>int main(){ int n; scanf("%d",&n); n--; int ans=1; while(n--) { ans=(ans+1)*2; } printf("%d\n",ans); return 0;}
2020-10-27 17:32:37 513
原创 7-4 A除以B (10分)
题目链接解题思路:水题AC代码:#include<cstdio>#include<iostream>using namespace std;int main(){ int a,b; scanf("%d %d",&a,&b); if(b>0) printf("%d/%d=%.2lf\n",a,b,(double)a/b); else if(b<0) printf("%d/(%d)=
2020-10-27 17:31:25 419
原创 7-3 大笨钟 (10分)
题目链接解题思路:水题AC代码:#include<cstdio>#include<iostream>using namespace std;int main(){ int hh,mm; scanf("%d:%d",&hh,&mm); if((hh>=0&&hh<12)||(hh==12&&mm==0)) printf("Only %02d:%02d. Too early
2020-10-27 17:30:12 1285
原创 7-2 日期格式化 (5分)
题目链接解题思路:水题,注意补零AC代码:#include<cstdio>#include<iostream>using namespace std;int main(){ int m,d,y; scanf("%d-%d-%d",&m,&d,&y); printf("%04d-%02d-%02d\n",y,m,d); return 0;}...
2020-10-27 17:29:00 416
原创 7-1 是不是太胖了 (5分)
题目链接思路:水题AC代码:#include<iostream>using namespace std;int main(){ int h; cin>>h; printf("%.1lf\n",(double)(h-100)*0.9*2); return 0;}
2020-10-27 17:27:44 273
原创 树状数组学习笔记
树状数组(Binary Index Tree, BIT)也是很多人心中最简洁优美的数据结构之一。最简单的树状数组支持两种操作,时间复杂度均为 :单点修改:更改数组中一个元素的值区间查询:查询一个区间内所有元素的和当然,树状数组能维护的不局限于加法,支持的操作也不止这两种,甚至有大佬能用树状数组实现平衡树,但这篇笔记不会深入讨论(因为我也还不是很懂)。树状数组的引入回顾一下,我们说,我们要实现两种操作:单点修改和区间求和。对于普通数组而言,单点修改的时间复杂度是 O(1)O(1)O(1),但区
2020-10-27 17:01:55 69
原创 最短路问题(Floyd、Bellman-Ford算法、SPFA算法、Dijkstra算法)+打印路径
最短路问题分为两类:单源最短路和多源最短路。前者只需要求一个固定的起点到各个顶点的最短路径,后者则要求得出任意两个顶点之间的最短路径。我们先来看多源最短路问题。Floyd算法int dist[400][400];void Floyd(int n){ for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
2020-10-27 08:43:50 310
原创 PTA 7-25 朋友圈 (25分) 数据结构与算法题目集(中文)(并查集)
题目链接思路:并查集有关并查集知识可以看此博客。AC代码#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;int fa[30005],res[30005];inline bool cmp(int a,int b){ return a>b;}inline void init(){ f
2020-10-24 16:42:57 326
原创 洛谷P3958 奶酪(并查集)NOIP提高组2017年D2T1
题目链接思路:并查集我们把所有空洞划分为若干个集合,一旦两个空洞相交或相切,就把它们放到同一个集合中。我们还可以划出2个特殊元素,分别表示底部和顶部,如果一个空洞与底部接触,则把它与表示底部的元素放在同一个集合中,顶部同理。最后,只需要看顶部和底部是不是在同一个集合中即可。这完全可以通过并查集实现。相关知识可以看此篇博客。AC代码#include<iostream>#include<cstdio>#include<cstring>#include<
2020-10-24 15:56:43 184
原创 洛谷P1551 亲戚(并查集)
题目链接思路:并查集的模板题目关于并查集相关知识可以看此博客AC代码#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int MAXN=5005;int fa[MAXN],rank[MAXN];inline void init(int n)//初始化{ for(int i=0;i<n;i++) { fa[
2020-10-24 15:36:50 279
原创 并查集学习
并查集被很多人认为是最简洁而优雅的数据结构之一,主要用于解决一些元素分组的问题。它管理一系列不相交的集合,并支持两种操作:合并(Union):把两个不相交的集合合并为一个集合。查询(Find):查询两个元素是否在同一个集合中。并查集的重要思想在于,用集合中的一个元素代表集合。我曾看过一个有趣的比喻,把集合比喻成帮派,而代表元素则是帮主。有兴趣的可以看这篇博客。并查集模板汇总:最简单版本//初始化int fa[MAXN];inline void init(int n){ for
2020-10-24 15:18:51 167
原创 L1-005 考试座位号 (15分)
题目链接AC代码#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<string>#include<map>#include<stack>using namespace std;typedef long long ll;const int maxn=1e6
2020-10-24 14:44:37 59
原创 L1-004 计算摄氏温度 (5分)
题目链接AC代码#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<string>#include<map>#include<stack>using namespace std;typedef long long ll;const int maxn=1e6
2020-10-20 19:19:50 112
原创 L1-003 个位数统计 (15分)
题目链接思路乙级题目里的同一个题AC代码#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<string>#include<map>#include<stack>using namespace std;typedef long long ll;cons
2020-10-20 19:15:23 42
原创 L1-002 打印沙漏 (20分)
题目链接AC代码#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<string>#include<map>#include<stack>using namespace std;typedef long long ll;const int maxn=1e6
2020-10-20 19:12:34 64
原创 L1-001 Hello World (5分)
题目链接AC代码#include<iostream>using namespace std;int main(){ cout<<"Hello World!"<<endl; return 0;}
2020-10-20 19:11:34 58
原创 停止更新乙级题目了。
本来是为了备战天梯赛才来刷的PAT题目,本来想着比赛前把这三个等级题目都做做,后来发现学校规定了要做的题集。。。。。。停更了,以后有机会的话再把这些水题刷完,虽然不一定有时间了。。。。。。...
2020-10-20 18:14:17 54
转载 1025 反转链表 (25分)+测试点详解
题目链接转载自https://blog.csdn.net/qq_45735810/article/details/106884432?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLe
2020-10-20 18:10:24 539
原创 1024 科学计数法 (20分)+测试点5
题目链接思路%[] 的意思是:读入此集合所限定的那些字符。例如 %[A-Z] 是指接受大写字母,一旦遇到非大写字母便停止接受,而 %[^] 是指不要读入此集合所限定的那些字符。例如 % [^A-Z] 是指不接受大写字母,一旦遇到大写字母便停止接受。测试点5不过可能是数组开小了AC代码#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<c
2020-10-20 09:08:50 580 1
原创 PAT 乙级 1023 组个最小数 (20分)
题目链接AC代码代码1#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<string>#include<map>#include<stack>using namespace std;typedef long long ll;const int maxn
2020-10-20 08:46:02 43
原创 1022 D进制的A+B (20分)+测试点3详解+栈
题目链接思路用栈存放,先进后出测试点3不过可能是没考虑a+b为0的情况AC代码#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<string>#include<map>#include<stack>using namespace std;typede
2020-10-20 00:26:31 187
原创 1021 个位数统计 (15分) + map
题目链接AC代码#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<string>#include<map>#include<stack>using namespace std;typedef long long ll;const int maxn=1e6
2020-10-20 00:14:56 55
原创 1020 月饼 (25分) + 测试点解析
题目链接思路有点贪心的意思,总是先卖单价最高的就好测试点2要注意库存什么都可能不是整数其他的测试点要注意考虑一个是可能需求比你库存还多,一个是可能根本就没需求AC代码#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<string>#include<map>#inc
2020-10-19 23:53:40 610
原创 1019 数字黑洞 (20分) +测试点解析 +测试样例
题目链接思路主要坑可能是格式问题,输出的时候要都按照四位数字输出,即要补0,但如果你测试点2、3、4没过的话可能是因为没考虑输入的数可能不足四位(虽然题目中说是四位数,挺离谱的)。。。。。。测试样例输入10输出1000 - 0001 = 09999990 - 0999 = 89919981 - 1899 = 80828820 - 0288 = 85328532 - 2358 = 6174AC代码#include<iostream>#include<cstdio
2020-10-19 23:23:12 1188 5
原创 1018 锤子剪刀布 (20分)
题目链接AC代码#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<string>#include<map>#include<stack>using namespace std;typedef long long ll;const int maxn=1e6
2020-10-19 21:10:49 52
原创 1017 A除以B (20分)+测试点1解析+测试样例
题目链接思路用数组或者字符串处理大数本题如果测试点1不过可能是没考虑A<B的情况例如输入1 2输出0 1AC代码#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<string>#include<map>#include<stack>u
2020-10-19 20:47:19 453 1
原创 1016 部分A+B (15分)
题目链接AC代码#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<string>#include<map>#include<stack>using namespace std;typedef long long ll;const int maxn=1e6
2020-10-19 20:02:50 34
原创 1015 德才论 (25分)
题目链接AC代码#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<string>#include<map>#include<stack>using namespace std;typedef long long ll;const int maxn=1e6
2020-10-19 19:39:10 88
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人