9.9笔试题
body
本题运行时间较长，建议使用C++、Go或者Java完成
艾文是一个居住在须弥城的孩子，原本活泼开朗，但因为伤病，无法远行。她有一个梦想，希望能够看到一场烟花表演。然而，由于须弥城是在雨林中建设的城市，为了防止火灾，城市规定不能燃放烟花。
幸运的是，附近的森林中有一群小精灵，它们被称为“兰那罗”。这些小精灵具有特殊的能力，可以让人们进入梦境中。当听说了艾文的梦想后，兰那罗决定帮助他实现愿望。
兰那罗通过让艾文进入梦境，在梦境中给他展示了一场华丽绚烂的烟花表演。艾文在梦境中感受到了烟花的美丽和绚烂。
兰那罗的梦境空间可看作一个无限大的二维网格（光栅），其中有一种二维绽放的烟花。这种烟花的行为可以用绽放总轮次n和每轮绽放深度t₁,t₂,...,tₙ来描述。一旦该烟花在二维网格的某个单元中发射，烟花就会开始向上移动。在经过t₁个单元（包括起始单元）后，它会爆炸并分裂成两个部件，每个部件都朝改变 45 度的方向移动（具体可参考最后的例子），即，一个部件沿左上方向移动，而另一个部件沿右上方向移动。每个部件在经过t₂个单元后再次爆炸，分裂成两个部件，移动方向再次改变 45 度。这个过程一直持续到第n级绽放，此时所有2^(n-1)个现有部件都会爆炸并消失，而不会创建新的部件。在整个过程中，某些部件可能会同时位于同一位置————这是允许的，并且各自按自己的规则独立运动而不会提前毁坏。
在发射一束烟花前，你能帮兰那罗计算出它会经过二维网格中多少个单元吗（同一个单元只计算一次）。
input format
第1行包括一个整数n (1≤n≤25)————绽放总轮次n
第2行包含n个整数t₁,t₂,...,tₙ(1≤tᵢ≤5)。在第i轮绽放的2^(i-1)个部件会经过的单元数量。
out format
打印一个整数，表示烟花至少经过一次的网格单元的数量。
sample input 1
4
4 2 2 3
sample output 1
39
sample input 2
6
1 1 1 1 1 3
sample output 2
85
hint
在第一个例子中，烟花的轨迹如下（数字表示绽放的轮次）：
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |4| | | |4| |4| | | |4| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |4| | | |4| | | |4| | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |4| | | |4| |4| |4| |4| | | |4| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |4| | | |3| | | |3| | | |4| | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |4| | |3| | | |3| | |4| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |3|3|2| | | |2|3|3| | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |4| | | |2| |2| | | |4| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |4| | | | | |1| | | | | |4| | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |4| | | | | | |1| | | | | | |4| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | |1| | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | |1| | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
在第2个例子里，第4、5、6轮绽放结束时烟花已经经过的轨迹分别如下：
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | |4| |4| |4| | |
+-+-+-+-+-+-+-+-+-+
| |4| |3| |3| |4| |
+-+-+-+-+-+-+-+-+-+
| | |3|2| |2|3| | |
+-+-+-+-+-+-+-+-+-+
| |4| | |1| | |4| |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+
| | | |5| |5| |5| | | |
+-+-+-+-+-+-+-+-+-+-+-+
| | |5|4|5|4|5|4|5| | |
+-+-+-+-+-+-+-+-+-+-+-+
| |5|4| |3| |3| |4|5| |
+-+-+-+-+-+-+-+-+-+-+-+
| | | |3|2| |2|3| | | |
+-+-+-+-+-+-+-+-+-+-+-+
| |5|4| | |1| | |4|5| |
+-+-+-+-+-+-+-+-+-+-+-+
| | |5| | | | | |5| | |
+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |6| |6| |6| |6| |6| |6| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |6| |6| |6| |6| |6| |6| |6| | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |6| |6| |6| |6| |6| |6| |6| |6| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |6| |6| |6| |5| |6| |6| |6| | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |6| |6| |5|4|5|4|5|4|5| |6| |6| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |6| |6|4|6|3| |3|6|4|5| |6| | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |6| |6|3|2| |2|3|6| |6| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |6| |6|4| | |1| | |4|5| |6| | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |6| |6| |5| | | | | |5| |6| |6| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |6| |6| |6| | | |6| |6| |6| | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |6| |6| | | |6| |6| | | |6| |6| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |6| | | | | |6| | | | | |6| | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
AC代码(大概？)：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define mod 1000000007
#define pb push_back
typedef pair<int,int> pir;
string sstr[]={"NO\n","YES\n"};
const int N=500010;
struct point
{
int x,y,d;
bool operator<(point p1)const{
if(x!=p1.x) return x<p1.x;
else if(y!=p1.y) return y<p1.y;
else return d<p1.d;
}
};
int T,n,m;
set<point> s1,s2;
int vis[5010][5010];
int t[100];
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};
void solve(int t)
{
s2.clear();
for(auto it:s1){
for(int i=1;i<=t;i++){
it.x+=dx[it.d];
it.y+=dy[it.d];
vis[it.x][it.y]=1;
}
s2.insert(point{it.x,it.y,(it.d+1)%8});
s2.insert(point{it.x,it.y,(it.d-1+8)%8});
}
s1=s2;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>t[i];
s1.insert(point{2500,2500,0});
for(int i=1;i<=n;i++){
solve(t[i]);
}
int ans=0;
for(int i=1;i<=5000;i++) for(int j=1;j<=5000;j++){
if(vis[i][j]) ans++;
}
cout<<ans<<'\n';
}
查看3道真题和解析