(2/3/4)-D Sqr/Rects/Cubes/Boxes?

2024-08-22 14:38
文章标签 boxes sqr cubes rects

本文主要是介绍(2/3/4)-D Sqr/Rects/Cubes/Boxes?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description

Problem J

(2/3/4)-D Sqr/Rects/Cubes/Boxes?

Input: standard input

Output: standard output

Time Limit: 2 seconds

     

You can see a (4x4) grid below. Can you tell me how many squares and rectangles are hidden there? You can assume that squares are not rectangles. Perhaps one can count it by hand but can you count it for a (100x100) grid or a (10000x10000) grid. Can you do it for higher dimensions? That is can you count how many cubes or boxes of different size are there in a (10x10x10) sized cube or how many hyper-cubes or hyper-boxes of different size are there in a four-dimensional (5x5x5x5) sized hypercube. Remember that your program needs to be very efficient. You can assume that squares are not rectangles, cubes are not boxes and hyper-cubes are not hyper-boxes. 

     

Fig: A 4x4 Grid

Fig: A 4x4x4 Cube

     

       

Input

The input contains one integer N (0<=N<=100) in each line, which is the length of one side of the grid or cube or hypercube. As for the example above the value of N is 4. There may be as many as 100 lines of input.

 

Output

For each line of input, output six integers S2, R2, S3, R3, S4, R4 in a single line where S2 means no of squares of different size in ( NxN) two-dimensional grid, R2 means no of rectangles of different size in (NxN) two-dimensional grid. S3, R3, S4, R4 means similar cases in higher dimensions as described before.  

       

Sample Input:

1
2
3

Sample Output:

1 0 1 0 1 0
5 4 9 18 17 64
14 22 36 180 98 1198

Shahriar Manzoor


二维三维还是可以算的,四维算个毛,想都想不出来别说画了,明显是个找规律的题目啊,
尽管我没有找到一个可以计算的公式,但是既然是个规律题,可以在二维找规律,在三维试验,最后应用于四维,话说一路很风顺,规律找的很轻松,可是写出来也太恐怖了吧;
代码如下:
#include <stdio.h>int main()
{long long s2,r2,s3,r3,s4,r4;long long ssum,rsum;int n;int l1,l2,l3,l4;int i,k,j,h;while (~scanf ("%d",&n)){ssum = 0;for (i = 1;i <= n;i++){l1 = n - i + 1;ssum += l1 * l1;}rsum = 0;for (i = 1; i <= n; i++)for (k = 1; k <= n; k++){l1 = n - i + 1;l2 = n - k + 1;rsum += l1 * l2;}s2 = ssum;r2 = rsum - ssum;ssum = 0;for (i = 1;i <= n;i++){l1 = n - i + 1;ssum += l1 * l1 * l1;}rsum = 0;for (i = 1;i <=n;i++)for (k = 1;k <= n;k++)for (j = 1;j <= n;j++){l1 = n - i + 1;l2 = n - k + 1;l3 = n - j + 1;rsum += l1 * l2 * l3;}s3 = ssum;r3 = rsum - ssum;ssum = 0;for (i = 1;i <= n;i++){l1 = n - i + 1;ssum += l1 * l1 * l1 * l1;}rsum = 0;for (i = 1;i <= n;i++)for (k = 1;k <= n;k++)for (j = 1;j <= n;j++)for (h = 1;h <= n;h++){l1 = n - i + 1;l2 = n - k + 1;l3 = n - j + 1;l4 = n - h + 1;rsum += l1 * l2 * l3 *l4;}s4 = ssum;r4 = rsum - ssum;printf ("%lld %lld %lld %lld %lld %lld\n",s2,r2,s3,r3,s4,r4);}return 0;
}

在写的时候就担心TLE,果然,不粗所料,TLE,见红了。
其实我实在不想放弃这个类似穷举的笨重算法,因为我现在还真没有什么好的方法,so,我把精力放在优化代码上
我发现我时间浪费在循环上,各种循环,n的上限是100 。最后一个循环可以执行100 * 100 * 100 * 100次,我去太恐怖了
看到自己的代码有个式子在不短重复 【n-自变量+1】,随着嵌套增多这个也在多
想到第一只学长曾经讲过的时间复杂度,并说调用比计算省时间,于是我打算把节省时间重点放在这个式子上,于是我改进了代码如下:
#include <stdio.h>int an[102];int main()
{long long s2,r2,s3,r3,s4,r4;long long ssum,rsum;int n;int l1,l2,l3,l4;int i,k,j,h;freopen ("1.txt","r",stdin);while (~scanf ("%d",&n)){for (i = 1;i <= n;i++)an[i] = n - i + 1;ssum = 0;for (i = 1;i <= n;i++){l1 = an[i];ssum += l1 * l1;}rsum = 0;for (i = 1; i <= n; i++)for (k = 1; k <= n; k++){l1 = an[i];l2 = an[k];rsum += l1 * l2;}s2 = ssum;r2 = rsum - ssum;ssum = 0;for (i = 1;i <= n;i++){l1 = an[i];ssum += l1 * l1 * l1;}rsum = 0;for (i = 1;i <=n;i++)for (k = 1;k <= n;k++)for (j = 1;j <= n;j++){l1 = an[i];l2 = an[k];l3 = an[j];rsum += l1 * l2 * l3;}s3 = ssum;r3 = rsum - ssum;ssum = 0;for (i = 1;i <= n;i++){l1 = an[i];ssum += l1 * l1 * l1 * l1;}rsum = 0;for (i = 1;i <= n;i++)for (k = 1;k <= n;k++)for (j = 1;j <= n;j++)for (h = 1;h <= n;h++){l1 = an[i];l2 = an[k];l3 = an[j];l4 = an[h];rsum += l1 * l2 * l3 *l4;}s4 = ssum;r4 = rsum - ssum;printf ("%lld %lld %lld %lld %lld %lld\n",s2,r2,s3,r3,s4,r4);}return 0;
}

居然AC了,其实时间和内存还是很恐怖的

事实证明,这样时间还是很悬的,但是也同样证明,这样的确可以缩短时间。

 

 

这篇关于(2/3/4)-D Sqr/Rects/Cubes/Boxes?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

【CF】E. Anya and Cubes(双向DFS)

根据题意的话每次递归分3种情况 一共最多25个数,时间复杂度为3^25,太大了 我们可以分2次求解第一次求一半的结果,也就是25/2 = 12,记录结果 之后利用剩余的一半求结果 s-结果 = 之前记录过的结果 就可以 时间复杂度降低为 3 ^ (n/2+1) 题目链接:http://codeforces.com/contest/525/problem/E #include<set

Marching Cubes 算法再探

Marching Cubes 算法再探 基础过程代码mian.cppMarchingCubes.hMarchingCubes.cpp 之前做NeRF相关工作时简单看过,但没有深究其实现,知其然不知其所以然的程度,算是初探。 基础 为了对MC有大致了解,可以先根据Marching Cubes 算法初探,理解一下Marching Cubes这个名字的由来,其二维空间中的示例

Codeforces Round #295 (Div. 1) B. Cubes (STL+类拓扑)

最近课业繁重,这题写了两天。。昨晚睡觉的时候才突然想到了最后一点的解决方法。 不知道该不该叫做拓扑。。感觉还是挺像的。。就把标题称之为类拓扑了。。这题的方法是用map来标记状态是否存在,然后用类似拓扑的方法不断的找拿走后依然稳定的方块,我用了两个优先队列来维护,分别取最大和最小。然后就是模拟这个过程取方块了。 代码如下: #include <iostream>#include <stri

UVA 103--- Stacking Boxes

这道题在小白书中的分类是动态规划,把题AC了之后在网上看解题报告后,多数解法也是DAG上的动态规划。但其实一个简单的深度优先就能解决问题了。首先将每数从大到小排序,再将各组按照排序后的第一个数字的大小进行从大到小排序。需要注意的是,记录各组数据的编号也要和数进行同步的排序。 #include <iostream>#include <cstdio>#include <vect

UVA12657 Boxes in a Line【双向链表】【数组模拟】

You have n boxes in a line on the table numbered 1 . . . n from left to right. Your task is to simulate 4 kinds of commands: • 1 X Y : move box X to the left to Y (ignore this if X is already

marching cubes表面重建原理

Marching Cubes算法是三维离散数据场中提取等值面的经典算法,之前主要应用于医学图像重建,当前在TSDF等重建场景广泛应用。 参考论文:Marching Cubes: A High Resolution 3D Surface Construction Algorithm 参考论文: KinectFusion: real-time dynamic 3D surface reconstruc

UVA - 103 Stacking Boxes

题意:n维向量,如果向量A,B每一位上的数A都比B大,则A可以嵌套住B,求最大的嵌套个数,并输出依次是第几个。 思路:构成一个有向图DAG,如果X可以嵌套在Y里,那么X到Y就有一个有向边,最后就是求DAG上的最长路径 #include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using names

UVA 10177 (2/3/4)-D Sqr/Rects/Cubes/Boxes

(2/3/4)-D Sqr/Rects/Cubes/Boxes? Input: standard input Output: standard output Time Limit: 2 seconds   You can see a (4x4) grid below. Can you tell me how many squares and rectangles are hidden

10601 - Cubes(Ploya)

UVA 10601 - Cubes 题目链接 题意:给定正方体12条棱的颜色,要求用这些棱能组成多少不同的正方体 思路:利用ploya定理去求解,分类讨论,正方体一共24种旋转,对应的旋转方式有4种: 1、不动 2、沿两面中点连线旋转 3、沿对顶点连线旋转 4、沿两棱中点连线旋转 简单推算出每种情况对应的循环组数,在加上组合数学去进行选择颜色求解,注意第4种情况中,有两条棱和其他

tf.image.draw_bounding_boxes

____tz_zs 在一批图像上绘制边框。 . draw_bounding_boxes(images,boxes,name=None) . images:是 [batch, height, width, depth] 形状的四维矩阵,数据类型为 float32、half 中的一种,第一个值batch是因为处理的是一组图片。 boxes: 形状 [batch, num_boundi