Evolution957-CSDN博客

原创 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 214

原创 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 324

原创洛谷 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 220

原创 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 192

原创 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 246

原创 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 190

原创 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 286

原创 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 285

原创 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 571 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 326

原创 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 367

原创 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 1831

原创 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 609

原创 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 512

原创 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 1408

原创 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 486

原创 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 355

原创树状数组学习笔记

树状数组（Binary Index Tree, BIT）也是很多人心中最简洁优美的数据结构之一。最简单的树状数组支持两种操作，时间复杂度均为：单点修改：更改数组中一个元素的值区间查询：查询一个区间内所有元素的和当然，树状数组能维护的不局限于加法，支持的操作也不止这两种，甚至有大佬能用树状数组实现平衡树，但这篇笔记不会深入讨论（因为我也还不是很懂）。树状数组的引入回顾一下，我们说，我们要实现两种操作：单点修改和区间求和。对于普通数组而言，单点修改的时间复杂度是 O(1)O(1)O(1)，但区

2020-10-27 17:01:55 118

原创最短路问题（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 408

原创 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 402

原创洛谷P3958 奶酪（并查集）NOIP提高组2017年D2T1

题目链接思路：并查集我们把所有空洞划分为若干个集合，一旦两个空洞相交或相切，就把它们放到同一个集合中。我们还可以划出2个特殊元素，分别表示底部和顶部，如果一个空洞与底部接触，则把它与表示底部的元素放在同一个集合中，顶部同理。最后，只需要看顶部和底部是不是在同一个集合中即可。这完全可以通过并查集实现。相关知识可以看此篇博客。AC代码#include<iostream>#include<cstdio>#include<cstring>#include&lt

2020-10-24 15:56:43 250

原创洛谷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 358

原创并查集学习

并查集被很多人认为是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：合并（Union）：把两个不相交的集合合并为一个集合。查询（Find）：查询两个元素是否在同一个集合中。并查集的重要思想在于，用集合中的一个元素代表集合。我曾看过一个有趣的比喻，把集合比喻成帮派，而代表元素则是帮主。有兴趣的可以看这篇博客。并查集模板汇总：最简单版本//初始化int fa[MAXN];inline void init(int n){ for

2020-10-24 15:18:51 225

原创 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 90

原创 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 152

原创 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 74

原创 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 98

原创 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 90

原创停止更新乙级题目了。

本来是为了备战天梯赛才来刷的PAT题目，本来想着比赛前把这三个等级题目都做做，后来发现学校规定了要做的题集。。。。。。停更了，以后有机会的话再把这些水题刷完，虽然不一定有时间了。。。。。。...

2020-10-20 18:14:17 91

转载 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 577

空空如也

空空如也