洛谷【データ構造1-2/4】二叉樹/図

77723 ワード

目次
  • 二叉木
  • P 4913【深基16.例3】二叉樹深さ
  • P 129エルゴード問題
  • P 5318検索文献
  • P 316図のエルゴード
  • P 1807最長道路
  • P 127ワードチェーン
  • P 363ゴースト迷路
  • 二叉の木
    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;
    }