算法刷题记录(Day 31)

poj 2019计算机学科夏令营上机考试
A:数与字符串
#include
using namespace std;
string s;
int main() {
	while (1) {
		cin >> s;
		if (s.size() == 1 && s[0] == '0') break;
		if (s[0] == '9') cout << s < 
B:打印月历 
#include
using namespace std;
int year, month;
long long days;
int day1[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
int day2[13] = { 0,31,29,31,30,31,30,31,31,30,31,30,31 };
int is_leap(int x) {
	if (x % 4 == 0 && (x % 100 != 0 || x % 400 == 0)) return 1;
	else return 0;
}
void count() {
	for (int i = 1900; i != year; i++) {
		if (is_leap(i)) days += 366;
		else days += 365;
	}
}
int main() {
	cin >> year >> month;
	count();
	int* day;
	if (is_leap(year)) day = day2;
	else day = day1;
	for (int i = 1; i < month; i++) days += day[i];
	days++;
	int week = days % 7;
	printf("Sun Mon Tue Wed Thu Fri Satn");
	for (int i = 0; i < week; i++) printf("    ");
	for (int i = 1; i <= day[month]; i++) {
		printf("%3d", i);
		if (week == 6) printf("n");
		else printf(" ");
		week = (week + 1) % 7;
	}

}
 
C:Hopscotch 
题目类型:带方向的爆搜+剪枝
 解题思路：该题最后的输出要求是步数最少的情况下字典序最小，因此逐步增加步数，并在深搜的过程中首先走H，那么这就能保证第一个得到的解一定是符合要求的解。至于如何进行存储，当得到最终的解时便返回1，回溯的过程中将相应的操作压入res栈中，最后再出栈取出即可。
 为了减少爆搜的时间，进行相应的剪枝，即若从当前x全部走H，都到达不了d，且从当前x全部走O，都到达不了d,那么代表这是不可达的，直接返回0即可。 
#include
#include
using namespace std;
#define KMAX 26
int n, m;
long long three[KMAX];
long long two[KMAX];
stack res;
void init() {
	three[1] = 3;
	two[1] = 2;
	for (int i = 2; i < KMAX; i++) {
		three[i] = three[i-1] * 3;
		two[i] = two[i - 1] * 2;
	}
}
int Try(int x, int d, int s) {
	if (x == d) return 1;
	if (s == 0) return 0;
	if ((long long)x * three[s]< (long long )d && (long long) x / two[s]>(long long) d) return 0;//剪枝,必须放在s=0的下方，防止出现除以0的发生
	if (Try(x * 3, d, s - 1)) {
		res.push('H');
		return 1;
	}
	if (Try(x / 2, d, s - 1)) {
		res.push('O');
		return 1;
	}

	return 0;
}
int main() {
	init();
	while (1) {
		cin >> n >> m;
		if (!n && !m) break;
		for (int i = 1; i <= 25; i++) {
			if (Try(n, m, i)) break;
		}
		cout << res.size() << endl;
		while (!res.empty()) {
			cout << res.top();
			res.pop();
		}
		cout << endl;
	}
}
 
D：上楼梯 
#include
#include
using namespace std;
#define KNMAX 51
vector step;
long long num[KNMAX];
int n, k;
void init() {
	for (int i = 1; i <= KNMAX ; i++) {
		if (i % 10 != 4 && i / 10 != 4) step.push_back(i);
	}
}
int main() {
	init();
	//for (int i = 0; i < step.size(); i++) cout << step[i] << " ";
	while (1) {
		cin >> n >> k;
		if (!n && !k) break;
		memset(num, 0, sizeof(num));
		num[0] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; step[j] <= k; j++) {
				if (i - step[j] >= 0) num[i] += num[i - step[j]];
			}
		}
		cout << num[n] << endl;
	}
}
 
G:Falling Leaves 
建树，然后先序读取即可。 
#include
#include
#include
using namespace std;
string line, cur;
stack input;
struct node* root;

struct node {
	char c;
	struct node* left;
	struct node* right;
	node() {
		c = 'A';
		left = NULL;
		right = NULL;
	}
};
void build(char x) {
	struct node* cur = root;
	struct node* pre= root;
	while (cur != NULL) {
		if (x > cur->c) pre = cur, cur = cur->right;
		else pre = cur, cur = cur->left;
	}
	struct node* brand = new node;
	brand->c = x;
	if (x > pre->c) pre->right = brand;
	else pre->left = brand;
}
void read(struct node* cur) {
	if (cur == NULL) return;
	cout << cur->c;
	read(cur->left);
	read(cur->right);
	free(cur);
}
int main() {
	while (1) {
		getline(cin, line);
		if (line == "*" || line == "$") {
			
			root = new node;
			cur = input.top();
			root->c = cur[0];
			input.pop();
			while (!input.empty()) {
				cur = input.top();
				input.pop();
				for (int i = 0; i < cur.size(); i++) build(cur[i]);
			}
			read(root);
			cout << endl;
			if (line == "$") break;
		}
		else input.push(line);
	}
}
 
H:昂贵的聘礼 
题目类型:带限制的最短路
 首先，建立如下的图，其中s代表的是源点，其指向每一个点，边值为本来的价格；若物品b能够得到物品a的优惠价格为c，则建立一条从b到a的边值为c的边。那么这个问题就转化为从s点到达1点的最短距离问题。
 
 对于题目中的等级的限制，虽然表面上来看似乎是一个传递性的关系，但是本质上让然是一个等级的范围。由于最终是一定要和1号节点互换的，因此围绕一号节点，遍历所有可能的等级范围。 
#include
#include
using namespace std;
#define NMAX 110
int level[NMAX];
int map[NMAX][NMAX];
int N, M;
int spfa(int left, int right) {
	queue Q;
	int dist[NMAX];
	int inq[NMAX];
	memset(dist, 0x3f, sizeof(dist));
	memset(inq, 0, sizeof(inq));
	dist[0] = 0;
	inq[0] = 1;
	Q.push(0);
	while (!Q.empty()) {
		int s = Q.front();
		Q.pop();
		inq[s] = 0;
		for (int i = 0; i <= N; i++) {
			if (level[i] >= left && level[i] <= right && dist[i] > dist[s] + map[s][i]) {
				dist[i] = dist[s] + map[s][i];
				if (!inq[i]) {
					Q.push(i);
					inq[i] = 1;
				}
			}
		}
	}
	return dist[1];
}
int main() {
	cin >> M >> N;
	memset(map, 0x3f, sizeof(map));
	for (int i = 1; i <= N; i++) {
		int P, L, X;
		cin >> P >> L >> X;
		map[0][i] = P;
		level[i] = L;
		if (i == 1) level[0] = L;
		for (int j = 0; j < X; j++) {
			int T, V;
			cin >> T >> V;
			map[T][i] = V;
		}
	}
	
	int res = 0x3f3f3f3f;
	for (int i = level[0] - M; i <= level[0]; i++) {
		int cur = spfa(i, i + M);
		if (cur < res) res = cur;
	}
	cout << res;
}
算法刷题记录(Day 31)

C/C++/C#相关栏目本月热门文章
