蓝桥杯算法特训第七课【图】源代码

【内容简介】
本文章内容为【2018蓝桥杯大赛算法特训(软件)系列课程】第七课【图】中涉及到的课上例题的代码实现,加入赛前算法特训获取全部课程内容请联系【小蓝】。


【课程中涉及的源代码】
1. 连通性

给定一个方阵,定义连通:上下左右相邻,并且值相同。
可以想象成一张地图,不同的区域被涂以不同颜色。
输入:
整数N, (N<50)表示矩阵的行列数
接下来N行,每行N个字符,代表方阵中的元素
接下来一个整数M,(M<1000)表示询问数
接下来M行,每行代表一个询问,
格式为4个整数,y1,x1,y2,x2,
表示(第y1行,第x1列) 与 (第y2行,第x2列) 是否连通。
连通输出true,否则false

例如:
10
0010000000
0011100000
0000111110
0001100010
1111010010
0000010010
0000010011
0111111000
0000010000
0000000000
3
0 0 9 9
0 2 6 8
4 4 4 6

程序应该输出:
false
true
true

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.*;
public class A
{
  static boolean lian_tong(char[][] data, int y1, int x1, int y2, int x2){
    if(y1==y2 && x1==x2) return true;
    char old = data[y1][x1];
    data[y1][x1]='*';
    try{
      if(y1>0 && data[y1-1][x1]==old && lian_tong(data,y1-1,x1,y2,x2)) return true;
      if(y1<data.length-1 && data[y1+1][x1]==old && lian_tong(data,y1+1,x1,y2,x2)) return true; if(x1>0 && data[y1][x1-1]==old && lian_tong(data,y1,x1-1,y2,x2)) return true;
      if(x1<data.length-1 && data[y1][x1+1]==old && lian_tong(data,y1,x1+1,y2,x2)) return true;
    }
    finally{
      data[y1][x1] = old;
    }
    return false;
  }
 
  public static void main(String[] args){
    Scanner  scan = new Scanner(System.in);
   
    int n = Integer.parseInt(scan.nextLine());
    char[][] data = new char[n][];
    for(int i=0; i<n; i++){
      data[i] = scan.nextLine().toCharArray();
    }
   
    int m = Integer.parseInt(scan.nextLine());
    for(int i=0; i<m; i++){
      String[] ss = scan.nextLine().split(" ");
      int y1 = Integer.parseInt(ss[0]);
      int x1 = Integer.parseInt(ss[1]);
      int y2 = Integer.parseInt(ss[2]);
      int x2 = Integer.parseInt(ss[3]);
     
      System.out.println(lian_tong(data,y1,x1,y2,x2));
    }
  }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int lian_tong(char* data[],int len, int y1, int x1, int y2, int x2)
{
    if (y1 == y2 && x1 == x2)
      return 1;
    char old = data[y1][x1];
    data[y1][x1] = '*';
    if (y1 > 0 && data[y1 - 1][x1] == old && lian_tong(data, len, y1 - 1, x1, y2, x2))
    {
      data[y1][x1] = old;
      return 1;
    }
     
    if (y1<len - 1 && data[y1 + 1][x1] == old && lian_tong(data, len,y1 + 1, x1, y2, x2)) { data[y1][x1] = old; return 1; } if (x1>0 && data[y1][x1 - 1] == old && lian_tong(data, len, y1, x1 - 1, y2, x2)) {
      data[y1][x1] = old;
      return 1;
    }
    if (x1 < len - 1 && data[y1][x1 + 1] == old && lian_tong(data, len,y1, x1 + 1, y2, x2))
    {
      data[y1][x1] = old;
      return 1;
    }
  data[y1][x1] = old;
  return 0;
}


void main1()
{
 
  /*int len = 0;
  scanf("%d", &len);
  char* *data = (char**)malloc(len*sizeof(char*));
  for (int i = 0; i < len; i++)
  {
  data[i] = (char*)malloc(len);
  memset(data[i], 0, len);
  scanf("%s", data[i]);
  }*/


  FILE*fp1 = fopen("1.txt", "r");

  int len = 0;
  char arr[10] = { 0 };  
  fgets(arr, 10, fp1);
  len=atoi(arr);
  printf("%d\n\n", len);

  char* *data = (char**)malloc(len*sizeof(char*));
  for (int i = 0; i < len; i++)
  {
    data[i] = (char*)malloc(len+2);
    memset(data[i], 0, len+2);
    char *pp = data[i];
    fgets(data[i], len+2, fp1);
    printf("%s", data[i]);
  }
  fclose(fp1);

  int m = 0;
  scanf("%d", &m);
  for (int i = 0; i < m; i++) { char arr[1024] = { 0 }; char c; fflush(stdin); //while ((c = getchar()) != EOF && c != '\n');//不停地使用getchar()获取缓冲中字符,直到获取的c是“\n”或文件结尾符EOF为止 gets(arr); int shu[4] = { 0 }; int f1 = 0; int tail = 0; int f2 = 0; int flag = 1; while (flag>=0)
    {
      if (arr[f1] != ' '&&arr[f1] != '\0')
      {
        tail++;
      }
      else
      {
        char mp[1024] = { 0 };
        strncpy(mp, arr+f1-tail,tail);
        shu[f2] = atoi(mp);
        f2++;
        tail = 0;
      }      
      f1++;
      if (arr[f1] == '\0')
      {
        flag--;
      }
    }
    int x=lian_tong(data, len, shu[0], shu[1], shu[2], shu[3]);
    printf("%s\n", x ? "true" : "false");
  }
}


2. 迷宫问题
…11111111111111111111111111111
11.111111……..1111111111.1111
11.111111..111.11111111…..1111
11.11111111111.1111111111.111111
11.111111……………..111111
11.111111.11111111111.11111.1111
11.111111.11111111111.11111..111
11……….111111111.11111.1111
11111.111111111111111.11….1111
11111.111111111111111.11.11.1111
11111.111111111111111.11.11.1111
111…111111111111111.11.11.1111
111.11111111111111111….11.1111
111.11111111111111111111111.1111
111.1111.111111111111111……11
111.1111…….111111111.1111.11
111.1111.11111.111111111.1111.11
111……11111.111111111.1111111
11111111111111.111111111.111…1
11111111111111……………1.1
111111111111111111111111111111..

如上图的迷宫,入口,出口分别:左上角,右下角
“1”是墙壁,”.”是通路
求最短需要走多少步?

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.*;

public class A
{
  // from: 出发位置  goal: 目标位置
  static int f(char[][] data, Set from, String goal){
    if(from.contains(goal)) return 0; // 起点与终点重合,需要0步
   
    Set set = new HashSet(); // 找到from的相邻连通点
   
    for(Object obj: from){
      String[] ss = ((String)obj).split(",");
      int y = Integer.parseInt(ss[0]);
      int x = Integer.parseInt(ss[1]);
     
      if(y>0 && data[y-1][x]=='.'){ data[y-1][x] = '*'; set.add(y-1+","+x); }
      if(y<data.length-1 && data[y+1][x]=='.'){ data[y+1][x] = '*'; set.add(y+1+","+x); } if(x>0 && data[y][x-1]=='.'){ data[y][x-1] = '*'; set.add(y+","+(x-1)); }
      if(x<data[0].length-1 && data[y][x+1]=='.'){ data[y][x+1] = '*'; set.add(y+","+(x+1)); }
    }
   
    if(set.isEmpty()) return -1;
    int r = f(data, set, goal);
    if(r<0) return -1;
    return r + 1;
  }
 
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
   
    String[] ss = scan.nextLine().trim().split(" +");
    int n = Integer.parseInt(ss[0]);
    int m = Integer.parseInt(ss[1]);
   
    char[][] data = new char[n][];
    for(int i=0; i<n; i++){
      data[i] = scan.nextLine().trim().toCharArray();
    }
   
    Set set = new HashSet();
    set.add("0,0");
    System.out.println(f(data, set, n-1 + "," + (m-1)));
  }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//list.h
#ifndef LIST_H
#define LIST_H

#include <stdlib.h>

//定义基础的结构
typedef struct ListElmt_{
  void *data;
  struct ListElmt_ *next;
}ListElmt;

//定义列表
typedef struct list_{
  int size;//大小
  int(*match)(const void *key1, const void *key2);//比较,匹配
  void(*destroy)(void *data);//内存释放函数
  ListElmt *head;//头
  ListElmt *tail;//尾部
}List;

//初始化
void list_init(List *list, void(*destroy)(void *data));
//在element元素后插入一个元素,如果element为空,则插入链表头部
int list_ins_next(List *list, ListElmt *element, const void *data);
//删除element后面的那个元素,如果element为空,则删除链表头元素
int list_rem_next(List *list, ListElmt *element, void **data);
//删除一个列表,删除列表里面存储的data
void list_destroy(List *list);


//定义基础的宏,获取各种基础的数据:获取大小,头,尾部,判断是头,是尾,数据,下一个元素
#define list_size(list) ((list)->size)
#define list_head(list) ((list)->head)
#define list_tail(list) ((list)->tail)
#define list_is_head(list,element) ((element) == (list)->head?1:0)
#define list_is_tail(element) ((element)->next == NULL?1:0)
#define list_data(element)((element)->data)
#define list_next(element)((element)->next)

#endif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//list.c
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#include "list.h"


void list_init(List *list, void(*destroy)(void *data)){
  list->size = 0;

  list->destroy = destroy;
  list->head = list->tail = NULL;
  return;
}


//在element元素后插入一个元素,
//如果element为空,则插入链表头部
//需要考虑链表为空的情况
int list_ins_next(List *list, ListElmt *element, const void *data){
  //创建新数据
  ListElmt *new_element;
  if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL)
    return -1;
  new_element->data = (void *)data;
  new_element->next = NULL;
  //如果选定数据为空,插入到表头
  if (element == NULL){
    //如果列表为空,尾部也指向新元素
    if (list_size(list) == 0)
      list->tail = new_element;
    //在头链表前插入
    new_element->next = list->head;
    list->head = new_element;
  }
  else{
    //如果是最后一个元素
    if (element->next == NULL)
      list->tail = new_element;
    //在元素后插入
    new_element->next = element->next;
    element->next = new_element;
  }
  list->size++;
  return 0;
}

//删除element后面的那个元素
//如果element为空,则删除链表头元素
int list_rem_next(List *list, ListElmt *element, void **data){

  //队列不为空
  if (list_size(list) == 0){
    return -1;
  }
  ListElmt *old_element;

  if (element == NULL){
    //头部删除一个元素
    *data = list->head->data;
    old_element = list->head;

    list->head = list->head->next;
    if (list_size(list) == 1) {
      list->tail = NULL;
    }
  }
  else{
    //尾部删除一个元素
    if (element->next == NULL){
      return -1;
    }
    *data = element->next->data;
    old_element = element->next;
    element->next = element->next->next;
    if (element->next == NULL){
      list->tail = element;
    }
  }
  free(old_element);
  list->size--;
  return 0;
}


//删除一个列表,删除列表里面存储的data
void list_destroy(List *list){
  void *data;
  while (list_size(list) > 0){
    if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy != NULL){
      list->destroy(data);
    }
  }
  memset(list, 0, sizeof(List));
  return;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//
//  set.h
//  set
//
//  Created by bikang on 16/9/18.
//  Copyright (c) 2016年 bikang. All rights reserved.
//

#ifndef __set__set__
#define __set__set__

#include <stdlib.h>
#include "list.h"

typedef List Set;

void set_init(Set *set, int(*match)(const void *k1, const void *k2), void(*destroy)(void*data));
#define set_destroy list_destroy
//插入
int set_insert(Set *set, const void *data);
//删除
int set_remove(Set *set, void **data);
//并集
int set_union(Set *setu, const Set *set1, const Set *set2);
//交集
int set_intersection(Set *seti, const Set *set1, const Set *set2);
//差集
int set_difference(Set *setd, const Set *set1, const Set *set2);
//是否是他的成员
int set_is_member(const Set *set, const void *data);
//是否是子集
int set_is_subset(const Set *set1, const Set *set2);
//是否相等
int set_is_equal(const Set *set1, const Set *set2);

#define set_size(set) ((set)->size)
#endif /* defined(__set__set__) */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
//  set.c
//  set
//
//  Created by bikang on 16/9/18.
//  Copyright (c) 2016年 bikang. All rights reserved.
//
#include <stdlib.h>
#include <string.h>

#include "set.h"


//初始化集合
void set_init(Set *set, int(*match)(const void *k1, const void *k2), void(*destroy)(void*data))
{
  list_init(set, destroy);
  set->match = match;
  return;
}

//插入数据
int set_insert(Set *set, const void *data)
{
  if (set_is_member(set, data)){
    return 1;
  }
  return list_ins_next(set, list_tail(set), data);
}

//删除数据
int set_remove(Set *set, void **data){

  ListElmt *item, *pre;
  pre = NULL;
  for (item = list_head(set); item != NULL; item = list_next(item)){
    if (set->match(*data, list_data(item))) break;
    pre = item;
  }
  if (item == NULL) return -1;
  return list_rem_next(set, pre, data);
}
//并集
int set_union(Set *setu, const Set *set1, const Set *set2){
  ListElmt *item;
  void *data;
  set_init(setu, set1->match, NULL);
  for (item = list_head(set1); item != NULL; item = list_next(item)){
    data = list_data(item);
    if (list_ins_next(setu, list_tail(setu), data) != 0){
      set_destroy(setu);
      return -1;
    }
  }

  for (item = list_head(set2); item != NULL; item = list_next(item)){
    data = list_data(item);
    if (!set_is_member(setu, list_data(item))){
      if (list_ins_next(setu, list_tail(setu), data) != 0){
        set_destroy(setu);
        return -1;
      }
    }
  }
  return 0;
}

//交集
int set_intersection(Set *seti, const Set *set1, const Set *set2){
  ListElmt *item;
  void *data;
  set_init(seti, set1->match, NULL);

  for (item = list_head(set1); item != NULL; item = list_next(item)){
    if (set_is_member(set2, list_data(item))){
      data = list_data(item);
      if (list_ins_next(seti, list_tail(seti), data) != 0){
        set_destroy(seti);
        return -1;
      }
    }
  }
  return 0;
}

//差集
int set_difference(Set *setd, const Set *set1, const Set *set2){
  ListElmt *item;
  void *data;
  set_init(setd, set1->match, NULL);

  for (item = list_head(set1); item != NULL; item = list_next(item)){
    if (!set_is_member(set2, list_data(item))){
      data = list_data(item);
      if (list_ins_next(setd, list_tail(setd), data) != 0){
        set_destroy(setd);
        return -1;
      }
    }
  }
  return 0;
}


//是否是他的成员
int set_is_member(const Set *set, const void *data){
  ListElmt *item;
  for (item = list_head(set); item != NULL; item = list_next(item)){
    if (set->match(data, list_data(item))) return 1;
  }
  return 0;
}

//set1是否是set2的子集
int set_is_subset(const Set *set1, const Set *set2){
  ListElmt *item;
  // set1
  if (set_size(set1) > set_size(set2)) return 0;
  for (item = list_head(set1); item != NULL; item = list_next(item)){
    if (!set_is_member(set2, list_data(item))) return 0;
  }
  return 1;
}

//是否相等
int set_is_equal(const Set *set1, const Set *set2){
  if (set_size(set1) != set_size(set2)) return 0;

  return set_is_subset(set1, set2);
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "set.h"
#include "list.h"

int match_data(const void *d1, const void *d2){
  if (*(int*)d1 == *(int*)d2) return 1;
  return 0;
}

int f(char* data[],int len, Set from, char* goal)
{
  Set *set2 = (Set*)malloc(sizeof(Set));
  Set *set3 = (Set*)malloc(sizeof(Set));
  set_init(set2, match_data, NULL);
  set_insert(set2, goal);
  if (set_is_subset((const Set *)&from, set2))
    return 0; // 起点与终点重合,需要0步

  set_init(set3, match_data, NULL); // 找到from的相邻连通点

  for (ListElmt *item = list_head(&from); item != NULL; item = list_next(item))
  {


    char*p1=strstr(item->data, ",");
    char akq[10] = { 0 };
    strncpy(akq, item->data, p1 - item->data);
    int y = atoi(akq);
    strcpy(akq, item->data, p1+1);
    int x = atoi(akq);
   
    if (y > 0 && data[y - 1][x] == '.')
    {
      data[y - 1][x] = '*';

      char *buf = (char*)malloc(1024);
      memset(buf, 0, 1024);
      _itoa(y - 1, buf, 10);
      char tmp[1024] = { 0 };
      _itoa(x, tmp, 10);
      strcat(buf, ",");
      strcat(buf, tmp);
      set_insert(set3, buf);
    }
    if (y<len - 1 && data[y + 1][x] == '.') { data[y + 1][x] = '*'; char *buf = (char*)malloc(1024); memset(buf, 0, 1024); _itoa(y + 1, buf, 10); char tmp[1024] = { 0 }; _itoa(x, tmp, 10); strcat(buf, ","); strcat(buf, tmp); set_insert(set3, buf); } if (x>0 && data[y][x - 1] == '.')
    {
      data[y][x - 1] = '*';
     
      char *buf = (char*)malloc(1024);
      memset(buf, 0, 1024);
      _itoa(y, buf, 10);
      char tmp[1024] = { 0 };
      _itoa(x - 1, tmp, 10);
      strcat(buf, ",");
      strcat(buf, tmp);
      set_insert(set3, buf);
    }

    char *pk = data[0];
    int xy=strlen(pk);
    if (x <xy - 1 && data[y][x + 1] == '.')
    {
      data[y][x + 1] = '*';
     
      char *buf = (char*)malloc(1024);
      memset(buf, 0, 1024);
      _itoa(y, buf, 10);
      char tmp[1024] = { 0 };
      _itoa(x + 1, tmp, 10);
      strcat(buf, ",");
      strcat(buf, tmp);
      set_insert(set3, buf);
    }
  }

  if (set_size(set3) == 0)
    return -1;
  int r = f(data, len, *set3, goal);
  if (r < 0)
    return -1;
  return r + 1;
}

void main2()
{
  FILE*fp1 = fopen("2.txt", "r");
  int n[2] = {0};
  int m = 0;
  char arr[10] = { 0 };  
  fgets(arr, 10, fp1);
  char* token = strtok(arr, " ");
  int len = 0;
  while (token != NULL)
  {
    n[len++]=atoi(token);
    token = strtok(NULL, " ");
  }

  char* *data = (char**)malloc(n[0]*sizeof(char*));
  for (int i = 0; i < n[0]; i++)
  {
    data[i] = (char*)malloc(n[1] + 2);
    memset(data[i], 0, n[1] + 2);
    fgets(data[i], n[1]+2, fp1);
    printf("%s", data[i]);
  }
  fclose(fp1);

 
  Set *set1 = (Set*)malloc(sizeof(Set));
  set_init(set1, match_data, NULL);
  char *pi = "0,0";
  set_insert(set1, pi);

  char *buf = (char*)malloc(1024);
  memset(buf, 0, 1024);
  _itoa(n[0] - 1, buf, 10);
  char tmp[1024] = { 0 };
  _itoa(n[1] - 1, tmp, 10);
  strcat(buf, ",");
  strcat(buf, tmp);

  char *ps = f(data, n[0], *set1, buf);
 
}


3. 分酒问题
有4个红酒瓶子,它们的容量分别是:9升, 7升, 4升, 2升
开始的状态是 [9,0,0,0],也就是说:第一个瓶子满着,其它的都空着。

允许把酒从一个瓶子倒入另一个瓶子,但只能把一个瓶子倒满或把一个瓶子倒空,不能有中间状态。
这样的一次倒酒动作称为1次操作。

假设瓶子的容量和初始状态不变,对于给定的目标状态,至少需要多少次操作才能实现?
本题就是要求你编程实现最小操作次数的计算。

输入:最终状态(空格分隔)
输出:最小操作次数(如无法实现,则输出-1)

例如:
输入:
9 0 0 0
应该输出:
0

输入:
6 0 0 3
应该输出:
-1

输入:
7 2 0 0
应该输出:
2

测试用例:
输入:2,4,1,2
输出:6
输入:3,1,3,2
输出:9
输入:2,6,1,0
输出:7

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// 图的节点就是状态,在运行中才产生
import java.util.*;
public class A
{
  // 当前状态的可达集合
  static Set move(String cur){
    int[] cap = {9,7,4,2};
    int[] data = new int[4];
    String[] ss = cur.split(" ");
    for(int i=0; i<4; i++) data[i] = Integer.parseInt(ss[i]);
   
    Set set = new HashSet();
    // 试着从i倒入j
    for(int i=0; i<4; i++)
    for(int j=0; j<4; j++){
      if(j==i) continue;
      if(data[i]==0) continue;  //源空
      if(data[j]==cap[j]) continue; //目标满了
     
      int sum = data[i]+data[j];  
      int vi = (sum <= cap[j])? 0 : sum - cap[j]; // 假如倒酒后,i号的新值
      int vj = (sum <= cap[j])? sum : cap[j];  // 假如倒酒后,j号的新值
 
      //生成新的状态串
      String s = "";
      for(int k=0; k<4; k++){
        if(k==i) s += vi + " ";
        else if(k==j) s += vj + " ";
        else s += data[k] + " ";
      }
     
      set.add(s.trim());
    }
   
    return set;
  }

  static int f(Set hist, Set from, String goal){
    if(from.contains(goal)) return 0;
   
    Set from2 = new HashSet();
    for(Object it: from){
      Set t = move(it.toString());
      from2.addAll(t);
    }
   
    from2.removeAll(hist);
    if(from2.isEmpty()) return -1;
   
    hist.addAll(from2);
    int r = f(hist, from2, goal);
    if(r<0) return r;
    return r + 1;
  }

  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
   
    Set from = new HashSet(); //出发态
    from.add("9 0 0 0");
    Set hist = new HashSet(); //所有历史态
    hist.addAll(from);
   
    System.out.println(f(hist,from,scan.nextLine().trim()));
  }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "set.h"
typedef struct Node
{
  int data[4];
  struct Node *pNext;
}Node;


typedef struct Link
{
  Node * pHeadOfNode;
  struct Link * pNext;
}Link;

//比较数组是否相同,相同返回1,不同返回0;
int cmp(int arr1[4], int len1, int arr2[4], int len2)
{
  if (len1!=len2)
  {
    return 0;
  }

  for (int i = 0; i < len1;i++) { if (arr1[i] != arr2[i]) { return 0; } } return 1; } //遍历链表中的节点,再遍历节点看看是否有于和goal相同的数组;有的话返回1,没有返回0 int contains(Link* from, int goal[4]) { Link*temp = from; while (temp) { Node *tempNode = temp->pHeadOfNode;
    while (tempNode)
    {
      int x=cmp(tempNode->data, 4, goal, 4);
      if (x)
      {
        return 1;
      }
      tempNode = tempNode->pNext;
    }
    temp = temp->pNext;
  }
  return 0;
}

void addAll(Link ** head, Link **temp, Link*p)
{
  if (*head==NULL)
  {
    *head = p;
    *temp = p;
  }
  else
  {
    (*temp)->pNext = p;
    *temp = p;
  }
}
void removeAll(Link *from, Link*hist1)
{

  while (from)
  {
    Node*pNode = from->pHeadOfNode;
    while (pNode)
    {      
          Link*hist = hist1;
          while (hist)
          {
            Node*phistNode = hist1->pHeadOfNode;
            while (phistNode)
            {
              int x=cmp(pNode->data, 4, phistNode->data, 4);
              if (x==1)
              {
                //from2里面的data和hist里面的data相同,则把from2里面的改为0000;
                memset(pNode->data, 0, 4 * sizeof(int));
                goto A;
              }
              phistNode = phistNode->pNext;
            }
            hist = hist->pNext;
          }
      pNode = pNode->pNext;
    }
A:    from = from->pNext;
  }
}



//一组数据,只倒一下,可以由多少张情况。例如9 0 0 0,可以获取多少种情况
Node* move(int cur[], int len)
{
  int cap[] = { 9, 7, 4, 2 };
  int data[4];
  for (int x = 0; x < 4; x++)
  {
    data[x] = cur[x];
  }

  Node* phead = NULL;
  Node* ptail = NULL;
  for (int i = 0; i < 4; i++)
  {
    Node* tep = NULL;
    for (int j = 0; j < 4; j++)
    {
      if (j == i)
        continue;
      if (data[i] == 0)
        continue;  //源空
      if (data[j] == cap[j])
        continue; //目标满了
      int sum = data[i] + data[j];
      int vi = (sum <= cap[j]) ? 0 : sum - cap[j]; // 假如倒酒后,i号的新值
      int vj = (sum <= cap[j]) ? sum : cap[j]; // 假如倒酒后,j号的新值 tep = malloc(1 * sizeof(Node)); tep->pNext = NULL;
      //生成新的状态串
      for (int k = 0; k < 4; k++) { if (k == i) tep->data[i] = vi;
        else if (k == j)
          tep->data[k] = vj;
        else
          tep->data[k] = data[k];
      }
      if (phead == NULL)
      {
        phead = tep;
        ptail = tep;
      }
      else
      {
        ptail->pNext = tep;
        ptail = tep;
      }
    }
   
  }
  return phead;
}


//hist 历史状态,from出发态
int ff(Link* hist, Link* from, int goal[4])
{
  //出发态链表中有索要求得状态时,返回0,表明不需要在进行查找了,本层就包含
  if (contains(from, goal))
  {
    return 0;
  }
  //定义一个由出发态得到的所有状态集合(链表)
  Link* from2=NULL;
  Link* from2tem = NULL;
  //遍历出发态,得到所有状态集合
  Link*temp = from;
  while (temp)
  {

    Node *tempNode = temp->pHeadOfNode;
    while (tempNode)
    {
      //如果数据为0 0 0 0,说明已经在历史数据里面,进行跳过
      int arr[4] = { 0, 0, 0, 0 };
      int x = cmp(tempNode->data, 4, arr, 4);
      if (x == 1)
      {
        goto B;
      }
      Node*k=move(tempNode->data,4);
      Link *lk = (Link *)malloc(sizeof(Link));
      lk->pHeadOfNode = k;
      lk->pNext = NULL;
      addAll(&from2, &from2tem,lk);

B:      tempNode = tempNode->pNext;
    }
    temp = temp->pNext;
  }
 

  removeAll(from2, hist);
  Link*kk = from2;
  Link * pttep;
  while (kk)
  {
    Node*tt = kk->pHeadOfNode;
    int art[4] = { 0 };
    while (tt)
    {
      if (cmp(tt->data, 4, art,4)==0)
      {
        goto K;
      }
      tt = tt->pNext;
    }
    kk = kk->pNext;
  }
  return -1;

K:  //添加到历史数据里面
  pttep = hist;
  while (pttep->pNext)
  {
    pttep = pttep->pNext;
  }
  addAll(&hist, &pttep, from2);
 
  Link*ph = from2;
 
  int r = ff(hist, from2, goal);
  if (r<0)
  {
    return r;
  }
  else
  {
    return r + 1;
  }
}


// 图的节点就是状态,在运行中才产生
// 当前状态的可达集合
void main()
{
  int cap[] = { 9, 7, 4, 2 };
  Link *pHead = NULL;

  int goal[4] = { 0 };
  for (int i = 0; i < 4; i++) { scanf("%d", goal+i); } Link*hist = (Link*)malloc(sizeof(Link));; hist->pNext = NULL;
  hist->pHeadOfNode = NULL;

  Node*p1 = (Node*)malloc(sizeof(Node));
  p1->data[0] = 9;
  p1->data[1] = 0;
  p1->data[2] = 0;
  p1->data[3] = 0;
  p1->pNext = NULL;
 
  hist->pHeadOfNode = p1;

  int x = ff(hist, hist, goal);
  printf("需要多少步:%d", x);

}


4. 风险度量

X星系的的防卫体系包含 n 个空间站。这 n 个空间站间有 m 条通信链路,构成通信网。
两个空间站间可能直接通信,也可能通过其它空间站中转。

对于两个站点x和y (x != y), 如果能找到一个站点z,使得:
当z被破坏后,x和y不连通,则称z为关于x,y的关键站点。

显然,对于给定的两个站点,关于它们的关键点的个数越多,通信风险越大。

你的任务是:已经网络结构,求两站点之间的通信风险度,即:它们之间的关键点的个数。

输入数据第一行包含2个整数n(2 <= n <= 1000), m(0 <= m <= 2000),分别代表站点数,链路数。
空间站的编号从1到n。通信链路用其两端的站点编号表示。
接下来m行,每行两个整数 u,v (1 <= u, v <= n; u != v)代表一条链路。
最后1行,两个数u,v,代表被询问通信风险度的两个站点。

输出:一个整数,如果询问的两点不连通则输出-1.

例如:
用户输入:
7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6
则程序应该输出:
2

资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 2000ms

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

所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
java选手注意:不要使用package语句。不要使用jdk1.7及以上版本的特性。
java选手注意:主类的名字必须是:Main,否则按无效代码处理。

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

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

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
import java.util.*;
public class A
{
  static void fan_zu(int[][] re, int me, int goal){
    if(re[me][3] <= goal) return; re[me][3] = goal; fan_zu(re, re[me][2], goal); } static void dfs(List[] gr, int[][] re, int v1, int v2){ if(v1==v2) return; for(Object obj: gr[v1]){ int it = (Integer)obj; if(re[it][0] > 0){
        fan_zu(re,v1,re[it][1]);  // 更新整个家族的返祖级
        continue;
      }
     
      re[it][0] = 1;
      re[it][1] = re[v1][1]+1;
      re[it][2] = v1;
      re[it][3] = re[v1][1];
      dfs(gr,re,it,v2);
    }
  }
 
  static int solve(int[][] re, int root, int leaf){
    int sum = 0;
    int p = leaf;
    int min = re[p][3];  // 当前最高(小)返祖级
    while(true){
      int pa = re[p][2];
      System.out.println("pa " + pa);
      if(pa==0 || pa==root) break;
      if(re[pa][1] <= min) sum++;
      if(re[pa][3] < min) min = re[pa][3]; p = pa; } return sum; } public static void main(String[] args) { Scanner scan = new Scanner(System.in); String[] ss = scan.nextLine().trim().split(" "); int m = Integer.parseInt(ss[0]); //节点数 int n = Integer.parseInt(ss[1]); //边数 List[] gr = new List[m+1]; // 顶点 --> list(顶点)
    for(int i=0; i<gr.length; i++) gr[i] = new Vector(); int[][] re = new int[m+1][4]; // dfs生成树结果: 顶点 --> (可见性, 深度, 父节点, 最高返祖)
   
    for(int i=0; i<n; i++){
      ss = scan.nextLine().trim().split(" ");
      int v1 = Integer.parseInt(ss[0]);
      int v2 = Integer.parseInt(ss[1]);
      gr[v1].add(v2);
      gr[v2].add(v1);
    }
   
    ss = scan.nextLine().trim().split(" ");
    int a = Integer.parseInt(ss[0]);
    int b = Integer.parseInt(ss[1]);
   
    re[a][0] = 1;
    re[a][1] = 0;
    re[1][3] = 0;
    dfs(gr,re,a,b);
   
    System.out.println(solve(re,a,b));  
  }
 
  static void debug(int[][] re){
    for(int i=0; i<re.length; i++){
      System.out.println(i + ": " + re[i][0] + "," + re[i][1] + "," + re[i][2] + "," + re[i][3]);
    }
  }
}

import java.util.*;


class MyGraph{
  class DfsNode{
    public int vex;
    public int level;
    public List<Integer> child;
    public int parent;
    public List<Integer> back;  //返祖
    public int min_back;  // 最小返祖level
   
    public DfsNode(int v){
      vex = v;
      level = 0;
      child = new ArrayList<Integer>();
      parent = -1;
      back = new ArrayList<Integer>();
      min_back = Integer.MAX_VALUE;
    }
   
    public void dfs(int v, Map<Integer,DfsNode> vis){
      DfsNode node = vis.get(v);
      if(node==null){
        child.add(v);
        node = new DfsNode(v);
        node.level = level + 1;
        node.parent = vex;
        vis.put(v, node);
       
        List<Integer> lst = map.get(v);
        for(int it: lst){
          node.dfs(it, vis);
        }
       
        return;
      }
     
      if(node.vex == parent) return;
       
      back.add(node.vex);
    }
   
    public void f_min_back(Map<Integer,DfsNode> tree){
      int min = Integer.MAX_VALUE;
      for(int it: back){
        int l = tree.get(it).level;
        if(l<min) min = l;
      }
     
      for(int it: child){
        DfsNode dn = tree.get(it);
        dn.f_min_back(tree);
        if(dn.min_back < min) min = dn.min_back;
      }
     
      min_back = min;
    }
   
    public String toString(){
      return "("+vex+",l="+level+",p="+parent+")";
    }
   
    public int ge_num(DfsNode root, Map<Integer,DfsNode> vis){
      if(parent == root.vex) return 0;
     
      DfsNode p = vis.get(parent);
      return p.ge_num(root, vis) + (min_back<p.level? 0 : 1);
    }
  }
 
  private Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
 
  public void add(int v1, int v2){
    List<Integer> lst = map.get(v1);
    if(lst==null){
      lst = new ArrayList<Integer>();
      map.put(v1, lst);
    }
    lst.add(v2);
   
    lst = map.get(v2);
    if(lst==null){
      lst = new ArrayList<Integer>();
      map.put(v2, lst);
    }
    lst.add(v1);
  }
 
  public int ge_num(int v1, int v2){
    DfsNode root = new DfsNode(v1);
    List<Integer> lst = map.get(v1);
    Map<Integer,DfsNode> vis = new HashMap<Integer,DfsNode>();
    vis.put(v1, root);
   
    for(int it: lst){
      root.dfs(it, vis);
    }
   
    root.f_min_back(vis);
    DfsNode p = vis.get(v2);    
    return p.ge_num(root, vis);
  }
}

public class B
{
  public static void main(String[] args)
  {
    Scanner scan = new Scanner(System.in);
   
    MyGraph g = new MyGraph();
   
    String[] ss = scan.nextLine().trim().split(" ");
    int n = Integer.parseInt(ss[1]);
    for(int i=0; i<n; i++){
      ss = scan.nextLine().trim().split(" ");
      g.add(Integer.parseInt(ss[0]), Integer.parseInt(ss[1]));
    }
   
    ss = scan.nextLine().trim().split(" ");
    int a = Integer.parseInt(ss[0]);
    int b = Integer.parseInt(ss[1]);
   
    System.out.println(g.ge_num(a,b));    
  }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
//mylist.h
#ifndef MYLIST_H
#define MYLIST_H

typedef struct myNode
{
    void * data;
    struct myNode *next;
} MyNode;

typedef struct myList
{
    MyNode * first;
    MyNode * last;
    int count;
    int (*equal)(void * a, void * b);
} MyList;

typedef struct myListIterator
{
    MyNode * p;
    int count;
    int allSize;
} MyListIterator;

//创建链表
MyList * createMyList();

//创建链表,带有相等参数,用于查找
MyList * createMySearchList(int(*equal)(void * a, void * b));

//释放链表
void freeMyList(MyList * list);

//插入在尾部
void myListInsertDataAtLast(MyList* const list, void* const data);

//插入在首部
void myListInsertDataAtFirst(MyList * const list, void* const data);

//插入
void myListInsertDataAt(MyList * const list, void* const data, int index);

//删除在尾部
void* myListRemoveDataAtLast(MyList* const list);

//删除在首部
void* myListRemoveDataAtFirst(MyList * const list);

//删除
void* myListRemoveDataAt(MyList* const list, int index);

//删除对象,返回是否删除成功
int myListRemoveDataObject(MyList* const list, void * data);

//长度
int myListGetSize(const MyList * const list);

//打印
void myListOutput(const MyList * const list, void(*pt)(const void * const));

//取得数据
void* myListGetDataAt(const MyList * const list, int index);

//取得第一个数据
void* myListGetDataAtFirst(const MyList * const list);

//取得最后一个数据
void* myListGetDataAtLast(const MyList * const list);

//查找某个数据的位置,如果equal方法为空,比较地址,否则调用equal方法
//如果不存在返回-1,如果存在,返回出现的第一个位置
int myListFindDataIndex(const MyList * const list, void * data);

//创建遍历器
MyListIterator* createMyListIterator(const MyList * const list);

//释放遍历器
void freeMyListIterator(MyListIterator* iterator);

//遍历器是否有下一个元素
int myListIteratorHasNext(const MyListIterator* const iterator);

//返回遍历器的下一个元素
void * myListIteratorNext(MyListIterator* const iterator);

#endif // MYLIST_H

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
//mylist.cpp
#include "mylist.h"

#include<malloc.h>
#include<stdlib.h>

//创建链表
MyList * createMyList()
{
    MyList * re = (MyList *) malloc(sizeof(MyList));
    re->count = 0;
    re->first = NULL;
    re->last = NULL;
    re->equal = NULL;
    return re;
}

//释放链表
void freeMyList(MyList * list)
{
    MyNode * p;
    while (list->first)
    {
        p = list->first->next;
        free(list->first);
        list->first = p;
    }
    free(list);
}

//插入在尾部
void myListInsertDataAtLast(MyList * const list, void* const data)
{
    MyNode * node = (MyNode *) malloc(sizeof(MyNode));
    node->data = data;
    node->next = NULL;
    if (list->count)
    {
        list->last->next = node;
        list->last = node;
    }
    else
    {
        list->first = node;
        list->last = node;
    }
    (list->count)++;
}

//插入在首部
void myListInsertDataAtFirst(MyList * const list, void* const data)
{
    MyNode * node = (MyNode *) malloc(sizeof(MyNode));
    node->data = data;
    node->next = NULL;

    if (list->count)
    {
        node->next = list->first;
        list->first = node;
    }
    else
    {
        list->first = node;
        list->last = node;
    }
    (list->count)++;
}

//长度
int myListGetSize(const MyList * const list)
{
    return list->count;
}

//打印
void myListOutput(const MyList * const list, void(*pt)(const void * const))
{
    MyNode * p = list->first;
    while (p)
    {
        (*pt)(p->data);
        p = p->next;
    }
}

//删除在尾部
void* myListRemoveDataAtLast(MyList* const list)
{
    if (list->count == 1)
    {
        return myListRemoveDataAtFirst(list);
    }
    MyNode * p = list->first;
    while (p->next != list->last)
    {
        p = p->next;
    }
    void *re = list->last->data;
    free(list->last);
    p->next = NULL;
    list->last = p;
    (list->count)--;
    return re;
}

//删除在首部
void* myListRemoveDataAtFirst(MyList * const list)
{
    MyNode *p = list->first;
    list->first = p->next;
    void * re = p->data;
    free(p);
    (list->count)--;
    if (list->count == 0)
    {
        list->last = NULL;
    }
    return re;
}

//插入
void myListInsertDataAt(MyList * const list, void* const data, int index)
{
    if (index == 0)
    {
        myListInsertDataAtFirst(list, data);
        return;
    }
    if (index == list->count)
    {
        myListInsertDataAtLast(list, data);
        return;
    }
    MyNode * node = (MyNode *) malloc(sizeof(MyNode));
    node->data = data;
    node->next = NULL;

    MyNode * p = list->first;
    for (int i = 0; i < index - 1; i++) { p = p->next;
    }
    node->next = p->next;
    p->next = node;

    (list->count)++;
}

//删除
void* myListRemoveDataAt(MyList* const list, int index)
{
    if (index == 0)
    {
        return myListRemoveDataAtFirst(list);
    }
    if (index == list->count - 1)
    {
        return myListRemoveDataAtLast(list);
    }

    MyNode * p = list->first;
    for (int i = 0; i < index - 1; i++) { p = p->next;
    }
    MyNode *tp = p->next;
    p->next = p->next->next;
    void * re = tp->data;
    free(tp);
    (list->count)--;
    return re;
}

//取得数据
void* myListGetDataAt(const MyList * const list, int index)
{
    if (index == list->count - 1)
    {
        return myListGetDataAtLast(list);
    }
    MyNode * p = list->first;
    for (int i = 0; i < index; i++) { p = p->next;
    }
    return p->data;
}

//取得第一个数据
void* myListGetDataAtFirst(const MyList * const list)
{
    return list->first->data;
}

//取得最后一个数据
void* myListGetDataAtLast(const MyList * const list)
{
    return list->last->data;
}

//查找某个数据的位置,如果equal方法为空,比较地址,否则调用equal方法
//如果不存在返回-1,如果存在,返回出现的第一个位置
int myListFindDataIndex(const MyList * const list, void * data)
{
    MyNode * p = list->first;
    int re = 0;
    if (list->equal)
    {
        while (p)
        {
            if (p->data == data || (*(list->equal))(p->data, data))
            {
                return re;
            }
            re++;
            p = p->next;
        }

    }
    else
    {
        while (p)
        {
            if (p->data == data)
            {
                return re;
            }
            re++;
            p = p->next;
        }
    }
    return -1;
}

//创建链表,带有相等参数,用于查找
MyList * createMySearchList(int(*equal)(void * a, void * b))
{
    MyList * re = createMyList();
    re->equal = equal;
    return re;
}

//创建遍历器
MyListIterator* createMyListIterator(const MyList * const list)
{
    MyListIterator * re = (MyListIterator *) malloc(sizeof(MyListIterator));
    re->p = list->first;
    re->allSize = list->count;
    re->count = 0;
    return re;
}

//释放遍历器
void freeMyListIterator(MyListIterator* iterator)
{
    free(iterator);
}

//遍历器是否有下一个元素
int myListIteratorHasNext(const MyListIterator* const iterator)
{
    return iterator->count < iterator->allSize;
}

//返回遍历器的下一个元素
void * myListIteratorNext(MyListIterator* const iterator)
{
//    if (iterator->p  == NULL)
//        return NULL;
    void * re = iterator->p->data;
    iterator->p = iterator->p->next;
    (iterator->count)++;
    return re;
}

//删除对象,返回是否删除成功
int myListRemoveDataObject(MyList* const list, void * data)
{
    MyListIterator * it = createMyListIterator(list);
    int a = 0;
    while (myListIteratorHasNext(it))
    {
        void * ld = myListIteratorNext(it);
        if (data == ld || (list->equal != NULL && (*(list->equal))(ld, data)))
        {
            a = 1;
            break;
        }
    }
    if (a)
    {
        myListRemoveDataAt(list, it->count - 1);
    }
    return a;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//mymap.h
#ifndef MYMAP_H
#define MYMAP_H

#include "mylist.h"

#define DEFAULT_INITIAL_CAPACITY 16
#define DEFAULT_LOAD_FACTOR 0.75f

typedef struct entry
{
    void * key;
    void * value;
} Entry;

typedef struct myHashMap
{
    int size;   //大小
    int initialCapacity; //初始容量
    float loadFactor;    //加载因子
    int (*hashCode)(void *key);
    int (*equal)(void *key1,void *key2);
    MyList ** entryList;
} MyHashMap;

typedef struct myHashMapEntryIterator
{
    int index;       //第几个链表
    MyHashMap *map;
    MyNode *current;
    int count;        //第几个数据
} MyHashMapEntryIterator;

//创建HashMap
MyHashMap *createMyHashMap(int (*hashCode)(void *key),int (*equal)(void *key1,void *key2));

//使用全部参数创建HashMap
MyHashMap *createMyHashMapForAll(int initialCapacity,float loadFactor,int (*hashCode)(void *key),int (*equal)(void *key1,void *key2));

//释放HashMap
void freeMyHashMap(MyHashMap * map);

//是否包含某个key
int myHashMapContainsKey(MyHashMap *const map,void * const key);

//增加一条映射
void myHashMapPutData(MyHashMap *const map,void * const key,void * const value);

//通过key得到数据,如果没有数据则返回null
void* myHashMapGetDataByKey(MyHashMap * const map,void *const key);

//数据的容量
int myHashMapGetSize(const MyHashMap * const map);

//创建Entry迭代器
MyHashMapEntryIterator* createMyHashMapEntryIterator( MyHashMap *const map);

//释放Entry迭代器
void freeMyHashMapEntryIterator(MyHashMapEntryIterator* iterator);

//Entry迭代器是否有下一个
int myHashMapEntryIteratorHasNext(MyHashMapEntryIterator* iterator);

//遍历下一个Entry元素
Entry* myHashMapEntryIteratorNext(MyHashMapEntryIterator* iterator);

//删除一条数据,返回是否删除成功
int myHashMapRemoveDataByKey(MyHashMap *const map,void * const key);

//遍历
void myHashMapOutput(MyHashMap *map, void(*pt)(Entry*));

#endif // MYMAP_H

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
//mymap.cpp
#include "myMap.h"
#include <stdlib.h>

//某条Entry链表上是否包含某个key值。
Entry* listContainsEntry(MyList * list, void * key,
        int(*equal)(void *key1, void *key2))
{
    MyListIterator* it = createMyListIterator(list);
    while (myListIteratorHasNext(it))
    {
        Entry * entry = (Entry *) (myListIteratorNext(it));
        if (entry->key == key || (equal != NULL && (*equal)(entry->key, key)))
        {
            return entry;
        }
    }
    freeMyListIterator(it);
    return NULL;
}

void rebuildMyHashMap(MyHashMap * map)
{
    int newSize = map->initialCapacity * 2;
    MyList **newentryList = (MyList **) malloc(sizeof(MyList*) * newSize);
    for (int i = 0; i < newSize; i++) { newentryList[i] = createMyList(); } MyHashMapEntryIterator* it = createMyHashMapEntryIterator(map); while (myHashMapEntryIteratorHasNext(it)) { Entry * entry = myHashMapEntryIteratorNext(it); int hasCode = (*(map->hashCode))(entry->key);
        hasCode %= newSize;
        if (hasCode < 0)
            hasCode += newSize;
        myListInsertDataAtLast(newentryList[hasCode], entry);
    }
    freeMyHashMapEntryIterator(it);
    for (int i = 0; i < map->initialCapacity; i++)
    {
        freeMyList(map->entryList[i]);
    }
    free(map->entryList);
    map->entryList = newentryList;
    map->initialCapacity = newSize;
}

//创建HashMap
MyHashMap *createMyHashMap(int(*hashCode)(void *key),
        int(*equal)(void *key1, void *key2)) {
    MyHashMap *re = (MyHashMap *) malloc(sizeof(MyHashMap));
    re->size = 0;
    re->loadFactor = DEFAULT_LOAD_FACTOR;
    re->initialCapacity = DEFAULT_INITIAL_CAPACITY;
    re->entryList = (MyList **) malloc(sizeof(MyList*) * re->initialCapacity);
    re->hashCode = hashCode;
    re->equal = equal;
    for (int i = 0; i < re->initialCapacity; i++)
    {
        re->entryList[i] = createMyList();
    }
    return re;
}

//使用全部参数创建HashMap
MyHashMap *createMyHashMapForAll(int initialCapacity, float loadFactor,
        int(*hashCode)(void *key), int(*equal)(void *key1, void *key2))
{
    MyHashMap *re = createMyHashMap(hashCode, equal);
    re->initialCapacity = initialCapacity;
    re->loadFactor = loadFactor;
    return re;
}

//是否包含某个key
int myHashMapContainsKey(MyHashMap * const map, void * const key)
{
    int hasCode = (*(map->hashCode))(key);
    hasCode %= map->initialCapacity;
    if (hasCode < 0) hasCode += map->initialCapacity;
    Entry * re = listContainsEntry(map->entryList[hasCode], key, map->equal);
    return re != NULL;
}

//增加一条映射
void myHashMapPutData(MyHashMap * const map, void * const key,
        void * const value)
{
    int hasCode = (*(map->hashCode))(key);
    hasCode %= map->initialCapacity;
    if (hasCode < 0) hasCode += map->initialCapacity;
    Entry * re = listContainsEntry(map->entryList[hasCode], key, map->equal);
    if (re == NULL)
    {
        Entry * entry = (Entry*) malloc(sizeof(Entry));
        entry->key = key;
        entry->value = value;
        myListInsertDataAtLast(map->entryList[hasCode], entry);
        (map->size)++;
        if (map->size > map->initialCapacity * map->loadFactor)
        {
            rebuildMyHashMap(map);
        }
    } else
    {
        re->value = value;
    }
}

//通过key得到数据,如果没有数据则返回null
void* myHashMapGetDataByKey(MyHashMap * const map, void * const key)
{
    int hasCode = (*(map->hashCode))(key);
    hasCode %= map->initialCapacity;
    if (hasCode < 0) hasCode += map->initialCapacity;
    Entry * re = listContainsEntry(map->entryList[hasCode], key, map->equal);
    if (re == NULL)
    {
        return NULL;
    }
    return re->value;
}

//数据的容量
int myHashMapGetSize(const MyHashMap * const map)
{
    return map->size;
}

//创建Entry迭代器
MyHashMapEntryIterator* createMyHashMapEntryIterator(MyHashMap * const map)
{
    MyHashMapEntryIterator* re = (MyHashMapEntryIterator*) malloc(
            sizeof(MyHashMapEntryIterator));
    re->count = 0;
    re->index = 0;
    re->map = map;
    re->current = map->entryList[0]->first;
    return re;
}

//释放Entry迭代器
void freeMyHashMapEntryIterator(MyHashMapEntryIterator* iterator)
{
    free(iterator);
}

//Entry迭代器是否有下一个
int myHashMapEntryIteratorHasNext(MyHashMapEntryIterator* iterator)
{
    return iterator->count < iterator->map->size;
}

//遍历下一个Entry元素
Entry* myHashMapEntryIteratorNext(MyHashMapEntryIterator* iterator)
{
    (iterator->count)++;
    while (!(iterator->current))
    {
        (iterator->index)++;
        iterator->current = iterator->map->entryList[iterator->index]->first;
    }
    Entry * re = (Entry *) iterator->current->data;
    iterator->current = iterator->current->next;
    return re;
}

//删除一条数据,返回是否删除成功
int myHashMapRemoveDataByKey(MyHashMap * const map, void * const key)
{
    int hasCode = (*(map->hashCode))(key);
    hasCode %= map->initialCapacity;
    if (hasCode < 0) hasCode += map->initialCapacity;
    MyListIterator* it = createMyListIterator(map->entryList[hasCode]);
    int re = 0;
    while (myListIteratorHasNext(it))
    {
        Entry * entry = (Entry *) (myListIteratorNext(it));
        if ((*(map->equal))(entry->key, key))
        {
            myListRemoveDataAt(map->entryList[hasCode], it->count - 1);
            re = 1;
            (map->size)--;
            break;
        }
    }
    freeMyListIterator(it);
    return re;
}

void myFree(Entry * p)
{
    free(p);
}

//释放HashMap
void freeMyHashMap(MyHashMap * map)
{
    myHashMapOutput(map, myFree);
    for (int i = 0; i < map->initialCapacity; i++)
    {
        freeMyList(map->entryList[i]);
    }
    free(map->entryList);
    free(map);
}

//遍历
void myHashMapOutput(MyHashMap *map, void(*pt)(Entry*))
{
    MyHashMapEntryIterator* iterator = createMyHashMapEntryIterator(map);
    while (myHashMapEntryIteratorHasNext(iterator))
    {
        pt(myHashMapEntryIteratorNext(iterator));
    }
    freeMyHashMapEntryIterator(iterator);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
//main.cpp
#include<stdio.h>
#include<stdlib.h>

#include "mylist.h"
#include "mymap.h"

//int类型hashCode
int myHashCodeInt(void * a)
{
    int * aa = (int *) a;
    return *aa;
}

//int类型相等的方法
int myEqualInt(void * a, void *b)
{
    int *aa = (int*) a;
    int *bb = (int *) b;
    return *aa == *bb;
}

MyHashMap * map = NULL;

struct DfsNode
{
    int vex;
    int level;
    MyList * child;
    int parent;
    MyList * back;
    int min_back;
};

void creatDfs(DfsNode* node, int v)
{
    node->vex = v;
    node->level = 0;
    node->child = createMyList();
    node->parent = -1;
    node->back = createMyList();
    node->min_back = __INT_MAX__;
}

void dfs(DfsNode* node, int v, MyHashMap * vis)
{
    DfsNode * tmpNode = (DfsNode*)myHashMapGetDataByKey(vis, (void*)(&v));
    if(tmpNode == NULL)
    {
        int * pV = (int *)malloc(sizeof(int));
        *pV = v;

        int * pV2 = (int *)malloc(sizeof(int));
        *pV2 = v;

        myListInsertDataAtLast(node->child, (void*)(pV));

        tmpNode = (DfsNode*)malloc(sizeof(DfsNode));
        creatDfs(tmpNode, v);
        tmpNode->level = node->level + 1;
        tmpNode->parent = node->vex;

        myHashMapPutData(vis, (void*)pV2, (void*)(tmpNode));

        MyList * lst = (MyList*)myHashMapGetDataByKey(map, (void*)(&v));

        if(lst)
        {
            // 遍历
            MyListIterator * it = createMyListIterator(lst);
            while(myListIteratorHasNext(it))
            {
                int * p = (int *)myListIteratorNext(it);

                dfs(tmpNode, *p, vis);
            }
            //释放迭代器
            freeMyListIterator(it);
        }

        return;
    }

    if(tmpNode->vex == node->parent)
        return;
    int * pVex = (int *)malloc(sizeof(int));
    *pVex = tmpNode->vex;
    myListInsertDataAtLast(node->back, (void*)pVex);
}

void f_min_back(DfsNode* node, void * tree)
{
    int min = __INT_MAX__;

    MyHashMap* pTree = (MyHashMap*)tree;

    // 遍历
    if(node && pTree && node->back)
    {
        MyListIterator * it = createMyListIterator(node->back);
        while(myListIteratorHasNext(it))
        {
            int * pValue = (int*)myListIteratorNext(it);
            DfsNode * tmpNode =
                    (DfsNode *)myHashMapGetDataByKey(pTree, (void*)pValue);

            if(tmpNode)
            {
                int l = tmpNode->level;
                if(l < min) min = l; } } //释放迭代器 freeMyListIterator(it); } if(node && pTree && node->child)
    {
        // 遍历
        MyListIterator * it = createMyListIterator(node->child);
        while(myListIteratorHasNext(it))
        {
            int * pValue = (int*)myListIteratorNext(it);
            DfsNode * tmpNode =
                    (DfsNode *)myHashMapGetDataByKey(pTree, (void*)pValue);

            if(tmpNode)
            {
                f_min_back(tmpNode, tree);
                if(tmpNode->min_back < min) min = tmpNode->min_back;
            }
        }
        //释放迭代器
        freeMyListIterator(it);
    }
    node->min_back = min;
}

int dfs_ge_num(DfsNode* node, DfsNode * root, void * vis)
{
    if(node->parent == root->vex) return 0;

    DfsNode * p =
            (DfsNode *)myHashMapGetDataByKey((MyHashMap*)vis, (void*)(&node->parent));
    return dfs_ge_num(p, root, vis) + ((node->min_back < p->level) ? 0 : 1);
}

void add(int v1, int v2)
{
    int * pV1 = (int *)malloc(sizeof(int));
    int * pV2 = (int *)malloc(sizeof(int));

    *pV1 = v1;
    *pV2 = v2;

    MyList * lst =
            (MyList *)myHashMapGetDataByKey(map, (void*)(pV1));

    if(lst == NULL)
    {
        lst = createMyList();
        myHashMapPutData(map, (void*)(pV1), (void*)lst);
    }
    myListInsertDataAtLast(lst, (void*)(pV2));

    lst = (MyList *)myHashMapGetDataByKey(map, (void*)(pV2));
    if(lst == NULL)
    {
        lst = createMyList();
        myHashMapPutData(map, (void*)(pV2), (void*)lst);
    }
    myListInsertDataAtLast(lst, (void*)(pV1));
}

int ge_num(int v1, int v2)
{
    DfsNode * root = (DfsNode*)malloc(sizeof(DfsNode));
    creatDfs(root, v1);

    int * pV1 = (int *)malloc(sizeof(int));
    *pV1 = v1;
    MyList * lst = (MyList *)myHashMapGetDataByKey(map, (void*)(&v1));

    MyHashMap * vis = createMyHashMap(myHashCodeInt, myEqualInt);
    myHashMapPutData(vis, (void*)(pV1), (void*)root);

    if(lst)
    {
        // 遍历
        MyListIterator * it = createMyListIterator(lst);
        while(myListIteratorHasNext(it))
        {
            int * pValue = (int*)myListIteratorNext(it);
            dfs(root, *pValue, vis);
        }
        //释放迭代器
        freeMyListIterator(it);
    }

    f_min_back(root, (void*)vis);
    int * pV2 = (int *)malloc(sizeof(int));
    *pV2 = v2;
    DfsNode * p = (DfsNode *)myHashMapGetDataByKey(vis, (int*)(pV2));
    return dfs_ge_num(p, root, vis);
}

int main(/*int argc, char *argv[]*/)
{
    printf("%s", "Hello World!\n");
    map = createMyHashMap(myHashCodeInt, myEqualInt);

    int m, n, a, b = 0;

    scanf("%d %d", &m, &n);

    for(int i = 0; i < n; i++)
    {
        scanf("%d %d", &a, &b);
        add(a, b);
    }

    scanf("%d %d", &a, &b);
    printf("%d", ge_num(a, b));

    return 0;
}


如果您需要更多课程内容和讲解视频,请联系小蓝


蓝桥杯算法特训第六课【分治】源代码

【内容简介】
本文章内容为【2018蓝桥杯大赛算法特训(软件)系列课程】第六课【分治】中涉及到的课上例题的代码实现,加入赛前算法特训获取全部课程内容请联系【小蓝】。


【课程中涉及的源代码】
1. 二分查找

已知有序的序列,比如:2,3,3,5,9,9,9,12,12,13,15,22,22,22,22,25,25,23,91,95
有整数x,比如: x=23
要求找到一个刚好比x稍微大一点的元素位置

当数组较大的时候,需要二分查找加快速度。

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class A
{
  // 含有begin, 不含end
  static int f(int[] a, int begin, int end, int x){
    if(end-begin==1){
      if(a[begin] > x) return begin;
      return end;
    }
   
    int k = (begin+end)/2;
    if(x>=a[k]) return f(a,k,end,x);
    return f(a,begin,k,x);
  }
 
  // 求x应该插入的位置
  // return 刚好比x稍微大点的那个数的位置
  static int f(int[] a, int x){
    if(x>=a[a.length-1]) return -1;
    return f(a,0,a.length,x);
  }
 
  public static void main(String[] args){
    int[] a = {1,5,11,24,25,32,32,33,49,66,68,69,70
      ,75,88,102,114,119,120,135,146,221,294,300,302,305,333};
    System.out.println(f(a,32));
  }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 含有begin, 不含end
int f(int* a, int begin, int end, int x)
{
  if (end - begin == 1)
  {
    if (a[begin] > x)
      return begin;
    return end;
  }

  int k = (begin + end) / 2;
  if (x >= a[k])
    return f(a, k, end, x);
  return f(a, begin, k, x);
}

// 求x应该插入的位置
// return 刚好比x稍微大点的那个数的位置
int f1(int* a,int len, int x)
{
  if (x >= a[len - 1])
    return -1;
  return f(a, 0, len, x);
}

 void main()
 {
  int a[]  = { 1, 5, 11, 24, 25, 32, 32, 33, 49, 66, 68, 69, 70, 75, 88, 102, 114, 119, 120, 135, 146, 221, 294, 300, 302, 305, 333 };
  printf("%d ",f1(a, 27, 32));

}


2. 最大序列和

数组中整数有正有负
求一连续子段,使得和最大化
例如:
2,4,-7,5,2,-1,2,-4,3
最大连续段:
5,2,-1,2

其最大和为8

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class A
{
  static int f(int[] a, int begin, int end){
    if(end-begin==1){
      if(a[begin] > 0) return a[begin];
      return 0;
    }
   
    int k = (begin+end)/2;
    int t1 = f(a,begin,k);
    int t2 = f(a,k,end);
   
    int t3a = 0;
    int sum = 0;
    for(int i=k-1; i>=begin; i--){
      sum += a[i];
      if(sum > t3a) t3a = sum;
    }
   
    int t3b=0;
    sum = 0;
    for(int i=k; i<end; i++){ sum += a[i]; if(sum > t3b) t3b = sum;
    }
   
    int t3 = t3a + t3b;
   
    int max = 0;
    if(t1 > max) max = t1;
    if(t2 > max) max = t2;
    if(t3 > max) max = t3;
   
    return max;
  }
 
  static int work(int[] a){
    return f(a,0,a.length);
  }
 
  public static void main(String[] args){
    System.out.println(work(new int[]{2,4,-7,5,2,-1,2,-4,3}));
  }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int ff(int* a, int begin, int end)
{
  if (end - begin == 1)
  {
    if (a[begin] > 0)
      return a[begin];
    return 0;
  }

  int k = (begin + end) / 2;
  int t1 = ff(a, begin, k);
  int t2 = ff(a, k, end);

  int t3a = 0;
  int sum = 0;
  for (int i = k - 1; i >= begin; i--)
  {
    sum += a[i];
    if (sum > t3a)
      t3a = sum;
  }

  int t3b = 0;
  sum = 0;
  for (int i = k; i<end; i++) { sum += a[i]; if (sum > t3b)
      t3b = sum;
  }

  int t3 = t3a + t3b;

  int max = 0;
  if (t1 > max)
    max = t1;
  if (t2 > max)
    max = t2;
  if (t3 > max)
    max = t3;

  return max;
}

int work(int * a,int len)
{
  return ff(a, 0, len);
}

 void main()
 {
   int arr[] = { 2, 4, -7, 5, 2, -1, 2, -4, 3 };
   int x=work(arr, 9);
   printf("%d ", x);
}


3. 大数乘法问题

用串的形式表示大数的乘法。

即求类似: “23234845847839461464158174814792” * “6457847285617487843234535”
要求结果返回一个串。

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.math.BigInteger;
public class A
{
  static String zero(int n){
    if(n==0) return "";
    if(n==1) return "0";
    return zero(n/2) + zero(n/2) + zero(n%2);
  }
 
  static String add(String a, String b){
    if(a.length()<=8 && b.length()<=8) return Integer.parseInt(a) + Integer.parseInt(b) + ""; String a1 = "0"; String a2 = a; if(a.length()>8){
      a1 = a.substring(0,a.length()-8);
      a2 = a.substring(a.length()-8);
    }
   
    String b1 = "0";
    String b2 = b;
    if(b.length()>8){
      b1 = b.substring(0,b.length()-8);
      b2 = b.substring(b.length()-8);
    }
   
    String t = add(a2,b2);
    while(t.length()<8) t = "0" + t; if(t.length()>8) return add(add(a1,b1),"1") + t.substring(1);
    return add(a1,b1) + t;    
  }
 
  static String multi(String a, String b){
    if(a.length()<=4 && b.length()<=4) return Integer.parseInt(a) * Integer.parseInt(b) + ""; if(a.length()>4){
      int k = a.length()/2;
      String a1 = a.substring(0,k);
      String a2 = a.substring(k);
     
      return add(multi(a1,b)+zero(a2.length()),multi(a2,b));
    }
   
    return multi(b,a);
  }
 
  public static void main(String[] args){
    System.out.println(multi("1234567890987654321666",
      "1234567890123456789555"));
     
    System.out.println(new BigInteger("1234567890987654321666")
      .multiply(new BigInteger("1234567890123456789555")));
  }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
/*
由于C原因进行字符串拼接比较繁琐,需要开辟对应长度的内存空间,全部都是用的malloc()在堆上开辟,时间紧张没有及时释放,深度递归时大量消耗内存,所以运行特别特别大的数据时内存不够会报错,所以建议大家不要用太大的数据验证。本代码注重的是算法逻辑,请知晓!
*/

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
char * myMallocCpy(char *s)
{
  int len = strlen(s) + 1;
  char *p = (char *)malloc(len);
  memset(p, 0, len);
  strcpy(p, s);
  return p;
}

char * myMallocLink(char *s1,char*s2)
{
  int len1 = strlen(s1);
  int len2 = strlen(s2);
  int len = len1 + len2+ 1;
 
  char *p = (char *)malloc(len);
  memset(p, 0, len);
  strcpy(p, s1);
  strcat(p, s2);
  return p;
}



char * zero(int n)
 {
  if (n == 0)
    return myMallocCpy("");
  if (n == 1)
    return myMallocCpy("0");
  char *s1 = zero(n / 2);
  char *s2 = zero(n / 2);
  char *s3 = zero(n % 2);
  char *s1Link = myMallocLink(s1, s2);
  char *s2Link = myMallocLink(s1Link, s3);
  return s2Link;
}

char* add(char* a, char* b)
{
  int lenOfA = strlen(a);
  int lenOfB = strlen(b);

  if (lenOfA <= 8 && lenOfB <= 8) { int x1 = atoi(a); int x2 = atoi(b); int sum = x1 + x2; int maxLen = lenOfA > lenOfB ? lenOfA : lenOfB;
    char*p = (char*)malloc(maxLen + 2);
    memset(p, 0, maxLen + 2);
    _itoa(sum, p,10);
    return p;
  }


  char * a1 = myMallocCpy("0");
  char * a2 = myMallocCpy(a);
 
  if (lenOfA > 8)
  {
    char tmp = a[lenOfA - 8];
    a[lenOfA - 8] = '\0';
    a1 = myMallocCpy(a);
    a[lenOfA - 8] = tmp;

    a2 = myMallocCpy(a + lenOfA - 8);
  }

  char * b1 = myMallocCpy("0");
  char * b2 = myMallocCpy(b);
  if (lenOfB > 8)
  {
    char tmp = b[lenOfB - 8];
    b[lenOfB - 8] = '\0';
    b1 = myMallocCpy(b);
    b[lenOfB - 8] = tmp;
    b2 = myMallocCpy(b + lenOfB - 8);

  }

  char* t = add(a2, b2);

  while (strlen(t)<8) { int tempLen = strlen(t); char *tt = (char*)malloc(tempLen + 1+1); memset(tt, 0, tempLen + 2); strcpy(tt + 1, t); t = tt; } if (strlen(t)>8)
  {
    char * padd1 = add(add(a1, b1), "1");
    int lenOdAdd1 = strlen(padd1);

    int lenOft = strlen(t);
    int lenSum = lenOdAdd1 + lenOft;

    char *pOk = (char*)malloc(lenSum);
    memset(pOk, 0, lenSum);

    strcpy(pOk, padd1);
    strcat(pOk, t + 1);

    return pOk;
  }

  char*padd2 = add(a1, b1);
  int lenOdAdd2 = strlen(padd2);

  int lenOft = strlen(t);

  int lenSum = lenOdAdd2 + lenOft + 1;
  char *pOk = (char*)malloc(lenSum);
  memset(pOk, 0, lenSum);

  strcpy(pOk, padd2);
  strcat(pOk, t);
  return pOk;
}

char* multi(char* a, char* b)
{
  int lena = strlen(a);
  int lenb = strlen(b);

  if (lena <= 4 && lenb <= 4) { int aInt = atoi(a); int bInt = atoi(b); int mul = aInt * bInt; int len = 0; int mulTmp = mul; while (mulTmp>0)
    {
      len++;
      mulTmp = mulTmp / 10;
    }

    char *p = (char*)malloc(len + 1);
    memset(p, 0, len + 1);

    _itoa(mul, p, 10);
    return p;
  }

  if (lena > 4)
  {
    int k = lena / 2;
    char aTemp = a[k];
    a[k] = '\0';
    char *pa1=myMallocCpy(a);
    a[k] = aTemp;
    char *pa2 = myMallocCpy(a+k);
   
    char *plh1 = multi(pa1, b);
    char *plh2 = zero(strlen(pa2));
    char*plh = myMallocLink(plh1, plh2);
    return add(plh, multi(pa2, b));
  }
  return multi(b, a);
}

void main()
{
  char *pl=myMallocLink("123", "567");
  char a[] = "1234567890";
  char b[] = "1234567890";


  printf("1234567890*1234567890 = ");
  printf("%s\n",multi(a, b));

/*  System.out.println(multi("1234567890987654321666",
    "1234567890123456789555"));

  System.out.println(new BigInteger("1234567890987654321666")
    .multiply(new BigInteger("1234567890123456789555")));*/

}


4. 提速

取球博弈和振兴中华等的递归解法有个弱点:

规模变大后,迅速超时…

解决方案:
1. 缓存子调用,把已经调用过的存在map中。
2. 不用递归,巧妙设计计算次序,使用数组存结果

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
//取球问题
public class A
{
  // n: 球数
  // return: true必赢
  static boolean f(int n){
    if(n==0) return true;
   
    if(n >= 1 && f(n-1)==false) return true;
    if(n >= 3 && f(n-3)==false) return true;
    if(n >= 7 && f(n-7)==false) return true;
    if(n >= 8 && f(n-8)==false) return true;    
    return false;
  }
 
  public static void main(String[] args){
    System.out.println(f(55));
  }
}

// 缓存法
import java.util.*;
public class B
{
  static Map map = new HashMap();
 
  // n: 球数
  // return: true必赢
  static boolean f(int n){
    if(map.get(n)!=null) return (Boolean)map.get(n);
   
    boolean t = false;
    if(n >= 1 && f(n-1)==false) t = true;
    if(n >= 3 && f(n-3)==false) t = true;
    if(n >= 7 && f(n-7)==false) t = true;
    if(n >= 8 && f(n-8)==false) t = true;
     
    map.put(n,t);
    return t;
  }
 
  public static void main(String[] args){
    map.put(0,true);
    System.out.println(f(1055));
  }
}

//振兴中华
public class AA
{
  static int f(int m, int n)
  {
    if(m==1 || n==1) return 1;
   
    return (f(m-1,n) + f(m,n-1)) % 10000;
  }
 
  public static void main(String[] args)
  {
    System.out.println(f(20,15));
    //System.out.println(f(3,2));
  }

}

public class BB
{
  static int f(int m, int n)
  {
    if(m==1 || n==1) return 1;  
    return (f(m-1,n) + f(m,n-1)) % 10000;
  }
 
  public static void main(String[] args)
  {
    int[][] a = new int[100][100];
   
    for(int i=1; i<100; i++){
      a[i][1] = 1;
      a[1][i] = 1;
    }
   
    for(int i=2; i<100; i++){
      for(int j=2; j<100; j++){
        a[i][j] = (a[i-1][j] + a[i][j-1]) % 10000;
      }
    }
    System.out.println(a[20][15]);
    System.out.println(f(20,15));
  }

}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//取球问题
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include<string.h>

int fff(int n)
{
  if (n == 0)
    return 1;

  if (n >= 1 && fff(n - 1) == 0)
    return 1;
  if (n >= 3 && fff(n - 3) == 0)
    return 1;
  if (n >= 7 && fff(n - 7) == 0)
    return 1;
  if (n >= 8 && fff(n - 8) == 0)
    return 1;

  return 0;
}

void main()
{
  printf("55 : %s\n",  fff(55) ? "true" : "false");
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
//取球问题
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include<string.h>

typedef struct MyNode
{
  int n;
  int b;
  struct MyNode*pNext;
}MyNode;

MyNode *pHead = NULL;
MyNode *pTail = NULL;

void put(int n, int b)
{
  MyNode*pNode = (MyNode*)malloc(sizeof(MyNode));
  pNode->n = n;
  pNode->b = b;
  pNode->pNext = NULL;

  if (pHead == NULL)
  {
    pHead = pNode;
    pTail = pNode;
  }
  else
  {
    pTail->pNext = pNode;
    pTail = pNode;
  }
}

int get(int n)
{
  MyNode * pTemp = pHead;
  while (pTemp)
  {
    if (n==pTemp->n)
    {
      return pTemp->b;
    }
    pTemp = pTemp->pNext;
  }
  return -1;
}


// n: 球数
// return: true必赢
 int fa(int n)
 {
   if (get(n) != -1)
    return get(n);

  int t = 0;
  if (n >= 1 && fa(n - 1) == 0)
    t = 1;
  if (n >= 3 && fa(n - 3) == 0)
    t = 1;
  if (n >= 7 && fa(n - 7) == 0)
    t = 1;
  if (n >= 8 && fa(n - 8) == 0)
    t = 1;

  put(n, t);
  return t;
 }

void main()
{
  put(0, 1);
  int x=fa(1055);
  printf("%s", x ? "true" : "false");
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//振兴中华
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int f5(int m, int n)
{
  if (m == 1 || n == 1)
    return 1;

  return (f5(m - 1, n) + f5(m, n - 1)) % 10000;
}

void main()
{

  printf("%d",f5(20, 15));

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//振兴中华
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int fc(int m, int n)
{
  if (m == 1 || n == 1)
    return 1;
  return (fc(m - 1, n) + fc(m, n - 1)) % 10000;
}

void main()
{
  int a[100][100] = { 0 };

  for (int i = 1; i < 100; i++)
  {
    a[i][1] = 1;
    a[1][i] = 1;
  }

  for (int i = 2; i < 100; i++)
  {
    for (int j = 2; j < 100; j++)
    {
      a[i][j] = (a[i - 1][j] + a[i][j - 1]) % 10000;
    }
  }

  printf("%d\n", a[20][15]);
  printf("%d\n", fc(20, 15));
}


5. 城墙刷漆
X国的一段古城墙的顶端可以看成 2*N个格子组成的矩形(如图所示)
现需要把这些格子刷上保护漆。

你可以从任意一个格子刷起,刷完一格,可以移动到和它相邻的格子(对角相邻也算数),但不能移动到较远的格子(因为油漆未干不能踩!)

比如:a d b c e f 就是合格的刷漆顺序。
c e f d a b 是另一种合适的方案。

当已知 N 时,求总的方案数。当N较大时,结果会迅速增大,请把结果对 1000000007 (十亿零七) 取模。
输入数据为一个正整数(不大于1000)
输出数据为一个正整数。

例如:
用户输入:
2
程序应该输出:
24

再例如:
用户输入:
3
程序应该输出:
96

再例如:
用户输入:
22
程序应该输出:
359635897

锦囊:

fb(n) 从边缘某格开始,到与它相邻的另一个边缘格子结束
fb(n) = fb(n-1) * 2

fa(n) 从某个边缘格子开始的所有情况
fa(n) = fb(n) + 2*fa(n-1) + 4 * fa(n-2)
最后走相邻边缘格 第1步走相邻边缘格 第2步走相邻边缘格

fk(i,n) 一共有n个格子,从中间的第i个格子为起点,任意结束
fk(i,n) = ( fb(i)*fa(n-i)*2 + fb(n-i+1)*fa(i-1)*2 ) * 2
先走左边再右边 先走右边再左边 有两个可能起点

总情况包含:
从某个边缘格开始的所有情况 4 * fa(i)
从中间某个格子开始的所有情况 i从2到n-1求和:fk(i,n)

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
public class A
{
  static long MM = 1000000007;
  // 从某个边缘格子开始,到它相邻的边缘格子结束的所有情况
  static long fb(int n)
  {
    if(n==1) return 1;
    return fb(n-1) * 2 % MM;
  }
 
  // 从某个边缘格子开始的所有情况
  static long fa(int n)
  {
    if(n==1) return 1;
    if(n==2) return 6;
    return (2 * fa(n-1) + 4 * fa(n-2) + fb(n)) % MM;
  }
 
  // 规模为n的问题之中间第i格
  static long fk(int i, int n)
  {
    //return fb(i) * fa(n-i) * 2 * 4 % MM; //相当于镜像互换了
    return (fb(i)*fa(n-i)*2 % MM + fb(n-i+1)*fa(i-1)*2 % MM) * 2 % MM;
  }
 
  static long f(int n)
  {
    if(n==1) return 2;
   
    long sum = fa(n) * 4 % MM;
    for(int i=2; i<n; i++){
      sum = (sum + fk(i,n)) % MM;
    }
    return sum;
  }
 
  public static void main(String[] args)
  {
    for(int i=1; i<30; i++){
      System.out.println(i + ": " + f(i));  
    }
  }
}

public class B
{
  static long M = 1000000007;
  // 从某个边缘格子开始,到它相邻的边缘格子结束的所有情况
  static long[] fb = new long[1000];
  // 从某个边缘格子开始的所有情况
  static long[] fa = new long[1000];
   
  // 规模为n的问题之中间第i格
  static long fk(int i, int n)
  {
    //return fb(i) * fa(n-i) * 2 * 4 % MM; //相当于镜像互换了
    return (fb[i]*fa[n-i]*2 % M + fb[n-i+1]*fa[i-1]*2 % M) * 2 % M;
  }
 
  static long f(int n)
  {
    if(n==1) return 2;
   
    long sum = fa[n] * 4 % M;
    for(int i=2; i<n; i++){
      sum = (sum + fk(i,n)) % M;
    }
    return sum;
  }
 
  public static void main(String[] args)
  {
    fb[1] = 1;
    for(int i=2; i<fb.length; i++){
      fb[i] = fb[i-1] * 2 % M;
    }
       
    fa[1] = 1;
    fa[2] = 6;
    for(int i=3; i<fa.length; i++){
      fa[i] = (2*fa[i-1] + 4 * fa[i-2] + fb[i]) % M;
    }
   
    for(int i=1; i<130; i++){
      System.out.println(i + ": " + f(i));  
    }
  }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static long long MM = 1000000007;
// 从某个边缘格子开始,到它相邻的边缘格子结束的所有情况
long long fb6(int n)
{
  if (n == 1) return 1;
  return fb6(n - 1) * 2 % MM;
}

// 从某个边缘格子开始的所有情况
long long fa6(int n)
{
  if (n == 1) return 1;
  if (n == 2) return 6;
  return (2 * fa6(n - 1) + 4 * fa6(n - 2) + fb6(n)) % MM;
}

// 规模为n的问题之中间第i格
long long fk(int i, int n)
{
  //return fb6(i) * fa6(n-i) * 2 * 4 % MM; //相当于镜像互换了
  return (fb6(i)*fa6(n - i) * 2 % MM + fb6(n - i + 1)*fa6(i - 1) * 2 % MM) * 2 % MM;
}
long long f6(int n)
{
  if (n == 1) return 2;

  long long sum = fa6(n) * 4 % MM;
  for (int i = 2; i < n; i++){
    sum = (sum + fk(i, n)) % MM;
  }
  return sum;
}


void main()
{
  for (int i = 1; i < 30; i++)
  {
    printf("%d : %d\n", i, f6(i));
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static long long M = 1000000007;
  // 从某个边缘格子开始,到它相邻的边缘格子结束的所有情况
static long long fb[1000] = {0};
  // 从某个边缘格子开始的所有情况
static long long fa[1000] = { 0 };


  // 规模为n的问题之中间第i格
long long fk62(int i, int n)
{
  //return fb(i) * fa(n-i) * 2 * 4 % MM; //相当于镜像互换了
  return (fb[i] * fa[n - i] * 2 % M + fb[n - i + 1] * fa[i - 1] * 2 % M) * 2 % M;
}


long long f62(int n)
{
  if (n == 1) return 2;
  long long sum = fa[n] * 4 % M;
  for (int i = 2; i < n; i++)
  {
    sum = (sum + fk62(i, n)) % M;
  }
  return sum;
}

void main()
{
  fb[1] = 1;
  for (int i = 2; i < 1000; i++)
  {
    fb[i] = fb[i - 1] * 2 % M;
  }

  fa[1] = 1;
  fa[2] = 6;
  for (int i = 3; i < 1000; i++)
  {
    fa[i] = (2 * fa[i - 1] + 4 * fa[i - 2] + fb[i]) % M;
  }

  for (int i = 1; i < 130; i++)
  {
    printf("%d : %d\n",i,f62(i));
  }
}


6. 环形涂色

如上图,组成环形的格子需要涂3种颜色。
它们的编号分别是1~14
相邻的格子不能用相同的颜色。
涂色方案的数目是:24576

当格子数目为50的时候,求涂色方案总数。

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class A
{
  /*
  static long f(int n){
    if(n==1) return 3;
    if(n==2) return 6;
    return 2 * f(n-2) + f(n-1);
  }
  */

 
  public static void main(String[] args){
    long[] f = new long[50+10];
    f[1] = 3;
    f[2] = 6;
    for(int i=3; i<=50; i++){
      f[i] = f[i-2] * 2 + f[i-1];
    }
   
    for(int i=3; i<=50; i++){
      System.out.println(i + ": " + f[i]);
    }
  }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 

void main()
{
  long long f[60] = { 0 };
  f[1] = 3;
  f[2] = 6;
  for (int i = 3; i <= 50; i++)
  {
    f[i] = f[i - 2] * 2 + f[i - 1];
  }

  for (int i = 3; i <= 30; i++)
  {
    printf("%d : %d\n",i,f[i]);
  }
}


如果您需要更多课程内容和讲解视频,请联系小蓝


蓝桥杯算法特训第五课【博弈问题的思路】源代码

【内容简介】
本文章内容为【2018蓝桥杯大赛算法特训(软件)系列课程】第五课【博弈问题的思路】中涉及到的课上例题的代码实现,加入赛前算法特训获取全部课程内容请联系【小蓝】。


【课程中涉及的源代码】
1. 日期与星期
大数学家高斯有个好习惯:无论如何都要记日记。
他的日记有个与众不同的地方,他从不注明年月日,而是用一个整数代替,比如:4210

后来人们知道,那个整数就是日期,它表示那一天是高斯出生后的第几天。这或许也是个好习惯,它时时刻刻提醒着主人:日子又过去一天,还有多少时光可以用于浪费呢?

高斯出生于:1777年4月30日。
在高斯发现的一个重要定理的日记上标注着:5343,因此可算出那天是:1791年12月15日。

高斯获得博士学位的那天日记上标着:8113
请你算出高斯获得博士学位的年月日。

1949年的国庆节(10月1日)是星期六。
今年(2012)的国庆节是星期一。
那么,从建国到现在,有几次国庆节正好是星期日呢?

只要答案,不限手段!
可以用windows日历,windows计算器,Excel公式,。。。。。
当然,也可以编程!

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 日期差问题
// 2015-3-2 距离 1979-12-15 多少天?
// 日期表示法?? 距离基点的天数

public class A
{
   
    static int day_dif(int year1,int month1,int day1,
                       int year2,int month2,int day2){
        return get_days(year2,month2,day2)
             - get_days(year1,month1,day1);
   
    }
   
    static boolean is_leap_year(int year){
        boolean tag = false;
        if(year%4==0) tag = true;
        if(year%100==0) tag = false;
        if(year%400==0) tag = true;
        return tag;
    }
   
    static int get_days(int year, int month, int day){
        int[] M = {0,31,28,31,30,31,30,31,31,30,31,30,31};
        if(is_leap_year(year)) M[2]++;
       
        int sum = 0;
        for(int i=1; i<year; i++){
            sum += 365;
            if(is_leap_year(i)) sum++;
        }
       
        for(int i=1; i<month; i++){
            sum += M[i];
        }
       
        sum += day;
        return sum;
    }
   
    public static void main(String[] args){
        System.out.println(day_dif(1979,12,15,2015,3,2));
    }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
// 日期差问题
// 2015-3-2 距离 1979-12-15 多少天?
// 日期表示法?? 距离基点的天数


int day_dif(int year1, int month1, int day1,int year2, int month2, int day2)
{
    return get_days(year2, month2, day2)- get_days(year1, month1, day1);

}

int is_leap_year(int year)
{
    int tag = 0;
    if (year % 4 == 0)
        tag = 1;
    if (year % 100 == 0)
        tag = 1;
    if (year % 400 == 0)
        tag = 1;
    return tag;
}

int get_days(int year, int month, int day)
{
    int M[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
    if (is_leap_year(year))
        M[2]++;

    int sum = 0;
    for (int i = 1; i < year; i++)
    {
        sum += 365;
        if (is_leap_year(i))
            sum++;
    }

    for (int i = 1; i < month; i++)
    {
        sum += M[i];
    }

    sum += day;
    return sum;
}
void main7()
{
    printf("%d\n", day_dif(1979, 12, 15, 2015, 3, 2));
}


2. excel地址
Excel单元格的地址表示很有趣,它使用字母来表示列号,比如:
A表示第1列,
B表示第2列,
Z表示第26列,
AA表示第27列,
AB表示第28列,
BA表示第53列,
….
当然Excel的最大列号是有限度的,所以转换起来不难。
如果我们想把这种表示法一般化,可以把很大的数字转换为很长的字母序列呢?

本题目既是要求对输入的数字, 输出其对应的Excel地址表示方式。

例如,
输入:
26
则程序应该输出:
Z

再例如,
输入:
2054
则程序应该输出:
BZZ

我们约定,输入的整数范围[1,2147483647]

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class A
{
    // n 转换为excel列地址
    static String f(int n){
        for(int i=0; i<=26; i++)
        for(int j=(i==0)?0:1; j<=26; j++)
        for(int k=(j==0)?0:1; k<=26; k++){ int x = i*26*26 + j*26 + k; if(x==n){ String s =""; if(i>0) s += (char)(i-1+'A');
                if(j>0) s += (char)(j-1+'A');
                if(k>0) s += (char)(k-1+'A');              
                return s;
            }
        }
        return "";
    }
   
    public static void main(String[] args){
        for(int i=700; i<750; i++){
            System.out.println(i + ": " + f(i));
        }
    }
}

public class B
{
    // excel列地址转换为n
    static int f(String s){
        int n = 0;
        for(int i=0; i<s.length(); i++){
            n = n * 26 + (s.charAt(i)-'A' + 1);
        }
        return n;
    }
   
    public static void main(String[] args){
        System.out.println(f("AA"));
        System.out.println(f("BA"));
        System.out.println(f("ZZ"));
        System.out.println(f("AAA"));
    }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>
#include <stdlib.h>

// n 转换为excel列地址
char * f(int n)
{
    for (int i = 0; i <= 26; i++)
        for (int j = (i == 0) ? 0 : 1; j <= 26; j++)
            for (int k = (j == 0) ? 0 : 1; k <= 26; k++)
            {
                int x = i * 26 * 26 + j * 26 + k;
                if (x == n)
                {


                    char *p = (char*)malloc(4);
                    memset(p, 0, 4);
                    int len = 0;
                    if (i)
                    {
                        p[len] = (char)(i + 'A' - 1);
                        len++;
                    }
                    if(j)
                    {
                        p[len] = (char)(j + 'A' - 1);
                        len++;
                    }
                    if (k)
                    {
                        p[len] = (char)(k + 'A' - 1);
                        len++;
                    }
                    return p;
                }
            }  

}

void main1()
{
    for (int i = 700; i < 750; i++){
        printf("%d :%s\n",i,f(i));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
   
// excel列地址转换为n
int ff(char *s,int len)
{
    int n = 0;
    for (int i = 0; i < len; i++)
    {
        n = n * 26 + (s[i] - 'A' + 1);
    }
    return n;
}

void main13()
{
    printf("%d\n", ff("AA", 2));
    printf("%d\n", ff("BA", 2));
    printf("%d\n", ff("ZZ", 2));
    printf("%d\n", ff("AAA", 3));
}

3. 取球博弈
今盒里有n个小球,A、B两人轮流从盒中取球。
每个人都可以看到另一个人取了多少个,也可以看到盒中还剩下多少个。
两人都很聪明,不会做出错误的判断。

每个人从盒子中取出的球的数目必须是:1,3,7或者8个。
轮到某一方取球时不能弃权!
A先取球,然后双方交替取球,直到取完。

被迫拿到最后一个球的一方为负方(输方)

编程确定出在双方都不判断失误的情况下,对于特定的初始球数,A是否能赢?
【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class A
{
    static boolean f(int n){
        if(n==0) return true;
       
        if(n>=1 && f(n-1)==false) return true;
        if(n>=3 && f(n-3)==false) return true;
        if(n>=7 && f(n-7)==false) return true;
        if(n>=8 && f(n-8)==false) return true;
       
        return false;
    }
   
    public static void main(String[] args){
        for(int i=1; i<=50; i++){
            System.out.println(i + ": " + f(i));
        }
    }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include<string.h>

int fff(int n)
{
    if (n == 0)
        return 1;

    if (n >= 1 && fff(n - 1) == 0)
        return 1;
    if (n >= 3 && fff(n - 3) == 0)
        return 1;
    if (n >= 7 && fff(n - 7) == 0)
        return 1;
    if (n >= 8 && fff(n - 8) == 0)
        return 1;

    return 0;
}

void main2()
{
    for (int i = 1; i <= 50; i++){
        printf("%d : %s\n", i, fff(i)?"true": "false");
    }
}


4. 填字母游戏
K大师在纸上画了一行n个格子,要小明和他交替往其中填入字母。
1. 轮到某人填的时候,只能在某个空格中填入L或O
2. 谁先让字母组成了“LOL”的字样,谁获胜。
3. 如果所有格子都填满了,仍无法组成LOL,则平局。

小明试验了几次都输了,他很惭愧,希望你能用计算机帮他解开这个谜。

本题的输入格式为:
第一行,数字n(n<10),表示下面有n个初始局面。
接下来,n行,每行一个串,表示开始的局面。
比如:“******”, 表示有6个空格。“L****”, 表示左边是一个字母L,它的右边是4个空格。

要求输出n个数字,表示对每个局面,如果小明先填,当K大师总是用最强着法的时候,小明的最好结果。
1 表示能赢
-1 表示必输
0 表示可以逼平

例如,
输入:
4
***
L**L
L**L***L
L*****L

则程序应该输出:
0
-1
1
1
【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
import java.util.*;

public class A
{
    // -1: 必输,0: 平局, 1: 必赢
    static int f(char[] x)
    {
        String s = new String(x);      
        if(s.contains("LOL")) return -1;
        if(s.contains("*")==false) return 0;
       
        boolean ping = false;  // 假设无法平局
       
        for(int i=0; i<x.length; i++){
            if(x[i]=='*'){
                try{
                    x[i]='L';  //试着填L
                    switch(f(x)){
                        case -1: return 1;
                        case 0: ping = true;
                    }
                    x[i]='O';  //试着填O
                    switch(f(x)){
                        case -1: return 1;
                        case 0: ping = true;
                    }
                }
                finally{           
                    x[i]='*';
                }
            }
        }
       
        if(ping) return 0;
        return -1;
    }
   
    static int game(String s)
    {
        return f(s.toCharArray());
    }
   
    public static void main(String[] args)
    {  
        System.out.println(game("***"));
        System.out.println(game("L**L"));
        System.out.println(game("L**L***L"));
        System.out.println(game("L*****L"));
    }
}

import java.util.*;

public class LOL
{
    static Map<String, Integer> map = new HashMap<String, Integer>();
   
    // -1: 必输,0: 平局, 1: 必赢
    static int f(char[] x)
    {
        String s = new String(x);
        if(map.get(s) != null) return map.get(s);
       
        if(s.contains("LOL")) {
            map.put(s,-1);
            return -1;
        }
        if(s.contains("*")==false) {
            map.put(s,0);
            return 0;
        }
       
        boolean ping = false;
       
        for(int i=0; i<x.length; i++){
            if(x[i]=='*'){
                try{
                    x[i]='L';
                    {
                        int t = f(x);
                        if(t<0) {
                            map.put(s,1);
                            return 1;
                        }
                        if(t==0) ping = true;
                    }
                    x[i]='O';
                    {
                        int t = f(x);
                        if(t<0) {
                            map.put(s,1);
                            return 1;
                        }
                        if(t==0) ping = true;
                    }      
                }
                finally{           
                    x[i]='*';
                }
            }
        }
       
        if(ping){
            map.put(s,0);
            return 0;
        }
       
        map.put(s,-1);
        return -1;
    }
   
    static int game(String s)
    {
        map.clear();
        return f(s.toCharArray());
    }
   
    public static void main(String[] args)
    {  
        Scanner scan = new Scanner(System.in);
       
        int n = Integer.parseInt(scan.nextLine().trim());
        for(int i=0; i<n; i++){
            System.out.println(game(scan.nextLine().trim()));
        }
    }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include<string.h>

// -1: 必输,0: 平局, 1: 必赢
int f3(char* x, int len)
{
    char *p = (char *)malloc(len);
    memset(p, 0, len);
    strcpy(p, x);

    if (strstr(p,"LOL"))
        return -1;
    if (!strstr(p,"*"))
        return 0;

    int  ping = 0;  // 假设无法平局

    for (int i = 0; i < len; i++)
    {
        if (p[i] == '*')
        {
           
                p[i] = 'L';  //试着填L
                switch (f3(p, len))
                {
                    case -1:
                        return 1;
                    case 0:
                        ping = 1;
                }
                p[i] = 'O';  //试着填O
                switch (f3(p, len))
                {
                    case -1:
                        return 1;
                    case 0:
                        ping = 1;
                }              
                p[i] = '*';
        }
    }
    if (ping)
        return 0;
    return -1;
}

int game(char * s)
{
    int len = strlen(s) + 1;
    int bool=f3(s, len);
    return bool;
}

void main31()
{
    printf("%d \n",game("***"));
    printf("%d \n", game("L**L"));
    printf("%d \n", game("L**L***L"));
    printf("%d \n", game("L*****L"));
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include<string.h>

typedef struct MyNode
{
    char*s1;
    int num;
    struct MyNode*pNext;
}MyNode;
MyNode *pHead = NULL;
MyNode *pTail = NULL;

void put(char*s,int x)
{
    MyNode*pNode = (MyNode*)malloc(sizeof(MyNode));
    pNode->num = x;
    int len = strlen(s);
    pNode->s1 = malloc(len);
    memset(pNode->s1, 0, len);
    strcpy(pNode->s1, s);
    pNode->pNext = NULL;

    if (pHead == NULL)
    {
        pHead = pNode;
        pTail = pNode;
    }
    else
    {
        pTail->pNext = pNode;
        pTail = pNode;
    }
}
struct flag
{
    int f;
    int num;
};

struct flag get(char *s)
{
    struct flag f1;
    f1.f = 0;

    MyNode * pTemp = pHead;
    while (pTemp)
    {
        if (!strcmp(pTemp->s1, s))
        {
            f1.f = 1;
            f1.num=pTemp->num;
        }
        pTemp = pTemp->pNext;
    }
    return f1;
}


// -1: 必输,0: 平局, 1: 必赢
int fn(char *x,int len)
{
    char *pc = (char*)malloc(len);
    memset(pc, 0, len);
    strcpy(pc, x);

    struct flag g = get(pc);
    if (g.f)
        return g.num;

    if (strstr(pc,"LOL"))
    {
        put(pc, -1);
        return -1;
    }


    if (!strstr(pc, "*"))
    {
        put(pc, 0);
        return 0;
    }

    int  ping = 0;
    for (int i = 0; i < len; i++)
    {
        if (x[i] == '*')
        {
                x[i] = 'L';
                {
                    int t = fn(x,len);
                    x[i] = '*';
                    if (t < 0)
                    {
                        put(pc, 1);
                        return 1;
                    }                      
                    if (t == 0)
                        ping = 1;
                }

                x[i] = 'O';
                {
                    int t = fn(x,len);
                    x[i] = '*';
                    if (t < 0)
                    {
                        put(pc, 1);
                        return 1;
                    }
                    if (t == 0)
                        ping = 1;
                }
        }
    }

    if (ping)
    {
        put(pc, 0);
        return 0;
    }

    put(pc, -1);
    return -1;
}

int myGame(char* s,int len)
{
    pHead = NULL;
    return fn(s,len);
}
void main()
{
    int n = 0;
    char arr[1024] = { 0 };
    scanf("%d",&n);
    for (int i = 0; i < n; i++)
    {
        scanf("%s", arr);
        int len = strlen(arr);
        int x = myGame(arr, len);
        printf("%d \n", x);
    }
}


5. 高僧斗法
古时丧葬活动中经常请高僧做法事。
仪式结束后,有时会有“高僧斗法”的趣味节目,以舒缓压抑的气氛。

节目大略步骤为:先用粮食(一般是稻米)在地上“画”出若干级台阶(表示N级浮屠)。
又有若干小和尚随机地“站”在某个台阶上。
最高一级台阶必须站人,其它任意。(如图所示)

两位参加斗法的法师分别指挥某个小和尚向上走任意多级的台阶,但会被站在高级台阶上的小和尚阻挡,不能越过。
两个小和尚也不能站在同一台阶,也不能向低级台阶移动。

两法师轮流发出指令,最后所有小和尚必然会都挤在高段台阶,再也不能向上移动。
轮到哪个法师指挥时无法继续移动,则游戏结束,该法师认输。

对于已知的台阶数和小和尚的分布位置,请你计算先发指令的法师该如何决策才能保证胜出。

输入数据为一行用空格分开的N个整数,表示小和尚的位置。台阶序号从1算起,所以最后一个小和尚的位置即是台阶的总数。(N<100, 台阶总数<1000)

输出为一行用空格分开的两个整数: A B, 表示把A位置的小和尚移动到B位置。
若有多个解,输出A值较小的解,若无解则输出-1。

例如:
用户输入:
1 5 9
则程序输出:
1 4

再如:
用户输入:
1 5 8 10
则程序输出:
1 3

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 组合博弈论....转化为尼姆堆
import java.util.*;
public class A
{
    static boolean f(int[] x)
    {
        int sum = 0;
        for(int i=0; i<x.length-1; i+=2){ sum ^= x[i+1] - x[i] - 1; // 两人一组间的空台阶数===>尼姆堆
        }
        return sum != 0;
    }
   
    static void solve(int[] x)
    {
        for(int i=0; i<x.length-1; i++){
            for(int k=x[i]+1; k<x[i+1]; k++){
                int old = x[i];  //试着走
                try{
                    x[i] = k;
                    if(f(x)==false) {
                        System.out.println(old + " " + k);
                        return;
                    }
                }
                finally{
                    x[i] = old; //回溯
                }
            }
        }
    }
   
    public static void main(String[] args)
    {  
        solve(new int[]{1,5,9});
        solve(new int[]{1,5,8,10});
        solve(new int[]{1,4,8,12,16,19,28,33,35,36,40,45,52,66,67,68,69,77
          ,85,99,102,134,155,211,214,216,355,376,400,412});
    }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
// 组合博弈论....转化为尼姆堆

int f4(int* x,int len)
{
    int sum = 0;
    for (int i = 0; i < len - 1; i += 2) { sum ^= x[i + 1] - x[i] - 1; // 两人一组间的空台阶数===>尼姆堆
    }
    return sum != 0;
}

void solve(int* x,int len)
{
    for (int i = 0; i < len - 1; i++)
    {
        for (int k = x[i] + 1; k < x[i + 1]; k++){
            int old = x[i];  //试着走
            {
                x[i] = k;
                if (!f4(x,len))
                {
                    printf("%d %d\n",old,k);
                    return;
                }
            }
           
            x[i] = old; //回溯
           
        }
    }
}

void main4()
{
    int x[] = { 1, 5, 9 };
    solve(x,3);
    int y[] = { 1, 5, 8, 10 };
    solve(y,4);
    int z[] = { 1, 4, 8, 12, 16, 19, 28, 33, 35, 36, 40, 45, 52, 66, 67, 68, 69, 77, 85, 99, 102, 134, 155, 211, 214, 216, 355, 376, 400, 412 };
    solve(z,30);
}


6. 古代赌局
俗话说:十赌九输。因为大多数赌局的背后都藏有阴谋。
不过也不尽然,有些赌局背后藏有的是:“阳谋”。

有一种赌局是这样的:桌子上放六个匣子,编号是1至6。
多位参与者(以下称玩家)可以把任意数量的钱押在某个编号的匣子上。
所有玩家都下注后,庄家同时掷出3个骰子(骰子上的数字都是1至6)。
输赢规则如下:

1.若只有1个骰子上的数字与玩家所押注的匣子号相同,则玩家拿回自己的押注,庄家按他押注的数目赔付(即1比1的赔率)。
2.若2个骰子上的数字与玩家所押注的匣子号相同,则玩家拿回自己的押注,庄家按他押注的数目的2倍赔付(即1比2的赔率)。
3.若3个骰子上的数字都与玩家押注的匣子号相同,则玩家拿回自己的押注,庄家按他押注的数目的10倍赔付(即1比10的赔率)。

乍一看起来,好像规则对玩家有利,庄家吃亏。但经过大量实战,会发现局面很难说,于是怀疑是否庄家做了手脚,庄家则十分爽快地说:可以由玩家提供骰子,甚至也可以由玩家来投掷骰子。

你的任务是:通过编程模拟该过程。模拟50万次,假定只有1个玩家,他每次的押注都是1元钱,其押注的匣子号是随机的。再假定庄家有足够的资金用于赔付。最后计算出庄家的盈率(庄家盈利金额/押注总金额)。

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class DuJu
{
    public static double f()
    {
        int a = (int)(Math.random() * 6) + 1;
        int b = (int)(Math.random() * 6) + 1;
        int c = (int)(Math.random() * 6) + 1;
       
        int w = (int)(Math.random() * 6) + 1;
       
        int n = 0;
        if(a==w) n++;
        if(b==w) n++;
        if(c==w) n++;
       
        if(n==3) return -10;
        if(n==2) return -2;
        if(n==1) return -1;
       
        return 1;
    }
   
    public static void main(String[] args)
    {
        int N = 500*1000;
       
        double sum = 0;
        for(int i=0; i<N; i++)
        {
            sum += f();
        }
       
        System.out.println(sum/N);
    }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
     double f5()
    {
         int a = (int)(rand() / (RAND_MAX + 0.0) * 6) + 1;
         int b = (int)(rand() / (RAND_MAX + 0.0) * 6) + 1;
         int c = (int)(rand() / (RAND_MAX + 0.0) * 6) + 1;

         int w = (int)(rand() / (RAND_MAX + 0.0) * 6) + 1;

        int n = 0;
        if (a == w) n++;
        if (b == w) n++;
        if (c == w) n++;

        if (n == 3) return -10;
        if (n == 2) return -2;
        if (n == 1) return -1;

        return 1;
    }

    void main5()
    {
        int N = 500 * 1000;

        double sum = 0;
        for (int i = 0; i < N; i++)
        {
            sum += f5();
        }

        printf("%f \n", sum / N);

    }


7. 火柴游戏
这是一个纵横火柴棒游戏。
如图1,在3×4的格子中,游戏的双方轮流放置火柴棒。
其规则是:
1. 不能放置在已经放置了火柴棒的地方(即只能在空格中放置)。
2. 火柴棒的方向只能是竖直或水平放置。
3. 火柴棒不能与其它格子中的火柴“连通”。
所谓连通是指两根火柴棒可以连成一条直线,且中间没有其它不同方向的火柴“阻拦”。
例如:
火柴游戏.jpg

图1

图1所示的局面下,可以在C2位置竖直放置(为了方便描述格子位置,图中左、下都添加了标记),但不能水平放置,因为会与A2连通。
同样道理,B2,B3,D2此时两种方向都不可以放置。
但如果C2竖直放置后,D2就可以水平放置了,因为不再会与A2连通(受到了C2的阻挡)。
4. 游戏双方轮流放置火柴,不可以弃权,也不可以放多根。

如某一方无法继续放置,则该方为负(输的一方)。

游戏开始时可能已经放置了多根火柴。
你的任务是:编写程序,读入初始状态,计算出对自己最有利的放置方法并输出放置后的局面。
图1的局面表示为:
00-1
-000
0100
即用“0”表示空闲位置,用“1”表示竖直放置,用“-”表示水平放置。

解法不唯一,找到任意解法即可。

例如,局面:
0111
-000
-000
的解:
-111
-000
-000

再例如,局面:
1111
—-
0010
的解:
1111
—-
0110

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import java.util.*;
public class A
{
    static void show(char[][] data){
        System.out.println();
        for(int i=0; i<data.length; i++){
            System.out.println(new String(data[i]));
        }
    }
   
    static boolean f(char[][] data){       
        for(int i=0; i<data.length; i++){
            String s = new String(data[i]).replaceAll("0","");
            if(s.contains("--")) return true;
        }
       
        for(int i=0; i<data[0].length; i++){
            String s = ("" + data[0][i] + data[1][i] + data[2][i]).replaceAll("0","");
            if(s.contains("11")) return true;
        }  
       
        for(int i=0; i<data.length; i++){
            for(int j=0; j<data[i].length; j++){
                if(data[i][j]=='0'){
                    try{
                        data[i][j] = '1';
                        if(f(data)==false) return true;
                        data[i][j] = '-';
                        if(f(data)==false) return true;
                    }
                    finally{
                        data[i][j] = '0';
                    }
                }
            }
        }
   
        return false;
    }
   
    static void solve(char[][] data){
        for(int i=0; i<data.length; i++){
            for(int j=0; j<data[i].length; j++){
                if(data[i][j]=='0'){
                    try{
                        data[i][j] = '1';
                        if(f(data)==false) {
                            show(data);
                            //return
                        }
                        data[i][j] = '-';
                        if(f(data)==false){
                            show(data);
                            //return;
                        }
                    }
                    finally{
                        data[i][j] = '0';
                    }
                }
            }
        }
    }
   
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
       
        char[][] data = new char[3][];
        data[0] = scan.nextLine().trim().toCharArray();
        data[1] = scan.nextLine().trim().toCharArray();
        data[2] = scan.nextLine().trim().toCharArray();
       
        solve(data);
        //System.out.println(f(data));
    }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
void show(char* data[],int len1)
{
    printf("\n");
    for (int i = 0; i < len1; i++)
    {
        printf("%s\n", data[i]);
    }
}

int f6(char* data[], int len1)
{

    for (int i = 0; i < len1; i++)
    {
        int len2 = strlen(data[i]);
        char*p = (char*)malloc(len2 + 1);
        memset(p, 0, len2);

        int lenOfP = 0;
        for (int j = 0; j < len2;j++)
        {
            if (data[i][j]!='0')
            {
                p[lenOfP] = data[i][j];
                lenOfP++;
            }
        }
        if (strstr(p,"--"))
        {
            return 1;
        }
    }

    int lenth = strlen(data[0]);
    for (int i = 0; i < lenth; i++)
    {
        char*p = (char*)malloc(3);
        p[0] = data[0][i];
        p[1] = data[1][i];
        p[2] = data[2][i];


        int lenOfP = 0;
        for (int j = 0; j < 3; j++)
        {
            if (data[j][i] != '0')
            {
                p[lenOfP] = data[j][i];
                lenOfP++;
            }
        }
        if (strstr(p, "11"))
            return 1;
    }

    for (int i = 0; i < len1; i++)
    {

        int len2 = strlen(data[i]);
        for (int j = 0; j < len2; j++)
        {
            if (data[i][j] == '0')
            {
                {
                    data[i][j] = '1';
                    if (f6(data,len1) == 0)
                        return 1;
                    data[i][j] = '-';
                    if (f6(data,len1) == 0)
                        return 1;
                }
                {
                    data[i][j] = '0';
                }
            }
        }
    }

    return 0;
}

void solve6(char* data[],int len1)
{
    for (int i = 0; i < len1; i++)
    {
        int len2 = strlen(data[i]);
        for (int j = 0; j < len2; j++)
        {
            if (data[i][j] == '0'){
                {
                    data[i][j] = '1';
                    if (f6(data, len1) == 0)
                    {
                        show(data,len1);
                        //return
                    }
                    data[i][j] = '-';
                    if (f6(data, len1) == 0){
                        show(data, len1);
                        //return;
                    }
                }
                {
                    data[i][j] = '0';
                }
            }
        }
    }
}

void main6()
{
    char *data[3] = { NULL };
    for (int i = 0; i<3; i++)
    {
        data[i] = malloc(1024);
        memset(data[i], 0, 1024);

        scanf("%s", data[i]);
    }
           
    solve6(data,3);

    //System.out.println(f6(data));
}


如果您需要更多课程内容和讲解视频,请联系小蓝


蓝桥杯算法特训第四课【数学知识的运用】源代码

【内容简介】
本文章内容为【2018蓝桥杯大赛算法特训(软件)系列课程】第四课【数学知识的运用】中涉及到的课上例题的代码实现,加入赛前算法特训获取全部课程内容请联系【小蓝】。


【课程中涉及的源代码】
1. 奇怪的捐赠
地产大亨Q先生临终的遗愿是:拿出100万元给X社区的居民抽奖,以稍慰藉心中愧疚。
麻烦的是,他有个很奇怪的要求:

  1. 100万元必须被正好分成若干份(不能剩余)。每份必须是7的若干次方元。比如:1元, 7元,49元,343元,…
  2. 相同金额的份数不能超过5份。
  3. 在满足上述要求的情况下,分成的份数越多越好!

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class A
{
    public static void main(String[] args){
        // 直接求一个数字的7进制表示
        // 如果没有函数,可以自己用长除法取余数的方式
        String s = Integer.toString(1000*1000,7);
        int sum=0;
        for(int i=0; i<s.length(); i++){
            sum += s.charAt(i)-'0';
        }
        System.out.println(s);
        System.out.println("result=" + sum);
    }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <stdlib.h>
#include <string.h>

void main1()
{
    // 直接求一个数字的7进制表示
    // 如果没有函数,可以自己用长除法取余数的方式
    char arr[1024] = { 0 };
    _itoa(1000 * 1000, arr, 7);
    int sum = 0;

    for (int i = 0; i < strlen(arr); i++)
    {
        sum += arr[i] - '0';
    }
    printf("%s\n", arr);
    printf("result=%d", sum);
}


2. 天平称重
【问题描述】
用天平称重时,我们希望用尽可能少的砝码组合称出尽可能多的重量。
如果只有5个砝码,重量分别是1,3,9,27,81
则它们可以组合称出1到121之间任意整数重量(砝码允许放在左右两个盘中)。

本题目要求编程实现:对用户给定的重量,给出砝码组合方案。
例如:
用户输入:
5
程序输出:
9-3-1
用户输入:
19
程序输出:
27-9+1

要求程序输出的组合总是大数在前小数在后。
可以假设用户的输入的数字符合范围1~121。

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 天平称重,递归解法
public class A
{
    // 把s中的符号取反(+变-,-变+)
    static String reve(String s){
        s = s.replace('-','#');
        s = s.replace('+','-');
        s = s.replace('#','+');
        return "-" + s;
    }
   
    static String f(int x){
        int a = 1;
        while(a<x) a *= 3;
       
        if(a==x) return "" + a;
       
        if(x<=a/2) return a/3 + "+" + f(x-a/3);
       
        return a + reve(f(a-x));
    }
   
    public static void main(String[] args){
        for(int i=1; i<100; i++){ System.out.println(i + ": " + f(i)); } } } // 天平称重,进制解法 public class B { static String f(int n){ String s = ""; int q = 1; //位权重 while(n>0){
            int sh = n/3; //商
            if(n%3 == 1) s = "+" + q + s;
            if(n%3 == 2){
                sh++;
                s = "-" + q + s;
            }
           
            n = sh;
            q *= 3;
        }  
       
        return s.substring(1);
    }
       
    public static void main(String[] args){
        for(int i=1; i<100; i++){
            System.out.println(i + ": " + f(i));
        }
    }
}

【C语言:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <stdlib.h>
#include <string.h>

// 天平称重,递归解法

// 把s中的符号取反(+变-,-变+)
    char* reve(char *s)
    {
        int n = strlen(s);
        for (int i = 0; i < n;i++)
        {
            if (s[i]=='-')
            {
                s[i] = '+';
            }
            else if (s[i]=='+')
            {
                s[i] = '-';
            }
        }

        char *p = (char *)malloc(n + 2);
        memset(p, 0, n + 2);
        p[0] = '-';
        strcat(p, s);

        return p;
    }

    char* f(int x)
    {
        char *p = (char *)malloc(1024);
        memset(p, 0, 1024);

        int a = 1;
        while (a < x)
            a *= 3;

        if (a == x)
        {
            _itoa(a, p, 10);
            return p;
        }
           
        if (x <= a / 2)
        {
            int m = x - a / 3;
            char *p1 = f(m);
            _itoa(a/3, p, 10);
            strcat(p, "+");
            return strcat(p, p1);
        }
        char *h = reve(f(a - x));
        _itoa(a, p, 10);
        strcat(p, h);
        return p;
    }

    void main21(){
        for (int i = 1; i < 100; i++)
        {
            char*p=f(i);
            printf("%d : %s\n", i, p);
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <stdlib.h>
#include <string.h>
// 天平称重,进制解法
   
char * f2(int n){
    char*p = (char*)malloc(1024);
    memset(p, 0, 1024);


    int q = 1; //位权重
    while (n > 0){
        int sh = n / 3; //商
        if (n % 3 == 1)
        {

            char arr[1024] = { 0 };
            strcpy(arr, p);
            memset(p, 0, 1024);

            strcat(p, "+");

            char arr1[1024] = { 0 };
            _itoa(q, arr1, 10);
            strcat(p, arr1);

            strcat(p, arr);
        }

        if (n % 3 == 2)
        {
            sh++;

            char arr[1024] = { 0 };
            strcpy(arr, p);
            memset(p, 0, 1024);

            strcat(p, "-");

            char arr1[1024] = { 0 };
            _itoa(q, arr1, 10);
            strcat(p, arr1);

            strcat(p, arr);
        }

        n = sh;
        q *= 3;
    }

    return p+1;
}

void main22(){
    for (int i = 1; i < 100; i++)
    {
        char*p = f2(i);
        printf("%d : %s\n", i, p);
    }
}


3. 尼姆堆
【问题描述】
有3堆硬币,分别是3,4,5
二人轮流取硬币。
每人每次只能从某一堆上取任意数量。
不能弃权。
取到最后一枚硬币的为赢家。

求先取硬币一方有无必胜的招法。

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 尼姆堆的模2加(异或)解法
/*
    10
   101
  1100
  1110
--------
  0101  
*/

public class A
{
    static void f(int[] a){
        int sum = 0;
        for(int i=0; i<a.length; i++){
            sum ^= a[i];
        }
        if(sum==0){
            System.out.println("输了");
            return;
        }
       
        for(int i=0; i<a.length; i++){
            int x = sum ^ a[i];
            if(x<a[i]) System.out.println(a[i] + " --> " + x);
        }
    }
   
    public static void main(String[] args){
        int[] a = {2,5,12,14};
        f(a);
    }
}

【C语言:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <stdlib.h>
#include <string.h>

// 尼姆堆的模2加(异或)解法
/*
10
101
1100
1110
--------
0101
*/


    void f3(int* a,int len)
    {
        int sum = 0;
        for (int i = 0; i<len; i++)
        {
            sum ^= a[i];
        }
        if (sum == 0)
        {
            printf("输了\n");
            return;
        }

        for (int i = 0; i<len; i++)
        {
            int x = sum ^ a[i];
            if (x < a[i]) printf("%d --> %d\n", a[i], x);
        }
    }

    void main3()
    {
        int a[] = { 2, 5, 12, 14 };
        f3(a,4);
    }


4. 公约公倍
【问题描述】
如果两个数很大,怎样求最大公约数,最小公倍数?
如果是n个数呢?比如1000个数的最小公倍数

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
   辗转相除法
   欧几里得定理 gcd(A,B) = gcd(B,A%B)
   算数基本定理:质因数分解的唯一性
     n = p1^n1 * p2^n2 * ...
*/


public class A
{
    static int gcd(int a, int b){
        if(b==0) return a;
        return gcd(b, a%b);
    }
   
    static int lcm(int a, int b){
        return a * b / gcd(a,b);
    }
   
    public static void main(String[] args){
        System.out.println(gcd(42,60));
        System.out.println(lcm(42,60));
    }
}

【C语言:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <stdlib.h>
#include <string.h>
/*
辗转相除法
欧几里得定理 gcd(A,B) = gcd(B,A%B)
算数基本定理:质因数分解的唯一性
n = p1^n1 * p2^n2 * ...
*/

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a%b);
}

int lcm(int a, int b)
{
    return a * b / gcd(a, b);
}

void main4()
{
    printf("%d\n", gcd(42, 60));
    printf("%d\n", lcm(42, 60));

}


5. 一步之遥
【问题描述】
从昏迷中醒来,小明发现自己被关在X星球的废矿车里。
矿车停在平直的废弃的轨道上。
他的面前是两个按钮,分别写着“F”和“B”。

小明突然记起来,这两个按钮可以控制矿车在轨道上前进和后退。
按F,会前进97米。按B会后退127米。
透过昏暗的灯光,小明看到自己前方1米远正好有个监控探头。
他必须设法使得矿车正好停在摄像头的下方,才有机会争取同伴的援助。
或许,通过多次操作F和B可以办到。

矿车上的动力已经不太足,黄色的警示灯在默默闪烁…
每次进行 F 或 B 操作都会消耗一定的能量。
小明飞快地计算,至少要多少次操作,才能把矿车准确地停在前方1米远的地方。

请填写为了达成目标,最少需要操作的次数。

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
  解不定方程
  97x + 127y = 1
 
  欧几里得定理 ---- 辗转相除法  gcd
  扩展欧几里得定理
  Ax + By = gcd(A,B)
  理论基础: gcd(A,B) == gcd(B,A%B)
 
  求出特解后,通解很好表示
 
  Ax + By = gcd(A,B)
  Ax + By = gcd(B,A%B)
  B(A/B x + y) + (A%B)x = gcd(B,A%B)
  对比:
  A/B x + y = 新x
  x = 新y
*/


public class A
{
    // 返回最大公约数
    // xy: 顺便解出的xy
    static int e_gcd(int A, int B, int[] xy)
    {
        if(B==0){
            xy[0] = 1;
            xy[1] = 0;
            return A;
        }
       
        int ans = e_gcd(B, A%B, xy);
        int t = xy[0];
        xy[0] = xy[1];
        xy[1] = t - A/B * xy[0];
        return ans;
    }
   
    public static void main(String[] args)
    {
        int[] xy = new int[2];
        int a = e_gcd(97,127,xy);
       
        System.out.println(a);
        System.out.println(xy[0] + " " + xy[1]);   
    }
}

【C语言:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <stdlib.h>
#include <string.h>
/*
解不定方程
97x + 127y = 1

欧几里得定理 ---- 辗转相除法  gcd
扩展欧几里得定理
Ax + By = gcd(A,B)
理论基础: gcd(A,B) == gcd(B,A%B)

求出特解后,通解很好表示

Ax + By = gcd(A,B)
Ax + By = gcd(B,A%B)
B(A/B x + y) + (A%B)x = gcd(B,A%B)
对比:
A/B x + y = 新x
x = 新y
*/


// 返回最大公约数
// xy: 顺便解出的xy
int e_gcd(int A, int B, int* xy,int len)
{
    if (B == 0)
    {
        xy[0] = 1;
        xy[1] = 0;
        return A;
    }

    int ans = e_gcd(B, A%B, xy,len);
    int t = xy[0];
    xy[0] = xy[1];
    xy[1] = t - A / B * xy[0];
    return ans;
}

void main5()
{
    int* xy =(int *) malloc(sizeof(int)*2);
    int a = e_gcd(97, 127, xy,2);
    printf("%d \n", a);
    printf("%d " " %d \n", xy[0], xy[1]);
}


6. 有理数
【问题描述】
如果求 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + …. + 1/100 = ?
要求绝对精确,不能有误差。

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
public class A
{
    public static void main(String[] args){
        Rati x = new Rati(1,3).add(new Rati(1,6));
        System.out.println(x);
    }
}

【C语言:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Rati
{
    long zi;
    long mu;
}Rati;

long gcd1(long a, long b)
{
    if (b==0)
        return a;
    return gcd1(b, a%b);
}

Rati* add(Rati it1, Rati it2)
{
    Rati*p = (Rati*)malloc(sizeof(Rati));
    p->zi = it1.zi*it2.mu + it2.zi*it1.mu;
    p->mu = it1.mu*it2.mu;
    return p;

}

Rati* mul(Rati it1, Rati it2)
{
    Rati*p = (Rati*)malloc(sizeof(Rati));
    p->zi  = it1.zi*it2.zi;
    p->mu = it1.mu*it2.mu;
    return p;
}

//最大公约数
long gcd2(long a, long b)
{
    if (b == 0)
        return a;
    return gcd2(b, a%b);
}

void main()
{
    Rati*sum=(Rati*)malloc(sizeof(Rati));
    sum->zi = 0;
    sum->mu = 1;

    for (int i = 1; i <= 10; i++) { Rati*p = (Rati*)malloc(sizeof(Rati)); p->zi = 1;
        p->mu = i;
        sum = add(*sum,*p);
        long x = gcd2(sum->zi, sum->mu);
        sum->zi = sum->zi / x;
        sum->mu = sum->mu / x;
    }
    printf("1/2 + 1/3 + 1/4 + 1/5 + 1/6 +1/7 + 1/8 + 1/9 + 1/10 = ");
    printf("%d / %d ",sum->zi,sum->mu);
}


7. 素数
【问题描述】
第1个素数是2,第2个素数是3,…
求第100002(十万零二)个素数

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*
筛到第x个素数,需要数组准备多大?
素数分布定理:不大于n的素数的个数为:n / ln(n)
    double t = 100;
    while(t / Math.log(t) < x) t *= 1.1;
    System.out.println(t);
   
   
*/


public class SuShu
{
    public static void main(String[] args)
    {
        int N = 1500 * 1000;
        int x = 100002;
       
        byte[] a = new byte[N];
       
        for(int i=2; i<N/2; i++)
        {
            if(a[i]==1) continue; //越过已经找到的合数
            for(int k=2; k<=N/i; k++)
            {
                if(i*k<N) a[i*k] = 1;
            }
        }
       
       
        int m = 0;
        for(int i=2; i<N; i++)
        {
            if(a[i]==0)
            {
                m++;
                if(m==x) System.out.print(i + " ");
            }
        }
       
        System.out.println("m=" + m);
    }
}

【C语言:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <stdlib.h>
#include <string.h>

/*
筛到第x个素数,需要数组准备多大?
素数分布定理:不大于n的素数的个数为:n / ln(n)
double t = 100;
while(t / Math.log(t) < x) t *= 1.1;
System.out.println(t);
*/


void main()
{
    int N = 1500 * 1000;
    int x = 100002;

    int* a = (int *)malloc(N*sizeof(int)); 
    memset(a, 0, N*sizeof(int));
    for (int i = 2; i<N / 2; i++)
    {
        if (a[i] == 1)
            continue; //越过已经找到的合数
        for (int k = 2; k <= N / i; k++)
        {
            if (i*k<N)
                a[i*k] = 1;
        }
    }

    int m = 0;
    for (int i = 2; i<N; i++)
    {
        if (a[i] == 0)
        {
            m++;
            if (m == x)
                printf("%d \n",i);
        }
    }


    printf("m= %d" , m);
}


如果您需要更多课程内容和讲解视频,请联系小蓝

蓝桥杯算法特训第三课【典型问题的递归框架】源代码

【内容简介】
本文章内容为【2018蓝桥杯大赛算法特训(软件)系列课程】第三课【典型问题的递归框架】中涉及到的课上例题的代码实现,加入赛前算法特训获取全部课程内容请联系【小蓝】。


【课程中涉及的源代码】
1. 搭积木
【问题描述】
小明最近喜欢搭数字积木。一共有10块积木,每个积木上有一个数字,0~9。

搭积木规则:
每个积木放到其它两个积木的上面,并且一定比下面的两个积木数字小。
最后搭成4层的金字塔形,必须用完所有的积木。

下面是两种合格的搭法:

0
1 2
3 4 5
6 7 8 9

0
3 1
7 5 2
9 8 6 4

请你计算这样的搭法一共有多少种?

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/*
存储位置备忘
   0
  1 2
 3 4 5
6 7 8 9

*/

public class A
{
    static int N;
   
    static void show(int[] a)
    {
        System.out.println("   " + a[0]);
        System.out.println("  " + a[1] + " " + a[2]);
        System.out.println(" " + a[3] + " " + a[4] + " " + a[5]);
        System.out.println("" + a[6] + " " + a[7] + " " + a[8] + " " + a[9]);
        System.out.println();
    }
   
    static boolean near(int a, int b)
    {
        if(a+1==b || a==b+1) return true;
        return false;
    }
   
    static void test(int[] a)
    {
        if(a[1]<a[0]) return;
        if(a[2]<a[0]) return;
        if(a[3]<a[1]) return;
        if(a[4]<a[1]) return;
        if(a[4]<a[2]) return;
        if(a[5]<a[2]) return;
        if(a[6]<a[3]) return;
        if(a[7]<a[3]) return;
        if(a[7]<a[4]) return;
        if(a[8]<a[4]) return;
        if(a[8]<a[5]) return;
        if(a[9]<a[5]) return;
       
        show(a);
        N++;
    }
   
    // a: 待排元素
    // k: 当前考虑的位置
    static void f(int[] a, int k)
    {
        if(k==a.length-1){
            test(a);
            return;
        }
       
        for(int i=k; i<a.length; i++){
            {int t=a[i]; a[i]=a[k]; a[k]=t;}
            f(a,k+1);
            {int t=a[i]; a[i]=a[k]; a[k]=t;}
        }
    }
   
    public static void main(String[] args)
    {
        int[] a = {0,1,2,3,4,5,6,7,8,9};
       
        f(a,0);
       
        System.out.println("N= " + N);
    }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
存储位置备忘
0
1 2
3 4 5
6 7 8 9

*/


int N;

void show(int * a,int num)
{
    char * p = malloc((num+1)*sizeof(int));
    int t = 0;
    int flag = 0;

    for (int x = 0; x < 4;x++)
    {
        memset(p, 0, num);
        char ak[10] = { ' ' };
        for (t = 0; t < 3 - x;t++)
        {
            strcat(p, ak);
        }
       
       
        for (int y=0; y <= x; y++)
        {
           
            int x = a[flag];
            _itoa(x, p+t, 10);
           
            t++;
            flag++;
        }

        for (int v = 0; v < t; v++)
        {
            printf("%c ", p[v]);
            if (p[v]!=' ')
            {
                printf("%c ", ' ');
            }
           
        }
        printf("\n");
    }
    printf("\n\n\n");
}

int  near(int a, int b)
{
    if (a + 1 == b || a == b + 1)
        return 1;
    return 0;
}

void test(int *a,int num)
{
    if (a[1] < a[0]) return;
    if (a[2] < a[0]) return;
    if (a[3] < a[1]) return;
    if (a[4] < a[1]) return;
    if (a[4] < a[2]) return;
    if (a[5] < a[2]) return;
    if (a[6] < a[3]) return;
    if (a[7] < a[3]) return;
    if (a[7] < a[4]) return;
    if (a[8] < a[4]) return;
    if (a[8] < a[5]) return;
    if (a[9] < a[5]) return;

    show(a,10);
    N++;
}

//// a: 待排元素
//// k: 当前考虑的位置
void f(int *a,int num, int k)
{
    if (k == num-1){
        test(a,num);
        return;
    }

    for (int i = k; i < num; i++)
    {
        {
            int t = a[i];
            a[i] = a[k];
            a[k] = t;
        }
        f(a, num,k + 1);
        {int t = a[i]; a[i] = a[k]; a[k] = t; }
    }
}

  void main()
{
    int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13 };

    f(a, 10,0);
/*  System.out.println("N= " + N);*/
}


2. 代表团出访
【问题描述】

X星球要派出一个5人组成的观察团前往W星。
其中:
A国最多可以派出4人。
B国最多可以派出2人。
C国最多可以派出2人。
D国最多可以派出1人。
E国最多可以派出1人。
F国最多可以派出3人。
那么最终派往W星的观察团会有多少种国别的不同组合呢?
【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class A
{
    //a:可取最大个数的限定
    //k: 当前考虑位置
    //n: 目标名额
    //s: 已经决定的代表团成员
    public static void f(int[] a, int k, int n, String s)
    {
        if(k==a.length){
            if(n==0) System.out.println(s);
            return;
        }
       
        String s2 = s;
        for(int i=0; i<=a[k]; i++){
            f(a,k+1,n-i,s2);
            s2 += (char)(k+'A');
        }
    }
   
    public static void main(String[] args)
    {
        int[] a = {4,2,2,1,1,3};
       
        f(a,0,5,"");
    }
}

【C语言:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


    //a:可取最大个数的限定
    //k: 当前考虑位置
    //n: 目标名额
    //s: 已经决定的代表团成员
    void fk(int*a,int num1, int k, int n, char *s,int num2)
    {
        if (k == num1){
            if (n == 0)
                printf("%s\n",s);
            return;
        }
        char *s2 = malloc(sizeof(char)*num2);
        strcpy(s2, s);

        for (int i = 0; i <= a[k]; i++)
        {
            fk(a, num1, k + 1, n - i, s2, num2);
           
            char x=k + 'A';
            char arr[10] = { 0 };
            arr[0] = x;
            strcat(s2, arr);           
            num2++;
        }
    }

    void main()
    {
        int a[] = { 4, 2, 2, 1, 1, 3 };

        fk(a,6, 0, 5, "",0);
    }


3. 排列枚举
【问题描述】
已知不同字母构成的串,求它的全排列
【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.*;
public class A
{  
    static List f(String s){
        List lst = new Vector();
       
        if(s.length()==1){
            lst.add(s);
            return lst;
        }
       
        for(int i=0; i<s.length(); i++){
            char x = s.charAt(i);
            List t = f(s.substring(0,i)+s.substring(i+1));
            for(int k=0; k<t.size(); k++){
                lst.add("" + x + t.get(k));
            }
        }
       
        return lst;
    }

    public static void main(String[] args){
        List lst = f("ABC");
        for(int i=0; i<lst.size(); i++){
            System.out.println(lst.get(i));
        }
    }
}

// ABCDE 所有排列
public class B
{  
    // aa: 待排数据
    // k: 考虑的当前位置(数组下标)
    static void f(char[] aa, int k){
        if(k==aa.length-1){
            System.out.println(String.valueOf(aa));
            return;
        }
       
        for(int i=k; i<aa.length; i++){
            {char t=aa[k]; aa[k]=aa[i]; aa[i]=t;} // 试探
            f(aa,k+1);
            {char t=aa[k]; aa[k]=aa[i]; aa[i]=t;} // 回溯
        }
    }
   
    public static void main(String[] args){
        f("ABC".toCharArray(), 0);
    }
}

【C语言:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <string>
using namespace std;

void permute1(string prefix, string str)
{
    if (str.length() == 0)
        cout << prefix << endl;
    else
    {
        for (int i = 0; i < str.length(); i++)
            permute1(prefix + str[i], str.substr(0, i) + str.substr(i + 1, str.length()));
    }
}

void permute1(string s)
{
    permute1("", s);
}

void main()
{
    //method1, unable to remove duplicate permutations.
    permute1("ABC");
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;

void swap(char* x, char* y)
{
    char tmp;
    tmp = *x;
    *x = *y;
    *y = tmp;
}

/* Function to print permutations of string
This function takes three parameters:
1. String
2. Starting index of the string
3. Ending index of the string. */

void permute(char *a, int i, int n)
{
    int j;
    if (i == n)
        printf("%s\n", a);
    else
    {
        for (j = i; j <= n; j++)
        {
            if (a[i] == a[j] && j != i) //为避免生成重复排列,当不同位置的字符相同时不再交换
                continue;
            swap((a + i), (a + j));
            permute(a, i + 1, n);
            swap((a + i), (a + j)); //backtrack
        }
    }
}

int main42()
{
    //method2
    char a[] = "ABC";
    permute(a, 0, 2);
    return 0;
}


4. 组合
【问题描述】
有重复的字母中求取出m个所有组合

例如: “AAABBCCCCCCDD” 中取3个字母的所有组合
【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
public class A
{
    // m个不同的球中,取n个
    static int f(int m, int n){
        if(n==m) return 1;
        if(n==0) return 1;
        return f(m-1,n) + f(m-1,n-1);
    }
   
    public static void main(String[] args){
        System.out.println(f(5,3));
        System.out.println(f(5,2));
    }
}

// 固定数目的组合问题
// ABCDE 中取3个
public class B
{
    public static void main(String[] args){
        for(char i='A'; i<='E'; i++){
            for(char j=(char)(i+1); j<='E'; j++){
                for(char k=(char)(j+1); k<='E'; k++){
                    System.out.println(""+i+j+k);
                }
            }
        }
    }
}


import java.util.*;

// 递归思路:第1次取什么?
public class C
{
    static List f(String s, int n){
        List lst = new Vector();
        if(n==0){
            lst.add("");
            return lst;
        }
       
        for(int i=0; i<s.length(); i++){
            char x = s.charAt(i);
            List t = f(s.substring(i+1),n-1);
            for(int k=0; k<t.size(); k++){
                lst.add("" + x + t.get(k));
            }
        }
       
        return lst;
    }
   
    public static void main(String[] args){
        List lst = f("ABCDE", 3);
        for(int i=0; i<lst.size(); i++){
            System.out.println(lst.get(i));
        }
    }
}

// "AABBBC" 取3个, 哪些取法?
public class D
{  
    static void work(int[] x){
        for(int i=0; i<x.length; i++){
            for(int k=0; k<x[i]; k++){
                System.out.print((char)('A'+i));
            }
        }
        System.out.println();  
    }
    // data: 不动, 限制条件
    // x: 取法
    // k: 当前考虑的位置
    // goal: 距离目标的剩余名额
    static void f(int[] data, int[] x, int k, int goal){
        if(k==x.length){
            if(goal==0) work(x);
            return;
        }
       
        for(int i=0; i<=Math.min(data[k],goal); i++){
            x[k] = i;
            f(data, x, k+1, goal-i);
        }
        x[k] = 0; // 回溯
    }
   
    public static void main(String[] args)
    {  
        int[] data = {2,3,1};  // 每个元素的最大个数
        int[] x = new int[data.length];  // 每个元素取几个
       
        f(data, x, 0, 3);
    }
}

【C语言:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

    // m个不同的球中,取n个
    int f51(int m, int n)
    {
        if (n == m)
            return 1;
        if (n == 0)
            return 1;
        return f51(m - 1, n) + f51(m - 1, n - 1);
    }

    void main()
    {
        printf("%d    ",f51(5, 3));
        printf("%d    ", f51(5, 2));
   
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void main(){
    char arr[10] = { 0 };
    for (char i = 'A'; i <= 'E'; i++)
    {
        for (char j = (char)(i + 1); j <= 'E'; j++){
            for (char k = (char)(j + 1); k <= 'E'; k++){
               
                arr[0] = i;
                arr[1] = j;
                arr[2] = k;
                printf("%s ", arr);
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


typedef struct MyNode
{
    char *pChar;
    struct MyNode *pNext;
}MyNode;

int xx = -1;
MyNode *pHead = NULL;
MyNode *pTime = NULL;
//组合中有相同字母的删除,没有重复字母的保存到新的结构体链表中
MyNode * myPrint(MyNode *pHead)
{
    MyNode *pMyHead = NULL;
    MyNode *pMyTemp = NULL;
    while (pHead != NULL)
    {
        int x = strlen(pHead->pChar);
        int i = 0;
        for ( i = 0; i < x; i++) { char m = *(pHead->pChar + i);
            char *p=strchr(pHead->pChar + i + 1, m);
            if (!p)
            {
                MyNode*p = (MyNode*)malloc(sizeof(MyNode));
                p->pChar = (char*)malloc(1024);
                memset(p->pChar, 0, 10);
                strcpy(p->pChar, pHead->pChar);
                p->pNext = NULL;
                if (pMyHead==NULL)
                {
                    pMyHead = p;
                    pMyTemp = p;
                } else
                {
                    pMyTemp->pNext = p;
                    pMyTemp = p;
                }

                /*printf("%s\n", pHead->pChar);*/
                pHead = pHead->pNext;
                if (!pHead)
                {
                    goto A;
                }
            }
            else
            {
                pHead = pHead->pNext;
                if (!pHead)
                {
                    goto A;
                }
                break;
            }  
           
        }
       
    }
A:;
    return pMyHead;
}
//打印链表(去除链表中字符串重复的)
void myPrintStruct(MyNode* pMyHead)
{
    while (pMyHead)
    {

        char arr[1024] = { 0 };
        strcpy(arr, pMyHead->pChar);
        MyNode* myMySecondHead = pMyHead->pNext;
        while (myMySecondHead)
        {
            int x = strcmp(arr, myMySecondHead->pChar);
            if (x==0)
            {
                break;
            }
            myMySecondHead = myMySecondHead->pNext;
            if (!myMySecondHead)
            {
                printf("%s \n", arr);
            }
        }

        pMyHead = pMyHead->pNext;
    }

}
//递归取出所有符合n的组合
MyNode* f53(char* s, int len, int n)
{
    if (strcmp(s,"DE")==0)
    {
        printf("");
    }
    if (xx == -1)
    {
        xx = n;
    }
   
    if (n <= 0) { MyNode *p = malloc(sizeof(MyNode)); p->pChar = malloc(len);
        memset(p->pChar, 0, 10);
        p->pNext = NULL;

        return p;
    }

    int hn = strlen(s);
    MyNode * kHead = NULL;
    MyNode *KTemp = NULL;
    for (int i = 0; i < hn; i++)
    {

       

        char x = s[i];
       
        char *pc = malloc(len);
        memset(pc, 0, 10);
        strcpy(pc, s+i + 1);

        int yy = strlen(pc);
        if (yy<n-1) { break; } MyNode * pTm = f53(pc, len, n - 1); MyNode*phh = pTm; while (phh != NULL) { int num = strlen(phh->pChar);
            if (num!=xx)
            {
                char arr[1024] = { x };
                strcat(arr, phh->pChar);
                strcpy(phh->pChar, arr);
               
            }  
            phh = phh->pNext;

        }
        if (kHead==NULL)
        {
            kHead = pTm;
            KTemp = pTm;
        }
        else
        {
            if (KTemp != pTm&&kHead != pTm)
            {
                while (KTemp->pNext != NULL)
                {
                    KTemp = KTemp->pNext;
                }
                KTemp->pNext = pTm;
                KTemp = KTemp->pNext;
            }
        }          


    }
   

    return kHead;
}

void main()
{
    char arr[] = "ABCDE";

    pHead=f53(arr, 7, 3);

    MyNode * simplStruct=myPrint(pHead);

    myPrintStruct(simplStruct);
   
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void work(int *x,int len)
{
    for (int i = 0; i < len; i++){
        for (int k = 0; k < x[i]; k++){
            int x = 'A' + i;
            printf("%c",(char)x);
        }
    }
    printf("\n");
}
// data: 不动, 限制条件
// x: 取法
// k: 当前考虑的位置
// goal: 距离目标的剩余名额
void ff(int* data,int len1, int* x,int len2, int k, int goal)
{
    if (k == len2){
        if (goal == 0)
            work(x,len2);
        return;
    }
    int min = data[k] < goal ? data[k] : goal;
    for (int i = 0; i<=min; i++)
    {
        x[k] = i;
        ff(data,len1, x,len2, k + 1, goal - i);
    }
    x[k] = 0; // 回溯
}

void main()
{
    int data[] = { 2, 3, 1 };  // 每个元素的最大个数
 // 每个元素取几个
    int *x=malloc(sizeof(int)* 3);

    ff(data, 3, x,3, 0, 3);
}


5. 扑克序列
【问题描述】
A A 2 2 3 3 4 4, 一共4对扑克牌。请你把它们排成一行。
要求:两个A中间有1张牌,两个2之间有2张牌,两个3之间有3张牌,两个4之间有4张牌。

请填写出所有符合要求的排列中,字典序最小的那个。
例如:22AA3344 比 A2A23344 字典序小。当然,它们都不是满足要求的答案。

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.*;

public class TA
{
    static Set set = new TreeSet();
   
    static void test(char[] da)
    {
        String s = new String(da);
       
        if(s.lastIndexOf('A') - s.indexOf('A') != 2) return;
        if(s.lastIndexOf('2') - s.indexOf('2') != 3) return;
        if(s.lastIndexOf('3') - s.indexOf('3') != 4) return;
        if(s.lastIndexOf('4') - s.indexOf('4') != 5) return;
       
        set.add(s);
    }
   
    static void f(char[] da, int k)
    {
        if(k==da.length){
            test(da);
            return;
        }
       
        for(int i=k; i<da.length; i++){
            {char t=da[k]; da[k]=da[i]; da[i]=t;}
            f(da,k+1);
            {char t=da[k]; da[k]=da[i]; da[i]=t;}
        }
    }
   
    public static void main(String[] args)
    {
        char[] da = "AA223344".toCharArray();
        f(da, 0);
       
        for(Object s: set) System.out.println(s);
    }
}

【C语言:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <cstdlib>  
using namespace std;
char para[8];
int findit(char a, int index)
{
    for (int i = index; i < 8; i++)
    {
        if (para[i] == a)return i;
    }
}
int main6()
{
    char card[8] = { 'A', 'A', '2', '2', '3', '3', '4', '4' };
    for (int i = 0; i < 8; i++)
    {
        para[0] = card[i];
        for (int i2 = 0; i2 < 8; i2++)
        {
            if (i2 == i)continue;
            para[1] = card[i2];
            for (int i3 = 0; i3 < 8; i3++)
            {
                if (i3 == i || i3 == i2)continue;
                para[2] = card[i3];
                for (int i4 = 0; i4 < 8; i4++)
                {
                    if (i4 == i || i4 == i2 || i4 == i3)continue;
                    para[3] = card[i4];
                    for (int i5 = 0; i5 < 8; i5++)
                    {
                        if (i5 == i || i5 == i2 || i5 == i3 || i5 == i4)continue;
                        para[4] = card[i5];
                        for (int i6 = 0; i6 < 8; i6++)
                        {
                            if (i6 == i || i6 == i2 || i6 == i3 || i6 == i4 || i6 == i5)continue;
                            para[5] = card[i6];
                            for (int i7 = 0; i7 < 8; i7++)
                            {
                                if (i7 == i || i7 == i2 || i7 == i3 || i7 == i4 || i7 == i5 || i7 == i6)continue;
                                para[6] = card[i7];
                                for (int i8 = 0; i8 < 8; i8++)
                                {
                                    if (i8 == i || i8 == i2 || i8 == i3 || i8 == i4 || i8 == i5 || i8 == i6 || i8 == i7)continue;
                                    para[7] = card[i8];
                                    int in1 = findit('A', 0);
                                    int in2 = findit('A', in1 + 1);
                                    int in3 = findit('2', 0);
                                    int in4 = findit('2', in3 + 1);
                                    int in5 = findit('3', 0);
                                    int in6 = findit('3', in5 + 1);
                                    int in7 = findit('4', 0);
                                    int in8 = findit('4', in7 + 1);
                                    //cout<<in1<<" "<<in2<<" "<<in3<<" "<<in4<<" "<<in5<<" "<<in6<<" "<<in7<<" "<<in8<<endl;  
                                    if ((in2 - in1) == 2 && (in4 - in3) == 3 && (in6 - in5) == 4 && (in8 - in7) == 5)
                                    {
                                        for (int i = 0; i < 8; i++)
                                        {
                                            cout << para[i] << " ";
                                        }
                                        cout << endl;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    system("pause");
    return 0;
}


如果您需要更多课程内容和讲解视频,请联系小蓝

蓝桥杯算法特训第一课【实用性原则】源代码

【内容简介】
本文章内容为【2018蓝桥杯大赛算法特训(软件)系列课程】第一课【实用性原则】中涉及到的课上例题的代码实现,加入赛前特训获取全部课程内容请联系【小蓝】。


【课程中涉及的源代码】
1. 猜年龄
【问题描述】
美国数学家维纳(N.Wiener)智力早熟,11岁就上了大学。
他曾在1935~1936年应邀来中国清华大学讲学。
一次,他参加某个重要会议,年轻的脸孔引人注目。
于是有人询问他的年龄,他回答说:
“我年龄的立方是个4位数。我年龄的4次方是个6位数。这10个数字正好包含了从0到9这10个数字,每个都恰好出现1次。”
请你推算一下,他当时到底有多年轻。
【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
public class A{
    public static void main(String[] args){
        for(int i=1; i<100; i++){
            int a = i * i * i;
            int b = a * i;
            if((a+"").length()!=4) continue;
            if((b+"").length()!=6) continue;           
            System.out.println(i + " = " + a + " " + b);
        }
    }
}

【C语言:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//判断数组里面每一个元素是否相同,相同返回1,不同返回0
int ifDiffInArr(char* arr,int num)
{
    for (int x = 0; x < num-1; x++)
    {
        for (int y = x + 1; y < num; y++)
        {
            if (arr[x] == arr[y])
            {
                return 1;
            }
        }
    }
    return 0;
}
//判断数组1和数组2里面每一个元素是否相同,相同返回1,不同返回0
int ifDiffOfArr(char* arr1, int num1,char*arr2,int num2)
{
    for (int x = 0; x < num1; x++)
    {
        for (int y = 0; y < num2; y++)
        {
            if (arr1[x] == arr2[y])
            {
                return 1;
            }
        }
    }
    return 0;
}

void main()
{
    char arr1[4] = { 0 };//保存立方结果4位数的数组
    char arr2[6] = { 0 };//保存4次方结果6位数的数组
    int a, b;//保存立方和4次方的变量
    for (int i = 1; i < 100; i++)//年龄从1到100
    {
        //立方过程
        a= i * i * i;
        //把整形转变为数组类型char*
        itoa(a, arr1, 10);
        //判断arr1数组里面的数字是否重复,重复的话就舍掉i,继续判断下一个i++
        if (ifDiffInArr(arr1, 4) == 1)
        {
            continue;
        }

        //4次方过程
        b = a * i;
        //把整形转变为数组类型char*
        itoa(b, arr2, 10);
        //判断arr2数组里面的数字是否重复,重复的话就舍掉i,继续判断下一个i++
        if (ifDiffInArr(arr2, 6) == 1)
        {
            continue;
        }

        //判断数组arr1和arr2里面的数字是否重复,重复的话就舍掉i,继续判断下一个i++;不重复的话就是我们要找的年龄,并打印出来。
        if (ifDiffOfArr(arr1,4,arr2,6)==1)
        {
            continue;
        }
        else
        {
            printf("计算结果如下:\n\n");
            printf("数学家维纳的年龄是:%d\n\n", i);
            printf("年龄的立方是%d,  \n年龄的4次方是:%d。", a, b);
        }

    }
   
}

2. 罗马数字
【问题描述】
古罗马帝国开创了辉煌的人类文明,但他们的数字表示法的确有些繁琐,尤其在表示大数的时候,现在看起来简直不能忍受,所以在现代很少使用了。
之所以这样,不是因为发明表示法的人的智力的问题,而是因为一个宗教的原因,当时的宗教禁止在数字中出现0的概念!
罗马数字的表示主要依赖以下几个基本符号:

I –> 1
V –> 5
X –> 10
L –> 50
C –> 100
D –> 500
M –> 1000

这里,我们只介绍一下1000以内的数字的表示法。
单个符号重复多少次,就表示多少倍。最多重复3次。
比如:CCC表示300 XX表示20,但150并不用LLL表示,这个规则仅适用于I X C M。

如果相邻级别的大单位在右,小单位在左,表示大单位中扣除小单位。
比如:IX表示9 IV表示4 XL表示40
49 = XLIX

更多的示例参见下表,你找到规律了吗?
I = 1
II = 2
III = 3
IV = 4
V = 5
VI = 6
VII = 7
VIII = 8
IX = 9
X = 10
XI = 11
XII = 12
XIII = 13
XIV = 14
XV = 15
XVI = 16
XVII = 17
XVIII = 18
XIX = 19
XX = 20
XXI = 21
XXII = 22
XXIX = 29
XXX = 30
XXXIV = 34
XXXV = 35
XXXIX = 39
XL = 40
L = 50
LI = 51
LV = 55
LX = 60
LXV = 65
LXXX = 80
XC = 90
XCIII = 93
XCV = 95
XCVIII = 98
XCIX = 99
C = 100
CC = 200
CCC = 300
CD = 400
D = 500
DC = 600
DCC = 700
DCCC = 800
CM = 900
CMXCIX = 999

本题目的要求是:请编写程序,由用户输入若干个罗马数字串,程序输出对应的十进制表示。

输入格式是:第一行是整数n,表示接下来有n个罗马数字(n<100)。
以后每行一个罗马数字。罗马数字大小不超过999。
要求程序输出n行,就是罗马数字对应的十进制数据。

例如,用户输入:
3
LXXX
XCIII
DCCII

则程序应该输出:
80
93
702
【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
//罗马数字的枚举解法
public class A{
   
    public static int romeNum(String s){
        int sum = 0;
        for(int i=0; i<s.length(); i++){ char c = s.charAt(i); if(c=='I') sum += 1; if(c=='V') sum += 5; if(c=='X') sum += 10; if(c=='L') sum += 50; if(c=='C') sum += 100; if(c=='D') sum += 500; if(c=='M') sum += 1000; } // 补偿 if(s.indexOf("IV")>=0) sum -= 2;
        if(s.indexOf("IX")>=0) sum -= 2;
        if(s.indexOf("XL")>=0) sum -= 20;
        if(s.indexOf("XC")>=0) sum -= 20;
        if(s.indexOf("CD")>=0) sum -= 200;
        if(s.indexOf("CM")>=0) sum -= 200;
       
        return sum;
    }
   
    public static void main(String[] args){
        System.out.println(romeNum("MCCCXIV"));
        System.out.println(romeNum("CMXCIX"));
    }
}
//罗马数字的逆向解法
public class NiXiang
{
    static String NumRoman(int x){
        int a = x / 1000;  // 千位
        int b = x % 1000 / 100;  //百位
        int c = x % 100 / 10;  // 十位
        int d = x % 10;
       
        String s = "";
       
        if(a==1) s += "M";
        if(a==2) s += "MM";
        if(a==3) s += "MMM";
       
        if(b==1) s += "C";
        if(b==2) s += "CC";
        if(b==3) s += "CCC";
        if(b==4) s += "CD";
        if(b==5) s += "D";
        if(b==6) s += "DC";
        if(b==7) s += "DCC";
        if(b==8) s += "DCCC";
        if(b==9) s += "CM";
       
        if(c==1) s += "X";
        if(c==2) s += "XX";
        if(c==3) s += "XXX";
        if(c==4) s += "XL";
        if(c==5) s += "L";
        if(c==6) s += "LX";
        if(c==7) s += "LXX";
        if(c==8) s += "LXXX";
        if(c==9) s += "XC";
               
        if(d==1) s += "I";
        if(d==2) s += "II";
        if(d==3) s += "III";
        if(d==4) s += "IV";
        if(d==5) s += "V";
        if(d==6) s += "VI";
        if(d==7) s += "VII";
        if(d==8) s += "VIII";
        if(d==9) s += "IX";
       
        return s;  
    }
     
    static boolean RomanNumOK(String s){
        for(int i=0; i<4000; i++){
            if(s.equals(NumRoman(i))) return true;
        }
        return false;
    }
   
    public static void main(String[] args){
        System.out.println(RomanNumOK("CCXLIX"));
        System.out.println(RomanNumOK("CCXXLIX"));
        //System.out.println(NumRoman(3009));
    }
}

【C语言:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 罗马数字的枚举解法
int romeNum(char* s,int num)
{
        int sum = 0;
        for (int i = 0; i < num; i++)
        {
            char c = s[i];
            if (c == 'I')
                sum += 1;
            if (c == 'V')
                sum += 5;
            if (c == 'X')
                sum += 10;
            if (c == 'L')
                sum += 50;
            if (c == 'C')
                sum += 100;
            if (c == 'D')
                sum += 500;
            if (c == 'M')
                sum += 1000;
        }

        // 补偿
        if (strstr(s,"IV") != NULL)
            sum -= 2;
        if (strstr(s, "IX") != NULL)
            sum -= 2;
        if (strstr(s, "XL") != NULL)
            sum -= 20;
        if (strstr(s, "XC") != NULL)
            sum -= 20;
        if (strstr(s, "CD") != NULL)
            sum -= 200;
        if (strstr(s, "CM") != NULL)
            sum -= 200;

        return sum;
}

void main