PAT甲级1042~1055

PAT甲级1042~1055

前言：距离四级考试剩23天，PAT甲级考试剩24天
对PAT甲级练习题做总结

1042 Shuffling Machine (20 分)

• 题目大意：
  重复给出排列方式，把放在下标 i i i的牌调换到下标 j j j
• 题目解析：
  模拟题

英语单词：

shuffle 洗牌，侧滑
machine 机器，机械
procedure 程序，手续，过程，步骤
deck 平台，甲板
be seen as 被认为是，被看作
gamblers 赌徒
collaborate 合作，协作
inadequate 不充分的，不适当的
casino 赌场
automatic 自动的
simulate 模拟，假装
initial 初始的，最初的
in the following 在下文中，在下面
spade 铁锹，铲子
heart 心
club 俱乐部
diamond 钻石，方块
joker 小丑，大小王
stand for 代表

代码如下：

#include

using namespace std;

const int N = 1e3+10;
const int inf = 0x3f3f3f3f;

#define x first
#define y second

typedef pair pii;
typedef double db;



int n,k;
int pos[N];
string alp = "SHCD";
vector t1,t2;

void init(){
    int cnt = 0;
    for(int j = 0; j < 4; j ++ ){
        for(int i = 1; i <= 13; i ++ ){
            string t = alp[j] + to_string(i);
            t1.push_back(t);
        }
    }
    for(int i = 1; i <= 2; i ++ ) t1.push_back("J" + to_string(i));
}

int main(){
    cin >> k;
    for(int i = 0; i < 54; i ++ ) cin >> pos[i];
    init();
    while(k --){
        t2 = t1;
        for(int i = 0; i < 54; i ++ ) t2[pos[i] - 1] = t1[i];
        t1 = t2;
    }
    for(int i = 0; i < 54; i ++ ){
        if(i) cout<<" ";
        cout< 
1043 Is It a Binary Search Tree (25 分) 
题目大意：
 给出前序，本身或者镜像是BST就OJK，并输出后序
题目解析：
 二叉树问题
 
英语单词： 
Binary Search Tree 二叉搜索树
 recursively 递归地
 mirror 镜子，镜面
 preorder 前序
 inorder 中序
 postorder 后序
 
代码如下： 
#include

using namespace std;

const int N = 1e3+10;
const int inf = 0x3f3f3f3f;

#define x first
#define y second

typedef pair pii;
typedef double db;



int n;
int a[N];
vector post;
bool isok;

void dfs(int l,int r){
    if(l > r) return ;
    int x = a[l];
    int i = l + 1,j = r;
    if(isok){
        while(i <= r && a[i] < x) i ++;
        while(j > l && a[j] >= x) j --;
    }else{
        while(i <= r && a[i] >= x) i ++;
        while(j > l && a[j] < x) j --;
    }
    if(i - j != 1) return ;
    dfs(l+1,j);
    dfs(i,r);
    post.push_back(x);
}

void print(){
    bool ok = false;
    for(auto x : post) {if(ok) cout<<" ";ok=true;cout<> n;
    for(int i = 0; i < n; i ++ ) cin >> a[i];
    isok = true;
    dfs(0,n - 1);
    if(post.size() != n){
        isok = false;
        post.clear();
        dfs(0,n - 1);
    }
    if(post.size() == n) isok = true;
    if(isok) {puts("YES");print();}
    else puts("NO");
    return 0;
}
 
1044 Shopping in Mars (25 分) 
题目大意：
 找到连续子数组之和>=给定值，取最小的值
题目解析：
 求前缀和，因为前缀和数组是非递减的。因此，可以用二分找到>=给定值的最小值。
 
英语单词： 
diamond 钻石
 take off 起飞，脱下，离开
 exact 精确的，准确的
 This is sufficient to 能够这样就足够了
 sufficient 足够的，充分的，充足的
 
代码如下： 
#include

using namespace std;

const int N = 1e5+10;
const int inf = 0x3f3f3f3f;

#define x first
#define y second

typedef pair pii;
typedef double db;



int n,m;
int a[N],s[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    for(int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];
    map> v;
    for(int l = 1; l <= n; l ++ ){
        int r = lower_bound(s+1,s+n+1,m+s[l-1]) - s;
        if(r > n) continue;
        int sum = s[r]-s[l-1];
        v[sum].push_back({l,r});
    }
    for(auto t : v){
         vector ans = t.y;
         for(auto [l,r] : ans) cout< 
1045 Favorite Color Stripe (30 分) 
题目大意：
 很有意思的一道题，普通人的眼睛可以辨别的颜色不超过200种，我只想挑选我喜欢的颜色，其他的不管。喜欢的颜色按照喜欢的顺序排放。找出满足这些条件的最长子序列。
题目解析：
 最长上升子序列问题。因为按照指定的顺序排列，因此，我们这里需要存储下标来计算。
 
英语单词： 
stripe 线条，条纹
 the remaining parts 剩余的部分
 
代码如下： 
#include

using namespace std;

const int N = 1e5+10;
const int inf = 0x3f3f3f3f;

#define x first
#define y second

typedef pair pii;
typedef double db;



int n,m;
int c[N],a[N],f[N];
int cnt;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> m>> n;
    for(int i = 1; i <= n; i ++ ){
        int x; cin >> x;
        c[x] = i;
    }
    cin >> m;
    for(int i = 1; i <= m; i ++ ){
        int x; cin >> x;
        if(c[x] >= 1) a[++cnt] = c[x];
    }
    int mx = -1;
    for(int i = 1; i <= cnt; i ++ ){
        f[i] = 1;
        for(int j = 1; j < i; j ++ ){
            if(a[i] >= a[j]) f[i] = max(f[i],f[j] + 1);
        }
        mx = max(mx,f[i]);
    }
    cout< 
1046 Shortest Distance (20 分) 
题目大意：
 找出两个点的最短距离
题目解析：
 可以把这些点看作一维平面上相邻的点，用2倍N来模拟循环。查询的是点，存的是边距离，找出相应的下标。
 
英语单词： 
the total round trip distance 全部往返总距离
 
代码如下： 
#include

using namespace std;

const int N = 2e5+10;
const int inf = 0x3f3f3f3f;

#define x first
#define y second

typedef pair pii;
typedef double db;



int n,m;
int a[N],s[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> a[i],a[i+n] = a[i];
    for(int i = 1; i <= 2*n; i ++ ) s[i] = s[i - 1] + a[i];
    cin >> m;
    while(m --){
        int a,b;cin>>a>>b;
        if(a > b) swap(a,b);
        cout< 
1047 Student List for Course (25 分) 
 
题目大意：
 话不多说看代码。
 
 
题目解析：
 模拟题。
 
 
英语单词： 
代码如下： 
#include

using namespace std;

const int N = 2e5+10;
const int inf = 0x3f3f3f3f;

#define x first
#define y second

typedef pair pii;
typedef double db;



int n,m;

int main(){
    cin >> n >> m;
    map> info;
    for(int i = 0; i < n; i ++ ){
        string s;int k;cin>>s>>k;
        for(int j = 0; j < k; j ++ ){
            int x; cin >> x;
            info[x].push_back(s);
        }
    }
    for(int i = 1; i <= m; i ++ ){
        int id = i;
        vector v = info[id];
        sort(v.begin(),v.end());
        cout< 
1048 Find Coins (25 分) 
 
题目大意：
 找出一对硬币满足给定值，如果找不到，输出No Solution.
 
 
题目解析：
 当前值是a，和是sum，得出另一个值是sum-a。判断是否存在并且下标不一样就可。
 
 
英语单词： 
definitely 当然地，肯定的，确实
 whether or not 无论，是否
 no solution 无解
 multiple solutions 多解
 
代码如下： 
#include

using namespace std;

const int N = 2e5+10;
const int inf = 0x3f3f3f3f;

#define x first
#define y second

typedef pair pii;
typedef double db;



int n,m;
int a[N];
map hs;

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i ++ ) cin >> a[i];
    sort(a,a+n);
    for(int i = 0; i < n; i ++ ) hs[a[i]] = i;
    bool ok = false;
    for(int i = 0; i < n; i ++ ){
        if(hs[m - a[i]] && i != hs[m-a[i]]) {ok=true;cout<
 
1049 Counting ones (30 分) 
题目大意：
 找出1到N中，所有数字位上的1
题目解析：
 先暴力混分吧，回头再看看
 
英语单词： 
代码如下： 
#include

using namespace std;

const int N = 2e5+10;
const int inf = 0x3f3f3f3f;

#define x first
#define y second

typedef pair pii;
typedef double db;


int n;

int cal(int n){
    int cnt = 0;
    while(n){
        if(n%10==1) cnt++;
        n/=10;
    }
    return cnt;
}

int main(){
    cin>>n;
    int cnt = 0;
    for(int i = 1; i <= n; i ++ ){
        cnt += cal(i);
    }
    cout< 
1050 String Subtraction (20 分) 
题目大意：
 在S1中，输出字符串S2没有出现过的字母
题目解析：
 标记辣
 
英语单词： 
代码如下： 
#include

using namespace std;

const int N = 2e5+10;
const int inf = 0x3f3f3f3f;

#define x first
#define y second

typedef pair pii;
typedef double db;



int main(){
    string a,b;
    getline(cin,a);
    getline(cin,b);
    map hs;
    for(auto c : b) hs[c] = true;
    for(auto c : a) if(!hs[c]) cout< 
1051 Pop Sequence (25 分) 
 
题目大意：
 
 
题目解析：
 合法输出出栈序列问题。
 栈 - 关于出栈序列，判断合法的出栈序列
 
 
 
英语单词： 
代码如下： 
#include

using namespace std;

const int N = 1e5+10;
const int inf = 0x3f3f3f3f;

#define x first
#define y second

typedef pair pii;
typedef double db;



int n,m,k;
int stk[N],a[N];
int tot;

int main(){
    cin >> n >> m >> k;
    while(k --){
        tot = 0;
        for(int i = 1; i <= m; i ++ ) cin >> a[i];
        bool ok = true;
        int cur = 1;
        for(int i = 1; i <= m; i ++ ){
            stk[++tot] = i;
            if(tot > n) ok = false;
            while(tot && stk[tot] == a[cur]) tot--,cur ++;
        }
        if(ok && !tot) puts("YES");
        else puts("NO");
    }
    return 0;
}
 
1052 linked List Sorting (25 分) 
题目大意：
 原链表结点的值按照递增排序调整。
题目解析：
 根据给出的头节点，找出这个链表，建立一个新链表输出。
注意：
 给出的结点，不一定在头节点的链表上。读题读不出来还有这样的输入，但是又合情合理，他又不说。如果不这样，我直接排个序输出不就OJK了？
 
英语单词： 
necessarily 必要的
 adjacent 相邻的
 
代码如下： 
#include

using namespace std;

const int N = 1e6+10;
const int inf = 0x3f3f3f3f;

#define x first
#define y second

typedef pair pii;
typedef double db;



int n,m;
int h1,ne[N];
map we,ew,hs;

int main(){
    cin >> n >> h1;
    for(int i = 1; i <= n; i ++ ){
        int a,c,b;cin>>a>>b>>c;
        ne[a] = c;
        we[b] = a;
        ew[a] = b;
    }
    if(h1 == -1) {puts("0 -1");return 0;}
    while(h1 != -1){
        hs[h1] = 1,h1 = ne[h1];
    }
    vector v;
    for(auto t : we){
        if(hs[t.y]) v.push_back(t.y);
    }
    int nn = v.size();
    printf("%d %05dn",nn,v[0]);
    for(int i = 0; i < nn; i ++ ){
        if(i != nn-1) printf("%05d %d %05dn",v[i],ew[v[i]],v[i+1]);
        else printf("%05d %d %dn",v[i],ew[v[i]],-1);
    }
    return 0;
}
 
1053 Path of Equal Weight (30 分) 
题目大意：
 找出从根节点到叶子结点权值和是给定值的所有路径
题目解析：
 dfs辣
注意：所有儿子结点按照非递减的顺序排放，这样能保证跟输出格式一致
 
英语单词： 
leaf node 叶子结点
 sake 利益，好处；目的；为了便于讨论
 For the sake of simplicity 为了简单起见
 extra 额外的
 
代码如下： 
#include

using namespace std;

const int N = 1e3+10;
const int inf = 0x3f3f3f3f;

#define x first
#define y second

typedef pair pii;
typedef double db;


int n,k,m;
int w[N];
vector v[N];
bool vis[N];
int mx;
vector tmp;
vector> ans;

void dfs(int u,int sum){
    if(v[u].size() == 0){
        if(sum == m) ans.push_back(tmp);
        return ;
    }
    for(int j : v[u]){
        if(vis[j]) continue;
        vis[j] = true;
        tmp.push_back(w[j]);
        dfs(j,sum + w[j]);
        vis[j] = false;
        tmp.pop_back();
    }
}

int main(){
    cin >> n >> k >> m;    
    for(int i = 0; i < n; i ++ ) cin >> w[i];
    while(k --){
        int id,kk; cin >> id >> kk;
        vector t;
        while(kk --){
            int x;cin>>x;
            t.push_back({w[x],x});
        }
        sort(t.begin(),t.end(),greater<>());
        for(auto &[k,x] : t) v[id].push_back(x);
    }
    tmp.push_back(w[0]);
    dfs(0,w[0]);
    for(auto t : ans){
        bool ok = false;
        for(auto x : t) {if(ok) cout<<" ";cout< 
1054 The Dominant Color (20 分) 
题目大意：
 严格主色：找出占超过一半区域的颜色
题目解析：
 找最大的那个就可，因为题目保证有，也不可以是俩辣
 
英语单词： 
dominant adj. 占支配地位的，占优势的；（基因）显性的
 scene 场景，场面
 a series 一系列
 pixel 像素
 be called 被称为
 proportional 成比例的
 strictly 严格的，完全的，确实的
 an image of resolution 图片分辨率
 
代码如下： 
#include

using namespace std;

const int N = 1e3+10;
const int inf = 0x3f3f3f3f;

#define x first
#define y second

typedef pair pii;
typedef double db;



int n,m;
int main(){
    map cnts;
    cin >> n >> m;
    for(int i = 1; i <= n*m; i ++ ){
        int x; cin>>x;
        cnts[x] ++;
    }
    int mx = -1,mx_id = -1;
    for(auto &[k,v] : cnts){
        if(v > mx) mx = v,mx_id = k;
    }
    cout< 
1055 The World’s Richest (25 分) 
 
题目大意：
 
 
题目解析：
 
 
英语单词： 
代码如下： 
#include

using namespace std;

const int N = 1e3+10;
const int inf = 0x3f3f3f3f;

#define x first
#define y second

typedef pair pii;
typedef double db;


int n,k;
map> info;
struct Node{
    string name;
    int age,w;
};

bool cmp1(Node a,Node b){
    if(a.w!=b.w) return a.w>b.w;
    if(a.age!=b.age) return a.age> n >> k;
    vector v(n);
    for(int i = 0; i < n; i ++ ){
        string id;int a,b;cin>>id>>a>>b;
        v[i] = {id,a,b};
    }
    sort(v.begin(),v.end(),cmp2);
    vector val;
    for(auto t : v) val.push_back(t.age);
    sort(val.begin(),val.end());
    int c = 1;
    while(k --){
        int m,l,r;cin>>m>>l>>r;
        int L = lower_bound(val.begin(),val.end(),l)-val.begin();
        int R = upper_bound(val.begin(),val.end(),r)-val.begin();
        R--;
        vector ans;
        for(int i = L; i <= min(L+m,R); i ++ ) ans.push_back(v[i]);
        printf("Case #%d:n",c++);
        // cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5611547.html