UVA548 (根据中序后序还原树)
难点：如何根据中序后序还原树
卡点：题目让求一个叶子节点的权重，这个节点到根的数值总和最小，且这个叶子节点是最小的那个。算总和的时候初值设为单个点的权重上限，而忘记了总和很可能超出单个点的权重上限。
纠正：minsum往大乘个1000即可
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
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
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
const int maxn=10010;
int minsum=maxn;
int minthis=maxn;
struct node{
	int weight;
	node *left;
	node *right;
	node(){
		left=right=NULL;
		weight=0;
	}
}*root;

int in[maxn],post[maxn];

node * build(int l1,int r1,int l2,int r2,int sumw){
	if(l1>r1) return NULL;
	node *now=new node();
	now->weight=post[r2];
	int p=l1;
	while(in[p]!=post[r2]) p++;
	int cnt=p-l1;

	sumw+=now->weight;
	if(l1>p-1&&p+1>r1){
		if(sumw<minsum){
			minsum=sumw;
			minthis=now->weight;
		}
		else if(sumw==minsum&&now->weight<minthis)
			minthis=now->weight;
	}

	now->left=build(l1,p-1,l2,l2+cnt-1,sumw);
	now->right=build(p+1,r1,l2+cnt,r2-1,sumw);
	return now;
}

void deltree(node *now){
	if(now==NULL) return;
	deltree(now->left);
	deltree(now->right);
	delete now;
	return;
}

int main(){
	while(!cin.eof()){
        //minsum=minthis=maxn;
		minsum=minthis=maxn*1000;
		string s1,s2;
		getline(cin,s1);
		getline(cin,s2);
		stringstream ss1(s1);
		stringstream ss2(s2);
		int x1,x2,n=0;
		while(ss1>>x1){
			in[n]=x1;
			ss2>>x2;
			post[n++]=x2;
		}
		root=build(0,n-1,0,n-1,0);
		deltree(root);
        //if(minthis!=maxn) cout<<minthis<<'\n';
		if(minthis!=maxn*1000) cout<<minthis<<'\n';
	}
	return 0;
}

UVA839 递归模拟生成树 树的先序遍历
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
#include <iostream>
using namespace std;
bool ans;

int f(){
    int wl,dl,wr,dr;
    cin>>wl>>dl>>wr>>dr;
    if(wl==0) wl=f();
    if(wr==0) wr=f();
    if(wl*dl!=wr*dr) ans=false;
    return wl+wr;
}

int main(){
    int n;
    cin>>n;
    while(n--){
        ans=true;
        f();
        if(ans) cout<<"YES\n";
        else cout<<"NO\n";
        if(n) cout<<'\n';
    }
    return 0;
}

UVA699 递归模拟树 树的先序遍历

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
#include <iostream>
using namespace std;
const int maxn=20010;
int a[maxn];
int mini,maxi;
bool emptytree;
void f(int i){
	int w;
	cin>>w;
	if(w==-1) return;
	else emptytree=false;
	if(i<mini) mini=i;
	if(i>maxi) maxi=i;
	a[i]+=w;
	f(i-1);
	f(i+1);
	return;
}
main(){
	for(int i=0;i<maxn;i++) a[i]=0;
	int n=0;
	while(!cin.eof()){
		emptytree=true;
		mini=maxn+1;
		maxi=-1;
		f(maxn/2);
		if(emptytree) break;
		cout<<"Case "<<++n<<":\n";
		for(int i=mini;i<maxi;i++){
			if(a[i]>0) cout<<a[i]<<' ';
			a[i]=0;
		}
		cout<<a[maxi]<<"\n\n";
		a[maxi]=0;
	}
	return 0;
}

UVA297 根据前序序列构建四分树
WA了一次，题目需要构建一个32*32的方阵，心里念叨着三十乘三十大约是九百多想当然的开了一个长度为1000的数组，结果理所当然的RE了……

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 <cstdio>
#include <cstring>
using namespace std;
int indexl;
char s[2000];
char map[36][36]={0};
void draw(int x,int y,int l){
	for(int i=0;i<l;i++)
		for(int j=0;j<l;j++)
			map[j+y][i+x]=1;
	return;
}
void f(int x,int y,int l){
	char ch=s[indexl++];
	if(ch=='f') draw(x,y,l);
	else if(ch=='p'){
		f(x,y,l/2);
		f(x+l/2,y,l/2);
		f(x,y+l/2,l/2);
		f(x+l/2,y+l/2,l/2);
	}
	return;
}

int main(){
	int n,ans;
	cin>>n;
	while(n--){
		for(int i=0;i<32;i++)
			for(int j=0;j<32;j++)
					map[j][i]=0;
		indexl=0;
		scanf("%s",s);
		f(0,0,32);
		indexl=0;
		scanf("%s",s);
		f(0,0,32);
		ans=0;
		for(int i=0;i<32;i++)
			for(int j=0;j<32;j++)
				if(map[j][i]==1) ans++;
		cout<<"There are "<<ans<<" black pixels.\n";
	}
	return 0;
}

UVA572 简单的DFS
卡点：看到主函数里那被注释的两条函数了吗？那是一个关于变量作用域的悲剧；看到dfs里的<=0了吗？那是一个关于RE的悲剧。
EXP1:注意不要把一个变量莫名声明两次
EXP2:遍历一格周围八个点时，记得从-1开始，<=1时结束
EXP3:遍历地图时，既要注意不超上界，也要注意不超下界

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
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxl=105;
char map[maxl][maxl];
char str[maxl];
int ans,x,y;
void dfs(int j,int i){
	if(j>=0&&i>=0&&j<x&&i<y&&map[i][j]=='@'){
		map[i][j]='*';
		for(int q=-1;q<=1;q++)
			for(int w=-1;w<=1;w++){
				dfs(j+w,i+q);
			}
	}
	return;
}
int main(){
	//int x,y;
	while(1){
		ans=0;
		scanf("%d%d",&y,&x);
		if(x==0&&y==0) break;
		for(int i=0;i<y;i++){
			scanf("%s",str);
			for(int j=0;j<x;j++)
				map[i][j]=str[j];
		}
		for(int i=0;i<y;i++)
			for(int j=0;j<x;j++)
				if(map[i][j]=='@') {
					dfs(j,i);
					ans++;
				}
		cout<<ans<<'\n';
	}
	return 0;
}

P1141 简单的BFS+高性能 人生第一次MLE达成！
BFS，顺便把到目前为止总的询问的次数作为该次的连通分量，再记一下本次询问的解，以后查询到被标记的块儿就去找现成的之前的解
卡点1:没看全题就上手，完全忽略了01变换的条件
卡点2:题中所给坐标从1开始，而数组下标从0开始
卡点3:为节约内存，连通分量的数组用的char类型，后来超出了char的限制还没意识到…..再后来用连通分量做数组下标，超内存了
EXP1:审题的时候稍微沉着一点
EXP2:记得思考题中坐标能不能拿来直接做数组下标
EXP3:MLE很可能是下标出了问题
EXP4:128M内存真的绰绰有余，我再也不省内存了(你看没省内存的时候从不出问题，一省内存就内存不足)
EXP5:VSCODE的调试功能岂是我等手动加调试代码所能相比的？

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
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=1000+10;
int map[maxn][maxn];
int mark[maxn][maxn];
char str[maxn];
int n,m,ans,xx,yy,t;
int oldans[100000];
void bfs(int x,int y,char now){
	if(x<0||y<0||x>=n||y>=n||mark[y][x]!=0||map[y][x]!=now) return;
	mark[y][x]=t;
	ans++;
	if(now=='0') now='1';
	else now='0';
	bfs(x-1,y,now);
	bfs(x+1,y,now);
	bfs(x,y-1,now);
	bfs(x,y+1,now);
}
int main(){
	t=0;
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%s",str);
		for(int j=0;j<n;j++) map[i][j]=str[j];
	}
	for(int q=0;q<n;q++)
		for(int w=0;w<n;w++)
			mark[q][w]=0;
	for(int i=0;i<m;i++){
		t++;
		scanf("%d%d",&yy,&xx);
		if(mark[yy-1][xx-1]!=0) printf("%d\n",oldans[mark[yy-1][xx-1]]);
		else{
			ans=0;
			bfs(xx-1,yy-1,map[yy-1][xx-1]);
			printf("%d\n",ans);
			oldans[t]=ans;
		}
	}
	return 0;
}

2019/1/29
UVA10305 拓扑排序
定义:对一个有向图的所有节点进行排序，使得所得排序中没有一个节点指向它前面的节点。
用处:判断一个有向图是否成环。若拓扑序列长度等于节点数，则无环；若小于，则有环。
核心思路:先把所有入度为0的节点放进队列里，在将其指向的所有节点入度减一；若入度减为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
#include <iostream>
#include <queue>
using namespace std;
const int maxn=100+5;
char map[maxn][maxn];
char in[maxn];
int m,n,x,y;
int main(){
	while(1){
		cin>>n>>m;
		if(m==0&&n==0) break;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				map[i][j]=0;
		for(int i=1;i<=n;i++) in[i]=0;
		for(int i=0;i<m;i++){
			cin>>y>>x;
			map[y][x]=1;
			in[x]++;
		}
		queue<int> q;
		for(int i=1;i<=n;i++)
			if(in[i]==0) q.push(i);//入度为0，入队列
		while(!q.empty()){
			int w=q.front();
			q.pop();
			for(int i=1;i<=n;i++)
				if(map[w][i]){
					in[i]--;
					if(in[i]==0) q.push(i);//入度为0，入队列
				}
			cout<<w<<' ';
		}
		cout<<'\n';
	}
	return 0;
}

UVA10129 欧拉回路
欧拉回路定义:参考“七桥问题”
构成欧拉回路的条件:要判断的有向图为弱连通图，且存在0个或2个节点的入度不等于出度。且那两个节点必须是一个的”出度-入度”=1做起点，另一个的”入度-出度”=1做终点
卡点:单词开头结尾相同，卡；输入数据ab ab，卡。总的来讲就是没看仔细欧拉回路的定义

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
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
const int maxn=26;
int a[maxn][maxn];
int v[maxn],in[maxn],out[maxn];
int n,t;
int startmark,endmark,failed;
void dfs(int x){
	v[x]=1;
	for(int i=0;i<maxn;i++)
		if(a[x][i]&&v[i]==0)
			dfs(i);
	return;
}
int main(){
    cin>>t;
    while(t--){
		startmark=endmark=failed=0;
        memset(a,0,sizeof(a));
		memset(v,0,sizeof(v));
		memset(in,0,sizeof(in));
		memset(out,0,sizeof(out));
        cin>>n;
        while(n--){
            string s;
            cin>>s;
            a[s[0]-'a'][s[s.length()-1]-'a']++;
			a[s[s.length()-1]-'a'][s[0]-'a']++;
			in[s[0]-'a']++;
			out[s[s.length()-1]-'a']++;
        }
		int q;
		failed=0;
		for(q=0;in[q]==0&&out[q]==0;q++);
		dfs(q);
		for(int i=0;i<maxn;i++)
			if((in[i]||out[i])&&v[i]==0){
				failed=1;
				break;
			}
		if(failed==0){
			for(int i=0;i<maxn;i++){
				if(in[i]>out[i]) startmark+=in[i]-out[i];
				if(out[i]>in[i]) endmark+=out[i]-in[i];
			}
		}
		if(failed) cout<<"The door cannot be opened.\n";
		else if(startmark==endmark&&startmark<=1) cout<<"Ordering is possible.\n";
		else cout<<"The door cannot be opened.\n";
    }
}