2025 CSP J1/S1 游记

昨天参加了CCF的CSP-J1/S1竞赛，总体感觉不是很好。上午的J组因为是第一次考，又有点紧张，做题顺序和思维比较混乱，然后出考场对完答案之后整个人都不好了~~因为挂了个50多分~~，但睡完一觉还得继续考S组，所以还是暂时遏制住了崩溃的心态，走进下午的考场。借鉴了上午的经验，下午考S组的时候状态明显好了很多，没有那么慌，整个做题的过程也比较稳定冷静了。查分的时候比J组都高也是不可思议了。~~不会J组没过S组过了吧~~

CPP

上午J组的题选择题开门红，int类型无符号和有符号表示范围应该分别是2^32-1和-2^31~2^31。换算成十进制≈4*10^9。这题错了纯属弱智行为。

逻辑表达式：只有C项在a=1,b=0,c=0时与原式不等价。这道题只有耐心一点，分别列举a b c可能的情况就可以做出来。

路径问题：移动方式：向右 4 步、向下 3 步，共 7 步；路径数 C(7,3)就解出来了。

完全二叉树算叶子节点，可以结合完全二叉树的性质：叶子结点数=总结点数/2；

双指针+去重：

CPP

#include<bits/stdc++.h>
using namespace std;
int main(){
  int n, k;
  int a[200007];
  int ans[200007];

	scanf("%d%d",&n,&k);
	for (int i=1; i <= n; +i){
		scanf("%d"，&a[i]);
	}
	sort(a + 1,a + n + 1);
	n = unique(a + 1,a +n + 1)-a-1;
	for (int i = 1,j= θ; i<= n; ++i){
		for (; j<i && a[i]- a[j + 1]>k;++j)
			;
		ans[i]= ans[j]+ 1;
	}
	printf("%d\n",ans[n]);
	return 0;
}

CPP

①函数 unique(a+1,a+n+1)-a-1; 就是对a数组进行去重操作。

②26.当输入的 n=100、k=2、a={1,2,...,100}时，输出为（）
  A.34
  B.100
  C.58
  D.33
解析：将 1~100 以窗口差≤2 的最少分段，等价每段至多 3 个数，就有100/2=34（向上取整）个段。

二维DP+LCS（最长公共子序列）变体:

CPP

#include<bits/stdc++.h>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define 1l long long
int f[5007][5007];
int a[5007],b[5007];
int n;
int main(){
  scanf("%d"，&n);
  for (int i = 1; i <= n; ++i){
    scanf("%d"，&a[i]);
  }

  for (int i= 1; i <= n; ++i){
    scanf("%d"，&b[i]);
  }

  for (int i = 1; i <= n; ++i){
    for (int j = 1; j<= n; ++j){
      f[i][j]=max(f[i][j],max(f[i -1][j],f[i][j -1]));

      if (a[i]== b[j]){
        f[i][j]=max(f[i][j],f[i -1][j -1] + 1);
      }
    }
  }
  printf("%d\n",f[n][n]);
  return 0;
}

CPP

33.如果输入的 a={1,2,...,n}，而且 b数组中数字均为 1~n 中的正整数，则上述代码等价于下面哪个问题:()

A.求b数组去重后的长度

B.求b数组的最长上升子序列

C.求b数组的长度

D.求b数组的最大值

解析：当 a=1到n 严格递增时，最长公共子序列(a,b) 等价于 b 的最长递增子序列（在自然顺序下）。

下午做S组选择题的时候，后悔前一天晚上为什么没有把字典树搞明白。要是弄明白了就可以对一道选择题了（我哭）。

第一题，隔板法：

使用隔板法（先安排红球，再插入蓝球）

由于蓝球不能相邻，我们可以先安排红球，然后在红球之间的空隙（包括两端）插入蓝球。

1.先排列红球(所有红球相同，所以只有1种方式）

CPP

将5个红球排成一排：
   R R R R R

这样形成了6个空隙（包括两端）：
   _ R _ R _ R _ R _ R _

2.在空隙中插入蓝球（每个空隙最多放1个蓝球，以避免蓝球相邻）：

CPP

我们需要插入5个蓝球，但只有6个空隙可用。

因此，必须从6个空隙中选择5个来放置蓝球（每个空隙放1个）。

选择方式数为：C(5,6)=6

3.由于蓝球也完全相同，一旦选定了空隙，放置方式只有1种。

CPP

因此，总排列方法数为：C(5,6)=6

为什么每个空隙最多只能放1个蓝球？

CPP

  如果同一个空隙放多个蓝球，这些蓝球就会相邻（因为它们之间没有红球隔开）。
  例如，如果在某个空隙放2个蓝球，就会形成“BB”，这违反了规则。
  所以，必须每个空隙至多放1个蓝球。

文章操作

相关推荐

评论

2025 CSP J1/S1 游记