例题做不动了，换着做点简单的习题缓一缓

2019/1/30
UVA673 栈的超简单应用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <string>
#include <cstdio>
#include <stack>
using namespace std;
int main(){
	int n;
	char c;
	scanf("%d",&n);
	getchar();
	while(n--){
		stack<char> s;
		while(scanf("%c",&c)==1&&c!='\n'){
			if(s.empty()) s.push(c);
			else if((s.top()=='('&&c==')')||(s.top()=='['&&c==']')){
				s.pop();
			}
			else s.push(c);
			//cout<<s.top()<<'\n';
		}
		if(s.empty()) cout<<"Yes\n";
		else cout<<"No\n";
		
	}
	return 0;
}

UVA712 二叉树 二进制
卡点:没静心去读英文题，直接上手后翻车……
EXP:二叉树有时候和二进制有密切联系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
int main(){
	int n,m,a,t=0;
	int order[10];
	while(++t){
		cin>>n;
		if(n==0) break;
		getchar();
		cout<<"S-Tree #"<<t<<":\n";
		string s1,s2;
		getline(cin,s1);
		for(int i=0;i<n;i++) order[i]=s1[3*i+1]-'0';
		getline(cin,s2);
		a=1<<n;
		cin>>m;
		while(m--){
			int x=0;
			string s3;
			cin>>s3;
			for(int i=0;i<n;i++){
				x=x*2+s3[order[i]-1]-'0';
			}
			cout<<s2[x];
		}
		cout<<"\n\n";
	}
	return 0;
}

UVA536 根据先序中序求后序
卡点1:先序序列与中序序列中元素的想对位置关系
卡点2:用cin.eof()来判断结尾忽略了换行符
EXP:cin返回值为istream&，当遇到eof时返回0,故可用于while(cin>>a)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <string>
using namespace std;
string s1,s2;
void dfs(int l1,int r1,int l2,int r2){
	if(l1>r1) return;
	int m=s2.find(s1[l1]);
	int cnt=m-l2;//左子树的节点数
	dfs(l1+1,l1+cnt,l2,m-1);
	dfs(l1+cnt+1,r1,m+1,r2);
	cout<<s1[l1];
}
int main(){
    while(cin>>s1>>s2){
		dfs(0,s1.length()-1,0,s2.length()-1);
		cout<<'\n';
    }
	return 0;
}

2019/2/1
UVA439 简单的BFS
没啥好说的，干就是了。一开始很莽的写成了DFS，不过改也容易，一遍AC。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
struct node{
	int x,y,step;
	node(int xa=0,int ya=0,int stepa=0){
		x=xa;
		y=ya;
		step=stepa;
	}
};
const int offset[2][8]={{1,1,-1,-1,2,2,-2,-2},
						{2,-2,2,-2,-1,1,-1,1}};
const int maxn=8;
int a[8][8];
int xstart,ystart,xend,yend;

int bfs(int x,int y,int step){
	queue<node> q;
	bool ok=false;
	q.push(node(x,y));
	while(!q.empty()){
		x=q.front().x;
		y=q.front().y;
		step=q.front().step;
		q.pop();
		if(x<0||y<0||x>=maxn||y>=maxn||a[y][x]) continue;
		a[y][x]=step;
		if(x==xend&&y==yend) return step;
		for(int i=0;i<8;i++)
			q.push(node(x+offset[0][i],y+offset[1][i],step+1));
	}
	return 0;
}

int main(){
	string s1,s2;
	while(cin>>s1>>s2){
		xstart=s1[0]-'a';
		ystart=s1[1]-'1';
		xend=s2[0]-'a';
		yend=s2[1]-'1';
		memset(a,0,sizeof(a));
		bfs(xstart,ystart,0);
		cout<<"To get from "<<s1<<" to "<<s2<<" takes "<<a[yend][xend]<<" knight moves.\n";
	}
	return 0;
}

UVA1600 简单的BFS
只是比前一题多了一点数据处理而已，一遍AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
struct node{
	int x,y,step,k;
	node(int xa,int ya,int stepa,int ka)
	:x(xa),y(ya),step(stepa),k(ka)
	{};
};
const int maxn=20;
const int offset[2][4]={{0,0,1,-1},{1,-1,0,0}};
int xmax,ymax,kmax;
int a[maxn][maxn],b[maxn][maxn],c[maxn][maxn];
void bfs(){
	int x,y,step,k;
	queue<node> q;
	q.push(node(0,0,0,kmax));
	while(!q.empty()){
		x=q.front().x;
		y=q.front().y;
		step=q.front().step;
		k=q.front().k;
		q.pop();
		if(x<0||y<0||x>=xmax||y>=ymax) continue;
		if(a[y][x]==0){ 
			if(b[y][x]>=0) continue;
			b[y][x]=step;
			k=kmax;
		} 
		else if(a[y][x]==1){
			k-=1;
			if(c[y][x]>=k) continue;
			c[y][x]=k;
			b[y][x]=step;
		}
		if(x==xmax-1&&y==ymax-1) return;
		for(int i=0;i<4;i++) 
			q.push(node(x+offset[0][i],y+offset[1][i],step+1,k));
	}
	return;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		cin>>ymax>>xmax>>kmax;
		for(int i=0;i<ymax;i++)
			for(int j=0;j<xmax;j++)
				cin>>a[i][j];
		memset(b,-1,sizeof(b));
		memset(c,-1,sizeof(c));
		bfs();
		printf("%d\n",b[ymax-1][xmax-1]);
	}
	return 0;
}

UVA12166 BFS，二叉树的平衡
一开始思路是从叶到根逐级平衡，后来发现思路不对。下级平衡了上级不一定平衡，而要调整上级的平衡就得干扰下级的平衡，脑回路就此堵塞。
在CSDN上看到一种解法运用了统一化的思路。基于二叉树的独特性质，把所有的砝码重量统一为“原重量 \<\< depth”，再借助于map来统计所有统一化重量对应的个数，得解。
在实现过程中把<< depth错写成了<< (16-depth)，（此处16为题目所规定的最大深度）花了一点点时间来debug，借助于VScode强大的debug能力很快的解决了bug(比以前内嵌代码的debug快了无数被)，然后一遍AC
EXP:在处理有差异的元素时可以运用标准化，统一化的思想 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <cctype>
#include <map>
using namespace std;
map<long long,int> cnt;
string s;
int dfs(int i,int depth){
	if(s[i]=='['){
		i=dfs(i+1,depth+1);
		if(s[i]!=',') return i+1;
		i=dfs(i+1,depth+1);
		return i+1;
	}
	else{
		long long num=0;
		while(isdigit(s[i])){
			num=num*10+s[i]-'0';
			i++;
		}
		num=num<<(depth);
		auto iter=cnt.find(num);
		if(iter==cnt.end()) cnt.insert(make_pair(num,1));
		else iter->second++;
	}
	return i;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		long long total=0,max=0,maxnum=0;
		cnt.clear();
		cin>>s;
		dfs(0,0);
		for(auto iter=cnt.begin();iter!=cnt.end();iter++){
			if(iter->second > max){
				total+=max;
				maxnum=iter->first;
				max=iter->second;
			}
			else total+=iter->second;
		}
		cout<<total<<'\n';
	}
	return 0;
}

UVA804 模拟
死在不知名的地方了。至今未果
2019/24 过大年也要好好学习
UVA806 四分树 DFS 严谨
难度有一点儿，不过思路很清晰，但主要是实现起来有各种细节容易出错

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn=64+5;
int a[maxn][maxn];
int num[maxn*maxn];
int n,id;
void inputMaxtrix(){
	for(int i=0;i<n;i++){
		getchar();
		for(int j=0;j<n;j++)
			scanf("%c",&a[i][j]);
	}
	return;
}
void inputSequence(){
	id=0;
	while(scanf("%d",&num[id])==1&&num[id]!=-1) id++;
    //输入矩阵和输出矩阵所用符号不同
	for(int i=0;i<n;i++) memset(a[i],'.',sizeof(int)*n);
	return;
}
bool dfs(int x,int y,int l,int now,int depth){
	if(l<=0) return false;
	int mark=0;
	int white=0,black=0;
	for(int i=y;i<l+y;i++)
		for(int j=x;j<l+x;j++){
			if(a[i][j]!='0') black++;
			else white++;
			if(black&&white) break;
		}

	if(white==0){
		num[id++]=now;
		return true;
	}
	else if(black==0) return true;
	depth++;
    //五进制从低位到高位对应从根部到叶子  
	dfs(x,y,l/2,now+(int)pow(5,depth)*1,depth);
	dfs(x+l/2,y,l/2,now+(int)pow(5,depth)*2,depth);
	dfs(x,y+l/2,l/2,now+(int)pow(5,depth)*3,depth);
	dfs(x+l/2,y+l/2,l/2,now+(int)pow(5,depth)*4,depth);
	return false;
}
void dfsnum(int x,int y,int l,int now){

	if(l<=0) return;
	switch(now%5){
		case 0: 
			for(int i=y;i<y+l;i++)
				for(int j=x;j<x+l;j++)
					a[i][j]='*';
			return;
		case 1:
			dfsnum(x,y,l/2,now/5);
			return;
		case 2:
			dfsnum(x+l/2,y,l/2,now/5);
			return;
		case 3:
			dfsnum(x,y+l/2,l/2,now/5);
			return;
		case 4:
			dfsnum(x+l/2,y+l/2,l/2,now/5);
			return;
	}
	return;
}
void outputSequence(){
	for(int i=0;i<id-1;i++){
        //输出要求每行最多12个数
		if(i%12==11) printf("%d\n",num[i]);
		else printf("%d ",num[i]);
	}
	if(id>0) printf("%d\n",num[id-1]);
	printf("Total number of black nodes = %d\n",id);
	return;
}
void outputMatrix(){
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++)
			putchar(a[i][j]);
		putchar('\n');
	}
	return;
}
int main(){
	int kase=0;
	while(scanf("%d",&n)==1){
		if(n==0) break;
		id=0;
		memset(a,0,sizeof(a));//不在这儿初始化会发生各种奇怪的问题
		if(kase) putchar('\n');
		printf("Image %d\n",++kase);
		if(n>0){
			inputMaxtrix();
			dfs(0,0,n,0,-1);
			sort(num,num+id);

			outputSequence();
		}
		else{
			n=-n;
			inputSequence();
			for(int i=0;i<id;i++) dfsnum(0,0,n,num[i]);
			outputMatrix();
		}
	}
	return 0;
}

2019/2/7
UVA127 栈的简单应用
很简单的题，但我掉坑了
坑点:在最后输出的时候要考虑英语的单复数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
int main(){
    string s;
	while(1){
		vector<stack<string>> v;
		for(int i=0;i<26*2;i++){
			cin>>s;
			if(s[0]=='#') return 0;
			stack<string> st;
			st.push(s);
			v.push_back(st);
		} 
		vector<stack<string>>::iterator iter=v.begin();
		while(iter!=v.end()){
			int mark=0;
			if(iter+1<v.end()){
				vector<stack<string>>::iterator iter1=iter+1;
				if((*iter).top()[0]==(*iter1).top()[0]||(*iter).top()[1]==(*iter1).top()[1]){
					(*iter).push((*iter1).top());
					(*iter1).pop();
					if((*iter1).empty()) v.erase(iter1);
					mark=1;
				}
			}
			if(mark==0&&iter+3<v.end()){
				vector<stack<string>>::iterator iter3=iter+3;
					if((*iter).top()[0]==(*iter3).top()[0]||(*iter).top()[1]==(*iter3).top()[1]){
					(*iter).push((*iter3).top());
					(*iter3).pop();
					if((*iter3).empty()) v.erase(iter3);
					mark=1;
				}
			}
			if(mark) iter=v.begin();
			else iter++;
		}
		cout<<v.size()<<" piles remaining:";
		for(vector<stack<string>>::iterator i=v.begin();i!=v.end();i++) 
			cout<<' '<<(*i).size();
		cout<<'\n';

	}
    return 0;
}

UVA10410 根据DFS和BFS重建树
这题确实把我难住了，后来参照着这篇博文跟着敲了一遍才有了一点感觉
思路：
思考可得两条性质：
在BFS序列中，与a相邻的下一个点可能有三种情况：
（1）节点a的孩子 （2）节点a的第一后兄弟 （3）节点a的兄弟的孩子
在DFS序中，与点a相邻的下一个点可能有三种身份：
（1）节点a的孩子（2）节点a的第一后兄弟（3）啥也不是（意思是说直接回到父辈及以上了）
由这两条性质可得：
若bfs(v)=bfs(u)+1且dfs(v)=dfs(u)+1且v>u,则u，v关系可以（1）或（2）。对于（1）的情况，思考可知此时把v和v的子树提到u这一层并不改变bfs序列和dfs序列，所以此时的（1）可以视为（2）即“若bfs(v)=bfs(u)+1且dfs(v)=dfs(u)+1且v>u,则v为u的第一后兄弟”
若bfs(v) > bfs(u)+1那么它不可能是u的后兄弟，只能是u的孩子。因为u，v的bfs序列不相邻，不能成为第一兄弟节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
const int maxn=1000+10;
int bfsOrder[maxn];
vector<int> child[maxn];
int main(){
    int n;
    while(~scanf("%d",&n)){
        int x;
        for(int i=1;i<=n;i++){
            child[i].clear();
            scanf("%d",&x);
            bfsOrder[x]=i;
        }
        stack<int> sta;
        int root;
        scanf("%d",&root);
        sta.push(root);
        for(int i=1;i<n;i++){
            scanf("%d",&x);
            while(true){
                int temp=sta.top();
                if(bfsOrder[x]>bfsOrder[temp]+1|| //x为temp的子节点
                (bfsOrder[x]==bfsOrder[temp]+1&&temp>=x)|| //x不是temp的第一兄弟节点
                temp==root){
                    child[temp].push_back(x);
                    sta.push(x);
                    break;
                }
                else sta.pop();
            }
        }
        for(int i=1;i<=n;i++){
            printf("%d:",i);
            for(int j=0;j<child[i].size();j++) printf(" %d",child[i][j]);
            putchar('\n');
        }
    }
    return 0;
}

2019/2/10
UVA12118 图的连通性 欧拉回路
开始的时候一点思路也没有，看他人题解讲到了欧拉道路，突然来了灵感，觉得核心在于算出奇点总数并除以二减一，再加上个e，几分钟写完然后WA了。再仔细看了看这篇博文，发现还要判断连通图的个数，对于单个连通图求它所含的奇点数，再和2比较取最大值(每个图至少要有一个入口和一个出口)，最后把总奇点数/2-1，并与0取较大值，最后加上e。
除以二减一的原因：
要把奇点两两相连来创造欧拉道路，故除以二；因为要求出最小道路数，所以欧拉道路存在两个节点度为奇数，故减一
欧拉道路的定义:
构成欧拉道路的条件:要判断的有向图为弱连通图，且存在0个或2个节点的入度不等于出度。且那两个节点必须是一个的”出度-入度”=1做起点，另一个的”入度-出度”=1做终点(有0个节点的欧拉道路又叫欧拉回路)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=1000+10;
int a[maxn];
bool vis[maxn];
int m[maxn][maxn];
int v,e,t,x,y,least,kase,total;
int dfs(int x){
    if(vis[x]) return 0;
    int cnt=0;
    if(a[x]%2==1) cnt=1;
    vis[x]=true;
    for(int i=1;i<=v;i++)
        if(m[x][i]) cnt+=dfs(i);
    return cnt;
}
int main(){
    kase=0;
    while(cin>>v>>e>>t){
        if(v==0&&e==0&&t==0) return 0;
        memset(a,0,sizeof(a));
        memset(vis,false,sizeof(vis));
        memset(m,0,sizeof(m));
        for(int i=0;i<e;i++){
            cin>>x>>y;
            a[x]++;
            a[y]++;
            m[x][y]=1;
            m[y][x]=1;
        }
        least=0,total=0;
        for(int i=1;i<=v;i++)
            if(!vis[i]&&a[i]>0)
                    total+=max(dfs(i),2);
        e+=max(total/2-1,0);
        cout<<"Case "<<++kase<<": "<<e*t<<'\n';
    }
    return 0;
}