#洛谷P1058 立体图

非常标准的一道思考题。

题目描述

小渊是个聪明的孩子,他经常会给周围的小朋友们将写自己认为有趣的内容。最近,他准备给小朋友们讲解立体图,请你帮他画出立体图。

小渊有一块面积为m*n的矩形区域,上面有m*n个边长为1的格子,每个格子上堆了一些同样大小的积木(积木的长宽高都是1),小渊想请你打印出这些格子的立体图。我们定义每个积木为如下格式,并且不会做任何翻转旋转,只会严格以这一种形式摆放:

每个顶点用1个加号’+’表示,长用3个”-”表示,宽用1个”/”,高用两个”|”表示。字符’+’,”-”,”/”,”|”的ASCII码分别为43,45,47,124。字符’.’(ASCII码46)需要作为背景输出,即立体图里的空白部分需要用’.’来代替。立体图的画法如下面的规则:

若两块积木左右相邻,图示为:

若两块积木上下相邻,图示为:

若两块积木前后相邻,图示为:

立体图中,定义位于第(m,1)的格子(即第m行第1列的格子)上面自底向上的第一块积木(即最下面的一块积木)的左下角顶点为整张图最左下角的点。

这题不需要一定立体几何的分析。

我们都知道透视是什么。透视让你通过二维屏幕yy出三维空间 什么xjb玩意儿。

也就是说,你如果从右前上方看的话(题目方向),右面的(离你近的)会盖住左面的(离你远的),同理高的盖住低的,前面的盖住后面的。

那么可以遵循自底向上,自后向前,自左向右的绘画准则,在虚拟画布mapx[1010][1010]上面打表(数据范围我乱写的)

1.注意横坐标上限只与从顶上看的矩阵大小有关,但是纵坐标上限还与高度以及从顶上看的矩阵长度(矩阵纵坐标最大值)有关

社会我C哥,人狠话不多,不管那么多。

直接倒着填,右下角基准点,初始化为’.’ , 最后统计上限。

将每个block右下角作为basic point基准点,推一下公式。具体怎么来的,不作解释。

然后打个表。打表还不简单。

#洛谷 P1066 2^k进制数

题目描述

设r是个2^k 进制数,并满足以下条件:

(1)r至少是个2位的2^k 进制数。

(2)作为2^k 进制数,除最后一位外,r的每一位严格小于它右边相邻的那一位。

(3)将r转换为2进制数q后,则q的总位数不超过w。

在这里,正整数k(1≤k≤9)和w(k<W< span>≤30000)是事先给定的。

问:满足上述条件的不同的r共有多少个?

我们再从另一角度作些解释:设S是长度为w 的01字符串(即字符串S由w个“0”或“1”组成),S对应于上述条件(3)中的q。将S从右起划分为若干个长度为k 的段,每段对应一位2^k进制的数,如果S至少可分成2段,则S所对应的二进制数又可以转换为上述的2^k 进制数r。

例:设k=3,w=7。则r是个八进制数(23=8)。由于w=7,长度为7的01字符串按3位一段分,可分为3段(即1,3,3,左边第一段只有一个二进制位),则满足条件的八进制数有:

2位数:高位为1:6个(即12,13,14,15,16,17),高位为2:5个,…,高位为6:1个(即67)。共6+5+…+1=21个。

3位数:高位只能是1,第2位为2:5个(即123,124,125,126,127),第2位为3:4个,…,第2位为6:1个(即167)。共5+4+…+1=15个。

所以,满足要求的r共有36个。

输入输出格式

输入格式:

输入只有1行,为两个正整数,用一个空格隔开:

k W

输出格式:

输出为1行,是一个正整数,为所求的计算结果,即满足条件的不同的r的个数(用十进制数表示),要求最高位不得为0,各数字之间不得插入数字以外的其他字符(例如空格、换行符、逗号等)。

(提示:作为结果的正整数可能很大,但不会超过200位)

上来给了题解了,好贴心QAQ

第一要用高精度

第二,让你构造一个2k进制的,w/k位的(w的划分残余不考虑)数,且左面一位严格小于右面一位。

我们考虑递推,可以先打一个表

那么设p[i][j]表示从右向左数i位,最高位(最左面)的数最小为j , 可以构成的2k进制数的个数。 (最高位不为0)

那么,有两种转移。一是添加这个最小的数j,那从p[i-1][j+1]转移 (后面i-1位最小取j+1,由此计算可以构成的2k进制数的个数)

二是最高位数字比j大,从p[i][j+1]转移。

那么,看这个

考虑样例k=3 , w=7 的情况,串w肯定不能被完全分割,所以剩下一位,可以取0 ~ 2w%k -1 这样。

那就统计一发答案,最高位取i的时候需要的答案是p[w/k][i+1]这是肯定的。

然后考虑不完全取,ans+= ∑ p[i][1] (2<=i<=w/k)

但是,我们再来考虑这个样例:

k=2,w=8  这四位并不能完全用完。

那么显然最多可以有2k-1位。 (e.g. 当k=2时,位数最多时的方案是123,不存在1234或234或345等等,当k=3时,位数最多时的方案是1234567),也就是说,只需要加一下1~2k-1位的方案p[位数][1]就可以了。

那么就来推一波

然后写一个重载运算符的BNUM类

然后就行了,这是所有代码,注意readint

 

IOI1998 Starry Night 夜空繁星

BFS,超级麻烦

推荐A这道模拟方块转换

高高的星空,簇簇闪耀的群星形态万千。一个星座(cluster)是一群连通的星组成的非空连通星系,这里的连通是指水平,垂直或者对角相邻的两个星星。一个星座不能是另一个更大星座的一部分, 星座可以相似(similar)。如果两个星座有相同的形状,而且包括相同数目的星体,那么不管其方向性如何,就算相似。一般而言,星座可能的方向有八个,如图所示。(图片搬运自Luogu Online Judge)

 

 

懒癌了,我就贴上来吧……我用了一个特殊的表来判断是不是相似

详见代码