1. 结果填空 (满分13分)
标题：三角形面积

已知三角形三个顶点在直角坐标系下的坐标分别为：
(2.3, 2.5)
(6.4, 3.1)
(5.1, 7.2)

求该三角形的面积。

注意，要提交的是一个小数形式表示的浮点数。
要求精确到小数后3位，如不足3位，需要补零。

答案：

#include <cstdio>
#include <iostream>

using namespace std;

struct dian{
    double x,y;
};

int main()
{
    dian A,B,C;
    scanf("%lf %lf %lf %lf %lf %lf",&A.x,&A.y,&B.x,&B.y,&C.x,&C.y);
    double Area = 0.5*(A.x*B.y - A.x*C.y - B.x*A.y + A.y*C.x + B.x*C.y - C.x*B.y);
    printf("%.3lf\n",Area);
    return 0;
}

2. 结果填空 (满分39分)
标题：阅兵方阵

x国要参加同盟阅兵活动。
主办方要求每个加盟国派出的士兵恰好能组成 2 个方阵。
x国发现弱小的 y国派出了130人的队伍，他们的士兵在行进中可以变换2种队形：
 130 = 81 + 49 = 9^2 + 7^2
 130 = 121 + 9 = 11^2 + 3^2

x国君很受刺激，觉得x国面积是y国的6倍，理应变出更多队形。
于是他发号施令：
我们要派出一支队伍，在行进中要变出 12 种队形！！！

手下人可惨了，要忙着计算至少多少人才能组成 12 种不同的双方阵。
请你利用计算机的优势来计算一下，至少需要多少士兵。

（ps: 不要失去信心，1105人就能组成4种队形了）

注意，需要提交的是一个整数，表示至少需要士兵数目，不要填写任何多余的内容。

答案：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>

using namespace std;
int num[2000000],m = 2000000;
int main()
{
    for(int i = 1;i < 1000; ++i) {
        for(int j = i; j < 1000 ; ++j) {
            int d = i*i + j*j;
            num[d]++;
            if(num[d] >= 12) m = min(m,d);
        }
    }
    //打印看一下
    printf("%d\n",m);
    for(int i = 1;i * i * 2 <= m; ++i) {
        int d = (int)sqrt(m - i*i);//这一步用的十分细致
        if(d*d == m - i*i) {
            printf("%d^2 + %d^2 = %d\n", i , d , i*i + d*d);
        }
    }
    return 0;
}

3. 代码填空 (满分27分)

标题：找假币

在8枚硬币中，有1枚假币，假币外观与真币一模一样，只是重量略轻或略重一点。
给你一架天平，要求最多称3次，就找出假币，并且知道它是重一些还是轻一些。
下面的代码给出一个解决方案，仔细分析逻辑，填写划线位置缺少的代码。

#include <stdio.h>

int balance(int a, int b)
{
	if(a<b) return -1;
	if(a>b) return 1;
	return 0;
}

void judge(char* data, int a, int b, int std)
{
	switch(balance(data[a],data[std])){
	case -1:
		printf("%d light\n", a);
		break;
	case 0:
		printf("%d heavy\n", b);
		break;
	case 1:
		printf("err!\n", b);
	}
}

// data 中8个元素，有一个假币，或轻或重
void f(char* data)
{
	switch( ____________________________________ ){  // 填空
	case -1:
		switch(balance(data[0]+data[4],data[3]+data[1])){
			case -1:
				judge(data,0,3,1);
				break;
			case 0:
				judge(data,2,5,0);
				break;
			case 1:
				judge(data,1,4,0);
		}
		break;
	case 0:
		judge(data,6,7,0);		
		break;
	case 1:
		switch(balance(data[0]+data[4],data[3]+data[1])){
			case -1:
				judge(data,4,1,0);
				break;
			case 0:
				judge(data,5,2,0);
				break;
			case 1:
				judge(data,3,0,1);
		}
		break;		
	}	
}

int main()
{
	int n;
	char buf[100];
	
	scanf("%d", &n);
	gets(buf);
	
	int i;
	for(i=0; i<n; i++){
		gets(buf);
		f(buf);
	}
	
	return 0;
}

请注意：只需要填写划线部分缺少的内容，不要抄写已有的代码或符号。

4. 程序设计（满分41分）

标题：约瑟夫环

n 个人的编号是 1~n，如果他们依编号按顺时针排成一个圆圈，从编号是1的人开始顺时针报数。
（报数是从1报起）当报到 k 的时候，这个人就退出游戏圈。下一个人重新从1开始报数。
求最后剩下的人的编号。这就是著名的约瑟夫环问题。

本题目就是已知 n，k 的情况下，求最后剩下的人的编号。

题目的输入是一行，2个空格分开的整数n, k
要求输出一个整数，表示最后剩下的人的编号。

约定：0 < n,k < 1百万

例如输入：
10 3

程序应该输出：
4

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗  < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。

提交程序时，注意选择所期望的语言类型和编译器类型。

5. 程序设计（满分71分）

标题：自描述序列

小明在研究一个序列，叫Golomb自描述序列，不妨将其记作{G(n)}。这个序列有2个很有趣的性质:

1. 对于任意正整数n，n在整个序列中恰好出现G(n)次。
2. 这个序列是不下降的。

以下是{G(n)}的前几项：

n         1    2    3    4    5    6    7    8    9    10    11    12    13
G(n)    1    2    2    3    3    4    4    4    5    5      5      6      6

给定一个整数n，你能帮小明算出G(n)的值吗？

输入
----
一个整数n。  

对于30%的数据，1 <= n <= 1000000  
对于70%的数据，1 <= n <= 1000000000  
对于100%的数据，1 <= n <= 2000000000000000  

输出
----
一个整数G(n)

【样例输入】
13

【样例输出】
6

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗  < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。

提交程序时，注意选择所期望的语言类型和编译器类型。

6. 程序设计（满分109分）
标题：采油

LQ公司是世界著名的石油公司，为世界供应优质石油。
最近，LQ公司又在森林里发现了一大片区域的油田，可以在这个油田中开采n个油井。
LQ公司在这n个油井之间修建了n-1条道路，每条道路连接两个油井，路径中间不会路过任何油井，而且这些道路将所有油井连通。
建立油井的时候需要使用一台大型设备，运输起来非常麻烦，LQ公司准备在其中的一个油井位置建立一个空运站，先将设备空运到空运站，之后每次经过他们建立的道路来运输这个大型设备以建立不同的油井，当油井建立完毕后再从空运站将大型设备运走。
为了减少运输的麻烦，公司要求大型设备在道路上运输的总路程是最短的。

在建立油井和采油的过程中需要花费一些人力，第i个油井需要花费Bi个人，而一旦油井建成，就需要Si个人一直坚守在油井上进行维护。
当然，如果一个人参与了油井的建设，他可以直接留下来维护油井，或者参与下一个油井的建设，但是在维护油井的人不能再参加后续油井的建设了。

现在LQ公司想知道，大型设备运输的总路径长度最短是多少？在保证总路径长度最短的情况下，LQ公司至少需要花费多少人力才能完成所有油井的建立与维护。

【输入格式】
　　输入的第一行包含一个整数n，表示油井的数量。油井由1到n依次标号。
　　第二行包含n个整数，依次表示B1, B2, …, Bn，相邻的整数之间用一个空格分隔。
　　第三行包含n个整数，依次表示S1, S2, …, Sn，相邻的整数之间用一个空格分隔。
　　接下来n-1行描述油井之间的道路，其中的第i行包含两个整数a，b，用一个空格分隔，表示一条道路的起点为i+1、终点为a，长度为b，道路是双向的，设备可以从任意一端运送到另一端，每条道路都可以经过任意多次。数据保证任意两个油井之间都可以通过道路连接。

【输出格式】
　　输出包含两个整数，用一个空格分隔，表示最优情况下大型设备需要运输的总路程，以及在总路程最短的情况下最少需要花费的人力数量。

【样例输入】
2
10 20
15 15
1 8

【样例输出】
16 30

【样例说明】
　　有两种方案达到最优。
　　方案一：在油井2建立空运站，先建立油井2，再将大型设备运输到油井1建立油井1，最后将大型设备运回油井2。
　　方案二：在油井1建立空运站，先将大型设备运输到油井2建立油井2，再将大型设备运送到油井1建立油井1。

【样例输入】
6
3 10 20 7 15 9
2 6 10 4 8 7
1 9
1 2
2 5
3 4
3 7

【样例输出】
54 38

【数据规模和约定】
　　对于20%的数据：n不超过10；
　　另外20%的数据：每个油井最多和两个油井之间有道路直接连接；
　　另外10%的数据：有n-1个油井只有一条道路与其他油井连接；
　　对于100%的数据：n不超过100000，B、S、c均为不超过10000的正整数。

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗  < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。

提交程序时，注意选择所期望的语言类型和编译器类型。
 

题目结构

第一题 三角形面积

• 题面

  已知三角形三个顶点在直角坐标系下的坐标分别为：
  (2.3, 2.5)
  (6.4, 3.1)
  (5.1, 7.2)
  求该三角形的面积。

  输出

  要求精确到小数后3位，如不足3位，需要补零。

• 解题思路

  两种做法，一种是海伦公式：$S=sqrt(p\times (p-a)\times (p-b)\times (p-c))$，其中$p=\frac{a+b+c}{2}$；还有一种是叉积公式：$S=\frac{1}{2}\times |x_1{y}_2-x_2{y}_1|$。

• 代码

/**
  *@filename:三角形面积
  *@author: pursuit
  *@csdn:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-05-07 21:39
**/
#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef pair<double,double> pdd;
typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;

pdd points[3];
double dist(pdd a,pdd b){
    return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y)); 
}
void solve(){
    //已知三条边计算三角形的面积，可以利用海伦公式，也可以使用叉积公式。
    //海伦公式：S=sqrt(p*(p-a)*(p-b)*(p-c))，其中p=(a+b+c)/2
    double a=dist(points[0],points[1]),b=dist(points[1],points[2]),c=dist(points[0],points[2]);
    double p=(a+b+c)/2;
    printf("%.03f\n",sqrt(p*(p-a)*(p-b)*(p-c)));
    //叉积公式
    printf("%.03f\n",0.5*abs((points[1].x-points[0].x)*(points[2].y-points[0].y)-(points[1].y-points[0].y)*(points[2].x-points[0].x)));
    //8.795

}
int main(){
    for(int i=0;i<3;i++){
        cin>>points[i].x>>points[i].y;
    }
    solve();
    return 0;
}

• 答案

  $8.795$

第二题 阅兵方阵

• 题面

  x国要参加同盟阅兵活动。
  主办方要求每个加盟国派出的士兵恰好能组成 2 个方阵。
  x国发现弱小的 y国派出了130人的队伍，他们的士兵在行进中可以变换2种队形：
  130 = 81 + 49 = 9^2 + 7^2
  130 = 121 + 9 = 11^2 + 3^2
  x国君很受刺激，觉得x国面积是y国的6倍，理应变出更多队形。
  于是他发号施令：
  我们要派出一支队伍，在行进中要变出 12 种队形！！！
  手下人可惨了，要忙着计算至少多少人才能组成 12 种不同的双方阵。
  请你利用计算机的优势来计算一下，至少需要多少士兵。

  输出

  输出一个整数表示答案

• 解题思路

  暴力枚举即可。

• 代码

/**
  *@filename:阅兵方阵
  *@author: pursuit
  *@csdn:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-05-07 21:56
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;

//要求士兵能恰好组成两个方阵。不一样恰好是两种队形，暴力枚举即可。对于出现过的标记即可。
int a[maxn];
void init(){
    for(int i=1;i<1000;i++){
        a[i]=i*i;
    }
}
int check(int x){
    int ans=0;
    for(int i=1;a[i]*2<=x;i++){
        int temp=sqrt(x-a[i]);
        if(temp*temp==x-a[i]){
            ans++;
        }
    }
    return ans;
}
void solve(){
    init();
    for(int i=1;;i++){
        if(check(i)==12){
            cout<<i<<endl;//160225
            break;
        }
    }
}
int main(){
    solve();
    return 0;
}

• 答案

  $160225$

第三题 找假币

• 题面

  在8枚硬币中，有1枚假币，假币外观与真币一模一样，只是重量略轻或略重一点。 给你一架天平，要求最多称3次，就找出假币，并且知道它是重一些还是轻一些。 下面的代码给出一个解决方案，仔细分析逻辑，填写划线位置缺少的代码。

  #include<bits/stdc++.h>
  
  //判断天平两边哪边重。
  int balance(int a, int b)
  {
      if(a<b) return -1;
      if(a>b) return 1;
      return 0;
  }
  
  void judge(char* data, int a, int b, int std)
  {
      //judge判断并输出相关信息。
      switch(balance(data[a],data[std])){
          case -1:printf("%d light\n", a);break;
          case 0:printf("%d heavy\n", b);break;
          case 1:printf("err!\n", b);break;
      }
  }
  
  // data 中8个元素，有一个假币，或轻或重
  void f(char* data)
  {
      //易知这里也是一个比较的地方。
      //switch( ____________________________________ ){ // 填空
      switch(balance(data[0]+data[1]+data[2],data[3]+data[4]+data[5])){ // 填空
          case -1:
              //如果为-1，说明左边小于右边。那么我们需要交叉组合判断。
              switch(balance(data[0]+data[4],data[3]+data[1])){
                  case -1:judge(data,0,3,1);break;//如果左边小于右边。
                  case 0:judge(data,2,5,0);break;//如果相等，说明假币只可能在2和5之中。判断即可。
                  case 1:judge(data,1,4,0);
              }
          break;
          case 0:judge(data,6,7,0);break;//相等，说明只可能在6和7中出现。0是比较值，说明之前的实际上在判断除了6,7之外的。
          case 1:
              switch(balance(data[0]+data[4],data[3]+data[1])){
                  case -1:judge(data,4,1,0);break;
                  case 0:judge(data,5,2,0);break;
                  case 1:judge(data,3,0,1);
              }
          break;
      }
  }
  
  int main()
  {
      int n;
      char buf[100];
      scanf("%d", &n);
      gets(buf);//gets被删除了。
      int i;
      for(i=0; i<n; i++){
          gets(buf);
          f(buf);
      }
      return 0;
  }
  

• 解题思路

  上述代码已贴详细分析思路。

• 答案

  balance(data[0]+data[1]+data[2],data[3]+data[4]+data[5])

第四题 约瑟夫环

• 题面

  n 个人的编号是 1~n，如果他们依编号按顺时针排成一个圆圈，从编号是1的人开始顺时针报数。
  报数是从1报起，当报到 k 的时候，这个人就退出游戏圈。下一个人重新从1开始报数。
  求最后剩下的人的编号。这就是著名的约瑟夫环问题。
  本题目就是已知 n，k 的情况下，求最后剩下的人的编号。

  输入

  输入两个整数n,k(0<n,k<10^6)

  输出

  要求输出一个整数，表示最后剩下的人的编号。

  样例输入

  10 3
  

  样例输出

  4
  

• 解题思路

  这题应该是递推模板题了吧。为了方便处理，我们假设编号从$0$开始，那我们来简单分析一下，对于$n=1$的时候，那么自然存活的就是$0$,而如果$n=2$，那么就会先排掉轮了第$k$个人的时候，也就是$k\%i$，那么最后剩下的那个实际上就是$(f[n-1]+k)\%n$，因为编号变了。同理这样一直往后，得到递推式$f[n]=(f[n-1]+k)\%n$。故此题易解。

• 代码

/**
  *@filename:约瑟夫环
  *@author: pursuit
  *@csdn:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-05-08 16:33
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1000000 + 5;
const int mod = 1e9+7;

int n,k;
int f[maxn];
void solve(){
    f[1]=0;
    for(int i=2;i<=n;i++){
        f[i]=(f[i-1]+k)%i;
    }
    cout<<f[n]+1<<endl;
}
int main(){
    cin>>n>>k;
    solve();
    return 0;
}

第五题 自描述序列

• 题面

  小明在研究一个序列，叫Golomb自描述序列，不妨将其记作{G(n)}。这个序列有2个很有趣的性质:

  \1. 对于任意正整数n，n在整个序列中恰好出现G(n)次。
  \2. 这个序列是不下降的。
  以下是{G(n)}的前几项：
  n 1 2 3 4 5 6 7 8 9 10 11 12 13
  G(n) 1 2 2 3 3 4 4 4 5 5 5 6 6
  给定一个整数n，你能帮小明算出G(n)的值吗？

  输入

  输入存在多组数据，对于每组测试数据，输入一行包含一个整数n
  (1<=n<=2000000000000000)

  输出

  对于每组测试数据，输出一个整数表示答案。

  样例输入

  13
  

  样例输出

  6
  

• 解题思路

  首先我们需要知道在$G$中有$g[i]$个$i$，所以我们可以利用这个先求出$1e6$的$g[i]$，这样就可以推出$1e6$的所有要迭代的次数。我们利用跟求前缀的思想一样不断迭代到$n$。这样就可以求出$G(n)$。

• 代码

/**
  *@filename:自描述序列
  *@author: pursuit
  *@csdn:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-05-09 12:27
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1000000 + 5;
const int mod = 1e9+7;

ll n,g[maxn];
//在g数组中有g[i]个i。利用这个求前缀和就可以达到目的。
void init(){
    g[1]=1,g[2]=2;
    for(int i=2,j=2;i<maxn;i++){
        for(int k=0;k<g[i]&&j<maxn;k++)g[j++]=i;
    }
}
void solve(){
    ll s,t;
    s=t=0;
    for(ll i=1;;i++){
        s+=i*g[i];//过渡完直接跳到下一个。
        if(s>=n){
            //说明当前已经过了n。
            s-=i*g[i];//先减掉当前加过头的。
            cout<<t+(n-s+i-1)/i<<endl;//t为当前开头的值。
            break;
        }
        t+=g[i];//t获取的就是每次出现的值。
    }
}
int main(){
    init();
    while(cin>>n)
        solve();
    return 0;
}

第六题 采油

• 题面

  LQ公司是世界著名的石油公司，为世界供应优质石油。
  最近，LQ公司又在森林里发现了一大片区域的油田，可以在这个油田中开采n个油井
  LQ公司在这n个油井之间修建了n-1条道路，每条道路连接两个油井，路径中间不会路过任何油井，而且这些道路将所有油井连通。
  建立油井的时候需要使用一台大型设备，运输起来非常麻烦。LQ公司准备在其中的一个油井位置建立一个空运站。
  先将设备空运到空运站，之后每次经过他们建立的道路来运输这个大型设备以建立不同的油井，当油井建立完毕后再从空运站将大型设备运走。
  为了减少运输的麻烦，公司要求大型设备在道路上运输的总路程是最短的。
  在建立油井和采油的过程中需要花费一些人力，第i个油井需要花费Bi个人，而一旦油井建成，就需要Si个人一直坚守在油井上进行维护。
  当然，如果一个人参与了油井的建设，他可以直接留下来维护油井，或者参与下一个油井的建设，但是在维护油井的人不能再参加后续油井的建设了。
  现在LQ公司想知道，大型设备运输的总路径长度最短是多少？
  在保证总路径长度最短的情况下，LQ公司至少需要花费多少人力才能完成所有油井的建立与维护。

  输入

  第一行包含一个整数n，表示油井的数量。油井由1到n依次标号。
  第二行包含n个整数，依次表示B1, B2, …, Bn，相邻的整数之间用一个空格分隔。
  第三行包含n个整数，依次表示S1, S2, …, Sn，相邻的整数之间用一个空格分隔。
  接下来n-1行描述油井之间的道路，其中的第i行包含两个整数a，b，用一个空格分隔。
  表示一条道路的起点为i+1、终点为a，长度为b，道路是双向的，设备可以从任意一端运送到另一端，每条道路都可以经过任意多次。
  数据保证任意两个油井之间都可以通过道路连接。

  n不超过100000，B、S、c均为不超过10000的正整数。

  输出

  输出包含两个整数，用一个空格分隔。
  表示最优情况下大型设备需要运输的总路程，以及在总路程最短的情况下最少需要花费的人力数量。

  样例输入

  2
  10 20
  15 15
  1 8
  

  样例输出

  16 30
  

  提示

  有两种方案达到最优。
  方案一：在油井2建立空运站，先建立油井2，再将大型设备运输到油井1建立油井1，最后将大型设备运回油井2。
  方案二：在油井1建立空运站，先将大型设备运输到油井2建立油井2，再将大型设备运送到油井1建立油井1。

• 解题思路

  暂时不会，待补。

1.网友年龄

某君新认识一网友。
当问及年龄时，他的网友说：
我的年龄是个2位数，我比儿子大27岁,
如果把我的年龄的两位数字交换位置，刚好就是我儿子的年龄”

请你计算：网友的年龄一共有多少种可能情况？

提示：30岁就是其中一种可能哦.

请填写表示可能情况的种数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

#include<stdio.h>

int main()
{
    int age = 2;
    int num = 0;
    for (age = 2; age < 73; age++)
    {
        if ((age % 10 * 10 + age / 10)==age+27)
        {
            num++;
            //printf("age=%2d,age+27=%2d\n", age, age + 27);
        }
    }
    printf("%d\n", num);
    return 0;
}

2.生日蜡烛

某君从某年开始每年都举办一次生日party，并且每次都要吹熄与年龄相同根数的蜡烛。

现在算起来，他一共吹熄了236根蜡烛。

请问，他从多少岁开始过生日party的？

请填写他开始过生日party的年龄数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。 

int main()
{
	int age = 1;
	int count = 0;
	for (age = 1;age<236; age++)
	{
		int num = 236;
		count = age;
		int n = 0;
		while (num > n)
		{
			n += count;
			count++;
		}
		if (n == num)
		{
			printf("%d\n", age);
		}
	}
	return 0;
}

3.方格填数

如下的10个格子
   +--+--+--+
   |  |  |  |
+--+--+--+--+
|  |  |  |  |
+--+--+--+--+
|  |  |  |
+--+--+--+

（如果显示有问题，也可以参看【图1.jpg】）

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

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

请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

思路就是用递归对每个方格进行遍历，再进行判断。递归的时候for循环的控制变量一定不能用全局变量 。

#include<stdio.h>
#include<math.h>

int ans = 0;
int my_arr[10] = { 0 };
int arr[10] = { 0 };
int visit[3][4] = { 0 };
int count = 0;
int dir[8][2] = { 0, -1, 0, 1, 1, 0, -1, 0, 1, 1, 1, -1, -1, -1, -1, 1 };
//表示周围的位置

int judge(const int x,const int y)
{
	int i = 0;
	int tx = 0;
	int ty = 0;
	for (i = 0; i < 8; i++)
	{
		tx = x + dir[i][0];
		ty = y + dir[i][1];
		if ((tx<0) || (tx>2) || (ty<0) || (ty>3))
		{
			continue;
		}
		if (visit[tx][ty] == -10)
		{
			continue;
		}
		if (abs(visit[tx][ty] - visit[x][y] == 1))
		{
			return 0;
		}
	}
	return 1;
}

void slove()
{
	int i = 0;
	int j = 0;
	int n = 0;
	for (i = 0; i < 3; i++)
	{
		for (j = 0; j < 4; j++)
		{
			if ((i == 0 && j == 0) || (i == 2 && j == 3))
			{
				visit[i][j] = -10;
			}
			else
			{
				visit[i][j] = arr[n];
				n++;
			}
		}
	}
	for (i = 0; i < 3; i++)
	{
		for (j = 0; j < 4; j++)
		{
			if ((i == 0 && j == 0) || (i == 2 && j == 3))
			{
				continue;
			}
			else
			{
				if (!judge(i,j))
				{
					return;
				}
			}
		}
	}
	ans++;
}


void dfs(int index)
{
	if (index == 10)
	{
		slove();
		return;
	}
	else
	{
		int i = 0;
		for (i = 0; i <= 9; i++)
		{
			if (!my_arr[i])
			{
				my_arr[i] = 1;
				arr[count] = i;
				count++;
				dfs(index + 1);
				arr[count] = 0;
				count--;
				my_arr[i] = 0;
			}
		}
	}
}

int main()
{
	dfs(0);
	printf("%d", ans);
	return 0;
}

4.快速排序

排序在各种场合经常被用到。
快速排序是十分常用的高效率的算法。
其思想是：先选一个“标尺”，
用它把整个队列过一遍筛子，
以保证：其左边的元素都不大于它，其右边的元素都不小于它。
这样，排序问题就被分割为两个子区间。
再分别对子区间排序就可以了。
下面的代码是一种实现，请分析并填写划线部分缺少的代码。

#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);
    }
    //______________________;
    swap(a, p, 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[] = { 5, 13, 6, 24, 2, 8, 19, 27, 6, 12, 1, 17 };
    int N = 12;

    quicksort(a, 0, N - 1);

    for (i = 0; i<N; i++) printf("%d ", a[i]);
    printf("\n");

    return 0;
}

5.消除尾一

下面的代码把一个整数的二进制表示的最右边的连续的1全部变成0
如果最后一位是0，则原数字保持不变。

如果采用代码中的测试数据，应该输出：
00000000000000000000000001100111   00000000000000000000000001100000
00000000000000000000000000001100   00000000000000000000000000001100

请仔细阅读程序，填写划线部分缺少的代码。

#include <stdio.h>

void f(int x)
{
    int i;
    for (i = 0; i<32; i++) printf("%d", (x >> (31 - i)) & 1);
    printf("   ");

    //x = _______________________;
    x = x&(x+1);
    for (i = 0; i<32; i++) printf("%d", (x >> (31 - i)) & 1);
    printf("\n");
}

int main()
{
    f(103);
    f(12);
    return 0;
}

6.寒假作业

现在小学的数学题目也不是那么好玩的。
看看这个寒假作业：

   □ + □ = □
   □ - □ = □
   □ × □ = □
   □ ÷ □ = □
   
   (如果显示不出来，可以参见【图1.jpg】)
   
每个方块代表1~13中的某一个数字，但不能重复。
比如：
 6  + 7 = 13
 9  - 8 = 1
 3  * 4 = 12
 10 / 2 = 5

以及： 
 7  + 6 = 13
 9  - 8 = 1
 3  * 4 = 12
 10 / 2 = 5

就算两种解法。（加法，乘法交换律后算不同的方案）
 
你一共找到了多少种方案？
当时想这个题的时候，没想到那些简单点的算法，只想遍历解决一遍，可能代码看上去会有那么一点不精简。。

#include<stdio.h>

void bianli(int* a)
{
	int i = 0;
	for (i = 0; i <= 13; i++)
	{
		a[i] = 1;
	}
}
int main()
{
	int add = 0;
	int sub = 0;
	int mul= 0;
	int div = 0;
	int count = 0;
	int i = 0;
	int j = 0;
	int m = 0;
	int n = 0;
	for (add =1; add <= 13; add++)
	{
		int a[14] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
		for (i = 1; i <= 13-add; i++)
		{
			bianli(a);
			a[add] = 0;
			if ((a[i] != 1) || (a[add+i]!=1))
			{
				continue;
			}
			for (sub = 13; sub >0; sub--)
			{
				bianli(a);
				a[add] = 0;
				a[i] = 0;
				a[add + i] = 0;
				if (a[sub]!= 1)
				{
					continue;
				}
				for (j = 1; j <sub; j++)
				{
					bianli(a);
					a[add] = 0;
					a[i] = 0;
					a[add + i] = 0;
					a[sub] = 0;
					if (a[j] != 1)
					{
						continue;
					}
					a[j] = 0;
					if (a[sub - j] != 1)
					{
						continue;
					}
					for (mul = 1; mul <= 13; mul++)
					{
						bianli(a);
						a[add] = 0;
						a[i] = 0;
						a[add + i] = 0;
						a[sub] = 0;
						a[j] = 0;
						a[sub - j] = 0;
						if (a[mul] != 1)
						{
							continue;
						}
						for (m = 1; m <= (13/mul); m++)
						{
							bianli(a);
							a[add] = 0;
							a[i] = 0;
							a[add + i] = 0;
							a[sub] = 0;
							a[j] = 0;
							a[sub - j] = 0;
							a[mul] = 0;
							if (a[m] != 1) 
							{
								continue;
							}
							a[m] = 0;
							if  (a[m*mul] != 1)
							{
								continue;
							}
							for (div = 13; div > 0; div--)
							{
								bianli(a);
								a[add] = 0;
								a[i] = 0;
								a[add + i] = 0;
								a[sub] = 0;
								a[j] = 0;
								a[sub - j] = 0;
								a[m] = 0;
								a[mul] = 0;
								a[m*mul] = 0;
								if (a[div] != 1)
								{
									continue;
								}
								a[div] = 0;
								for (n = 1; n < div; n++)
								{
									bianli(a);
									a[add] = 0;
									a[i] = 0;
									a[add + i] = 0;
									a[sub] = 0;
									a[j] = 0;
									a[sub - j] = 0;
									a[m] = 0;
									a[mul] = 0;
									a[m*mul] = 0;
									a[div] = 0;
									if ((div%n )!= 0)
									{
										continue;
									}
									if (a[n] != 1)
									{
										continue;
									}
									a[n] = 0;
									if (a[div/n] != 1)
									{
										continue;
									}
									count++;
									//printf("%d+%d=%d\n", add, i, add + i);
									//printf("%d-%d=%d\n", sub, j, sub-j);
									//printf("%d*%d=%d\n", mul, m, mul*m);
									//printf("%d/%d=%d\n", div, n, div/n);
									//printf("\n");
								}
							}
						}
					}
				}
			}
		}
	}
	printf("%d\n", count);
	return 0;
} 

7.剪邮票

如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。

请你计算，一共有多少种不同的剪取方法。

请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

递推实现： 

#include<stdio.h>
#include<string.h>

int mip[3][4] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
int count = 0;
int have[13] = { 0 };//记录五个邮票的位置
int visit[3][4] = { 0 };//判断该邮票是否已经符合
int dir[4][2] = { 0, 1, 0, -1, 1, 0, -1, 0 };
//当前邮票的上下左右位置

void find(const int x, const int y)
{
	int i = 0;
	int tx, ty;
	for (i = 0; i<4; i++)
	{
		tx = x + dir[i][0];
		ty = y + dir[i][1];
		if ((tx<0) || (tx >= 3) || (ty<0) || (ty >= 4))
		{
			continue;
		}
		if ((have[mip[tx][ty]] == 0)|| visit[tx][ty])
        //如果该位置没有邮票或者已经判断过了，就跳出
		{
			continue;
		}
		visit[tx][ty] = 1;
		count++;
		find(tx, ty);
	}
}

int slove(const int i, const int j, const int k, const int m, const int n)
{
	count = 0;
	memset(have, 0, sizeof(have));
	int a[5] = { i, j, k, m, n };
	memset(visit, 0, sizeof(visit));
	int num = 0;
	for (num = 0; num<5; num++)
	{
		have[a[num]] = 1;
	}
	int x, y;
	x = i / 4;
	y = i % 4-1;
	if (i % 4 == 0)
	{
		x -= 1;
		y = 3;
	}
	count = 1;
	visit[x][y] = 1;
	find(x, y);
	if (count == 5)
	{
		return 1;
	}
	return 0;
}

int main()
{
	int i = 0;
	int j = 0;
	int k = 0;
	int m = 0;
	int n = 0;
	int ans = 0;
	for (i = 1; i<9; i++)
	{
		for (j = i + 1; j<10; j++)
		{
			for (k = j + 1; k<11; k++)
			{
				for (m = k + 1; m<12; m++)
				{
					for (n = m + 1; n<13; n++)
					{
						if (slove(i, j, k, m, n))
						{
							ans++;
							//printf("%d %d %d %d %d\n", i, j, k, m, n);
						}
					}
				}
			}
		}
	}
	printf("%d", ans);
	return 0;
}

8.四平方和

四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多4个正整数的平方和。
如果把0包括进去，就正好可以表示为4个数的平方和。

比如：
5 = 0^2 + 0^2 + 1^2 + 2^2
7 = 1^2 + 1^2 + 1^2 + 2^2
（^符号表示乘方的意思）

对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对4个数排序：
0 <= a <= b <= c <= d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法

程序输入为一个正整数N (N<5000000)
要求输出4个非负整数，按从小到大排序，中间用空格分开

例如，输入：
5
则程序应该输出：
0 0 1 2

再例如，输入：
12
则程序应该输出：
0 2 2 2

再例如，输入：
773535
则程序应该输出：
1 1 267 838

资源约定：
峰值内存消耗 < 256M
CPU消耗  < 3000ms

#include<stdio.h>
#include<math.h>


int main()
{
	int num = 0;
	int count = 0;
	int i = 0;
	scanf("%d", &num);
	int i1 = 0, i2 = 0, i3 = 0;
	int x1 = sqrt(num / 4) + 1;
	int x2 = sqrt(num / 3) + 1;
	int x3 = sqrt(num / 2) + 1;
	for (i1 = 0; i1 <= x1; i1++)
	{
		for (i2 = i1; i2 <= x2; i2++)
		{
			for (i3 = i2; i3 <= x3; i3++)
			{
				int x4 = num - i1*i1 - i2*i2 - i3*i3;
				if (x4 == (int)sqrt(x4)*(int)sqrt(x4) && (int)sqrt(x4)>=x3)
				{
					printf("%d %d %d %d\n", i1, i2, i3, (int)sqrt(x4));
					exit();
				}
			}
		}
	}
	return 0;
} 

9.密码脱落(放弃)

X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。

你的任务是：
给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。

输入一行，表示现在看到的密码串（长度不大于1000）
要求输出一个正整数，表示至少脱落了多少个种子。

例如，输入：
ABCBA
则程序应该输出：
0

再例如，输入：
ABDCDCBABC
则程序应该输出：
3

资源约定：
峰值内存消耗 < 256M
CPU消耗  < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

10.最大比例(放弃)

X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。
并且，相邻的两个级别间的比例是个固定值。
也就是说：所有级别的奖金数构成了一个等比数列。比如：
16,24,36,54
其等比值为：3/2

现在，我们随机调查了一些获奖者的奖金数。
请你据此推算可能的最大的等比值。

输入格式：
第一行为数字 N (0<N<100)，表示接下的一行包含N个正整数
第二行N个正整数Xi(Xi<1 000 000 000 000)，用空格分开。每个整数表示调查到的某人的奖金数额

要求输出：
一个形如A/B的分数，要求A、B互质。表示可能的最大比例系数

测试数据保证了输入格式正确，并且最大比例是存在的。

例如，输入：
3
1250 200 32

程序应该输出：
25/4

再例如，输入：
4
3125 32 32 200

程序应该输出：
5/2

再例如，输入：
3
549755813888 524288 2

程序应该输出：
4/1

资源约定：
峰值内存消耗 < 256M
CPU消耗  < 3000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码