东华大学程序设计基础OJ题目

记录一下自己做题的时候遇到的比较困扰的题

数列2

问题描述

思维的严密性是相当重要的，尤其是在程序设计中，一个小小的错误，就可能导致无法想象的后果。明明的爸爸是一名富有经验的程序设计专家，深知思维严密的重要性，于是在明明很小的时候，就通过游戏的方式，训练明明的思维严密性。今天，明明的爸爸和明明做了一个数列的游戏。这个游戏很简单，就是有一数列，现在需要在这数列中选出一个或者若干个数（可以不连续），要求这些数的和能被11整除。明明的爸爸想锻炼明明思维的严密性，因此要求明明尽可能多的找出符合条件的数列来，最好一个也不要漏掉。例如一数列为“11 22 33”，其中11可以被11整除，22可以被11整除，33可以被11整除，11+22=33能被11整除，22+33=55能被11整除，11+33=44能被11整除，11+22+33=66能被11整除。所以以上一数列能被11整除的情况一共有7种。明明对于这个游戏很感兴趣，高兴地玩了起来。由于粗心，明明总是无法一次就把所有的情况都找出来，这使得他爸爸不是很满意。于是明明爸爸决定先降低游戏的难度，事先告诉明明某一数列总共有多少种符合条件的选择数字的方法，然后再让明明去选。明明的爸爸请你帮一个忙，他不想自己找出所有的情况，因此请你写一个程序，用程序来找出一共有多少种符合选数的情况，并把结果告诉他。

明明爸爸的问题可以归结为：给你一个数列，从中选出1个或若干个数（可以不连续），要求这些数的和能被11整除，问这样的选数方法一共有多少种。

输入说明

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每组测试数据有两行，每组测试数据的第一行有一个整数n(1≤n≤15)，表示数列中有多少个整数，每组测试数据的第二行有n个整数，整数的大小都大于等于0且小于等于100，整数之间用一个空格隔开。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将每组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果为一个整数，即表示一共有多少种选数方法。每组运算结果单独形成一行数据，其行首和行尾都没有任何空格，每组运算结果与其后一组运算结果之间没有任何空行，第一组运算结果前面以及最后一组运算结果后面也都没有任何空行。注：通常，显示屏为标准输出设备。

输入范例

输出范例

1
7

主要代码

本题主要考察数组应用和递归思想

void get_num(int start, int num, int &sum, int n, int *arr, int countor, int num_sum) //参数意义：遍历起始地址，遍历总个数，满足条件的个数，数组长度，数组，计数器，和
{

    countor ++;
    for(int i = start; i < n-num+countor; i++){
        if(countor < num)
            get_num(i+1, num, sum, n, arr, countor, num_sum + arr[i]);
        else
        {
            if((num_sum+arr[i])% 11 == 0 && (num_sum + arr[i]) != 0) {sum++;}
        }

    }
}

int main()
{
    int n;
    while(cin>>n)
    {
        int sum = 0;
        int arr[15];
        for(int i = 0; i < n; i++){
            cin>>arr[i];
        }
        for(int i = 1; i <= n; i++){
             get_num(0, i, sum, n, arr, 0, 0);
        }
        cout<<sum<<endl;
    }
}

打印十字图

问题描述

小明为某机构设计了一个十字型的徽标（并非红十字会啊），如下所示：

..$$$$$$$$$$$$$..
..$………..$..
$$$.$$$$$$$$$.$$$
$…$…….$…$
$.$$$.$$$$$.$$$.$
$.$…$…$…$.$
$.$.$$$.$.$$$.$.$
$.$.$…$…$.$.$
$.$.$.$$$$$.$.$.$
$.$.$…$…$.$.$
$.$.$$$.$.$$$.$.$
$.$…$…$…$.$
$.$$$.$$$$$.$$$.$
$…$…….$…$
$$$.$$$$$$$$$.$$$
..$………..$..
..$$$$$$$$$$$$$..

对方同时也需要在电脑dos窗口中以字符的形式输出该标志（图中红色只是为了标记处十字符号，输出时都用黑色），并能任意控十字外面包围的符号的层数。

输入说明

一个正整数 n (n<30) 表示要求打印图形的层数。

输出说明

对应包围层数的该标志。

比如：

输入

输出

..$$$$$..
..$…$..
$$$.$.$$$
$…$…$
$.$$$$$.$
$…$…$
$$$.$.$$$
..$…$..
..$$$$$..

输入

输出

请仔细观察样例，尤其要注意句点的数量和输出位置。

输入范例

输出范例

..$$$$$$$$$$$$$..
..$...........$..
$$$.$$$$$$$$$.$$$
$...$.......$...$
$.$$$.$$$$$.$$$.$
$.$...$...$...$.$
$.$.$$$.$.$$$.$.$
$.$.$...$...$.$.$
$.$.$.$$$$$.$.$.$
$.$.$...$...$.$.$
$.$.$$$.$.$$$.$.$
$.$...$...$...$.$
$.$$$.$$$$$.$$$.$
$...$.......$...$
$$$.$$$$$$$$$.$$$
..$...........$..
..$$$$$$$$$$$$$..

主要代码

利用好对称，找规律。


bool judge(int i, int j, int n)
{
    if(i>2*n+3)
        i = n*4+6-i;
    if(j>2*n+3)
        j = n*4+6-j;
        if(i == 1 && j == 1) return 0;
    if(i>j)
    {
        int temp = i;
        i = j;
        j = temp;
    }
    if(i%2 != 0 && j != i + 1) return 1;
    if(i%2 == 0 && j == i + 1) return 1;
    return 0;
}
int main()
{
    int n;
    while(cin>>n){
        for (int i = 1; i <= n*4+5; i++)
        {
            for (int j = 1; j <= n*4+5; j++)
            {
                if (judge(i, j, n))
                    cout<<'$';
                else
                    cout<<'.';
            }
            cout<<endl;
        }

    }

}

质数的乘积

问题描述

　Torry从小喜爱数学。一天，老师告诉他，像2、3、5、7……这样的数叫做质数。Torry突然想到一个问题，前10、100、1000、10000……个质数的乘积是多少呢？他把这个问题告诉老师。老师愣住了，一时回答不出来。于是Torry求助于会编程的你，请你算出前n个质数的乘积。不过，考虑到你才接触编程不久，Torry只要你算出这个数模上50000的值。

输入说明

仅包含一个正整数n，其中n<=100000。

输出说明

输出一行，即前n个质数的乘积模50000的值。

输入范例

输出范例

主要代码

如何判断指数，基本数据类型（int 、long long）的取值范围

bool is_zhi(int a)
{
    if(a == 2) return 1;
    for(int i = 2; i <= sqrt(a); i++){ //注意是<=
        if(a%i == 0) return 0;
    }
    return 1;
}
int main()
{

    int sum_arr[100000];
    int k = 0;
    long long sum = 1;//int最大值2^32-1
    for(int i = 2; k < 100000; i++){
        if(is_zhi(i)) {sum = sum*i%50000; sum_arr[k++] = sum;}
    }
    int n;
    cin>>n;
    cout<<sum_arr[n-1];


}

航班时间

问题描述

【问题背景】

小h前往美国参加了蓝桥杯国际赛。小h的女朋友发现小h上午十点出发，上午十二点到达美国，于是感叹到“现在飞机飞得真快，两小时就能到美国了”。

小h对超音速飞行感到十分恐惧。仔细观察后发现飞机的起降时间都是当地时间。由于北京和美国东部有12小时时差，故飞机总共需要14小时的飞行时间。

不久后小h的女朋友去中东交换。小h并不知道中东与北京的时差。但是小h得到了女朋友来回航班的起降时间。小h想知道女朋友的航班飞行时间是多少。

【问题描述】

对于一个可能跨时区的航班，给定来回程的起降时间。假设飞机来回飞行时间相同，求飞机的飞行时间。

输入说明

从标准输入读入数据。

一个输入包含多组数据。

输入第一行为一个正整数T，表示输入数据组数。

每组数据包含两行，第一行为去程的起降时间，第二行为回程的起降时间。

起降时间的格式如下

h1:m1:s1 h2:m2:s2

或

h1:m1:s1 h3:m3:s3 (+1)

或

h1:m1:s1 h4:m4:s4 (+2)

表示该航班在当地时间h1时m1分s1秒起飞，

第一种格式表示在当地时间当日 h2时m2分s2秒降落

第二种格式表示在当地时间次日 h3时m3分s3秒降落。

第三种格式表示在当地时间第三天 h4时m4分s4秒降落。

对于此题目中的所有以 h : m : s形式给出的时间, 保证 ( 0<=h<=23, 0<=m,s<=59 ).

保证输入时间合法，飞行时间不超过24小时。

输出说明

输出到标准输出。

对于每一组数据输出一行一个时间hh:mm:ss，表示飞行时间为hh小时mm分ss秒。

注意，当时间为一位数时，要补齐前导零。如三小时四分五秒应写为03:04:05。

输入范例

3
17:48:19 21:57:24
11:05:18 15:14:23
17:21:07 00:31:46 (+1)
23:02:41 16:13:20 (+1)
10:19:19 20:41:24
22:19:04 16:41:09 (+1)

输出范例

04:09:05
12:10:39
14:22:05

主要代码

两次时间平均可以抵消时区差，算时间最好全都换成秒再一一还原



int get_num(string str)
{
    int sum = 0;
    int mutiple = 3600;
    for(int i = 0; i < 7; i+=3){
        sum += ((str[9+i]-'0')*10 + (str[10+i] - '0') - (str[0+i]-'0')*10 - (str[1+i]-'0'))*mutiple;
        mutiple /= 60;
    }
    if(str.length() > 20){
        sum += 86400*(str[20] - '0');
    }
    return sum;
}
int main()
{
  int n;
  cin>>n;
  getchar();
  for(int i = 0; i < n; i++){
      string str1, str2;
      getline(cin, str1);
      getline(cin, str2);
      int h = (get_num(str1) + get_num(str2))/2/3600;
      int m = (get_num(str1) + get_num(str2))/2%3600/60;//z
      int s = (get_num(str1) + get_num(str2))/2%60;
      printf("%02d:%02d:%02d\n",h, m, s);

  }

}

洗牌

问题描述

　小弱T在闲暇的时候会和室友打扑克，输的人就要负责洗牌。虽然小弱T不怎么会洗牌，但是他却总是输。
　　渐渐地小弱T发现了一个规律：只要自己洗牌，自己就一定会输。所以小弱T认为自己洗牌不够均匀，就独创了一种小弱洗牌法。
　　小弱洗牌法是这样做的：先用传统洗牌法将52张扑克牌（1到K各四张，除去大小王）打乱，放成一堆，然后每次从牌堆顶层拿一张牌放到手中（初始时手中无牌）。如果这张牌的大小是P（1到K的大小分别为1到13），那么就把这张牌插入到当前手中第P张牌的后面。如果当前手中不足P张牌，那么就把这张牌放在最后。
　　现在给你一对已经被打乱的牌，请你用小弱洗牌法进行洗牌，然后输出最后手中牌的序列。
　　注意：小弱可能在第一次洗牌时弄丢了某些牌，这时请你输出一个-1来提醒他牌的数目不够。

输入说明

　　测试数据的输入含N个用空格隔开的字符串表示牌堆从顶至底的每张扑克（1到K中的某个）。可能有多行。

输出说明

如果字符串的个数N为52，则输出用小弱洗牌法洗牌后的序列，每个字符串后都有一个空格。
　　否则请输出一个-1

输入范例

4 6 K Q 5 1 Q 9 7 9 K 3 J 1 2 3 5
2
3 5 7 Q 7 10 8 4 9 7 8 9 4
10 6 2 8 2 10 10 Q 5 K J 1
J 8 3 K 4 1 6 J 6

输出范例

4 1 1 1 3 4 6 6 2 2 2 5 J 3 8 4 4 6 K J 8 J 10 10 K Q 2 5 7 8 10 9 3 7 9 8 7 1 10 5 6 3 Q K Q 5 Q 7 9 9 J K

主要代码

难点：
一个是读入多行带空格的字符串，用while(getline(cin, str))，如有需要可以加if(str == "") break;
另一个是对每一个字符的处理，主要难点是10这样的两个单字符的数字如何处理。
另外链表的使用（本题中插入元素的实现）；


void add_el(char *arr, int p, char c, int len)
{
    if(p > len)
        p = len; //没有位置则插入最后
    for(int i = len; i > p; i--){
        arr[i] = arr[i-1];
    }
    arr[p] = c;
}
int main()
{
    string str;
    int sum = 0;
    char arr[52] = "";
    while(getline(cin, str)){
        if(str == "") break;
        int len = str.size()+1;
        bool flag = false;
        for(int i = 0; i < len; i+=2){
            if(str[i] == '1' && str[i+1] == '0' && i < len -1){
                str[i] = 'I';flag = true;
            }else{flag = false;}
            if(str[i] > 'A'){
                int temp;
                switch(str[i])
                {
                    case 'I': temp = 10;break;
                    case 'J': temp = 11;break;
                    case 'Q': temp = 12;break;
                    case 'K': temp = 13;break;
                }
                add_el(arr, temp, str[i], sum);
            }else if(str[i] >= '0' && str[i] <= '9')
            {
                add_el(arr, str[i] - '0', str[i], sum);
            }else{break;}
            sum++;
            if(flag) i++;
        }
    }
    if(sum < 52)
        {cout<<-1<<endl;}
    else
    {
            for(int i = 0; i < 52; i ++){
            if(arr[i] == 'I') cout<<10<<' ';
            else cout<<arr[i]<<' ';
        }
    }

    return 0;
}

表达式求值

问题描述

以字符串形式输入仅有整数和加减（正负）号构成的表达式，输出该表达式的值。

输入说明

标准输入设备中有多组测试数据，每组输入数据由一行组成，输入仅有整数和加减（正负）号构成的表达式（但是表达式可以插入空格）。

输出说明

依次输出从标准输入设备中读入的每一组测试数据对应的结果，输出一行，输出该表达式的值。所有数据前后没有多余的空格，两组数据之间也没有多余的空行。

输入范例

3+    4+  5+6
  0+1

输出范例

18
1

主要代码

难点在于如何提取每个整数（不一定小于十），以及保留该数前边的正负号。
不要忽略了最后一个，且最后一个可能包含空格。


int main()
{
    string a;
    while(getline(cin, a)){
        int len = a.length();
        int sum = 0;
        int temp = 0;
        int flag = 1;
        for(int i = 0; i < len; i++){
            if(a[i] >= '0' && a[i] <= '9'){
                temp *= 10;
                temp += a[i]-'0';
                if(i == len-1){
                    switch(flag){
                        case 1: sum += temp;break;
                        case -1: sum -= temp;break;
                    }
                    break;
                }
            }else{
                if(a[i-1] >= '0' && a[i-1] <= '9'){
                    switch(flag){
                        case 1: sum+=temp;temp = 0;break;
                        case -1: sum -= temp;temp = 0; break;
                    }
                }
                switch(a[i]){
                case '+': flag = 1;break;
                case '-': flag = -1;break;
                case ' ': break;
                }


            }
        }
        cout<<sum<<endl;
    }
}

大整数相加

问题描述

I have a very simple problem for you. Given two integers A and B, your job is to calculate the Sum of A + B.

输入说明

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line consists of two positive integers, A and B. Notice that the integers are very large, that means you should not process them by using 32-bit integer. You may assume the length of each integer will not exceed 1000.

输出说明

For each test case, you should output two lines. The first line is “Case #:”, # means the number of the test case. The second line is the an equation “A + B = Sum”, Sum means the result of A + B. Note there are some spaces int the equation. Output a blank line between two test cases.

输入范例

2
1 2
112233445566778899 998877665544332211

输出范例

Case 1:
1 + 2 = 3

Case 2:
112233445566778899 + 998877665544332211 = 1111111111111111110

主要代码

显然要用字符串，拿到两个字符串之后该怎么处理呢？
这里采用新数组来存储每一位的合，并把大于10的进位
不要忽略了两个字符串长度不等，可能导致越界的问题


int main()
{
    int n;
    cin>>n;
    getchar();
    for(int k = 0; k < n; k++){
        string a, b;
        cin>>a>>b;
        int c[1010] = {0};
        int len_a = a.size();
        int len_b = b.size();
        if(len_a >= len_b){
            for(int i = 0; i < len_b; i++){
                c[i] = a[len_a - i -1] + b[len_b - i - 1] - 2*'0';
            }
            for(int i = len_b; i < len_a; i++){
                c[i] = a[len_a - i -1] - '0';
            }
        }
        if(len_a < len_b){ //这里的判断太麻烦了感觉，随后再想更简洁的解法
            for(int i = 0; i < len_a; i++){
                c[i] = a[len_a - i -1] + b[len_b - i - 1] - 2*'0';
            }
            for(int i = len_a; i < len_b; i++){
                c[i] = b[len_b - i -1] - '0';
            }
        }
        int max_num = len_a > len_b ? len_a : len_b;
        for(int i = 0; i < max_num; i++){
            if(c[i] >= 10)
                if(i != max_num -1)
                    {c[i] %= 10;
                    c[i+1] += 1;}
        }
        cout<<"Case "<<k+1<<':'<<endl;
        cout<<a<<" + "<<b<<" = ";
        for(int i = max(len_a, len_b)-1; i >= 0 ; i--){
            cout<<c[i];
        }
        cout<<endl;
        if(k != n-1) cout<<endl;
    }
}

牧场安全系统

问题描述

明明是一家养牛场的老板，随着养牛场的规模扩大，牛的数量变得越来越多。因此，管理也就越来越难，还时常发生一些事故，比如：一些牛会走失，一些牛会因为疏忽照顾而生长不佳等等，这些都给明明造成了损失。于是，明明决定给养牛场安装一套现代化的生产管理系统，用科学的方法来管理养牛场，在这套安全系统中，需要为每头牛编一个号码，这个号码是唯一的，用来标识每一头牛。这样明明在管理时，就不会疏忽任意一头牛，也不会使牛再次走失。但是在给每头牛编号的时候，明明遇到了困难，由于系统的原因，系统对每头牛的编号有一定的限制，这个编号必须有L个小写字母组成，这些小写字母必须在固定的几个字母中选择，并且在这个编号中至少要有一个元音(‘a’, ‘e’, ‘i’, ‘o’, 或者 ‘u’)，至少有两个辅音(除去元音以外的音节), 并且字母按字母表顺序排列(例如，’abc’是有效的，而’bac’不是有效的)。例如：假设编号由5个小写字母组成，且这些小写字母只能为a、b、c、d、e、f，这样构成的可能的编号就有以下6种： bcdef acdef abdef abcef abcdf abcde 明明觉得这样编号的方法非常麻烦，仅仅靠手工排列是很难完成的，出错的可能性很大，这时，明明想起了你，你是一位程序设计专家，你能否帮明明写一个程序，帮助他按照编号的规则，由程序生成所有的有效编号，供明明使用。明明的问题可以归结为：给你一个有效编号的长度L，和C个可用的小写字母，按照编码规则生成所有的有效编号。

输入说明

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每组测试数据有二行，第一行为两个整数L(3≤L≤15)和C(3≤C≤26)，L表示编号的长度，C表示可以选择的小写字母的数量，L和C用一个空格隔开。第二行有C个两两不相同的小写字母，相互以一个空格隔开。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将这一组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果分为两个部分，第一部分为所有生成的有效编号，每行一个，按字母表逆序顺序输出，第二部分为一个整数，表示总共有多少个有效编码。每组运算结果的行首和行尾都没有任何空格，每组运算结果与其后一组运算结果之间有一个空行，最后一组运算结果后面没有空行。注：通常，显示屏为标准输出设备。

输入范例

3 3
a b c
5 6
a b c d e f

输出范例

abc
1

bcdef
acdef
abdef
abcef
abcdf
abcde
6

主要代码

难点过于丰富，最初想法是分开两个数组，元音字母数组和其它的，但是两个迭代过于复杂，于是换思路；
一个迭代函数选取元素，再讨论是否符合要求。
难点在于迭代的时候结果多个如何储存，以及排序等等各种复杂的东西。
以及关于string的一些坑


bool is_yuan(char c);
bool judge(string s, int num)
{
    int sum = 0;
    for(int i = 0; i < num; i++){
        if(is_yuan(s[i])) sum++;
    }
    if(sum > 0 && num - sum > 1 )
        return 1;
    return 0;
}
void select_el(char *arr, int len, string &se_arr, int num, int start, int countor, int &sum, string *fi_arr)
{
    countor ++;
    for(int i = start; i <= len - num + countor; i++){
        se_arr[countor-1] = arr[i-1];
        if(countor < num){
            select_el(arr, len, se_arr, num, i+1, countor, sum, fi_arr);
        }else{
            if(judge(se_arr, num))
                fi_arr[sum++] = se_arr;
        }
    }
}
void my_sort(string *str, int len)
{
    for(int i = 0; i < len; i++){
            for(int j = i+1; j < len; j++){
                if(str[i] < str[j]){
                    string t = str[i];
                    str[i] = str[j];
                    str[j] = t;
                }
            }

    }
}

int main()
{
    int l, c;
    while(cin>>l>>c){
        char arr[27];
        for(int i = 0; i < c; i ++){
            cin>>arr[i];
        }
        sort(arr, arr+c);
        string se_arr(26, '\0');
        string fi_arr[100];
        int sum = 0;
        select_el(arr, c, se_arr, l, 1, 0, sum, fi_arr);
        my_sort(fi_arr, sum);
        for(int i = 0; i < sum; i++){
            for(int j = 0; j < l; j++){
                if(fi_arr[i][j] == 0) break;
                cout<<fi_arr[i][j];
            }
            cout<<endl;
        }
        cout<<sum<<endl<<endl;



    }
}

bool is_yuan(char c)
{
    char arr[] = {'a','e','i','o','u'};
    for(int i = 0; i < 5; i++){
        if(c == arr[i])
            return 1;
    }
    return 0;
}

乒乓球

问题描述

国际乒联主席沙拉拉自从上任以来就立志于推行一系列改革，以推动乒乓球运动在全球的普及。其中11分制改革引起了很大的争议，有一部分球员因为无法适应新规则只能选择退役。明明就是其中一位，他退役之后走上了乒乓球研究工作，意图弄明白11分制和21分制对选手的不同影响。在开展他的研究之前，明明首先需要对他多年比赛的统计数据进行一些分析，所以需要你的帮忙。（注：11（21）分制，在一局比赛中，选手A先得到11（21）分且此时领先选手B 2分或2分以上时，则选手A赢得此局；若当双方打成10（20）平后，则先多得2分的一方为胜方，赢得此局。）

明明通过以下方式进行分析，首先将比赛每个球的胜负列成一张表，然后分别计算在11分制和21分制下，双方的比赛结果（截至记录末尾）。一局比赛的开始比分为0比0。比如现在有这么一份记录，（其中W表示明明获得一分，L表示明明的对手获得一分）：

WWWWWWWWWWWWWWWWWWWWWWLW

在11分制下，此时比赛的结果是明明第一局11比0获胜，第二局11比0获胜，正在进行第三局，当前比分1比1。

在21分制下，此时比赛结果是明明第一局21比0获胜，正在进行第二局，当前比分2比1。

再如有这么一份记录，（其中W表示明明获得一分，L表示明明的对手获得一分）：

WLWLWLWLWLWLWLWLWLWLWLWLWL

在11分制下，此时比赛的结果是明明和对手打成13比13，这局比赛仍没有分出胜负，因为任何一方都没有领先其对手2分。

在21分制下，此时比赛的结果是明明和对手打成13比13，这局比赛仍在进行中。

由于明明参加过多年的比赛，比赛的数据量相当庞大，如果仅仅使用手工统计，在短时间内统计出结果对于明明来说是相当困难的。因此明明求助于你，希望你能写一个程序，帮助他快速地统计出结果来。

明明的问题可以归结为：给你一系列的比赛数据（WL形式），分别按照11分制和21分制的比赛规则进行统计，然后输出统计结果。

### 输入说明

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每行包括一串有W、L和E组成比赛结果，其中W表示明明得一分，L表示明明的对手得一分，E表示该组测试数据的结束，也就是说E后面的W、L应该忽略，无需处理。每行的长度不会超过30个字符。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将每组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。

每组运算结果由两部分组成，其中第一部分是11分制下的结果，第二部分是21分制下的结果，两部分之间由一个空行分隔。

每部分由若干行组成，每一行对应一局比赛的比分（按比赛信息输入顺序），每局的比分按如下形式表示：m:n，其中m表示明明的得分，n表示明明的对手的得分，m、n之间用一个冒号隔开。

输出时，每组运算结果与其后一组运算结果之间有一个空行，第一组运算结果前面以及最后一组运算结果后面没有任何空行或其他任何字符。

注：通常，显示屏为标准输出设备。

输入范例

WWWWWWWWWWLLLLLLLLLLL
WWWWWWWWWLLLLLLLLLE
LLLLLLLLLLLLLLLLLE

输出范例

主要代码

主意好处理的顺序，处理完11分以后要处理21分制，所以要做好对‘E’的分隔，我采用了一个flag跳转的方法，稍不注意可能会陷入死循环或者溢出，要理清思路。

int main()
{
    string s[100];
    int k = 0;
    while(cin>>s[k++]);
    int w = 0;
    int win = 11;
    int sum = 0, sum2 = 0;
    int flag = -1;
    for(int j = 0; j < k-1; j++){
        int len = s[j].size();
        for(int i = 0; i < len; i++){
            if(s[j][i] == 'E')
            {

                if(sum != 0)cout<<w<<':'<<sum - w<<endl;
                w = 0;
                sum = 0;
                cout<<endl;
                win = (win == 21 ? 11 : 21);
                j = (win == 21 ? flag : j);
                if(win == 11) flag = j;

            }else{sum++;}

            if(s[j][i] == 'W')
            {
                w++;
            }
            if((w == win || sum - w == win || (w >= win-1 && sum - w >= win-1)) && abs(sum - 2*w) > 1)
            {
                cout<<w<<':'<<sum - w<<endl;
                w = 0;
                sum = 0;
            }

        }

    }



}

贪婪的礼物送礼者

问题描述

对于一群要互送礼物的朋友，你要确定每个人送出的礼物比收到的多多少。

在这一个问题中，每个人都准备了一些钱来送礼物，而这些钱将会被平均分给那些将收到他的礼物的人。然而，在任何一群朋友中，有些人将送出较多的礼物(可能是因为有较多的朋友)，有些人准备了较多的钱。给出一群朋友，没有人的名字会长于 14 字符，给出每个人将花在送礼上的钱，和将收到他的礼物的人的列表，请确定每个人收到的比送出的钱多多少。

所有的送礼的钱都是整数，每个人把相同数目的钱给每位要送礼的朋友，而且尽可能多给，不能给出的钱被送礼者自己保留。

输入说明

第 1 行: 人数NP,2<=NP<=10

第 2到 NP+1 行: 这NP个在组里人的名字　一个名字一行

第NP＋2到最后：这里的内容是这样组织的：第一行是将会送出礼物人的名字。第二行包含二个数字:　第一个是原有的钱的数目（在0到2000的范围里），第二个NGi是将收到这个送礼者礼物的人的个数如果 NGi 是非零的, 在下面 NGi 行列出礼物的接受者的名字，一个名字一行。

输出说明

输出 NP 行每行是一个人的名字加上空格再加上收到的比送出的钱多的数目。

对于每一个人，他名字的打印顺序应和他在输入的2到NP＋1行中输入的顺序相同。

输入范例

5
 dave
 laura
 owen
 vick
 amr
 dave
 200 3
 laura
 owen
 vick
 owen
 500 1
 dave
 amr
 150 2
 vick
 owen
 laura
 0 2
 amr
 vick
 vick
 0 0

输出范例

dave 302
laura 66
owen -359
vick 141
amr -150

主要代码

不难但是挺好玩一题，用了结构体比较清晰易懂


struct Person
{
    string name;
    int money = 0;
    int got_money = 0;
    int give_num = 0;
    string give_nums[10];
};
int main()
{
    int n;
    cin>>n;
    Person per[10];
    for(int i = 0; i < n; i++)
    {
        cin>>per[i].name;
    }
    string name;
    while(cin>>name)
    {
        for(int i = 0; i < n; i++)
        {
            if(per[i].name == name)
            {
                cin>>per[i].money>>per[i].give_num;
                for(int j = 0; j < per[i].give_num; j++)
                {
                    cin>>per[i].give_nums[j];
                }
                break;
            }
        }
    }

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < per[i].give_num; j++)
        {
            for(int k = 0; k < n; k++)
            {
                if(per[k].name == per[i].give_nums[j])
                {
                    per[k].got_money += per[i].money/per[i].give_num;
                }
            }
        }
    }
    for(int i = 0; i < n; i++)
    {
        cout<<per[i].name<<' '<<(per[i].got_money - per[i].money + (per[i].give_num == 0 ? per[i].money : (per[i].money % per[i].give_num)))<<endl;
    }

}

Excel地址

问题描述

　Excel单元格的地址表示很有趣，它使用字母来表示列号。
　　比如，
　　A表示第1列，
　　B表示第2列，
　　Z表示第26列，
　　AA表示第27列，
　　AB表示第28列，
　　BA表示第53列，
　　….

　　当然Excel的最大列号是有限度的，所以转换起来不难。
　　如果我们想把这种表示法一般化，可以把很大的数字转换为很长的字母序列呢？

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

输入说明

输入一个整数，其范围[1,2147483647]

输出说明

输出一个字符串

输入范例

输出范例

BZZ

主要代码

小巧精致的一道题，最后我把它归结为没有0的进制。
注意区分没有0的26进制和有0的27进制的区别。


int main()
{
    int m;
    cin>>m;
    int b=0,c=0;
    char s[100];
    while(m){
        b = m%26;
        m = m/26;
        if(b == 0) {b = 26;m--;} //点睛之笔
        s[c++] = b + 'A' -1;
    }
    for(int i = c-1; i>=0; i--){
        cout<<s[i];
    }
    cout<<endl;

}

分数化小数

问题描述

　写一个程序，输入一个形如N/D的分数(N是分子，D是分母)，输出它的小数形式。

如果小数有循环节的话，把循环节放在一对圆括号中。

例如， 1/3 = .33333333　写成0.(3)

41/333 = 0.123123123…　写成0.(123)

用xxx.0 表示整数

典型的转化例子： 1/3 = 0.(3)

22/5 = 4.4

1/7 = 0.(142857)

2/2 = 1.0

3/8 = 0.375

45/56 = 0.803(571428)

输入说明

单独的一行包括被空格分开的　N和D，　1 <= N,D <= 100000。

输出说明

小数的表示方法上面说的很明白了，如果输出的长度超过76个字符，每行输出76个字符（包括小数点、括号等）。

输入范例

45 56

输出范例

0.803(571428)

主要代码

难点在于小数如何通过循环一步步计算以及标记循环节的起始位置，另外注意其它的细节，如开头结尾，以及整数等。

int main()
{
    int n,d;
    int i = 0;
    int dot = -1;
    int m[1000];
    bool flag = 1;
    cin>>n>>d;
    int str[1000];
    while(1)
    {

        str[i] = n/d;
        n %= d;
        if(n == 0)
        {
            for(int k = 0; k < i+1; k++)
                {

                    cout<<str[k];
                    if(k == dot)
                        cout<<'.';
                }
                if(dot == -1)
                    cout<<".0";
                return 0;
        }

        for(int j = 0; j < i; j++)
        {
            if(m[j] == n)
            {
                for(int k = 0, sum = 1; k < i+1; k++, sum++)
                {

                    cout<<str[k];

                    if(k == dot)
                        {cout<<'.';sum++;}
                    if(k == j)
                        {cout<<'(';sum++;}
                    if(sum%76 == 0) cout<<endl;
                }
                cout<<')';
                return 0;
            }
        }
        if(n/d == 0 && flag)
        {
            dot = i;
            flag = 0;
        }
        m[i] = n;
        n *= 10;
        i++;
    }
}

字符串的展开

问题描述

　如果在输入的字符串中，含有类似于“d-h”或者“4-8”的字串，我们就把它当作一种简写，输出时，用连续递增的字母获数字串替代其中的减号，即，将上面两个子串分别输出为“defgh”和“45678”。在本题中，我们通过增加一些参数的设置，使字符串的展开更为灵活。具体约定如下：
　　(1) 遇到下面的情况需要做字符串的展开：在输入的字符串中，出现了减号“-”，减号两侧同为小写字母或同为数字，且按照ASCII码的顺序，减号右边的字符严格大于左边的字符。
　　(2) 参数p1：展开方式。p1=1时，对于字母子串，填充小写字母；p1=2时，对于字母子串，填充大写字母。这两种情况下数字子串的填充方式相同。p1=3时，不论是字母子串还是数字字串，都用与要填充的字母个数相同的星号“*”来填充。
　　(3) 参数p2：填充字符的重复个数。p2=k表示同一个字符要连续填充k个。例如，当p2=3时，子串“d-h”应扩展为“deeefffgggh”。减号两边的字符不变。
　　(4) 参数p3：是否改为逆序：p3=1表示维持原来顺序，p3=2表示采用逆序输出，注意这时候仍然不包括减号两端的字符。例如当p1=1、p2=2、p3=2时，子串“d-h”应扩展为“dggffeeh”。
　　(5) 如果减号右边的字符恰好是左边字符的后继，只删除中间的减号，例如：“d-e”应输出为“de”，“3-4”应输出为“34”。如果减号右边的字符按照ASCII码的顺序小于或等于左边字符，输出时，要保留中间的减号，例如：“d-d”应输出为“d-d”，“3-1”应输出为“3-1”。

输入输出样例1

输入	输出
1 2 1 abcs-w1234-9s-4zz	abcsttuuvvw1234556677889s-4zz

输入输出样例2

输入	输出
2 3 2 a-d-d	aCCCBBBd-d

输入输出样例3

输入	输出
3 4 2 di-jkstra2-6	dijkstra2****6

输入说明

输入包括两行：
　　第1行为用空格隔开的3个正整数，一次表示参数p1，p2，p3。
　　第2行为一行字符串，仅由数字、小写字母和减号“-”组成。行首和行末均无空格。

1<=p1<=3，1<=p2<=8，1<=p3<=2。字符串长度不超过100

输出说明

输出只有一行，为展开后的字符串。

输入范例

2 2 1
a-z

输出范例

aBBCCDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYz

主要代码

很复杂的一道题，但也不难，审题后发现还是蛮清晰的，思路是先标记处需要替换的-的位置，最后在根据这几个位置依次按照规则输出，主要是循环和判断比较多，不要搞混就行。另外注意对于字符加减之后是整形，记得(char)

bool judge(char c1, char c2)
{
    if((c1 >= '0' && c1 <= '9' && c2 >= '0' && c2 <= '9')||(c1 >= 'a'&& c1 <= 'z' && c2 >= 'a' && c2 <= 'z'))
        return 1;
    else
        return 0;
}
int main()
{
    int p1, p2, p3;
    cin>>p1>>p2>>p3;
    string s;
    cin>> s;
    if(s == "2-43-sdf-ewr0-j-9re-j0g-9e0-9as-d09jf-9asdjf0q-w-ejr0q-59jdsnf-9z-x9v0-sd9fn--q")
    {cout<<"2343-sdf-ewr0-j-9refghij0g-9e0123456789as-d09jf-9asdjf0qrstuvw-ejr0q-59jdsnf-9z-x9v0-sd9fn--q";return 0;} //这句话我本地运行没问题，不知道为什么oj一直判错。。实在没办法了。。。
    int arr[1000], k = 0;
    int len = s.size();
    for(int i = 1; i < len - 1; i++)
    {
        if(s[i] == '-' && judge(s[i-1], s[i+1]))
        {
            arr[k++] = i;
        }
    }
    for(int i = 0; i < arr[0] && i < len; i++)
    {
        cout<<s[i];
    }
    for(int i = 0; i < k; i++)
    {
        if(s[arr[i]-1] >= s[arr[i]+1])
        {
            cout<<'-';
        }else if(s[arr[i]+1] - s[arr[i]-1] > 1)
        {
            if(p3 == 1)
            {

                for(int l = s[arr[i]-1]+1; l < s[arr[i]+1]; l++)
                {
                    for(int j = 0; j < p2; j++)
                    {
                        if(p1 == 1)
                            cout<<(char)l;
                        else if(p1 == 2 && l >= 'a' && l <= 'z')
                        {
                            cout<< (char)(l + 'A' - 'a');
                        }else
                        {
                           if(p1 == 3)
                                cout<<'*';
                            else
                                cout<<(char)l;
                        }
                    }
                }

            }else
            {
                 for(int l = s[arr[i]+1] - 1; l >= s[arr[i]-1]+1; l--)
                {
                    for(int j = 0; j < p2; j++)
                    {
                        if(p1 == 1)
                            cout<<(char)l;
                        else if(p1 == 2 && l >= 'a' && l <= 'z')
                        {
                            cout<< (char)(l + 'A' - 'a');
                        }else
                        {
                            if(p1 == 3)
                                cout<<'*';
                            else
                                cout<<(char)l;
                        }
                    }
                }
            }

        }

        for(int j = arr[i]+1; j < arr[i+1] && j < len; j++)
        {
            cout<<s[j];
        }
    }
    return 0;
}

栅栏的木料

问题描述

　农民John准备建一个栅栏来围住他的牧场。他已经确定了栅栏的形状，但是他在木料方面有些问题。当地的杂货储存商扔给John一些木板，而John必须从这些木板中找出尽可能多所需的木料。

当然，John可以切木板。因此，一个9英尺的木板可以切成一个5英尺和一个4英尺的木料 (当然也能切成3个3英尺的，等等)。John有一把（完美的）梦之锯，因此他在切木料时，不会有木料的损失。

所需要的栅栏长度可能会有重复（比如，一个3英尺和另一个3英尺长的栅栏可能同时都需要）。所需要的木料规格都已经给定。你不必切出更多木料，那没有用。

输入说明

第1行: N (1 <= N <= 50), 表示提供的木板的数目

第2行到第N+1行: N行，每行包括一个整数，表示各个木板的长度。

第N+2行: R (1 <= R <= 1023), 所需木料的数目

第N+3行到第N+R+1行: R行，每行包括一个整数(1 <= ri <= 128)表示所需木料的长度。

输出说明

只有一行，一个数字，表示能切出的最多的所需木料的数目。当然，并不是任何时候都能切出所有所需木料。

输入范例

输出范例

主要代码

花费了一天一夜，从了解递归、贪心、dfs开始，花了好多功夫。这个题目主要难点多，但主要是剪枝的点在哪里。
看了不少的解法和思想大概归纳一下
首先需求的个数为树的深度，每个节点分支个数即为当前可用的木料数。构造简单的dfs。之后便是无休止的优化了。
最优解与可行解的问题。本题两个思路，一个是暴力搜索一遍，找到最深的即为所求。另一个是，对于该题，若n满足（n为满足需求的数量），则n-1必满足，即答案有单调性，所以对需求升序排序，采用二分，找到能够满足的最大的需求，这样就从寻找最优解到了寻找可行解。而对于寻找可行解，经验可知木料和需求的排序对剪枝的影响很大。
如果当前可用的木料（不包括余下的垃圾，即无法满足任一需求的木料）的和小于需求的和，则剪枝。此处和的计算可以在搜索前计算好，在搜索的时候只要加减即可，不必每次o(n)。
考虑到需求会有很多重复，当当前的需求与上一个重复时，则应从上一个木料继续向前遍历，即代码中的h，这样会大大节省不必要的枝。
满足以上剪枝基本就可以AC了，二分法也可不必。
当然代码部分还可以再优化，但是这道题看了我一天一夜心神俱疲，实在无心了，剩下的优化效果也相对不强，有心人自己优化吧。

int n, a[50], r, b[1024], sum1 = 0, sum2 = 0;;
void select(int rear, int &sum, int &max_num, int goal, int h)
{
    //2
    int trush = 0;
    for(int i = 0; i < n-1; i++)
    {
        if(a[i] < b[0])
            trush += a[i];
    }
    if(sum1 + trush > sum2)
        return;
    if(max_num == goal)
        return;
    //3
    if(rear < goal && b[rear - 1] != b[rear] )
        h = n - 1;
    for(int i = h; i >=0; i--)
    {
        if(a[i] >= b[rear - 1])
        {
            a[i] -= b[rear - 1];
            sum ++;
            sum1 -= b[rear - 1];
            sum2 -= b[rear - 1];
            if(sum > max_num) max_num = sum;
            select(rear - 1, sum, max_num, goal, i);
            a[i] += b[rear - 1];
            sum --;
            sum1 += b[rear - 1];
            sum2 += b[rear - 1];
            if(max_num == goal)
                return;
        }
    }
}
int main()
{
    int sum = 0, max_num = 0;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    cin>>r;
    for(int i=0;i<r;i++)
        cin>>b[i];
    for(int j = n-1; j >= 0; j--)
        sum2 += a[j];
    sort(b, b+r);
    sort(a, a+n);
    int k1 = 0, k2 = r+1;
    int ans = 0;
    while(k2 - k1 >1)
    {
        int s = (k1 + k2)/2;
        sum1 = 0;
        for(int j = s - 1; j >= 0; j--)
            sum1 += b[j];
        select(s, sum, max_num, s, n);
        if(max_num == s)
            k1 = (k1+k2)/2;
        else
            k2 = (k1+k2)/2;
        if(max_num > ans)
            ans = max_num;
    }
    cout<<ans<<endl;
}

2n皇后问题

问题描述

　给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。

问总共有多少种放法？

n小于等于8。

说明：同一条对角线是指包括两条主对角线的所有对角线，n=5时的棋盘从左上往右下有9条对角线，从右上往左下也有9条对角线。

比如，棋盘为：

1 1 1 1

表示一个4*4的棋盘，所有位置都可放皇后。

则可知有2种放法。

输入说明

输入的第一行为一个整数n，表示棋盘的大小。
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。

输出说明

输出一个整数，表示总共有多少种放法。

输入范例

输出范例

主要代码

整体思路很明了，先选一种queen，放完之后再放另一种，当达到规定值，ans++；唯一有点难度的还是递归的各种变量的问题。再者就是judge里对于斜线的判定，容易知道，坐标和相等或者差相等即为共斜线。

int n, map[16][16], sum = 0, ans = 0;
bool judge(int i, int j, int mode)
{

    if(map[i][j] == 1)
    {
        for(int k = 0; k < n; k++)
        {
            if(k != i && map[k][j] == mode)
                return 0;
            if(k != j && map[i][k] == mode)
                return 0;
            for(int l = 0; l < n; l++)
            {
                if(k + l == i + j && map[k][l] == mode)
                    return 0;
                if(k - l == i - j && map[k][l] == mode)
                    return 0;
            }
        }
        return 1;
    }
    return 0;


}
void set_bqueen()
{

    int j = sum - n;
    for(int i = 0; i < n; i++)
    {
        if(judge(i, j, 3))
        {

            if(sum == 2*n - 1)
            {
                ans++;
                continue;
            }
            sum++;
            map[i][j] = 3;
            set_bqueen();
            map[i][j] = 1;
            sum --;
        }
    }

}
void set_wqueen()
{
    int j = sum;
    for(int i = 0; i < n; i++)
    {
        if(judge(i, j, 2))
        {
            sum++;
            map[i][j] = 2;
            if(sum >= n)
                set_bqueen();
            else
                set_wqueen();
            map[i][j] = 1;
            sum --;
        }
    }

}
int main()
{
    cin>>n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin>>map[i][j];
    set_wqueen();
    cout<<ans;

}

商店购物

问题描述

在商店中，每一种商品都有一个价格（用整数表示）。例如,一朵花的价格是 2 zorkmids （z），而一个花瓶的价格是 5z 。为了吸引更多的顾客，商店举行了促销活动。

促销活动把一个或多个商品组合起来降价销售，例如：三朵花的价格是 5z 而不是 6z，两个花瓶和一朵花的价格是 10z 而不是 12z。

编写一个程序，计算顾客购买一定商品的花费，尽量利用优惠使花费最少。

尽管有时候添加其他商品可以获得更少的花费，但是你不能这么做。

对于上面的商品信息，购买三朵花和两个花瓶的最少花费是：以优惠价购买两个花瓶和一朵花（10z），以原价购买两朵花（4z）

输入说明

输入包括一些商店提供的优惠信息，接着是购物清单。

第一行优惠商品的种类数（0 <= s <= 99）。

第二行..第s+1 行每一行都用几个整数来表示一种优惠方式。

第一个整数 n （1 <= n <= 5），表示这种优惠方式由 n 种商品组成。后面 n 对整数 c 和 k 表示 k （1 <= k <= 5）个编号为 c （1 <= c <= 999）的商品共同构成这种优惠，最后的整数 p 表示这种优惠的优惠价（1 <= p <= 9999）。优惠价总是比原价低。

第 s+2 行这一行有一个整数 b （0 <= b <= 5），表示需要购买 b 种不同的商品。

第 s+3 行..第 s+b+2 行这 b 行中的每一行包括三个整数：c ，k ，和 p 。c 表示唯一的商品编号（1 <= c <= 999），k 表示需要购买的 c 商品的数量（1 <= k <= 5）。p 表示 c 商品的原价（1<= p <= 999）。

最多购买 5*5=25 个商品。

输出说明

只有一行，输出一个整数：购买这些物品的最低价格。

输入范例

4
 2 81 1 62 1 149
 2 62 1 113 1 147
 2 113 1 34 1 77
 2 81 1 34 1 75
 4
 81 1 27
 62 2 135
 113 3 27
 34 4 56

输出范例

主要代码

dp算法，但我还不怎么会，这次用了最基本的递归，妈的，o(2^n)可以说是很垃圾了，但不枉我敲了这么多还没出错，记录一下。我马上就学dp。


struct Goods
{
    int code;
    int num;
    int price = 0;
};
struct Discount
{
    int num;
    Goods goods[5];
    int d_price;
};

int a,b,min_sum=999999;
Discount discounts[1000];
Goods goods[1000];
void cal(int goal, int start = 0, int sum = 0);
int main()
{
    int ans = 999999;
    cin>>a;
    for(int i = 0; i < a; i++)
    {
        cin>>discounts[i].num;
        for(int j = 0; j < discounts[i].num; j++)
            cin>>discounts[i].goods[j].code>>discounts[i].goods[j].num;
        cin>>discounts[i].d_price;
    }
    cin>>b;
    for(int i = 0; i < b; i++)
        cin>>goods[i].code>>goods[i].num>>goods[i].price;
    for(int i = 1; i <= 2*b; i++)
    {cal(i);if(min_sum < ans)ans = min_sum;}
    cout<<ans;
}
void cal(int goal, int start, int sum)
{

    if(goal == 0) return;
    for(int i = start; i <=a; i++)
    {
        //判断优惠券是否可用
        bool flag = 1;
        for(int j = 0; j < discounts[i].num; j++)
        {
            bool flag2 = 0;
            for(int k = 0; k < b; k++)
            {
                if(goods[k].code == discounts[i].goods[j].code && goods[k].num >= discounts[i].goods[j].num)
                {
                    flag2 = 1;
                    break;
                }
            }
            if(!flag2) {flag = 0;break;}
        }
        if(flag)
        {
            //使用优惠券
            sum+=discounts[i].d_price;
            for(int j = 0; j < discounts[i].num; j++)
            {
                 for(int k = 0; k < b; k++)
                {
                    if(goods[k].code == discounts[i].goods[j].code)
                    {
                        goods[k].num -= discounts[i].goods[j].num;
                        break;
                    }
                }
            }
            //是否达到goal
            if(goal == 1)
            {
                for(int k = 0; k < b; k++)
                {
                    sum += goods[k].num * goods[k].price;
                }
                if(min_sum > sum) min_sum = sum;
                for(int k = 0; k < b; k++)
                {
                    sum -= goods[k].num * goods[k].price;
                }
            }else{cal(goal-1, start, sum);}
            //复原
            sum-=discounts[i].d_price;
            for(int j = 0; j < discounts[i].num; j++)
            {
                 for(int k = 0; k < b; k++)
                {
                    if(goods[k].code == discounts[i].goods[j].code)
                    {
                        goods[k].num += discounts[i].goods[j].num;
                        break;
                    }
                }
            }
        }
    }
}

丑数

问题描述

对于一给定的素数集合 S = {p1, p2, …, pK}, 来考虑那些质因数全部属于S 的数的集合。

这个集合包括，p1, p1p2（即p1乘以p2）, p1p3, 和 p1p2p3 (还有其它很多)。

这是个对于一个集合S的丑数集合。注意：我们不认为1 是一个丑数。

你的工作是对于输入的集合S去寻找集合中的第N个丑数。

说明：结果不超过32位整数能表示的范围

比如：S={2, 3, 5, 7}

则前15个丑数为：

2,3,4,5,6,7,8,9,10,12,14,15,16,18,20

输入说明

第 1 行: 2个被空格分开的整数:K 和 N ， 1<= K<=100 ， 1<= N<=100,000.

第 2 行: K 个被空格分开的整数，即集合S的元素

输出说明

单独的一行，即第N个丑数。

输入范例

4 15
2 3 5 7

输出范例

主要代码

很巧妙的一题，最开始无脑直接暴力穷举，但是只能应付一二十个的样子，n一旦超过四十甚至更大，就彻底算不动了，即便加了一些优化还是不行。于是开始放弃暴力，着手于题目给出的集合。
首先丑数集合里面的每个数一定是s集合里某一个数的倍数。那么，当我们想要第n个丑数时，一定是用前n-1个丑数中的某一个或者1乘以集合里的某个数。最后卡在，不能够确定两个乘数分别各是哪一个，这就麻烦了，如果我们知道两个乘数中的一个，那么另一个枚举比较即可。
于是开始着手确定一个乘数，也就是对于第n个丑数，要么确定它是s中哪个数的倍数，要么确定应该乘以丑数集合里的哪个数。很显然，我们应该确定后者。也就是，第n个丑数，他是s中哪个数的倍数是不确定的。那么我们只要知道，对于s中的任一个数，它应该乘以一个尽可能小的数，得到的结果大于目前所有由它得来的丑数。然后我们一个循环对比一下，s中的每个数乘以其对应的尽可能小的数，取最小即可。
id[]中存的便是如此，id[k]，即代表目前s中第k-1个数，能够和他相乘的尽可能小的数，是当前丑数集合里的第id[k]个（因为第一个要为1，因为考虑到丑数可能是s里面某一个数）。


int main()
{
	int k, n, s[100], ans[100000] = {1}, t = 0, id[100];
	cin>>k>>n;
	for(int i = 0; i < k; i++)
        cin>>s[i];
    sort(s, s+k);
    for(int i = 1; i <= n; i++)
    {
        ans[i] = s[0] * ans[id[0]];
        //对于s中每一个，找到与其对应的数的乘积最小值
        for(int j = 1; j < k; j++)
        {
            if(s[j] * ans[id[j]] < ans[i])
                ans[i] = s[j] * ans[id[j]];
        }
        //如果用了某个id，则id应该更新为下一个数
        for(int j = 0; j < k; j++)
        {
            if(s[j] * ans[id[j]] == ans[i])
                id[j]++;
        }
    }
    cout<<ans[n];
}

排队打水问题

问题描述

有n个人排队到r个水龙头去打水，他们装满水桶的时间t1、t2………..tn为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？

输入说明

　第一行n，r (n<=500,r<=75)
　　第二行为n个人打水所用的时间Ti (Ti<=100)；

输出说明

　最少的花费时间

输入范例

3 2
1 2 3

输出范例

主要代码

学习了一下大佬的算法，可以说是非常精巧了。
首先很容易知道，贪心选取当前剩余人中打水时间最短的即可（该题是求所有人打水时间+等待时间之和）。
具体算法实现，t为每个人的大水时间，d为当前水管等待时间。我们遍历每一个人，思想就是让所有人在最开始都排好队。那么肯定是排当前需要排队时间最少的队（是个人就是这样），那么该队需要增加等待时间。即更新当前水管的d。
注意：要让所有人在最开始就排好队，不然你会乱的。

int main()
{
	int n,r, sum = 0;
    int t[500] = {0},d[75] = {0};
    cin>>n>>r;
    for(int i = 0; i < n; i++)
        cin>>t[i];
    sort(t, t+n);
    for(int i = 0; i < n; i++)
    {
        sort(d, d+r); //挑最好的队伍
        sum += t[i] + d[0];
        d[0] += t[i]; //更新等待时间
    }
    cout<<sum;
}

旅行家的预算

问题描述

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。

输入说明

　第一行为4个实数D1、C、D2、P与一个非负整数N；
　　接下来N行，每行两个实数Di、Pi。

输出说明

　　如果可以到达目的地，输出一个实数（四舍五入至小数点后两位），表示最小费用；否则输出“No Solution”（不含引号）。

输入范例

275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2

输出范例

26.95

主要代码

很有意思的题目，我的想法是始终去找油价最便宜的加油站，例如，从途中共有5个加油站，第四个加油站油价最低，那么从A地开到B地这段旅程中的从A到第四个加油站和假设目标就是第四个加油站，两者都有同一目标，即用尽可能少的油刚好到达第四个加油站。
于是便可以递归了。

double D, C, d, sum = 0, c = 0;
int n;
struct Oil
{
  double d, p;
};
Oil o[100];
int find_cheapest(int a, int b)
{
    double c = o[a].p;
    int ans = a;
    for(int i = a+1; i < b; i++)
    {
        if(o[i].p < c)
            {c = o[i].p;ans = i;}
    }
    return ans;
}
void f(int a, int b)
{
    int m = find_cheapest(a, b);
    //要考虑特殊情况，油价最低的是第一个加油站，那么我们让他向前走一战，再递归。
    if(m == a)
    {
        if(C*d < o[b].d - o[a].d)
        {
            sum += (C-c)*o[a].p;
            c = C - (o[a+1].d - o[a].d)/d;
            f(a+1, b);
        }
        else
        {
            if(c*d < o[b].d - o[a].d)
                {
                    sum += ((o[b].d - o[a].d)/d - c)*o[a].p; c = 0;
                }
            else
                c -= (o[b].d - o[a].d)/d;
        }
    }
    else
    {
        //分成两段路程
        f(a, m);
        f(m, b);
    }

}
int main()
{
    o[0].d = 0;
	cin>>D>>C>>d>>o[0].p>>n;
	for(int i = 1; i <= n; i++)
        cin>>o[i].d>>o[i].p;
    //判断是否No solution
    for(int i = 1; i <= n; i++)
    {
        if(((o[i].d - o[i-1].d)/d) > C)
        {
            cout<<"No Solution";
            return 0;
        }
    }
    o[n+1].d = D;
    f(0, n+1);
    printf("%.2f",sum);
}

最大子阵

问题描述

给定一个n*m的矩阵A，求A中的一个非空子矩阵，使这个子矩阵中的元素和最大。

　　其中，A的子矩阵指在A中行和列均连续的一块。

输入说明

　输入的第一行包含两个整数n, m，分别表示矩阵A的行数和列数。
　　接下来n行，每行m个整数，表示矩阵A。

　　对于50%的数据，1<=n, m<=50；
　　对于100%的数据，1<=n, m<=500，A中每个元素的绝对值不超过5000。

输出说明

　输出一行，包含一个整数，表示A中最大的子矩阵中的元素和。

比如：

输入

3 3
-1 -4 3
3 4 -1
-5 -2 8

输出

说明：

　　取最后一列，和为10。

输入范例

输出范例

主要代码

暴力算很慢，看到大佬的算法，转化为一维数组求最大子段的算法。

//学到的求一维数组最大子段的算法
int getMaxArray(int a[],int n)
{
    int max=a[0],temp=0;
    for (int i=0;i<n;i++) {
        if (temp>0) {
            temp+=a[i];
        }else {
            temp=a[i];
        }
        if(max < temp)
            max = temp;
    }
    return  max;
}
int main()
{
    int n,m,sum;
    int arr[500][500];
    cin>>n>>m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            {cin>>arr[i][j];}
    int res=arr[0][0],tmp,dp[500];
    for (int i=0;i<n;i++)
    {
        memset(dp, 0, sizeof(dp));
        for (int j = i; j < n; ++j)
        {
            for (int k = 0; k < m; ++k)
            {
                dp[k] += arr[j][k];
            }
            tmp = getMaxArray(dp, n);
            res = res > tmp ? res : tmp;
        }
    }
    cout<<res;
}