荒芜知地

Knowhere

0%

恐怖的宇宙射线

发表于 分类于 Valine：

可怕又恐怖的宇宙射线

问题描述

宇宙射线会在无限的二维平⾯上传播(可以看做⼀个二维网格图)，初始方向默认向上。宇宙射线会在发射出⼀段距离后分裂，向该⽅向的左右45°⽅向分裂出两条宇宙射线，同时威力不变！宇宙射线会分裂 n 次，每次分裂后会在分裂方向前进 ai 个单位长度。
求宇宙射线共经过多少个位置。

Input

输⼊第⼀行包含⼀个正整数n(n ≤ 30)，表示宇宙射线会分裂n次
第⼆行包含n个正整数a1, a2, ..., an，第i个数 表示第i次分裂的宇宙射线会在它原方向上继续走多少个单位长度。

Input

输出⼀个数ans，表示有多少个位置有射线经过。

Sample

input: 
4
4 2 2 3
output: 
39

input: 
15
1 2 3 4 5 5 4 3 2 1 1 2 3 4 5
output: 
6179

input: 
20
1 2 3 4 5 5 4 3 2 1 1 2 3 4 5 5 4 3 2 1
output: 
11404

input: 
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
output: 
43348

0002.png

Limitation

Time limit		1000 ms
Memory limit	262144 kB

数据范围

数据点 n
10% ≤10
40% ≤20
100% ≤30

解题思路

信息量挺大的，短时间内要理解题意，还要想出解题方法，还要写好代码，还要考虑MLE或者TLE去优化时间、空间复杂度，还要测试是否CE，还要自己出数据验证思路对不对……反正赛时那时间我没写出来，最后几分钟草草提交，结果CE了……赛后也是写了好久，一直卡在MLE on test 5……后来才对DFS优化剪枝，用优化前后的测试数据对比判断优化是否WA了……最后才AC……🤧

思路就是DFS，8种选择写的麻烦了一点，主要就是解题有许多坑啊……😖

分裂后的方向问题

每次分裂都会往左右45°产生2个方向，二维平面总共有8个方向，因此我对这些方向标号(见代码)，原方向与分裂后产生的方向(方向1、方向2，原方向的左侧优先)就有规律可循了，用2个函数就能求出方向1、方向2。

第几次分裂、前进长度问题

刚开始我的处理是对输出进行多次录入处理，比如原输入1 2 3 4，对应数组第0 1 2 3位，则对应产生的射线就是2i条(i 为数组下标)，则我在输入时对数组进行处理，数组元素就变成{ 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4 }。
可是后来剪枝优化的时候，发现比较难判断这是第几次分裂，况且n越大这个数组指数级变长……所以就要对当前是第几次大分裂进行标记，简单方法就是把这个第几次存入点dot的结构体中，每次要用的时候取出，每次分裂并前进结束后再对这个数+1就能清楚当前是第几次大分裂了。

标记到达的问题

我一开始的思路是，对于每个经过点，都pushback()到vector里面，然后对这个vector排序，for循环后算出有多少个重复点，再用size()减去重复数量就能求出有多少点……但是后面数据太大太多，明显会MLE且TLE，所以我考虑用reach数组标记到达的方法。
但是问题又来了，我一开始的起始点思维定式成(0, 0)，射线可以会经过x轴跟y轴的负数区间的，数组标记不了负的下标啊……后来想想，可以用一个四维数组reach[x][y][2][2]，第三维的2代表x的正负，第四维的2代表y的正负。但是……好麻烦，if又要写一大堆还容易出错😥。
后来观察图形，发现是关于y轴对称的，所以可以只记录x轴正半轴处的分裂，只记录y的正负，降维成三维数组，最终得到的点数目×2 - 处于y轴上的点就是结果了。但是，老是要考虑正负还是麻烦啊😒……
后来，后来，再后来……我观察了数据范围，发现它最长能达到的横坐标是 5 × 30 × 2 = 300 (每一大次分裂都走5步, 最多30次, 正负各一次)，纵坐标奕然，所以，把起点换成(150, 150)就不用考虑x, y的坐标正负问题了😀……
思维定式真的坑🕳啊……

如何剪枝的问题

每次分裂只考虑一个方向的话，8次后，方向就会绕回来了。所以那么多次分裂，很多步骤都是重复的。所以要用另一个数组标记，con[x][y][8][31]表示分裂起始点坐标，方向，第几次分裂(确定了第几次分裂就一定可以知道前进步数，所以不用再对步数进行标记到达)，这样就可以免去许多重复的步骤，优化复杂度。

源代码

AC代码

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

const int MAXREACH = 310;//最大300，大一点点以防万一

//x, y, direction, time
bool con[MAXREACH][MAXREACH][8][31] = { false };
bool reach[MAXREACH][MAXREACH] = { false };
		/*我根据产生方向的先后顺序标记的8个方向*/
/*↑: 1   ↖: 2   ↗: 3   ←: 4   →:5   ↙: 6   ↘: 7   ↓: 8*/
	/*north: 1;  northwest: 2;   northeast: 3;   west: 4;
	east: 5;   southwest: 6;   southeast: 7;   south: 8*/

struct dot {
	int x, y;
	int dir;
	int times;
	dot() {  }
	dot(int _x, int _y) : x(_x), y(_y) { dir = 0; times = 0; }
	dot(int _x, int _y, int d, int t) : x(_x), y(_y), dir(d), times(t) {  }
	bool operator<(const dot d)const {
		if (x == d.x)	return y < d.y;
		return x < d.x;
	}
	bool operator==(const dot d)const {
		return (x == d.x && y == d.y);
	}
};

int nextDir1(int d) {//往左45°产生的方向
	if (d == 1)	return 2;
	if (d == 2)	return 4;
	if (d == 3)	return 1;
	if (d == 4)	return 6;
	if (d == 5)	return 3;
	if (d == 6)	return 4;
	if (d == 7)	return 8;
	if (d == 8)	return 6;
}

int nextDir2(int d) {//往右45°产生的方向
	if (d == 1)	return 3;
	if (d == 2)	return 1;
	if (d == 3)	return 5;
	if (d == 4)	return 2;
	if (d == 5)	return 7;
	if (d == 6)	return 8;
	if (d == 7)	return 5;
	if (d == 8)	return 7;
}

dot genDot(dot s, int dir) {//每次走一步 产生下一个点
	dot e(s.x, s.y);
	if (dir == 1)	e.y += 1;//↑
	if (dir == 4)	e.x -= 1;//←
	if (dir == 5)	e.x += 1;//→
	if (dir == 8)	e.y -= 1;//↓
	if (dir == 2) { e.x -= 1; e.y += 1; }//↖
	if (dir == 3) { e.x += 1; e.y += 1; }//↗
	if (dir == 6) { e.x -= 1; e.y -= 1; }//↙
	if (dir == 7) { e.x += 1; e.y -= 1; }//↘
	return e;
}

int main() {
	int n;
	cin >> n;
	int* step = new int[n + 10];
	for (int i = 0; i < n; i++)
		cin >> step[i];
	dot s(152, 152, 1, 0);//以防万一 起点变成(152, 152) 方向1 第0次分裂

	queue<dot> q;
	q.push(s);

	int reachCount = 0;//记录到达过多少个位置
	int times = 0;//记录第几次大分裂
	while (!q.empty()) {
		dot cur = q.front();//当前点
		q.pop();
		int dir = cur.dir;//当前方向
		times = cur.times;//当前是第几次大分裂
		if (con[cur.x][cur.y][dir - 1][times] == true)//如果这次分裂重复来过了
			continue;//不用管这一次了 继续下一个循环
		con[cur.x][cur.y][dir-1][times] = true;//没来过 标记true
		
		for (int i = 0; i != step[times]; i++) {//走几步
			dot temp = genDot(cur, dir);//产生下一个点
			cur = temp;
			int ca = cur.x, cb = cur.y;
			
			if (reach[ca][cb] == false) {//标记到达
				reach[ca][cb] = true;
				reachCount++;//计数
			}
		}

		if (times < n - 1) {//还没到最后一次的大分裂 可入队
			int a = cur.x, b = cur.y;
			dot cur1(a, b, nextDir1(dir), times + 1);
			dot cur2(a, b, nextDir2(dir), times + 1);
            //2个方向 入队
			q.push(cur1);
			q.push(cur2);
		}
	}
	cout << reachCount << endl;
	return 0;
}

MLE暴力代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;

struct dot {
	int x, y;
	int dir;
	dot() {  }
	dot(int _x, int _y) : x(_x), y(_y) { dir = 0; }
	dot(int _x, int _y, int d) : x(_x), y(_y), dir(d){  }
	bool operator<(const dot d)const {
		if (x == d.x)	return y < d.y;
		return x < d.x;
	}
	bool operator==(const dot d)const {
		return (x == d.x && y == d.y);
	}
};

int nextDir1(int d) {
	if (d == 1)	return 2;
	if (d == 2)	return 4;
	if (d == 3)	return 1;
	if (d == 4)	return 6;
	if (d == 5)	return 3;
	if (d == 6)	return 4;
	if (d == 7)	return 8;
	if (d == 8)	return 6;
}

int nextDir2(int d) {
	if (d == 1)	return 3;
	if (d == 2)	return 1;
	if (d == 3)	return 5;
	if (d == 4)	return 2;
	if (d == 5)	return 7;
	if (d == 6)	return 8;
	if (d == 7)	return 5;
	if (d == 8)	return 7;
}

dot genDot(dot s, int dir) {
	dot e(s.x, s.y);
	if (dir == 1)	e.y += 1;//↑
	if (dir == 4)	e.x -= 1;//←
	if (dir == 5)	e.x += 1;//→
	if (dir == 8)	e.y -= 1;//↓
	if (dir == 2) { e.x -= 1; e.y += 1; }//↖
	if (dir == 3) { e.x += 1; e.y += 1; }//↗
	if (dir == 6) { e.x -= 1; e.y -= 1; }//↙
	if (dir == 7) { e.x += 1; e.y -= 1; }//↘
	return e;
}

int main() {
	int n;
	cin >> n;

	vector<int> step;
	for (int i = 0; i < n; i++) {
		int sx;
		cin >> sx;
		double stimes = pow(2, i);
		for (double j = 0; j != stimes; j++)
			step.push_back(sx);
	}

	dot s(0, 0, 1);
	vector<dot> path;

	queue<dot> q;
	q.push(s);
	int times = 0;
	while (!q.empty()) {
		dot cur = q.front();
		q.pop();
		int dir = cur.dir;
		for (int i = 0; i != step[times]; i++) {
			dot temp = genDot(cur, dir);
			path.push_back(temp);
			cur = temp;
		}
		times++;
		int a = cur.x, b = cur.y;
		dot cur1(a, b, nextDir1(dir));
		dot cur2(a, b, nextDir2(dir));
		q.push(cur1);
		q.push(cur2);
		if (times == step.size())
			break;
	}
	sort(path.begin(), path.end());
	int psize = path.size();
	int sameCount = 0;
	for(int i=0;i!=psize-1;i++)
		if (path[i] == path[i + 1])
			sameCount++;
	cout << psize - sameCount << endl;
	return 0;
}