题目链接接:
http://uva.onlinejudge.org/index.phpoption=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=2052
题目类型: 数据结构, 链表
题目大意:
这题的题意比较难懂,看了好几变才明白。 就是有一个可以嵌套娃娃的娃娃,然后嵌套在里面的娃娃又可以继续嵌套娃娃。
然后要求直接嵌套在里面(内一层)的娃娃的尺寸大小之和不能超过外面的。 例如,-3 -2 2 3,代表有两层,-3和3表示一个嵌套(这个娃娃的尺寸大小为3,且负数一定要在左边先出现),里面时-2和2表示一个大小2的娃娃。 再比如-5 -2 2 -1 1 5,表示有3个娃娃,5嵌套这2和1。当有更多层的嵌套时,如-9 -7
-22 -3 -2 -112379,表示9嵌套着7.然后7又嵌套着2(左边的-2,2)和3, 3又嵌套这2(右边出现的-2,2), 这个2又嵌套着1。 只要相邻的层次,内一层的大小相加起来小于(不能等于)外一层的大小就满足条件。
解题思路:
这一题也和“括号嵌套”有点像。 首先是题目的输入,由于一开始没有采用一个好的输入方案,导致WA了无数次,浪费了几个小时。 然后题目需要注意的一些地方:1.如果娃娃个数是奇数,则直接判断错误; 2. 正数个数和负数不想等,也是错误的; 3.如果
正数先于对应的负数出现,也是错误的。
我采用的方法是,开一个数组level,用来保存各个层次娃娃的容量,然后每次遇到一个‘)’时就进行处理, 把当前这个层次的”外层“容量减去这个层次的大小。 当有个层次为0或负数时,则可以判断是错误的。最需要注意的是怎样处理和判断当前层次时哪一层。
样例输入:
-9 -7 -2 2 -3 -2 -1 1 2 3 7 9
-9 -7 -2 2 -3 -1 -2 2 1 3 7 9
-9 -7 -2 2 -3 -1 -2 3 2 1 7 9
-100 -50 -6 6 50 100
-100 -50 -6 6 45 100
-10 -5 -2 2 5 -4 -3 3 4 10
-9 -5 -2 2 5 -4 -3 3 4 9
样例输出:
:-) Matrioshka!
:-( Try again.
:-( Try again.
:-) Matrioshka!
:-( Try again.
:-) Matrioshka!
:-( Try again.
#include<cstdio>
#include<iostream>
#include<cstring>
#include<stack>
#include<cmath>
using namespace std;
string str;
int level[30000], arr[30000], numDoll, cntNeg, cntPos, n;
stack<int>st;
bool solve(){
if(numDoll%2==1 || cntNeg!=cntPos)
return false;
int i,j,index=0;
if(numDoll==2){
if(arr[0]<0 && arr[0]+arr[1]==0)
return true;
return false;
}
while(!st.empty())
st.pop();
for(i=0; i<numDoll; ++i){
if(arr[i]<0){
st.push(arr[i]);
level[index++] = abs(arr[i]);
}
else if(arr[i]>0){
if(st.empty() || abs(st.top()) != arr[i])
return false;
if(st.size()==1){
if(level[0] <=0 )
return false;
st.pop();
}
else{
st.pop();
--index;
level[st.size()-1] -= arr[i];
if( level[st.size()-1] <= 0 ){
return false;
}
}
}
}
return true;
}
void input(){
arr[0] = n;
while(getchar()!='\n'){
scanf("%d",&arr[numDoll++]);
};
}
int main()
{
freopen("input.txt","r",stdin);
bool flag=true;
cntNeg=0, cntPos=0;
numDoll=1;
while(~scanf("%d", &n)){
input();
if(solve())
printf(":-) Matrioshka!\n");
else
printf(":-( Try again.\n");
cntNeg=0;
cntPos=0;
numDoll=1;
}
return 0;
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
数据结构英文课件:Chap5 Array, Matrix and Generalized List.ppt
Generalized Linear Mixed Model 教程
VESA Generalized Timing Formula (GTF) Standard.
The Generalized Correlation Method for Estimation of Time Delay The Generalized Correlation Method for Estimation of Time Delay The Generalized Correlation Method for Estimation of Time Delay The ...
This paper introduces the Generalized Search Tree (GiST), an index structure supporting an extensible set of queries and data types. The GiST allows new data types to be indexed in a manner supporting...
Generalized Linear Mixed Models For Large-Scale Response Prediction, introduced by linkedin corp, applied in recommendation scenario mostly.
Principal components analysis (PCA) is a well-known technique for approximating a tabular data set by a low ...fitting generalized low rank models, and describe implementations and numerical results. M.
Generalized Linear Models, Second Edition (Monographs on Statistics and Applied Probability) (Hardcover) by P. McCullagh P. McCullagh (Author) › Visit Amazon's P. McCullagh Page Find all the books, ...
Generalized rough sets based on relations
机器人广义逆的理论与应用
generalized linear model。
针对Generalized Benders Decomposition原始论文逐步进行推导,直到推导出Generalized Benders Decomposition的一般解法
Bollverslev, T. (1986). Generalized autoregressive conditional heteroskedasticity. Journal of Econometrics, 31 (3), 307–327 .
Structural Dynamic Analysis with Generalized Damping Models-Identification.pdf
Aleksandr V. Segal的论文Generalized-ICP。In this paper we combine the Iterative Closest Point (’ICP’) and ‘point-to-plane ICP‘ algorithms into a single probabilistic framework.
BlendedMVS - A Large-Scale Dataset for Generalized Multi-View St
Hastie的成名作,扩展的加性模型,从统计角度看待Adaboost。成书于1990年。 Hastie. Generalized Additive Models, Chapman and Hall, 1990.
作者:Vidal, René, Ma, Yi, Sastry, S.S. 2016年新书。据作者说:研究 unsupervised learning,从一百多年前的PCA讲到压缩感知,知识纵跨上百年。...而应用更涉及科学和工程各个领域,是数据科学的入门基础
Real-time object recognition using a modified generalized Hough transform
Generalized Least Squares -- good book for least squares