????????????
????????????Hello，大家好我是[上进小菜猪]，一个有趣的全栈博主，欢迎关注，多多关照????????????
????????????欢迎大家找我合作学习（文末有VX与公众号 想进学习交流群or学习资料or一起刷题 欢迎++）????????????
????????????苟怀四方志，所在可游盘，一起加油进步！????????????
????????????

一，快排问题

标签：2016，省赛，代码补全填空题

题目描述

本题为代码补全填空题，请将题目中给出的源代码补全，并复制到右侧代码框中，选择对应的编译语言（C/Java）后进行提交。若题目中给出的源代码语言不唯一，则只需选择其一进行补全提交即可。复制后需将源代码中填空部分的下划线删掉，填上你的答案。提交后若未能通过，除考虑填空部分出错外，还需注意是否因在复制后有改动非填空部分产生错误。
排序在各种场合经常被用到。 快速排序是十分常用的高效率的算法。
其思想是：先选一个“标尺”，用它把整个队列过一遍筛子，以保证：其左边的元素都不大于它，其右边的元素都不小于它。
这样，排序问题就被分割为两个子区间。 再分别对子区间排序就可以了。
下面的代码是一种实现，请分析并填写划线部分缺少的代码。
源代码

#include <stdio.h>

void swap(int a[], int i, int j)
{
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

int partition(int a[], int p, int r)
{
    int i = p;
    int j = r + 1;
    int x = a[p];
    while(1){
        while(i<r && a[++i]<x);
        while(a[--j]>x);
        if(i>=j) break;
        swap(a,i,j);
    }
    _____________________;
    return j;
}

void quicksort(int a[], int p, int r)
{
    if(p<r){
        int q = partition(a,p,r);
        quicksort(a,p,q-1);
        quicksort(a,q+1,r);
    }
}
    
int main()
{
    int i;
    int a[] = {50,49,48,48,47,46,1,3,5,2,4,6,30,30,30,30};
    int N = 16;
    
    quicksort(a, 0, N-1);
    
    for(i=0; i<N; i++) printf("%d.", a[i]);
    printf("\n");
    
    return 0;
}

答案：

swap(a,p,j);

总结：考察快速排序双指针，不熟悉难度较大。

二，抽签

题目描述
本题为代码补全填空题，请将题目中给出的源代码补全，并复制到右侧代码框中，选择对应的编译语言（C/Java）后进行提交。若题目中给出的源代码语言不唯一，则只需选择其一进行补全提交即可。复制后需将源代码中填空部分的下划线删掉，填上你的答案。提交后若未能通过，除考虑填空部分出错外，还需注意是否因在复制后有改动非填空部分产生错误。
X星球要派出一个 5 人组成的观察团前往 W 星。

其中：
A 国最多可以派出 4 人。
B 国最多可以派出 2 人。
C 国最多可以派出 2 人。
....

那么最终派往 W 星的观察团会有多少种国别的不同组合呢？

下面的程序解决了这个问题。 数组 a[] 中既是每个国家可以派出的最多的名额。 程序执行结果为：

DEFFF
CEFFF
CDFFF
CDEFF
CCFFF
CCEFF
CCDFF
CCDEF
BEFFF
BDFFF
BDEFF
BCFFF
BCEFF
BCDFF
BCDEF
....
(以下省略，总共101行)

下面的代码就是为了这个目的的，请仔细阅读源码，并填写划线部分缺少的代码。

源代码
C

#include <stdio.h>
#define N 6
#define M 5
#define BUF 1024

void f(int a[], int k, int m, char b[])
{
    int i,j;
    
    if(k==N){ 
        b[M] = 0;
        if(m==0) printf("%s\n",b);
        return;
    }
    
    for(i=0; i<=a[k]; i++){
        for(j=0; j<i; j++) b[M-m+j] = k+'A';
        ______________________;  //填空位置
    }
}
int main()
{    
    int  a[N] = {4,2,2,1,1,3};
    char b[BUF];
    f(a,0,M,b);
    return 0;
}

答案：

f(a,k+1,m-j,b);  //填空位置

总结：经典的递归题目

三，方格填数

题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

   +--+--+--+
   |  |  |  |
+--+--+--+--+
|  |  |  |  |
+--+--+--+--+
|  |  |  |
+--+--+--+

填入 00 ~ 99 的数字。要求：连续的两个数字不能相邻。 （左右、上下、对角都算相邻）

一共有多少种可能的填数方案？

运行限制 最大运行时间：1s 最大运行内存: 128M

答案：

1580

分析

#include<bits/stdc++.h>
using namespace std;
bool check(int a[])
{
    if(abs(a[0]-a[1])==1||
       abs(a[0]-a[4])==1||
       abs(a[0]-a[5])==1||
       abs(a[0]-a[3])==1||

       abs(a[1]-a[2])==1||
       abs(a[1]-a[4])==1||
       abs(a[1]-a[5])==1||
       abs(a[1]-a[6])==1||

       abs(a[2]-a[5])==1||
       abs(a[2]-a[6])==1||

       abs(a[3]-a[4])==1||
       abs(a[3]-a[8])==1||
       abs(a[3]-a[7])==1||

       abs(a[4]-a[5])==1||
       abs(a[4]-a[7])==1||
       abs(a[4]-a[8])==1||
       abs(a[4]-a[9])==1||

       abs(a[5]-a[6])==1||
       abs(a[5]-a[8])==1||
       abs(a[5]-a[9])==1||

       abs(a[6]-a[9])==1||

       abs(a[7]-a[8])==1||

       abs(a[8]-a[9])==1
       )
    {
        return false;
    }
    return true;
}
int main()
{
    int a[11]={0,1,2,3,4,5,6,7,8,9},sum=0;

    while(next_permutation(a,a+10))
    {
        bool b=check(a);
        if(b)
        {
            sum++;
        }
    }
    cout<<sum<<endl;
return 0;
}

**今日总结：
快排和全排列问题。**

四，END

????????????关注作者，持续阅读作者的文章，一起学习更多知识！
[点击关注，联系作者，进入群聊，一起刷题]????????????

如果有更优解法及其思路，欢迎讨论。