devbox
凡人多烦事01
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

编程2222_7-1 地下迷宫探索

作者：凡人多烦事01 | 2024-06-05 17:18:58

赞

踩

7-1 地下迷宫探索

7-2 寻找大富翁

  1. #include<stdio.h>   //堆排序；  注意:此算法中，下标从1开始
  2. #define max 1000010
  3. int num[max];
  4. void sift(int *num,int low,int high)  //将下标为low位置上的点调到适当位置
  5. {
  6.     int i,j,temp;
  7.     i=low;    j=2*i;   //num[j]是num[i]的左孩子结点；
  8.     temp=num[i];  //待调整的结点
  9.     while(j<=high)
  10.     {
  11.         if(j<high&&num[j]<num[j+1])   //如果右孩子比较大，则把j指向右孩子，j变为2*i+1；
  12.         ++j;
  13.         if(temp<num[j])
  14.         {
  15.             num[i]=num[j];    //将num[j]调整到双亲结点的位置上；
  16.             i=j;   //修改i和j的值，以便继续向下调整；
  17.             j=i*2;
  18.         }
  19.         else break;     //调整结束；
  20.     }
  21.     num[i]=temp;   //被调整的结点放入最终位置
  22. }
  23. int main()
  24. {
  25.      int n,m,i,temp,count=0;
  26.      scanf("%d%d",&n,&m);
  27.      for(i=1;i<=n;i++)
  28.         scanf("%d",&num[i]);
  29.      if(n<m) m=n;   //注意，有一个测试点是n小于m的情况，这时，只用排前n个;
  30.      for(i=n/2;i>=1;i--)  //所有结点建立初始堆
  31.        sift(num,i,n);
  32.      for(i=n;i>=2;i--)   //进行n-1次循环，完成堆排序
  33.     {
  34.         /*以下3句换出了根节点中的关键字，将其放入最终位置*/
  35.         temp=num[1];
  36.         num[1]=num[i];
  37.         num[i]=temp;
  38.         count++;
  39.         if(count==1)
  40.         printf("%d",num[i]);
  41.         else
  42.         printf(" %d",num[i]);
  43.         if(count==m) break;  //打印前m个；
  44.         sift(num,1,i-1);    //减少了1个关键字的无序序列，继续调整。
  45.     }
  46.     if(m==n) printf(" %d",num[1]);  //当n<m的特殊情况下，上面只打印了n~2，还有最后一个下标为1的没有打印，故再打印一个。
  47.     return 0;
  48. }

7-1 公路村村通

  1. #include<stdio.h>
  2. #define  inf 0x3f3f3f3f
  3. int size=0;
  4. typedef struct NODE node;
  5. struct NODE{
  6.     int cell;//节点是谁
  7.     int key;
  8. };
  9. void heapify(node *am,int i)
  10. {
  11.     int l,r,min;
  12.     while(1)
  13.     {
  14.         l=i<<1;
  15.         r=i<<1|1;
  16.         if(l<=size&&am[l].key<am[i].key) min=l;
  17.         else min=i;
  18.         if(r<=size&&am[r].key<am[min].key) min=r;
  19.         if(min==i) return;
  20.         node t=am[min];
  21.         am[min]=am[i];
  22.         am[i]=t;
  23.         i=min;
  24.     }
  25. }
  26. node extract_min(node *am)
  27. {
  28.     node tep=am[1];
  29.     am[1]=am[size--];
  30.     heapify(am,1);
  31.     return tep;    
  32. }
  33. void change(node *am,int i)
  34. {
  35.     while(i>1&&am[i>>1].key>am[i].key)
  36.     {
  37.         node tep=am[i>>1];
  38.         am[i>>1]=am[i];
  39.         am[i]=tep;
  40.         i=i>>1;
  41.     }
  42. }
  43. int findit(node *dis,int v)
  44. {
  45.     for(int i=1;i<=size;i++)
  46.     {
  47.         if(dis[i].cell==v)
  48.         {
  49.             return i;        
  50.         }
  51.     }
  52. }
  53. int cost[1001][1001]={0};
  54. int main(void)
  55. {
  56.     node dis[1002];
  57.     node tep[1002];
  58.     int n,m;
  59.     scanf("%d%d",&n,&m);
  60.     size=n;
  61.     for(int i=1;i<=n;i++)//初始化，dis是队列，tep保存结点的更新情况
  62.     {
  63.         dis[i].key=tep[i].key=inf;
  64.         dis[i].cell=tep[i].cell=i;
  65.         
  66.     }
  67.     for(int i=1;i<=m;i++)
  68.     {
  69.         int r1,r2,co;
  70.         scanf("%d%d%d",&r1,&r2,&co);
  71.         cost[r1][r2]=co;
  72.         cost[r2][r1]=co;
  73.     }
  74.     int ans=0;
  75.     dis[1].key=0;//初始时，设根结点1的路径长度为0
  76.     int mark[1002]={0};//标记有木有在生成树里面
  77.     int flag=0;
  78.     while(size!=0)
  79.     {
  80.         node u=extract_min(dis);
  81.         if(u.key==inf)
  82.         {
  83.             flag=1;
  84.             break;
  85.         }
  86.         mark[u.cell]=1;
  87.         ans+=u.key;
  88.         for(int v=1;v<=n;v++)//用临接链表更快，但也麻烦
  89.         {
  90.             if(cost[u.cell][v]!=0&&mark[v]==0&&cost[u.cell][v]<tep[v].key)
  91.     
  92.             {
  93.                 int t=findit(dis,v);//找到结点v在队列里的位置
  94.                 tep[v].key=cost[u.cell][v];
  95.                 dis[t].key=cost[u.cell][v];
  96.                 change(dis,t);//更新队列
  97.             }
  98.         }
  99.     }
  100.     if(flag)printf("-1\n");
  101.     else printf("%d\n",ans);
  102. }

7-1 地下迷宫探索

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int vis[1010],r[1010][1010],path[1010];
  4. int n,m,s,j=0,cnt=1;  //cnt统计可以点亮的灯个数
  5.  
  6. void dsf(int x){
  7.     for(int i=1; i<=n; i++){
  8.         if(r[x][i]&&!vis[i]){
  9.             cnt++;
  10.             vis[i]=1;
  11.             
  12.             //核心*************
  13.             path[j++]=i;//保存去的结点
  14.             dsf(i);
  15.             path[j++]=x; //保存回去的路
  16.             //*************
  17.         }
  18.     }
  19. }
  20.  
  21. int main(){
  22.     ios::sync_with_stdio(false);
  23.     cin>>n>>m>>s;
  24.     while(m--){
  25.         int a,b;
  26.         cin>>a>>b;
  27.         r[a][b]=1;
  28.         r[b][a]=1;
  29.     }
  30.     path[j++]=s;
  31.     vis[s]=1;
  32.     dsf(s);
  33.     for(int i=0; i<j; i++){
  34.         if(i!=0) cout<<" ";
  35.         cout<<path[i];
  36.     }
  37.     if(cnt<n) cout<<" 0"<<endl;
  38.     return 0;
  39. }

 

7-2 深入虎穴

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.     int n;
  5.     cin>>n;
  6.     vector<int> e[n+1];
  7.     vector<int> vis(n+1,0);
  8.     for(int i = 1;i <= n;i++){
  9.         int t;
  10.         cin>>t;
  11.         for(int j = 0;j < t;j++){
  12.             int a;
  13.             cin>>a;
  14.             vis[a] = 1;
  15.             e[i].push_back(a);
  16.         }
  17.     }
  18.     queue<int> q;
  19.     //找到入口并将入口入队
  20.     for(int i = 1;i <= n;i++){
  21.         if(vis[i] == 0){
  22.             q.push(i);
  23.             break;
  24.         }
  25.     }
  26.     int u = -1;
  27.     //从入口开始bfs
  28.     while(!q.empty()){
  29.         u = q.front();
  30.         q.pop();
  31.         for(auto i : e[u]){
  32.             q.push(i);
  33.         }
  34.     }
  35.     //输出
  36.     cout<<u<<endl;
  37.     return 0;
  38. }

7-1 那就别担心了

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int maxn = 510;
  5. int n,m,s,t;
  6. vector<int> ve[maxn];
  7. int dp[maxn];
  8.  
  9. int dfs(int x){
  10.     if(dp[x]) return dp[x];
  11.     if(x == t) return 1;
  12.     for(auto v : ve[x]){
  13.         dp[x] += dfs(v);
  14.     }
  15.     return dp[x];
  16. }
  17.  
  18. int vis[maxn];
  19. queue<int> que;
  20. int bfs(){
  21.     que.push(s);
  22.     while(!que.empty()){
  23.         int tp = que.front();
  24.         que.pop();
  25.         if(vis[tp]) continue;
  26.         vis[tp] = 1;
  27.         if(tp == t) continue;
  28.         if(!dp[tp]) return 0;
  29.         for(auto x : ve[tp]){
  30.             que.push(x);
  31.         }
  32.     }
  33.     return 1;
  34. }
  35. int main(){
  36.     ios::sync_with_stdio(0);
  37.     cin >> n >> m;
  38.     for(int i = 0; i < m; i++){
  39.         int a,b;cin >> a >> b;
  40.         ve[a].push_back(b);    
  41.     }
  42.     cin >> s >> t;
  43.     dfs(s);
  44.     //for(int i = 1; i <= n; i++){
  45.     //    cout << " " << dp[i] << endl;
  46. //    }
  47.     cout << dp[s] << " ";
  48.     if(bfs()) cout << "Yes" << endl;
  49.     else cout << "No" << endl;
  50.     return 0;
  51. }

 

1-1 新浪微博热门话题

  1. #include <stdlib.h>
  2. #include <string.h>
  3. #include <stdio.h>
  4. #define MAXLENTH 1000007
  5. typedef struct node *Node;
  6. struct node {
  7.     char* KTitle;//整理后的话题
  8.     int Times;//提到次数
  9.     int LastTimeWhoPost;//最近一次提及它的是哪条微博（用于去重）
  10. };
  11. void Scan(int);
  12. int HashKey(char*);
  13. int Mod(int);
  14. void Insert(int,char*);
  15.  
  16. Node Hash[MAXLENTH];//散列存储
  17. Node Titles[MAXLENTH]; // 建立双索引
  18. int SumofTitles=0;//话题总数
  19.  
  20. int main() {
  21.     int n;
  22.     scanf("%d",&n);
  23.     getchar();
  24.     for(int i=0; i<n; i++) {
  25.         Scan(i);
  26.     }
  27.  
  28.     Node MostTimes=Titles[0];
  29.     int NumofMost=0;
  30.     for(int i=1; i<SumofTitles; i++) {
  31. //      printf("{%s--%d}",Titles[i]->KTitle,Titles[i]->Times);
  32.         if(Titles[i]->Times>MostTimes->Times) {
  33.             MostTimes=Titles[i];
  34.             NumofMost=0;
  35.         } else if(Titles[i]->Times==MostTimes->Times) {
  36.             if(strcmp(Titles[i]->KTitle,MostTimes->KTitle)<0) {
  37.                 MostTimes=Titles[i];
  38.             }
  39.             ++NumofMost;
  40.         }
  41.     }
  42.     if(MostTimes->KTitle[0]>='a'&&MostTimes->KTitle[0]<='z')MostTimes->KTitle[0]+='A'-'a';
  43.     printf("%s\n%d",MostTimes->KTitle,MostTimes->Times);
  44.     if(NumofMost) {
  45.         printf("\nAnd %d more ...",NumofMost);
  46.     }
  47.     return 0;
  48. }
  49. void Scan(int NumofWeibo) {
  50.     char temp[141];//每行给出一条英文微博，其长度不超过140个字符
  51. //  getchar();
  52.     gets(temp);
  53.     int Flag_Jin=0;
  54.     char title[141];
  55.     int Flag_Space=1;
  56. //  printf("{S-%s}\n",temp);
  57.     for(char*i=temp,*j=title; *i!='\0'; i++) {
  58.         if(Flag_Jin==1) {
  59.             switch(*i) {
  60.                 case '#':
  61.                     while(*(j-1)==' ')--j;
  62.                     *j='\0';
  63.                     if(strlen(title)>0)//两个连续的#是空话题，不予计数
  64.                         Insert(NumofWeibo,title);
  65.                     Flag_Jin=0;                 
  66.                     j=title;
  67.                     break;
  68.                 case 'a'...'z':
  69.                 case '0'...'9':
  70.                     *j++=*i;
  71.                     Flag_Space=0;
  72.                     break;
  73.                 case 'A'...'Z':
  74.                     *j++=*i-'A'+'a';
  75.                     Flag_Space=0;
  76.                     break;
  77.                 default:
  78.                     if(Flag_Space==0) {
  79.                         *j++=' ';
  80.                         Flag_Space=1;
  81.                     }
  82.                     break;
  83.             }
  84.         } else if(*i=='#') {
  85.             Flag_Jin=1;
  86.             Flag_Space=1;
  87.         }
  88.     }
  89. }
  90. int HashKey(char*K) {
  91. //  printf("&");
  92.     unsigned int n=0;
  93.     while(*K) {
  94.         n+=*K-'a';
  95.         n<<=5;
  96. //      printf("(%d)",n);
  97.         K++;
  98.     }
  99. //  printf("*-*");
  100.     return n;
  101. }
  102. int Mod(int n) {
  103.     while(n<0)n+=MAXLENTH;
  104.     return n%MAXLENTH;
  105. }
  106. void Insert(int NumofWeibo,char*t) {//比较后插入散列表并更新话题原型
  107. //  printf("{I-%s}",t);
  108.     int Key=HashKey(t);
  109.     int i=0,j=0;
  110.     for( ; i<=MAXLENTH/2; i++) {
  111.         j=Mod(Key+i);
  112.         if(Hash[j]) {
  113.             if(strcmp(t,Hash[j]->KTitle)==0) {
  114.                 if(Hash[j]->LastTimeWhoPost==NumofWeibo)return;
  115.                 ++Hash[j]->Times;
  116.                 Hash[j]->LastTimeWhoPost=NumofWeibo;
  117. //              printf("{add:%s}",Hash[j]->KTitle);
  118.             }
  119.         } else break;
  120.         j=Mod(Key-i);
  121.         if(Hash[j]) {
  122.             if(strcmp(t,Hash[j]->KTitle)==0) {
  123.                 if(Hash[j]->LastTimeWhoPost==NumofWeibo)return;
  124.                 ++Hash[j]->Times;
  125.                 Hash[j]->LastTimeWhoPost=NumofWeibo;
  126. //              printf("{add:%s}",Hash[j]->KTitle);
  127.             }
  128.         } else break;
  129.     }
  130.     if(i>MAXLENTH/2) {
  131. //      printf("NOT ENOUGH SPACE");
  132.         exit(1);
  133.     }
  134.     Hash[j]=(Node)malloc(sizeof(struct node));
  135.     Hash[j]->KTitle=(char*)malloc(strlen(t));
  136.     strcpy(Hash[j]->KTitle,t);
  137.     Hash[j]->Times=1;
  138.     Hash[j]->LastTimeWhoPost=NumofWeibo;
  139.     Titles[SumofTitles++]=Hash[j];//把新加入的元素在哈希表中的地址保存进数组。方便遍历。
  140. //  printf("{new:%s}",Hash[j]->KTitle);
  141. }

 

7-1 修理牧场

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<queue>
  4. using namespace std;
  5. const int maxn=10010;
  6.  
  7. priority_queue<int,vector<int>,greater<int> > q;
  8.  
  9. int main(){
  10.     
  11.     int n,k;
  12.     
  13.     cin>>n;
  14.     while(n--){
  15.         
  16.         cin>>k;
  17.         q.push(k);
  18.     }
  19.     
  20.     int ans=0;
  21.     while(q.size()>1){
  22.         
  23.         int x=q.top();
  24.          q.pop();
  25.         
  26.         int y=q.top();
  27.          q.pop();
  28.         
  29.          ans+=x+y;
  30.         q.push(x+y);
  31.         
  32.     }
  33.     cout<<ans<<endl;
  34. }

1-1 二叉排序树查找操作


BSTree SearchBST(BSTree T,ElemType e){
    if(!T||T->data==e)return T;
    else if(e<T->data)return SearchBST(T->lchild,e);
    else
        return SearchBST(T->rchild,e);
}

2-1 平衡二叉树的根

  1. #include <stdio.h>
  2. #include<stdlib.h>
  3. typedef struct node *AVLTree;
  4. struct node{
  5.     int Data;
  6.     AVLTree Left;
  7.     AVLTree Right;
  8. };
  9. int High(AVLTree T){
  10.     if(!T)
  11.         return 0;
  12.     int left=High(T->Left)+1;
  13.     int right=High(T->Right)+1;
  14.     return left>right?left:right;
  15. }
  16. AVLTree LL(AVLTree T){
  17.     AVLTree T1;
  18.     T1=T->Right;
  19.     T->Right=T1->Left;
  20.     T1->Left=T;
  21.     return T1;
  22. }
  23. AVLTree RR(AVLTree T){
  24.     AVLTree T1;
  25.     T1=T->Left;
  26.     T->Left=T1->Right;
  27.     T1->Right=T;
  28.     return T1;
  29. }
  30. AVLTree LR(AVLTree T){
  31.     AVLTree T1,T2;
  32.     T1=T->Left;
  33.     T2=T1->Right;
  34.     T->Left=NULL;
  35.     T2->Right=T;
  36.     T1->Right=NULL;
  37.     T2->Left=T1;
  38.     return T2;
  39. }
  40. AVLTree RL(AVLTree T){
  41.     AVLTree T1,T2;
  42.     T1=T->Right;
  43.     T2=T1->Left;
  44.     T->Right=NULL;
  45.     T2->Left=T;
  46.     T1->Left=NULL;
  47.     T2->Right=T1;
  48.     return T2;
  49. }
  50. AVLTree Insert(AVLTree T,int x){
  51.     if(!T){
  52.         AVLTree T =(AVLTree)malloc(sizeof(struct node));
  53.         T->Data=x;
  54.         T->Left=T->Right=NULL;
  55.         return T;
  56.     }else if(x>T->Data){
  57.         T->Right=Insert(T->Right,x);
  58.         if((High(T->Right)-High(T->Left))>=2){
  59.             if(x>T->Right->Data)
  60.                 T=LL(T);
  61.             else
  62.                 T=RL(T);
  63.         }
  64.     }else if(x<T->Data){
  65.         T->Left=Insert(T->Left,x);
  66.         if((High(T->Left)-High(T->Right))==2){
  67.             if(x<T->Left->Data)
  68.                 T=RR(T);
  69.             else
  70.                 T=LR(T);
  71.         }
  72.     }
  73.     return T;
  74. }
  75. int main() {
  76.     int n,x;
  77.     AVLTree T=NULL;
  78.     scanf("%d",&n);
  79.     for (int i = 0; i < n; i++) {
  80.         scanf("%d",&x);
  81.         T=Insert(T,x);
  82.     }
  83.     printf("%d\n",T->Data);
  84.     return 0;
  85. }

1-1 分糖果（循环线性表）

  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.  
  5.     public static void main(String[] args) {
  6.  
  7.         Scanner sc = new Scanner(System.in);
  8.         int n = sc.nextInt();
  9.         int tangGuo = 0;
  10.         int temp;
  11.         
  12.         int array[] = new int[n];
  13.  
  14.         for (int i = 0; i < n; i++) {
  15.             array[i] = sc.nextInt();
  16.         }
  17.  
  18.         while (true) {
  19.                         int x=0; //x用于记录数组中相同元素的个数
  20.             for (int i = 0; i < n; i++) {
  21.  
  22.                 if (array[i] % 2 != 0) {
  23.                     array[i]++;
  24.                     tangGuo++;
  25.                 }
  26.             }
  27.             for (int i = 0; i < n; i++) {
  28.                 array[i] = array[i] / 2;
  29.             }
  30.  
  31.             temp = array[0]; //将第一个元素的一半赋值给临时变量
  32.             for (int i = 0; i < n - 1; i++) {
  33.  
  34.                 array[i] = array[i] + array[i + 1];
  35.  
  36.             }
  37.             array[n - 1] = array[n - 1] + temp;
  38.             
  39.             for (int i = 0; i < n - 1; i++) {
  40.                 if (array[i] == array[i + 1])
  41.                     ++x;
  42.             }
  43.             if (x == n-1) {
  44.                 System.out.print(tangGuo);
  45.                 break;
  46.             }
  47.         }
  48.     }
  49. }

1-2 表达式转换

  1. import java.util.*;
  2.  
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner input = new Scanner(System.in);
  6.         String str = input.nextLine();
  7.         Stack<Character> stk = new Stack<Character>();
  8.         Map<Character, Integer> map = new HashMap<Character, Integer>();
  9.         map.put('+', 1);map.put('-', 1);map.put('*', 2);map.put('/', 2);
  10.         map.put('(', 3);map.put(')', 3);
  11.         int index = 0;
  12.         boolean flag = true;
  13.         while(index < str.length()){
  14.             
  15.             if((index < 1 || str.charAt(index - 1) == '(') && (str.charAt(index) == '+' || str.charAt(index) == '-')  || isdigit(str.charAt(index))){
  16.                 if(flag) flag = false;
  17.                 else System.out.printf(" ");
  18.                 if(str.charAt(index) != '+') System.out.printf("%c", str.charAt(index));
  19.                 while(index + 1 < str.length() && (str.charAt(index + 1) == '.' || isdigit(str.charAt(index + 1))))
  20.                     System.out.printf("%c", str.charAt(++index));
  21.                 index++;
  22.             }else{
  23.                 
  24.                 if(str.charAt(index) == '(') stk.push(str.charAt(index));
  25.                 else if(str.charAt(index) == ')'){
  26.                     while(!stk.empty() && stk.peek() != '('){
  27.                         System.out.printf(" %c", stk.peek());
  28.                         stk.pop();
  29.                     }
  30.                     stk.pop();
  31.                 }else{
  32.                     while(!stk.empty() && stk.peek() != '(' && map.get(stk.peek()) >= map.get(str.charAt(index))){
  33.                         System.out.printf(" %c", stk.peek());
  34.                         stk.pop();
  35.                     }
  36.                     stk.push(str.charAt(index));
  37.                 }
  38.                 index++;
  39.             }
  40.         }
  41.         while(!stk.empty()){
  42.             System.out.printf(" %c", stk.peek());
  43.             stk.pop();
  44.         }
  45.     }
  46.     static boolean isdigit(char s){
  47.         if(s == '1' || s == '2' || s == '3' || s == '4' || s == '5' || s == '6' || s == '7'
  48.                 || s == '8' || s == '9' || s == '0') {
  49.             return true;
  50.         }
  51.         return false;
  52.     }
  53. }

3-1 优美的括号序列

  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. char s[1000];
  5.  
  6. int main(){
  7.     while(~scanf("%s",s)){
  8.          int count=0;
  9.          int judge=1;
  10.          int i;
  11.          for(i=0;i<strlen(s);i++){
  12.              if(s[i]=='(')count++;
  13.              else if(s[i]==')')count--;
  14.              if(count<0){
  15.                  printf("NO\n");
  16.                  judge=0;
  17.                  break;
  18.              }
  19.          }
  20.          if(count==0&&judge==1)printf("YES\n");
  21.          else if(judge==1&&count!=0)printf("NO\n");
  22.     }
  23.     return 0;
  24. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/677412
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号