nyoj1278 zzuli1929 Prototypes analyze(河南省acm第九届省赛)

本文主要是介绍nyoj1278 zzuli1929 Prototypes analyze(河南省acm第九届省赛),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Prototypes analyze
时间限制:1000 ms | 内存限制:65535 KB
难度:2
描述
ALpha Ceiling Manufacturers (ACM) is analyzing the properties of its new series of Incredibly Collapse-Proof Ceilings (ICPCs). An ICPC consists of n layers of material, each with a different value of collapse resistance (measured as a positive integer). The analysis ACM wants to run will take the collapse-resistance values of the layers, store them in a binary search tree, and check whether the shape of this tree in any way correlates with the quality of the whole construction. Because, well, why should it not? To be precise, ACM takes the collapse-resistance values for the layers, ordered from the top layer to the bottom layer, and inserts them one-by-one into a tree. The rules for inserting a value v are:

• If the tree is empty, make v the root of the tree.

• If the tree is not empty, compare v with the root of the tree.

• If v is smaller, insert v into the left subtree of the root,

• otherwise insert v into the right subtree.

ACM has a set of ceiling prototypes it wants to analyze by trying to collapse them. It wants to take each group of ceiling prototypes that have trees of the same shape and analyze them together. For example , assume ACM is considering five ceiling prototypes with three layers each, as described by Sample Input 1 and shown in Figure C.1. Notice that the first prototype’s top layer has collapseresistance value 2, the middle layer has value 7, and the bottom layer has value 1. The second prototype has layers with collapse-resistance values of 3, 1, and 4 – and yet these two prototypes induce the same tree shape, so ACM will analyze them together. Given a set of prototypes, your task is to determine how many different tree shapes they induce.

这里写图片描述

输入
The first line of the input contains one integers T, which is the nember of test cases (1<=T<=8).
Each test case specifies :
● Line 1: two integers n (1 ≤ n ≤ 50), which is the number of ceiling prototypes to analyze,
and k (1 ≤ k ≤ 20), which is the number of layers in each of the prototypes.
● The next n lines describe the ceiling prototypes. Each of these lines contains k distinct
integers ( between 1 and 1e6, inclusive ) , which are the collapse-resistance values of the
layers in a ceiling prototype, ordered from top to bottom.
输出
For each test case generate a single line containing a single integer that is the number of different tree
shapes.
样例输入
1
5 3
2 7 1
1 5 9
3 1 4
2 6 5
9 7 3
样例输出
4
题意就是根据输入给的数字,判断有多少种二叉树结构。
例如2 7 1,2首先放在根节点,然后7比2大放在根节点右边(右子树),1比7小 放在跟节点左边(左子树) 依次类推。如果是2 7 1 5,在放完1后 5比2大应该放在2的右边(右子树),可是2的右边已经有7,5和7比较,5比7小,放在7的左边。~

根据题意建二叉树即可。
难点在于如何分辨有多少子树。
在这里我通过遍历二叉树来分辨。如果某个节点有值置为1,否则置为0.最后将这些0 1 串放入set集合,输出set大小即可。

#include <stdio.h>
#include <set>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <string.h>
using namespace std;
int tree[1100000];
int pos;
//建二叉树 
void build(int root,int x)
{if(tree[root]==0){//pos 表示当树的最远叶子节点的标号 pos=max(pos,root);tree[root]=x;return ;}else {if(x<tree[root])build(root*2,x);elsebuild(root*2+1,x);}
}
int main()
{int n,k,t;scanf("%d",&t);while(t--){scanf("%d %d",&n,&k);set<string>s;s.clear();while(n--){memset(tree,0,sizeof(tree));pos=0;for(int i=0;i<k;i++){int x;scanf("%d",&x);build(1,x);}//  printf("pos=%d\n",pos);string temp="";for(int i=1;i<=pos;i++){if(tree[i]) temp.append("1");else temp.append("0");}//  cout<<temp<<endl;s.insert(temp);}printf("%d\n",s.size());}
}

这篇关于nyoj1278 zzuli1929 Prototypes analyze(河南省acm第九届省赛)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/694631

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

rtklib.h : RTKLIB constants, types and function prototypes 解释

在 RTKLIB 中,rtklib.h 是一个头文件,包含了与 RTKLIB 相关的常量、类型和函数原型。以下是该头文件的一些常见内容和翻译说明: 1. 常量 (Constants) rtklib.h 中定义的常量通常包括: 系统常量: 例如,GPS、GLONASS、GALILEO 等系统的常量定义。 时间常量: 如一年、一天的秒数等。 精度常量: 如距离、速度的精度标准。 2. 类型

【转载】ACM感悟

今天看了一篇我们学校前辈的ACM的感悟,觉得写的十分有道理,这里转载,文章还会不断的改进和更新。 原文链接:http://www.cnblogs.com/Chierush/p/3760870.html?ADUIN=1339764596&ADSESSION=1401536826&ADTAG=CLIENT.QQ.5329_.0&ADPUBNO=26349 声明:本文是写给弱校ACM新手的一点

我们依旧在追梦的路上-山东省第六届ACM比赛总结

这场比赛从结果而言达到了预期(金牌),从过程而言和我的预期相差甚远(打的太乱,个人发挥很差),还好关键时刻队友抗住压力,负责后果真的不堪设想。 热身赛 热身赛纯粹测机器的,先把A,B,C草草水过(A题小写x打成大写的也是醉了),我和老高开始各种测机器,long long不出所料是lld的,试了一下除0和数组越界的re问题,发现没有re,只有wa(甚至数组越界还AC了),至于栈深的话也没过多追

ACM东北地区程序设计大赛

不得不说随着参赛级别的提高,题目真的是越来越难啊,不过队长真是给力啊,在我们三个共同努力之下拿下了地区赛三等奖,哈哈我们可是大一唯一一只获奖队,终于在这次比赛打败了田大神。。。大神是失手了,俺和他差距还是挺大的。。。队友陈彤马上要去服兵役了,他说这是我们送给他最好的离别礼物,希望那家伙在部队好好干,以后谁干揍我!!!东北地区赛结束后,今年已经估计没机会参加亚洲区比赛了,赶紧补高数和线数啊!!别挂了

ACM比赛中如何加速c++的输入输出?如何使cin速度与scanf速度相当?什么是最快的输入输出方法?

在竞赛中,遇到大数据时,往往读文件成了程序运行速度的瓶颈,需要更快的读取方式。相信几乎所有的C++学习者都在cin机器缓慢的速度上栽过跟头,于是从此以后发誓不用cin读数据。还有人说Pascal的read语句的速度是C/C++中scanf比不上的,C++选手只能干着急。难道C++真的低Pascal一等吗?答案是不言而喻的。一个进阶的方法是把数据一下子读进来,然后再转化字符串,这种方法传说中

2014年ACM/ICPC亚洲区现场赛广州赛区总结

本来不想提这件事的,后来学姐找我谈心时提到这件事,我突然意识到在这件事情上我错了一次,明明答应的去参加这场比赛,最后临时决定不去......其实中间有很多很多原因 1:我和tyh,sxk临时不去主要是广州太远,我们身上money不够,呵呵。。。别笑我们,你以为我们是高富帅啊,去一趟广州消费要2个月的生活费,奖学金又没发,你让我找我妈要她辛辛苦苦挣来的工资吗?!从哈尔滨到广州单来回的火车票每个人就

Open Source, Open Life 第九届中国开源年会论坛征集正式启动

中国开源年会 COSCon 是业界最具影响力的开源盛会之一,由开源社在2015年首次发起,而今年我们将迎来第九届 COSCon! 以其独特定位及日益增加的影响力,COSCon 吸引了越来越多的国内外企业、高校、开源组织/社区的大力支持。与一般企业、IT 媒体、行业协会举办的行业大会不同,COSCon 具有跨组织、跨项目、跨社区的广泛覆盖面,也吸引了众多国内外开源开发者和开源爱好者的关注及参与

找不同-第15届蓝桥省赛Scratch初级组真题第4题

[导读]:超平老师的《Scratch蓝桥杯真题解析100讲》已经全部完成,后续会不定期解读蓝桥杯真题,这是Scratch蓝桥杯真题解析第183讲。 如果想持续关注Scratch蓝桥真题解读,可以点击《Scratch蓝桥杯历年真题》并订阅合集,查阅教程更方便。 第15届蓝桥杯省赛已于2024年8月24日落下帷幕,编程题一共有5题,分别如下: 猪八戒落地 游乐场 画西瓜 找不同 消

第十五届蓝桥杯图形化省赛题目及解析

第十五届蓝桥杯图形化省赛题目及解析 一. 单选题 1. 运行以下程序,角色会说( )? A、29     B、31     C、33     D、35 正确答案:C 答案解析: 重复执行直到m>n不成立,即重复执行直到m<=n。所有当m小于或者 等于n时,循环结束。循环过程中变量m与变量n的变化如下表: 通过上述表格可知,循环到第五次循环结束。m的值为14,n的值为19