【CSP-J/S】复赛知识点

经验分享区
1

0.前言

由于初赛更完了，所以只能更复赛了。
本帖蒟蒻做，也是很cai，有问题请及时指出。

1.复赛的题目结构

复赛有4道编程题目，每题100分，共400分。
而且，现在的CSP-J就是以前的NOIP。

2.排序

由于这次要讲的排序与分治有关，所以先科普一下分治。

2.1 分治

分治就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
分治一般有这几步：

1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

3 合并：将各个子问题的解合并为原问题的解。

如： P1115 最大子段和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
大家去练习一下，分治AC代码（不是我写的）在

这里 
#include<cstdio>
int n , arr[200200]; //arr存储该序列 
const int minn = -19260817; // 定义最小值 
inline int Max( int a , int b) { return a > b ? a : b ;} //自定义 Max 函数（好像比stl的快一点） 
int rec( int l , int r ) { //分治函数 
    if ( l == r ) {    //    l=r时，直接返回该位置的值 
        return arr[l];
    }
    int mid = ( l + r ) >> 1;  
    int sum = 0 , ret1 = minn , ret2 = minn; //ret1为[l..mid]区间内包含mid的最大子段和，ret2为[mid+1..r]区间内包含(mid+1)的最大子段和  
    for( int i = mid ; i >= l ; i-- ) {
        sum += arr[i];
        ret1 = Max( ret1 , sum );
    }  //求出[i..mid]区间最大值
    sum = 0;
    for( int i = mid+1 ; i <= r ; i++ ) {
        sum += arr[i];
        ret2 = Max( ret2 , sum );
    }  //求出[mid+1..r]区间最大值
    return Max( Max( rec( l , mid ) , rec( mid + 1 , r ) ) , ret1 + ret2 );   //返回可能一 可能二 可能三 中的最大值
}
int main() { // 以下主函数  
    scanf("%d", &n );
    for( int i = 1 ; i <= n ; i++ ) {
        scanf("%d" , &arr[i] );
    }
    printf("%d" , rec(1 , n) ); 
    return 0;
}

2.2 快速排序

这里是详细介绍。 快速排序 - OI Wiki

快速排序的原理

我们设待排序的序列为一个长度为 n 的序列 a。快速排序的具体原理如下：
首先，在 a 中随机选择一个数 x，之后我们进行如下操作：

  • 如果 n<2 ，此时根本无需排序，直接退出；
  • 定义三个新的序列 b,c,d；
  • 遍历整个序列 a，将比 x 小的放在 b 内，比 x 大的放在 d 内，和 x 相等的放在 c 内；
  • 将 b,d 按如上过程继续排序。序列 c 中的数因为都相等所以不必排序。
  • 重复此过程

快速排序代码

int a[N];
void sort_1(int l,int r){
    if(l>=r) return;
    int x=a[l+r>>1];
    int i=l-1,j=r+1;
    while(i<j){//将a分为 <=x 和 >=x 的两个小数组
        do i++;while(a[i]<x)//do-while循环,i和j一定会自增,使得循环会继续下去
        do j--;while(a[j]>x)//while循环,i和j特殊情况下不自增,循环卡死
        if(i<j)swap(a[i],a[j]);
    }
    sort_1(l,j);
    sort_1(j+1,r);//递归处理两个小数组
    return;
}

未完结…

2 个赞