首页 > ACM题库 > HDU-杭电 > HDU 2766-HOJ-Equilibrium Mobile[解题报告]C++
2014
02-14

HDU 2766-HOJ-Equilibrium Mobile[解题报告]C++

Equilibrium Mobile

问题描述 :


A mobile is a type of kinetic sculpture constructed to take advantage of the principle of equilibrium. It consists of a number of rods, from which weighted objects or further rods hang. The objects hanging from the rods balance each other, so that the rods remain more or less horizontal. Each rod hangs from only one string, which gives it freedom to rotate about the string.

We consider mobiles where each rod is attached to its string exactly in the middle, as in the figure underneath. You are given such a configuration, but the weights on the ends are chosen incorrectly, so that the mobile is not in equilibrium. Since that’s not aesthetically pleasing, you decide to change some of the weights.

What is the minimum number of weights that you must change in order to bring the mobile to equilibrium? You may substitute any weight by any (possibly non-integer) weight. For the mobile shown in the figure, equilibrium can be reached by changing the middle weight from 7 to 3, so only 1 weight needs to changed.

输入:

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

* One line with the structure of the mobile, which is a recursively defined expression of the form:

<expr> ::= <weight> | "[" <expr> "," <expr> "]"

with <weight> a positive integer smaller than 109 indicating a weight and [<expr>,<expr>] indicating a rod with the two expressions at the ends of the rod. The total number of rods in the chain from a weight to the top of the mobile will be at most 16.

输出:

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

* One line with the structure of the mobile, which is a recursively defined expression of the form:

<expr> ::= <weight> | "[" <expr> "," <expr> "]"

with <weight> a positive integer smaller than 109 indicating a weight and [<expr>,<expr>] indicating a rod with the two expressions at the ends of the rod. The total number of rods in the chain from a weight to the top of the mobile will be at most 16.

样例输入:

3
[[3,7],6]
40
[[2,3],[4,5]]

样例输出:

1
0
3

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#define maxn 1000100
#define ll long long
using namespace std;
char str[maxn];
ll a[maxn];
int main()
{
 // freopen("dd.txt","r",stdin);
 int ncase;
 scanf("%d",&ncase);
 while(ncase--)
 {
 scanf("%s",str);
 int len=strlen(str);
 ll tmp=0;
 int num=0,deep=0,i,ans=1;
 for(i=0;i<len;i++)
 {
 if(str[i]=='[')
 deep++;
 else if(str[i]==',')
 {
 if(tmp)
 {
 a[num++]=tmp*(1<<deep);
 }
 tmp=0;
 }
 else if(str[i]==']')
 {
 if(tmp)
 {
 a[num++]=tmp*(1<<deep);
 }
 tmp=0;
 deep--;
 }
 else
 {
 tmp=tmp*10+str[i]-'0';
 }
 }
 if(tmp)
 {
 a[num++]=tmp<<deep;
 }
 sort(a,a+num);
 tmp=1;
 for(i=1;i<num;i++)
 {
 if(a[i]==a[i-1])
 {
 tmp++;
 if(tmp>ans)ans=tmp;
 }
 else
 tmp=1;
 }
 printf("%d\n",num-ans);
 }
 return 0;
}

  1. 不开车的看不太懂你们争论啊,我只有一点不明白,如果真的快到出口了非并线不可的话,稍微减速等别人过去再从后面并不行吗?非要小窄缝里把屁股往别人脸上挤?

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

  4. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  5. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false