CSP-J初赛复习大题整理笔记

本篇全是整理，为比赛准备.





在这里插入代码片

#include<cstdio>
using namespace std;
int n, m;
int a[100], b[100];int main() {scanf_s("%d%d", &n, &m);for (int i = 1; i <= n; ++i)a[i] = b[i] = 0;//将两个数组清0，这步基本谁都能看懂for (int i = 1; i <= m; ++i) {int x, y;scanf_s("%d%d", &x, &y);if (a[x] < y && b[y] < x) {//这步就很有迷惑性了，如果一拿到这道题，可能会以为是一个类似取最大//值的题目，但是分析一下总感觉哪里有问题，"a[x]<y&&b[y]<x"这步看不//的话我们具体来分析一下，首先当i=1的时候，a[x]和b[y]都是==0，如果// x和y不等于，肯定能够进来,在到后面的时候，如果我的x和y都不同于前// 面所输入的x和y，那么我的a[x]和a[y]永远都是==0的，都能进来，那如// 果与前面的相同，我则需要比较一下，如果比之前那个大，就能进来，否// 则就进不了这层循环，直接进下一层forif (a[x] > 0)//"a[x]>0和b[y]>0这两种情况就说明了我之前已经输入过一遍甚至多遍这次的x和y，而为什么要清0呢？b[a[x]] = 0;//上面已知我这次的x和y已经进入过这层if，而我这次还能进去说明我满足的那个"[x] < y && b[y] < x"的条件//而我肯定要把这次的x和y值分别赋给a[x]和a[y]，但是在赋值之前，我一定要把b[a[x]]和a[b[y]]给清0，理解// 起来就是说先要把之间连的那条给断掉，再连新的嘛//让我们举个栗子就是说：初始x=3，y=2,然后进了if判断，使得a[3]=2.b[2]=3.,然后呢第二次我让x还等于3，y=4，//这时候的a[3]==2，是小于现在的y也就是4的，然后b[4]==0,也小于当前的x也就是3，所以进了if循环。这时候我的// a[x]因为x之前输出过一遍相同的，所以呢a[x]是铁定>0的，进入那个if(a[x]>0)的循环，然后这时候重点来了，他让b[a[x]]=0，//我们看下，现在的a[x]还是上一次的for赋值的a[x]=y也就是a[3]=2，那么b[a[x]]也就是相当于b[3]嘛，注意我这时候因为输了两// 遍3进去，所以说x是等于3的，等于3因为之前有过赋值操作所以a[x]就不会为0，好，我们现在把b[2]=0了，我们回去看一下，b[2]// 是什么？他就是上一次循环与a[3]相连的那个b[2]呀，我上次让a[3]=2,b[2]=3,理解起来就是让这两个点互连，为什么呢？因为我可// 以通过b[2]的值找到与他相连的a数组的那个下标，同样我也可以通过a[3]的值找到与他相连的b点的下标，但是我时候把b[2]清0了，// 为什么？因为我目前录入了一个y值是比之前录入的y值更大，所以我们根据题目条件，要重新将a[3]和b[4]相连，但是一个a[3]只能// 链接一个b[i]呀，所以我们要清除第一个链接的b[2]，也就是说要取消a[3]与b[2]的链接，重新将a[3]与b[4]相连。这就是这短短一// 句话的含义，同样下面那个if语句是同理的，就不多于赘述。if (b[y] > 0)a[b[y]] = 0;a[x] = y;//最后这两步在我认为还是有个小坑，就是说为什么不放在if语句的里面而是放在这里？之前讲了这个if进来的条件1.是x与之前的x都不一样，b[y] = x;//2.是我x和y中有一个是与之前一样的，另一个的话是要大于之前那个的，举个例子就是说我第一次x=2，y=3，第二次x=2，y就要>3，或者y=3，//x就要>2,这样才能进入这个if语句里进行模拟。而我这两种情况第一种的话是进不去a[x]>0和b[y]>0这两个if的，直接进行赋值操作，第二种情况// 呢则是需要先把之前那个链接的断掉，这步操作呢在上面两个if中就完成了，剩下的还是要连接新的，也就是赋值操作，所以说两种情况都需要进// 行最后的相互连接，写在这里能减少一丢代码难度。}}int ans = 0;for (int i = 1; i <= n; ++i) {//这个if就很简单，就是看下a和b数组中有多少个没有连接成功的，最后统计ans，输出出来就行if (a[i] == 0)++ans;if (b[i] == 0)++ans;}printf_s("%d", ans);return 0;
}