【PAT】2021年冬季考试甲级,摸鱼游记、92分
【摘要】
T1,简单模拟,20/20分
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int a[maxn...
T1,简单模拟,20/20分
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int a[maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n, m; cin>>n>>m;
for(int i = 1; i <= m; i++){
vector<int>vc;
map<int,int>ma;
for(int j = 1; j <= n; j++){
int x; cin>>x;
vc.push_back(x);
ma[x]++;
}
int mx = 0;
for(int j = 0; j < n; j++){
vc[j] = n-ma[vc[j]];
mx = max(mx, vc[j]);
}
for(int j = 0; j < n; j++){
if(vc[j]==mx){
a[j+1]++;
}
}
}
int mx = 0; vector<int>res;
for(int i = 1; i <= n; i++){
if(a[i]>mx){
mx = a[i];
res.clear();
res.push_back(i);
}else if(a[i]==mx){
res.push_back(i);
}
}
cout<<res[0];
// for(int i = 0; i < res.size(); i++){
// cout<<res[i]<<" ";
// }
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
T2,模拟链表,25/25分
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int a[maxn], ans[maxn];
int nxt[maxn], in[maxn], pre[maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
memset(pre,-1,sizeof(pre));
int n; cin>>n;
int ed;
for(int i = 0; i < n; i++){
int x; cin>>x;
a[i]= x;
nxt[i] = x;
if(x!=-1)pre[x] = i;
else{
ed = i;
}
}
vector<int>vc;
for(int x = ed; x!=-1; x = pre[x]){
vc.push_back(x);
}
reverse(vc.begin(),vc.end());
for(int i = 0; i < n; i++){
ans[vc[i]] = i;
}
for(int i = 0; i < n ; i++){
if(i!=0)cout<<" ";
cout<<ans[i]+1;
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
T3,简单树遍历,25/25分
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
vector<int>G[maxn];
int in[maxn], ans[maxn];
int dfs(int x){
int res = 0;
for(int to : G[x]){
res += dfs(to);
}
return ans[x] = res+G[x].size();
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n; cin>>n;
for(int i = 2; i <= n; i++){
int x; cin>>x;
G[x].push_back(i);
in[i]++;
}
int rt;
for(int i = 1; i <= n; i++){
if(in[i]==0){
rt = i; break;
}
}
dfs(rt);
int m; cin>>m;
for(int i = 0; i< m; i++){
int x; cin>>x;
cout<<ans[x]+1<<"\n";
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
T4,稍复杂模拟,22/30分
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
const int inf = 1e9+10;
struct tim{ int hh, mm; };
void add(tim &t, int min){
t.mm += min;
while(t.mm>=60){
t.mm -= 60;
t.hh++;
}
}
int smal(tim x, tim y){
if(x.hh!=y.hh)return x.hh<y.hh;
return x.mm<y.mm;
}
struct node{ tim t; int Y, P; }a[1010];
int e[2020][2020];
int main(){
//input
int n, m; scanf("%d%d", &n, &m);
tim st; scanf("%d:%d", &st.hh,&st.mm);
a[0].t = st;
a[0].P = a[0].Y = 0;
for(int i = 1; i <= n; i++){
scanf("%d:%d %d %d",&a[i].t.hh,&a[i].t.mm, &a[i].Y, &a[i].P);
}
//memset(e,0x3f,sizeof(e));
for(int i = 0; i <= n; i++){
for(int j= 0; j <= n; j++){
if(i!=j)e[i][j] = inf;
else e[i][j] = 0;
}
}
for(int i = 1; i <= m; i++){
int u, v, w; scanf("%d%d%d",&u, &v, &w);
e[u][v] = min(e[u][v], w);
e[v][u] = min(e[v][u], w);
if(w>120){ while(1);}
}
//min_dis,floyd
for(int k = 0; k <= n; k++){
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
if(i!=j)e[i][j] = min(e[i][j], e[i][k]+e[k][j]);
}
}
}
// for(int i = 0; i <= n; i++){
// for(int j = 0; j <= n; j++){
// cout<<e[i][j]<<" ";
// }
// cout<<"\n";
// }
//跑K次
int K; cin>>K;
tim at= tim{23,59}; int ap = -1e9+10;//肯定比23:59早,亏钱亏钱
while(K--){
tim tt = st; int tp=0; int now = 0;//0元钱,在起点,时间st
int ok = 1; set<int>se;
//printf("%d: %d %02d:%02d\n", K+1, tp, tt.hh,tt.mm);
for(int i = 1; i <= n+1; i++){
se.insert(now);
int x;
if(i!=n+1)cin>>x; else x = 0;//下一个要去的点
if(e[now][x]==inf){ok = 0;}//无法到达就再见
if(x>n||x<0)ok = 0;
//if(a[x].bad==1){ok = 0;}//垃圾点再见
if(ok==0)continue;
add(tt, e[now][x]);//用时间到达
tp += a[x].Y;//获得那么多钱
//小于等于deadline
if(smal(tt,(a[x].t))==1 ){// || (tt.hh==a[x].t.hh&&tt.mm==a[x].t.mm
now = x; continue;
}else{
//大于deadline,扣钱
tp -= a[x].P;
}
now = x;
//printf("%d: %d %02d:%02d\n", K+1, tp, tt.hh,tt.mm);
}
if(se.size()!=n+1)continue;//如果有点没有到达,那么不算!
//if(ok==0)continue;//如果无法到达点,那么慢不算
//printf("%d: %d %02d:%02d\n", K+1, tp, tt.hh,tt.mm);
if(tp>ap){//赚的钱更多优先
ap = tp; at = tt;
}else if(tp==ap){// 钱一样,时间短优先
if(smal(tt,at)==1){
at = tt;
}
}
}
printf("%d %02d:%02d\n", ap, at.hh,at.mm);
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
文章来源: gwj1314.blog.csdn.net,作者:小哈里,版权归原作者所有,如需转载,请联系作者。
原文链接:gwj1314.blog.csdn.net/article/details/122027887
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)