3 睡不着kkk

学生身份

我要认证

暂无相关简介

等级
TA的排名 9w+

PAT | T1027 Larry and Inversions

这里主要就是要注意:对于某一个排列[i … j],假设已知其逆序对数为X,将其reverse后的逆序对数为(i - j) * (i - j + 1) / 2而对于某个排列[1,…,i,…,j,…,n],假设已知其逆序对数为wholeSeq,将[i,…,j]reverse后,整个排列的逆序对数为wholeSeq - 2 * X + (i - j) * (i - j + 1) / 2;附用线段树...

2020-04-21 19:29:17

PAT | T1026 String of Colorful Beads

啥玩意这是。。。最大珠子种类数和串最大长度咋都用N表示,整的我一直段错误,最后干脆直接全开最大了#include <iostream>#include <queue>using namespace std;const int maxn = 1e5+ 5;const int maxType = 1e5+ 5;int value[maxType];int s...

2020-04-20 23:00:11

PAT | T1025 Keep at Most 100 Characters

动态规划dp#include <iostream>#include <string>#include <unordered_set>using namespace std;typedef long long ll;const int mod = 1000000007;ll dp[110][1010]; // dp[i][j] : s[0......

2020-04-20 21:36:37

PAT | T1024 Currency Exchange Centers

总算遇到一道会做的#include <iostream>#include <string>#include <vector>#include <algorithm>#include <unordered_set>using namespace std;const int maxn = 1e4 + 5;struct E...

2020-04-20 20:25:40

PAT | T1021 Safe Fruit

最后两个点超时了。。26分#include <iostream>#include <vector>#include <unordered_set>#include <climits>#include <algorithm>using namespace std;struct Fruit{ int id,price; ...

2020-04-19 22:07:48

PAT | T1018 Subnumbers

这道题没想出来,借鉴了https://blog.csdn.net/richenyunqi/article/details/87891111大佬的算法#include <iostream>#include <string>using namespace std;typedef long long ll;const ll mod = 1000000007;co...

2020-04-19 14:11:37

PAT | T1017 The Best Peak Shape

又是测试点3。。。34分#include <iostream>using namespace std;const int maxn = 1e4 + 5;int seq[maxn];int up[maxn]; // up[i] : 从前往后以seq[i]结尾的最长递增子序列int down[maxn];int main(){ int n; scanf("%d",...

2020-04-18 22:24:24

PAT | T1016 Uniqueness of MST

测试点3答案错误,31分#include <iostream>#include <vector>#include <algorithm>#include <unordered_set>using namespace std;const int maxn = 510;typedef long long ll;struct Edge...

2020-04-18 21:36:16

PAT | T1015 Letter-moving Game

越发觉得自己很菜。。。这道题参考了https://blog.csdn.net/jtjy568805874/article/details/53610545大佬的代码,自己没想出来,哭哭#include <iostream>#include <string>using namespace std;const int maxn = 1010;int dp[ma...

2020-04-18 20:52:49

PAT | T1014 Circles of Friends

1013看不懂,来1014了hhh2次bfs找最深的深度(应该是两次?)#include <iostream>#include <unordered_set>#include <queue>#include <vector>using namespace std;bool m[1010][1010];bool vis[1010]...

2020-04-18 19:54:39

PAT | T1012 Greedy Snake

累死了累死了,好多边界条件,一定要想清楚再写,后面修修补补,有很多地方应该都可以删掉的。好在数据量很小,直接dfs即可#include <iostream>#include <climits>using namespace std;bool map[20][20]; // true表示能走bool vis[20][20]; // 某个点有没有被访问过in...

2020-04-17 22:36:07

PAT | T1011 Cut Rectangles

写了一个半小时,测试点3和4答案错误,应该是某个情况没考虑到(我觉得应该是翻转没考虑)扣了三分,还行吧,考试的时候这三分就不要了以下是AC代码(附详细注释):#include <iostream>#include <vector>#include <climits>#include <cmath>using namespace std;...

2020-04-17 20:36:01

PAT | T1010 Lehmer Code

和1009一样的,直接套我1009的模板就行,嘻嘻#include <iostream>using namespace std;typedef long long ll;// ================================= Segment Tree ================================= const int maxn =...

2020-04-15 21:02:58

PAT | T1009 Triple Inversions

线段树求逆序对,线段树模板可以直接用,是我在AgOH大佬那里摘下来的,加了一些注释啥的,只有少数地方需要改动。#include <iostream>using namespace std;typedef long long ll;// ================================= Segment Tree ======================...

2020-04-15 20:43:56

PAT | T1008 Airline Routes

Edge数组最开始开成了Edge[maxn]导致最后一个点一直段错误。#include <iostream>#include <stack>#include <algorithm>using namespace std;const int maxn = 10010;const int maxm = 6 * maxn;struct E{ ...

2020-04-15 13:51:39

PAT | T1007 Red-black Tree

去学了几天高级数据结构和算法,莫队,fhq Treap,线段树啥的,也不知道有没有用倒数第二个测试点超时了。33分 // Red-black Tree #include <iostream>using namespace std;const int maxn = 505;const int con = 1000000007;typedef long long ll;...

2020-04-15 12:10:39

PAT | T1004 To Buy or Not to Buy - Hard Version(待优化)

28分,有3个测试点超时,暂时还没想出怎么优化。#include <iostream>#include <string>#include <unordered_map>#include <climits>using namespace std;struct Beads{ unordered_map<char,int> c...

2020-04-05 12:08:58

PAT | T1003 Universal Travel Sites

网络流算法:关于网络流是什么#include <queue>#include <cstdio>#include <string>#include <iostream>#include <climits>#include <unordered_map>using namespace std;const int ...

2020-04-04 12:32:05

PAT | T1002 Business

动态规划自己做出来了我好快乐。这道题是这样的,首先所有projects按截止日期排序,若截止日期相同则按所需时间排序,若所需时间相同则按利润排序。dp[i][j]表示:考虑0~i个project的时候,截止日期为j时,所能获得的最大利润。那么最后的答案就在dp[n - 1][maxD]中(maxD是在读入project的时候记录的最大截止日期)1.先初始化dp的第一行,即看第一个proje...

2020-04-03 12:35:45

PAT | T1001 Battle Over Cities - Hard Version

Top确实难多了这道题我是将一开始就连通的路cost改成0,然后对每个陷落的城市,做一次kruskal,统计出最大的代价。一开始顶点编号写成了0~n - 1,导致很多测试点出错,下次一定要小心,不能再犯这种低级错误了!#include <iostream>#include <vector>#include <algorithm>#include &l...

2020-04-03 10:41:19

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 分享学徒
    分享学徒
    成功上传1个资源即可获取