第二次参加PAT就打了顶级,属于是有点膨胀结果被锤爆了QAQ,第一题模拟题甚至0分,也就后两题稍微做了下。不得不说这PAT数据挺水的,我T3后面发现这么明显的一个逻辑错误,竟然只扣了两分;
T1 The Rescue
一个巨恶心的模拟题,同时也是甲级的T4,顶级也只有4个人做出了这题(顶级本来就只有4个满分,其他有好几个有满分机会的大佬也是栽在了这题上),不说了,一分没有,都是泪QAQ
T2 Prize Game
题意是,给定一个长度为n的数组(可能有负数),以及一个整数x,我们可以有一次机会将数组的某个区间乘上x(也可以不乘),问乘完之后,最大子数组和是多少;
数据范围n<=10^6
经典且普通的dp,难以想象这题居然比T1分值高,跟T3同分值
#include<bits/stdc++.h>
using namespace std;
long long a[1000010],dp[1000010][4],x,n;
int main() {
cin>>n>>x;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) {
dp[i][0]=max({(long long)0,a[i],dp[i-1][0]+a[i]});
dp[i][1]=max({(long long)0,a[i]*x,dp[i-1][0]+a[i]*x,dp[i-1][1]+a[i]*x});
dp[i][2]=max({(long long)0,dp[i-1][1]+a[i],dp[i-1][2]+a[i]});
dp[i][3]=max({(long long)0,dp[i-1][1],dp[i-1][2],dp[i-1][3],dp[i-1][0]});
}
cout<<max({(long long)0,dp[n][0],dp[n][1],dp[n][2],dp[n][3]});
return 0;
}
T3 Memories of Youth
题目的意思是,有m位年轻人,在很久以前,他们每个人都分到了一个code(一个长度为2的string),现在他们想要回忆以前这段时光,于是想知道每个人拿到的code是哪一个,但由于时间太过久远,他们都忘记了。所幸他们还有n张照片,每张照片记录了上面出现了哪些人,以及出现了哪些code(但是哪个人对应哪个code是未知的),现在请你根据这些照片判断,每个人对应的code是哪个,如果不能确定则输出 ‘?’,如果可以确定则输出对应的code;
数据范围m<=54,n<=100
输入格式:
第一行输入m和n;随后对于每张照片,第一行输入一个数字x,表示照片中出现了几个人,第二行输入x个code,第三行输入x个人的编号,均以空格隔开;
输出格式:
按人的编号从小到大输出每个人对应的code,如果不能确定,则输出‘?’;
这道题一开始就给我一种二分图匹配的感觉,但是想了半天,也没法解决不能确定的情况,于是在浪费了半个多小时之后,想到了一种拓扑排序的方法,但拓扑排序属实是把问题搞复杂了,所以这里写的方法是刚刚想到的;
具体想法是,如果说第i个人能够有望与第k个code匹配,那么凡是第i个人出现过的照片,必然包含第k个code;凡是包含了第k个code的照片,必然出现了第i个人;如果同时满足了这两个条件,那么第k个code就能够作为第i个人的备选;如果一个人有两个及以上的code作为备选,那么这个人一定是不能确定的;因为上面的规则是双向的,code和人是等价的,如果按照上面的规则,一个人能对应两个及以上code,反过来说,这其中的每一个code,它也能对应两个及以上的人;
实现比较丑陋QAQ(还是改良后的QAQ)建议直接无视
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt1[200],cnt2[200],idc=0;
unordered_map<string,int>id;
string name[200];
vector<int>have1[200],have2[200];
int d[200],pp[200],p[200],same[200][200];
int main() {
cin>>m>>n;
memset(same,1,sizeof same);
for(int i=1;i<=n;i++) {
int a;
cin>>a;
for(int k=0;k<a;k++) {
string s;
cin>>s;
if(id[s]==0) id[s]=++idc,name[idc]=s;
have1[i].push_back(id[s]);
}
for(int k=0;k<a;k++) {
int s;
cin>>s;
have2[i].push_back(s);
}
}
for(int i=1;i<=n;i++) {
bool h1[200]={0},h2[200]={0};
for(int k=0;k<have1[i].size();k++) {
cnt1[have1[i][k]]++;
h1[have1[i][k]]=1;
}
for(int j=0;j<have2[i].size();j++) {
cnt2[have2[i][j]]++;
h2[have2[i][j]]=1;
}
for(int k=1;k<=m;k++) {
if(h1[k]==1) continue;
for(int j=1;j<=idc;j++) {
if(h2[j]==0) continue;
same[k][j]=0;
}
}
}
for(int i=1;i<=idc;i++) {
for(int k=1;k<=m;k++) {
if(cnt1[i]==cnt2[k]&&same[i][k]!=0) {
if(pp[k]==0) pp[k]=i,p[i]=k;
else pp[k]=-1,pp[p[i]]=-1;
}
}
}
for(int i=1;i<=m;i++) {
if(pp[i]==-1||pp[i]==0) cout<<"?"<<endl;
else cout<<name[pp[i]]<<endl;
}
return 0;
}
题外话:
我今年考研报的是广西某211,今年的专业课的算法压轴题,就是T2的简化版,在不改变数组的前提下,求最大子数组和,同时这也是leetcode上的原题,难度标为easy,分值20分;
结果我的专业课分数有些惨不忍睹,属于群里垫底了QAQ,不会正是因为我的代码比较丑陋所以老师没看明白吧QAQ
码风很好,我很喜欢