CSP-M1 补题 C - 可怕的宇宙射线 Gym - 270437F

时间与内存限制

每个测试点 1000ms 262144KB

题目描述

众所周知，瑞神已经达到了CS本科生的天花板，但殊不知天外有天，人外有苟。在浩瀚的宇宙中，存在着一种叫做苟狗的生物，这种生物天生就能达到人类研究生的知识水平，并且天生擅长CSP，甚至有全国第一的水平！但最可怕的是，它可以发出宇宙射线！宇宙射线可以摧毁人的智商，进行降智打击！
宇宙射线会在无限的二维平面上传播（可以看做一个二维网格图），初始方向默认向上。宇宙射线会在发射出一段距离后分裂，向该方向的左右45°方向分裂出两条宇宙射线，同时威力不变！宇宙射线会分裂 次，每次分裂后会在分裂方向前进 个单位长度。
现在瑞神要带着他的小弟们挑战苟狗，但是瑞神不想让自己的智商降到普通本科生 那么菜的水平，所以瑞神来请求你帮他计算出共有多少个位置会被"降智打击

输入描述

输入第一行包含一个正整数 ，表示宇宙射线会分裂 次
第二行包含n个正整数 ，第 个数 表示第 次分裂的宇宙射线会在它原方向上继续走多少个单位长度。
输出描述
输出一个数 ，表示有多少个位置会被降智打击

样例

30
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 54334828
5 5 1 1 1 1 2 1 1 2 2 5 5 5 4 3 5 4 3 5 4 3 3 5 5 4 1 1 2 3 52218827
5 5 1 1 1 1 2 1 1 2 2 5 5 5 4 3 5 4 3 5 4 3 3 5 5 4 1 1 221871

数据点说明

数据点 n 10% <=10 40% <=20 100% <=30

样例解释

下图描绘了样例中宇宙射线分裂的全过程，仅做参考（如加载缓慢请耐心等待）

解题思路

暴力算法时间复杂度要2^30，在1s内较难完成，怎么优化都是超时的
。因此我们可以只用递归算出一种可能，按顺序标记在这次递归中的点。然后从终点开始，在每一次分裂点处求处在分裂点后产生的点关于分裂点的对称点，从而组成对称的图形。

我们从最后一次分裂产生的点开始根据分裂对称方向求对称点，求完当前分裂点的对称点，返回到上一个交叉点之前，将在这个步骤中在地图上标记的点加入队列中，并在地图中标出。list l1 中按顺序存储从分裂开始到结束标记的点，而 list l2 中存储的则是从分裂结束开始往起点求对称点过程中，图中标记的点。虽然这种方法比较麻烦，在 n<=30 时可以控制在几十毫秒以内。

程序源码

#include<iostream>
#include<stdio.h>
#include<list>using namespace std;
int n;
int px[] = { -1,-1,0,1,1,1,0,-1 }; //x轴偏移 
int py[] = { 0,1,1,1,0,-1,-1,-1 }; //y轴偏移 
bool m[3200][3200] = { 0 };
int l[30];
list<point> l1; //从开始到结束标记的点 
list<point> l2; //从结束到开始标记的点 struct point { //点结构体 int x;int y;point(int xx, int yy) :x(xx), y(yy) {}
};void dfs(int x, int y, int lv, int posi) {int steps = l[lv];point* newp;for (int i = 0; i < steps; i++) { //将当前层次要标记的点存入 l1 中 x = x + px[posi]