洛谷【データ構造1-2/4】二叉樹/図
77723 ワード
目次二叉木 P 4913【深基16.例3】二叉樹深さ P 129エルゴード問題 図 P 5318検索文献 P 316図のエルゴード P 1807最長道路 P 127ワードチェーン P 363ゴースト迷路 二叉の木
P 4913【深基16.例3】二叉樹深さ
前の順序と後の順序がすでに知られています.中の順序が連続データの数を遍歴することを求めます.
前のシーケンスと後のシーケンスのみが分かりますが、中のシーケンスの不確実性は、サブノードが左のサブツリーか右のサブツリーかを知らないことです.
したがって、DFSを使用して、1本のツリーを深く検索し、左のサブツリーの場合*右のサブツリーの場合*ルートノードa全体の場合は、全体の中間シーケンスの個数となる.
再帰境界は、このときツリーにはノードが一つしかない場合と、一つの場合しかない.
その後、シーケンスのルートノードの左のサブツリーと右のサブツリーをそれぞれdfsし、各レイヤの場合の数を得て、さらに乗算することが最後の結果となる.
P 5318文献を検索する
P 4913【深基16.例3】二叉樹深さ
#include
using namespace std;
const int maxn = 100010;
struct node{
int left,right;
}tree[maxn];
int n,ans;
void dfs(int id,int deep){
if(id == 0) return;//
ans = max(ans,deep);
dfs(tree[id].left,deep+1);
dfs(tree[id].right,deep+1);
}
int main(){
scanf("%d",&n);//
for(int i=1;i<=n;i++){
scanf("%d %d",&tree[i].left,&tree[i].right);
}
dfs(1,1);
printf("%d
",ans);
return 0;
}
P 229エルゴード問題前の順序と後の順序がすでに知られています.中の順序が連続データの数を遍歴することを求めます.
前のシーケンスと後のシーケンスのみが分かりますが、中のシーケンスの不確実性は、サブノードが左のサブツリーか右のサブツリーかを知らないことです.
a b c
c b a
ルートノードはaであり、ルートノードの左のサブツリーはbをルートノードとしているに違いない.この場合、bがちょうど後のシーケンスのaの前のビットであれば、明のルートノードaは第2のケムの木がないという.このとき、サブツリーbcは左のツリーでも右のサブツリーでも良いので、2つの場合がある.a b c
b c a
このとき、bcはそれぞれaの左右のサブツリーであり、中間シーケンスが固定されているのは、一つの場合だけである.したがって、DFSを使用して、1本のツリーを深く検索し、左のサブツリーの場合*右のサブツリーの場合*ルートノードa全体の場合は、全体の中間シーケンスの個数となる.
再帰境界は、このときツリーにはノードが一つしかない場合と、一つの場合しかない.
int ltree = index[s1[st1+1]]-st2+1;
左のサブツリーの長さを計算するには、次のシーケンスの各文字の位置を記録するindex配列が必要です.for(int i =0;i<len;i++){
index[s2[i]] = i;// s2
}
このとき、左サブツリーのルートノードは、後のシーケンスの位置−後のシーケンスの先頭index+1であり、左サブツリーの結点個数である.if(st1+ltree == en1) k=2;
最初のシーケンスのルートノードindex+左サブツリーがポイントの個数==最初のシーケンスの最後のノードindexを結べば、ルートノードはサブツリーしかない.この場合、サブツリーの場合は2つあり、左または右とすることができる.その後、シーケンスのルートノードの左のサブツリーと右のサブツリーをそれぞれdfsし、各レイヤの場合の数を得て、さらに乗算することが最後の結果となる.
#include
using namespace std;
const int maxn = 1010;
string s1,s2;
int index[maxn];
int dfs(int st1,int en1,int st2,int en2){
if(st1>=en1) return 1;// ,
int ltree = index[s1[st1+1]]-st2+1;// st1
int k =1;//
if(st1+ltree == en1) k=2;// st1 , ,k=2
return (dfs(st1+1,st1+ltree,st2,st2+ltree-1) * dfs(st1+ltree+1,en1,st2+ltree,en2) ) * k;
}
int main(){
cin>>s1;//
cin>>s2;//
int len = s2.length();
for(int i =0;i<len;i++){
index[s2[i]] = i;// s2
}
int cnt =dfs(0,s1.length()-1,0,len-1);
printf("%d
",cnt);
return 0;
}
図P 5318文献を検索する
int n,m;//n ,m
vector<int> adj[maxn]; //
bool vis[maxn];
bool inq[maxn];
void dfs(int u){
vis[u] = true;
printf("%d ",u);// dfs
for(int i=0;i<adj[u].size();i++){
int v = adj[u][i];
if(vis[v]==false){
dfs(v);
}
}
}
void dfsG(){
for(int u =1;u<=n;u++){
if(vis[u]==false){
dfs(u);
}
}
}
void bfs(int u){
queue<int> q;
q.push(u);
inq[u] = true;
while(!q.empty()){
int temp = q.front();
printf("%d ",temp);
q.pop();
for(int i=0;i<adj[temp].size();i++){
int v = adj[temp][i];
if(inq[v]==false){
q.push(v);
inq[v] = true;
}
}
}
}
int main(){
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++){
int a,b;
scanf("%d %d",&a,&b);
adj[a].push_back(b);
}
for(int i=1;i<=n;i++){
sort(adj[i].begin(),adj[i].end());
}
dfsG();
printf("
");
bfs(1);
return 0;
}
P 3116図のエルゴード#include
using namespace std;
const int maxn =500100;
int n,m;
vector<int> adj[maxn];
int a[maxn];
void dfs(int s,int k){
if(a[s]) return;
a[s] =k;
for(int i=0;i<adj[s].size();i++){
dfs(adj[s][i],k);
}
}
int main(){
scanf("%d %d",&n,&m);
for(int i =1;i<=m;i++){
int a,b;
scanf("%d %d",&a,&b);
adj[b].push_back(a);//
}
for(int i=n;i>=1;i--){
dfs(i,i);
}
for(int i =1;i<=n;i++){
printf("%d ",a[i]);
}
return 0;
}
P 1807最長道路#include
using namespace std;
const int maxn =1510;
const int INF = 0x3fffff;
int n,m;
int G[maxn][maxn];
int dp[maxn];// i n
bool vis[maxn];
int Qdp(int x){
if(vis[x]==true) return dp[x];//x
vis[x] = true;
for(int i=1;i<=n;i++){// x
if(G[x][i]!=0){
dp[x] = max(dp[x],Qdp(i)+G[x][i]);
}
}
return dp[x];
}
int main(){
memset(vis,0,sizeof(vis));
scanf("%d %d",&n,&m);
for(int i =0;i<m;i++){
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
if(G[u][v]!=0){
if(G[u][v]>w){
continue;
}
}else{
G[u][v] = w;
}
}
fill(dp,dp+n,-INF);// i n
dp[n] = 0;//
vis[n] = true;
Qdp(1);
if(dp[1] == -INF){
printf("-1
");
}else
printf("%d
",dp[1]);
return 0;
}
P 127ワードチェーン#include
using namespace std;
const int maxn =1010;
//const int INF = 0x3fffff;
int n;
int G[maxn][maxn];//
string s[maxn];
int len[maxn];//
int st[maxn],en[maxn];// ( )
bool vis[maxn];
string now[maxn],ans[maxn];// ,
int flag =0,sum=0;//
int findS(){//
for(int i =1;i<=n;i++){
if(st[s[i][0]]-en[s[i][0]] == 1)
return i;
}
return 1;// ,
}
void dfs(int last,int step){
if(flag==1) return;//
if(step == n){
flag=1;
for(int i =1;i<=sum;i++){
ans[i] = now[i];
}
return;
}
for(int i=1;i<=n;i++){
if(vis[i]==true) continue;//
if(G[last][i] == 1){//
now[++sum] = s[i];
vis[i]=true;
dfs(i,step+1);
vis[i] = false;//
sum--;
}
}
}
int main(){
memset(st,0,sizeof(st));
memset(en,0,sizeof(en));
memset(G,0,sizeof(G));
memset(vis,false,sizeof(vis));
scanf("%d",&n);
for(int i =1;i<=n;i++){
cin>>s[i];
}
sort(s+1,s+1+n);
for(int i =1;i<=n;i++){
len[i] = s[i].length();
}
for(int i=1;i<=n;i++){//
for(int j =1;j<=n;j++){
if(i==j) continue;//
if(s[i][len[i]-1]==s[j][0]) G[i][j]=1;
}
}
for(int i =1;i<=n;i++){//
st[s[i][0]]++;
en[s[i][len[i]-1]]++;
}
int start = findS();
vis[start] = true;
now[++sum] = s[start];//
dfs(start,1);
if(flag ==0){
printf("***
");
return 0;
}
for(int i=1;i<=n;i++){
if(i!=n) cout<<ans[i]<<".";
else cout<<ans[i];
}
return 0;
}
P 163ゴースト迷路#include
using namespace std;
const int maxn =1510;
//const int INF = 0x3fffff;
int n,m;
int G[maxn][maxn];//
int dis[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int vis[maxn][maxn][3];// , x , y
bool flag = false;
int stx,sty;
// ,
void dfs(int x,int y,int lx,int ly){// xy lx/ly
if(flag == true) return;
if(vis[x][y][0]&&(vis[x][y][1]!=lx ||vis[x][y][2]!=ly)){
flag = true;
return;
}
vis[x][y][1] = lx,vis[x][y][2] = ly,vis[x][y][0] = true;
for(int i=0;i<4;i++){
int nx = (x+dis[i][0]+n)%n, ny=(y+dis[i][1]+m)%m;// + %
int nlx = lx+dis[i][0],nly=ly+dis[i][1];
if(G[nx][ny]==0){
if(vis[nx][ny][1]!=nlx||vis[nx][ny][2]!=nly ||vis[nx][ny][0]==0){
dfs(nx,ny,nlx,nly);
}
}
}
}
int main(){
while(scanf("%d %d",&n,&m) != EOF){
flag = false;
memset(G,0,sizeof(G));
memset(vis,0,sizeof(vis));
char ch;
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
cin >>ch;
if(ch=='#') G[i][j] = 1;//
if(ch=='S'){//
stx = i; sty =j;
}
}
}
dfs(stx,sty,stx,sty);
if(flag==true) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}