初赛做题方法

xxx听取AC声一片 · 2023-09-15 19:56:18 · 科技·工程

rt，本文章主要讲讲初赛中的阅读程序题或者单选题中的程序题该怎么写。

文章分为两个部分：递归代码和非递归代码。

单选题部分

在csp的单选题中，的确可能会有程序，但基本上都比较简单，即使是递归，递归层数也不会深到哪里去。

所以，csp的递归中，我们用如下的方式来模拟代码。

 第一个参数: 1 2 3 4 5
第 1
二 2
个 3
参 4
数 5

没错，就是类似记忆化的方式。递归题基本上都是这个套路。

至于非递归的...一般都是些很短的代码，然后有几种题型：

等价于什么代码，例如那个很常见的:
```
s=a;
for(b=1;b<=c;b++)
s++;
```
初赛题刷的比较多的，都见过吧。

预测结果，例如BBCC第一轮:

int ans=0;
for(int i=5;i>=0;i-=2)
ans=ans*10+i;
cout<<ans;

哪个语句错了（抱歉忘记是哪题了）

这些题目基本上手玩都可以想出答案。

阅读程序题

同单选题，我们也讲讲题型，例题和解法。

更改blablabla，程序结果会/不会改变

简单一点的可以手玩，复杂一点的可以从代码入手。

例如

int ans=-1;
for(int i=1;i<=n;i++)
   for(int j=1;j<=n;j++)
        if(d[i]<d[j]) ans=max(d[i]+d[j]+(d[i]&d[j]),ans);
cout<<ans;

将d[i]<d[j]改为d[i]!=d[j],程序结果不会改变(对/错)

从代码中我们可以明白，将d[i]>d[j]改为d[i]!=d[j]，只是多加了d[j]>d[i]这个条件，但是当 i 循环到 j 的时候，即使不改，这个条件还是会被满足并执行后面的语句。

答案：对。

程序结果会...

还是刚刚那个代码：

输出是否一定大于0

从赋值语句入手，ans 初始时为 -1，为了避免 ans 被给到其他的值，我们必须让 ans 在循环中不被给到其他值。

所以必须让 if 语句永不满足，所以能想到当 d_i 两两相等时，输出-1。

当输入...时，程序结果为...

这里直接给大家讲讲怎么手玩非递归代码，笔者习惯用一下的结构：

	0	1	2	3	4	5	6
a
b
ans	正

平常的计数器我习惯画正字，建议用铅笔来模拟，毕竟数值有变动方便更改。

对于 base64 这种初赛恶魔，这方法再好用不过了。

当然，平常积累代码模板也是一个比较重要的方面，有时候能通过代码来判断程序在做什么，不过小心程序的一些坑，例如 CSP-S2019 的阅读程序第二题，很多人都能看出来它是并查集，但没留意到它没有判断两点在同一集合的情况。

该代码的（最坏/最好/平均）时间复杂度是：

这个就是手算时间复杂度，以平均时间复杂度为例，最坏/最好直接往最坏/最好的情况想就好。

举个例子，有个人跳楼的，最坏的情况就是下面有一排尖刺，最好的情况就是下面有一堆干草，平均的就是下面啥都没。

接下来讲正经的。

程序的复杂度有O(n),O(1),O(logn),O(\sqrt{n}),O(n^2),O(nlogn),O(n\sqrt{n})...

而这些主要是由程序中的循环和递归函数来推断的，例如：

for(int i=3;i<=n;i*=2)
   for(int j=1;j<=2;j++)
        cin>>a;

首先，我们可以得出复杂度为 O(log(n-3)\times 2)，省略常数和系数就得到了该代码的时间复杂度为 O(logn)。

递归的则是看它递归了多少层，而每层的时间复杂度又是多少，例如下面这个：

void quick_sort(int l,int r)
{
    if(l>=r) return ;
   int mid=(l+r)>>1,l1=l,r1=r;
   while(l1<r1)
   {
        while(l1<r1 && a[l1]<a[mid]) l1++;
      while(l1<r1 && a[r1]>=a[mid]) r1--;
      swap(a[l1],a[r1]);
      l1++,r1--;
    }
   quick_sort(l,mid);
   quick_sort(mid+1,r);
}

代码中可以看出，区间每次折半，平均下来递归O(logn)层，每层总共循循环O(n)次，时间复杂度为O(nlogn)。

空间复杂度跟时间复杂度有相似之处，只不过要看的是数组等储存器的长度

\text{谢谢观看}

祝各位CSP2023 rp++