1. 基础

(1)显示数字出现次数

输 入 一 个 十 进 制 正 整 数 , 转 换 成 16 进 制 数 。 再 输 入 一 个 数 (0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f),统计这个数出现的次数。
【输入格式】 一行输入十进制正整数。 另一行输入要统计的数。
【输出格式】 要统计的数出现的次数。
【输入样例】 在这里给出一组输入。例如: 841175128
【输出样例】 3

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<sstream>
using namespace std;
int* Change(int m);
string num2str(int i[]);
int main() {
	int src, target, num, y;
	num = 0;
	cin >> src;
	int* x;
	y = src;
	x = Change(src);
	cout << "请输入要查找的数" << endl;
	cin >> target;
	for (int index = 0; index < 9; index++) {
		//cout << x[kkk] << endl;
		if (x[index] == target) {
			num++;
		}
	}
	cout << num << endl;
	return 0;
}
int* Change(int num) {
	int i = 0;
	int a;
	static int s[9];
	int* p;//指针
	while (num != 0)//将整型;
	{
		a = num % 16;
		num = num / 16;
		i++;
		s[i] = a;
	}
	for (int j = i; j >= 1; j--)
	{
		if (s[j] >= 10)
		{
			s[j] += 55;
		}
	}
	p = s;
	return p;
}

思路:该题的思路是输入一个十进制整形,然后不停的除 16,将余数存在 s 数组内,之后遍历 s 数组,对大于 10 的元素,再加上 55,使其成为 A,B。。。通过 int 型指针将他传回。之后输入待查找的数。遍历 s 数组,将元素一一与待查找的数比对。得出相等的数

(2)显示 Pascal 三角形

输入行数 n,显示 n 行 Pascal 三角形。数字间有一个空格。每行最后一个数字后 有一个空格。
【输入格式】 在一行中输入行数 n。
【输出格式】 输出 n 行 Pascal 三角形。
【输入样例】 在这里给出一组输入。例如: 4
【输出样例】 在这里给出相应的输出。例如: 1 1 1 1 2 1 1 3 3 1

#include<stdio.h>
#include<iostream>
using namespace std;

int main() {
	int lineNum;
	cin >> lineNum;
	int** a = new int* [lineNum];   //分配一个指针数组,将其首地址保存在a中   、
		for (int i = 0; i < lineNum; i++) {
			a[i] = new int[i+1];
			for (int LineIndex = 0;LineIndex < i+1;LineIndex++) {
				a[i][0] = 1;
				if (LineIndex > 0) {
					a[i][i] = 1;
				}
				if (i > 1&&LineIndex>0&&LineIndex<i) {
					a[i][LineIndex] = a[i - 1][LineIndex] + a[i - 1][LineIndex - 1];
				}
				cout << a[i][LineIndex]<<" ";
			}
			cout<< endl;
		}
	return 0;
}

思路:这题的思路是利用二维数组,二维数组的第一维是行,第二维是列,首先对每一行的第一列【0】【0】置 1,然后将第二行开始的每一行的最后一个元素置 1。对中间的元素,就采用,本行的 i 元素是上一行元素的第 i 个元素+上一行的第 i-1 元素。然后逐行输出。在第一个循环输出换行。

(3)计算到任意日期的总天数

编程序实现:输入任意一个日期的年、月、日的值,求出从公元 1 年 1 月 1 日 到该日期前一年的年末总共有多少天,到该日期前一个月的月末总共有多少天,到 这一天总共有多少天。假定从公元第一天开始,就实施格里高利历法。格里高利历 8 / 19 法的置闰规则是 400 年 97 闰,也可以概括为:四闰百不闰,四百闰。
【输入格式】 输入三个代表年、月、日的正整数,以空格分隔。
【输出格式】 输出三个总天数,数据之间以换行符分隔,最后换行。
【输入样例】 2012 3 29
【输出样例】 734502 734562 734591

#include<iostream>
using namespace std;
int Day(int month,bool u);
int main() {
	int year, month, day,doubleYear=0,yearNum,dayNum=0;
	bool isDouble;
	cin >> year >> month >> day;
	for (int year1 = 1;year1 <= year;year1++) {
		if ((year1 % 4 == 0 && year1 % 100 != 0) || year1 % 400 == 0) {
			doubleYear++;
		}
	}
	if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) {
		isDouble = true;
	}
	else {
		isDouble = false;
	}
	if (isDouble) {
		yearNum = (doubleYear-1) * 366 + (year - doubleYear) * 365;
	}else{
		yearNum = doubleYear * 366 + (year - doubleYear-1) * 365;
	}
	for (int month1 = 1; month1 < month; month1++) {
		int day1=Day(month1, isDouble);
		dayNum += day1;
	}
	cout << yearNum<< endl;
	cout << yearNum + dayNum << endl;
	cout << yearNum + dayNum + day << endl;
}
int Day(int month, bool isDouble) {
	int day;
	switch (month)
	{
	case 1:
		day = 31;
		break;
	case 2:
		switch (isDouble)
		{
		case true:
			day = 29;
			break;
		case false:
			day = 28;
			break;
		default:
			break;
		}
		break;
	case 3:
		day = 31;
		break;
	case 4:
		day = 30;
		break;
	case 5:
		day = 31;
		break;
	case 6:
		day = 30;
		break;
	case 7:
		day = 31;
		break;
	case 8:
		day = 31;
		break;
	case 9:
		day = 30;
		break;
	case 10:
		day = 31;
		break;
	case 11:
		day = 30;
		break;
	case 12:
		day = 31;
		break;
	default:
		break;
	}
	return day;
}

思路:首先,判断输入年份和公园 1 年之间差多少个闰年。再然后,判断当前年份是否是闰年,之后进行年份的计算。之后循环,看月份。

(4)字符统计

请编写程序,找出一段给定文字中出现最频繁的那个英文字母。
【输入格式】 输入在一行中给出一个长度不超过 1000 的字符串。字符串由 ASCII 码表中 任意可见字符及空格组成,至少包含 1 个英文字母,以回车结束(回车不算在内)。
【输出格式】 在一行中输出出现频率最高的那个英文字母及其出现次数,其间以空格分隔。 如果有并列,则输出按字母序最小的那个字母。统计时不区分大小写,输出小写字 母。
【输入样例】 This is a simple TEST. There ARE numbers and other symbols 1&2&3………..
【输出样例】 e 7

include<iostream>
#include<string>
#include <map>

using namespace std;
int main() {
    std::map<char, int> mymap;
    string input;
    //cin >> input;
    input = "This is a simple TEST. There ARE numbers and other symbols 1&2&3...........";
    char final[100]{0};
    int a[128] = { 0 };
    int output = 0;
    char temp;
    for (int i = 0; i < input.length(); i++) {
        if (input[i] >= 65 && input[i] <= 90) {
            input[i] += 32;
        }
    }

    for (int i = 0; i < input.length(); i++) {
        temp = input[i];
        if (temp < 97 || temp>122) {
            continue;
        }
        int first=input.find(temp);
        mymap[temp] = 1;
        for (; first < input.length();) {
            first = input.find(temp, first + 1);
            if (first != input.npos) {
                mymap[temp] += 1;
            }
      }
    }
    int max = 0;
    for (std::map<char, int>::iterator it = mymap.begin(); it != mymap.end(); ++it) {
        if (max < it->second) {
            max = it->second;
        }

    }
    int point1 = 0;
    for (std::map<char, int>::iterator it = mymap.begin(); it != mymap.end(); it++)
    {

        if (it->second == max) {
            final[point1] = it->first;
            point1++;
        }

    }
    cout << max << " " << final[0] << endl;
        return 0;
    }

思路:首先遍历输入的字符数组,把大写字母全部转换成小写,然后再次遍历字符数组,若碰到非英文字符的,则 continue;之后就用 c++的 find 函数不停查找 temp 在整个字符串中的出现位置,一旦 find 的返回值为-1 则停止查找,进入下一个循环,这里使用 c++的 map,键值对来储存字符和出现次数。之后,遍历 map,找到出现次数最大值,再遍历 map,找到索引,存入 final 数组,之后输出 final 数组的第 0 个元素就好了

(5)汉诺塔

事实上,汉诺塔游戏中的行动可以这样看待:当你需要移动某个盘子的时候, 你需要先将它上面的全部盘子移动到无关杆上,再将这个盘子移动到目标杆,然后 将它上面的盘子从无关杆移动到目标杆。从而,这一问题就可以通过递归的方式解 决了。现在题目给出起始杆上按规律码放的盘子数量,请你给出将它们移动到目标 杆上所需的最少步数。
【输入格式】 一个正整数 N(N<5000),代表你需要移动的的盘子数。
【输出格式】 一个正整数,代表最少需要的步数。
【输入样例】 70 【输出样例】 1180591620717411303423
提示: 如遇 WA,请注意输入数据的范围。
法一:(纯递归)能够精确的表达每一步做了什么。但是时间复杂度太高。不可接受。

#include<iostream>
using namespace std;
int i =0;
void hanoi(int n, char a, char b, char c);
int main() {
	int n;
	cin >> n;
	hanoi(n, 'A', 'B', 'C');
	cout << i << endl;
}
void hanoi(int n, char a, char b, char c) {
	if (n == 1) {
		++i;
	}
	else {
		hanoi(n - 1, a, c, b);
		//cout << ++i << endl;
		//cout << ++i << endl;
		++i;
		cout << i << endl;
		hanoi(n - 1, b, a, c);
	}
}

法二:(大整数乘法)

#include<iostream>
using namespace std;
int a[1000000]; //当数组较大时定义为全局数组,这里是为能计算更大的数。
int main() {
	int n;
	cin >> n;
	a[1] = 1;
	int x = 0, k = 1; 	//x表示需要进的数。k表示位数。
	for (int i = 1; i <= n; i++) {
		int x = 0;
		for (int j = 1; j <= k; j++) {
			a[j] = a[j] * 2 + x;
			x = a[j] / 10;
			a[j] %= 10;
			if (x != 0 && j == k) 	//当计算到最高位并且有进位时,位数加一。
				k++;
		}
	}
	for (int i = k; i >= 1; i--)//遍历输出,将最后一位-1;
		if (i == 1) {
			cout << a[i]-1;
		}
		else {
			cout << a[i];
		}

	return 0;
}

(6)周游世界

周游世界是件浪漫事,但规划旅行路线就不一定了…… 全世界有成千上万条 航线、铁路线、大巴线,令人眼花缭乱。所以旅行社会选择部分运输公司组成联盟, 每家公司提供一条线路,然后帮助客户规划由联盟内企业支持的旅行路线。本题就 要求你帮旅行社实现一个自动规划路线的程序,使得对任何给定的起点和终点,可 以找出最顺畅的路线。所谓“最顺畅”,首先是指中途经停站最少;如果经停站一样 多,则取需要换乘线路次数最少的路线。
【输入格式】 输入在第一行给出一个正整数 N(≤100),即联盟公司的数量。接下来有 N 行, 第 i 行(i=1,⋯,N)描述了第 i 家公司所提供的线路。格式为: M S[1] S[2] ⋯ S[M] 其中 M(≤100)是经停站的数量,S[i](i=1,⋯,M)是经停站的编号(由 4 位 0- 9 的数字组成)。这里假设每条线路都是简单的一条可以双向运行的链路,并且输 入保证是按照正确的经停顺序给出的——也就是说,任意一对相邻的 S[i]和 S[i+1] (i=1,⋯,M−1)之间都不存在其他经停站点。我们称相邻站点之间的线路为一个运 营区间,每个运营区间只承包给一家公司。环线是有可能存在的,但不会不经停任 何中间站点就从出发地回到出发地。当然,不同公司的线路是可能在某些站点有交 叉的,这些站点就是客户的换乘点,我们假设任意换乘点涉及的不同公司的线路都 不超过 5 条。 在描述了联盟线路之后,题目将给出一个正整数 K(≤10),随后 K 行,每行给 出一位客户的需求,即始发地的编号和目的地的编号,中间以一空格分隔。
【输出格式】 处理每一位客户的需求。如果没有现成的线路可以使其到达目的地,就在一行 中输出“Sorry, no line is available.”;如果目的地可达,则首先在一行中输出最顺畅 路线的经停站数量(始发地和目的地不包括在内),然后按下列格式给出旅行路线: Go by the line of company #X1 from S1 to S2. Go by the line of company #X2 from S2 to S3. 10 / 19 …… 其中 Xi 是线路承包公司的编号,Si 是经停站的编号。但必须只输出始发地、换 乘点和目的地,不能输出中间的经停站。题目保证满足要求的路线是唯一的。
【输入样例】
4
7 1001 3212 1003 1204 1005 1306 7797
9 9988 2333 1204 2006 2005 2004 2003 2302 2001
13 3011 3812 3013 3001 1306 3003 2333 3066 3212 3008 2302 3010 3011
4 6666 8432 4011 1306
4
3011 3013 6666 2001 2004 3001 2222 6666
【输出样例】
2 Go by the line of company #3 from 3011 to 3013.
10 Go by the line of company #4 from 6666 to 1306.
Go by the line of company #3 from 1306 to 2302.
Go by the line of company #2 from 2302 to 2001. 6 Go by the line of company #2 from 2004 to 1204.
Go by the line of company #1 from 1204 to 1306. Go by the line of company #3 from 1306 to 3001.             Sorry, no line is available.

#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;
#define MAXN 10015
#define INF 0x3f3f3f
vector<vector<int> > group;
vector<int> ans, pre, l_ans, l;
int n, m, u, v, k, num_min, d_min, route[MAXN][MAXN];
int st, ed;
bool book[MAXN];
void dfs(int now, int d, int num, int r)
{
    if (now == ed)
    {
        if (d < d_min)
        {
            num_min = num;
            d_min = d;
            l_ans = l;
            ans = pre;
        }
        else if (d == d_min && num < num_min)
        {
            l_ans = l;
            num_min = num;
            ans = pre;
        }
    }
    else
    {
        for (int i = 0; i < group[now].size(); i++)
        {
            if (!book[group[now][i]])
            {
                book[group[now][i]] = true;
                if (r != route[now][group[now][i]])
                {
                    pre.push_back(now);
                    l.push_back(route[now][group[now][i]]);
                    dfs(group[now][i], d + 1, num + 1, route[now][group[now][i]]);
                    pre.pop_back();
                    l.pop_back();
                }
                else dfs(group[now][i], d + 1, num, r);
                book[group[now][i]] = false;
            }
        }
    }
}
int main()
{
    cin >> n;
    group.resize(10005);
    for (int i = 1; i <= n; i++)
    {
        scanf_s("%d %d", &k, &u);
        for (int j = 1; j < k; j++)
        {
            scanf_s("%d", &v);
            group[u].push_back(v);
            group[v].push_back(u);
            route[u][v] = i;
            route[v][u] = i;
            u = v;
        }
    }
    int r;
    cin >> m;
    while (m--)
    {
        scanf_s("%d %d", &st, &ed);
        fill(book, book + 10005, false);
        pre.clear();
        ans.clear();
        l.clear();
        l_ans.clear();
        d_min = INF;
        num_min = INF;
        book[st] = true;
        dfs(st, 0, 0, -1);
        if (d_min == INF) printf("Sorry, no line is available.\n");
        else
        {
            printf("%d\n", d_min);
            ans.push_back(ed);
            for (int j = 1; j < ans.size(); j++) {
                printf("Go by the line of company #%d from %04d to %04d.\n", l_ans[j - 1], ans[j - 1], ans[j]);
            }
        }
    }
    return 0;
}

(7)最强阵容

拿着新换来的英雄卡,小李满心欢喜的准备和同学们 PK 一下。 他们的游戏规 则非常简单,双方把自己的牌绕成一圈,然后指定一个起点,从该张牌开始顺时针 方向往后取,谁取出的字符串字典序更小(从左到右开始比较,碰到第一个不一样 的字符进行比较,比较规则为 (a<b<c…)谁将获得胜利。具体规则可参考样例。 虽然现在小李的牌已经很好了,但是你能不能帮他快速算出起始位置,使得他能够 派出最强阵容。
【输入格式】 第一行 n,表示共有 n 张牌。 第二行共 n 个用一个空格隔开的小写字母,表示 给定的一圈牌起始序列。
【输出格式】 仅一个整数,能获得最小字典序字符串的起点位置。如果有多个位置开始的字 符串一样,则输出最小的那个位置,且第一个位置从 1 开始。
【输入样例】
4
b c a b
【输出样例】
3

#include<iostream>
#include<cstdio>
using namespace std;
char a[1000005];
int MinimumRepresentation(char* s, int l) {
    int i = 0, j = 1, k = 0, t;
    while (i < l && j < l && k < l) {
        t = s[(i + k) >= l ? i + k - l : i + k] - s[(j + k) >= l ? j + k - l : j + k];
        if (!t) k++;
        else {
            if (t > 0) i = i + k + 1;
            else j = j + k + 1;
            if (i == j) ++j;
            k = 0;
        }
    }
    return (i < j ? i : j);
}
int main() {
    int n;
    scanf_s("%d\n", &n);
    int k = -1;
    while (k != n) {
        char c;
        c = getchar();
        if (c != ' ') {
            k++;
            a[k] = c;
        }
        if (k == n) break;
    }
    cout << MinimumRepresentation(a, n) + 1 << endl;
    return 0;
}

思路:核心思想是输入之后不停地拿一个元素和他右边的元素比对。取出第一个跟他不一样且比他大的,作为起点

(8)朋友

【问题描述】 同学们应该学会多交一些好朋友。朋友关系是相互的,A 是 B 的 好朋友,则 B 也是 A 的好朋友。朋友关系是不传递的,A 是 B 的好朋友,B 是 C 的好朋友,但 A 和 C 不一定是 好朋友。现在给出某小学部分同学之间的朋友关 系,请编程统计朋友最多的人有多少个好 朋友。 【输入数据】 输入共 m+1 行。 第 1 行是两个整数 n 和 m,分别表示同学总人数和朋友关系对数。 第 2 行到第 m+1 行,描述了 m 对朋友关系。每行两个用单个空格隔开的同学 姓名。 每个人的姓名仅由小写字母组成,且 1≤ 姓名的长度 ≤10。
【输出数据】 一个整数,表示朋友最多的人有多少个好朋友。
【输入输出样例 1】 4 3 lucy lily jam lily jam peter 2
【样例 1 解释】 4 个人,3 对朋友关系。 lucy 只有一个朋友 lily; jam 有两个朋友 lily 和 peter; lily 有两个朋友 lucy 和 jam; peter 只有一个朋友 jam。 所以 lily 和 jam 朋友最多,都是 2 个。
【输入输出样例 2】 6 5 andy bob bella andy bob andy andy cassie cassie bob 3
【样例 2 解释】 6 个人,5 对朋友关系。其中第 1 对朋友关系“andy bob”和第 3 对朋友关系“bob andy” 重复。 andy 有三个朋友,分别是 bob、bella 和 cassie; bob 有两个朋友 andy 和 cassie; bella 只有一个朋友 andy; cassie 有两个朋友 bob 和 andy; 另外 2 个人没有朋友(这两个人在输入中没有出现)。 所以 andy 的朋友最多,有 3 个朋友。
【数据范围约定】 50%以上的测试点输入数据保证朋友关系没有重复。 100% 12 / 19 的测试点输入数据保证 2≤n≤100,1≤m≤1000,且没有自己跟自己的朋友关系。

#include<iostream>
#include<map>
using namespace std;
int main() {
	int n, m;
	cin >> n >> m;
	string *name=new string[n];
	string **rela=new string*[m];
	int re=0;
	for (int point = 0; point < m; point++) {
		rela[point] = new string[2];
	}
	for (int point = 0; point < m; point++) {
		cin >> rela[point][0] >> rela[point][1];
	}
	int flag[10]{0};
	int* flag1;
	flag1 = flag;
	 for (int point1 = 0; point1 < m; point1++) {
		string temp[2] ;
		for (int kkk = 0; kkk < 2; kkk++) {
			temp[kkk] = rela[point1][1-kkk];


		}//数组反转
		for (int ll = 0; ll < m; ll++) {
			if (temp[0] == rela[ll][0] && temp[1] == rela[ll][1]) {
				(*flag1) = ll;
				flag1++;
			}

		}
	}
	 rela[flag[0]] = NULL;
	map<string, string> mymap;
	for (int index = 0; index < m; index++) {
		if (rela[index] == NULL) {
			continue;
		}
		string test[10];
		if (mymap.find(rela[index][0]) != mymap.end()) {//键存在;
			mymap[rela[index][0]] = mymap[rela[index][0]] + "," + rela[index][1];
			//mymap[rela[index][0]] = test->append(mymap[rela[index][1]]);

		}
		else {
			mymap[rela[index][0]]= rela[index][1];
			//mymap[rela[index][0]]=
		}
		if (mymap.find(rela[index][1]) != mymap.end()) {//键存在;
			mymap[rela[index][1]] = mymap[rela[index][1]] + "," + rela[index][0];
		}
		else {
			mymap[rela[index][1]] = rela[index][0];
		}
	}
	int max = 0;
	for (std::map<string, string>::iterator it = mymap.begin(); it != mymap.end(); ++it) {

		int num = 0;
		int first = it->second.find(',');

		if (first == -1) {//没找到逗号,则只有一个朋友
			continue;
		}
		else
		{
			num = 1;
			int first = it->second.find(',');

			for (; first < it->second.length();) {
				first = it->second.find(',', first + 1);
				if (first != it->second.npos) {
					num++;
				}
			}
		}
		if (num > max) {
			max = num;
		}
	}
	cout << max+1 << endl;
	return 0;

}

思路:首先将每对关系存进一个二维数组里,第一维关系数,第二维是具体的朋友关系。然后取一个二维数组,将其反转。比对是否有重复的,有就把他删掉。直到没有重复的。然后利用 c++的 map,朋友中的某一个为键。另一个为值。如果对应键有值,则加逗号再加名字,无值,则直接加对应名字。之后遍历键值对,找逗号个数嘴都的那个,利用 find 函数

(9)旷工

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
typedef long long ll;
vector<int>e[50005];
int t, n, root, dfn[50005], low[50005], tot;
bool vis[50005], ge[50005];
void init() {
    for (int i = 0; i <= 50000; ++i)e[i].clear();
    memset(vis, 0, sizeof(vis));
    memset(ge, 0, sizeof(ge));
    tot = 0; n = 0; root = 1;
    while (t--) {
        int u, v;
        scanf_s("%d%d", &u, &v);
        e[u].push_back(v);
        e[v].push_back(u);
        n = max(v, n);
        n = max(u, n);
    }
}
void tar(int u, int p) {
    low[u] = dfn[u] = tot++;
    vis[u] = 1;
    int cnt = 0;
    for (int i = 0; i < (int)e[u].size(); ++i) {
        int v = e[u][i];
        if (v == p)continue;
        if (!vis[v]) {
            tar(v, u);
            cnt++;
            low[u] = min(low[u], low[v]);
        }
        else low[u] = min(low[u], dfn[v]);
    }
    if ((u == root && cnt > 1) || (u != root && cnt && low[u] >= dfn[u]))ge[u] = 1;
}
ll dfs(int u) {
    int cnt = 1;
    vis[u] = 1;
    for (int i = 0; i < (int)e[u].size(); ++i) {
        int v = e[u][i];
        if (!vis[v] && !ge[v])cnt += dfs(v);
    }
    return cnt;
}
int main(void) {
    while (scanf_s("%d", &t)) {
        if (!t)break;
        init();
        tar(root, -1);
        memset(vis, 0, sizeof(vis));
        ll a1 = 0, a2 = 1;
        for (int i = 1; i <= n; ++i)
            if (!vis[i] && !ge[i]) {
                a1++;
                a2 *= dfs(i);
            }
        printf("%lld %lld\n", a1, a2);
    }
}

(10)字母塔

请编写程序,显示字母塔。
【输入格式】 行数(正整数,不超过 26)
【输出格式】 显示指定行数的字母塔
【输入样例】 6
【输出样例】
a
aba
abcba
abcdcba
abcdedcba
abcdefedcba

#include<iostream>
using namespace std;
int main() {
	int n;
	cin >> n;
	int max = 2 * n - 1;//最大数
	int max1 = (max - 1) / 2;//中位数
	for (int index = 0; index < n; index++) {
		int need = 2 * index +1;
		int need1 = need / 2;
		for (int col = 0; col < max; col++) {
			if (col < max1 - need1) {
				cout << " ";
			}
			else if (col > (max1 + need1)) {
				cout << " ";
			}
			else {
				if (col - max1 > 0) {
					cout << (char)(97+index - (col - max1));
				}
				else if ((col - max1 < 0)) {
					cout << (char)(97 + index -(max1-col));
					cout << (char)(97 + index -(max1-col));
				}
				else {
					cout << (char)(97 + index);
				}
				}
			}
		cout << endl;
		}
	}

思路:利用两层 for 循环,外层循环在循环行,内层循环循环烈,在中心数+-2*n-1 的范围内添加空格。然后对字符的 ascii 码做加减。

2.进阶

1.整数因子分解问题:

package CCPC;
import java.util.Scanner;
public class IntDivide {
    public int count=0;
    public static void main(String[] arg){
        Scanner scan=new Scanner(System.in);
        String n=scan.next();
        int num=Integer.parseInt(n);
        Test1 test=new Test1();
        test.Test(num);
        System.out.println(test.count);
    }

}
class Test1{
    public int count=0;
    public void Test(int n){
        if(n==1){
            this.count++;
        }
        int i = 2 ;
        while ( i<=n ){
            if( n%i == 0) {
                Test( n/i ) ;
            }
            i++ ;
        }

    }
}

思路:将一个数 n 从 2 到它本身依次求余,如果发现 n 求余后为 0,证明这个被求余的数 i 是这个整数的因子,那么我们对 n/i 再进行递归,直到 n/i 变为 1 停止递归。

2.选择问题

【输入】 输入多组测试例:对于每一个测试例有两行,第一行是整数 n 和 k,1 ≤ 𝑘 ≤ 𝑛 ≤ 2000; 第二行是 n 个整数 【输出】 第 k 小的元素
【输入样例】
5 2 3 9 4 1 6
7 3 4 59 7 23 61 55 46
【输出样例】
3
23

package CCPC;
import java.util.Arrays;
import java.util.Scanner;;
public class FindElement {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        while(true) {
            String testcase = scan.nextLine();
            String[] Test = testcase.split(" ");
            int K = Integer.parseInt(Test[1]);
            int N = Integer.parseInt(Test[0]);
            String Num = scan.nextLine();
            String[] Test1 = Num.split(" ");
            int Num2[] = new int[N];
            int point = 0;
            for (String Num1 : Test1) {
                Num2[point] = Integer.parseInt(Num1);
                point++;
            }
            Arrays.sort(Num2);
            System.out.println(Num2[K - 1]);
        }
    }
}

思路:这题是采用 java 来做的,主要就是将输入,按空格打散成数组,然后对数组进行 sort 排序。取出第 k 小的,即数组索引 k-1 的,输出即可。

3.n 皇后问题

给定一个 n × n 格的棋盘上放置彼此不受攻击的 n 个皇后。按照国际象棋规则棋盘中 有一些位置不能放皇后。问总共有多少种放法?使任意的两个皇后都不在同一行、 同一列或同一条对角线上。
编程要求:当面向 n × n 格的棋盘上放置彼此不受攻击的 n 个皇后,找出所有放置方 案。
【输入】
【输入包含多组测试例】 对每个测试例,每行只有一个数字 n,(4 ≤ n ≤ 12)
【输出】 对每组测试数据,输出所有可能的放置情况,最后一行是方案总数。
【输入样例】 5
【输出样例】
1 3 5 2 4
1 4 2 5 3
2 4 1 3 5
2 5 3 1 4
3 1 4 2 5
3 5 2 4 1
4 1 3 5 2
4 2 5 3 1
5 2 4 1 3
5 3 1 4 2
Total = 10

#include<stdio.h>

int count = 0;
int isCorrect(int i, int j, int(*Q)[5])
{
    int s, t;
    for (s = i, t = 0; t < 5; t++)
        if (Q[s][t] == 1 && t != j)
            return 0;//判断行
    for (t = j, s = 0; s < 5; s++)
        if (Q[s][t] == 1 && s != i)
            return 0;//判断列
    for (s = i - 1, t = j - 1; s >= 0 && t >= 0; s--, t--)
        if (Q[s][t] == 1)
            return 0;//判断左上方
    for (s = i + 1, t = j + 1; s < 5 && t < 5; s++, t++)
        if (Q[s][t] == 1)
            return 0;//判断右下方
    for (s = i - 1, t = j + 1; s >= 0 && t < 5; s--, t++)
        if (Q[s][t] == 1)
            return 0;//判断右上方
    for (s = i + 1, t = j - 1; s < 5 && t >= 0; s++, t--)
        if (Q[s][t] == 1)
            return 0;//判断左下方

    return 1;//否则返回
}

void Queue(int j, int(*Q)[5])
{
    int i, k;
    if (j == 5) {//递归结束条件
        for (i = 0; i < 5; i++) {
            //得到一个解,在屏幕上显示
            for (k = 0; k < 5; k++)
                printf("%d ", Q[i][k]);
            printf("\n");
        }
        printf("\n");
        count++;
        return;
    }
    for (i = 0; i < 5; i++) {
        if (isCorrect(i, j, Q)) {//如果Q[i][j]可以放置皇后
            Q[i][j] = 1;//放置皇后
            Queue(j + 1, Q);//递归深度优先搜索解空间树
            Q[i][j] = 0;//这句代码就是实现回溯到上一层
        }
    }
}

int main()
{
    int Q[5][5];
    int i, j;
    for (i = 0; i < 5; i++)
        for (j = 0; j < 5; j++)
            Q[i][j] = 0;
    Queue(0, Q);
    printf("Total %d\n", count);
    return 0;
}

思路:本题主要是采用回溯法,先放在

4. 哈夫曼树

Huffman 树在编码中有着广泛的应用。在这里,我们只关心 Huffman 树的构造 过程。 给出一列数{pi}={p0, p1, …, pn-1},用这列数构造 Huffman 树的过程如下: 1. 找到{pi}中最小的两个数,设为 pa 和 pb,将 pa 和 pb 从{pi}中删除掉,然后 将它们的和加入到{pi}中。这个过程的费用记为 pa + pb。 2. 重复步骤 1,直到{pi}中只剩下一个数。 在上面的操作过程中,把所有的费用相加,就得到了构造 Huffman 树的总费用。 本题任务:对于给定的一个数列,现在请你求出用该数列构造 Huffman 树的总 费用。 例如,对于数列{pi}={5, 3, 8, 2, 9},Huffman 树的构造过程如下: 1. 找到{5, 3, 8, 2, 9}中最小的两个数,分别是 2 和 3,从{pi}中删除它们并将和 5 加入,得到{5, 8, 9, 5},费用为 5。 2. 找到{5, 8, 9, 5}中最小的两个数,分别是 5 和 5,从{pi}中删除它们并将和 10 加入,得到{8, 9, 10},费用为 10。 3. 找到{8, 9, 10}中最小的两个数,分别是 8 和 9,从{pi}中删除它们并将和 17 加入,得到{10, 17},费用为 17。 4. 找到{10, 17}中最小的两个数,分别是 10 和 17,从{pi}中删除它们并将和 27 加入,得到{27},费用为 27。 5. 现在,数列中只剩下一个数 27,构造过程结束,总费用为 5+10+17+27=59。
【输入格式】 输入的第一行包含一个正整数 n(n<=100)。 接下来是 n 个正整数,表示 p0, p1, …, pn-1,每个数不超过 1000。
【输出格式】 输出用这些数构造 Huffman 树的总费用。
【样例输入】 5 5 3 8 2 9
【样例输出】 59

package CCPC;
import java.util.*;
public class Haffman {
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        int temp=Integer.parseInt(scan.nextLine());
        String tempNum=scan.nextLine();
        String[] arr=tempNum.split(" ");
        List<Integer> Inter=new ArrayList<Integer>() ;
        int point=0;
        int fee=0;
        for (String tempArr:arr) {
            Inter.add(Integer.parseInt(tempArr));
        }
        do {
            Inter.sort(Comparator.comparingInt(Integer::intValue));
            fee += Inter.get(0) + Inter.get(1);
            int sum = Inter.get(0) + Inter.get(1);
            Inter.set(1, sum);
            Inter.remove(0);
        }while(Inter.size()!=1);
        System.out.println(fee);
    }
}

思路:这题也是使用 java 来解,首先输入。将输入转化成数组。然后对数组排序。排完了之后取出数组的第 0,1 元素,相加,然后放入数组的 1 元素中,将 0 元素删掉。fee 则把 0,1 元素相加。当 list 的长度为 1 的时候。就退出循环,输出 fee;

5. 最长公共子串问题

假设有两个字符串(可能包含空格),找出其中最长的公共连续子串,并输出其 长度。
输入描述: 输入为两行字符串(可能包含空格),长度均小于等于 50
输出描述: 输出为一个整数,表示最长公共连续子串的长度
输入例子:
abcde
abgde
输出例子:
2

package CCPC;
import java.util.Scanner;
public class Common {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            char[] s1 = scanner.nextLine().toCharArray();
            char[] s2 = scanner.nextLine().toCharArray();

            int res = 0;
            int[][] dp = new int[s1.length][s2.length];
            for (int i = 0; i < s1.length; i++) {
                for (int j = 0; j < s2.length; j++) {
                    if (s1[i] == s2[j]) {
                        dp[i][j] = (i == 0 || j == 0) ? 1: dp[i - 1][j - 1] + 1;
                        res = Math.max(res, dp[i][j]);
                    }
                }
            }
            System.out.println(res);
        }
    }
}

思路:首先,将输入转成字符数组,然后定义一个二维数组。遍历数组 s1,s2.当 s1[i]==s2[j]时,判断是否是第一行或者第一列,否则会数组越界。如果是。则置为一,不是,就这个索引的左上角位置的值+1,然后比对,这个值和存储的最大值,大小。最后输出。

3. 北大 OJ

1.Financial Management

Description
Larry graduated this year and finally has a job. He’s making a lot of money, but somehow never seems to have enough. Larry has decided that he needs to grab hold of his financial portfolio and solve his financing problems. The first step is to figure out what’s been going on with his money. Larry has his bank account statements and wants to see how much money he has. Help Larry by writing a program to take his closing balance from each of the past twelve months and calculate his average account balance.
Input
The input will be twelve lines. Each line will contain the closing balance of his bank account for a particular month. Each number will be positive and displayed to the penny. No dollar sign will be included.
Output
The output will be a single number, the average (mean) of the closing balances for the twelve months. It will be rounded to the nearest penny, preceded immediately by a dollar sign, and followed by the end-of-line. There will be no other spaces or characters in the output.
Sample Input
100.00
489.12
12454.12
1234.10
823.05
109.20
5.27
1542.25
839.18
83.99
1295.01
1.75
Sample Output
$1581.42
翻译:
描述
拉里今年毕业了,终于找到了一份工作。他赚了很多钱,但不知怎么的,似乎永远都不够。拉里已经决定,他需要控制他的金融投资组合,解决他的融资问题。第一步是弄清楚他的钱到底怎么了。拉里有他的银行账户对账单,想看看他有多少钱。帮助拉里写一个程序,从他过去 12 个月的期末余额计算他的平均帐户余额。
输入
输入将是 12 行。每一行将包含他的银行账户在一个特定月份的期末余额。每个数字将是正的,并显示到便士。不包括美元符号。
输出
输出将是单个数字,即 12 个月期末余额的平均值。它将四舍五入到最接近的便士,前面紧跟着一个美元符号,后面跟着行尾。输出中将没有其他空格或字符。
样例输入
100.00
489.12
12454.12
1234.10
823.05
109.20
5.27
1542.25
839.18
83.99
1295.01
1.75
样例输出
1581.42 美元

#include<iostream>
using namespace std;
int main() {
	double sum = 0.00;
	for (int point1 = 0; point1 < 12; point1++) {
		double i;
		cin >> i;
		sum += i;
	}
	sum /= 12;
	cout << "$" << sum << endl;
}

2. Biorhythms

Description
Some people believe that there are three cycles in a person’s life that start the day he or she is born. These three cycles are the physical, emotional, and intellectual cycles, and they have periods of lengths 23, 28, and 33 days, respectively. There is one peak in each period of a cycle. At the peak of a cycle, a person performs at his or her best in the corresponding field (physical, emotional or mental). For example, if it is the mental curve, thought processes will be sharper and concentration will be easier.
Since the three cycles have different periods, the peaks of the three cycles generally occur at different times. We would like to determine when a triple peak occurs (the peaks of all three cycles occur in the same day) for any person. For each cycle, you will be given the number of days from the beginning of the current year at which one of its peaks (not necessarily the first) occurs. You will also be given a date expressed as the number of days from the beginning of the current year. You task is to determine the number of days from the given date to the next triple peak. The given date is not counted. For example, if the given date is 10 and the next triple peak occurs on day 12, the answer is 2, not 3. If a triple peak occurs on the given date, you should give the number of days to the next occurrence of a triple peak.
Input
You will be given a number of cases. The input for each case consists of one line of four integers p, e, i, and d. The values p, e, and i are the number of days from the beginning of the current year at which the physical, emotional, and intellectual cycles peak, respectively. The value d is the given date and may be smaller than any of p, e, or i. All values are non-negative and at most 365, and you may assume that a triple peak will occur within 21252 days of the given date. The end of input is indicated by a line in which p = e = i = d = -1.
Output
For each test case, print the case number followed by a message indicating the number of days to the next triple peak, in the form:

Case 1: the next triple peak occurs in 1234 days.

Use the plural form ``days’’ even if the answer is 1.
Sample Input
0 0 0 0
0 0 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 301 203 40
-1 -1 -1 -1
Sample Output
Case 1: the next triple peak occurs in 21252 days.
Case 2: the next triple peak occurs in 21152 days.
Case 3: the next triple peak occurs in 19575 days.
Case 4: the next triple peak occurs in 16994 days.
Case 5: the next triple peak occurs in 8910 days.
Case 6: the next triple peak occurs in 10789 days.
翻译:
描述
有些人认为人的一生有三个周期,从他或她出生的那一天开始。这三个周期是身体周期、情感周期和智力周期,它们的周期分别为 23 天、28 天和 33 天。每个周期都有一个峰值。在一个周期的高峰,一个人在相应领域(身体、情感或精神)表现出他或她的最佳状态。例如,如果是心理曲线,思维过程会更敏锐,注意力也会更容易集中。
由于这三个周期有不同的周期,所以这三个周期的峰值一般出现在不同的时间。我们想要确定任何一个人的三重峰值何时出现(三个周期的峰值在同一天出现)。对于每个周期,您将得到从年初开始出现其中一个峰值(不一定是第一个)的天数。您还将获得一个日期,该日期表示为从当年年初开始的天数。您的任务是确定从给定日期到下一个三峰的天数。给定的日期不计算在内。例如,如果给定的日期是 10,而下一个三重峰值出现在第 12 天,那么答案是 2,而不是 3。如果在给定的日期出现了一个三重峰值,您应该给出下一个三重峰值出现的天数。

输入
你将会得到一些案例。每种情况的输入都由一行 4 个整数 p、e、i 和 d 组成。p、e 和 i 的值分别是从年初开始身体、情绪和智力周期达到峰值的天数。值 d 是给定的日期,可能比 p、e 或 i 中的任何一个都小。所有的值都是非负的,最大值为 365,你可以假设在给定日期的 21252 天内会出现一个三重峰值。输入的结束用一条线表示,其中 p = e = i = d = -1。
输出
对于每个测试用例,打印用例编号,后面是指示到下三个峰值的天数的消息,形式如下:
案例 1:下一个三峰出现在 1234 天。
即使答案是 1,也要用 double 形式。
样例输入
0 0 0 0
00 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 301 203 40
-1 -1 -1 -1
样例输出
案例 1:下一个三峰出现在 21252 天。
案例 2:下一个三峰出现在 21152 天。
案例 3:下一个三峰出现在 19575 天。
案例 4:下一个三峰出现在 16994 天。
案例 5:下一个三峰出现在 8910 天。
案例 6:下一个三峰出现在 10789 天。

#include <cstdio>
  int main(int argc, const char * argv[]){
      int physical, emotional, intellectual, date;
      int physicalCycle = 23, emotionalCycle = 28, intellectualCycle = 33, LCM = 21252;
      int caseIndex = 0;
      while (scanf("%d %d %d %d", &physical, &emotional, &intellectual, &date)) {
          if (physical < 0 || emotional < 0 || intellectual <0 || date <0) break;//不要死循环
          caseIndex ++;
          physical ? physical = physical % physicalCycle : NULL;
         emotional ? emotional = emotional % emotionalCycle : NULL;
         intellectual ? intellectual = intellectual % intellectualCycle : NULL;
         int i = 0, temp;
         while (1) {
             temp = i * intellectualCycle + intellectual;
             if ((temp % physicalCycle == physical) && (temp % emotionalCycle == emotional)) break;
             i++;         }
         temp = temp <= date ? temp + LCM : temp;
         temp -= date;
         printf("Case %d: the next triple peak occurs in %d days.\n", caseIndex, temp);
     }
     return 0;
 }

思路:这个问题使用中国剩余定理,  使 33×28×a 被 23 除余 1,用 33×28×8=5544,使 23×33×b 被 28 除余 1,用 23×33×19=14421 使 23×28×c 被 33 除余 1,用 23×28×2=1288 因此有(5544×p+14421×e+1288×i)% lcm(23,28,33) =n+d  又 23、28、33 互质,即 lcm(23,28,33)= 2125,所以有 n=(5544×p+14421×e+1288×i-d)!252
本题所求的是最小整数解,避免 n 为负,因此最后结果为 n= [n+21252]% 21252
那么最终求解 n 的表达式就是:
n=(5544p+14421e+1288*i-d+21252)!252;

3.Maya Calendar

Description
During his last sabbatical, professor M. A. Ya made a surprising discovery about the old Maya calendar. From an old knotted message, professor discovered that the Maya civilization used a 365 day long year, called Haab, which had 19 months. Each of the first 18 months was 20 days long, and the names of the months were pop, no, zip, zotz, tzec, xul, yoxkin, mol, chen, yax, zac, ceh, mac, kankin, muan, pax, koyab, cumhu. Instead of having names, the days of the months were denoted by numbers starting from 0 to 19. The last month of Haab was called uayet and had 5 days denoted by numbers 0, 1, 2, 3, 4. The Maya believed that this month was unlucky, the court of justice was not in session, the trade stopped, people did not even sweep the floor.

For religious purposes, the Maya used another calendar in which the year was called Tzolkin (holly year). The year was divided into thirteen periods, each 20 days long. Each day was denoted by a pair consisting of a number and the name of the day. They used 20 names: imix, ik, akbal, kan, chicchan, cimi, manik, lamat, muluk, ok, chuen, eb, ben, ix, mem, cib, caban, eznab, canac, ahau and 13 numbers; both in cycles.

Notice that each day has an unambiguous description. For example, at the beginning of the year the days were described as follows:

1 imix, 2 ik, 3 akbal, 4 kan, 5 chicchan, 6 cimi, 7 manik, 8 lamat, 9 muluk, 10 ok, 11 chuen, 12 eb, 13 ben, 1 ix, 2 mem, 3 cib, 4 caban, 5 eznab, 6 canac, 7 ahau, and again in the next period 8 imix, 9 ik, 10 akbal . . .

Years (both Haab and Tzolkin) were denoted by numbers 0, 1, : : : , where the number 0 was the beginning of the world. Thus, the first day was:
Haab: 0. pop 0
Tzolkin: 1 imix 0
Help professor M. A. Ya and write a program for him to convert the dates from the Haab calendar to the Tzolkin calendar.
Input
The date in Haab is given in the following format:
NumberOfTheDay. Month Year

The first line of the input file contains the number of the input dates in the file. The next n lines contain n dates in the Haab calendar format, each in separate line. The year is smaller then 5000.
Output
The date in Tzolkin should be in the following format:
Number NameOfTheDay Year

The first line of the output file contains the number of the output dates. In the next n lines, there are dates in the Tzolkin calendar format, in the order corresponding to the input dates.
Sample Input
3 10. zac 0 0. pop 0 10. zac 1995
Sample Output
3
3 chuen 0
1 imix 0
9 cimi 2801
翻译:
描述

雅教授有一个关于古玛雅历法的惊人发现。从一个古老的结信息中,教授发现玛雅文明使用一年 365 天,称为 Haab,有 19 个月。前 18 个月的每个月都有 20 天,这些月的名字是 pop, no, zip, zotz, tzec, xul, yoxkin, mol, chen, yax, zac, ceh, mac, kankin, muan, pax, koyab, cumhu。每天没有名字,而是用从 0 到 19 的数字表示。Haab 的最后一个月叫做 uayet,有 5 天,用数字 0、1、2、3、4 表示。玛雅人认为这个月是不吉利的,法院没有开庭,贸易停止,人们甚至不扫地。
出于宗教目的,玛雅人使用了另一种历法,将这一年称为卓尔金(冬青年)。一年分为十三个周期,每个周期 20 天。每一天都由一个数字和一天的名字组成的一对来表示。他们使用了 20 个名字:imix, ik, akbal, kan, chicchan, cimi, manik, lamat, muluk, ok, chuen, eb, ben, ix, mem, cib, caban, eznab, canac, ahau 和 13 个数字循环使用。

请注意,每一天都有明确的描述。例如,在年初,对这些日子的描述如下:

本土知识 1 imix, 2、3 akbal 4 菅直人 5 chicchan 6 cimi 7 马尼克,8 lamat 9 muluk 10 好了,11 个村,12 eb, 13 本,1 第九,2 mem 3 cib 4 caban 5 eznab 6 canac 7 ahau,又在下一期 8 imix 9 本土知识,10 akbal。。。

年份(Haab 和 Tzolkin)用数字 0,1,:::表示,其中数字 0 是世界的开始。因此,第一天是:

Haab: 0。流行 0

卓尔金:1 imix 0

帮助教授 M. a . Ya 和为他写一个程序转换日期从哈伯日历到卓尔金日历。

输入

Haab 中的日期以下列格式列出:

NumberOfTheDay。月年

输入文件的第一行包含文件中输入日期的编号。接下来的 n 行包含了 Haab 日历格式的 n 个日期,每个日期在单独的行中。这一年比 5000 年要小。

输出

卓尔金的日期格式如下:

NameOfTheDay 数年

输出文件的第一行包含输出日期的编号。在接下来的 n 行中,有 Tzolkin 日历格式的日期,其顺序与输入日期相对应。

样例输入

  1. 扎克 0

  2. 流行 0

  3. 扎克 1995

样例输出

3 村 0

1 imix 0

9 cimi 2801

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;
char s1[20][10]={"pop","no","zip","zotz","tzec","xul","yoxkin","mol","chen","yax","zac","ceh","mac","kankin","muan","pax","koyab","cumhu","uayet"};
char s2[20][10]={"imix","ik","akbal","kan","chicchan","cimi","manik","lamat","muluk","ok","chuen","eb","ben","ix","mem","cib","caban","eznab","canac","ahau"};
int main()
{
    int t,day,year,ans,sum,num;
    char mon[10];
    scanf("%d",&t);
    printf("%d\n",t);
    for(int xx=0;xx<t;xx++)
    {
        ans=sum=0;
        scanf("%d. %s %d",&day,mon,&year);
        for(int i=0;i<20;i++)
        {
            if(strcmp(s1[i],mon)==0)
            {
                ans=year*365+day+i*20;
                break;
            }
        }
        ans++;
        year=ans/260;
        num=ans%260;
        if(num==0){//如果是一年的最后一天,我们应该怎样去处理
        	year--;
        	num+=260;
		}
        day=num%13;
        if(day==0)
        	day=13;
        int mon=num%20;
        if(mon==0)
          mon=20;
        printf("%d %s %d\n",day,s2[mon-1],year);
    }
    return 0;
}

4.STAMPS

Description
Have you done any Philately lately?

You have been hired by the Ruritanian Postal Service (RPS) to design their new postage software. The software allocates stamps to customers based on customer needs and the denominations that are currently in stock.

Ruritania is filled with people who correspond with stamp collectors. As a service to these people, the RPS asks that all stamp allocations have the maximum number of different types of stamps in it. In fact, the RPS has been known to issue several stamps of the same denomination in order to please customers (these count as different types, even though they are the same denomination). The maximum number of different types of stamps issued at any time is twenty-five.

To save money, the RPS would like to issue as few duplicate stamps as possible (given the constraint that they want to issue as many different types). Further, the RPS won’t sell more than four stamps at a time.
Input
The input for your program will be pairs of positive integer sequences, consisting of two lines, alternating until end-of-file. The first sequence are the available values of stamps, while the second sequence is a series of customer requests. For example:

1 2 3 0 ; three different stamp types
7 4 0 ; two customers
1 1 0 ; a new set of stamps (two of the same type)
6 2 3 0 ; three customers

Note: the comments in this example are not part of the data file; data files contain only integers.
Output
For each customer, you should print the “best” combination that is exactly equal to the customer’s needs, with a maximum of four stamps. If no such combination exists, print “none”.
The “best” combination is defined as the maximum number of different stamp types. In case of a tie, the combination with the fewest total stamps is best. If still tied, the set with the highest single-value stamp is best. If there is still a tie, print “tie”.

For the sample input file, the output should be:

7 (3): 1 1 2 3
4 (2): 1 3
6 —- none
2 (2): 1 1
3 (2): tie

That is, you should print the customer request, the number of types sold and the actual stamps. In case of no legal allocation, the line should look like it does in the example, with four hyphens after a space. In the case of a tie, still print the number of types but do not print the allocation (again, as in the example).Don’t print extra blank at the end of each line.
Sample Input
1 2 3 0 ; three different stamp types
7 4 0  ; two customers
1 1 0  ; a new set of stamps (two of the same type)
6 2 3 0 ; three customers
Sample Output
7 (3): 1 1 2 3 
4 (2): 1 3 
6 —- none
2 (2): 1 1
3 (2): tie

翻译:
描述

你最近集邮吗?

你已经被卢里塔尼亚邮政服务(RPS)雇佣来设计他们的新的邮费软件。该软件根据客户的需求和目前库存的面额,将邮票分配给客户。

卢里塔尼亚到处都是与集邮者通信的人。作为对这些人的服务,RPS 要求所有的邮票分配中有最大数量的不同类型的邮票。事实上,RPS 为了取悦顾客,已经发行了好几种相同面额的邮票(即使它们的面额相同,这些邮票也被算作不同的类型)。在任何时候,不同类型的邮票的最大发行数量是 25 枚。

为了省钱,RPS 希望发行尽可能少的重复戳记(考虑到他们希望发行尽可能多的不同类型的约束)。此外,RPS 一次不能销售超过 4 个邮票。

输入

程序的输入将是对正整数序列,由两行组成,交替进行,直到文件结束。第一个序列是邮票的可用值,而第二个序列是一系列客户请求。例如:

1 2 3 0;三种不同邮票类型

7 4 0;两个客户

11 10 0;一套新邮票(两款同一类型)

6 2 3 0;三个客户

注意:本例中的注释属于数据文件;数据文件只包含整数。

输出

为每位顾客印制符合其需要的”最佳”邮票组合,最多不超过四枚。如果不存在这样的组合,则打印“none”。

“最佳”组合定义为不同邮票类型的最大数量。如果是平局,最好是总邮票最少的组合。如果仍然是平局,那么具有最高单值邮票的集合是最好的。如果还有领带,打印“tie”。

对于示例输入文件,输出应该为:

7 (3): 1 1 2 3

4 (2): 1

6——没有

2 (2): 11

3(2):领带

也就是说,您应该打印客户请求、销售的类型数量和实际的邮票。在没有合法分配的情况下,行应该看起来像它在示例中所做的那样,在一个空格后面有四个连字符。在 tie 的情况下,仍然打印类型的数量,但不打印分配(同样,如本例所示)。不要在每行的末尾打印额外的空白。

样例输入

1 2 3 0;三种不同邮票类型

7 4 0;两个客户

11 10 0;一套新邮票(两款同一类型)

6 2 3 0;三个客户

样例输出

7 (3): 1 1 2 3

4 (2): 1

6——没有

2 (2): 11

3(2):领带


#include <iostream>
using namespace std;

#define MAX_STAMP_TYPE 100
int stamp[MAX_STAMP_TYPE];
bool tie,none;
int now[4],ans[4];//记录stamp的index
int max_stamp;//记录最大邮票
int getInfo(int sta[]){
    int tmp_a,tmp_b,tmp_c;
    tmp_a=1;
    tmp_b=1;
    tmp_c=sta[0];
    for(int i=1;i<4 && sta[i]>0;i++)
    {
        if(sta[i-1]!=sta[i]) tmp_a++;//取种类数  千位
        tmp_b++;//取总张数  百位
        tmp_c=sta[i-1]>sta[i]?sta[i-1]:sta[i];//取最大值  十位和个位
    }
    return tmp_a*1000+(10-tmp_b)*100+tmp_c;
}
void compare(){
    none=false;//只要有结果,none就置为false
    int nowInfo=getInfo(now);
    int ansInfo=getInfo(ans);
    char r=nowInfo>ansInfo?'g':(nowInfo<ansInfo?'l':'e');//g:出现更优解  l:不如现有解  e:tie
    if(r=='g'){//如果出现更优解,将now中的数据复制到ans中保存
        memcpy(ans,now,sizeof(now));
        tie=false;
    }else if(r=='e'){
        tie=true;
    }
    return;
}
void dfs(int num,int cnt){
    if(num==0){//剩余数为0,即为解的出现条件
        compare();
        return;
    }else if(cnt>=4){//邮票数不能大于4张
        return;
    }else if(num<0){//剩余需分配数不能小于0
        return;
    }else if(num>max_stamp*(4-cnt)){
        return;
    }
    for(int i=(cnt>0?now[cnt-1]:1);i<=stamp[0];i++)
    {
        now[cnt]=i;
        dfs(num-stamp[i],cnt+1);
        now[cnt]=0;
    }
}
int main()
{
    do{
        int tmp,i=1;
        max_stamp=0;
        memset(stamp,0,sizeof(stamp));
        while(cin>>tmp && tmp!=0){
            stamp[i++]=tmp;
            max_stamp=max_stamp>tmp?max_stamp:tmp;
        }
        stamp[0]=i-1;//记录邮票种类数
        while(cin>>tmp && tmp!=0){
            tie=false;
            none=true;
            memset(now,0,sizeof(now));
            memset(ans,0,sizeof(ans));
            dfs(tmp,0);
            if(tie){
                cout<<tmp<<" ("<<getInfo(ans)/1000<<"): "<<"tie"<<endl;
            }else if(none){
                cout<<tmp<<" ---- none"<<endl;
            }else{
                cout<<tmp<<" ("<<getInfo(ans)/1000<<"):";
                for(int i=0;i<4 && ans[i]>0;i++){
                    cout<<" "<<stamp[ans[i]];
                }
                cout<<endl;
            }
        }
    }while(getchar()!=EOF);
    return 0;
}

5.Sticks

Description
George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.
Input
The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.
Output
The output should contains the smallest possible length of original sticks, one per line.
Sample Input
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

Sample Output
6
5
翻译:
描述

乔治拿着同样长度的棍子,随机地切割,直到所有部分都变成最多 50 个单位的长度。现在他想把木棍恢复到原来的状态,但是他忘记了原来有多少根木棍和木棍的长度。请帮助他设计一个程序,计算出这些棍子的最小原始长度。所有以单位表示的长度都是大于零的整数。

输入

输入包含 2 行代码块。第一行是切割后的杆件数量,最多 64 个杆件。第二行包含由空格分隔的部分的长度。文件的最后一行包含 0。

输出

输出应该包含原始杆的尽可能小的长度,每行一个。

样例输入

9

5 2 1 5 2 1 5 2 1

4

1 2 3 4

0

样例输出

6

5

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int n,maxx,sum,arr[70];
bool ispos,vis[70];
// 由大到小排序
bool cmp(int a,int b)
{
    return a>b;
}


void dfs(int res,int js,int pos)
{
    // 找到答案,返回
    if(ispos==1)    return;
    // 如果所有都被选择 ispos置1,表示找到
    if(js==n)   {ispos=1;return;}
    // 如果res=0 且并非所有都被选择,则继续将maxx   dfs
    if(res==0 && js<n)  dfs(maxx,js,0);

    int i;
    for(i=pos;i<n;++i)
    {
        if(!ispos && !vis[i] && arr[i]<=res)
        {
            vis[i]=1;
            dfs(res-arr[i],js+1,pos);
            vis[i]=0;

            // 这个去掉 +40MS
            if(res==arr[i]) return;
            // 这个去掉,TLE。。
            if(res==maxx)   return;
            // 这个剪枝去掉了,+100MS
            while(arr[i]==arr[i+1]) ++i;
        }
    }

}

int main()
{
    int i;
    while(cin>>n)
    {
        if(!n)  break;
        sum=0;
        for(i=0;i<n;++i)
        {
            cin>>arr[i];
            sum+=arr[i];
        }
        sort(arr,arr+n,cmp);
        maxx=arr[0];

        // 剪枝:如果最长的长度大于剩余所有长度和,则答案就是他们的和
        //(这个去掉了也可以,耗时没有变化 = 。=,就是说不写也可以)
        if(maxx>sum-maxx)
        {
           cout<<sum<<endl;
            continue;
        }
        ispos=0;
        while(!ispos)
        {
            // 剪枝: 如果所有长度总和 对 目标长度 取模不为0 ,则目标长度一定不是答案,这个必须有
            // 这个如果去掉,耗时增多不说,对后面剪枝影响,会导致WA
            while(sum%maxx!=0) {++maxx;}

            memset(vis,0,sizeof(vis));
            dfs(maxx,0,0);
            if(ispos)   break;
            ++maxx;
        }
        cout<<maxx<<endl;
    }
    return 0;
}