从头开始刷ACM，真的发现过去的很多漏洞，特别越是基础的数据结构，越应该学习得精，无论是ACM竞赛，研究生考试，还是工程上，对这些基础数据结构的应用都非常多，深刻理解非常必要。不得不说最近感触还是比较多，申请阿里的校招挂了，申请的是算法工程师。然而得到的答复是第一，几乎只招研究生，本科生被Pass掉了，然后第二，问我是否有读研的打算，我说有，然后吐槽我的ACM搞得像屎一样，成绩根本无法让他满意，如果有意向，建议我能研一能拿个像样的成绩，真是2333。自己弱也怪不得别人了。
训练地址：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=84416#overview
uva679
好吧，先贴一道大水题，自习室做得。
链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=620
ps：白书上代码是超时的，真是个坑
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
int T;
int main()
{
while(cin>>T)
{
if(T==-)
break;
while(T--)
{
int d,l,k;
cin>>d>>l;
k=;
for(int i=;i<d;i++)
{
if(l%)
{
l=l-l/;
k=k*;
}
else
{
l=l/;
k=k*+;
}
}
cout<<k<<endl;
} }
return ;
}
uva122
白书上的一道例题，第一棵二叉树，建树，bfs遍历
链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=58
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<queue>
#include<cstdlib>
#include<cctype>
using namespace std;
const int maxn=;
char s[maxn+];
int failed=;
//结点类型
typedef struct Tnode
{
int have_value; //是否被赋值过
int v; //结点值
struct Tnode *left,*right;
}Node;
Node* root; Node* newnode()
{
Node* u=(Node*)malloc(sizeof(Node)); //申请动态内存
if(u!=NULL) //若申请成功
{
u->have_value=; //初始化为0
u->left=u->right=NULL; //初始化没有左右儿子
}
return u;
} void addnode(int v,char *s)
{
int n=strlen(s);
Node* u=root; //从根结点开始往下走
for(int i=;i<n;i++)
if(s[i]=='L')
{
if(u->left==NULL) u->left=newnode(); //结点不存在，建立新结点
u=u->left; //往左走
}
else if(s[i]=='R')
{
if(u->right==NULL) u->right=newnode();
u=u->right;
} //忽略其他情况，即最后那个多余的右括号
if(u->have_value) failed=; //已经赋值，表示输入有误
u->v=v;
u->have_value=; //做标记
} void remove_tree(Node* u)
{
if(u==NULL) return; //提前判断比较稳妥
remove_tree(u->left); //递归释放左子树
remove_tree(u->right); //递归释放右子树
free(u); //释放u本身
} int read_input() //保存读入结点
{
failed=;
remove_tree(root); //释放一棵二叉树
root=newnode(); //创建跟结点
for(;;)
{
if(scanf("%s",s)!=) return ; //整个输入结束
if(!strcmp(s,"()")) break; //结束标志
int v;
sscanf(&s[],"%d",&v); //读入结点值
addnode(v,strchr(s,',')+); //查找逗号，然后插入结点
}
return ;
} int n=,ans[maxn];
int bfs()
{
int front=,rear=;
Node* q[maxn];
q[]=root;
while(front<rear)
{
Node* u=q[front++];
if(!u->have_value) return ;
ans[n++]=u->v;
if(u->left!=NULL) q[rear++]=u->left;
if(u->right!=NULL) q[rear++]=u->right;
}
return ;
} void print()
{
for(int i=;i<n;i++)
{
if(i) printf(" ");
printf("%d",ans[i]);
}
printf("\n");
n=;
}
int main()
{
while(read_input())
{
if(failed||!bfs()) cout<<"not complete"<<endl;
else print();
}
return ;
}
一个简单的知识点，今天复习数据结构教材的时候写的，已经前序跟中序，打印后序遍历
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<string>
#include<stack>
using namespace std;
const int maxn=+;
void build(int n,char* s1,char* s2,char* s)
{
if(n<=) return;
int p=strchr(s2,s1[])-s2;
build(p,s1+,s2,s); //后序遍历左子树
build(n-p-,s1+p+,s2+p+,s+p); //后序遍历右子树
s[n-]=s1[];
}
int main()
{
char s1[maxn],s2[maxn],s[maxn];
while(scanf("%s%s",s1,s2)==)
{
int n=strlen(s1);
build(n,s1,s2,s);
s[n]='\0';
printf("%s\n",s);
}
return ;
}
uva112
这题让我学到了cin的用法，不得不感叹C++还是博大精深啊，具体请看我的下一篇文章《cin的用法》
开始想建树，后来看了别人的一些思路发现并不用建树，cin.clear()确实是新的认知，uva题目质量真心高，我一定坚持刷下去，最近进度有点慢，明天要开始一切恢复正常了，8月了，一切都开始火烧眉毛了。
下面贴一下代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<cctype>
using namespace std;
typedef struct Tnode
{
Tnode *left,*right;
}node;
int flag;
node* Tree_sum(int n,int sum)
{
char ch;
int v;
cin>>ch;
if(!(cin>>v)==)
{
n+=v;
node* root=(node*)malloc(sizeof(node));
root->left=Tree_sum(n,sum);
root->right=Tree_sum(n,sum);
if(!flag&&root->left==NULL&&root->right==NULL)
{
if(sum==n)
flag=;
}
cin>>ch;
return root;
}
else
{
cin.clear();
cin>>ch;
return NULL;
}
}
int main()
{
int sum;
while(cin>>sum)
{
flag=;
node *root=Tree_sum(,sum);
if(flag)
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
return ;
}
二叉树一个重要知识点：（已知中序+后序，求先序）
ps:白书上是已知先序+中序,求后序，这个稍有改动，说一下，严奶奶书上这个地方代码好像有问题
下面是我的代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<string>
#include<stack>
#include<sstream>
using namespace std;
const int maxn=+;
int k;
bool read_input(int* a)
{
string line;
if(!getline(cin,line)) return false;
stringstream ss(line);
int x;
k=;
while(ss>>x) a[k++]=x;
return k>;
}
int i=;
void build(int n,int* s1,int* s2,int* s)
{
if(n<=) return;
int p=n-;
s[]=s2[p];
while(s1[p]!=s2[n-]) p--;
build(p,s1,s2,s+); //先序遍历左子树
build(n-p-,s1+p+,s2+p,s+p+); //先序遍历右子树
}
int main()
{
int pre[maxn],in[maxn],post[maxn];
while(read_input(in))
{
read_input(post);
build(k,in,post,pre);
for(int i=;i<k;i++)
cout<<pre[i]<<" ";
cout<<endl;
}
return ;
}
uva548
链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=489
不得不说这道题目写了半天，开始我以为可以先通过后序跟中序得出先序，然后向uva112那样写的，后来发现并不能这样，于是开始漫长的建树之路，之后yy出一种可以不用建树的解法，还有不得不说sstream头文件中的stringstream流输入很好用，详见刘汝佳粉书《入门经典第二版》不过最大的缺点就是速度慢
我的AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
#include<sstream>
#include<cstdlib>
using namespace std;
const int maxn=+;
int k,best_sum,best;
bool read_input(int* a) //输入部分
{
string line;
if(!getline(cin,line)) return false;
stringstream ss(line);
k=;
int x;
while(ss>>x) a[k++]=x;
return k>;
}
void dfs(int n,int sum,int* in,int* post) //深搜即可
{
if(n<=) return;
int p=find(in,in+n,post[n-])-in;
sum+=post[n-];
if(n==)
{
if(sum<best_sum)
{
best_sum=sum;
best=post[n-];
}
else if(sum==best_sum)
best=min(best,post[n-]);
return;
}
dfs(p,sum,in,post); //左子树
dfs(n-p-,sum,in+p+,post+p); //右子树
}
int main()
{
int in[maxn],post[maxn];
while(read_input(in))
{
read_input(post);
best_sum=best=0x3ffff;
dfs(k,,in,post);
cout<<best<<endl;
}
return ;
}
uva297
链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104
四叉树，第一次写，不过这题比较特殊，只需要先序就可以建树，然后照着画，边画边统计
我的代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=;
char s1[maxn],s2[maxn];
char *p;
int sum;
typedef struct Tnode
{
int have_value;
struct Tnode* child[];
}node;
//建立四叉树
node* build_tree()
{
node* root=(node*)malloc(sizeof(node));
root->have_value=;
if(*p=='p')
{
for(int i=;i<;i++)
{
++p;
root->child[i]=build_tree();
}
}
else
{
if(*p=='f')
root->have_value=;
for(int i=;i<;i++)
root->child[i]=NULL;
}
return root;
}
//dfs遍历一下
void dfs(node* root1,node* root2,int cnt)
{
if(root1==NULL&&root2==NULL) return;
if(root1==NULL)
{
if(root2->have_value)
{
sum+=>>(*cnt);
return;
}
for(int i=;i<;i++)
dfs(root1,root2->child[i],cnt+);
return;
}
if(root2==NULL)
{
if(root1->have_value)
{
sum+=>>(*cnt);
return;
}
for(int i=;i<;i++)
dfs(root1->child[i],root2,cnt+);
return;
}
if(root1->have_value||root2->have_value)
{
sum+=>>(*cnt);
return;
}
for(int i=;i<;i++)
dfs(root1->child[i],root2->child[i],cnt+);
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>s1>>s2;
p=s1;
node* root1=build_tree();
p=s2;
node* root2=build_tree();
sum=;
dfs(root1,root2,);
printf("There are %d black pixels.\n",sum);
}
}
uva712
链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=653
关键是对题目意思的理解，一个大水题，其实就是0表示向左2*n，1表示向右2*n+1，然后给出一堆查询，输出最后的序列
要换行，uva没有pe，只有WA我也是醉了，要不是看题目意思，我还找不出错误在哪儿
我的代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
const int maxn=;
string s[maxn],query[maxn];
char p[maxn];
int main()
{
int n,t;
int cas=;
while(cin>>n)
{
if(n==)
break;
for(int i=;i<n;i++)
cin>>s[i];
cin>>p;
cin>>t;
for(int i=;i<t;i++)
cin>>query[i];
int sum;
printf("S-Tree #%d:\n",cas);
for(int i=;i<t;i++)
{
sum=;
for(int j=;j<query[i].length();j++)
{
if(query[i][j]=='')
sum=sum*;
else
sum=sum*+;
}
int ff=pow(,n);
printf("%c",p[sum-ff]);
}
printf("\n\n");
cas++;
}
return ;
}
复习复习，晚上在刷一题
uva699
链接：http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=19244
题意：就是统计二叉树每一行的和为多少，给出了先序遍历。我们可以把当前位置设为p，左子树p-1，右子树p+1，然后进行递归即可
我的代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=;
int sum[maxn];
void build(int root,int p)
{
if(root!=-)
{
sum[p]+=root;
int x,y;
cin>>x;
build(x,p-);
cin>>y;
build(y,p+);
}
}
int main()
{
int n,cas=;
while(cin>>n)
{
if(n==-)
break;
memset(sum,,sizeof(sum));
build(n,);
printf("Case %d:\n",cas);
int k;
for(int i=;i<;i++)
if(sum[i]!=)
{
k=i;
printf("%d",sum[i]);
break;
}
for(int i=k+;i<;i++)
if(sum[i]!=)
printf(" %d",sum[i]);
printf("\n\n");
cas++;
}
}
uva327
链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=263
我也不知道这题为什么放在二叉树里面，直接模拟就好了嘛，注意几种情况,a+b,a-b,a++-b,a+++b,--a,++a,然后注意处理一下空格就好了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cctype>
#include<cstdlib>
using namespace std;
const int maxn=;
int a[maxn],flag[maxn];
int main()
{
string s;
while(getline(cin,s))
{
cout<<"Expression: "<<s<<endl;
string ss="";
for(int i=;i<s.length();i++)
if(s[i]!=' ')
ss+=s[i];
for(int i=;i<;i++)
a[i]=i+;
memset(flag,,sizeof(flag));
int sum=;
for(int i=;i<ss.length();i++)
{
if(islower(ss[i]))
{
if(i==)
sum+=(ss[i]-'a'+);
else
{
if(ss[i-]!=ss[i-])
{
if(ss[i-]=='+')
sum+=ss[i]-'a'+;
else if(ss[i-]=='-')
sum-=ss[i]-'a'+;
}
else
{
if(ss[i-]=='-')
a[ss[i]-'a']--;
else if(ss[i-]=='+')
a[ss[i]-'a']++;
if(i>&&ss[i-]=='-')
sum-=a[ss[i]-'a'];
else
sum+=a[ss[i]-'a'];
}
}
if(i+<ss.length()&ss[i+]==ss[i+]&&ss[i+]=='+')
a[ss[i]-'a']++;
else if(i+<ss.length()&&ss[i+]==ss[i+]&&ss[i+]=='-')
a[ss[i]-'a']--;
flag[ss[i]-'a']=;
}
}
cout<<" value = "<<sum<<endl;
for(int i=;i<;i++)
if(flag[i])
printf(" %c = %d\n",'a'+i,a[i]);
}
return ;
}
uva839
链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=780
这题我参照了题解，采取递归的方式定义，因此编写一个递归进行定义就是比较自然的事情
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int ok;
int dfs()
{
int wl,dl,wr,dr;
cin>>wl>>dl>>wr>>dr;
if(wl&&dl&&wr&&dr) //叶子结点
{
if(wl*dl!=wr*dr) //只要有一个不平衡全不平衡
{
ok=;
return ;
}
else return wl+wr; //返回子树的重量
}
else
{
if(!wl) wl=dfs(); //遍历左子树
if(!wr) wr=dfs(); //遍历右子树
if(wl*dl!=wr*dr)
{
ok=;
return ;
}
else
return wl+wr;
}
}
int main()
{
int T;
cin>>T;
int i=;
while(T--)
{
ok=;
dfs();
if(i++) cout<<endl;
if(ok) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return ;
}