UVA 12166 Equilibrium Mobile （天平性质 + DFS）

今天药忘吃喽~ 2024-02-17 19:05 57阅读 0赞

思路：题目要求是求改变的最小，那么就需要选定一个基准砝码，选择方式如下：对于任何一个结点砝码m来说，如果选定为基准，那么整棵树的总重量为m\*2^deepth (m<<deepth)，其中deepth为此砝码的深度，deeoth从0开始；用map<long long ,int>映射重量为(m<<deepth)的个数int，个数最多者选定为基准砝码。

DFS 递归思想：将表达式分成两份（通过，）然后分别DFS向下递归求解

#include<iostream>
    #include<map>
    #include<cstring>
    using namespace std;
    map<long long ,int >map1;
    int tatal;
    string str;
    void dfs(int cur,int len,int deepth){
       if(str[cur]=='['){
       	int temp=0;
       	for(int i=cur+1;i<len;i++){
       		if(str[i]=='[')temp++;
       		else if(str[i]==']')temp--;
       		else if(str[i]==',' && temp==0){
       			dfs(cur+1,i-1,deepth+1);
       			dfs(i+1,len-1,deepth+1);
       			break;     //找到中间点就退出了 
    		   }
    	   }
       }
       else {
       	tatal++;
       	long long  sum=0;  //一定要定义为long long 型，sum<<deepth 可能大于int类型值 
       	while(cur<=len){
       		sum=sum*10+str[cur]-'0';
       		cur++;
    	   }
    	   map1[sum<<deepth]++;
       }
    }
    int main(){
    	int T;
        scanf("%d",&T);
    	while(T--){
    		cin>>str;
    		tatal=0;
    		int len=str.length();
    		dfs(0,len-1,0);
    		int max1=0;
    		for(map<long long ,int>::iterator iter=map1.begin();iter!=map1.end();iter++){
    		max1=max(max1,iter->second);
    		}
    		printf("%d\n",tatal-max1);
    		map1.clear();
    	} 
    	return 0; 
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，57人围观）

还没有评论，来说两句吧...

相关阅读

相关 UVA 12166 Equilibrium Mobile （天平性质 + DFS）

思路：题目要求是求改变的最小，那么就需要选定一个基准砝码，选择方式如下：对于任何一个结点砝码m来说，如果选定为基准，那么整棵树的总重量为m\2^deepth (m<<deept

今天药忘吃喽~/ 2024年02月17日 19:05/ 0 赞/ 58 阅读

相关 Tree UVA 548(DFS)

解题思路：对于给定的二叉树的中序遍历和后序遍历，可以构造出这棵二叉树，方法是根据后序遍历找到树根。然后在中序遍历中找到树根，从而找出左右子树的结点列表，然后递归构造左

我就是我/ 2024年02月17日 18:51/ 0 赞/ 32 阅读

相关 Not so Mobile 天平 UVA839

1. \include<iostream> 2. using namespace std; 3. //通过引用返回左右重物之和 4. bool solve(int& W

男娘i/ 2024年02月17日 18:51/ 0 赞/ 31 阅读

相关 uva705 - Slash Maze 【转化+dfs】

题目：[uva705 - Slash Maze ][uva705 - Slash Maze] 题意：给出一个迷宫，看题目给出的图就知道，由 \\ 和 / 组成，让你

电玩女神/ 2022年08月12日 01:02/ 0 赞/ 16 阅读

相关 uva 1354——Mobile Computing

There is a mysterious planet called Yaen, whose space is 2-dimensional. There are many b

墨蓝/ 2022年08月09日 12:56/ 0 赞/ 53 阅读

相关 Password UVA - 1262——DFS

Think: 1方法: 1>数学规律+DFS or 数学规律+递推 2>暴力枚举 2反思:题意没有理解好，结果一直Wrong Answer(符合对应列都出现的元

傷城~/ 2022年06月15日 09:29/ 0 赞/ 104 阅读

相关 DFS-UVA10004-Bicoloring

DFS-UVA10004-Bicoloring -------------------- 题目链接：[10004 - Bicoloring][]

朴灿烈づ我的快乐病毒、/ 2022年05月14日 22:08/ 0 赞/ 131 阅读

相关 Tree UVA - 548 (DFS+建立二叉树)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsZXgx

男娘i/ 2022年02月28日 13:22/ 0 赞/ 201 阅读

相关 UVA 839 Not so Mobile

思路：记得自己画个图。 ![1586717-20190314230449557-1968612645.png][] 1 // 题意：输入一个树状天平，根据力矩相

旧城等待，/ 2022年01月06日 11:45/ 0 赞/ 145 阅读

相关 UVA 705 - Slash Maze （Flood_Fill + DFS）

分析： 1. 可以知道的是，給定的 slash Maze 中只存在 ‘/’ 和 ‘\\’ ，將斜線或反斜線離散化為 3 \ 3 單位的方格，比如用數字 1 表示單位被覆蓋

客官°小女子只卖身不卖艺/ 2021年11月04日 12:20/ 0 赞/ 274 阅读