冬季乙级考试总结
前言
这次考试难度其实并不大，第三题又考了字符串的输出，题库有类似的，只不过换成了String，还有第五题的链表，秋季考了链表，以为不会考了，姥姥真是不按套路出牌，还好对链表还算熟悉。让人糟心的是第四题。考了HELLO WORLD，没错真的是HELLO WORLD，但又不是一般的helloworld，这题光是输入的数据就一百八十多行，用7*5的矩阵表示二十六个字母。只能说会HELLO WORLD就离满分不远了。
姥姥在知乎对本次考试的评价是：简单？
是简单，只是再也不敢说自己是HELLO WORLD水平了。。
7-1 2019数列 (15分)
把 2019 各个数位上的数字 2、0、1、9 作为一个数列的前 4 项，用它们去构造一个无穷数列，其中第 n（>4）项是它前 4 项之和的个位数字。例如第 5 项为 2， 因为 2+0+1+9=12，个位数是 2。
本题就请你编写程序，列出这个序列的前 n 项。
输入格式：
输入给出正整数 n（≤1000）。
输出格式：
在一行中输出数列的前 n 项，数字间不要有空格。
输入样例：
10
输出样例：
2019224758
题外话：这个数列中永远不会出现 2018，你能证明吗？
这题比较容易，值得注意的是，初始项并非2019，而是从2开始，开始我以2019为初始项没AC，然后以2为初始项才AC，花了13分钟。。
#include<iostream>
#include<string>
#include<cmath>
#include<vector>
using namespace std;
int main(){
int N;
int i,j,x;
string str="";
cin>>N;
for(j=0,i=0;str.size()<N;i++,j++){
if(j<4){
if(j==0)str.push_back('2');
else if(j==1)str.push_back('0');
else if(j==2)str.push_back('1');
else if(j==3)str.push_back('9');
continue;
}
x=((str[j-1]-'0')+(str[j-2]-'0')+(str[j-3]-'0')+(str[j-4]-'0'))%10;
str.push_back(x+'0');
}
cout<<str;
return 0;
}
7-2 老鼠爱大米 (20分)
翁恺老师曾经设计过一款 Java 挑战游戏，叫“老鼠爱大米”（或许因为他的外号叫“胖胖鼠”）。每个玩家用 Java 代码控制一只鼠，目标是抢吃尽可能多的大米让自己变成胖胖鼠，最胖的那只就是冠军。
因为游戏时间不能太长，我们把玩家分成 N 组，每组 M 只老鼠同场竞技，然后从 N 个分组冠军中直接选出最胖的冠军胖胖鼠。现在就请你写个程序来得到冠军的体重。
输入格式：
输入在第一行中给出 2 个正整数：N（≤100）为组数，M（≤10）为每组玩家个数。随后 N 行，每行给出一组玩家控制的 M 只老鼠最后的体重，均为不超过 10^4的非负整数。数字间以空格分隔。
输出格式：
首先在第一行顺次输出各组冠军的体重，数字间以 1 个空格分隔，行首尾不得有多余空格。随后在第二行输出冠军胖胖鼠的体重。
输入样例：
3 5
62 53 88 72 81
12 31 9 0 2
91 42 39 6 48
输出样例：
88 31 91
91
这题没啥好说的，sort用的快乐哈，懒得再找最值。
#include<iostream>
#include<string>
#include<cmath>
include<vector>
#include<algorithm>
using namespace std;
int main(){
int N,M,max[104],l=0;
cin>>N>>M;
for(int i=0;i<N;i++){
int a[15];
for(int j=0;j<M;j++){
cin>>a[j];
}
sort(a,a+M);
max[l]=a[M-1];
l++;
}
for(int i=0;i<l;i++){
if(i)cout<<' ';
cout<<max[i];
}
sort(max,max+l);
cout<<endl<<max[l-1];
return 0;
}
7-3 String复读机 (20分)
给定一个长度不超过 10^4的、仅由英文字母构成的字符串。请将字符重新调整顺序，按 StringString…. （注意区分大小写）这样的顺序输出，并忽略其它字符。当然，六种字符的个数不一定是一样多的，若某种字符已经输出完，则余下的字符仍按 String 的顺序打印，直到所有字符都被输出。例如 gnirtSSs 要调整成 StringS 输出，其中 s 是多余字符被忽略。
输入格式：
输入在一行中给出一个长度不超过 10^4的、仅由英文字母构成的非空字符串。
输出格式：
在一行中按题目要求输出排序后的字符串。题目保证输出非空。
输入样例：
sTRidlinSayBingStrropriiSHSiRiagIgtSSr
输出样例：
StringStringSrigSriSiSii
这题跟题库里的那道做法一样，统计数量按顺序输出就好了
#include<iostream>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
string str;
int s,t,r,i,n,g;
int j,k;
s=t=r=i=n=g=0;
getline(cin,str);
for(j=0;j<str.size();j++){
if(str[j]=='S')s++;
else if(str[j]=='t')t++;
else if(str[j]=='r')r++;
else if(str[j]=='i')i++;
else if(str[j]=='n')n++;
else if(str[j]=='g')g++;
}
while(s||t||r||i||n||g){
if(s){
cout<<'S';
s--;
}
if(t){
cout<<'t';
t--;
}
if(r){
cout<<'r';
r--;
}
if(i){
cout<<'i';
i--;
}
if(n){
cout<<'n';
n--;
}
if(g){
cout<<'g';
g--;
}
}
return 0;
}
7-4 擅长C (20分)
输入格式：
输入首先给出 26 个英文大写字母 A-Z，每个字母用一个 7×5 的、由 C 和 . 组成的矩阵构成。最后在一行中给出一个句子，以回车结束。句子是由若干个单词（每个包含不超过 10 个连续的大写英文字母）组成的，单词间以任何非大写英文字母分隔。
题目保证至少给出一个单词。
输出格式：
对每个单词，将其每个字母用矩阵形式在一行中输出，字母间有一列空格分隔。单词的首尾不得有多余空格。
相邻的两个单词间必须有一空行分隔。输出的首尾不得有多余空行。
输入样例：
..C..
.C.C.
C…C
CCCCC
C…C
C…C
C…C
CCCC.
C…C
C…C
CCCC.
C…C
C…C
CCCC.
.CCC.
C…C
C….
C….
C….
C…C
.CCC.
CCCC.
C…C
C…C
C…C
C…C
C…C
CCCC.
CCCCC
C….
C….
CCCC.
C….
C….
CCCCC
CCCCC
C….
C….
CCCC.
C….
C….
C….
CCCC.
C…C
C….
C.CCC
C…C
C…C
CCCC.
C…C
C…C
C…C
CCCCC
C…C
C…C
C…C
CCCCC
..C..
..C..
..C..
..C..
..C..
CCCCC
CCCCC
….C
….C
….C
….C
C…C
.CCC.
C…C
C..C.
C.C..
CC…
C.C..
C..C.
C…C
C….
C….
C….
C….
C….
C….
CCCCC
C…C
C…C
CC.CC
C.C.C
C…C
C…C
C…C
C…C
C…C
CC..C
C.C.C
C..CC
C…C
C…C
.CCC.
C…C
C…C
C…C
C…C
C…C
.CCC.
CCCC.
C…C
C…C
CCCC.
C….
C….
C….
.CCC.
C…C
C…C
C…C
C.C.C
C..CC
.CCC.
CCCC.
C…C
CCCC.
CC…
C.C..
C..C.
C…C
.CCC.
C…C
C….
.CCC.
….C
C…C
.CCC.
CCCCC
..C..
..C..
..C..
..C..
..C..
..C..
C…C
C…C
C…C
C…C
C…C
C…C
.CCC.
C…C
C…C
C…C
C…C
C…C
.C.C.
..C..
C…C
C…C
C…C
C.C.C
CC.CC
C…C
C…C
C…C
C…C
.C.C.
..C..
.C.C.
C…C
C…C
C…C
C…C
.C.C.
..C..
..C..
..C..
..C..
CCCCC
….C
…C.
..C..
.C…
C….
CCCCC
HELLO~WORLD!
输出样例：
这题我只想说：我不擅长C（哭.png）
前面三道二十四分钟就做完了，当时看了一下排名还是算是第十几的并列第一，原本信心满满的我栽在了HELLO WORLD上。。这题先留个坑，等复习甲级或者有时间再重新写一遍。卡在79分。。于是就只为过个点至少上80，然后就不写通用的，最后过了题目的样例拿了12分，再处理一个点13分。。而且让人郁闷的是定义的三维数组w[26][7][5],当时用cout<< w[i][j],输出一行居然出来一堆东西，调试看数据是对的，调试半天，最后试了试%c 一个一个字符打印才正确输出。。
我回来了，经过半小时的挣扎，终于写出HELLO WORLD。
总的来说不算难（马后炮），程序经过以下几组的测试都能正常输出答案，应该能AC了
2020-4-4
果然不还是不会HELLO WORLD…今天做了去年的冬季甲级题，这道题还是不能AC。。新写的拿了17分，一个点段错误。拿了下面这个去提交，也是17分，但却没有段错误。。👏
测试数据：
. 12aHA,HA4
. 1234
. A1B1C1D1
. WE ARE FAMILY
. HELLO WORLD
. HELLO
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
int i,j,k,n,x=0;
char w[30][10][10];
string str;
vector<int>v,ch;
for(i=0;i<26;i++){
for(j=0;j<7;j++){
cin>>w[i][j]; //存字母
}
}
getchar();
getline(cin,str);
for(i=0,j=0;i<str.size();i++){
if(str[i]>='A'&&str[i]<='Z'){
ch.push_back(str[i]-'A');
j++;
}
if(i<str.size()-1&&i>0&&str[i-1]>='A'&&str[i-1]<='Z'&&str[i+1]>='A'&&str[i+1]<='Z'&&(str[i]<'A'||str[i]>'Z')){
v.push_back(j);//统计单词个数
}
}
if(v.size())
v.push_back(ch.size());
for(i=0;i<v.size();i++){
for(j=0;j<7;j++){
for(n=x;n<v[i];n++){
cout<<w[ch[n]][j];
if(n!=v[i]-1)cout<<' ';
}
cout<<endl;
}
x=v[i];
if(i!=v.size()-1)
cout<<endl;
}
return 0;
}
下面是2020-4-4做甲级卷写的
#include<bits/stdc++.h>
using namespace std;
int main(){
char word[30][10][10];
string str,ans[100],s;
for(int i=0;i<26;i++){
for(int j=0;j<7;j++){
cin>>word[i][j];
}
}
getchar();
getline(cin,str);
int L=0;
for(int i=0;i<str.size();i++){
if(str[i]>='A'&&str[i]<='Z')
s.push_back(str[i]);
else if(s!=""){
ans[L++]=s;
s.clear();
}
}
if(s!="")ans[L++]=s;
for(int i=0;i<L;i++){
if(ans[i]!=""){
for(int j=0;j<7;j++){
for(int k=0;k<ans[i].size();k++){
if(k)cout<<' ';
cout<<word[ans[i][k]-'A'][j];
}
printf("\n");
}
if(i!=L-1)cout<<endl;
}
}
return 0;
}
7-5 区块反转 (25分)
给定一个单链表 L，我们将每 K 个结点看成一个区块（链表最后若不足 K 个结点，也看成一个区块），请编写程序将 L 中所有区块的链接反转。例如：给定 L 为 1→2→3→4→5→6→7→8，K 为 3，则输出应该为 7→8→4→5→6→1→2→3。
输入格式：
每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N (≤10^5)、以及正整数 K (≤N)，即区块的大小。结点的地址是 5 位非负整数，NULL 地址用 −1 表示。
接下来有 N 行，每行格式为：
Address Data Next
其中 Address 是结点地址，Data 是该结点保存的整数数据，Next 是下一结点的地址。
输出格式：
对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。
输入样例：
00100 8 3
71120 7 88666
00000 4 99999
00100 1 12309
68237 6 71120
33218 3 00000
99999 5 68237
88666 8 -1
12309 2 33218
输出样例：
71120 7 88666
88666 8 00000
00000 4 99999
99999 5 68237
68237 6 00100
00100 1 12309
12309 2 33218
33218 3 -1
当时直接跳过HELLO WORLD了，看到链表终于找回一点信心。按套路来就行。不过这题有个坑点，好多人都卡在24分，我也是，当时考虑了会不会K=0，但考后看了题目K为正整数，怪不得当时加了K=0的判断还没AC，知乎有人说那一分可能是有个垃圾点不在链表上，这个我做了处理了，也没有AC，所以肯定不是这个的原因。不知道是不是K=1的情况，K=1的话，我的程序是逆序输出的，但K=1的话，反转自己，那岂不是没反转，所以是不是要正序输出
2020-4-4更新:
做甲级卷的时候，还是卡这个点，上面的推测全都不对。😒菜该如此。
#include<iostream>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
struct node{
int next;
int data;
}p[100005];
int main(){
int first,N,K,temp,i;
vector<int>ad;
cin>>first>>N>>K;
for(i=0;i<N;i++){
cin>>temp;
cin>>p[temp].data>>p[temp].next;
}
temp=first;
while(temp!=-1){
ad.push_back(temp);
temp=p[temp].next;
}
for(i=1;i<=ad.size()/K;i++){
reverse(ad.begin()+K*(i-1),ad.begin()+K*i);
}
if(ad.size()%K!=0){
reverse(ad.end()-(ad.size()%K),ad.end());
}
for(i=ad.size()-1;i>=0;i--){
if(i)printf("%05d %d %05d\n",ad[i],p[ad[i]].data,ad[i-1]);
else printf("%05d %d -1\n",ad[i],p[ad[i]].data);
}
return 0;
}
这是第一次参加，只拿了92分，没有满分还是有点遗憾的，下次的甲级加油吧！ 🤪
2020-4-4：
2019冬季甲级题有上面的HELLO WORLD跟链表区块反转的两题跟下面两道。
今天在教育超市买了冬季的甲级题来做了做，后面两道还算比较友好，前面两道。。该掉的坑，绝对躲不掉。。 😩
7-3 Summit (25分)
A summit (峰会) is a meeting of heads of state or government. Arranging the rest areas for the summit is not a simple job. The ideal arrangement of one area is to invite those heads so that everyone is a direct friend of everyone.
Now given a set of tentative arrangements, your job is to tell the organizers whether or not each area is all set.
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers N (≤ 200), the number of heads in the summit, and M, the number of friendship relations. Then M lines follow, each gives a pair of indices of the heads who are friends to each other. The heads are indexed from 1 to N.
Then there is another positive integer K (≤ 100), and K lines of tentative arrangement of rest areas follow, each first gives a positive number L (≤ N), then followed by a sequence of L distinct indices of the heads. All the numbers in a line are separated by a space.
Output Specification:
For each of the K areas, print in a line your advice in the following format:
if in this area everyone is a direct friend of everyone, and no friend is missing (that is, no one else is a direct friend of everyone in this area), print Area X is OK..
if in this area everyone is a direct friend of everyone, yet there are some other heads who may also be invited without breaking the ideal arrangement, print Area X may invite more people, such as H. where H is the smallest index of the head who may be invited.
if in this area the arrangement is not an ideal one, then print Area X needs help. so the host can provide some special service to help the heads get to know each other.
Here X is the index of an area, starting from 1 to K.
Sample Input:
8 10
5 6
7 8
6 4
3 6
4 5
2 3
8 2
2 7
5 3
3 4
6
4 5 4 3 6
3 2 8 7
2 2 3
1 1
2 4 6
3 3 2 1
Sample Output:
Area 1 is OK.
Area 2 is OK.
Area 3 is OK.
Area 4 is OK.
Area 5 may invite more people, such as 3.
Area 6 needs help.
手残把赋值语句写成了“==”，调试半天🙂。
这道考察并查集，但我没有用并查集的写法来做，
#include<bits/stdc++.h>
using namespace std;
int G[205][205];
int main(){
int N,K,M,x,y;
cin>>N>>K;
for(int i=0;i<K;i++){
scanf("%d %d",&x,&y);
G[x][y]=1;
G[y][x]=1;
}
for(int i=1;i<=N;i++)
G[i][i]=1;
cin>>M;
for(int i=0;i<M;i++){
int n,is=1;
unordered_map<int,int>mp;
scanf("%d",&n);
vector<int>v(n);
for(int j=0;j<n;j++){
scanf("%d",&v[j]);
mp[v[j]]=1; //在这里写了==，一度以为编译器抽风
}
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
if(G[v[j]][v[k]]==0){
is=0;
break;
}
}
if(is==0)break;
}
if(is==0)printf("Area %d needs help.\n",i+1);
else {
int is1=1;
for(int j=1;j<=N;j++){
int is2=1;
for(int k=0;k<v.size();k++){
if(G[j][v[k]]!=1){
is2=0;
break;
}
}
if(is2==1&&mp[j]==0){
is1=0;
printf("Area %d may invite more people, such as %d.\n",i+1,j);
break;
}
}
if(is1==1)printf("Area %d is OK.\n",i+1);
}
}
return 0;
}
7-4 Cartesian Tree (30分)
A Cartesian tree is a binary tree constructed from a sequence of distinct numbers. The tree is heap-ordered, and an inorder traversal returns the original sequence. For example, given the sequence { 8, 15, 3, 4, 1, 5, 12, 10, 18, 6 }, the min-heap Cartesian tree is shown by the figure.
图略
Your job is to output the level-order traversal sequence of the min-heap Cartesian tree.
Input Specification:
Each input file contains one test case. Each case starts from giving a positive integer N (≤30), and then N distinct numbers in the next line, separated by a space. All the numbers are in the range of int.
Output Specification:
For each test case, print in a line the level-order traversal sequence of the min-heap Cartesian tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the beginning or the end of the line.
Sample Input:
10
8 15 3 4 1 5 12 10 18 6
Sample Output:
1 3 5 8 4 6 15 10 12 18
建树类型题。一开始没看出来怎么建树，给出了中序，并建成小顶堆（非完全二叉树）。观察了下发现找到序列中最小的元素，即可确定为根节点，然后递归建树。
果然建树经常离不开中序，不知道下次会不会考察中序+层序建树，有备无患吧。
#include<bits/stdc++.h>
using namespace std;
struct node{
int val;
node *lchild,*rchild;
};
vector<int>In;
int N,val,k=0;
node *Inorder(int InL,int InR){
if(InR<InL)return NULL;
int min=InL;
for(int i=InL+1;i<=InR;i++)
if(In[min]>In[i])min=i;
node *root=new node;
root->val=In[min];
root->lchild=Inorder(InL,min-1);
root->rchild=Inorder(min+1,InR);
return root;
}
void levelorder(node *root){
queue<node* >q;
q.push(root);
while(!q.empty()){
root=q.front();
q.pop();
if(k++)cout<<' ';
cout<<root->val;
if(root->lchild!=NULL)q.push(root->lchild);
if(root->rchild!=NULL)q.push(root->rchild);
}
}
int main(){
cin>>N;
for(int i=0;i<N;i++){
cin>>val;
In.push_back(val);
}
node *root=Inorder(0,In.size()-1);
levelorder(root);
return 0;
}
晚安🌙