猫史档案馆

很抱歉，markdown编辑器坏掉了，观感可能会有点差

一，选择题

第一题：不多说，基本题目

第二题：不多说，进制转换基本题目

第三题：不多说，新增的union考点，蒙都能蒙出来

第四题：自己还没搞懂qwq（为啥网上答案那么多A而不是C）

第五题：树很重要的东西

我们如果画一颗三叉树，如下图所示。 center_image

可以看到每层的节点数分别为1,3,9，依次是上一层的三倍。

这很好理解。高度要最少，那肯定得尽量多的塞满每一层，构成一个完全树。

由此我们可以得到一个公式，这里设F(n)表示高度为n的节点个数

F(n) = 3^(n-1)

从而根据等比数列公式，得出下面的式子：

center_image

则n<=7

那剩余的节点肯定得新开一层，故答案为7+1=8

第六题：直接喵枚举，18

第七题：学过高精度的应该知道，或者说，列个乘法竖式就知道。他是和两个数字都有关系的。

第八题：转换成表达式树求后缀，基础知识不多说

第九题：进制转换和基础加减法，都换成10进制就好了

第十题：

这里讲解一下哈夫曼树怎么画。

先把他们写出来，每次取最小的两个相加，成为他们俩的父亲节点，然后以此类推每次去选最小的两个，会得到下面的树： center_image

整理后如下： center_image

往左走是1，往右走是0，且每个编码不能是任意一个编码的前缀（比如01和0101）

按照树来走就行了，选A

第十一题：基础知识，不多说

第十二题：

拓扑排序是什么？我的理解大概就是如果A->B是有路径的，那拓扑排序A一定得在B前面。

那看图，确定1肯定在最前面，4肯定在最后面

B就出来了，1234和1324其实都是可行的拓扑排序（因为2和3只要在1后面，4前面就行了，他们俩没有路径连接）

第十三题：

网上有争bit不是存储单位的，但我选的bit

第十四题：

经典排列组合题目。

这个你别想着枚举了。

最简单的方法就是先算出所有选出3个人的情况，再扣去男生中选出3个人的情况就是答案了。

也就是 center_image

第十五题：送分题，是个人都知道HT////ML是超文本标记语言。

二、程序阅读题

第一大题

#include<iostream>
#include<cmath>
using namespace std;
 
double f(double a,double b,double c){
    double s=(a+b+c)/2;
    return sqrt(s*(s-a)*(s-b)*(s-c));
}
 
int main(){
    cout.flags(ios::fixed);
    cout.precision(4);
    
    int a,b,c;
    cin>>a>>b>>c;
    cout<<f(a,b,c)<<endl;
    return 0;
}

考试的时候我不知怎么想到标准差去了，没想到是海喵式。

知道三边长度求面积，海喵式如下：（粘贴自百度百科）

center_image

判断题

第一题：对，根号3大约为1.73205，四舍五入得1.7321

第二题：乘法分配律啊，小学生都知道的事情

第三题：错。万一他给的三个数据组成不了三角形呢？万一sqrt的参数减成负数去了呢？

选择题：

第一题：3 4 5

一组勾股数，可以组成三角形

直角边3，4，答案就是3*4/2=6

选A

第二题：5 12 13

这个也很巧，又给了个勾股数，5*12/2选B

第二大题：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int f(string x,string y){
    int m=x.size();
    int n=y.size();
    vector<vector<int>>v(m+1,vector<int>(n+1,0));
   for(int i=1;i<=m;i++){
       for(int j=1;j<=n;j++){
            if(x[i-1]==y[j-1]){
                v[i][j]=v[i-1][j-1]+1;
            }else{
                v[i][j]=max(v[i-1][j],v[i][j-1]);
            }
        }
    }
    return v[m][n];
}
 
bool g(string x,string y){
    if(x.size() != y.size()){
        return false;
    }
    return f(x+x,y)==y.size();
}
 
int main(){
    string x,y;
    cin>>x>>y;
    cout<<g(x,y)<<endl;
    return 0;
}

这个看起来很难，但这种dp只要你肯列表，就能发现规律了。

考场上我列的这样一个表： center_image

列的过程中恍然大悟：这不就是最长公共子序列吗？

然后之后又列了一个acdd和asdf的，可能更清楚一点 center_image

然后g函数判断的就是y是否是2个x的子序列（注意子串和子序列的差别）

那这题就很好做了。

判断题：

第一题：对，子序列你总不可能大于较短的那个字符串长度吧

第二题：错。是2倍的第一个字符串，很坑

第三题：对。很好理解。你两个都相等了那第二个肯定是2倍x的子序列啊

选择题

第一题：我选的是D。长度不相等直接退出了，v[n][m]不会影响，但如果长度相等就会发生越界，大概3221225477吧

第二题：B。首先排除cd，选cd的人建议仔细读读代码，如果还不知道，那或许你把python记得太深刻了。

csp-j写两遍是csp-jcsp-j，很容易找到p-jcs

第三题：D。按上面看，csppsc重复两遍为csppsccsppsc，看加粗的部分，是可以找到第二个字符串的。

第三大题

#include <iostream>
#include <cmath>
using namespace std;
 
int solve1(int n){
    return n*n;
}
 
int solve2(int n){
   int sum=0;
   for(int i=1;i<=sqrt(n);i++){
        if(n%i==0){
            if(n/i==i){
                sum+=i*i;
            }else{
                sum+=i*i+(n/i)*(n/i);
            }
        }
    }
    return sum;
}
 
int main(){
    int n;
    cin>>n;
    cout<<solve2(solve1(n))<<" "<<solve1((solve2(n)))<<endl;
    return 0;
}

题目意思很简单，solve1就是平方，solve2就是求出n的所有因子并进行平方求和。

判断题

第一题：对

第二题：对。如果这个数是平方数，那算到√n的时候如果不进行判断，就会求√n*√n+(n/√n)*(n/√n)，重复算了两次。

第三题：对。输入为质数，只有两个因子：1和n本身，那平方和就是n^2+1

选择题

第一题：

n=p*p，那n一共有下面几个因数：

center_image