CSP测试中完善程序题目的解题经验与运用

预计阅读时间：10分钟 

一、方法总结

 1、初步理解 

初步观察程序的时候，我们应该 

• 通过变量名称初步判断该变量的作用（如result和ans就是反馈和答案的意思）；
• 通过函数名称初步分析理解函数的作用（如dfs就是深搜的意思）；
• 通过循环的内容初步判断循环的作用。

 2、相关填空

如果需要填for循环条件，则

• 通过循环变量的变化并结合题意和选项判断循环的结束条件；
• 通过数组的内容与含义了解循环变量的作用并判断循环结束条件。

 如果要填for循环内容，则

• 需要先知道for循环在干什么，常见的有输入数组、判断前导0、拆分、打擂台等；
• 判断之后进行填空。 

如果需要填while循环条件，则

• 根据循环内容及变量的变化判断结束条件；
• 根据题目要求判断结束条件。 

如果需要填while循环内容，则

• 根据循环条件判断出循环在干什么，然后进行填空。

如果需要填if条件，则

• 根据内容想一想为什么要if；
• 知道为什么之后将原因写在条件里。

如果需要填if的内容，则

• 根据条件想想在这个条件下应该干什么，为什么。 

如果if条件和内容都要填，则

• 根据题目或循环含义想想有哪些特殊情况；
• 根据选项进行选择。 

如果需要填变量初始化，则

• 根据变量意义及作用判断初始值（常见的有1、0、-1和0x3f）。 

如果需要填函数的参数，则

• 先明白函数的含义；
• 再到函数里进行参数变化及使用的观察即可。 

如果需要填函数返回值，则

• 根据函数的变量以及含义判断返回值；
• 根据题目要求判断返回值；
• 注意返回值的类型（如bool只能返回true或false）。

如果需要填打擂台的对象（这么说可能不好理解，简单来说就是max(ans,__)这种），则

•  想想哪些变量有可能需要进行打擂台。

 如果需要填运算符（if(a___b==c)这种），则

• 想明白为什么需要填，填之后会有什么变化，再进行填写。

如果需要填输出内容，则

• 根据题目要求判断当前在输出什么，再判断当前需要输出什么变量即可。 

3、重点来啦!! 

 注意观察题目给出的注释和提示！！

好像大概就是这些，下面是运用。

---

二、运用

上真题！

（2018NOIP普及组初赛）

        对于一个 1 到 n 的排列 P即 1 到 n中每一个数在 P 中出现了恰好一次），令 q[i]为第 i个位置之后第一个比 P[i] 值更大的位置，如果不存在这样的位置，则 q[i] = n + 1。举例来说，如果 n = 5 且 P为 1 5 4 2 3 ，则 q 为2 6 6 5 6。
        下列程序读入了排列 P ，使用双向链表求解了答案。试补全程序。

#include 
using namespace std;
 
const int N = 100010;
int n;
int L[N], R[N], a[N];
 
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        ① ;
    }
    
    for (int i = 1; i <= n; ++i) {
        R[i] = ② ;
        L[i] = i - 1;
    }
    
    for (int i = 1; i <= n; ++i) {
        L[ ③ ] = L[a[i]];
        R[L[a[i]]] = R[ ④ ];
    }
    
    for (int i = 1; i <= n; ++i) {
    	cout << ⑤ << " ";
    }
    
    cout << endl;
    return 0;
}

 解析

       先说说这道题怎么拿链表解决。

       先找到最小的元素，是第1位的1，它右边不论是几都肯定比它大，所以这一位的答案就是右侧的第2位。
        此时把它从链表中删除，让前一位直接指向后一位。

        再在链表中找到最小的元素，是第4位的2，它右边不论是几都比它大，所以这一位的答案是第5位。
        再从链表中把2删除，让前一位指向后一位。

        继续这个过程，找到最小的元素是第5位的3，它右侧的元素肯定比它大，因此这一位的答案是第6位。
        然后从链表中把3删除，让前一位指向后一位。

         继续，最小的元素是第3位的4，它右侧的元素（第6位）比它大，这一位答案是6。
         从链表中删除4。

         最后只剩第2位的5，右侧（第6位）比它大，这一位答案是6。把它删除后，整个操作结束。

       最后只剩第2位的5，右侧（第6位）比它大，这一位答案是6。把它删除后，整个操作结束。
       最终的答案就是过程中记录下的数据，第1位是2，第4位是5，第5位是6，第3位是6，第2位是6，
       即答案数组2 6 6 5 6。

       程序用的是双向链表，L和R相当于分别存储了每个元素的上一位和下一位。
       这样有什么好处呢？副产品会更多。
       最终不止知道每个元素后面比它大的第一个元素在哪，还能知道前面比它大的第一个元素在哪。
       第2个for循环，显然它是先把ii对应到a[i]，再对应到L和R数组，为什么呢？为了去掉每轮都要先寻找最小值的过程。先存一下第1小、第2小、第3小……的值依次出现在哪儿，每轮就能直那一位。
       第1题：a[x] = i    因为正好是1~n的排列
     x就表示第x小的数
     a[x]表示第x小的数出现的位置
     p数组：1 5 4 2 3
     a数组：1 4 5 3 2
       即最小的数出现在第1位，第2小在第4位……
       第2题：i + 1
     L记录前面第一个更大值的位置
     R记录后面第一个更大值的位置
       根据最值更新链表的过程，定位到当前的最小值后，就要从双向链表中将它删除。
     i表示的是当前要找第i小的数，它的实际位置是a[i]，所以i与链表操作无直接关系，都是与a[i]有关。
       要让前一位和后一位直接互相指向，用自己的前一位更新后一位的前一位，用自己的后一位更新前一位的后一位。
       第3题：R[a[i]]
       第4题：a[i]
       我们假定位置ii后边的最大数字的位置为i+1，然后从最小的1开始更新，让1所在位置的前一位直接指向1的后一位（1不可能是1所在位置的前一位的后边的第一个最大的，相当于删除了1）。从小到大循环删除所有的不合法假定，剩下的就是答案。
       第5题：R[i]
     R记录后面第一个更大值的位置

 (2021CSP入门级第一轮认证)

(Josephus 问题）有 n 个人围成一个圈，依次标号 0 至 n-1。从 0 号开始，依次 0, 1, 0, 1, ... 交替报数，报到 1 的人会离开，直至圈中只剩下一个人。求最后剩下人的编号。
试补全模拟程序。

#include 
 
const int MAXN = 1000000;
int F[MAXN];
 
int main(){
    int n;
    scanf("%d", &n);
    int i = 0, p = 0, c = 0;
    while(①){
        if (F[i] == 0){
            if ( ② ){
                F[i] = 1;
                ③; 
            }
            ④; 
        }
        ⑤; 
    } 
    int ans = -1;
    for (int i = 0; i < n; i++)
        if (F[i] == 0)
            ans = i;
    printf("%d\n", ans);
    return 0;
} 

①处应填（）

A.i < n
B.c < n
C.i < n - 1
D.c < n - 1
②处应填（）

A.i % 2 == 0
B.i % 2 == 1
C.p
D.!p
③处应填（）

A.i++
B.i = (i+1) % n
C.c++
D.p ^= 1
④处应填（）
A.i++
B.i = (i+1) % n
C.c++
D.p ^= 1
⑤处应填（）
A.i++
B.i = (i+1) % n
C.c++
D.p ^= 1

 解析 

       本题考查变量与数组作用。
       数组F：由第22,23行发现F与答案输出有关，当F[i]为0时输出答案，因此可知F为标记是否出圈的数组。F[i]=0代表未离开，为1代表已离开
       变量c：观察有c的选项。发现特殊的，第一空中可能填入c，而第一空为while的边界条件。由题意可知循环结束条件为出圈人数达到n-1，联系选项可得c代表出圈人数。
       变量i：根据日常使用习惯结合题目选项合理考虑，可以猜测i为当前进行判定的位置，实际上确实如此
       变量p：剩余一个变量为p不知道作用。阅读题面发现“交替出圈”还未实现，且p初始化为0。结合第二空的选项以及第二空决定F[i]是否等于1（即是否出圈）来看，可以得知p用于判断当前人是否应当出圈。p为0则不出， p为1则出圈。
       1.c代表出圈人数，由题面可知出圈n-1个则循环结束
       2.由上推导可得，此处用于决定是否出圈，则与p有关。若p为1则出圈
       3.有一人出圈，出圈人数c增加
       4.实现p的01交替，0变1,1变0，使用异或1实现
       至此只剩一个操作也就是移动当前考虑的位置，注意到人围成一个环，因此需要进行取模。

       本题答案为DCCDB。

---

以上就是本文的全部内容啦！感谢阅读！