精华内容
下载资源
问答
  • 本文记载了我在备考PAT刷题的Codeup以及PTA上的题解和部分笔记.

    2021算法笔记Codeup、pat刷题记录

    目录

    《算法笔记》9.1小节——数据结构专题(2)->树与二叉树

    《算法笔记》9.2小节——数据结构专题(2)->二叉树的遍历

    Codeup

    复原二叉树

    #include<iostream>
    #include<string>
    using namespace std;
    struct node {
    	char data;
    	node* lchild;
    	node* rchild;
    };
    string pre, in, post;
    
    node* create(int preL, int preR, int inL, int inR) {
    	if (preR < preL) return NULL;
    	node* root = new node;
    	root->data = pre[preL];
    	int k;
    	for (k = inL;k < inR;++k) {
    		if (in[k] == pre[preL]) break;
    	}
    	int numLeft = k - inL;
    	root->lchild = create(preL + 1, preL + numLeft, inL, k - 1);
    	root->rchild = create(preL + numLeft + 1, preR, k + 1, inR);
    	return root;
    }
    
    void postOrder(node* root) {
    	if (root == NULL) return;
    	postOrder(root->lchild);
    	postOrder(root->rchild);
    	cout << root->data;
    }
    
    int main() {
    	while (cin >> pre >> in) {
    		int n = pre.size();
    		node* root = create(0, n - 1, 0, n - 1);
    		postOrder(root);
    		cout << endl;
    	}
    	return 0;
    }
    

    二叉树

    用的完全二叉树的性质

    #include<cstdio>
    int get_ans(int n, int m) {
    	if (m <= n) {
    		int ans = 1;
    		return ans + get_ans(n, m * 2) + get_ans(n, m * 2 + 1);
    	}
    	return 0;
    }
    int main() {
    	int m, n;
    	while (scanf("%d %d", &m, &n), m != 0 && n != 0) {
    		printf("%d\n", get_ans(n, m));
    	}
    	return 0;
    }
    

    二叉树遍历

    原题

    二叉树遍历

    #include<cstdio>
    #include<cstring>
    struct node {
    	char data;
    	node* lchild;
    	node* rchild;
    };
    char pre[110], len;
    int i = 0;
    node* create() {
    	if (pre[i] == '#') {
    		++i;
    		return NULL;
    	}
    	node* root = new node;
    	root->data = pre[i];
    	++i;
    	root->lchild = create();
    	root->rchild = create();
    	return root;
    }
    
    void inOrder(node* root) {
    	if (root == NULL) return;
    	inOrder(root->lchild);
    	printf("%c ", root->data);
    	inOrder(root->rchild);
    }
    
    int main() {
    	while (scanf("%s", pre) != EOF) {
    		i = 0;
    		len = strlen(pre);
    		node* root = create();
    		inOrder(root);
    		printf("\n");
    	}
    	return 0;
    }
    

    配套实战指南

    PAT A1020 Tree Traversals

    #include<cstdio>
    #include<queue>
    using namespace std;
    const int maxn = 35;
    struct node {
    	int data;
    	node* lchild;
    	node* rchild;
    };
    
    int in[maxn], post[maxn];
    int n;
    
    node* create(int postL, int postR, int inL, int inR) {
    	if (postL > postR) return NULL;
    	node* root = new node;
    	root->data = post[postR];
    	int k;
    	for (k = inR;k >= inL;--k) {//这里是in
    		if (in[k] == post[postR]) break;
    	}
    	int numLeft = k - inL;
    	root->lchild = create(postL, postL + numLeft - 1, inL, k - 1);
    	root->rchild = create(postL + numLeft, postR - 1, k + 1, inR);//记得这里要postR-1
    	return root;
    }
    
    int num = 0;
    void BFS(node* root) {
    	queue<node*> qu;
    	qu.push(root);
    	while (!qu.empty()) {
    		node* top = qu.front();
    		qu.pop();
    		if (num > 0) printf(" ");
    		printf("%d", top->data);
    		++num;
    		if (top->lchild) qu.push(top->lchild);
    		if (top->rchild) qu.push(top->rchild);
    
    	}
    }
    
    int main() {
    	scanf("%d", &n);
    	for (int i = 0;i < n;++i) scanf("%d", &post[i]);
    	for (int i = 0;i < n;++i) scanf("%d", &in[i]);
    	node* root = create(0, n - 1, 0, n - 1);
    	BFS(root);
    	return 0;
    }
    

    1086 Tree Traversals Again

    先序建树,思路是Push时建立结点,Pop时返回NULL,剩余的结点都填充NULL;
    答案的思路好像是Push的次序是先序遍历的顺序,Pop的次序则是中序遍历的顺序,通过先序遍历+中序遍历唯一确定二叉树。

    #include<cstdio>
    #include<cstring>
    
    struct node {
    	int data;
    	node* lchild;
    	node* rchild;
    };
    int n, count = 0;
    char str[5];
    node* create() {//输入时进行递归建树 
    	node* root = new node;
    	getchar();
    	if (count++ < 2 * n) scanf("%s", str);//2N次 
    	if (strcmp(str, "Push") == 0) {
    		int temp;
    		scanf("%d", &temp);
    		root->data = temp;
    		root->lchild = create();
    		root->rchild = create();
    		return root;
    	}
    	else {
    		return NULL;
    	}
    }
    int cnt = 0;
    void postOrder(node* root) {//后序输出 
    	if (root == NULL) return;
    	postOrder(root->lchild);
    	postOrder(root->rchild);
    	if (cnt > 0) printf(" ");
    	printf("%d", root->data);
    	++cnt;
    }
    
    int main() {
    	scanf("%d", &n);
    	node* root = create();
    	postOrder(root);
    	printf("\n");
    	return 0;
    }
    

    前序中序建树

    #include<cstdio>
    #include<cstring>
    #include<stack>
    using namespace std;
    const int maxn = 50;
    struct node {
    	int data;
    	node* lchild;
    	node* rchild;
    };
    int pre[maxn], in[maxn];
    int n;
    
    node* create(int preL, int preR, int inL, int inR) {
    	if (preL > preR) return NULL;
    	node* root = new node;
    	root->data = pre[preL];
    	int k;
    	for (k = inL;k <= inR;++k) {
    		if (in[k] == pre[preL]) break;
    	}
    	int numLeft = k - inL;
    	root->lchild = create(preL + 1, preL + numLeft, inL, k - 1);
    	root->rchild = create(preL + numLeft + 1, preR, k + 1, inR);
    	return root;
    }
    
    int num = 0;
    void postOrder(node* root) {
    	if (root == NULL) return;
    	postOrder(root->lchild);
    	postOrder(root->rchild);
    	if (num > 0) printf(" ");
    	printf("%d", root->data);
    	++num;
    }
    
    int main() {
    	scanf("%d", &n);
    	char str[5];
    	stack<int> st;
    	int x, preIndex = 0, inIndex = 0;
    	for (int i = 0;i < 2 * n;++i) {
    		scanf("%s", str);
    		if (strcmp(str, "Push") == 0) {
    			scanf("%d", &x);
    			pre[preIndex++] = x;
    			st.push(x);
    		}
    		else {
    			in[inIndex++] = st.top();
    			st.pop();
    		}
    	}
    	node* root = create(0, n - 1, 0, n - 1);
    	postOrder(root);
    	return 0;
    }
    

    PAT A1102 Invert a Binary Tree

    根据题目给予的编号关系想到使用静态二叉树。

    #include<cstdio>
    #include<queue>
    #include<algorithm>
    using namespace std;
    const int maxn = 15;
    struct node {
    	int data;
    	int lchild;
    	int rchild;
    	node() {
    		lchild = rchild = -1;
    	}
    }Node[maxn];
    
    bool hashTable[maxn] = { false };//标记根节点 
    int n, root;
    
    void LayerOrder() {
    	int cnt = 0;
    	queue<int> qu;
    	qu.push(root);
    	while (!qu.empty()) {
    		int top = qu.front();
    		qu.pop();
    		if (cnt > 0) printf(" ");
    		printf("%d", top);
    		++cnt;
    		if (Node[top].lchild != -1) qu.push(Node[top].lchild);
    		if (Node[top].rchild != -1) qu.push(Node[top].rchild);
    	}
    	printf("\n");
    }
    int time = 0;
    void inOrder(int root) {
    	if (root == -1) return;
    	inOrder(Node[root].lchild);
    	if (time > 0) printf(" ");
    	printf("%d", Node[root].data);
    	time++;
    	inOrder(Node[root].rchild);
    }
    
    int main() {
    	scanf("%d", &n);
    	for (int i = 0;i < n;++i) {
    		char a, b;
    		scanf("%*c%c %c", &a, &b);
    		Node[i].data = i;
    		if (a >= '0' && a <= '9') {
    			int temp = a - '0';
    			Node[i].lchild = temp;
    			hashTable[temp] = true;
    		}
    		if (b >= '0' && b <= '9') {
    			int temp = b - '0';
    			Node[i].rchild = temp;
    			hashTable[temp] = true;
    		}
    	}
    	for (int i = 0;i < n;++i) {//确定根节点,同时反转二叉树 
    		if (hashTable[i] != true) {
    			root = i;
    		}
    		swap(Node[i].lchild, Node[i].rchild);//反转 
    	}
    	LayerOrder();
    	inOrder(root);
    	return 0;
    }
    

    《算法笔记》9.3小节——数据结构专题(2)->树的遍历

    Codeup

    树查找

    利用完全二叉树的性质

    #include<cstdio>
    #include<vector>
    #include<cmath>
    using namespace std;
    
    int pow(int x, int p) {
    	int ans = 1;
    	for (int i = 0;i < p;++i) {
    		ans *= x;
    	}
    	return ans;
    }
    
    int main() {
    	vector<int> node;
    	int n, d;
    	while (scanf("%d", &n), n) {
    		node.push_back(0);
    		for (int i = 0;i < n;++i) {
    			int temp;
    			scanf("%d", &temp);
    			node.push_back(temp);
    		}
    		scanf("%d", &d);
    		int s = pow(2, d - 1);
    		int t = pow(2, d);
    		if (s > n) {
    			printf("EMPTY\n");
    			node.clear();//这里注意要clear
    			continue;
    		}
    		for (int i = s;i < min(t, n + 1);++i) {
    			if (i > s) printf(" ");
    			printf("%d", node[i]);
    		}
    		printf("\n");
    		node.clear();
    	}
    	return 0;
    }
    

    树的高度

    #include<cstdio>
    #include<vector>
    #include<queue>
    using namespace std;
    struct node {
    	vector<int> child;
    	int height;
    }Node[110];
    
    int BFS() {
    	int height;
    	queue<node> qu;
    	qu.push(Node[1]);
    	while (!qu.empty()) {
    		node top = qu.front();
    		height = top.height;
    		qu.pop();
    		if (top.child.size() != 0) {
    			for (int i = 0;i < top.child.size();++i) {
    				Node[top.child[i]].height = top.height + 1;
    				qu.push(Node[top.child[i]]);
    			}
    
    		}
    	}
    	return height;
    }
    int main() {
    	int n;
    	while (scanf("%d", &n) != EOF) {
    		for (int i = 1;i < n;++i) {
    			int a, b;
    			scanf("%d %d", &a, &b);
    			Node[a].child.push_back(b);
    		}
    		Node[1].height = 1;
    		printf("%d\n", BFS());
    	}
    	return 0;
    }
    
    

    配套实战指南

    PAT A1079 Total Sales of Supply Chain

    题目有点难看懂,其他很常规
    BFS解法

    #include<cstdio>
    #include<vector>
    #include<queue>
    using namespace std;
    const int maxn = 100010;
    struct node {
    	double price;
    	int amount;//销售数量
    	vector<int> child;
    	node() {
    		amount = 0;
    		child.clear();
    	}
    }Node[maxn];
    
    int n;
    double p, r;
    double sum = 0;
    int BFS() {
    	queue<int> qu;
    	qu.push(0);
    	while (!qu.empty()) {
    		int top = qu.front();
    		qu.pop();
    		if (Node[top].child.size() > 0) {
    			for (int i = 0;i < Node[top].child.size();++i) {
    				int c = Node[top].child[i];
    				Node[c].price = Node[top].price * r;
    				qu.push(c);
    			}
    		}
    		else {
    			sum += Node[top].amount * Node[top].price;
    		}
    	}
    	return sum;
    }
    
    int main() {
    	scanf("%d %lf %lf", &n, &p, &r);
    	r = r / 100 + 1;
    	for (int i = 0;i < n;++i) {
    		int temp;
    		scanf("%d", &temp);
    		if (temp == 0) {
    			scanf("%d", &Node[i].amount);
    		}
    		else {
    			for (int j = 0;j < temp;++j) {
    				int child;
    				scanf("%d", &child);
    				Node[i].child.push_back(child);
    			}
    		}
    	}
    	Node[0].price = p;
    	BFS();
    	printf("%.1f", sum);
    	return 0;
    }
    

    DFS解法

    void DFS(int index){
    	if(Node[index].child.size()==0){
    		sum+=Node[index].amount*Node[index].price;
    		return;
    	}
    	for(int i=0;i<Node[index].child.size();++i){
    		Node[Node[index].child[i]].price=Node[index].price*r;
    		DFS(Node[index].child[i]);
    	}
    	
    }
    

    PAT A1090 Highest Price in Supply Chain

    DFS

    #include<cstdio>
    #include<vector>
    #include<cmath>
    using namespace std;
    const int maxn = 100010;
    vector<int> child[maxn];
    int n, maxdepth = 0, cnt = 0;
    double p, r;
    
    void DFS(int index, int depth, int& maxdepth) {
    	if (depth > maxdepth) {
    		maxdepth = depth;
    		cnt = 1;
    	}
    	else if (depth == maxdepth) ++cnt;
    	if (child[index].size() > 0) {
    		for (int i = 0;i < child[index].size();++i) {
    			DFS(child[index][i], depth + 1, maxdepth);
    		}
    	}
    	else {
    		return;
    	}
    }
    
    int main() {
    	scanf("%d %lf %lf", &n, &p, &r);
    	r /= 100;
    	int root;
    	for (int i = 0;i < n;++i) {
    		int temp;
    		scanf("%d", &temp);
    		if (temp == -1) root = i;
    		else {
    			child[temp].push_back(i);
    		}
    	}
    	DFS(root, 0, maxdepth);
    	printf("%.2f %d\n", p * pow(1 + r, maxdepth), cnt);
    	return 0;
    }
    

    因为使用BFS要在struct里面放入height才能实现,所以不太想写-。-

    PAT A1094 The Largest Generation

    DFS

    #include<cstdio>
    #include<vector>
    #include<queue>
    using namespace std;
    const int maxn = 110;
    vector<int> child[maxn];
    int n, m, hashTable[maxn] = { 0 }, maxsize = 0;
    
    void DFS(int index, int height) {
    	++hashTable[height];
    	if (hashTable[height] > hashTable[maxsize]) maxsize = height;
    	for (int i = 0;i < child[index].size();++i) {
    		DFS(child[index][i], height + 1);
    	}
    }
    
    int main() {
    	scanf("%d %d", &n, &m);
    	for (int i = 0;i < m;++i) {
    		int id, t;
    		scanf("%d %d", &id, &t);
    		for (int j = 0;j < t;++j) {
    			int c;
    			scanf("%d", &c);
    			child[id].push_back(c);
    		}
    	}
    	DFS(1, 1);
    	printf("%d %d\n", hashTable[maxsize], maxsize);
    	return 0;
    }
    

    PAT A1106 Lowest Price in Supply Chain

    DFS

    #include<cstdio>
    #include<cmath>
    #include<vector>
    using namespace std;
    const int maxn = 100010;
    
    vector<int> child[maxn];
    int n, mindepth = maxn, cnt = 0;
    double p, r;
    
    void DFS(int index, int depth) {
    	if (depth == mindepth && child[index].size() == 0) ++cnt;
    	if (depth < mindepth && child[index].size() == 0) {
    		mindepth = depth;
    		cnt = 1;
    	}
    	for (int i = 0;i < child[index].size();++i) {
    		DFS(child[index][i], depth + 1);
    	}
    }
    
    int main() {
    	scanf("%d %lf %lf", &n, &p, &r);
    	r /= 100;
    	for (int i = 0;i < n;++i) {
    		int cnum;
    		scanf("%d", &cnum);
    		for (int j = 0;j < cnum;++j) {
    			int c;
    			scanf("%d", &c);
    			child[i].push_back(c);
    		}
    	}
    	DFS(0, 0);
    	printf("%.4f %d", p * pow((1 + r), mindepth), cnt);
    	return 0;
    }
    

    PAT A1004 Counting Leaves

    #include<cstdio>
    #include<vector>
    using namespace std;
    const int maxn = 110;
    vector<int> child[maxn];
    int n, m, hashTable[maxn] = { 0 }, maxheight;
    
    void DFS(int index, int height) {
    	if (child[index].size() == 0) ++hashTable[height];
    	if (height > maxheight) maxheight = height;
    	for (int i = 0;i < child[index].size();++i) {
    		DFS(child[index][i], height + 1);
    	}
    }
    
    int main() {
    	scanf("%d %d", &n, &m);
    	for (int i = 0;i < m;++i) {
    		int id, cnum;
    		scanf("%d %d", &id, &cnum);
    		for (int j = 0;j < cnum;++j) {
    			int c;
    			scanf("%d", &c);
    			child[id].push_back(c);
    		}
    	}
    	DFS(1, 0);
    	for (int i = 0;i <= maxheight;++i) {
    		if (i > 0) printf(" ");
    		printf("%d", hashTable[i]);
    	}
    	printf("\n");
    	return 0;
    }
    

    PAT A1053 Path of Equal Weight

    这题有点难,要注意的点有
    1、要用用path存下路径,方法1是申请path数组,通过递归获得的numNode作为下标,每递归下一层numNode+1;方法2是使用vector<int>path这样递归的时候不需要numNode,当达到递归边界时直接使用path.size()作为循环条件即可。
    2、输出的条件为从大至小输出,因此需要在DFS前先将所有结点的child由大至小排列,这样递归出结果时,结果默认是由大至小。

    #include<cstdio>
    #include<vector>
    #include<algorithm>
    using namespace std;
    const int maxn = 110;
    struct node {
    	int data;
    	vector<int> child;
    }Node[maxn];
    
    int n, m, s;
    vector<int> path;
    
    bool cmp(int a, int b) {
    	return Node[a].data > Node[b].data;
    }
    
    void DFS(int index, int sum) {
    	if (sum > s) return;
    	if (sum == s) {
    		if (Node[index].child.size() == 0) {
    			for (int i = 0;i < path.size();++i) {
    				if (i > 0) printf(" ");
    				printf("%d", Node[path[i]].data);
    			}
    			printf("\n");
    			return;
    		}
    		else return;
    	}
    	for (int i = 0;i < Node[index].child.size();++i) {
    		int child = Node[index].child[i];
    		path.push_back(child);
    		DFS(child, sum + Node[child].data);
    		path.pop_back();
    	}
    }
    
    int main() {
    	scanf("%d %d %d", &n, &m, &s);
    	for (int i = 0;i < n;++i) {
    		scanf("%d", &Node[i].data);
    	}
    	for (int i = 0;i < m;++i) {
    		int id, cnum;
    		scanf("%d %d", &id, &cnum);
    		for (int j = 0;j < cnum;++j) {
    			int child;
    			scanf("%d", &child);
    			Node[id].child.push_back(child);
    		}
    		sort(Node[id].child.begin(), Node[id].child.end(), cmp);
    	}
    	path.push_back(0);
    	DFS(0, Node[0].data);
    	return 0;
    }
    

    《算法笔记》9.4小节——数据结构专题(2)->二叉查找树(BST)

    Codeup

    二叉排序树

    挺坑的,有相同元素也不讲,每个数据后面有空格

    #include<cstdio>
    #include<vector>
    using namespace std;
    struct node {
    	int data;
    	node* lchild, * rchild;
    };
    void insert(node*& root, int data) {
    	if (root == NULL) {
    		root = new node;
    		root->data = data;
    		root->lchild = root->rchild = NULL;
    		return;
    	}
    	if (data < root->data) insert(root->lchild, data);
    	else if (data > root->data) insert(root->rchild, data);//这里不能写else因为会有相同元素
    }
    
    void preOrder(node* root) {
    	if (root == NULL) return;
    	printf("%d ", root->data);
    	preOrder(root->lchild);
    	preOrder(root->rchild);
    }
    
    void inOrder(node* root) {
    	if (root == NULL) return;
    	inOrder(root->lchild);
    	printf("%d ", root->data);
    	inOrder(root->rchild);
    }
    
    void postOrder(node* root) {
    	if (root == NULL) return;
    	postOrder(root->lchild);
    	postOrder(root->rchild);
    	printf("%d ", root->data);
    }
    
    int main() {
    	int n;
    	while (scanf("%d", &n) != EOF) {
    		node* root = NULL;
    		for (int i = 0;i < n;++i) {
    			int temp;
    			scanf("%d", &temp);
    			insert(root, temp);
    		}
    		preOrder(root);
    		printf("\n");
    		inOrder(root);
    		printf("\n");
    		postOrder(root);
    		printf("\n");
    	}
    	return 0;
    }
    

    二叉搜索树

    #include<cstdio>
    #include<iostream>
    #include<string> 
    using namespace std;
    struct node {
    	int data;
    	node* lchild, * rchild;
    };
    bool flag = true;
    
    void insert(node*& root, int data) {
    	if (root == NULL) {
    		root = new node;
    		root->data = data;
    		root->lchild = root->rchild = 0;
    		return;
    	}
    	if (data < root->data) insert(root->lchild, data);
    	else if (data > root->data) insert(root->rchild, data);
    }
    
    void compare(node* root1, node* root2) {//比较函数
    	if (flag == false) return;//如果flag已经为false则直接退出
    	else {
    		if ((root1 == NULL && root2 != NULL) || (root2 == NULL && root1 != NULL)) {
    			flag = false;
    			return;
    		}
    		if (root1 != NULL && root2 != NULL) {
    			if (root1->data != root2->data) {
    				flag = false;
    				return;
    			}
    			else {
    				compare(root1->lchild, root2->lchild);
    				compare(root1->rchild, root2->rchild);
    			}
    		}
    	}
    }
    
    int main() {
    	int n;
    	while (scanf("%d", &n), n) {
    		string num;
    		node* root = NULL, com;
    		getchar();//吸收空格
    		getline(cin, num);
    		for (int i = 0;i < num.length();++i) {
    			insert(root, num[i] - '0');
    		}
    		for (int i = 0;i < n;++i) {
    			num.clear();
    			getline(cin, num);
    			node* comroot = NULL;
    			for (int j = 0;j < num.length();++j) {
    				insert(comroot, num[j] - '0');
    			}
    			flag = true;
    			compare(root, comroot);
    			if (flag == true) printf("YES\n");
    			else printf("NO\n");
    		}
    	}
    	return 0;
    }
    

    配套实战指南

    PAT A1043 Is It a Binary Search Tree

    不要试图去找什么规律,直接构造出树来遍历即可

    #include<cstdio>
    #include<vector>
    using namespace std;
    
    struct node{
    	int data;
    	node* lchild,*rchild;
    };
    int n;
    vector<int> origin,pre,preM,post,postM;
    
    void insert(node* &root,int data){
    	if(root==NULL){
    		root=new node;
    		root->data=data;
    		root->lchild=root->rchild=NULL;
    		return;
    	}
    	if(data<root->data) insert(root->lchild,data);
    	else insert(root->rchild, data);
    }
    
    void preOrder(node *root){
    	if(root==NULL) return;
    	pre.push_back(root->data);
    	preOrder(root->lchild);
    	preOrder(root->rchild);
    }
    
    void preOrderMirror(node *root){
    	if(root==NULL) return;
    	preM.push_back(root->data);
    	preOrderMirror(root->rchild);
    	preOrderMirror(root->lchild);
    }
    
    void postOrder(node *root){
    	if(root==NULL) return;
    	postOrder(root->lchild);
    	postOrder(root->rchild);
    	post.push_back(root->data);
    }
    
    void postOrderMirror(node *root){
    	if(root==NULL) return;
    	postOrderMirror(root->rchild);
    	postOrderMirror(root->lchild);
    	postM.push_back(root->data);
    }
    
    int main(){
    	scanf("%d",&n);
    	node *root=NULL;
    	for(int i=0;i<n;++i){
    		int key;
    		scanf("%d",&key);
    		insert(root,key);
    		origin.push_back(key);
    	}
    	preOrder(root);
    	preOrderMirror(root);
    	if(origin==pre){
    		postOrder(root);
    		printf("YES\n");
    		for(int i=0;i<n;++i){
    			if(i>0) printf(" ");
    			printf("%d",post[i]);
    		}
    	}else if(origin==preM){
    		postOrderMirror(root);
    		printf("YES\n");
    		for(int i=0;i<n;++i){
    			if(i>0) printf(" ");
    			printf("%d",postM[i]);
    		}
    	}else{
    		printf("NO");
    	}
    	printf("\n");
    	return 0;
    }
    

    PAT A1064 Complete Binary Search Tree

    这道题的思路并不好想到,由于二叉查找树通过中序遍历得到的序列是递增序列,因此对静态二叉树中序遍历并将值不断填入,数组中保存的即是BST的层序遍历。

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn = 1010;
    int n, cnt = 1;
    int BST[maxn], CBT[maxn] = { 0 };
    void inOrder(int i) {//中序遍历 
    	if (i > n) return;
    	inOrder(2 * i);
    	CBT[i] = BST[cnt++];
    	inOrder(2 * i + 1);
    }
    
    int main() {
    	scanf("%d", &n);
    	for (int i = 1;i <= n;++i) {
    		scanf("%d", &BST[i]);
    	}
    	sort(BST + 1, BST + n + 1);
    	inOrder(1);
    	for (int i = 1;i <= n;++i) {
    		if (i > 1) printf(" ");
    		printf("%d", CBT[i]);
    	}
    	return 0;
    }
    

    PAT A1099 Build A Binary Search Tree

    将num序列递增排序,即为BST的中序遍历,然后通过中序遍历将数字填入BST中,最后层序遍历输出BST;

    #include<cstdio>
    #include<queue>
    #include<vector>
    #include<algorithm>
    using namespace std;
    const int maxn = 110;
    
    struct node {
    	int data;
    	int lchild, rchild;
    }Node[maxn];
    int cnt = 0, n;
    vector<int> num;
    
    void inOrder(int index) {//中序遍历
    	if (index == -1) return;
    	inOrder(Node[index].lchild);
    	Node[index].data = num[cnt++];
    	inOrder(Node[index].rchild);
    }
    
    void BFS() {//层序遍历
    	queue<int> qu;
    	qu.push(0);
    	while (!qu.empty()) {
    		int top = qu.front();
    		qu.pop();
    		if (cnt > 0) printf(" ");
    		++cnt;
    		printf("%d", Node[top].data);
    		if (Node[top].lchild != -1) qu.push(Node[top].lchild);
    		if (Node[top].rchild != -1) qu.push(Node[top].rchild);
    	}
    }
    
    
    int main() {
    	scanf("%d", &n);
    	for (int i = 0;i < n;++i) scanf("%d %d", &Node[i].lchild, &Node[i].rchild);
    	for (int i = 0;i < n;++i) {
    		int temp;
    		scanf("%d", &temp);
    		num.push_back(temp);
    	}
    	sort(num.begin(), num.end());//排序后即为中序遍历
    	inOrder(0);
    	cnt = 0;
    	BFS();
    	return 0;
    }
    

    《算法笔记》9.5小节——数据结构专题(2)->平衡二叉树(AVL)

    Codeup

    算法9-9~9-12:平衡二叉树的基本操作

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    struct node {
    	int data, height;
    	node* lchild, * rchild;
    };
    int n, k;
    
    int getHeight(node* root) {
    	if (root == NULL) return 0;
    	return root->height;
    }
    
    int getBalanceFactor(node* root) {
    	return getHeight(root->lchild) - getHeight(root->rchild);
    }
    
    void updateHeight(node* root) {
    	root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
    }
    
    void L_rotate(node*& root) {
    	node* temp = root->rchild;
    	root->rchild = temp->lchild;
    	temp->lchild = root;
    	updateHeight(root);
    	updateHeight(temp);
    	root = temp;
    }
    
    void R_rotate(node*& root) {
    	node* temp = root->lchild;
    	root->lchild = temp->rchild;
    	temp->rchild = root;
    	updateHeight(root);
    	updateHeight(temp);
    	root = temp;
    }
    
    void insert(node*& root, int data) {
    	if (root == NULL) {
    		root = new node;
    		root->data = data;
    		root->lchild = root->rchild = NULL;
    		root->height = 1;
    		return;
    	}
    	if (data < root->data) {
    		insert(root->lchild, data);
    		updateHeight(root);
    		if (getBalanceFactor(root) == 2) {
    			if (getBalanceFactor(root->lchild) == 1) {
    				R_rotate(root);
    			}
    			else if (getBalanceFactor(root->lchild) == -1) {
    				L_rotate(root->lchild);
    				R_rotate(root);
    			}
    		}
    	}
    	else {
    		insert(root->rchild, data);
    		updateHeight(root);
    		if (getBalanceFactor(root) == -2) {
    			if (getBalanceFactor(root->lchild) == -1) {
    				L_rotate(root);
    			}
    			else if (getBalanceFactor(root->lchild) == 11) {
    				R_rotate(root->lchild);
    				L_rotate(root);
    			}
    		}
    	}
    }
    
    void search(node* root, int x) {
    	if (root == NULL) {
    		printf("0 ");
    		return;
    	}
    	if (x == root->data) {
    		printf("1 ");
    		return;
    	}
    	else if (x < root->data) search(root->lchild, x);
    	else search(root->rchild, x);
    
    }
    
    int main() {
    	while (scanf("%d %d", &n, &k) != EOF) {
    		node* root;
    		for (int i = 0;i < n;++i) {
    			int temp;
    			scanf("%d", &temp);
    			insert(root, temp);
    		}
    		for (int i = 0;i < k;++i) {
    			int s;
    			scanf("%d", &s);
    			search(root, s);
    		}
    	}
    
    	return 0;
    }
    

    配套实战指南

    PAT A1066 Root of AVL Tree

    代码很长,但其实没有特别难
    最开始提交全部段错误,对比了一下参考书上发现写的没问题,在本地运行也没问题,最后把node* root放在外面定义了,就能AC了,原因有些不明

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    
    struct node {
    	int data, height;
    	node* lchild, * rchild;
    }*root;
    
    int getHeight(node* root) {
    	if (root == NULL) return 0;
    	return root->height;
    }
    
    int getBalanceFactor(node* root) {
    	return getHeight(root->lchild) - getHeight(root->rchild);
    }
    
    void updateHeight(node* root) {
    	root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
    }
    
    void L_rotate(node*& root) {//用引用 
    	node* temp = root->rchild;
    	root->rchild = temp->lchild;
    	temp->lchild = root;
    	updateHeight(root);
    	updateHeight(temp);
    	root = temp;
    }
    
    void R_rotate(node*& root) {
    	node* temp = root->lchild;
    	root->lchild = temp->rchild;
    	temp->rchild = root;
    	updateHeight(root);
    	updateHeight(temp);
    	root = temp;
    }
    
    void insert(node*& root, int data) {
    	if (root == NULL) {
    		root = new node;
    		root->data = data;
    		root->lchild = root->rchild = NULL;
    		root->height = 1;
    		return;
    	}
    	if (data < root->data) {
    		insert(root->lchild, data);
    		updateHeight(root);
    		if (getBalanceFactor(root) == 2) {
    			if (getBalanceFactor(root->lchild) == 1) {
    				R_rotate(root);
    			}
    			else if (getBalanceFactor(root->lchild) == -1) {
    				L_rotate(root->lchild);
    				R_rotate(root);
    			}
    		}
    	}
    	else {
    		insert(root->rchild, data);
    		updateHeight(root);
    		if (getBalanceFactor(root) == -2) {
    			if (getBalanceFactor(root->rchild) == -1) {
    				L_rotate(root);
    			}
    			else if (getBalanceFactor(root->rchild) == 1) {
    				R_rotate(root->rchild);
    				L_rotate(root);
    			}
    		}
    	}
    }
    
    int main() {
    	int n;
    	scanf("%d", &n);
    	//node* root;
    	for (int i = 0;i < n;++i) {
    		int data;
    		scanf("%d", &data);
    		insert(root, data);
    	}
    	printf("%d", root->data);
    	return 0;
    }
    

    《算法笔记》9.6小节——数据结构专题(2)->并查集

    Codeup

    通信系统

    每个端点不会重复收到信息。因此并查集中只能有一个根结点,而且不能有环。判断不能有环可以用结点数-1大于等于边数,其实是连通图而且不会形成环的时候结点数-1=边数。

    #include<cstdio>
    const int maxn = 1010;
    int father[maxn];
    bool isRoot[maxn] = { false };
    
    void init(int n) {
    	for (int i = 1;i <= n;++i) {
    		father[i] = i;
    		isRoot[i] = false;
    	}
    }
    
    int findFather(int x) {
    	int a = x;
    	while (x != father[x]) {
    		x = father[x];
    	}
    	while (a != father[a]) {
    		int z = a;
    		a = father[a];
    		father[z] = x;
    	}
    	return x;
    }
    
    void Union(int a, int b) {
    	int faA = findFather(a);
    	int faB = findFather(b);
    	if (faA != faB) {
    		father[faA] = faB;
    	}
    }
    
    int main() {
    	int n, m, a, b;
    	while (scanf("%d %d", &n, &m), m || n) {
    		init(n);
    		for (int i = 0;i < m;++i) {
    			scanf("%d %d", &a, &b);
    			Union(a, b);
    		}
    		for (int i = 1;i <= n;++i) {
    			isRoot[findFather(i)] = true;
    		}
    		int ans = 0;
    		for (int i = 1;i <= n;++i) {
    			ans += isRoot[i];
    		}
    		if (ans == 1 && m == n - 1) printf("Yes\n");
    		else printf("No\n");
    	}
    	return 0;
    }
    

    畅通工程

    #include<cstdio>
    const int maxn = 1010;
    int father[maxn];
    int isRoot[maxn] = { 0 };
    
    void init(int n) {
    	for (int i = 1;i <= n;++i) {
    		father[i] = i;
    		isRoot[i] = 0;
    	}
    }
    
    int findFather(int x) {
    	int a = x;
    	while (x != father[x]) {
    		x = father[x];
    	}
    	while (a != father[a]) {
    		int z = a;
    		a = father[a];
    		father[z] = x;
    	}
    	return x;
    }
    
    void Union(int a, int b) {
    	int faA = findFather(a);
    	int faB = findFather(b);
    	if (faA != faB) {
    		father[faA] = faB;
    	}
    }
    
    int main() {
    	int m, n, a, b;
    	while (scanf("%d", &n), n) {
    		scanf("%d", &m);
    		init(n);
    		for (int i = 0;i < m;++i) {
    			scanf("%d %d", &a, &b);
    			Union(a, b);
    		}
    		for (int i = 1;i <= n;++i) {
    			++isRoot[findFather(i)];
    		}
    		int cnt = 0;
    		for (int i = 1;i <= n;++i) {
    			if (isRoot[i] > 0) ++cnt;
    		}
    		printf("%d\n", cnt - 1);
    
    	}
    	return 0;
    }
    

    How Many Tables

    #include<cstdio>
    const int maxn = 1010;
    int father[maxn];
    bool isRoot[maxn] = { false };
    
    void init(int n) {
    	for (int i = 1;i <= n;++i) {
    		father[i] = i;
    		isRoot[i] = false;
    	}
    }
    
    int findFather(int x) {
    	int a = x;
    	while (x != father[x]) {
    		x = father[x];
    	}
    	while (a != father[a]) {
    		int z = a;
    		a = father[a];
    		father[z] = x;
    	}
    	return x;
    }
    
    void Union(int a, int b) {
    	int faA = findFather(a);
    	int faB = findFather(b);
    	if (faA != faB) {
    		father[faA] = faB;
    	}
    }
    
    int main() {
    	int t;
    	scanf("%d", &t);
    	for (int i = 0;i < t;++i) {
    		int n, m, a, b;
    		scanf("%d %d", &n, &m);
    		init(n);
    		for (int j = 0;j < m;++j) {
    			scanf("%d %d", &a, &b);
    			Union(a, b);
    		}
    		for (int j = 1;j <= n;++j) {
    			isRoot[findFather(j)] = true;
    		}
    		int cnt = 0;
    		for (int j = 1;j <= n;++j) {
    			if (isRoot[j] == true) ++cnt;
    		}
    		printf("%d\n", cnt);
    	}
    	return 0;
    }
    

    More is better

    题目不难但写了很久,粗心死

    #include<cstdio>
    const int maxn = 10000010;
    int friends[maxn];
    int isRoot[maxn] = { 0 };
    
    void init() {
    	for (int i = 1;i < maxn;++i) {
    		friends[i] = i;
    		isRoot[i] = 0;
    	}
    }
    
    int findFriends(int x) {
    	int a = x;
    	while (x != friends[x]) x = friends[x];
    	while (a != friends[a]) {
    		int z = a;
    		a = friends[a];
    		friends[z] = x;
    	}
    	return x;
    }
    
    void Union(int a, int b) {
    	int frA = findFriends(a);
    	int frB = findFriends(b);
    	if (frA != frB) {
    		friends[frA] = frB;
    	}
    }
    
    int main() {
    	int n;
    	while (scanf("%d", &n) != EOF) {
    		init();
    
    		for (int i = 0;i < n;++i) {
    			int a, b;
    			scanf("%d %d", &a, &b);
    			Union(a, b);
    		}
    		int max = 0;
    		for (int i = 1;i < maxn;++i) {
    			++isRoot[findFriends(i)];
    			if (isRoot[friends[i]] > max) max = isRoot[friends[i]];
    		}
    		printf("%d\n", max);
    	}
    
    	return 0;
    }
    

    配套实战指南

    1107 Social Clusters

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    
    const int maxn=1010;
    int father[maxn];
    int isRoot[maxn]={0};
    int course[maxn]={0};
    
    void init(int n){
    	for(int i=1;i<=n;++i){
    		father[i]=i;
    		isRoot[i]={0};
    	}
    }
    
    int findFather(int x){
    	int a=x;
    	while(x!=father[x]){
    		x=father[x];
    	}
    	while(a!=father[a]){
    		int z=a;
    		a=father[a];
    		father[z]=x;
    	}
    	return x;
    }
    
    void Union(int a,int b){
    	int farA=findFather(a);
    	int farB=findFather(b);
    	if(farA!=farB){
    		father[farA]=farB;
    	}
    }
    
    bool cmp(int a,int b){
    	return a>b;
    }
    
    int main(){
    	int n;
    	scanf("%d",&n);
    	init(n);//别忘了初始化 
    	for(int i=1;i<=n;++i){
    		int m;
    		scanf("%d:",&m);
    		for(int j=0;j<m;++j){
    			int k;
    			scanf("%d",&k);
    			if(course[k]==0){
    				course[k]=i;
    			}else{
    				Union(i,findFather(course[k]));//注意这里要写findFather(course[k]) 
    			}
    		}
    	}
    	for(int i=1;i<=n;++i){
    			++isRoot[findFather(i)];
    		}
    		int ans=0;
    		for(int i=1;i<=n;++i){
    			if(isRoot[i]>0) ++ans;
    		}
    		printf("%d\n",ans);
    		sort(isRoot+1,isRoot+n+1,cmp);
    		for(int i=1;i<=ans;++i){
    			if(i>1) printf(" ");
    			printf("%d",isRoot[i]);
    		}
    	return 0;
    }
    

    《算法笔记》9.7小节——数据结构专题(2)->堆

    Codeup

    算法10-10,10-11:堆排序

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn = 100010;
    int heap[maxn];
    int n;
    void downAdjust(int low, int high) {
    	int i = low, j = 2 * i;
    	while (j <= high) {//j<=high 不是j<=n 
    		if (j + 1 <= high && heap[j + 1] > heap[j]) {
    			j = j + 1;
    		}
    		if (heap[j] > heap[i]) {
    			swap(heap[j], heap[i]);
    			i = j;
    			j = i * 2;
    		}
    		else {
    			break;
    		}
    	}
    }
    
    void createHeap() {
    	for (int i = n / 2;i >= 1;--i) {
    		downAdjust(i, n);
    	}
    }
    
    void heapSort() {
    	createHeap();
    	for (int i = n;i > 1;--i) {
    		swap(heap[i], heap[1]);
    		downAdjust(1, i - 1);
    	}
    }
    
    int main() {
    	while (scanf("%d", &n) != EOF) {
    		for (int i = 1;i <= n;++i) {
    			scanf("%d", &heap[i]);
    		}
    		heapSort();
    		for (int i = 1;i <= n;++i) printf("%d ", heap[i]);
    		printf("\n");
    	}
    	return 0;
    }
    

    序列合并

    题目给的数据量相当大,最开始想直接堆排序硬解,然后就收获了一堆的运行错误,然后尝试vector,一样运行错误,网上搜到的代码思路

    #include<cstdio>
    const int maxn = 100010;
    int heap[maxn];
    int a[maxn], b[maxn];
    int n;
    void downAdjust(int low, int high) {
    	int i = low, j = 2 * i;
    	while (j <= high) {
    		if (j + 1 <= high && heap[j + 1] > heap[j]) j = j + 1;
    		if (heap[j] > heap[i]) {
    			swap(heap[i], heap[j]);
    			i = j;
    			j = 2 * i;
    		}
    		else {
    			break;
    		}
    	}
    }
    
    void createHeap() {
    	for (int i = n / 2;i >= 1;--i) {
    		downAdjust(i, n);
    	}
    }
    
    void heapSort() {
    	for (int i = n;i > 1;--i) {
    		swap(heap[1], heap[i]);
    		downAdjust(1, i - 1);
    	}
    }
    
    int main() {
    	while (scanf("%d", &n) != EOF) {
    		for (int i = 1;i <= n;++i) {
    			scanf("%d", &a[i]);
    		}
    		for (int i = 1;i <= n;++i) {
    			scanf("%d", &b[i]);
    			heap[i] = a[1] + b[i];//先将a[1]与b中各元素的加和创建堆
    		}
    		createHeap();
    		for (int i = 2;i <= n;++i) {//对其他结果遍历
    			for (int j = 1;j <= n;++j) {
    				int x = a[i] + b[j];
    				if (x < heap[1]) {//heap[1]为大堆顶中最大的元素
    					heap[1] = x;
    					downAdjust(1, n);//插入x
    				}
    				else break;//如果大于最大元素则无需入堆
    			}
    		}
    		heapSort();
    		for (int i = 1;i <= n;++i) {
    			if (i > 1) printf(" ");
    			printf("%d", heap[i]);
    		}
    		printf("\n");
    	}
    	return 0;
    }
    

    合并果子(堆)

    小顶堆堆实现

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn = 30010;
    int n;
    int heap[maxn];
    void downAdjust(int low, int high) {//向下调整
    	int i = low, j = 2 * i;
    	while (j <= high) {
    		if (j + 1 <= high && heap[j + 1] < heap[j]) {
    			j = j + 1;
    		}
    		if (heap[j] < heap[i]) {
    			swap(heap[i], heap[j]);
    			i = j;
    			j = 2 * i;
    		}
    		else {
    			break;
    		}
    	}
    }
    
    void upAdjust(int low, int high) {//向上调整
    	int i = high, j = i / 2;
    	while (j >= low) {
    		if (heap[j] > heap[i]) {
    			swap(heap[j], heap[i]);
    			i = j;
    			j = i / 2;
    		}
    		else break;
    	}
    }
    
    void createHeap() {//创建堆
    	for (int i = n / 2;i >= 1;--i) {
    		downAdjust(i, n);
    	}
    }
    
    int deleteTop() {//删除堆顶元素并返回元素值
    	int temp = heap[1];
    	heap[1] = heap[n--];
    	downAdjust(1, n);
    	return temp;
    }
    
    void insert(int x) {//插入新元素
    	heap[++n] = x;
    	upAdjust(1, n);
    }
    
    int main() {
    	int ans = 0;
    	scanf("%d", &n);
    	for (int i = 1;i <= n;++i) {
    		scanf("%d", &heap[i]);
    	}
    	createHeap();
    	while (n > 1) {
    		int a = deleteTop();
    		int b = deleteTop();//得到小堆顶的两个最小元素
    		insert(a + b);//将其相加并将两元素和插入堆中
    		ans += a + b;
    	}
    	printf("%d", ans);
    	return 0;
    }
    

    优先队列实现

    #include<cstdio>
    #include<queue>
    using namespace std;
    
    priority_queue<int, vector<int>, greater<int>> q;
    
    int main() {
    	int n;
    	int temp, x, y, ans = 0;
    	scanf("%d", &n);
    	for (int i = 0;i < n;++i) {
    		scanf("%d", &temp);
    		q.push(temp);
    	}
    	while (q.size() > 1) {
    		x = q.top();
    		q.pop();
    		y = q.top();
    		q.pop();
    		q.push(x + y);
    		ans += x + y;
    	}
    	printf("%d\n", ans);
    	return 0;
    }
    

    配套实战指南

    PAT A1098 Insertion or Heap Sort

    #include<cstdio>
    #include<vector>
    #include<algorithm>
    using namespace std;
    const int maxn = 110;
    vector<int> origin, tempOri, changed;
    int n;
    
    bool insertSort() {
    	bool flag = false;
    	for (int i = 2;i < n;++i) {
    		if (i != 2 && tempOri == changed) {
    			flag = true;
    		}
    		int j = i, temp = tempOri[i];
    		while (tempOri[j - 1] > temp && j > 1) {
    			tempOri[j] = tempOri[j - 1];
    			--j;
    		}
    		tempOri[j] = temp;
    		if (flag) return true;
    	}
    	return false;
    }
    
    void downAdjust(int low, int high) {
    	int i = low, j = 2 * i;
    	while (j <= high) {
    		if (j + 1 <= high && tempOri[j + 1] > tempOri[j]) j = j + 1;
    		if (tempOri[j] > tempOri[i]) {
    			swap(tempOri[j], tempOri[i]);
    			i = j;
    			j = 2 * i;
    		}
    		else {
    			break;
    		}
    	}
    }
    
    void createHeap() {
    	for (int i = n / 2;i >= 1;--i) {
    		downAdjust(i, n);
    	}
    }
    
    void heapSort() {
    	createHeap();
    	bool flag = false;
    	for (int i = n;i > 1;--i) {
    		if (tempOri == changed) flag = true;
    		swap(tempOri[1], tempOri[i]);
    		downAdjust(1, i - 1);
    		if (flag == true) {
    			return;
    		}
    	}
    }
    
    int main() {
    	int temp;
    	origin.push_back(0);
    	tempOri.push_back(0);
    	changed.push_back(0);
    	scanf("%d", &n);
    	for (int i = 0;i < n;++i) {
    		scanf("%d", &temp);
    		origin.push_back(temp);
    	}
    	tempOri = origin;
    	for (int i = 0;i < n;++i) {
    		scanf("%d", &temp);
    		changed.push_back(temp);
    	}
    	if (insertSort()) {
    		printf("Insertion Sort\n");
    		for (int i = 1;i <= n;++i) {
    			if (i > 1) printf(" ");
    			printf("%d", tempOri[i]);
    		}
    	}
    	else {
    		tempOri = origin;
    		heapSort();
    		printf("Heap Sort\n");
    		for (int i = 1;i <= n;++i) {
    			if (i > 1) printf(" ");
    			printf("%d", tempOri[i]);
    		}
    	}
    	return 0;
    }
    

    100000617 - 《算法笔记》9.8小节——图算法专题->哈夫曼树

    算法6-12:自底向上的赫夫曼编码

    算法6-13:自顶向下的赫夫曼编码

    哈夫曼树

    #include<cstdio>
    #include<queue>
    using namespace std;
    
    priority_queue<int, vector<int>, greater<int>> q;
    
    int main() {
    	int n;
    	while (scanf("%d", &n) != EOF) {
    		int temp, x, y, ans = 0;
    		for (int i = 0;i < n;++i) {
    			scanf("%d", &temp);
    			q.push(temp);
    		}
    		while (q.size() > 1) {
    			x = q.top();
    			q.pop();
    			y = q.top();
    			q.pop();
    			q.push(x + y);
    			ans += x + y;
    		}
    		printf("%d\n", ans);
    		q.pop();
    	}
    	return 0;
    }
    

    Haffman编码

    合并果子

    同上一节

    展开全文
  • 算法笔记CodeUp第一至第六章刷题记录

    千次阅读 多人点赞 2019-09-01 21:27:54
    本文记载了我在CodeUp刷题的题解和些许想法.

    文章目录


    《算法笔记》2.2小节——C/C++快速入门->顺序结构

    http://codeup.cn/contest.php?cid=100000566

    1.例题1-1-1 按要求输出信息(1)

    #include <stdio.h>
    
    int main()
    {
        printf("%s", "This is my first c program!");
        return 0;
    }
    

    2.例题1-1-2 按要求输出信息(2)

    #include <stdio.h>
    
    int main() 
    {
        char *asterisk = "********************";
        char *s = "Very Good!";
        printf("%s\n%s\n%s", asterisk, s, asterisk);
        return 0;
    }
    

    3.例题1-2-1 求两个整数之和(1)

    int main()
    {
        /* 设置3个变量a, b, sum,其中a, b用来存放两个整数,sum用来存放a, b两个数的和,
        通过赋值(即采用赋值运算符"=")的方式将a初始化为123,b初始化为456,并把两个
        变量相加的结果赋值给sum。*/
        int a, b, sum;
        a = 123, b = 456;
        sum = a + b;
        printf("sum=%d", sum);
        return 0;
    }
    

    4.例题1-2-2 求两整数数之和(2)

    #include <stdio.h>
    
    int main()
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d", a+b);
        return 0;
    }
    

    5.例题3-5 求一元二次方程的根

    #include <stdio.h>
    #include <math.h>
    int main()
    { 
        /*
        求一元二次方程ax2+bx+c=0的根,三个系数a, b, c由键盘输入,且a不能为0,且保证b2-4ac>0。
        程序中所涉及的变量均为double类型。
        输入 以空格分隔的一元二次方程的三个系数,双精度double类型
        输出 分行输出两个根如下(注意末尾的换行):
            r1=第一个根
            r2=第二个根
        结果输出时,宽度占7位,其中小数部分2位。*/
        double a, b, c;
        scanf("%lf%lf%lf", &a, &b, &c);
        double r1, r2;
        // 求根公式 x=[-b±√(b2-4ac)]/2a 
        r1 = (double)((-b + sqrt(pow(b, 2.0) - 4*a*c)) / (2 * a));
        r2 = (double)((-b - sqrt(pow(b, 2.0) - 4*a*c)) / (2 * a));
        printf("r1=%7.2f\nr2=%7.2f", r1, r2);
    }
    

    6.例题3-9 字符输入输出

    #include <stdio.h>
    int main()
    {
        /* 从键盘输入三个字符BOY,然后把他们输出到屏幕上
        输入 BOY三个字符,中间无分隔符
        输出 BOY,注意末尾的换行 */
        char s[10];
        scanf("%s", s);
        printf("%s", s);
        return 0;
    }
    

    《算法笔记》2.3小节——C/C++快速入门->选择结构

    http://codeup.cn/contest.php?cid=100000567

    1.例题4-1 一元二次方程求根

    #include <stdio.h>
    #include <math.h>
    int main()
    { 
        /* 不保证b2-4ac>0, 如果方程无实根,输出一行如下信息(注意末尾的换行)
        No real roots! */
        double a, b, c, cond, r1, r2;
        scanf("%lf%lf%lf", &a, &b, &c);
        cond = pow(b, 2.0) - 4*a*c;
        if (cond >= 0) {
            r1 = (double)(-b + sqrt(cond));
            r2 = (double)(-b - sqrt(cond));
            printf("r1=%7.2f\nr2=%7.2f", r1, r2);
        } else {
            printf("No real roots!\n")
        }
        return 0;
    } 
    

    2.例题4-2 比较交换实数值

    #include <stdio.h>
    int main()
    {
        /* 
        输入 用空格分隔的两个实数。
        输出 从小到大输出这两个实数,中间以空格来分隔,
        小数在前,大数在后。小数点后保留2位小数。末尾输出换行符。 */
        double a, b;
        scanf("%lf%lf", &a, &b);
        if (a > b) {
            printf("%.2f %.2f", b, a);
        } else {
            printf("%.2f %.2f", a, b);
        }
        return 0;
    }
    

    3.例题4-3 比较交换3个实数值,并按序输出

    #include <stdio.h>
    void swap(double *a, double *b) {
        double temp;
        temp = *a;
        *a = *b;
        *b = temp;
    }
    int main()
    {
        /*
        输入 输入以空格分隔的三个实数
        输出 按照从小到大的顺序输出这三个实数,中间以空格分隔,最小值在前,
        最大值在后。小数点后保留2位小数。末尾输出换行。
        */
        double a, b, c;
        scanf("%lf%lf%lf", &a, &b, &c);
        if (a > b) swap(&a, &b);
        if (b > c) swap(&b, &c);
        if (a > b) swap(&a, &b);
        printf("%.2f %.2f %.2f\n", a, b, c);
        return 0;
    }
    

    4.习题4-4 三个整数求最大值

    #include <stdio.h>
    
    int main()
    {
        /* 输入 以空格分割的三个整数。
        输出 三个数中的最大值,末尾换行。*/
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if (a >= b && a >= c) printf("%d\n", a);
        else if (b >= a && b >= c) printf("%d\n", b);
        else if (c >= a && c >= b) printf("%d\n", c);
        return 0;
    }
    

    5.习题4-10-1 奖金计算

    #include <stdio.h>
    
    int main()
    {
        double income, bonus;
        scanf("%lf", &income);
        /* 某企业发放的奖金根据利润提成。利润I低于或等于100000时,奖金可提10%;
        利润(100000<I<=200000)时,低于100000元的部分仍按10%提成,高于100000元的部分提成比例为7.5%;
        200000<I<=400000时,低于200000元的部分仍按上述方法提成(下同),高于200000元的部分按5%提成;
        400000<I<=600000元时,高于400000元的部分按3%提成;
        600000<I<=1000000时,高于600000元的部分按1.5%提成;
        I>1000000元时,超过1000000元的部分按1%提成。
        输入 企业利润,小数,双精度double类型
        输出 应发奖金数,保留2位小数,末尾换行。*/
        double b1, b2, b3, b4, b5;
        b1 = (double)(100000 * 10) / 100;
        b2 = b1 + (double)(100000 * 7.5) / 100;
        b3 = b2 + (double)(200000 * 5) / 100;
        b4 = b3 + (double)(200000 * 3) / 100;
        b5 = b4 + (double)(400000 * 1.5) / 100;
        if (income <= 100000) {
            bonus = (double)(income * 10) / 100;
        } else if (100000 < income && income <= 200000) {
            bonus = b1 + ((income - 100000) * 7.5) / 100;
        } else if (200000 < income && income <= 400000) {
            bonus = b2 + ((income - 200000) * 5.0) / 100;
        } else if (400000 < income && income <= 600000) {
            bonus = b3 + ((income - 400000) * 3.0) / 100;
        } else if (600000 < income && income <= 1000000) {
            bonus = b4 + ((income - 600000) * 1.5) / 100;
        } else {
            bonus = b5 + ((income - 1000000) * 1.0) / 100;
        }
        printf("%.2f\n", bonus);
        return 0;
    }
    

    《算法笔记》2.4小节——C/C++快速入门->循环结构

    http://codeup.cn/contest.php?cid=100000567

    问题 A: 例题5-1-1 连续自然数求和

    #include <stdio.h>
    int main() 
    {
        int i=1, sum=0;
        while (i <= 100) {
            sum += i;
            i++;
        }
        printf("%d\n", sum);
        return 0;
    }
    /*---------------------------------------------------*/
    #include <stdio.h>
    int main() 
    {
        printf("%d\n", 100 * (100 + 1) / 2);
        return 0;
    }
    

    问题 B: 例题5-1-2 连续自然数求和

    #include <stdio.h>
    int main() 
    {
        int i = 0, sum = 0;
        do {
            sum += i;
            i++;
        } while (i <= 100);
        printf("%d\n", sum);
        return 0;
    }
    

    问题 C: 例题5-1-3 连续自然数求和

    #include <cstdio>
    int main() 
    {
        int sum = 0;
        for (int i = 0; i < 100; i++, sum+=i);
        printf("%d\n", sum);
        return 0;
    }
    

    问题 D: 例题5-1-4 连续自然数求和

    #include <cstdio>
    int main() 
    {
        int n;
        scanf("%d", &n);
        printf("%d\n", n * (n + 1) / 2);
        return 0;
    }
    

    问题 E: 例题5-1-5 连续自然数求和

    #include <cstdio>
    int main() {
        /* 求1+2+3+...和的程序,要求得到使和数大于1000的最小正整数N。*/
        int i, sum = 0;
        for (i = 1; sum <= 1000; i++, sum += i);
        printf("%d\n", i);
        return 0;
    }
    
    

    问题 F: 例题5-6 矩阵输出

    #include <cstdio>
    int main() {
        for (int i=1; i <= 4; i++) {
        	for (int j=1; j <= 5; j++) {
        		printf("%3d", i*j);
    	        if (i * j % 5 == 0) 
    	            printf("\n");	
    		} 
        }
        return 0;
    }
    

    问题 G: 例题5-7 求圆周率pi的近似值

    #include <cstdio>
    /* 用如下公式 pi/4 = 1-1/3+1/5-1/7....求圆周率PI的近似值,直到发现某一项的绝对值
     小于10-6为止(该项不累加)。
     如果需要计算绝对值,可以使用C语言数学库提供的函数fabs,如求x的绝对值,则为fabs(x).
     输出 PI=圆周率的近似值 输出的结果总宽度占10位,其中小数部分为8位。末尾输出换行。 */
    int main() {
        double pi = 0.0;
        for (double term = 1, i = 1, j = 3; fabs(term) >= 1e-6; j+=2) {    
    		pi += term;
    		i = -i;
            term = i / j;
        }
        printf("PI=%10.8f\n", pi * 4);
        return 0;
    } 
    

    问题 H: 例题5-8 Fibonacci数列

    #include <cstdio>
    /*输入 一个不超过50的正整数
      输出 Fibonacci数列的第n个数,末尾输出换行。*/
    int fibo(int n) {
        if (n == 1 || n == 2) return 1;
        else return fibo(n-1) + fibo(n-2);
    }
    int main() {
        int N;
        scanf("%d", &N);
        printf("%d\n", fibo(N));
        return 0;
    }
    

    问题 I: 习题5-10 分数序列求和

    #include <cstdio>
    /* 有一个分数序列:2/1 , 3/2 , 5/3 , 8/5 , 13/8 , 21/13 ...
    求出这个数列的前20项之和. 输出 小数点后保留6位小数,末尾输出换行。*/
    double top(int n) {
        if (n == 1) return 2;
        else if (n == 2) return 3;
        else return top(n-1) + top(n-2);
    }
    double bottom(int n) {
        if (n == 1) return 1;
        else if (n == 2) return 2;
        else return bottom(n-1) + bottom(n-2);
    }
    int main() {
        double sum = 0.0;
        for (int i = 1; i <= 20; i++) 
            sum += (double)(top(i) / bottom(i));
        printf("%.6f\n", sum);
        return 0;
    }
    

    《算法笔记》2.5小节——C/C++快速入门->数组

    问题 A: 习题6-4 有序插入

    #include <cstdio>
    /* 第一行输入以空格分隔的9个整数数,要求按从小到大的顺序输入。
    第二行输入一个整数, 将此整数插入到前有序的9个数中,使得最终的10个数
    依然是从小到大有序的。
    输出 从小到大输出这10个数,每个数一行。*/
    int main()
    {
        int a[10], temp;
        for (int i = 0; i < 9; i++) 
            scanf("%d", &a[i]);
        scanf("%d", &temp);
        /* 类似插入排序 */
        int i;
        for (i = 9; a[i-1] > temp && i >= 0; i--)
            a[i] = a[i-1];
        a[i] = temp;
        for (int i=0; i < 10; i++) 
            printf("%d\n", a[i]);
        return 0;
    }
    

    问题 B: 习题6-5 数组元素逆置

    #include <cstdio>
    /*  将一个长度为10的整型数组中的值按逆序重新存放。
    输入 从键盘上输入以空格分隔的10个整数。
    输出 按相反的顺序输出这10个数,每个数占一行。*/
    int main()
    {
        int a[10];
        for (int i=0; i<10; i++) {
            scanf("%d", &a[i]);
        }
        for (int i=0; i<5; i++) {
            int temp = a[9-i];
            a[9-i] = a[i];
            a[i] = temp;
        }
        for (int i=0; i<10; i++) {
            printf("%d\n", a[i]);
        }
        return 0;
    }
    

    ★ 问题 C: 习题6-6 杨辉三角

    #include <cstdio>
    #include <cstring>
    /* 
    输入 输入只包含一个正整数n,表示将要输出的杨辉三角的层数。
    输出 对应于该输入,请输出1-相应层数的杨辉三角,每一层的整数之间用一个空格隔开, 最多输出10层 */
    int main()
    {
        int n, a[10] = {1, 1};
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            /* 打印第1、2层 */
            if (i == 1) printf("%d\n", a[0]);
            else if (i == 2) printf("%d %d\n", a[0], a[1]);
            else { /* 打印其他层 */
                int temp[10]; 
                temp[0] = a[0];
                int j; 
                /* 从a的现在一层推导出下一层, 存入临时数组 */
                for (j = 1; j <= i-2; j++) {
                    temp[j] = a[j-1] + a[j];
                }
                temp[j] = 1;
                /* 打印这一层 */
                for (int k=0; k < j; k++) {
                    printf("%d ", temp[k]);
                }
                printf("%d\n", temp[j]);
                /* 更新数组a */
                for (int m=0; m < i; m++) {
        	        a[m] = temp[m];
          		}
        	}
    	} 
    	return 0;	
    }
    

    问题 D: 习题6-12 解密

    #include <cstdio>
    #include <cstring>
    /* 第一个字母变成第26个字母,第i个字母变成第(26-i+1)个字母,非字母字符不变。
       要求根据密码译回原文,并输出。
       输入 输入一行密文; 输出 解密后的原文,单独占一行。*/
    int main()
    {
        char s[100], t[100];
        gets(s);
        for (int i=0; i < strlen(s); i++) {
            if (s[i] >= 65 && s[i] <= 90) {
                s[i] = 155 - s[i];  //'A'65 Z'90'
            } else if (s[i] >= 97 && s[i] <= 122) {
                s[i] = 219 - s[i]; // 'a'97 'z'122
            } 
        }
        puts(s);
        return 0;
    }
    

    问题 E: 习题6-13 字符串比较

    这个题目似乎只是对等长字符串进行比较,如果不等长的话…需要修改一下。

    #include <cstdio>
    #include <cstring>
    /* 比较两个字符串s1和s2的大小,如果s1>s2,则输出一个正数; 
    若s1=s2,则输出0;若s1<s2,则输出一个负数。
    要求:不用strcpy函数;两个字符串用gets函数读入。
    输入 输入2行字符串
    输出 一个整数,表示这两个字符串 比较的差值,单独占一行。*/
    int main()
    {
        char str1[100], str2[100];
        gets(str1);
        gets(str2);
        int res, lt = strlen(str1) < strlen(str2) ? strlen(str1) : strlen(str2);
        for (int i = 0; i < lt; i++) {
            res = str1[i] - str2[i];
            if (res) break;
        }
        printf("%d\n", res);
        return 0;
    }
    

    问题 F: 例题6-1 逆序输出数组元素

    #include <cstdio>
    /* 输入 10个整数,以空格分隔
       输出 将输入的10个整数逆序输出,每个数占一行。 */
    int main()
    {
        int a[10];
        for (int i = 0; i < 10; i++) 
            scanf("%d", a + i);
        for (int i = 9; i >= 1; i--) 
            printf("%d\n", a[i]);
        printf("%d", a[0]);
        return 0;
    }
    

    问题 G: 例题6-2 数组求解Fibonacci数列问题

    这是最好的求解Fibonacci数列的方法。

    #include <cstdio>
    /* 输入 无
       输出 Fibonacci数列的前20个数,每个数占一行。 */
    int main()
    {
        int fib[20] = {1, 1};
        for (int i = 2; i < 20; i++) 
            fib[i] = fib[i-1] + fib[i-2];
        for (int i = 0; i < 20; i++) 
            printf("%d\n", fib[i]);
        return 0;
    }
    

    问题 H: 例题6-3 冒泡排序

    #include <cstdio>
    int main()
    {
        int a[10];
        for (int i = 0; i < 10; i++) 
            scanf("%d", a + i);
        /* 标记+冒泡排序 */
        for (int i = 9; i >= 0; i--) {
            int flag = 1;
            for (int j = 0; j < i; j++) {
                if (a[j] > a[j+1]) {
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                    flag = 0;  
                }
            }
            if (flag) break;
        }
        for (int i = 0; i < 9; i++) 
            printf("%d\n", a[i]);
        printf("%d", a[9]);
        return 0;
    }
    

    问题 I: 例题6-4 矩阵转置

    #include <cstdio>
    /* 输入 2行数据,每行3个整数,以空格分隔。
    输出 行列互换后的矩阵,3行,每行2个数据,以空格分隔。*/
    int main()
    {
        int a[2][3], aT[3][2];
        for (int i = 0; i < 2; i++) 
            for (int j = 0; j < 3; j++)
                scanf("%d", *(a + i) + j);
        /* 转置操作 */
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                aT[j][i] = a[i][j];
            }
        }
        for (int i = 0; i < 2; i++) 
            printf("%d %d\n", aT[i][0], aT[i][1]);
        printf("%d %d", aT[2][0], aT[2][1]);
        return 0;
    }
    

    问题 J: 例题6-9 字符串求最大值

    #include <cstdio>
    #include <cstring>
    /* 输入 输入3行,每行均为一个字符串。
       输出 一行,输入三个字符串中最大者。*/
    int main() 
    {
        char s1[100], s2[100], s3[100], *Max;
        gets(s1);
        gets(s2);
        gets(s3);
        Max = s1;
        if (strcmp(Max, s2) < 0) Max = s2;
        if (strcmp(Max, s3) < 0) Max = s3;
        printf("%s", Max);
        return 0;
    }
    

    《算法笔记》2.6小节——C/C++快速入门->函数

    问题 A: 习题7-5 字符串逆序存放

    我这里使用的是原地修改, 懒得返回值了。

    #include <cstdio>
    #include <cstring>
    /* 输入 一行字符串。
       输出 输入字符串反序存放后的字符串。单独占一行。*/
    void strReverse(char s[]) {
        int len = strlen(s);
        for (int i = 0; i < len / 2; i++) {
            char temp = s[i];
            s[i] = s[len-1-i];
            s[len-1-i] = temp; 
        }
    }
    
    int main()
    {
        char s[100];
        gets(s);
        strReverse(s);
        printf("%s\n", s);
        return 0;
    }
    

    问题 B: 习题7-7 复制字符串中的元音字母

    /* 输入 一个字符串(一行字符)。
       输出 该字符串所有元音字母构成的字符串。行尾换行。*/
    void vowels(char s1[], char s2[]) {
        int len = strlen(s1), j = 0;
        for (int i = 0; i < len; i++) {
            if (s1[i] == 'a' || s1[i] == 'e' || s1[i] == 'i' || s1[i] == 'o' || s1[i] == 'u') {
                s2[j] = s1[i];
                j++;
            }
        }
        s2[j] = '\0';
    }
    int main()
    {
        char s1[100], s2[100];
        gets(s1);
        vowels(s1, s2);
        printf("%s\n", s2);
        return 0;
    }
    

    《算法笔记》2.7小节——C/C++快速入门->指针

    问题 A: C语言10.1

    #include <cstdio>
    /* 输入 两个用空格隔开的整数a和b。
    输出 按先大后小的顺序输出a和b,用空格隔开。请注意行尾输出换行。*/
    int main()
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a > b) printf("%d %d\n", a, b);
        else printf("%d %d\n", b, a);
        return 0;
    }
    

    问题 B: C语言10.2

    #include <cstdio>
    /*输入 三个用空格隔开的整数a、b和c。
      输出 按先大后小的顺序输出a、b和c,用空格隔开。请注意行尾输出换行。*/
    int main()
    {
        int a[3];
        scanf("%d%d%d", &a[0], &a[1], &a[2]);
        for (int i=0; i < 2; i++) {
        	for (int *p=a; p < a + 2; p++) {
    	        if (*p < *(p+1)) {
    	            int temp = *p;
    	            *p = *(p+1);
    	            *(p+1) = temp; 
    	        }
       	    }
    	}
        printf("%d %d %d\n", *a, *(a+1), *(a+2));
        return 0;
    }
    

    问题 C: C语言10.10

    #include <cstdio>
    /* 给定字符串定义char *a = “I love China!”,
    读入整数n,输出在进行了a = a + n这个赋值操作以后字符指针a对应的字符串。
    输入 一个整数n,保证0<=n<13.
    输出 输出进行了题目描述中赋值操作之后a对应的字符串. 请注意行尾输出换行。*/
    int main()
    {
        char *a = "I love China!";
        int n;
        scanf("%d", &n);
        puts(a + n);
        return 0;
    }
    
    

    问题 D: C语言10.15

    #include <cstdio>
    #include <cstring>
    /* 输入3个字符串,按从小到大的顺序输出。要求使用指针的方法进行处理。
    输入 3行,每行一个用字符串。保证每个字符串的长度不超过20。
    输出 按从小到大的顺序输出这3个字符串,每个字符串一行. */
    void swap(char s[], char a[]) {
        char t[30];
        strcpy(t, s);
        strcpy(s, a);
        strcpy(a, t);
    }
    int main()
    {
        char a[30], b[30], c[30];
        gets(a);
        gets(b);
        gets(c);
        if (strcmp(a, b) > 0) 
            swap(a, b);
        if (strcmp(a, c) > 0) 
            swap(a, c);
        if (strcmp(b, c) > 0) 
            swap(b, c);
        puts(a);
        puts(b);
        puts(c);
        return 0;
    }
    

    问题 E: C语言10.16

    #include <cstdio>
    /*输入10个整数,将其中最小的数与第一个数对换,把最大的数与最后一个数对换。要求
    用3个函数实现,分别为输入10个数、进行处理、输出10个数。要求使用指针的方法进行处理。
    输入 用空格隔开的10个整数。
    输出 输出进行题目描述操作之后的10个整数,每个整数之后输出一个空格。*/
    void swap(int *a, int *b) {
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    void Input(int t[], int len) {
        for (int i = 0; i < len; i++)
            scanf("%d", t + i);
    }
    void Deal(int t[], int len) {
        int min , max, minK, maxK;
        min = max = t[0];
        for (int i = 1; i < len; i++) {
            if (t[i] > max) {
                max = t[i];
                maxK = i;
            }
            if (t[i] < min) {
                min = t[i];
                minK = i;
            }
        }
        swap(t, t + minK);
        swap(t + 9, t + maxK);
    }
    void Print(int t[], int len) {
        for (int i = 0; i < len-1; i++) 
            printf("%d ", t[i]);
        printf("%d", t[9]);
    }
    int main()
    {
        int a[11];
        Input(a, 10);
        Deal(a, 10);
        Print(a, 10);
        return 0;
    }
    

    《算法笔记》2.8小节——C/C++快速入门->指针

    问题 A: C语言11.1

    #include <cstdio>
    #include <cstring>
    /* 输入第一行有一个整数n,表示以下有n张选票信息将会输入。保证n不大于100。
    以后的n行中,每一行包含一个人名,为选票的得票人。保证每一个人名都是Li,
    Zhang和Fun中的某一个。
    输出
    有三行,分别为Li,Zhang和Fun每人的得票数。格式为首先输出人名,其后输出一个冒号,
    最后输出候选人的得票数。注意行尾输出换行。*/
    struct person {
        char name[20];
        int count;
    } leader[3] = {"Li", 0, "Zhang", 0, "Fun", 0};
    int main()
    {
        int N;
        scanf("%d", &N);
        for (int i = 0; i <= N; i++) {
            char s[10];
            gets(s);
            if (!strcmp(s, leader[0].name)) leader[0].count++;
            else if (!strcmp(s, leader[1].name)) leader[1].count++;
            else if (!strcmp(s, leader[2].name)) leader[2].count++;
        }
        
        for (int i = 0; i < 3; i++) 
            printf("%s:%d\n", leader[i].name, leader[i].count);
        return 0;
    }
    

    问题 B: C语言11.2

    #include <cstdio>
    #include <cstring>
    /*  输入 第一行有一个整数n,表示以下有n个学生的信息将会输入。保证n不大于20。
    以后的n行中,每一行包含对应学生的学号、名字、性别和年龄,用空格隔开。保证每一个人名
    都不包含空格且长度不超过15,性别用M和F两个字符来表示。
        输出 有n行,每行输出一个学生的学号、名字、性别和年龄,用空格隔开。*/
    struct student {
        int num;
        char name[20];
        char sex;
        int age;
    };
    int main()
    {
        int n;
        scanf("%d", &n);
        int i;
        struct student stus[n], *ptrToStus[n];
        for (i = 0; i < n; i++) {
            scanf("%d %s %c %d", &stus[i].num, stus[i].name, &stus[i].sex, &stus[i].age);
            ptrToStus[i] = &stus[i];
        }
        for (i = 0; i < n; i++) {
            printf("%d %s %c %d\n", ptrToStus[i]->num, ptrToStus[i]->name, ptrToStus[i]->sex, ptrToStus[i]->age);
        }
        return 0;
    }
    

    问题 C: C语言11.4

    好久没有用共用体了,而且就隔了两天,这么简单的东西都会写错,汗颜。

    #include <cstdio>
    struct Job{
        int num;
        char name[10];
        char sex;
        char job;
        union {
            int Class;
            char position[10];
        } category;
    };
    int main()
    {
        int n;
        scanf("%d", &n);
        Job info[n];
        for (int i = 0; i < n; i++) {
            scanf("%d %s %c %c", &info[i].num, info[i].name, &info[i].sex, &info[i].job);
            if (info[i].job == 's') scanf("%d", &info[i].category.Class);
            else if (info[i].job == 't') scanf("%s", info[i].category.position);
        }
        for (int i = 0; i < n; i++) {
            printf("%d %s %c %c ", info[i].num, info[i].name, info[i].sex, info[i].job);
            if (info[i].job == 's') printf("%d\n", info[i].category.Class);
            else if (info[i].job == 't') printf("%s\n", info[i].category.position);
        }
        return 0;
    }
    
    

    问题 D: C语言11.7

    #include <cstdio>
    typedef struct student {
        int num;
        char name[25];
        int score1;
        int score2;
        int score3;
    } student;
    void input(student stds[]) {
        for (int i = 0; i < 5; i++) 
            scanf("%d %s %d %d %d", &stds[i].num, stds[i].name, &stds[i].score1, &stds[i].score2, &stds[i].score3);
    }
    void print(student *stds) {
        for (int i = 0; i < 5; i++) 
            printf("%d %s %d %d %d\n", stds[i].num, stds[i].name, stds[i].score1, stds[i].score2, stds[i].score3);
    }
    
    int main()
    {
        struct student stds[5];
        input(stds);
        print(stds);
        return 0;
    }
    

    问题 E: C语言11.8

    #include <cstdio>
    typedef struct student {
        int num;
        char name[25];
        int score1;
        int score2;
        int score3;
    } student;
    
    void input(student stds[]) {
        for (int i = 0; i < 10; i++) 
            scanf("%d %s %d %d %d", &stds[i].num, stds[i].name, &stds[i].score1, &stds[i].score2, &stds[i].score3);
    }
    void print(student *stds) {
        double sum1 = 0, sum2 = 0, sum3 = 0, max_aver = (stds[0].score1 + stds[0].score2 + stds[0].score3) / 3.0, N = 10.0;
        int k = 0;
        for (int i = 0; i < 10; i++) {
            sum1 += stds[i].score1;
            sum2 += stds[i].score2;
            sum3 += stds[i].score3;
            double now_max = (stds[i].score1 + stds[i].score2 + stds[i].score3) / 3.0;
            if ( now_max > max_aver) {
                k = i;
                max_aver = now_max;
            }
        }
        printf("%.2f %.2f %.2f \n", sum1 / N, sum2 / N, sum3 / N);
        printf("%d %s %d %d %d\n", stds[k].num, stds[k].name, stds[k].score1, stds[k].score2, stds[k].score3);
    }
    
    int main()
    {
        struct student stds[10];
        input(stds);
        print(stds);
        return 0;
    }
    

    ☆《算法笔记》2.10小节——C/C++快速入门->黑盒测试

    多点测试中有如下结构用于反复执行程序的核心部分:

    • while-EOF类型:如while (scanf("%d", &a) != EOF)while (scanf("%s", s) != EOF)while (gets(str) != NULL)等用于输入字符串和数值。如题1。
    • while-EOF-break类型:输入数据满足某个条件时退出,如while (scanf("%d %d", &a, &b) != EOF, a | b)。如题3。
    • while (T--)类型,给出测试数据的组数。如题2。

    1.A+B 输入输出练习I

    #include <cstdio>
    int main()
    {
        int a, b;
        while (scanf("%d %d", &a, &b) == 2) 
        // while (scanf("%d %d", &a, &b) != EOF)
            printf("%d\n", a + b);
        return 0;
    }
    

    2.A+B 输入输出练习II

    /* 输入 第一行是一个整数N,表示后面会有N行a和b,通过空格隔开。
    输出 对于输入的每对a和b,你需要在相应的行输出a、b的和。 */
    #include <cstdio>
    int main()
    {
        int a, b, T;
        scanf("%d", &T);
        while (T--) {
            scanf("%d %d", &a, &b);
            printf("%d\n", a + b);
        }
        return 0;
    }
    

    3.A+B 输入输出练习III

    /* 输入 输入中每行是一对a和b。其中会有一对是0和0标志着输入结束,且这一对不要计算。
    输出 对于输入的每对a和b,你需要在相应的行输出a、b的和。*/
    #include <cstdio>
    int main()
    {
        int a, b;
        while (scanf("%d%d", &a, &b), a || b) 
            printf("%d\n", a + b);
        return 0;
    }
    

    4.A+B 输入输出练习IV

    /*输入 每行的第一个数N,表示本行后面有N个数。
    如果N=0时,表示输入结束,且这一行不要计算。*/
    #include <cstdio>
    int r[100];
    int main()
    {
        int sum = 0, N, a, i = 0;
        scanf("%d", &N);
        while (N) {
            while (N--) {
                scanf("%d", &a);
                sum += a;
            }
            r[i++] = sum;
            scanf("%d", &N);
            sum = 0;
        }
        for (int j = 0; j < i; j++)  printf("%d\n", r[j]);
        return 0;
    }
    

    5.A+B 输入输出练习V

    /* 输入的第一行是一个正数N,表示后面有N行。每一行的第一个数是M,表示本行后面还有M个数。*/
    
    #include <cstdio>
    int r[100];
    int main()
    {
        int N, M, i = 0;
        scanf("%d", &N);
        while (N--) {
            scanf("%d", &M);
            int sum = 0, a;
            while (M--) {
                scanf("%d", &a);
                sum += a;
            }
            r[i++] = sum;
            sum = 0;
        }
        for (int j = 0; j < i; j++) printf("%d\n", r[j]);
        return 0;
    }
    

    6.A+B 输入输出练习VI

    #include <cstdio>
    int r[100];
    int main()
    {
        int sum = 0, N, a, i = 0;
        while (scanf("%d", &N) != EOF) {
            while (N--) {
                scanf("%d", &a);
                sum += a;
            }
            r[i++] = sum;
            sum = 0;
        }
        for (int j = 0; j < i; j++)  printf("%d\n", r[j]);
        return 0;
    }
    

    7.A+B 输入输出练习VII

    #include <cstdio>
    int main()
    {
        int a, b;
        while (scanf("%d%d", &a, &b) != EOF) 
            printf("%d\n\n", a + b);
        return 0;
    }
    

    8.A+B 输入输出练习VIII

    #include <cstdio>
    int r[100];
    int main() {
        int N, M, i = 0;
        scanf("%d", &N);
        while (N--) {
            int sum = 0, a;
            scanf("%d", &M);
            while (M--) {
                scanf("%d", &a);
                sum += a;
            }
            r[i++] = sum;
            sum = 0;
        }
        for (int j = 0; j < i; j++) printf("%d\n\n", r[j]);
        return 0;
    }
    

    《算法笔记》3.1小节——入门模拟->简单模拟

    简单模拟这类题目不涉及算法,完全只是根据题目描述来进行代码的编写

    问题 A: 剩下的树

    #include <cstdio>
    #include <cstring>
    /*有一个长度为整数L(1<=L<=10000)的马路,想象成数轴上长度为L的一个线段,起点是坐标原点,
    在每个整数坐标点有一棵树,即在0,1,2,...,L共L+1个位置上有L+1棵树。
      现在要移走一些树,移走的树的区间用一对数字表示,如 100 200表示移走从100到200之间(包括端点)所有的树。
      可能有M(1<=M<=100)个区间,区间之间可能有重叠。现在要求移走所有区间的树之后剩下的树的个数。
    输入 
      两个整数L(1<=L<=10000)和M(1<=M<=100)。接下来有M组整数,每组有一对数字。输入0 0表示结束。
    输出
      可能有多组输入数据,对于每组输入数据,输出一个数,表示移走所有区间的树之后剩下的树的个数。*/
     
    int main()
    {
        int r[200], j = 0;
        memset(r, 0, sizeof(r));
        int L, M;
        int left, right;
        while (scanf("%d%d", &L, &M), L) {
            int a[L+1];
            memset(a, 0, sizeof(a));
            while (M--) {
                scanf("%d%d", &left, &right);
                for (int i = left; i <= right; i++) {
                    a[i] = 1;
                }
            }
            for (int i = 0; i <= L; i++) 
                if (!a[i]) r[j]++;
            j++;
        }
        for (int i = 0; i < j; i++) {
            printf("%d\n", r[i]);
        }
        return 0;
    }
    

    问题 B: A+B

    /*给定两个整数A和B,其表示形式是:从个位开始,每三位数用逗号","隔开。
    输入 输入包含多组数据数据,每组数据占一行,由两个整数A和B组成(-10^9 < A,B < 10^9)。
    输出 请计算A+B的结果,并以正常形式输出,每组数据占一行。*/
    #include <cstdio>
    #include <cstring>
    long long to_int(char s[]) {
        int len = strlen(s);
        long long r = 0;
        int positive = 1;
        for (int i = 0; i < len; i++) {   //','就直接跳过
            if (s[i] <= '9' && s[i] >= '0') {
                r = r * 10 + (s[i] - '0');
            } else if (s[i] == '-') 
                positive = 0;
        }
        if (!positive) r = -r; 
        return r;
    }
    
    int main()
    {
        char s[50], r[50];
        while (scanf("%s %s", s, r) != EOF) {
            long long snum, rnum;
            snum = to_int(s);
            rnum = to_int(r);
            printf("%lld\n", snum + rnum);
        }
        return 0;
    }
    

    问题 C: 特殊乘法

    /*写个算法,对2个小于1000000000的输入,求结果。特殊乘法举例:123 * 45 = 1*4 +1*5 +2*4 +2*5 +3*4+3*5
    输入 两个小于1000000000的数
    输出 输入可能有多组数据,对于每一组数据,输出两个数按照题目要求的方法进行运算后得到的结果。*/
    #include <cstdio>
    int int_to_array(int n, int num[]) {
        int i = 0;
        while (n) {
            num[i++] = n % 10;
            n /= 10;
        }
        return i;
    }
    int specialMulti(int num1[], int num2[], int len1, int len2) {
        int sum = 0;
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                sum += (num1[i] * num2[j]);
            }
        }
        return sum;
    }
    int main()
    {
        int M, N;
        int numM[15], numN[15], lenM, lenN;
        while (scanf("%d%d", &M, &N) != EOF) {
            lenM = int_to_array(M, numM);
            lenN = int_to_array(N, numN);
            printf("%d\n", specialMulti(numM, numN, lenM, lenN));
        }
        return 0;
    }
    

    问题 D: 比较奇偶数个数

    /* 输入 输入有多组数据。每组输入n,然后输入n个整数(1<=n<=1000)。
    输出 如果偶数比奇数多,输出NO,否则输出YES。*/
    #include <cstdio>
    int main()
    {
        int N, a, odd, even;
        odd = even = 0;
        while (scanf("%d", &N) != EOF) {
            while (N--) {
                scanf("%d", &a);
                if (a % 2) odd++;
                else even++;
            }
            if (even > odd) printf("NO\n");
            else printf("YES\n");
        }
        return 0;
    }
    

    ★ 问题 E: Shortest Distance (20)

    • 题目描述
      The task is really simple: given N exits on a highway which forms a simple cycle,
      you are supposed to tell the shortest distance between any pair of exits.

    • 输入
      Each input file contains one test case. For each case, the first line contains an
      integer N (in [3, 105]), followed by N integer distances D1 D2 … DN, where Di
      is the distance between the i-th and the (i+1)-st exits, and DN is between the
      N-th and the 1st exits. All the numbers in a line are separated by a space.
      The second line gives a positive integer M (<=104), with M lines follow, each
      contains a pair of exit numbers, provided that the exits are numbered from 1 to
      N. It is guaranteed that the total round trip distance is no more than 107.

    • 输出
      For each test case, print your results in M lines, each contains the shortest
      distance between the corresponding given pair of exits.

    • 样例输入

        5 1 2 4 14 9
        3
        1 3
        2 5
        4 1
      
    • 样例输出

        3
        10
        7
      
    #include <cstdio>
    
    int RightDistance(int a[], int left, int right) {
        // [left, right)
        int sum = 0;
        for (int i = left - 1; i < right - 1; i++) // 逻辑序号映射到物理序号
            sum += a[i];
        return sum;
    }
    
    int LeftDistance(int a[], int N, int rightDist) {
        int sum = 0;
        for (int i = 0; i < N; i++)
            sum += a[i];
        return sum - rightDist;  // 环的性质
    }
    
    int main()
    {
        int N, M;
        while (scanf("%d", &N) != EOF) {
            int a[N];
            for (int i = 0; i < N; i++) {
                scanf("%d", &a[i]);
            }
            scanf("%d", &M);
            int left, right;
            while (M--) {
                scanf("%d%d", &left, &right);
                int r1, r2;
                if (left > right) r1 = RightDistance(a, right, left); // 改变方向
                else r1 = RightDistance(a, left, right);
                r2 = LeftDistance(a, N, r1);
                printf("%d\n", r1 < r2 ? r1 : r2);
            }
        }
        return 0;
    }
    

    问题 F: A+B和C (15)

    这题用int会溢出,干脆使用long long。除非这样也不行,就用大整数结构。

    /*题目描述
    给定区间[-2^31, 2^31]内的3个整数A、B和C,请判断A+B是否大于C。
    输入
    输入第1行给出正整数T(<=10),是测试用例的个数。随后给出T组测试用例,每组占一行,
    顺序给出A、B和C。整数间以空格分隔。
    输出
    对每组测试用例,在一行中输出“Case #X: true”如果A+B>C,否则输出“Case #X: false”,其中X是
    测试用例的编号(从1开始)。
    */
    #include <cstdio>
     
    int main()
    {
        int T;
        scanf("%d", &T);
        for (int i = 1; i <= T; i++) {
            long long a, b, c;
            scanf("%lld%lld%lld", &a, &b, &c);
            if (a + b > c) printf("Case #%d: true\n", i);
            else printf("Case #%d: false\n", i);
        }
        return 0;
    }
    

    问题 G: 数字分类 (20)

    给定一系列正整数,请按要求对数字进行分类,并输出以下5个数字:

    • A1 = 能被5整除的数字中所有偶数的和;
    • A2 = 将被5除后余1的数字按给出顺序进行交错求和,即计算n1-n2+n3-n4…;
    • A3 = 被5除后余2的数字的个数;
    • A4 = 被5除后余3的数字的平均数,精确到小数点后1位;
    • A5 = 被5除后余4的数字中最大数字。

    输入
    每个输入包含1个测试用例。每个测试用例先给出一个不超过1000的正整数N,随后给出N个
    不超过1000的待分类的正整数。数字间以空格分隔。
    输出
    对给定的N个正整数,按题目要求计算A1~A5并在一行中顺序输出。数字间以空格分隔,但行末不得有多余空格。若其中某一类数字不存在,则在相应位置输出“N”

    这题本来简单,就是要求输出N的判断麻烦,可能会栽在这里。

    #include <cstdio>
    
    int main()
    {
        int N, a;
        int a1, a2, a3, a5, n;
        double a4;
        int b1, b2, b5;
        while (scanf("%d", &N) != EOF) {	
            a1 = a2 = a3 = a4 = a5 = n = b1 = b2 = b5 = 0;
            int flag = 1;
            for (int i = 0; i < N; i++) {
                scanf("%d", &a);
                
                switch (a % 5) {
                    case 0:
                        if (a % 2 == 0) {
                           a1 += a;
    					   b1++;	
    					}
                        break;
                    case 1:
                        if (flag) {
                            a2 += a;
                            b2++;
                            flag = 0;
                        } else {
                            a2 += -a;
                            b2++;
                            flag = 1;
                        } 
                        break;
                    case 2:
                        a3++;
                        break;
                    case 3:
                        a4 += a;
                        n++;
                        break;
                    case 4:
                        if (a > a5) 
                        	a5 = a;
                       	b5++;
                        break;
                } 
            }
            if (b1) printf("%d ", a1);
            else printf("N ");
            if (b2) printf("%d ", a2);
            else printf("N ");
            if (a3) printf("%d ", a3);
            else printf("N ");
            if (n) printf("%.1f ", (double)a4 / n);
            else printf("N ");
            if (b5) printf("%d\n", a5);
            else printf("N\n");
        }
        return 0;
    }
    

    问题 H: 部分A+B (15)

    正整数A的“DA(为1位整数)部分”定义为由A中所有DA组成的新整数PA。例如:给定A = 3862767,DA = 6,则A的“6部分”PA是66,因为A中有2个6。
    现给定A、DA、B、DB,请编写程序计算PA + PB。

    • 输入
      输入在一行中依次给出A、DA、B、DB,中间以空格分隔,其中0 < A, B < 1010
    • 输出
      在一行中输出PA + PB的值。
    #include <cstdio>
    #include <cstring>
    /* 给出字符如'6'出现n次的数字, n=1时为6 */
    int charToNum(char d, int n) { 
        int numD = d - '0', res = 0;
        for (int i = 0; i < n; i++) {
            res = (res * 10 + numD);
        }
        return res;
    }
    
    int main()
    {
        char a[25], b[25];
        char da, db;
        while (scanf("%s %c %s %c", a, &da, b, &db) != EOF) {
            int len1 = strlen(a), len2 = strlen(b), n1 = 0, n2 = 0;
            for (int i = 0; i < len1; i++)
                if (a[i] == da) n1++;
            for (int i = 0; i < len2; i++)
                if (b[i] == db) n2++;
            printf("%d\n", charToNum(da, n1) + charToNum(db, n2));
        }    
        return 0;
    }
    

    问题 I: 锤子剪刀布 (20)

    大家应该都会玩“锤子剪刀布”的游戏:两人同时给出手势。现给出两人的交锋记录,请统计
    双方的胜、平、负次数,并且给出双方分别出什么手势的胜算最大。

    • 输入
      输入第1行给出正整数N(<=105),即双方交锋的次数。随后N行,每行给出一次交锋的信息
      即甲、乙双方同时给出的的手势。C代表“锤子”、J代表“剪刀”、B代表“布”,第1个字母代表
      甲方,第2个代表乙方,中间有1个空格。
    • 输出
      输出第1、2行分别给出甲、乙的胜、平、负次数,数字间以1个空格分隔。第3行给出两个字母
      ,分别代表甲、乙获胜次数最多的手势,中间有1个空格。如果解不唯一,则输出按字母序最小的解。

    本题我发现对于scanf("%c")的用法容易出错,此时会将空格和换行符一并输入,因此需要用getchar()吸收。

    #include <cstdio>
    #include <cstring>
    char c[] = {'B', 'C', 'J'};
    /* 返回获胜次数最多的手势,如果解不唯一,则返回按字母序最小的手势字符 */
    char checkWinWay(int m[])
    {
    	int k = 0;
    	for (int i = 1; i < 3; i++) 
    		if (m[i] > m[k]) k = i;
    	return c[k];
    }
    int main()
    {
        int N, winJ, winY, par, J[3], Y[3];
        winJ = winY = par = 0;
        memset(J, 0, sizeof(J)); // B C J
        memset(Y, 0, sizeof(Y));
        char a, b;
        scanf("%d", &N);
        getchar();        // 吸收换行 
        
        for (int i = 0; i < N; i++) {
            scanf("%c", &a);
            getchar();    // 吸收空格 
            scanf("%c", &b);
            getchar();    // 吸收换行 
            switch(a) {
                case 'C':
                    switch(b) {
                        case 'C': par++; break;
                        case 'J': winJ++; J[1]++; break;
                        case 'B': winY++; Y[0]++; break;
                    }
                    break;
                case 'J':
                    switch(b) {
                        case 'C': winY++; Y[1]++; break;
                        case 'J': par++; break;
                        case 'B': winJ++; J[2]++; break;
                    }
                    break;
                case 'B':
                    switch(b) {
                        case 'C': winJ++; J[0]++; break;
                        case 'J': winY++; Y[2]++; break;
                        case 'B': par++; break;
                    }
                    break;
            }
        }
        printf("%d %d %d\n%d %d %d\n", winJ, par, N-winJ-par, winY, par, N-winY-par);
        printf("%c %c\n", checkWinWay(J), checkWinWay(Y)); 
        return 0;
    }
    

    《算法笔记》3.2小节——入门模拟->查找元素

    http://codeup.cn/contest.php?cid=100000576

    问题 A: 统计同成绩学生人数

    这一题需要用输入的人数N作为循环判断条件。

    /*读入N名学生的成绩,将获得某一给定分数的学生人数输出。
    输入 每个测试用例的格式为
    第1行:N
    第2行:N名学生的成绩,相邻两数字用一个空格间隔。
    第3行:给定分数
    当读到N=0时输入结束。其中N不超过1000,成绩分数为(包含)0到100之间的一个整数。
    
    输出
    对每个测试用例,将获得给定分数的学生人数输出。
    */
    #include <cstdio>
    int main()
    {
        int N;
        while (scanf("%d", &N), N) {
            int a[N];
            for (int i = 0; i < N; i++)
                scanf("%d", &a[i]);
            int num, cnt = 0;
            scanf("%d", &num);
            for (int i = 0; i < N; i++) 
                if (a[i] == num) cnt++;
            printf("%d\n", cnt);
        }
        return 0;
    }
    

    问题 B: 找x

    /*输入一个数n,然后输入n个数值各不相同,再输入一个值x,输出这个值在这个数组中的下标(从0开始,若不在数组中则输出-1)。
    输入 测试数据有多组,输入n(1<=n<=200),接着输入n个数,然后输入x。
    输出 对于每组输入,请输出结果。
    */
    #include <cstdio>
    int main()
    {
        int N;
        while (scanf("%d", &N) != EOF) {
            int a[N];
            for (int i = 0; i < N; i++) 
                scanf("%d", &a[i]);
            int num, index;
            scanf("%d", &num);
            int flag = 1;
            for (int i = 0; i < N; i++) 
                if (a[i] == num) {
                    flag = 0;
                    printf("%d\n", i);
                    break;
                }
            if (flag) printf("%d\n", -1);
        }
        return 0;
    }
    

    问题 C: 查找学生信息

    CodeUp是多点测试的,竟然忘记了这个情况!同时,在对字符串申请空间时,尽量多申请一点。

    #include <cstdio>
    #include <cstring>
    typedef struct student {
        char index[5];
        char name[100];
        char sex[10];
        int age;
    } student;
    student stu[1010];
    
    int main() 
    {
        int N;
        while (scanf("%d", &N) != EOF) {
        	for (int i = 0; i < N; i++) 
                scanf("%s %s %s %d", stu[i].index, stu[i].name, stu[i].sex, &stu[i].age);
    		int M;
    	    scanf("%d", &M); 
    	    while (M--) {
    	    	char in[10];
    	        scanf("%s", in);
    	        int i;
    	        for (i = 0; i < N; i++) {
    	        	if (strcmp(stu[i].index, in) == 0) {
    	            	printf("%s %s %s %d\n", stu[i].index, stu[i].name, stu[i].sex, stu[i].age);
    	            	break;
    				}  
    			}     
    	        if (i == N) printf("No Answer!\n");
    	    }
    	}
        return 0;
    }
    

    问题 D: 查找

    /*输入数组长度 n 
    输入数组      a[1...n] 
    输入查找个数m 
    输入查找数字b[1...m] 
    输出 YES or NO  查找有则YES 否则NO 。
    输入 输入有多组数据。
    每组输入n,然后输入n个整数,再输入m,然后再输入m个整数(1<=m<=n<=100)。
    输出
    如果在n个数组中输出YES否则输出NO。
    */
    #include <cstdio>
    
    int main()
    {
        int n;
        while (scanf("%d", &n) != EOF) {
            int a[150];
            for (int i = 0; i < n; i++) 
                scanf("%d", &a[i]);
            int m;
            scanf("%d", &m);
            while (m--) {
                int num, i;
                scanf("%d", &num);
                for (i = 0; i < n; i++) 
                    if (a[i] == num) {
                    	printf("YES\n"); 
                    	break;
    				}
                if (i == n) printf("NO\n");
            }
        }
        return 0;
    }
    

    问题 E: 学生查询

    /*
    输入n个学生的信息,每行包括学号、姓名、性别和年龄,每一个属性使用空格分开。
    最后再输入一学号,将该学号对应的学生信息输出。
    输入
    测试数据有多组,第一行为样例数m。对于每个样例,第一行为学生人数n(n不超过20),
    加下来n行每行4个整数分别表示学号、姓名、性别和年龄,最后一行表示查询的学号。
    
    输出
    输出m行,每行表示查询的学生信息,格式参见样例。
    */
    #include <cstdio>
    typedef struct student {
        int index;
        char name[100];
        char sex[10];
        int age;
    } student;
    student stu[50];
    
    int main() 
    {
        int m;
        scanf("%d", &m);
        while (m--) {
            int n;
            scanf("%d", &n);
        	for (int i = 0; i < n; i++)  
                scanf("%d %s %s %d", &stu[i].index, stu[i].name, stu[i].sex, &stu[i].age);
            int in;
    	    scanf("%d", &in);
            int i;
            for (i = 0; i < n; i++) {
            	if (stu[i].index == in) {
                	printf("%d %s %s %d\n", stu[i].index, stu[i].name, stu[i].sex, stu[i].age);
                	break;
    			}  
    		}     
    	}
        return 0;
    }
    

    《算法笔记》3.3小节——入门模拟->图形输出

    问题 A: 输出梯形

    输入一个高度h,输出一个高为h,上底边为h的梯形。

    • 输入 一个整数h(1<=h<=1000)。
    • 输出 h所对应的梯形。

    样例输入

    5
    

    样例输出

            *****
          *******
        *********
      ***********
    *************
    

    这个题目也是多点测试的,别看它题目说是“一个”。

    #include <cstdio>
    int main()
    {
        int h;
        while (scanf("%d", &h) != EOF) {
            int UpEdge = h, DownEdge = 3 * h - 2;
            for (int i = UpEdge; i <= DownEdge; i += 2) {
                int spaceNum = DownEdge - i;
                for (int j = 1; j <= spaceNum; j++)
                    printf(" ");
                for (int k = 1; k <= i; k++)
                    printf("*");
                printf("\n");
            }
        }
        return 0;
    }
    

    ★ 问题 B: Hello World for U

    Given any string of N (>=5) characters, you are asked to form the characters into the shape of U.

    That is, the characters must be printed in the original order, starting top-down from the left vertical
    line with n1 characters, then left to right along the bottom line with n2 characters, and finally bottom-up
    along the vertical line with n3 characters. And more, we would like U to be as squared as possible – that is,
    it must be satisfied that n1 = n3 = max { k| k <= n2 for all 3 <= n2 <= N } with n1 + n2 + n3 - 2 = N.

    • 输入
      Each input file contains one test case. Each case contains one string with no less than 5 and no more than 80 characters in a line. The string contains no white space.
    • 输出
      For each test case, print the input string in the shape of U as specified in the description.
    • 样例输入
      helloworld!
      
    • 样例输出
      h   !
      e   d
      l   l
      lowor
      

    这一题需要解决的问题是将一个字符串写成U字形。拿到这一题的第一映像是U字的写法,先是写第一排第一个字符,然后写第二排第一个字符……然后是最后一排,然后是倒数第二排……但在C语言中如果我们要这
    样写U字形的字符串就需要在数组中操作了。如果是直接输出的话,那只能自上至下一行一行输出。首先是第一行,写出第一个字符和最后一个字符,第二行写出第二个字符和倒数第二个字符……最后是最后一行。需要注意的是除了最后一行输出所有字符,前面每一行只输出两个字符。中间还有空格来隔开每行的两个字符

    思路有了,看看具体的要求。字符串的长度是N,n1,n3代表两边每列字符的数目。n2代表最后一行的字符数。题目中给了一个算式:
    n1 = n3 = max { k| k <= n2 for all 3 <= n2 <= N } with n1 + n2 + n3 - 2 = N.
    仔细研究这个算式,这里的k是不大于n2的,也就是说n1和n3是不大于n2且满足n1+n2+n3=N+2的最大值类似于将字符串长度增加2再对折成三段。那么自然有n1=n3=(N+2)/3,n2=N+2-(n1+n3)
    也就是说设side为两边的字符数(包括最后一行的两端),则side=n1=n3=(N+2)/3。设mid为最后一行除去两端的两个字符后剩下的字符数,mid=N-side*2(总长度减去两边的字符数)。同时mid也是我们输出除最后一行外前面所有行需要空出的空格数

    最后,如何在第i行输出第一个字符和最后一个字符呢?那自然是str[i]和str[len-1-i](len为字符串的长度,也就是N)。具体细节详见代码。

    于是问题完美解决,步骤如下:
    1)计算字符串长度len;
    2)计算两边的字符数side=(len+2)/3;
    3)计算最后一行中间的字符数(前面每行中间的空格数)
    4)输出每行相应的字符。

    #include <cstdio>
    #include <cstring>
    int main()
    {
        char s[100];
        int side, mid, len;
        while (scanf("%s", s) != EOF) {
            len = strlen(s);
            side = (len + 2) / 3;
            mid = len - side * 2;
            for (int i = 0; i < side; i++) {
                if (i < side - 1) { //输出除最后一行的前面所有行
                    printf("%c", s[i]);
                    for (int j = 0; j < mid; j++)
                        printf(" ");
                    printf("%c\n", s[len - 1 - i]);
                } else if (i == side - 1) { //输出最后一行
                    for (int j = 0; j < mid + 2; j++) 
                        printf("%c", s[i++]);
                    printf("\n");
                }
            }
        }
        return 0;
    }
    

    问题 C: 等腰梯形

    请输入高度h,输入一个高为h,上底边长为h 的等腰梯形。

    • 输入 输入第一行表示样例数m,接下来m行每行一个整数h,h不超过10。
    • 输出 对应于m个case输出要求的等腰梯形。
      样例输入
    1
    4
    

    样例输出

       ****
      ******
     ********
    **********
    

    这题与上上题的打印梯形有很大联系,只是变化了一下。

    #include <cstdio>
    int main()
    {
        int m, h;
        scanf("%d", &m);
        while (m--) {
            scanf("%d", &h);
            int UpEdge = h, DownEdge = 3 * h - 2;
            for (int i = UpEdge; i <= DownEdge; i += 2) {
                //打印空格
                int spaceNum = (DownEdge - i) / 2;
                for (int j = 0; j < spaceNum; j++)
                    printf(" ");
                //打印等腰梯形主体
                for (int k = 0; k < i; k++)
                    printf("%c", '*');
                printf("\n");
            }
        }
        return 0;
    }
    

    问题 D: 沙漏图形 tri2str [1*+]

    问题:输入n,输出正倒n层星号三角形。首行顶格,星号间有一空格,效果见样例
    输入样例:

    3
    

    输出样例:

    * * *
     * * 
      *
     * * 
    * * *
    

    数据规模 1<= n <=50

    #include <cstdio>
    
    int main()
    {
        int n;
        while (scanf("%d", &n) != EOF) {
            //打印上半部分 
            int UpEdge = n + n - 1; //第一层的字符数(包括空格和星号)
            for (int i = UpEdge; i >= n; i--) { //i表示每层所拥有的字符数
                int spaceNum = UpEdge - i;
                for (int j = 0; j < spaceNum; j++)
                    printf(" ");
                int charNum = i - n + 1;
                for (int j = 0; j < charNum - 1; j++) 
                    printf("* ");
                printf("*\n");
            }
            //打印下半部分 
            for (int i = n + 1; i <= UpEdge; i++) {
                int spaceNum = UpEdge - i;
                for (int j = 0; j < spaceNum; j++)
                    printf(" ");
                int charNum = i - n + 1;
                for (int j = 0; j < charNum - 1; j++) 
                    printf("* ");
                printf("*\n");
            }
        }
        return 0;
    }
    

    《算法笔记》3.4小节——入门模拟->日期处理

    http://codeup.cn/contest.php?cid=100000578

    ★ 问题 A: 日期差值

    题目描述:有两个日期,求两个日期之间的天数,如果两个日期是连续的我们规定他们之间的天数为两天。

    • 输入:有多组数据,每组数据有两行,分别表示两个日期,形式为YYYYMMDD。
    • 输出:每组数据输出一行,即日期差值。
    #include <cstdio>
    int month[13][2] = { //平年闰年的每个月天数(月/日), 第一行平年, 第二行闰年
        {0, 0}, {31, 31}, {28, 29}, {31, 31}, {30, 30}, {31, 31}, {30, 30}, {31, 31},
        {31, 31}, {30, 30}, {31, 31}, {30, 30}, {31, 31} // {0, 0}没有意义
    };
    bool isLeap(int year) { //判断是否是闰年
        return (year % 400 == 0) || (year % 4 == 0 && year % 100 != 0);
    }
    
    int main()
    {
        int time1, y1, m1, d1;
        int time2, y2, m2, d2;
        while (scanf("%d%d", &time1, &time2) != EOF) { //scanf(%d)会忽视空格和换行 
            if (time1 > time2) { //如果time1晚于time2则交换, 使第一个日期早于第二个日期
                int temp = time1;
                time1 = time2;
                time2 = temp;
            }
            y1 = time1 / 10000, m1 = time1 % 10000 / 100, d1 = time1 % 100;
            y2 = time2 / 10000, m2 = time2 % 10000 / 100, d2 = time2 % 100;
            int ans = 1; //记录日期差值, 因为连续两个日期天数为两天, 所以初值为1
            /* 第一个日期没有达到第二个日期时循环 */
            while (y1 < y2 || m1 < m2 || d1 < d2) {
                d1++;
                if (d1 == month[m1][isLeap(y1)] + 1) { //满当月天数
                    d1 = 1;  //日期变为下个月的1号
                    m1++;    //月份+1
                }
                if (m1 == 13) { //月份满12个月
                    m1 = 1;  //月份变为下一年的1月
                    y1++;    //年+1
                }
                ans++; //累计 
            }
            printf("%d\n", ans);
        }
        return 0;
    }
    

    ★★ 问题 B: Day of Week

    We now use the Gregorian style of dating in Russia. The leap years are years with number divisible
    by 4 but not divisible by 100, or divisible by 400.

    For example, years 2004, 2180 and 2400 are leap. Years 2004, 2181 and 2300 are not leap.
    Your task is to write a program which will compute the day of week corresponding
    to a given date in the nearest past or in the future using today’s agreement about dating.

    • 输入
      There is one single line contains the day number d, month name M and year number y(1000≤y≤3000).
      The month name is the corresponding English name starting from the capital letter.
    • 输出
      Output a single line with the English name of the day of week corresponding to the date,
      starting from the capital letter. All other letters must be in lower case.
    • 样例输入
      21 December 2012
      5 January 2013
      
    • 样例输出
      Friday
      Saturday
      

    这么写只有50%?!不知道问题出在哪里……不过很多日期问题的实质就是在花式数天数

    #include <cstdio>
    #include <cstring>
    struct Date{
    	int y, m, d;
    };
    
    char MonthName[13][12]= {"None", "January", "February", "March", "April", "May", 
       "June", "July", "August", "September", "October", "November", "December"};
    
    char Weekday[8][12] = {"None", "Monday", "Tuesday", "Wednesday", "Thursday",
    "Friday", "Saturday", "Sunday"};
    
    int mapMonth(char s[]) {
        for (int i = 1; i < 13; i++) {
        	if (strcmp(s, MonthName[i]) == 0) 
               return i;
    	}
        return 0;
    }
    int month[13][2] = { //平年闰年的每个月天数(月/日), 第一行平年, 第二行闰年
        {0, 0}, {31, 31}, {28, 29}, {31, 31}, {30, 30}, {31, 31}, {30, 30}, {31, 31},
        {31, 31}, {30, 30}, {31, 31}, {30, 30}, {31, 31} // {0, 0}没有意义
    };
    bool isLeap(int year) { //判断是否是闰年
        return (year % 400 == 0) || (year % 4 == 0 && year % 100 != 0);
    }
    bool MoreEqu(struct Date day1, struct Date day2) { //如果第一个日期晚(大)于第二个日期, 返回true
        if (day1.y != day2.y) return day1.y >= day2.y;
        else if (day1.m != day2.m) return day1.m >= day2.m;
        else return day1.d >= day2.d;
    }
    
    int main() {
        struct Date MyDay, now = {2019, 7, 29};
        char mEnglish[14];
        while (scanf("%d%s%d", &MyDay.d, mEnglish, &MyDay.y) != EOF) {
            MyDay.m = mapMonth(mEnglish);
            int flag = 0;
            struct Date tmp = now;
            if (MoreEqu(MyDay, now)) {
                struct Date t = MyDay;
                MyDay = tmp;
                tmp = t;
                flag = 1;
            }
            int cnt = 0;
            while (MyDay.y < tmp.y || MyDay.m < tmp.m || MyDay.d < tmp.d) {
            	MyDay.d++;
            	cnt++;
            	if (MyDay.d == month[MyDay.m][isLeap(MyDay.y)] + 1) {
            		MyDay.m++;
            		MyDay.d = 1;
    			}
    			if (MyDay.m == 13) {
    				MyDay.y++;
    				MyDay.m = 1;
    			}
    		}
    	 	int offset = cnt % 7; // x
    	 	if (flag) printf("%s\n", Weekday[1 + offset]); // x
    	 	else printf("%s\n", Weekday[1 - offset + 7]); // x
        }
        return 0;
    }
    

    我知道错误了,小于20190729的每隔7天的日期(星期一)无法成功输出。把上面的最后标记的几句改成下面这样就可以了:

    if (!flag) cnt = - cnt;
    int offset = ((cnt % 7) + 7) % 7;
    printf("%s\n", Weekday[1 + offset]);
    

    或者打个补丁:

    int offset = cnt % 7; //22 July 2019
    if (flag) printf("%s\n", Weekday[1 + offset]); 
    else {
    	if (offset) printf("%s\n", Weekday[8 - offset]); 
    	else printf("%s\n", Weekday[1]);
    }
    

    换种数法,计算从公元到输入日期的天数好了,然后与标的日期天数相减。数的时候先数年再数月再数日,加快速度。这样节省了一点代码。

    #include <cstdio>
    #include <cstring>
    struct Date {
    	int y, m, d;
    };
    char MonthName[13][12]= {"None", "January", "February", "March", "April", "May", 
       "June", "July", "August", "September", "October", "November", "December"};
    char Weekday[8][12] = {"None", "Monday", "Tuesday", "Wednesday", "Thursday",
    "Friday", "Saturday", "Sunday"};
    int month[13][2] = { //平年闰年的每个月天数(月/日), 第一行平年, 第二行闰年
        {0, 0}, {31, 31}, {28, 29}, {31, 31}, {30, 30}, {31, 31}, {30, 30}, {31, 31},
        {31, 31}, {30, 30}, {31, 31}, {30, 30}, {31, 31} // {0, 0}没有意义
    };
    
    int mapMonth(char s[]) {
        for (int i = 1; i < 13; i++) {
        	if (strcmp(s, MonthName[i]) == 0) 
               return i;
    	}
        return 0;
    }
    
    bool isLeap(int year) { //判断是否是闰年
        return (year % 400 == 0) || (year % 4 == 0 && year % 100 != 0);
    }
    
    int sumDays(struct Date tmp) {
    	int day = 0;
    	for (int i = 0; i < tmp.y; i++) {
    		day += (isLeap(i) ? 366 : 365);
    	}
        for (int i = 1; i < tmp.m; i++) {
        	day += month[i][isLeap(tmp.y)];
    	}
    	for (int i = 1; i < tmp.d; i++) {
    		day++;
    	}
    	return day; // 737634
    }
    
    int main() {
        struct Date MyDay; // now = {2019, 7, 29}; 距离公元元年737634天 
        char mEnglish[14];
        while (scanf("%d%s%d", &MyDay.d, mEnglish, &MyDay.y) != EOF) {
            MyDay.m = mapMonth(mEnglish);
            int dayCount = sumDays(MyDay) - 737634; //得到日期差值
    	 	int offset = ((dayCount % 7) + 7) % 7;  //对负数和超出的正数修正 
    	 	printf("%s\n", Weekday[1 + offset]); //1-7 20190729星期一
        }
        return 0;
    }
    

    ★ 问题 C: 打印日期

    题目描述:给出年分m和一年中的第n天,算出第n天是几月几号。

    • 输入:输入包括两个整数y(1<=y<=3000),n(1<=n<=366)。
    • 输出:可能有多组测试数据,对于每组数据,按 yyyy-mm-dd的格式将输入中对应的日期打印出来。
    • 样例输入
      2013 60
      2012 300
      2011 350
      2000 211
      
    • 样例输出
      2013-03-01
      2012-10-26
      2011-12-16
      2000-07-29
      

    将天数翻译成对应年的第几天,这个问题跟A.日期差值是基本一样的,只是这题不是比较两个日期的差别,而是用一个累加器,每过一天+1,与输入的一年中第几天比较,不断循环。

    #include <cstdio>
    int month[13][2] = { //平年闰年的每个月天数(月/日), 第一行平年, 第二行闰年
        {0, 0}, {31, 31}, {28, 29}, {31, 31}, {30, 30}, {31, 31}, {30, 30}, {31, 31},
        {31, 31}, {30, 30}, {31, 31}, {30, 30}, {31, 31} // {0, 0}没有意义
    };
    bool isLeap(int year) { //判断是否是闰年
        return (year % 400 == 0) || (year % 4 == 0 && year % 100 != 0);
    }
    
    int main()
    {
        int year, day;
        while (scanf("%d%d", &year, &day) != EOF) {
            int y = year, m = 1, d = 1, cnt = 1; //cnt计数, 表示第几天
    
            while (cnt < day) {
                d++;
                if (d == month[m][isLeap(y)] + 1) {
                    m++;
                    d = 1;
                }
                cnt++; 
            }
            printf("%04d-%02d-%02d\n", y, m, d);
        }
        return 0;
    }
    

    问题 D: 日期类

    题目描述:编写一个日期类,要求按xxxx-xx-xx 的格式输出日期,实现加一天的操作。

    • 输入:输入第一行表示测试用例的个数m,接下来m行每行有3个用空格隔开的整数,分别表示年月日。
      测试数据不会有闰年。
    • 输出:输出m行。按xxxx-xx-xx的格式输出,表示输入日期的后一天的日期。
    • 样例输入
      2
      1999 10 20
      2001 1 31
      
    • 样例输出
      1999-10-21
      2001-02-01
      
    #include <cstdio>
    int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    
    int main()
    {
        int M;
        scanf("%d", &M);
        int y, m, d;
        for (int i = 0; i < M; i++) {
            scanf("%d%d%d", &y, &m, &d);
            d++;
            if (d == month[m] + 1) {
                m++;
                d = 1;
            }
            printf("%04d-%02d-%02d\n", y, m, d);
        }
        return 0;
    }
    

    ★ 问题 E: 日期累加

    题目描述:设计一个程序能计算一个日期加上若干天后是什么日期。

    • 输入:输入第一行表示样例个数m,接下来m行每行四个整数分别表示年月日和累加的天数。
    • 输出:输出m行,每行按yyyy-mm-dd的个数输出。
    • 样例输入
      1
      2008 2 3 100
      
    • 样例输出
      2008-05-13
      

    A.日期差值很多一样的代码,或者说日期类的题目,平年闰年、大月小月的分辨就是基础了。
    这一题是上一题D.日期类的深入,上一题只要求+1天,无闰年,而这一题就不一样了。但是大体上还是一样的思路。

    #include <cstdio>
    int month[13][2] = { //平年闰年的每个月天数(月/日), 第一行平年, 第二行闰年
        {0, 0}, {31, 31}, {28, 29}, {31, 31}, {30, 30}, {31, 31}, {30, 30}, {31, 31},
        {31, 31}, {30, 30}, {31, 31}, {30, 30}, {31, 31} // {0, 0}没有意义
    };
    bool isLeap(int year) { //判断是否是闰年
        return (year % 400 == 0) || (year % 4 == 0 && year % 100 != 0);
    }
    
    int main() {
        int M;
        scanf("%d", &M);
        int y, m, d, days;
        while (M--) {
            scanf("%d %d %d %d", &y, &m, &d, &days);
            int cnt = 0; //表示已增加的天数, 与days比较做循环
            while (cnt < days) {
                d++;
                if (d == month[m][isLeap(y)] + 1) {
                    m++;
                    d = 1;
                }
                if (m == 13) {
                    y++;
                    m = 1;
                }
                cnt++;
            }
            printf("%04d-%02d-%02d\n", y, m, d);
        }
        return 0;
    } 
    

    问题F: 公元时间

    得到某一日期距离公元元年的天数。

    • 法一:
    struct Date {
    	int y, m, d;
    };
    int sumDays(struct Date tmp) {
    	int reDay = 0;
    	struct Date Gen = {0, 1, 1};
        while (Gen.y < tmp.y || Gen.m < tmp.m || Gen.d < tmp.d) {
        	Gen.d++;
        	reDay++;
        	if (Gen.d == month[Gen.m][isLeap(Gen.y)] + 1) {
        		Gen.m++;
        		Gen.d = 1;
    		}
    		if (Gen.m == 13) {
    			Gen.y++;
    			Gen.m = 1;
    		}
    	}
    	return reDay; 
    }
    
    • 法二:
    int sumDays(struct Date tmp) {
    	int day = 0;
    	for (int i = 0; i < tmp.y; i++) { //先数年
    		day += (isLeap(i) ? 366 : 365);
    	}
        for (int i = 1; i < tmp.m; i++) { //再数月
        	day += month[i][isLeap(tmp.y)];
    	}
    	for (int i = 1; i < tmp.d; i++) { //再数日
    		day++;
    	}
    	return day; 
    }
    
    

    《算法笔记》3.5小节——入门模拟->进制转换9

    http://codeup.cn/contest.php?cid=100000579
    进制转换的基础主要是10进制转换为R进制和R进制转换为10进制,掌握这两个代码片就可以了。P进制转换为Q进制是这两个过程的统合,通过十进制作为中转站。

    问题 A: 又一版 A+B

    /* 
    输入两个不超过整型定义的非负10进制整数A和B(<=231-1),输出A+B的m (1 < m <10)进制数。
    输入:测试输入包含若干测试用例。每个测试用例占一行,给出m和A,B的值。当m为0时输入结束。
    输出:每个测试用例的输出占一行,输出A+B的m进制数。
    */
    #include <cstdio>
    
    int main() {
        long long a, b, sum;
        int m, nums[50];
        while (scanf("%d", &m), m) {
            scanf("%lld%lld", &a, &b);
            sum = a + b;
            int i = 0;
            /* 10进制转换为R进制的代码片 */
            do {
                nums[i++] = sum % m;
                sum /= m;
            } while (sum != 0);
            //倒着打印
            for (int j = i - 1; j >= 0; j--) {
                printf("%d", nums[j]);
                if (j == 0) printf("\n");
            }
        }
        return 0;
    }
    

    ★ 问题 B: 数制转换

    题目描述:求任意两个不同进制非负整数的转换(2进制~16进制),所给整数在long所能表达的范围之内。不同进制的表示符号为(0,1,…,9,a,b,…,f)或者(0,1,…,9,A,B,…,F)。

    • 输入
      输入只有一行,包含三个整数a,n,b。a表示其后的n是a进制整数,b表示欲将a进制整数n转
      换成b进制整数。a,b是十进制整数,2 =< a,b <= 16。
    • 输出
      可能有多组测试数据,对于每组数据,输出包含一行,该行有一个整数为转换后的b进制数。
      输出时字母符号全部用大写表示,即(0,1,…,9,A,B,…,F)。
    • 样例输入
      4 123 10
      
    • 样例输出
      27
      

    这一题的关键在于要用字符串存储和表示不同进制的数,因为输入的数为a进制,可能是16进制,会使用a-f或A-F的字符,而且输出的数也可能有字母。可以说,这一题就是比较通用的2-16进制非负整数间的转换程序

    #include <cstdio>
    #include <cstring>
    
    int CharToOct(int a, char n[]) {  //按进制a将n字符串(可表示2-16进制)转换为10进制数
        int sum = 0, product = 1;
        for (int i = strlen(n) - 1; i >= 0; i--) {
            if (n[i] <= '9') sum += (n[i] - '0') * product;
            else if (n[i] <= 'F') sum += (n[i] - 'A' + 10) * product; //大写字母符号
            else if (n[i] <= 'f') sum += (n[i] - 'a' + 10) * product; //小写字母符号
            product *= a;
        }
        return sum;
    }
    
    void OctToChar(int temp, int b, char r[]) { //将10进制数按b进制转换成r字符串
        int i = 0;
        do {
            int k = temp % b;
            if (k <= 9) r[i++] = '0' + k; //十进制符号
            else r[i++] = 'A' + k - 10;   //用大写字母表示大于9的数字
            temp /= b;
        } while (temp != 0);
        r[i] = '\0';  //必须添加结束符, 不然strlen无法正确判别长度 
    }
    
    int main() {
        int a, b; // 2-16
        char n[100];
        while (scanf("%d%s%d", &a, n, &b) != EOF) {
            int temp = CharToOct(a, n);
            if (b == 10) {
            	printf("%d\n", temp);
            	continue;
    		}
    		char r[100];
            OctToChar(temp, b, r);
            
            for (int j = strlen(r) - 1; j >= 0; j--) 
                printf("%c", r[j]);
            printf("\n");
        }
        return 0;
    }
    

    ★★ 问题 C: 进制转换(也算得上是大整数的题目)

    题目描述:将一个长度最多为30位数字的十进制非负整数转换为二进制数输出。

    • 输入: 多组数据,每行为一个长度不超过30位的十进制非负整数。
    • 输出: 每行输出对应的二进制数。
    • 样例输入
      985
      211
      1126
      
    • 样例输出
      1111011001
      11010011
      10001100110
      

    使用字符数组存储的时候,是逆位存储的,即整数低位存储在字符数组的高位,整数高位存储在字符数组的低位。虽然理顺了逻辑也很不错。

    #include <cstdio>
    
    int main() {
        char s[32]; //将十进制字符串转换为倒排的二进制字符串, 需模拟多次数字取余和除法
        while (gets(s)) {
            char nums[100] = {};
            int numsSize = 0, sum = 1; //全十进制字符串
            while (sum) { //当十进制字符还未除完时继续循环
                sum = 0; //每一次十进制字符串除以2都恢复0
                for (int i = 0; s[i]; i++) {
                    int digit = s[i] - '0';
                    int x = digit / 2; 
                    sum += x;
                    if (s[i + 1]) {
                        s[i + 1] += (digit % 2 * 10);
                    } else {
                        nums[numsSize++] = digit % 2 + '0'; //从低位向高位存入取余的字符
                    }
                    s[i] = x + '0'; //一位字符的变化
                }
            }
            for (int k = numsSize - 1; k >= 0; k--) {
                printf("%c", nums[k]);
            }
            printf("\n");
        }
        return 0;
    }
    

    问题 D: 八进制

    #include <cstdio>
    
    int main() {
        int N, nums[50];
        while (scanf("%d", &N) != EOF) {
            int i = 0;
            do {
                nums[i++] = N % 8;
                N /= 8;
            } while (N != 0);
            for (int j = i - 1; j >= 0; j--) 
                printf("%d", nums[j]);
            printf("\n");
        }
        return 0;
    }
    

    《算法笔记》3.6小节——入门模拟->字符串处理

    问题 A: 字符串连接

    #include <cstdio>
    
    int main() {
        char s1[200], s2[100], r[210];
        while (scanf("%s%s", s1, s2) != EOF) {
            int i;
            for (i = 0; s1[i]; i++) {
                r[i] = s1[i];
            }
            for (int j = 0; s2[j]; j++) {
                r[i++] = s2[j];
            }
            r[i] = '\0';
            puts(r);
        }
        return 0;
    }
    

    问题 B: 首字母大写

    • 题目描述:对一个字符串中的所有单词,如果单词的首字母不是大写字母,则把单词的首字母变成大写字母。在字符串中,单词之间通过空白符分隔,空白符包括:空格(’ ‘)、制表符(’\t’)、回车符(’\r’)、换行符(’\n’)
    • 输入:一行待处理的字符串(长度小于100)。
    • 输出:可能有多组测试数据,对于每组数据,输出一行转换后的字符串。
    • 样例输入
      if so, you already have a google account. you can sign in on the right.
      
    • 样例输出
      If So, You Already Have A Google Account. You Can Sign In On The Right.
      

    这个题其实很简单,PAT B1009说反话与之类似,都可以用两种方法实现,一者是直接对字符串进行整体处理,是一种简单的办法,但是可能会写错。像这题就是将第一个字母和每个空格符后面的字母变成大写,我的思路是这样,但是写的时候搞错判断了(主要是if条件太长),要对这些字母本身是否已经是大写进行判断,不然就会出错。

    #include <cstdio>
    
    int main() {
        char s[120];
        while (gets(s) != NULL) {
            for (int i = 0; s[i]; i++) {
                if (
    			   ((!i) || (s[i-1] == ' ' || s[i-1] == '\t' || s[i-1] == '\r' || s[i-1] == '\n'))
    			    && s[i] >= 'a' && s[i] <= 'z'
    	        ) 
                    s[i] -= ('a' - 'A'); // s[i] - 32
            }
            puts(s);
        }
        return 0;
    }
    

    第二种方法就是分割字符串成为一个个单词,这时省去对第一个字母进行特判,然后判断每个单词的首字母本身是否已经是大写,不是则变为大写,最后输出。这样麻烦一点。
    而且CodeUp的判题机也有问题,有时候加个大括号就可以正确了……

    #include <cstdio>
    
    int main() {
        char s[120];
        while (gets(s) != NULL) {
        	char words[100][100] = {};
            int r = 0, c = 0;
            //分割字符串成多个单词
            for (int i = 0; s[i]; i++) {
                if (s[i] != ' ' && s[i] != '\t' && s[i] != '\r' && s[i] != '\n') 
                    words[r][c++] = s[i];
                else {
                    words[r++][c] = '\0';
                    c = 0;
                }
            }
            //单词首字母大写
            for (int j = 0; j <= r; j++) 
                if (words[j][0] >= 'a') 
                	words[j][0] -= 32;
            //输出单词
            for (int j = 0; j <= r; j++) {
       	        printf ("%s", words[j]);  
       	    	if (j < r)   printf (" ");  
       	    	else 		 printf ("\n");
     	  	}  
        }
        return 0;
    }
    

    ★★ 问题 C: 字符串的查找删除

    题目描述:给定一个短字符串(不含空格),再给定若干字符串,在这些字符串中删除所含有的短字符串。

    • 输入:输入只有1组数据。输入一个短字符串(不含空格),再输入若干字符串直到文件结束为止。
    • 输出:删除输入的短字符串(不区分大小写)并去掉空格,输出。
    • 样例输入
      in
      #include 
      int main()
      {
      
      printf(" Hi ");
      }
      
    • 样例输出
      #clude
      tma()
      {
      
      prtf("Hi");
      }
      
    • 提示:注:将字符串中的In、IN、iN、in删除。

    这个题目还有点难度,必须一口气输入所有字符串进行处理。我的代码如下:
    判断逻辑:遍历字符串,某字符与短字符第一个字符相同;再判断下一位字符是否相同,直至完全相同,完全相同则跳过。

    #include <cstdio>
    char del[1000], temp[1001][1001], ans[1001][1001];
    
    int main() {
        int index = 0;
        gets(del);
        for (; gets(temp[index]) != NULL; index++);  //读入数据
        /* 将要删除的字符转为小写 */
        for (int i = 0; del[i]; i++) {
            if (del[i] >= 'A' && del[i] <= 'Z') {
                del[i] += 32; 
            }
        }
        for (int i = 0; i < index; i++) {
            int k;
            /* 用另一二维数组存储原数据,然后将原数据转化为小写字母 */
            for (k = 0; temp[i][k]; k++) {
                ans[i][k] = temp[i][k];
                if (temp[i][k] >= 'A' && temp[i][k] <= 'Z') {
                    temp[i][k] += 32;
                }
            }
            ans[i][k] = '\0'; //结束一句的复制
            /* 进行短字符判断,如果不是短字符或空格就输出 */
            for (int j = 0, len = 0; temp[i][j]; j++, len = 0) { //用len加以试探 
                while (temp[i][j + len] == del[len]) { //判断是否与短字符第一个字符相同, 相同则继续循环
                    len++;
                    if (!del[len]) { //这一段与短字符完全相同
                        j += len;    //指向i行j列的指针跳过这一段
                        len = 0;     //接着循环比较, 不同则进入下面的if语句打印字符
                    }
                }
                if (temp[i][j] != ' ')  printf("%c", ans[i][j]);
            }
            printf("\n");  //输出一句后的换行
        }
        return 0;
    }
    

    这一段的逻辑也可以这么写,两者等价:

     for (int j = 0, len = 0; temp[i][j]; ) {		
    		if (temp[i][j + len] == del[len]) {			
    			len++;								
    			if (!del[len])  {	//若完全相同则跳过 
    				j += len;       //接着就可以开始下一个字符的判断
    				len = 0;
    			}
    		} else {  // 不同则进入下面的if语句打印字符
    			if (temp[i][j] != ' ') printf ("%c", ans[i][j]); //输出原字符 
    			j++;  //打印一个字符后j+1
    			len = 0;
    		}
    }
    printf ("\n");
    

    问题 D: 单词置换

    本题要求将s中所有单词a替换成b之后的字符串,如果真正替换很麻烦,所以这里先将字符串分割成单词组,然后对要替换的单词a,输出替换后的单词b。

    #include <cstdio>
    #include <cstring>
    int main() {
        char s[120];
        while (gets(s)) {
            char source[110] = {}, dest[110] = {}, words[110][50] = {};
            gets(source);
            gets(dest);
            int r = 0, c = 0; 
            for (int i = 0; s[i]; i++) {
                if (s[i] != ' ') {
                    words[r][c++] = s[i];
                } else {
                    words[r++][c] = '\0';
                    c = 0;
                }
            }
            for (int j = 0; j <= r; j++) {
                if (strcmp(words[j], source) == 0) {
                    printf("%s", dest);
                } else {
                    printf("%s", words[j]);
                }
                if (j < r) printf(" ");
                else printf("\n");
            }
        }
        return 0;
    }
    

    问题 E: 字符串去特定字符

    这道题总是卡在50%上面。而且用scanf("%s\n%c", s, &c) != EOF在我的电脑上可以正确运行,在网上就不可以了。所以有时还是用gets和getchar()。
    这里,我发现有时候不一定要使用strlen函数,直接用结束符判断就很好,这也是结束符的本意

    #include <cstdio>
    
    int main() {
        char s[1000], c; 
        
        while (gets(s) != NULL) {
            c = getchar();
            for (int i = 0; s[i]; i++) 
                if (s[i] != c) printf("%c", s[i]);
            printf("\n");
            getchar();
        }
        return 0;
    }
    

    问题 F: 数组逆置

    #include <cstdio>
    #include <cstring>
    
    int main() {
        char s[210];
        while (gets(s) != NULL) { //可能有空格
            for (int i = strlen(s) - 1; i >= 0; i--) 
                printf("%c", s[i]);
            printf("\n");
        }
        return 0;
    }
    

    问题 G: 比较字符串

    这里我没有直接用字符串函数strlen,不过我觉得strlen可能就是这么写的。

    #include <cstdio>
    
    int main() {
        char s[100], r[100];
        int m;
        scanf("%d", &m);
        while (m--) {
            scanf("%s%s", s, r);
            int slen = 0, rlen = 0;
            for (slen = 0; s[slen]; slen++);
            for (rlen = 0; r[rlen]; rlen++);
            if (slen == rlen) {
                printf("%s is equal long to %s\n", s, r);
            } else if (slen > rlen) {
                printf("%s is longer than %s\n", s, r);
            } else {
                printf("%s is shorter than %s\n", s, r);
            }
        }
    }
    

    ★ 问题 H: 编排字符串

    题目描述:请输入字符串,最多输入4 个字符串,要求后输入的字符串排在前面,例如:

    输入:EricZ
    输出:1=EricZ
    输入:David
    输出:1=David 2=EricZ
    输入:Peter
    输出:1=Peter 2=David 3=EricZ
    输入:Alan
    输出:1=Alan 2=Peter 3=David 4=EricZ
    输入:Jane
    输出:1=Jane 2=Alan 3=Peter 4=David
    
    • 输入:第一行为字符串个数m,接下来m行每行一个字符床,m不超过100,每个字符床长度不超过20。
    • 输出:输出m行,每行按照样例格式输出,注意用一个空格隔开。
    • 样例输入
      5
      EricZ
      David
      Peter
      Alan
      Jane
      
    • 样例输出
      1=EricZ
      1=David 2=EricZ
      1=Peter 2=David 3=EricZ
      1=Alan 2=Peter 3=David 4=EricZ
      1=Jane 2=Alan 3=Peter 4=David
      

    这题麻烦在于没怎么做过这种类型,相当于实现了一个有大小限制的字符串容器,新进入的字符串会把旧的字符串挤下来,甚至挤出去。

    #include <cstdio>
    #include <cstring> 
    int main() {
        int m;
        scanf("%d", &m);
        char s[5][35]; //使用1-4行 
        for (int i = 1; i <= m; i++) {
            int j, w = i >= 1 && i <= 4 ? i : 4; //获得字符串数目
            for (j = w; j > 1; j--) { //将旧的字符串移到下一个位置
                strcpy(s[j], s[j - 1]);
      		}
            scanf("%s", s[1]);  //永远在第一个位置存入新字符串
            for (int k = 1; k <= w; k++) { //按格式打印全部已存入的字符串
                if (k < w) printf("%d=%s ", k, s[k]); 
    			else  printf("%d=%s\n", k, s[k]);
            }
        }
       return 0;
    }
    

    问题 I: 【字符串】回文串

    一行字符串,长度不超过255。个人觉得,我这种判断回文串的方法最简单最好写。

    #include <cstdio>
    #include <cstring>
    
    int main() {
        char s[260];
        while (gets(s) != NULL) {
            int left = 0, right = strlen(s) - 1, flag = 1;
            for (int i = left, j = right; i < j; i++, j--) { //双指针滑动
                if (s[i] != s[j]) {
                    printf("NO\n");
                    flag = 0;
                    break;
                }
            }
            if (flag) printf("YES\n");
        }
        return 0;
    }
    

    《算法笔记》4.1小节——算法初步->排序

    问题 A: 排序

    对输入的n个数进行从小到大的排序并输出。
    先自己实现一个插入排序的程序。

    #include <cstdio>
    
    int main() {
        int n, a[120];
        while (scanf("%d", &n) != EOF) {
            for (int i = 0; i < n; i++) {
                scanf("%d", &a[i]);
            }
            //插入排序
            for (int i = 1; i < n; i++) {
                int temp = a[i], j;
                for (j = i; j > 0 && temp < a[j - 1]; j--) 
                    a[j] = a[j - 1];
                a[j] = temp;
            }
            //输出
            for (int i = 0; i < n; i++) {
                printf("%d", a[i]);
                if (i < n - 1) printf(" ");
                else printf("\n");
            }
        }
    }
    

    再使用C++的库函数sort()直接排序。其使用格式sort(要排序的数组, 数组元素末项的下一项, 排序函数)

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    
    int main() {
        int n, a[120];
        while (scanf("%d", &n) != EOF) {
            for (int i = 0; i < n; i++) {
                scanf("%d", &a[i]);
            }
            //排序
            sort(a, a + n);
            //输出
            for (int i = 0; i < n; i++) {
                printf("%d", a[i]);
                if (i < n - 1) printf(" ");
                else printf("\n");
            }
        }
    }
    

    问题 B: 特殊排序

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    
    int main() {
        int n, a[1010];
        while (scanf("%d", &n) != EOF) {
            for (int i = 0; i < n; i++) {
            	scanf("%d", &a[i]);
    		} 
            if (n == 1) { //只有1个元素
                printf("%d\n", a[0]);
                printf("-1\n");
                continue;
            }
            sort(a, a + n);
            printf("%d\n", a[n - 1]);
            for (int i = 0; i < n - 1; i++) {
                printf("%d", a[i]);
                if (i < n - 2) printf(" ");
                else printf("\n");
            }
        }
        return 0;
    }
    

    问题 C: EXCEL排序

    题目描述
    Excel可以对一组纪录按任意指定列排序。现请你编写程序实现类似功能。
    对每个测试用例,首先输出1行“Case i:”,其中 i 是测试用例的编号(从1开始)。随后在 N 行中输出按要求排序后的结果,即:当 C=1 时,按学号递增排序;当 C=2时,按姓名的非递减字典序排序;当 C=3 时,按成绩的非递减排序。当若干学生具有相同姓名或者相同成绩时,则按他们的学号递增排序

    • 输入
      测试输入包含若干测试用例。每个测试用例的第1行包含两个整数 N (N<=100000) 和 C,
      其中 N 是纪录的条数,C 是指定排序的列号。以下有N行,每行包含一条学生纪录。每条学
      生纪录由学号(6位数字,同组测试中没有重复的学号)、姓名(不超过8位且不包含空格
      的字符串)、成绩(闭区间[0, 100]内的整数)组成,每个项目间用1个空格隔开。当读到 N=0 时,全部输入结束,相应的结果不要输出
    • 输出
      对每个测试用例,首先输出1行“Case i:”,其中 i 是测试用例的编号(从1开始)。随后在
      N 行中输出按要求排序后的结果,即:当 C=1 时,按学号递增排序;当 C=2时,按姓名
      的非递减字典序排序;当 C=3 时,按成绩的非递减排序。当若干学生具有相同姓名或者相同成绩时,则按他们的学号递增排序
    • 样例输入
      4 1
      000001 Zhao 75
      000004 Qian 88
      000003 Li 64
      000002 Sun 90
      4 2
      000005 Zhao 95
      000011 Zhao 75
      000007 Qian 68
      000006 Sun 85
      4 3
      000002 Qian 88
      000015 Li 95
      000012 Zhao 70
      000009 Sun 95
      0 3
      
    • 样例输出
      Case 1:
      000001 Zhao 75
      000002 Sun 90
      000003 Li 64
      000004 Qian 88
      Case 2:
      000007 Qian 68
      000006 Sun 85
      000005 Zhao 95
      000011 Zhao 75
      Case 3:
      000012 Zhao 70
      000002 Qian 88
      000009 Sun 95
      000015 Li 95
      

    这道问题的题目描述中,2和3的排序都要二级排序。

    #include <cstdio>
    #include <cstring> 
    #include <algorithm>
    using namespace std;
    struct student {
    	int id; // 6
    	char name[10];
    	int score;
    } excelBook[100050];
    
    bool cmp1(struct student a, struct student b) {
    	return a.id < b.id;  //按学号递增排序
    }
    
    bool cmp2(struct student a, struct student b) { //按姓名的非递减字典序排序
    	if (strcmp(a.name, b.name)) return strcmp(a.name, b.name) < 0;  
    	else return a.id < b.id;
    }
    
    bool cmp3(struct student a, struct student b) {
    	if (a.score != b.score) return a.score < b.score;  //按成绩的递增排序
    	else return a.id < b.id; 
    }
    
    int main() {
    	int N, C, caseCount = 0;
    	while (scanf("%d%d", &N, &C), N) {
    		for (int i = 0; i < N; i++) {
    			scanf("%d%s%d", &excelBook[i].id, excelBook[i].name, &excelBook[i].score);
    		}
    		switch (C) {
    			case 1:  //当 C=1 时,按学号递增排序
    		        sort(excelBook, excelBook + N, cmp1); break;
    			case 2:  //当 C=2时,按姓名的非递减字典序排序
    				sort(excelBook, excelBook + N, cmp2); break; 
    			case 3:  //当 C=3 时,按成绩的非递减排序, 当若干学生具有相同姓名或者相同成绩时,
    			//则按他们的学号递增排序
    				sort(excelBook, excelBook + N, cmp3); break;
    		}
    		//打印输出 
    		printf("Case %d:\n", ++caseCount);
    		for (int i = 0; i < N; i++) {
    			printf("%06d %s %d\n", excelBook[i].id, excelBook[i].name, excelBook[i].score);
    		}
    	}
    	return 0;
    }
    

    问题 D: 字符串内排序

    注意输入的字符串中可能有空格。因此要使用gets输入字符串,而且按字符从小到大排序,空格排在最前。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    int main() {
        char s[210];
        while (gets(s)) {
            int len = strlen(s);
            sort(s, s + len);
            puts(s);
        }
        return 0;
    }
    

    问题 E: Problem B

    求矩阵每一行、每一列、主次对角线和,并排序。即使只有一个元素,也要输出4个和

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    bool cmp(int a, int b) {
        return a > b;
    }
    int matrix[12][12];
    int r[30];
    
    int main() {
        int m;
        while (scanf("%d", &m) != EOF) {
            int len = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < m; j++) {
                    scanf("%d", &matrix[i][j]);
                }
            }
            //每一行与列求和
            for (int i = 0; i < m; i++) {
                int Rsum = 0, Csum = 0;
                for (int j = 0; j < m; j++) {
                    Rsum += matrix[i][j];
                    Csum += matrix[j][i];
                }
                r[len++] = Rsum;
                r[len++] = Csum;
            }
            //主次对角线求和
            int LDsum = 0, RDsum = 0;
            for (int i = 0; i < m; i++) {
                LDsum += matrix[i][i];
                RDsum += matrix[i][m - i - 1];
            }
            r[len++] = LDsum;
            r[len++] = RDsum;
            sort(r, r + len, cmp);
            for (int i = 0; i < len - 1; i++) {
                printf("%d ", r[i]);   
            }
            printf("%d\n", r[len - 1]);
        }
        return 0;
    }
    

    问题 F: 小白鼠排队

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    struct rat {
        int weight;
        char color[15];
    } mice[120];
    bool cmp(struct rat a, struct rat b) {
    	return a.weight > b.weight; //按重量从大到小, 重量各不相同	
    }
    
    int main() {
        int N;
        while (scanf("%d", &N) != EOF) {
            for (int i = 0; i < N; i++) {
                scanf("%d%s", &mice[i].weight, mice[i].color);
            }
            sort(mice, mice + N, cmp); 
            for (int i = 0; i < N; i++) {
            	puts(mice[i].color);  //输出小白鼠的颜色
    		}
        }
    }
    

    问题 G: 中位数

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    int a[10010];
    int main() {
    	int N;
    	while (scanf("%d", &N), N) {
    		for (int i = 0; i < N; i++) {
    			scanf("%d", &a[i]);
    		}
    		sort(a, a + N);
    		int mid = (0 + N - 1) / 2;
    		if (N % 2) {
    			printf("%d\n", a[mid]);
    		} else {
    			//求最中间两个数的平均数,向下取整即可
    			printf("%d\n", (a[mid] + a[mid + 1]) / 2);
    		}
    	}
    	return 0;
    }
    

    问题 H: 整数奇偶排序

    #include <iostream>
    #include <algorithm>
    using namespace std;
    bool cmp(int a, int b) {
    	return a > b;
    }
    int main() {
    	int a[10], odd[10], even[10];
    	while(cin>>a[0]>>a[1]>>a[2]>>a[3]>>a[4]
    	      >>a[5]>>a[6]>>a[7]>>a[8]>>a[9]) {
          	int len1 = 0, len2 = 0;
    	    for (int i = 0; i < 10; i++) {
    	    	a[i] % 2 ? odd[len1++] = a[i] : even[len2++] = a[i];
    		}
    		sort(odd, odd + len1, cmp);
    		sort(even, even + len2);
    		//输出其中的奇数,并按从大到小排列; 输出其中的偶数,并按从小到大排列
    		for (int i = 0; i < len1; i++) a[i] = odd[i];
    		for (int j = len1; j < 10; j++) a[j] = even[j - len1];
    		for (int k = 0; k < 10; k++) {
    			cout << a[k];
    			if (k < 9) cout << " ";
    			else cout << endl;
    		}
        }
        return 0;
    }
    

    问题 I: 排名

    这题比较简单,计算好合格的分数后按题目要求排序即可。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    struct student {
    	char id[25];
    	int m, TotalScores;
    } stu[1050];
    using namespace std;
    bool cmp(struct student a, struct student b) {
    	if (a.TotalScores != b.TotalScores) return a.TotalScores > b.TotalScores;
    	else return strcmp(a.id, b.id) < 0;
    }
    int main() {
    	int N, M, G;
    	while (scanf("%d", &N), N) {
    		scanf("%d%d", &M, &G);  //记录考题数M、分数线G
    		int exerScores[M + 1], cases = 0; //通过人数 
    		for (int i = 1; i <= M; i++) 
    			scanf("%d", &exerScores[i]);  //记录每道题的分数
    		for (int i = 0; i < N; i++) {
    			scanf("%s%d", stu[i].id, &stu[i].m); //记录考号和做出题数 
    			int sum = 0, t;
    			for (int j = 0; j < stu[i].m; j++) {  
    				scanf("%d", &t);
    				sum += exerScores[t];  //求出考生总分 
    			}
    			if (sum >= G) {
    			   cases++;     //超出分数线 
    			   stu[i].TotalScores = sum;  //记录合格的分数 
                }
    		}
    		sort(stu, stu + cases, cmp);
    		printf("%d\n", cases);
    		for (int i = 0; i < cases; i++) {
    			printf("%s %d\n", stu[i].id, stu[i].TotalScores);
    		}
    	}
    	return 0;
    }
    

    《算法笔记》4.2小节——算法初步->哈希

    http://codeup.cn/contest.php?cid=100000582
    在哈希这一块常用的问题包括:判断<=105个正整数中某m个正整数是否出现过、出现了多少次——声明bool/int hashTable[maxn] = {false}/{0}。其做法本质是直接将输入的整数作为数组的下标来对这个数的性质进行统计,即hash(key)=key直接定址,是最常见也最实用的散列应用。复杂一点还有二次映射。把这两个思想掌握了就差不多了。

    问题 A: 谁是你的潜在朋友

    本题中也是使用了这种做法,直接将输入的数作为数组的下标。分别有两个数组,记录记录1-N每个人喜欢看的书号的数组person,记录1-M每本书的喜欢人数的数组note。如果要通过某个人的编号查询到有多少人和这个人喜欢同一本书的写法是:note[person[i]]。实质是在人与书号间形成了一种单射。接下来就简单了。

    #include <cstdio>
    
    int main() {
    	int N, M;
    	while (scanf("%d%d", &N, &M) != EOF) {
    		int person[N + 1], note[M + 1] = {0}, tmp;
    		for (int i = 1; i <= N; i++) {
    			scanf("%d", &tmp);
    			person[i] = tmp; //记录1-N每个人喜欢看的书号 
    			note[tmp]++; //记录每本书的喜欢人数 
    		}		
    		for (int i = 1; i <= N; i++) {
    			if (note[person[i]] > 1) printf("%d\n", note[person[i]] - 1);
    			else printf("BeiJu\n");
    		} 
    	}
    	return 0;
    }
    

    ★★★ 问题 B: 分组统计

    题目描述:先输入一组数,然后输入其分组,按照分组统计出现次数并输出,参见样例。

    • 输入:输入第一行表示样例数m,对于每个样例,第一行为数的个数n,接下来两行分别有n个数,第一行有n个数,第二行的n个数分别对应上一行每个数的分组,n不超过100
    • 输出:输出m行,格式参见样例,按从小到大排
    • 样例输入
      1
      7
      3 2 3 8 8 2 3
      1 2 3 2 1 3 1
      
    • 样例输出
      1={2=0,3=2,8=1}
      2={2=1,3=0,8=1}
      3={2=1,3=1,8=0
      

    解析:这一道题目可以说是集整数哈希思想于大成,值得仔细分析。

    • 首先,题目中说输入的数据量不超过100,类别同样不超过100,但是没有说数据的具体范围,可能会在整数作为数组的下标超过数组下标范围,理论上来说,对于这种题目,以空间换时间,要求数据应该不超过106。因此,统计输入的数据和组别是否已经出现,可以开hashTable[100100]这样大。
    • 去重操作。在有了标识数据是否出现的哈希表的情况下,可以很简单的做到。
    • 答案矩阵是一个二次映射的二维数组,可以直接通过组别和数据查到相应组别的数据出现的次数。
    • 出现50%错误:如果二维数组开的太小,很容易溢出,所以记录第一行数据中最大的值,将其+10作为二维数组中的列数即可解决。

    思路:

    1. 输入第一行数据,存入data[]中,同时使用hashTable1[]去重,将去重后的数存入nums[]中,并排序。
    2. 输入第二行组别,存入group[]中,同时使用hashTable2[]函数去重,将去重后的数存入g[]中,并排序。
    3. 同时,将group[]和data[]对应映射到ans[][]中,ans[i][j]中i为分组,j为数。a[i][j]为第i组的j数出现的次数
    4. 遍历输出。
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    
    int main() {
    	int m;
    	scanf("%d", &m);
    	while (m--) {
    		int n, maxCol = 0, data[110], group[110]; //分别记录输入的数据和分组
    		scanf("%d", &n);
    		
    		//nums记录输入的数据去重后的数据  
    		int nums[120], len1 = 0;
    		//使用哈希表对data进行存在标识, 以便去重 
    		bool hashTable1[100100] = {false}; 
    		for (int i = 0; i < n; i++) { 
    			scanf("%d", &data[i]);      //边录入边去重 
    			if (!hashTable1[data[i]]) { //如果这个数据尚未被记录 
    	    		nums[len1++] = data[i]; 
    	            hashTable1[data[i]] = true; 
    			}
    			//得到最大的数, 方便答案直接映射而不溢出 
    			if (maxCol < data[i]) maxCol = data[i];  
    		} 
    		sort(nums, nums + len1); //数据从小到大存放在nums中, 无重复  
    		
    		//g记录输入的组别去重后的数据  
    		int g[120], len2 = 0; 
    		//使用哈希表对group进行存在标识, 以便去重
    		bool hashTable2[100100] = {false};
    		/*二维答案表,元素ans[g[i]][nums[j]]表示g[i]组中对应的nums[j]出现的次数 
    		ans[i][j], i为分组, j为数, a[i][j]为第i组的j数出现的次数 */
    		int ans[n + 10][maxCol + 10] = {0};  
    		for (int i = 0; i < n; i++) {
    			scanf("%d", &group[i]);
    			ans[group[i]][data[i]]++; 
    			if (!hashTable2[group[i]]) { //如果这个组别尚未被记录 
    			   g[len2++] = group[i];  
    			   hashTable2[group[i]] = true;
                } 
    		}
    		sort(g, g + len2); //组别从小到大存放在g中, 无重复 
    	
    		//输出结果 
    		for (int i = 0; i < len2; i++) {
    			printf("%d={", g[i]);
    			for (int j = 0; j < len1; j++) {
    				printf("%d=%d", nums[j], ans[g[i]][nums[j]]);
    				if (j < len1 - 1) printf(",");
    				else printf("}\n");
    			}
    		} 
    	}
    	return 0;
    }
    

    问题 C: Be Unique (20)

    这道题的难点在于找出第一个独特的数,其实只要按照输入的数组顺序,在记录次数的哈希表中查找只出现一次的数,发现了一个就结束查找并输出,直到最后也没找到就是没有。

    #include <cstdio>
    const int maxn = 10500;
    
    int main() {
    	int N; 
    	while (scanf("%d", &N) != EOF) {
    		int hashTable[maxn] = {0}, tmp[N];
    		for (int i = 0; i < N; i++) {
    			scanf("%d", &tmp[i]);
    			hashTable[tmp[i]]++;
    		}
    		int win = 0;
    		for (int i = 0; i < N; i++) {
    			if (hashTable[tmp[i]] == 1) {
    				printf("%d\n", tmp[i]);
    				win = 1;
    				break;
    			}
    		}
    		if (!win) printf("None\n");
    	}
    }
    

    问题 D: String Subtraction (20)

    all the characters are visible ASCII codes and white space。输入的字符包括字母数字和各种符号这些可见ascll字符,还有空格,因此需要能容纳整个ascll码的哈希表。这题虽然是字符串,但实际上还是整数哈希

    #include <cstdio>
    int main() {
    	char s1[10100], s2[10100];
    	while (gets(s1) != NULL) {
    		bool hashTable[130] = {false}; 
    		gets(s2);
    		for (int i = 0; s2[i]; i++) {
    			hashTable[s2[i]] = true;  //将字符相应ascii码位置的哈希表设为true
    		}
    		for (int i = 0; s1[i]; i++) {
    			if (!hashTable[s1[i]]) //如果字符没有出现在s2中
    			   printf("%c", s1[i]);
    		}
    		printf("\n");
    	}
    }
    

    《算法笔记》4.3小节——算法初步->递归

    http://codeup.cn/contest.php?cid=100000583
    很多数据结构本身也是递归定义的

    问题 A: 吃糖果

    题目描述
    名名的妈妈从外地出差回来,带了一盒好吃又精美的巧克力给名名(盒内共有 N 块巧克力,20 > N >0)。
    妈妈告诉名名每天可以吃一块或者两块巧克力。
    如果N=1,则名名第1天就吃掉它,共有1种方案;
    如果N=2,则名名可以第1天吃1块,第2天吃1块,也可以第1天吃2块,共有2种方案;
    如果N=3,则名名第1天可以吃1块,剩2块,也可以第1天吃2块剩1块,所以名名共有2+1=3种方案;
    如果N=4,则名名可以第1天吃1块,剩3块,也可以第1天吃2块,剩2块,共有3+2=5种方案。
    假设名名每天都吃巧克力,问名名共有多少种不同的吃完巧克力的方案。

    • 输入:输入只有1行,即整数N。
    • 输出:可能有多组测试数据,对于每组数据,输出只有1行,即名名吃巧克力的方案数。
    • 样例输入
      1
      2
      4
      
    • 样例输出
      1
      2
      5
      

    每次吃的时候,名名可以吃一块巧克力,或者吃两块巧克力,也就是说,每次吃的时候,有两种吃法。

    • 第一种吃法:第一次吃了一块巧克力,那么还剩下N-1块还没吃,剩下的N-1块的吃法是f(n-1)种。相信递归函数可以递归求解这个子问题。
    • 第二种跳法:第一次吃了两块块巧克力,那么还剩下N-2块还没吃,剩下的N-2块的吃法有f(n-2)种。同样相信递归函数可以递归求解这个子问题。
    • 所以,N块巧克力的全部吃法就是这两种吃法之和了,即 f(n) = f(n-1) + f(n-2)。

    这个题目可以有多种解法,不过大体是分治的思路(循环实现)。将一个大的问题F(N)分成多个小的性质相同的问题F(N-1)和F(N-2),运用递归或非递归求解这些子问题,然后合并起来。动态规划的实际代码如下,就是变形的斐波拉契数列。

    #include <cstdio>
    int a[30] = {0, 1, 2};
    
    int main() {
        int N;
        for (int i = 3; i <= 20; i++) {
            a[i] = a[i - 1] + a[i - 2];
        }
        while (scanf("%d", &N) != EOF) {
            printf("%d\n", a[N]);
        }
        return 0;
    }
    

    问题 B: 数列

    题目描述:编写一个求斐波那契数列的递归函数,输入n 值,使用该递归函数,输出如下图形(参见样例)。

    • 输入:输入第一行为样例数m,接下来有m行每行一个整数n,n不超过10。
    • 输出:对应每个样例输出要求的图形(参见样例格式)。
    • 样例输入
    1
    6
    
    • 样例输出
              0
            0 1 1
          0 1 1 2 3
        0 1 1 2 3 5 8
      0 1 1 2 3 5 8 13 21
    0 1 1 2 3 5 8 13 21 34 55
    

    出于对递归求解斐波那契数列(这绝对不是分治!)的厌恶,我还是选择了循环。

    #include <cstdio>
    
    int main() {
        int fib[25] = {0, 1, 1}; //f(0) = 0
        for (int i = 3; i <= 20; i++)
            fib[i] = fib[i - 1] + fib[i - 2];
        int m, n;
        scanf("%d", &m);
        while (m--) {
            scanf("%d", &n);
            for (int i = 1; i <= n; i++) { //打印n层
                int spaceNum = (n - i) * 2; //打印空格
                for (int l = 0; l < spaceNum; l++) {
                    printf(" ");
                }
                for (int j = 0; j < 2 * i - 1; j++) {
                    printf("%d", fib[j]);
                    if (j < 2 * i - 2) printf(" ");
                    else printf("\n");
                }
            }
        }
        return 0;
    }
    

    ★★ 问题 C: 神奇的口袋

    题目描述
    有一个神奇的口袋,总的容积是40,用这个口袋可以变出一些物品,这些物品的总体积必须是40。John现在有n个想要得到的物品,每个物品的体积分别是a1,a2……an。John可以从这些物品中选择一些,如果选出的物体的总体积是40,那么利用这个神奇的口袋,John就可以得到这些物品。现在的问题是,John有多少种不同的选择物品的方式。

    • 输入:输入的第一行是正整数n (1 <= n <= 20),表示不同的物品的数目。接下来的n行,每行有一个1到40之间的正整数,分别给出a1,a2……an的值。
    • 输出:输出不同的选择物品的方式的数目。
    • 样例输入
      2
      12
      28
      3
      21
      10
      5
      
    • 样例输出
      1
      0
      

    在我刷LeetCode的数组-回溯算法中的子集问题与这个问题十分相似,参照一下,都是对一棵树的深度遍历。递归边界是40递归式(缩小问题范围)是通过移动数组指针的方式进行的。https://blog.csdn.net/myRealization/article/details/97446896

    #include <cstdio>
    const int maxn = 25, Capacity = 40;
    int cnt;  //合法方案的数目 
    
    /* 相当于求出stuffs[]集合的真子集, 并判断总重量是否合适 */ 
    void MagicalDFS(int weight, int stuffs[], int pos) {
    	if (weight == Capacity) { //进入这里的就是合法方案 
    		cnt++;  //方案+1 
    		return;
    	} 
    	for (int i = pos; stuffs[i] != 0; i++) {
    		//printf("weight = %d + %d\n", weight, stuffs[i]); 
    		weight += stuffs[i];
    		if (weight <= Capacity) {
    		   MagicalDFS(weight, stuffs, i + 1); //深入遍历下一层 
    		}
    		weight -= stuffs[i]; //这一条路径遍历到底部, 从下一层返回到本层的状态 
    	}
    }
    
    int main() {
    	int n;
    	while (scanf("%d", &n) != EOF) {
    		int a[maxn] = {0}; 
    		for (int i = 0; i < n; i++) {
    			scanf("%d", &a[i]);
    		}
    		cnt = 0;
    		MagicalDFS(0, a, 0);
    		printf("%d\n", cnt);
    	}
    }
    

    ★★ 问题 D: 八皇后

    题目描述:会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8 * 8个方格),使它们谁也不能被吃掉!这就是著名的八皇后问题。
    对于某个满足要求的8皇后的摆放方法,定义一个皇后串a与之对应,即a=b1b2…b8,其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解(即92个不同的皇后串)。
    给出一个数b,要求输出第b个串。串的比较是这样的:皇后串x置于皇后串y之前,当且仅当将x视为整数时比y小。

    • 输入:第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数b(1 <= b <= 92)
    • 输出:输出有n行,每行输出对应一个输入。输出应是一个正整数,是对应于b的皇后串。
    • 样例输入
      3
      6
      4
      25
      
    • 样例输出
      25713864
      17582463
      36824175
      

    在我刷LeetCode的回溯算法中的N皇后问题与这个问题同出一源,参照一下,思路基本一样。https://blog.csdn.net/myRealization/article/details/97446896

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    //n为皇后的个数, 哈希表用来记录整数x是否已经在col中, col为不同行皇后所在列的一个排列 
    int n, hashTable[10] = {false}, col[10] = {0}, QueenStringList[100], p = 1; //皇后串的结果表 
    
    void QueenDFS(int CurRow) {
    	if (CurRow == n + 1) {
    		for (int i = 1; i <= 8; i++) 
    			QueenStringList[p] = QueenStringList[p] * 10 + col[i];
    		p++;
    		return;
    	}
    	for (int x = 1; x <= 8; x++) {   //第x列 
    		if (hashTable[x] == false) { //第x列还没有皇后 
    			bool flag = true;        //flag为true表示和之前的皇后不会冲突 
    			for (int pre = 1; pre < CurRow; pre++) {
    			 	if (abs(CurRow - pre) == abs(x - col[pre])) {
    			 	    flag = false;    //同之前的皇后在一条对角线上冲突 
    					break;	
    		        }
    		    }
    		    if (flag) { //如果可以摆放在这一列 
    		    	hashTable[x] = true; //这一列已经被占用 
    		    	col[CurRow] = x;     //令当前行的列号为x 
    				QueenDFS(CurRow + 1); //递归处理第curRow+1行的皇后该摆放在哪一列
    				hashTable[x] = false; //递归完毕, 无论是否这次递归抵达边界, 都还原其为未占用  
    			}	
    		}
    	}
    }
    int main() {
        int m;
        scanf("%d", &m);
        n = 8; //启动为8皇后 
        QueenDFS(1);
        while (m--) {
            int b;
            scanf("%d", &b);
            printf("%d\n", QueenStringList[b]);
        }
        return 0;
    }
    

    《算法笔记》4.4小节——算法初步->贪心

    http://codeup.cn/contest.php?cid=100000584

    ★★ 问题 A: 看电视

    题目描述
    暑假到了,小明终于可以开心的看电视了。但是小明喜欢的节目太多了,他希望尽量多的看到完整的节目。
    现在他把他喜欢的电视节目的转播时间表给你,你能帮他合理安排吗?

    • 输入
      输入包含多组测试数据。每组输入的第一行是一个整数n(n<=100),表示小明喜欢的节目的总数。
      接下来n行,每行输入两个整数si和ei(1<=i<=n),表示第i个节目的开始和结束时间,为了简化问题,每个时间都用一个正整数表示。
      当n=0时,输入结束。
    • 输出
      对于每组输入,输出能完整看到的电视节目的个数。
    • 样例输入
      12
      1 3
      3 4
      0 7
      3 8
      15 19
      15 20
      10 15
      8 18
      6 12
      5 10
      4 14
      2 9
      0
      
    • 样例输出
      5
      

    很有意思的区间贪心问题,这里总是先选择左端点最大的区间总是先选择右端点最小的区间也是可行的

    与之类似的是区间选点问题,给定N个闭区间[x, y],求最少需要确定多少个点才能保证每个闭区间中都至少存在一个点。例如对闭区间[1, 4]、[2, 6]、[5, 7]来说需要两个点如3、5,才能确保每个闭区间内都至少有一个点。代码写法也是类似的。

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    struct Inteval {
    	int left, right; //左右区间端点表示 
    };
    bool cmp(struct Inteval a, struct Inteval b) {
    	if (a.left != b.left) return a.left > b.left; // 按区间左端点大小从大到小排序 
    	else return a.right < b.right;  //左端点相同, 按右端点大小从小到大排序 
    }
    
    int main() {
    	int N;
    	while (scanf(