PAT(Advanced)模拟篇
A1042 Shuffling Machine (20分)
Question
Shuffling is a procedure used to randomize a deck of playing cards. Because standard shuffling techniques are seen as weak, and in order to avoid "inside jobs" where employees collaborate with gamblers by performing inadequate shuffles, many casinos employ automatic shuffling machines. Your task is to simulate a shuffling machine.
The machine shuffles a deck of 54 cards according to a given random order and repeats for a given number of times. It is assumed that the initial status of a card deck is in the following order:
S1, S2, ..., S13, H1, H2, ..., H13, C1, C2, ..., C13, D1, D2, ..., D13, J1, J2
where "S" stands for "Spade", "H" for "Heart", "C" for "Club", "D" for "Diamond", and "J" for "Joker". A given order is a permutation of distinct integers in [1, 54]. If the number at the i-th position is j, it means to move the card from position i to position j. For example, suppose we only have 5 cards: S3, H5, C1, D13 and J2. Given a shuffling order {4, 2, 5, 3, 1}, the result will be: J2, H5, D13, S3, C1. If we are to repeat the shuffling again, the result will be: C1, H5, S3, J2, D13.
Input Specification
Each input file contains one test case. For each case, the first line contains a positive integer K (≤20) which is the number of repeat times. Then the next line contains the given order. All the numbers in a line are separated by a space.
Output Specification
For each test case, print the shuffling results in one line. All the cards are separated by a space, and there must be no extra space at the end of the line.
Sample Input
2
36 52 37 38 3 39 40 53 54 41 11 12 13 42 43 44 2 4 23 24 25 26 27 6 7 8 48 49 50 51 9 10 14 15 16 5 17 18 19 1 20 21 22 28 29 30 31 32 33 34 35 45 46 47
Sample Output
S7 C11 C10 C12 S1 H7 H8 H9 D8 D9 S11 S12 S13 D10 D11 D12 S3 S4 S6 S10 H1 H2 C13 D2 D3 D4 H6 H3 D13 J1 J2 C1 C2 C3 C4 D1 S5 H5 H11 H12 C6 C7 C8 C9 S2 S8 S9 H10 D5 D6 D7 H4 H13 C5
Analysis
这题题意是将按序排好的54张扑克牌按照新给出的顺序重新排列一定次数。我们可以借助两个数组start[]和end[]来存放操作前和操作后的顺序，再将一次操作后的end[]数组重新赋值给start[]数组，进行下一次操作。执行规定次数操作后，start[]就是最终的结果。
Code
#include<iostream>
#include<cstdio>
using namespace std;
const int N=54;
char shcdj[5]={'S','H','C','D','J'};
int main(){
int start[N+1],end[N+1],next[N+1];
int k;//repeat times
scanf("%d",&k);
for(int i=1;i<=N;i++){
start[i]=i;
scanf("%d", &next[i]);
}
for(int i=0;i<k;i++){
for(int j=1;j<=N;j++){
end[next[j]]=start[j];
}
for(int j=1;j<=N;j++){
start[j]=end[j];
}
}
for(int i=1;i<=N;i++){
if(i!=1)printf(" ");
start[i]--;
printf("%c%d",shcdj[start[i] / 13],start[i]%13+1);
}
return 0;
}
A1046 Shortest Distance (20分)
Question
The task is really simple: given N exits on a highway which forms a simple cycle, you are supposed to tell the shortest distance between any pair of exits.
Input Specification
Each input file contains one test case. For each case, the first line contains an integer N (in [3,10^5]), followed by N integer distances D1 D2 ⋯ DN, where Di is the distance between the i-th and the (i+1)-st exits, and DN is between the N-th and the 1st exits. All the numbers in a line are separated by a space. The second line gives a positive integer M (≤10^4 ), with M lines follow, each contains a pair of exit numbers, provided that the exits are numbered from 1 to N. It is guaranteed that the total round trip distance is no more than 10^7.
Output Specification
For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.
Sample Input
5 1 2 4 14 9
3
1 3
2 5
4 1
Sample Output
3
10
7
Analysis
这题题意是给出一个由N个结点组成的闭环，并已知相邻两点的距离，求给出两点之间的最短距离。给出的两点编号存在第一个点编号大于第二个点编号的可能性，加一个判断交换即可。
原本是想用dis[]数组来保存第i个点到第i+1个点的距离，但是后面计算时需要大量循环，因此这里借鉴柳神的思路，用dis[]数组来保存第一个点到第n个点的距离，比较方便，就不用再循环计算！
Code
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n,m,sum=0,left,right;
scanf("%d",&n);
vector<int>dis(n+1);
for(int i=1;i<=n;i++){
int tmp;
scanf("%d",&tmp);
sum+=tmp;
dis[i]=sum;
}
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d %d",&left,&right);
if(left>right)swap(left,right);
int tmp=dis[right-1]-dis[left-1];
printf("%d\n",min(tmp,sum-tmp));
}
return 0;
}
A1065 A+B and C (64bit) (20分)
Question
Given three integers A, B and C in [−2^63, 2^63], you are supposed to tell whether A+B>C.
Input Specification
The first line of the input gives the positive number of test cases, T (≤10). Then T test cases follow, each consists of a single line containing three integers A, B and C, separated by single spaces.
Output Specification
For each test case, output in one line Case #X: true if A+B>C, or Case #X: false otherwise, where X is the case number (starting from 1).
Sample Input
3
1 2 3
2 3 4
9223372036854775807 -9223372036854775808 0
Sample Output
Case #1: false
Case #2: true
Case #3: false
Analysis
这题题意是给出三个整数并且范围在 [−2^63, 2^63]，对于普通int整型来说，一个整数占4Byte=32bit，取值范围远远小于题目要求，因此这里采用长整型，一个长整型整数占8Byte=64bit。
一开始写的时候没有考虑A+B的范围会溢出，因此只过了一个点的测试。
溢出的情况有两种：
- A>0,B>0,A+B<0
- A<0,B<0,A+B>=0
Code
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long int ll;
int main() {
ll a,b,c;
int t;
scanf("%d",&t);
for(int i=0;i<t;i++){
scanf("%lld %lld %lld",&a,&b,&c);
ll sum=a+b;
if(a>0&&b>0&&sum<0)printf("Case #%d: true\n",i+1);
else if(a<0&&b<0&&sum>=0)printf("Case #%d: false\n",i+1);
else if(sum>c)printf("Case #%d: true\n",i+1);
else printf("Case #%d: false\n",i+1);
}
return 0;
}
A1002 A+B for Polynomials (25分)
Question
This time, you are supposed to find A+B where A and B are two polynomials.
Input Specification
Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial:
K N1 aN1 N2 aN2 ... NK aNK
where K is the number of nonzero terms in the polynomial, Ni and aNi (i=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that 1≤K≤10，0≤NK<⋯<N2<N1≤1000.
Output Specification
For each test case you should output the sum of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate to 1 decimal place.
Sample Input
2 1 2.4 0 3.2
2 2 1.5 1 0.5
Sample Output
3 2 1.5 1 2.9 0 3.2
Analysis
这题题意是做多项式的加法运算，比较简单，用数组即可搞定，数组下标对应指数，存的数为底数。
Code
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
int k,cnt=0;double Num[1001]={0};
for(int i=0;i<2;i++){
scanf("%d",&k);
for(int j=0;j<k;j++){
int exp;double coe;
scanf("%d %lf",&exp,&coe);
Num[exp]+=coe;
}
}
for(int i=0;i<1001;i++){
if(Num[i]!=0)cnt++;
}
printf("%d",cnt);
for(int i=1000;i>=0;i--){
if(Num[i]!=0.0)printf(" %d %.1lf",i,Num[i]);
}
return 0;
}
A1009 Product of Polynomials (25分)
Question
This time, you are supposed to find A×B where A and B are two polynomials.
Input Specification
Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial:
K N1 aN1 N2 aN2 ... NK aNK
where K is the number of nonzero terms in the polynomial, Ni and aNi (i=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that 1≤K≤10，0≤NK<⋯<N2<N1≤1000.
Output Specification
For each test case you should output the product of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate up to 1 decimal place.
Sample Input
2 1 2.4 0 3.2
2 2 1.5 1 0.5
Sample Output
3 3 3.6 2 6.0 1 1.6
Analysis
这题和上题差不多，稍微有些不一样，是做多项式的乘法运算。
这里借用两个数组arr[]和ans[]，前者存第一行数据，后者边计算边存；同样数组下标对应指数，存的数为底数。注意相乘之后的指数范围高达2000！
Code
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
int k1,k2,cnt=0,exp;
double coe,arr[1001]={0.0},ans[2001]={0.0};
scanf("%d",&k1);
for(int i=0;i<k1;i++){
scanf("%d %lf",&exp,&coe);
arr[exp]=coe;
}
scanf("%d",&k2);
for(int i=0;i<k2;i++){
scanf("%d %lf",&exp,&coe);
for(int j=0;j<1001;j++){
ans[j+exp]+=coe*arr[j];
}
}
for(int i=0;i<2001;i++){
if(ans[i]!=0.0)cnt++;
}
printf("%d",cnt);
for(int i=2000;i>=0;i--){
if(ans[i]!=0.0)printf(" %d %.1lf",i,ans[i]);
}
return 0;
}