NOIP2010提高组复盘

整套卷子讲解：

noip2010初赛提高组试题详解 - Dijkstra·Liu - 博客园

_noip2010提高组初赛试题解析 - 豆丁网Docin

原题：

luogu

本文部分内容参考来自以上链接。

总结：这次的卷子比较难，考了67.5，全机房第2，cwz dalao拿到了68分 %%%，他的运气逆天，蒙对了程序输出题。

单选题

第五题：错了两题，如果在某个进制下等式 $7*7=41$ 成立，那么在该进制下等式 $12*12 = $我无脑选了 $100$，其实是$144$，模拟一下发现是十二进制，直接算就好了
第十题：全国青少年信息学奥林匹克竞赛 $NOI$ 历史最悠久！！！我还以为是 $IOI$ 历史最悠久呢！！！！

不定项题

第四题：整数 $0$ 只有一个唯一的二进制编码编码！
第五题：一颗二叉树的前序遍历序列是 $ABCDEFG$，后序遍历序列是$CBFEGDA$，则根结点的左子树的结点个数可能是？很容易就得出A是根节点，那么通过前序遍历知道B肯定是A得直接左儿子。有根据后序遍历可知D是A的右儿子，所以只有C跟着B，所以答案只有2。
第六题：在下列 HTML 语句中，可以正确产生一个指向 NOI 官方网站的超链接的是：<a href="http://www.noi.cn">欢迎访问NOI网站</a> 记住就好。
第七题：正确答案：拓扑排序结果序列中的第一个结点一定是入度等于 0 的点。这这，纯属脑抽
第八题：一个平面的法线是指与该平面垂直的直线。过点(1,1,1)、（0,3,0）、(2,0,0)的平面的法线是（）。因为点$（1,1,1）$与点$（2,0,0）$的间的向量为$（1，-1，-1,）$ 因为法向量（法线方向的向量）与平面上的向量的乘积为0 所以D满足要求过点$（2，0，0）、（5，2，1）$得向量为$（-3，-2，-1）（1，-1，-1,）*（-3，-2，-1）=1*（-3）+（-1）*（-2）+（-1）*（-1）=0$然而我并不会做←_←转自[这里](noip2010初赛提高组试题详解 - Dijkstra·Liu - 博客园)。就连学到高一数学的fjz大佬都不会……~~一套卷子总有难题嘛，搞不懂也正常~~
第九题：这道题…………，怎么说，我原本选了正确答案，后来发现卷子里（是张老师给的）有一个字母漏打了，我以为这样就不对，所以我把BCD改成了BC，啊啊啊
第十题：科普一下吧：今年（2010 年）发生的事件有: A. 惠普实验室研究员 Vinay Deolalikar 自称证明了 P≠NP B. 英特尔公司收购计算机安全软件公司迈克菲（McAfee）C. 苹果公司发布 iPhone 4 手机。然后win7不是10年发布的。要是在10年做的题，那我就知道了…………………我就记得win7不是10年的，但是无脑选了ABCD。

问题求解

第二题：无向图 G 有 7 个顶点，若不存在由奇数条边构成的简单回路，则它至多有____条边。这其实想想就发现这是一个二分图，因为每一条回路都是偶数条边构成的，那么正好是二分图的一个性质，因此二分图左右两边共7个节点，为了使乘积最大，一边为$3$一边为$4$，因此答案使$12$。
第三题：网上好像都说是容斥原理，~~我咋不会呢，看也看不懂~~

阅读程序

第四题：因为时间不太够而且能力也不够所以这道题就空着了。这道题好像考的是哈密尔顿图，没学过，~~感觉很高级~~。程序的目的是从指定的起点到指定的终点，图中经过所有其他结点且只经过一次。~~等以后学了再来看吧~~

完善程序

这里第二个链接分析的比较到位比较详细！

第一大题： 就是第一个空错了，实际上第一个空的含义是当$num$（剩下没过河的人）<= 2只剩两个人，直接过河就可以了，所以直接return;
第二大题： 这一部分都是半蒙半猜，都是靠着规律做的。实际上它就是一个二叉堆，堆排序的代码我都填对了，但是这个是DP+小根堆，我没理解这道题的DP 转移方程，所以DP转移部分写错了。转移方程是：$dp_i = min(dp_k+velue_i)$ 其中 $k=[i-m+1,i-1]$。因此就把这道题做出来了！

总结

这一次的试卷其实不会的知识不是特别多，满打满算估计就20分，其实还有很多失分在于粗心，有的题没有怎么经过思考就觉得很难，跳过。其实主要的原因还是在于这次考试时间相对比较紧张，只有2小时的时间，所以下次做题一定要提高效率，先紧后松，把时间安排好，争取把每一道题都做出来。

洛谷SCP-S初赛复盘

先把蒟蒻的答案放上来……

单选题：
BBBCD DDDDD ABDAA
阅读程序：
FTTTDC
FTFBAC
TFTBBB
完善程序
BBDAA
BABCA

正确答案……

单选题
DABDB ADDDD DAAAA
阅读程序：
FTFFDC
FTFBAA
FTFDAA
完善程序
BBDAB
BACBC

总分57分，单选失分16，阅读失分15分，完善失分12分

重大失分区域在于程序阅读题第三题，哈哈哈，全错，我真有点水平

单选题：

第一题：这就搞不懂了，正确答案是D？？？，难道CSP可以带”一大份绿鸟牌烤鸡柳“进考场，我不信啊，~~我下次就试试~~
第二题：正确答案都是三年，原来考场上没有及时举报别人作弊，自己和别人都要禁赛三年
第四题：C++是弱类型语言，强类型语言指的是这个语言中数据结构除非强转，不会自动改变，而弱类型反之，例如string + int等
第五题：第一次接触这种类型的题目，是计算音频的大小，首先三分钟，180秒，每秒有双声道，每个声道16bit（2byte），再乘上赫兹（44100，这个要从千赫兹化成赫兹，指的是每秒的频率）。因此得到式子：$180 \times 2byte \times 2 \times 44100 = 31752000byte = 30.3MB$
第六题：在 vim 编辑器中，若当前位于 normal 模式，你需要将光标移动到这一行的末尾并进入 insert 模式．依次按下以下按键无法实现该目标的是: 这个东西我都没听过，反正答案是Esc、:、w、q、回车，记着就是了。
第十一题：蒟蒻暂且不会，后面补上
第十二题：张教练也不会，盲猜选A，好像比较正确的样子，可惜我没有蒙对。
第十三题：蒟蒻还是不会

程序阅读题：

第一题嘛，就是"超级快排"，跟快排没区别，为什么错的两题好像都是想对写错的？？
第二题，就是个dfs求个深度，关于树的信息，然后算啊算啊算，w2,w1,w0把我搞得很混乱，但是前面还基本做出来，输出题，不想算（ ~~其实是不会~~，就蒙了，俩对了一个。
第三题，我一看到题目，query,update,modify,tag,太酷啦，竟然考线段树模板，连代码也没仔细看，刷刷刷把几道题信心满满的做完了，心里想这次一定能拿高分！！赛后发现，太酷了，三道判断，三道选择，完美避开正确答案？什么鬼？结果网上一查…………CirnoTree叫做决策树，本蒟蒻都没听过，太菜了，我真是个大葱明。

完善程序：

第一题不是太难，最后一个空有点难，就直接蒙了，错了。这道题主要还是代码短，稍微要有些推理才填的出来，不然那是一篇大括号啊。
第二题主要还是不太知道这个算法的原理，我只填出了快速幂和一个初始化，其他的我想找规律填好像被出题人预判了，搞不到正确答案，说实话，这代码我完全看不懂，只是靠着规律推了一点出来而已。

总结：

这次考试的题目非常非常难，单选题还是考到了很多不会的知识，甚至张教练也不会的。程序阅读题，惨就惨在最后一题，我就是不认真读题，要是认真读题可能能够找点规律弄点分，估计出题人预料到有人以为是线段树，所以设置了陷阱，我就跳进去了………………下次还是要认真读题，不要一看到题目就自以为是以为很简单。完善程序整体算发挥的正常，毕竟最后一题还是有难度的！

最后：祝我：CSP-S RP ++

CSP 2022 提高级第一轮复盘

总结：64分，还可以，在去年能够领先分数线十分左右，希望今年也能这样

单选题错了三题，24分，程序阅读，19分，完善程序，21分（第二题比较水）

去年考场上都是全蒙的，所以现在才来做一下（当时是45.5）

单选题：

第一题：在 Linux 系统终端中，用于切换工作目录的命令为cd。ls是查看，cd改变目录，cp，是copy。
第二题：你同时用 time 命令和秒表为某个程序在单核 CPU 的运行计时。假如 time 命令的输出如下：答案按照”real“这一条来看就对了（毕竟写的是‘真’）。
第六题：虽然不懂，但蒙对了，这里的小端和大端分别表示着多字节数据的存储方式，就例如0xDEADBEEF这个十六进制数，如果按照小端模式存的话，那么每两个字节一个单位，最后的EF放在最下面，被输出；反之，大端模式存的话，DE放最下面，所以输出DE。得出答案。
第九题：要形成一个欧拉回路就得要有一个环，然而题目要求，所以只能有n个点，n条边得情况。考虑第一个点为1，第二个点有n-1种，第三个点n-2种，因此就是（n-1）！，又因为这其中会有一半是重复的。所以是$(n-1)!/2$,关于这个一半重复的正确性：如果直接全排列的话，每一个点有可能连到x和y,还有y和x，此时就发生了重复，所以除以2。

程序阅读：

第一题：这道题我看出来了，其实就是一个find，但感觉玄学奇怪，为什么i每一次都要加上那个映射数组shift？所以我觉得好像有点KMP的样子（~~虽然好像不是~~，所以我就照着填了，幸好只有一个空是时间复杂度，这个我就选错了，其他都对了。这个的时间复杂度竟然是$O(nm)$，最后才发现，这竟然是朴素find，被坑了，还以为提高组会考KMP。没有往朴素想。
第二题：一看选项，都是在讨论排序的，所以盲猜是排序算法，但是程序又看不懂，所以答对了1.5/13.5。其实这是一个基数排序，其原理就是按照个位数排序，然后就是十位数，以此类推……从低位开始排序，所以程序一开始给一个k就是这个数的进制，这样才可以计算最大的位数（$m$)。然后到了solve里面，显示遍历m次，遍历完一次base要*=k，这就是一个关键地方，这就是进制的体现。其实这个算法我是学过的，时间复杂度知道，原理也知道，如果当时看出来是基数排序的话，就可以做出所有题来（~~我之前都没有写过板子~~。
第三题：一看就是进制转换，但是其实这里关于到负数取模的知识，我就认为跟正数一样的，没想到有一些区别，所以后面两题就错了，如果当时用脚模拟了话，后面两题都是对的。我应该在看到有一些奇怪的时候，认真一些，甚至来细心的模拟得出答案

完善程序

第一题：我都没有认为它是一个归并，妥妥的二分好吧。后面两题没有想到要-1，第三个空我当时也应该想出来，其实就是判断要使用那个left，显示判断一下第一个的情况，如果越界了，那么边界就是第一个的，否则就是第二个的（就是选left）。
第二题：hhh，全对，感觉挺水的。

总结：

这次主要失分在于程序阅读第二题，就是对基数排序理解不够，没有在考试时一眼鉴定，下次一定要抓住一些很小的细节（例如这里面一些进制转换的部分，应该由这些想到是基数排序的。）答题还是不够仔细，单选题其实就是几道都不会的，现在了解了就可以，毕竟单选题范围很广（准备起来比较难，就是错哪里补哪里。）还有一个失分点就是完善第一个，这道题如果我再细心一点点，或许能对多一两个空。另外，阅读的第三题我没有看出取模负数这个坑。下次做题一定要细心，看穿每一个细节或者坑，争取不要在能拿到的分上丢分！

最后：

csp还有三天了，RP++！！！

CSP 2020 提高级第一轮复盘

这个是一个月前做的。

总结：66分，单选题只错了一个，阅读程序扣了20分，完善程序扣了12分。

这一套卷子可以说是很难，我光研究错题就花了一晚上……

主要失分点还是在于阅读程序最后一道，仅答对了一道题。完善程序第一题比较简单，全对，第二题只对了一个。

单选题：

第十一道题错了，其实这一道题是不应该错的，就是模拟的题。

阅读程序：

第一题：程序蛮简单的，我们只需要推理
1. x为偶数，y为偶数，那么x+y=偶数，x&y=偶数，所以x+y-x&y = 偶数。
2. x为奇数，y为奇数，那么x+y=偶数，x&y=奇数，所以x+y-x&y = 奇数。
3. x为奇数，y为偶数，那么x+y=奇数，x&y=奇数，所以x+y-x&y = 奇数。
因此，只有答案C符合要求。
第二题：第4题正确答案应该是$O(n)$，因为这个递归每一次是调用n/2的，每一次是n/2次swap，因此时间复杂度就是$1/2 + 1/4 + 1/8 + 1/16 …… = n$，因此是线性时间复杂度。第5题：平均情况指的是递归的平均分布，所以同上就是 $O(n)$ 的时间复杂度，但是最坏情况就意味着每一次递归有可能是左半边(1,n-1)右半边(2,n)。因此总时间复杂度就是$O(n^2)$。如果每一个数都是同一个数的话，那么就触犯到了最坏情况，也就是每一次都要把整一个数组扫一遍， $O(n^2)$。
第三题：是一个双向广搜，我来在代码中添加注释吧：


#include <iostream>
#include <queue>
using namespace std;

const int maxl = 20000000;

class Map {//出题人自己封装了一个假的map，时间复杂度爆炸好吧，为什么不用STL？
    struct item {//定义类型
        string key; int value;//映射
    } d[maxl];//直接开个数组！
    int cnt;//长度
  public:
    int find(string x) {//查找元素，线性时间复杂度
        for (int i = 0; i < cnt; ++i)//遍历数组
            if (d[i].key == x)//相对应的数
                return d[i].value;//找到它的映射
        return -1;
    }
    static int end() { return -1; }
    void insert(string k, int v) {
        d[cnt].key = k; d[cnt++].value = v;//增加元素
    }
} s[2];

class Queue {//将一个queue封装成自己的函数，出题人为什么不用STL啊？
    string q[maxl];//string类型的队列
    int head, tail;//头和尾
  public:
    void pop() { ++head; }//弹出操作
    string front() { return q[head + 1]; }//返回最前面
    bool empty() { return head == tail; }//判断空
    void push(string x) { q[++tail] = x;  }//加入元素
} q[2];

string st0, st1;//输入的字符串
int m;

string LtoR(string s, int L, int R) {//函数名很明显
    //将左端元素移到右端，然后其他元素往左移动
    string t = s;
    char tmp = t[L];
    for (int i = L; i < R; ++i)
        t[i] = t[i + 1];
    t[R] = tmp;
    return t;
}

string RtoL(string s, int L, int R) {//与上一个函数的作用相反
     //将右端元素移到左端，然后其他元素往右移动
    string t = s;
    char tmp = t[R];
    for (int i = R; i > L; --i)
        t[i] = t[i - 1];
    t[L] = tmp;
    return t;
}

bool check(string st , int p, int step) {
    if (s[p].find(st) != s[p].end())
        return false;
    ++step;
    if (s[p ^ 1].find(st) == s[p].end()) {
        s[p].insert(st, step);
        q[p].push(st);
        return false;
    }
    cout << s[p ^ 1].find(st) + step << endl;
    return true;
}

int main() {
    cin >> st0 >> st1;//两个字符串
    int len = st0.length();
    if (len != st1.length()) {//长度不相等，输出-1
        cout << -1 << endl;
        return 0;
    }
    if (st0 == st1) {//相等，输出0
        cout << 0 << endl;
        return 0;
    }
    cin >> m;
    //s是map，q是队列
    //初始化
    s[0].insert(st0, 0); s[1].insert(st1, 0);
    q[0].push(st0); q[1].push(st1);
    for (int p = 0;!(q[0].empty() && q[1].empty());p ^= 1) {
        string st = q[p].front(); q[p].pop();
        int step = s[p].find(st);
        if ((p == 0 &&(check(LtoR(st, m, len - 1), p, step) || check(RtoL(st, 0, m), p, step)))||(p == 1 &&(check(LtoR(st, 0, m), p,step)||check(RtoL(st, m, len - 1), p, step))))//出题人垃圾马蜂，不是，if语句写那么长……
            return 0;
    }
    cout << -1 << endl;
    return 0;
}

这个搞了半天也没怎么搞懂，y总说了，这个双向bfs在-1的情况会遍历n!种情况，也就是会搞到所有全排列，然而那个很蠢的find函数导致变成$(n!)^2$，然后不知道为什么，又要*一个n，因此时间复杂度是$O((n!)^2 \times n)$。然后第五题就是按照n找规律，是一个有规律的数列，推出来的，第四题就是因为触犯到特殊情况，所以是-1。总感觉这题是我做过最难的之一（~~我太菜了~~

完善程序

第一题，坑人，说是背包，其实就是一个分数背包，什么意思呢，就是贪心，你可以把一个东西拆了放进去，当时差点被坑了，结果幸好全对，hh
第二题：分析一下这个算法：这个算法其实朴素DP就是类似于最长上升子序列,$n^2$枚举嘛。只不过运算不是加法而是异或。优化的方法就是：将每个数前8位二进制和后8位分开来处理，只用处理一个然后再枚举255就行了，时间复杂度：$255n$ 。只需要知道x是前8位，y是后8位就行了，不需要完全理解整个程序基本上也能填出来。~~这个算法略有点玄学~~
1. 这就是一个lowbit，搞得那么阴间。
2. 这个就直接取出这个数的前八位，a >> B，就可以，只用左移B，剩下的就是前面的二进制了。（y的取法就是&上MS，因为MS是代表着后面八位的二进制都是1，所以&上了相当于把他们取出来了。）
3. 初始化为0就可以了，搞什么其他奇奇怪怪的选项…………
4. 这里面z就是枚举0~255，也就是优化的部分。发现选项前面都是Max[x][z]，所以只用看一下后面的就可以了，那必定是跟z有关的。因为Max是x到z的，所以这里应当是y与z运算的结果，也就是y^z。
5. 这道题就选这个：to_max(Max[z][y], v + w((x ^ z) << B))。你会发现只有这后面w((x ^ z) << B))是正确的（并且是独一无二）所以呢，不用管前面的max，（不过我猜测max是重新再连一条从z到y，与上面一题的空相反）。其实这里根本就不需要用到什么a，不知道搞两个这样的选项干什么？

总结：

这次的卷子很难，特别是阅读程序第三题和完善程序最后一题，阅读第三题是真的比较难，很难按照找规律推出来（主要考的还是双向bfs），完善程序第二题他给了dp公式，优化方法后，再找规律也不是特别难。

CSP 2021 提高级第一轮复盘

总结：这次才57.5分，单选错三道，阅读程序错了21.5，完善程序正好错了一半

单选题：

第五题：首先先比较前两个数，1次，后面2n-2个数两两比较，n-1次，前两个数中的max与后面n-1个两两比较的最大值比较，n-1次，前两个数中的min与后面n-1个两两比较的最小值比较，总共：$1+n-1+n-1+n-1 = 3n-2$。
第十三题：分类讨论：挑一个$C_8^1=1$;接下来考虑插空法，挑两个，剩下7个位置$C_7^2=21$;挑三个$C_6^3=20$;挑四个$C_6=5^4=5$，挑五个不符合条件，所以答案是$8+21+20+5=54$
第十四题：直接枚举相等的两条边的长度时另一条边等于几，最后累加起来，考虑到等腰三角形的形态：aab,aba,baa。所以乘3，在考虑等边三角形重复计算的数量$2\times9$,所以最终的答案是:$165$。

阅读程序：
第一题：是一个求球的体积交，~~搞不太懂这些球的高级东西~~。
第二题：用两种方法求最大字段和，最后一题~~我这个大葱明~~，第一个数是n啊，啊啊。
第三题：这个一看就是一个解密和加密的过程，网上大佬说是将三个数拆成四个数这样来加密，首先第一个空是错的，如果有\n答案就有问题了，第32题，因为char只占一个字节，所以11111111是其-1的补码，因此答案输出-1，CCF出题人可真谓是精心布置陷阱啊啊！

完善程序：

第一题：比较简单，~全对hh
第二题：那是可恶的~~三体表~~(ST表)，~~人民币问题~~（RMQ问题）。我太菜了，学完这些又忘了，这一道题的思想就是优化RMQ问题，可以做得到线性预处理，O(1)查询，感觉很秀耶！不过这道题的前置知识也太多了，感觉不是一天两天能搞得懂的，后天就要考试了，还是先放一下这一题吧。~~PS：怎么我印象中那些题目我是选了正确答案的，怎么最后显示另一个答案，难道被JC了？~~。其实我是按照一些规律和策略来把这几个空填了的，按理来说应该只错两道的，所以我好像白丢了9分（玄学。

2019CSP-S初赛复盘

总结：这次 74.5，算是还可以，毕竟这是第一届csp嘛，比较简(du)单(liu)。单选题错两道，阅读程序扣9.5。完善程序错4道。主要失分在于完善程序第二题（抽象短小的代码蒟蒻看不懂

单选题：

第五题：没仔细做，强转int只是前面一部分，后面没有强转。
第六题：直接枚举每次选的数，然后计算其每一种可以拼出来的个数。
第九题：~~蒙对的~~，我们可以知道，前两位只能放0,1,8,6,9,5，而中间放0，1，8。第一位放了，第五位确定，第二位放了，第四位确定，那么剩下第三位。而我们发现0，1，8三个数%3正好构成了%3的完全剩余系（说人话呢，就是说有%3可能的结果他都有了，0，1，2嘛)，那么这个又意味着什么？意味着我们前两个数可以随便凑，因为如果其他四个数%3=0，那么可以中间放0，使得%3也等于0，其他四个数%3=1，那么中间可以放8使得%3=2，那么加起来%3就等于0了。也就是说，因为有了完全剩余系，所以%3多少都能选一个唯一的数来填满（使得整除3），因此答案为5*5=25。

主要还是排列组合这一块不太行，还有就是细心的问题！