甲级专题

PAT甲级-1044 Shopping in Mars

题目题目大意一串项链上有n个钻石，输入给出每个钻石的价格。用m元买一个连续的项链子串（子串长度可为1），如果不能恰好花掉m元，就要找到最小的大于m的子串，如果有重复就输出多个，按递增顺序输出子串的前端和后端索引。原来的思路取连续的子串使和恰等于m，没有恰等于就找最小的大于。可以将子串依次累加，使得每个位置都是起始位置到该位置的序列和，整个数组显递增顺序，就可以用右边减左边

1050 String Subtraction——PAT甲级

Given two strings S1 and S2, S=S1−S2 is defined to be the remaining string after taking all the characters in S2 from S1. Your task is simply to calculate S1−S2 for any given strings. However,

PAT 甲级 1095 Cars on Campus

PAT 甲级 1095 Cars on Campus #include <bits/stdc++.h>using namespace std;const int kMAXN = 10010;struct Car{char id[8];int time;char status[4];} all[kMAXN], valid[kMAXN];int valid_num = 0;map<st

PAT 甲级 1055 The World‘s Richest

PAT 甲级 1055 The World’s Richest 这道题一次AC，但是后来看《算法笔记·上机训练实战指南》中的解析，说由于M<100，所以每个年龄读入100个人，就可以不读入了，这样能显著提高时间，否则测试点二过不了。但是没有写这个预处理也过了，回去看了看时间是400ms，猜想应该是传参都用的是传引用调用，改成传值调用之后果然超时。解析也是用传值调用写的，传引用不香吗。 #i

PAT甲级 1058 A+B in Hogwarts

PAT甲级 1058 A+B in Hogwarts #include<bits/stdc++.h>using namespace std;int main(){#ifdef LOCALfreopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);#endiflong long sickle, galleon

PAT 甲级 1011 World Cup Betting

PAT 甲级 1011 World Cup Betting 简单模拟 #include<bits/stdc++.h>using namespace std;const double EPS=1e-7;int main(){double a,b,c,ans=1;for(int i=0;i<3;++i){cin>>a>>b>>c;if(a-b>-EPS&&a-c>-EPS) {co

PAT 甲级 1096 Consecutive Factors

PAT 甲级 1096 Consecutive Factors #include <bits/stdc++.h>using namespace std;int main(){#ifdef LOCALfreopen("input.txt", "r", stdin);#endifint num, max_len = -1, now_len = 0, beg = 0, now_beg;cin

PAT 甲级 1093 Count PAT‘s

#include <bits/stdc++.h>using namespace std;#define kMOD 1000000007int main(){#ifdef LOCALfreopen("input.txt", "r", stdin);#endifstring s;cin >> s;// 在位置i之前(包括位置i)有多少个P，位置i之后(包括位置i)有多少个Tvector<i

PAT 甲级 1048 Find Coins two pointer的写法

PAT 甲级 1048 Find Coins 这道题可以用二分、散列和two pointers三种方法实现，此前写过二分的方法：PAT 甲级 1048 Find Coins 二分的写法这里是two pointer的写法 #include <bits/stdc++.h>using namespace std;int main(){#ifdef LOCALfreopen("input.t

PAT 甲级 1048 Find Coins 二分的写法

PAT 甲级 1048 Find Coins 二分的写法散列的写法非常简单明了，LeetCode Problem List很前面就有类似的题。其实这道题用二分实现也是可以的，下面是二分的写法。之后准备做一个二分的专题总结。 #include <bits/stdc++.h>using namespace std;int main(){#ifdef LOCALfreopen("input

PAT甲级 1085 Perfect Sequence 二分和双指针（Two Pointers）

二分写法 #include <bits/stdc++.h>using namespace std;int find_upper_bound(const vector<long long>& nums, long long x){int beg = 0, end = nums.size(), mid = beg + (end - beg) / 2;while (beg < end) {mid

PAT 甲级 1038 Recover the Smallest Number 两种思路

这道题的大致思路是每次把能够让拼接后的数字最小的串放在前面，怎么来比较哪个放在前面最小呢？考虑下面两种情况情况1：321 32 324 情况2：131 13 134 显然应该把第一位最小的放在最前面，第一位相同比较第二位，如果所有位都相同呢？比如上面32和13的情况？可以循环进行比较。比如判断321和32谁放在前面的时候，比较3和3，2和2，3和1得到结果321更小，所以321放在前面。这个循环

PAT 甲级 2016年春季

1 PAT 甲级 1108 Finding Average #include <bits/stdc++.h>using namespace std;bool IsValid(string s,double &ans){int c1=0,c2=0,pos_p;for(size_t i=0;i<s.size();++i){if(s[i]=='-') ++c1;else if(s[i]=='.')

PAT 甲级 2016年秋季

1 PAT 甲级 1116 Come on! Let’s C #include <bits/stdc++.h>using namespace std;map<int,string> mp; bool is_prime[10010];void Init(){fill(is_prime,is_prime+10010,true);is_prime[0]=is_prime[1]=false;fo

PAT 甲级 2017年春季

1 PAT 甲级 1124 Raffle for Weibo Followers #include <bits/stdc++.h>using namespace std;string id[1010];set<string> st;int main() {int m,n,s;cin>>m>>n>>s;for(int i=0;i<m;++i) cin>>id[i];if(s>m) cout

PAT 甲级 2017年秋季

1 PAT 甲级 1132 Cut Integer #include <bits/stdc++.h>using namespace std;string num;void Solve(){string s1=num.substr(0,num.size()/2);string s2=num.substr(num.size()/2,num.size()/2);int a,b,c;a=atoi(

每日一题——Python实现PAT甲级1132 Cut Integer（举一反三+思想解读+逐步优化）五千字好文

一个认为一切根源都是“自己不够强”的INTJ 个人主页：用哲学编程-CSDN博客专栏：每日一题——举一反三Python编程学习Python内置函数 Python-3.12.0文档解读目录我的写法正确性和功能性时间复杂度空间复杂度其他点评总结我要更强优化后的时间复杂度和空间复杂度进一步优化哲学和编程思想 1. DRY（Don't Repeat Y

PAT甲级真题及训练集(10)--1036. Boys vs Girls (25)

1036. Boys vs Girls (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue This time you are asked to tell the difference between the lowest grade of a

PAT甲级真题及训练集(9)--1056. Mice and Rice (25)

1056. Mice and Rice (25) 时间限制 100 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue Mice and Rice is the name of a programming contest in which each programmer

PAT甲级真题及训练集(8)--1006. Sign In and Sign Out (25)

1006. Sign In and Sign Out (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue At the beginning of every day, the first person who signs in the comp

PAT甲级真题及训练集(7)--1011. World Cup Betting (20)

1011. World Cup Betting (20) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue With the 2010 FIFA World Cup running, football fans the world over were

PAT甲级真题及训练集(6)--1051. Pop Sequence (25)

1051. Pop Sequence (25) 时间限制 100 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue Given a stack which can keep M numbers at most. Push N numbers in the order o

PAT甲级真题及训练集(5)--1042. Shuffling Machine (20)

1042. Shuffling Machine (20) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue Shuffling is a procedure used to randomize a deck of playing cards. Beca

每日一题——Python实现PAT甲级1116 Come on! Let‘s C（举一反三+思想解读+逐步优化）五千字好文

一个认为一切根源都是“自己不够强”的INTJ 个人主页：用哲学编程-CSDN博客专栏：每日一题——举一反三Python编程学习Python内置函数 Python-3.12.0文档解读目录我的写法代码点评时间复杂度分析空间复杂度分析总结我要更强优化思路优化后的代码时间复杂度分析空间复杂度分析优化总结哲学和编程思想 1. 时间复杂度与空间复

每日一题——Python实现PAT甲级1077 Kuchiguse（举一反三+思想解读+逐步优化）

一个认为一切根源都是“自己不够强”的INTJ 个人主页：用哲学编程-CSDN博客专栏：每日一题——举一反三Python编程学习Python内置函数 Python-3.12.0文档解读目录我的写法代码点评时间复杂度分析空间复杂度分析总结我要更强方案1：利用字典树（后缀树）优化代码（后缀树实现）代码点评时间复杂度分析空间复杂度分析方案2：水平扫

每日一题——Python实现PAT甲级1046 Shortest Distance（举一反三+思想解读+逐步优化）

一个认为一切根源都是“自己不够强”的INTJ 个人主页：用哲学编程-CSDN博客专栏：每日一题——举一反三Python编程学习Python内置函数 Python-3.12.0文档解读目录我的写法专业点评优点改进建议时间复杂度分析空间复杂度分析总结我要更强方法一：优化空间复杂度（保留前缀和）方法二：直接使用距离数组进行查询代码优化解释时间和空