L1-019 谁先倒

链接
甲、乙两人的酒量（最多能喝多少杯不倒），没注意到是喝多少杯不倒。。。
a、b来表示甲乙，1、2来来表述属性，以免混乱。

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    
    int maxa, maxb;
    int n;
    scanf("%d%d%d", &maxa, &maxb, &n);
    int nowa = 0, nowb = 0;
    for(int i = 1; i <= n; i++) {
    
    	int a1, a2, b1, b2;
    	scanf("%d%d%d%d", &a1, &a2, &b1, &b2);
    	int ans = a1 + b1;
    	if(a2 == ans && b2 != ans) {
    
    		nowa++;
		}
		else if(b2 == ans && a2 != ans) {
    
			nowb++;
		}
		if(nowa > maxa) {
    
			printf("A\n");
			printf("%d", nowb);
			break;
		}
		else if(nowb > maxb) {
    
			printf("B\n");
			printf("%d", nowa);
			break;
		}
	}
}

L2-006 树的遍历

链接
后序数组中最后一个元素即为根，找到对应中序数组中的位置，确定左右子树节点个数，递归即可。

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int b[35];
int c[35];
int tLeft[35];
int tRight[35];
int n;
int build(int lb, int rb, int lc, int rc) {
    
	if(lb > rb) return 0;
	int root = c[rc];
	int index = 0;
	//找到根节点在中序数组中的位置 
	while(b[index] != root) index++;
	int count = index - lb;
	tLeft[root] = build(lb, index-1, lc, lc+count-1);
	tRight[root] = build(index+1, rb, lc+count, rc-1);
	return root;
}
void print(int root) {
    
	queue<int> q;
	q.push(root);
	int count = 1;
	while(!q.empty()) {
    
		int now = q.front();
		printf("%d", now);
		if(count != n) printf(" ");
		count++;
		q.pop();
		if(tLeft[now] != 0) q.push(tLeft[now]);
		if(tRight[now] != 0) q.push(tRight[now]);
	}
}
int main() {
    
	scanf("%d", &n);
	for(int i = 0; i < n; i++) scanf("%d", &c[i]);
	for(int i = 0; i < n; i++) scanf("%d", &b[i]);
	int root = build(0, n-1, 0, n-1);
	print(root);
}

L2-004 这是二叉搜索树吗？

链接
数组存储前序遍历序列，第一个元素为根。sl从左往右扫描，看是否都小于根，sr从右往左扫描，看是否都大于根。递归左右子树，最后将根添加到ans中，ans保存的即为后序序列。
注意：其右子树中所有结点的键值大于等于该结点的键值。

#include <iostream>
#include <cstdio>
#include <vector> 
using namespace std;
int a[1005];
int flag;
vector<int> ans;
void judge(int l, int r) {
    
	if(l > r) return;
	int sl = l + 1;
	int sr = r;
	//非镜像 
	if(flag == 0) {
    
		while(sl <= r && a[sl] < a[l]) sl++;
		//a[l]为根 
		while(sr > l && a[sr] >= a[l]) sr--;
	}
	//镜像 
	else {
    
		while(sl <= r && a[sl] >= a[l]) sl++;
		while(sr > l && a[sr] < a[l]) sr--;
	}
	if(sl - sr != 1) return;
	judge(l+1, sr);
	judge(sl, r);
	ans.push_back(a[l]);
}
int main() {
    
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
    
		scanf("%d", &a[i]);
	}
	judge(0, n-1);
	if(ans.size() != n) {
    
		flag = 1;
		ans.clear();
		judge(0, n-1);
	}
	if(ans.size() != n) printf("NO\n");
	else {
    
		printf("YES\n");
		for(int i = 0; i < n; i++) {
    
			printf("%d", ans[i]);
			if(i != n-1) printf(" ");
		}
	}
}

L2-019 悄悄关注

链接
使用map，输入被其关注的用户的ID时，映射value为1。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring> 
#include <map>
using namespace std;
map<string, int> mp;
struct node {
    
	char id[5];
	int num;
} b[10005];
int flag[10005];
bool cmp(node a, node b) {
    
	return strcmp(a.id, b.id) < 0;
}
int main() {
    
	int n, m, sum = 0;
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
    
		char s[10];
		scanf("%s", s);
		mp[s] = 1;
	}
	scanf("%d", &m);
	for(int i = 0; i < m; i++) {
    
		scanf("%s%d", b[i].id, &b[i].num);
		sum += b[i].num;
	}
	sort(b, b+m, cmp);
	float avg = 1.0 * sum / m;	
	for(int i = 0; i < m; i++) {
    
		if(mp[b[i].id] == 0) flag[i] = 1; 
	}
	int mark = 0;
	for(int i = 0; i < m; i++) {
    
		if(flag[i] == 1 && b[i].num > avg) {
    
			printf("%s\n", b[i].id);
			mark = 1;
		}
	}
	if(mark == 0) printf("Bing Mei You");
}

L2-032 彩虹瓶

链接
简单堆栈模拟

#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
stack<int> s;
int main() {
    
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= k; i++) {
    
		int now = 1;
		int flag = 0;
		while(!s.empty()) s.pop();
		for(int j = 1; j <= n; j++) {
    
			int next;
			scanf("%d", &next);
			if(next == now) {
    
				now++;
				while(!s.empty()) {
    
					if(s.top() == now) {
    
						s.pop();
						now++;
					}
					else break;
				}
			}
			else {
    
				s.push(next);
				if(s.size() > m) {
    
					flag = 1;
					//break;
				}
			}
		}
		if(s.size() == 0 && flag == 0) printf("YES\n");
		else printf("NO\n");
	}
}

L2-024 部落

链接
使用set容器统计社区的总人数。因为所有人的编号从1开始连续编号，所以扫描set集合时，下标i即对应每个人的编号。也可以用迭代器。

//直接扫描
for(int i = 1; i <= s.size(); i++) {
    
	if(fa[i] == i) {
    
		ans++;
	}
}

//迭代器
for(set<int>::iterator it = s.begin(); it != s.end(); it++) {
    
	if(fa[*it] == *it) {
    
		ans++;
	}
}

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
int fa[10005];
set<int> s;
void init() {
    
	for(int i = 1; i <= 10000; i++) {
    
		fa[i] = i;
	}
}
int get(int x) {
    
	if(x == fa[x]) return x;
	return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
    
	x = get(x);
	y = get(y);
	if(x != y) {
    
		fa[x] = y;
	}
}
bool judge(int x, int y) {
    
	if(get(x) == get(y)) return true;
	return false;
}
int main() {
    
	int n;
	scanf("%d", &n);
	init();
	for(int i = 1; i <= n; i++) {
    
		int k, a, last;
		scanf("%d", &k);
		for(int j = 1; j <= k; j++) {
    
			scanf("%d", &a);
			if(j != 1) {
    
				merge(last, a);				
			}
			last = a;
			s.insert(a);
		}
	}
	int ans = 0;
//	for(int i = 1; i <= s.size(); i++) {
    
//		if(fa[i] == i) {
    
//			ans++;
//		}
//	}
	for(set<int>::iterator it = s.begin(); it != s.end(); it++) {
    
		if(fa[*it] == *it) {
    
			ans++;
		}
	} 
	printf("%d %d\n", s.size(), ans);
	int q;
	scanf("%d", &q);
	for(int i = 1; i <= q; i++) {
    
		int x, y;
		scanf("%d%d", &x, &y);
		if(judge(x, y)) printf("Y\n");
		else printf("N\n");
	}
}

L3-003 社交集群

链接
创建一个habit数组，存储每个爱好的祖先。当输入某个人的这个爱好时，就与这个爱好的祖先合并。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int fa[1005];
int habit[1005];
int isRoot[1005];
int n;
int cmp(int a, int b) {
    
	return a > b;
}
void init() {
    
	for(int i = 1; i <= n; i++) {
    
		fa[i] = i;
	}
}
int get(int x) {
    
	if(x == fa[x]) return x;
	return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
    
	x = get(x);
	y = get(y);
	if(x != y) {
    
		fa[x] = y;
	}
}
int main() {
    
	scanf("%d", &n);
	//每个人有k个爱好，每个爱好为h
	int k, h; 
	init(); 
	for(int i = 1; i <= n; i++) {
    
		scanf("%d:", &k);
		for(int j = 1; j <= k; j++) {
    
			scanf("%d", &h);
			if(habit[h] == 0) {
    
				//这个爱好的根节点为第i人 
				habit[h] = i;
			}
			//将i与有相同爱好的人合并
			merge(i, habit[h]);
		}
	}
	int ans = 0; 
	for(int i = 1; i <= n; i++) {
    
		isRoot[get(i)]++ ; 
	}
	for(int i = 1; i <= n; i++) {
    
		if(isRoot[i] != 0) {
    
			ans++;
		}
	}
	printf("%d\n", ans);
	sort(isRoot+1, isRoot+1+n, cmp);
	for(int i = 1; i <= ans; i++) {
    
		printf("%d", isRoot[i]);
		if(i != ans) printf(" ");
	}
	printf("\n");
}