NEUQ-ACM第九届“图灵杯”题解

时间：2023-06-05

A.大学期末现状

【问题描述】

作为一名大学生的你，现在又到了期末查成绩的时候，当你的成绩大于等于60时请输出“jige,haoye!”,否则输出"laoshi,caicai,laolao"。

【输入格式】

一行，一个整数x代表你的成绩（0<=x<=100）

【输出格式】

一行字符串

【输入样例】

【输出样例】

jige,haoye!

【代码】

#includeusing namespace std;int main() {int x;cin>>x;if(x>=60) cout<<"jige,haoye!";else cout<<"laoshi,caicai,laolao";return 0;}

难度：签到题（简单）

题解：非常贴心的一道题

B.G1024

【问题描述】

期末考试结束后，图灵杯出题组的几位同学卑微地留在校出题，但是由于疫情影响，他们不得不尽快乘坐G1024号火车离开学校，现在假设图灵杯出题组共n人，并且通过APP可以知道G1024在接下来k天的已购票数x，总票数m，现在Phenix想知道在所有人都一起上车的前提下最早在第几天可以离开学校，如果无论怎样都无法离开请输出“G!”

【输入格式】

第一行两个整数,n,k，表示出题组人数和天数(n,k<1000)

接下来k行,第i行两个整数x,m表示接下来第i天G1024的已购票数和总票数(0<=x<=m<1000)

【输出格式】

一行，在所有人都一起上火车的前提下最早在第几天可以离开学校,如果不能离开请输出“G!”

【输入样例】

7 5100 10099 10095 100900 10000 1000

【输出样例】

【代码】

#includeusing namespace std;int main() {int n,k,i=1;cin>>n>>k;for(;i<=k;i++){int x,m;cin>>x>>m;int op=m-x;if(op> =n) {break;}}if(i>k) cout<<"G!";else cout<

难度：简单

题解：模拟，判断票数是否充足

C.NEUQ

【问题描述】

一天Phenix得到了一个长度为n的字符串，字符串仅由大写字母A~Z组成，现在Phenix想知道最少需要删除多少个字符使字符串变成NEUQNEUQ……这种由若干个"NEUQ"组成的形式。

【输入格式】

第一行一个整数n，表示字符串长度(n<=1000000) 第二行一个字符串

【输出格式】

一个整数，表示最少需要删除的字符数量

【输入样例1】

10NEUUQNEUQQ

【输出样例1】

【输入样例2】

9ILOVENEUQ

【输出样例2】

【代码】

#includeusing namespace std;string t="NEUQ";int main() {int n;cin>>n;int ans=0;int j=0;string s;cin>>s;for(int i=0;i

难度：适中

题解：字符串从左至右逐个匹配

D.7-4 小G的任务

【问题描述】

Phenix在验完题目之后，觉得图灵杯里面的简单题太多了,不符合图灵杯考验算法编程能力的初衷，决定增加一道难度更大的题目，将出题的任务交给了小G。众所周知，小G的水平十分有限，目前无法原创难度大的题目，于是他打算去各大oj里面白嫖题目

目前小G能查询到的oj一共有n个，对于第i个oj，可以白嫖的难度合适题目数量我们定义为ai，ai的大小定义为数字i的各数位之和。例如，i=233，ai=2+3+3=8；i=2048，ai=2+0+4+8=14。现在给定有n个oj可以白嫖，小G想知道，最后他有多少个题目可以白嫖

【输入格式】

一个正整数n<=1000000

【输出格式】

一个正整数表示有多少个题目可以白嫖

【输入样例1】

【输出样例1】

【输入样例2】

【输出样例2】

900

【代码】

#includeusing namespace std;long long n,sum=0;int main() {cin>>n;for(int i=1;i<=n;i++){int x=i;while(x){sum+=x%10;x=x/10;}}cout<

难度：简单

题解：拆分数位进行求和

E.nn与游戏

【问题描述】

nn最近突然对做游戏非常感兴趣，于是他去找做游戏的xf询问相关话题，而xf此时正好在做一个游戏demo。

目前游戏中有一个n×n大小的地图，里面有若干个可控制的己方单位、与己方单位同数量的敌对单位和一些障碍物。为了充分达成对各个单位的克制，玩家需要手动控制各个不同单位移动到自己所克制的敌对单位附近攻击。

现在xf将这样一个功能的实现强行塞给了nn：需要让玩家立刻了解到自己可控制的所有单位是否能绕过各个障碍移动到各自所克制的地方单位附近。你能帮nn解决这个问题吗？

【输入格式】

第1行输入n，m，代表该地图大小为n×n，存在m个障碍。

第2∼m+1行每行依次输入x,y，代表每个障碍的坐标位置。

第m+2行输入t，代表总共有t个可控制单位和t个敌对单位。

第m+3行往后每行依次输入x1,y1,x2,y2，(x1,y1)代表一个己方可控制单位的位置，(x2,y2)代表被其克制的敌对单位的位置（即该可控制己方单位的目标点）。

数据保证任何单位与障碍都不会出现重叠，地图的x，y坐标都位于[0,n)范围内。

1≤n≤1000，0≤m<1000000

1≤t≤10，0≤x,y,x1,y1,x2,y2

【输出格式】

按可控制单位坐标的输入顺序输出各个可控制单位是否能抵达对应敌对单位所在位置，若能抵达，输出抵达对应位置所需的最短步数，否则输出-1。

注：寻路过程中需要考虑单位间的阻挡（即一个单位不管是可控制单位还是敌对单位，都会成为其他单位的障碍物），但因为只是计算一个时间点的事情，所以在计算时默认其他单位都在原来位置静止不动就行。

【输入样例】

3 11 020 0 1 10 1 2 2

【输出样例】

-13

【样例解释】

地图如下（a，b为可控制单位，对应克制的敌对单位为c，d，障碍物为1，空位置为0）

00dbc0a10

如图可见，a去c的路程被b和1挡住了，故输出-1；b可以通过向上，向右，向右，三步到达d，此路径为b到达d的最短路径，故输出3

【代码】

#include #define MS(a, b) memset(a, b, sizeof(a))#define fi first#define se secondusing namespace std;struct Point { int x, y, d; Point(int _x, int _y, int _d=0): x(_x), y(_y), d(_d) {} bool operator==(const Point& a) { return x == a.x && y == a.y; }};int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};bool M1[1005][1005], M2[1005][1005];vector warrior[3];int n;int bfs(const Point& s, const Point& t) { MS(M2, false); queueq; q.push(s); while (!q.empty()) { Point p = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int x = p.x + dx[i]; int y = p.y + dy[i]; if (x < 0 || x >= n || y < 0 || y >= n || M1[x][y] || M2[x][y]) continue; M2[x][y] = true; Point tmp = Point(x, y, p.d + 1); if (tmp == t) return tmp.d; q.push(tmp); } } return -1;}void solve() { int m; MS(M1, false); cin>>n>>m; for (int i = 0; i < m; i++) { int x, y; cin>>x>>y; warrior[0].push_back(Point(x, y)); M1[x][y] = true; } int t; cin>>t; for (int i = 0; i < t; i++) { int x1, y1, x2, y2; cin>>x1>>y1>>x2>>y2; warrior[1].push_back(Point(x1, y1)); M1[x1][y1] = true; warrior[2].push_back(Point(x2, y2)); M1[x2][y2] = true; } for (int i = 0; i < warrior[1].size(); i++) { M1[warrior[2][i].x][warrior[2][i].y] = false; cout<

难度：困难

题解：BFS，对每一个起点进行搜索得到即可起点到终点的最短距离

F.第二大数

【问题描述】

牛神对于第一的宝座感到厌倦，他开始研究第二大的贡献。

现在给你一个N个数的排列P,包含(1,2,...,N)，其中对于任给的一组(L,R) (1≤L

现在请聪明的你算出的结果，AC者可凭运气获得牛神签名照一张。

【输入格式】

第一行为牛神想要研究的数字N，其中2≤N≤10000 。

第二行为N的一个排列。

【输出格式】

输出包括一个整数，表示所求结果。

【输入样例】

32 3 1

【输出样例】

【代码】

#include#define ll long longusing namespace std;ll arr[10100];int main(){ ll n,ans=0,first,second; cin>>n; for(int i=1;i<=n;i++) cin>>arr[i]; for(int i=1;ifirst) { second=first; first=arr[j]; } else if(arr[j]>second) { second=arr[j]; } ans+=second; } } cout<

难度：较难

题解：枚举所有区间第二大的和，比赛时一直wa，最后还是不知道自己错在哪

G.Num

【问题描述】

Phenix有一个正整数N，他想知道正整数N是否可以写成a∗b+a+b的形式(其中a>0,b>0)

例如3=1∗1+1+1，如果可以请输出"Yes"，否则输出"No"

【输入格式】

一个正整数N(0

【输出格式】

"Yes"或者"No"

【输入样例1】

【输出样例1】

【输入样例2】

【输出样例2】

Yes

【代码】

#includeusing namespace std;long long n;int main() {cin>>n;n++;bool op=true;for(int i=2;i<=sqrt(n);i++){if(n%i==0){op=false;break;}}if(op) cout<<"No";else cout<<"Yes";return 0;}

难度：较难

题解：数学题，左右各＋1可得(n + 1) = (a + 1) * (b + 1)，直接判断n + 1是否为质数

H.特征值

【问题描述】

最近捷宝学习了线性代数的知识，并成功在期末考试中获得了100分的好成绩。

其中计算矩阵的特征值这一题型给他留下深刻印象。

出于好奇心，他决定利用假期时间仔细钻研特征值这一概念。经过长达好多好多好多好多天的闭关研究，捷宝提出了整数的特征值这一概念。

现在捷宝想要把概念进行推广，他需要你帮忙设计一个程序，能够对于任意读入的一个正整数，快速计算它的特征值.

提示：由于本题中读入数据的数据范围较大，所以可以考虑使用int类型的数组来存储X的每一位，以便于后续操作。

计算答案和输出答案也同理，可以使用数组来存储数字的每一位。

【输入格式】

输入共包括1行，输入捷宝想要研究的数字X，X可以无穷大

【输出格式】

输出共包括一行，输出所研究数字的特征值

【输入样例1】

1225

【输出样例1】

1360

【输出样例2】

314159265358979323846264338327950288419716939937510

【输出样例2】

349065850398865915384738153697722542688574377708317

【代码】

#includeusing namespace std;const int maxn=5e5+1;int a[maxn];char s[maxn];int n,sum[maxn];vector ans;int main() {cin>>(s+1);n=strlen(s+1);for(int i=1;i<=n;i++){a[i]=s[i]-'0';sum[i]=sum[i-1]+a[i];}for(int i=n;i>=1;i--){ans.push_back(sum[i]);}for(int i=0;i=10){if(i+1>=ans.size()){ans.push_back(ans[i]/10);}else{ans[i+1]+=ans[i]/10;}ans[i]%=10;}}for(int i=ans.size()-1;i>=0;i--){cout<

难度：困难

题解：使用数组读入数据，手动模拟进位...算了还是用出题组的解释吧

I.最大公因数

【问题描述】

雯雯沉迷学习数学无法自拔，他在闭关修炼中遇到了难题，聪明的你能帮他解答吗？

现在给你一个N个数的序列P，定义X为这N个数的最大公因数，你可以进行无限次操作，每次操作选择一组(L,R) (1≤L=R≤N,PL≥1)，使得PL−1且PR+1，每次操作产生新的序列P。请问所有可能产生的P对应的X最多有多少个。AC者可凭RP获得雯雯签名照一张。

定义：A是序列P的一个公因数当且仅当序列P的每一个元素都能被A整除，且A≥1。

注意：本题规定任何正整数都是0的公因数。

【输入格式】

第一行包含一个数N，其中2≤N≤500。

第二行为长度为N的一个序列，其中序列元素P满足 1≤P≤1000000。

【输出格式】

输出包括一个整数，表示所有序列产生的最大公因数的个数。

【输入样例】

31 1 2

【输出样例】

【样例解释】

第一次操作，L=1，R=2，操作后P=0,2,2，此时P的最大公因数为2。

第二次操作，L=2，R=3，操作后P=0,1,3，此时P的最大公因数为1。

第三次操作，L=2，R=3，操作后P=0,0,4，此时P的最大公因数为4。

经过若干次操作后，序列P产生的最大公因数为1，2，4，共3个。

【代码】

#includeusing namespace std;int n,sum=0,op=0;int a[501];int main() {int i,j;cin>>n;for(i=1;i<=n;i++){ cin>>a[i];sum+=a[i];a[i]+=a[i-1];}for(j=1;j*j<=sum;j++){if(sum%j!=0) ;else{if(sum/j<=a[n-1] && j*j!=sum) op++;if(j<=a[n-1]) op++;}}cout<<++op;return 0;}

难度：较难

题解：N个数相加得到sum，计算sum的所有因数，求小于前n-1个数和的因数即可

J.玄神的字符串

【问题描述】

玄神有一条珍藏多年的神奇字符串。因为某种原因，该字符串只由数字0和数字1组成。但是最近，他开始对字符串感到厌烦，所以他想将这个字符串删除。他可以任意进行以下三种操作，每种操作的次数不限：

1）选择字符串中的一个0和一个1，将他们删除，代价为a；

2）选择字符串中两个位置不同的0或者两个位置不同的1，将他们删除，代价为b；

3）将字符串中的一个0变成1或将字符串中的一个1变成0，代价为c。

聪明的你能不能帮帮玄神，求出将这条神奇字符串删除成空字符串（不含任何字符的字符串）的最小代价为多少？

【输入格式】

第一行包括一个仅由数字0和数字1构成的字符串s，s的长度不超过50000,保证s的长度为偶数

第二行包括三个整数a、b、c，分别代表上述三种操作的代价。保证1≤a,b,c≤10000

【输出格式】

输出包括一个整数，表示删除该字符串的最小代价

【输入样例1】

01100110013 4 5

【输出样例1】

【输入样例2】

011001100110 2 3

【输出样例2】

【代码】

#include#define int long longusing namespace std;const int maxn=5e4+5;char str[maxn];int a,b,c,n;signed main() { cin>>(str+1);cin>>a>>b>>c;n=strlen(str+1);int c0=0,c1=0;for(int i=1;i<=n;i++){if(str[i]=='0'){c0++;}else c1++;}if(a<=b){int d=min(c0,c1);int ans=d*a;c0-=d;c1-=d;int x=max(c0,c1);ans+=min(x/2*b,x/2*(c+a));cout<0){ans+=min(a,b+c);}cout<

难度：困难
题解：贪心，先统计0和1的数量，对abc三者关系分类讨论

K.金牌厨师

【问题描述】

Phenix作为食堂的金牌厨师，每天的工作是为同学们准备饭菜，Phenix做出的每一种菜都有一个辣度值，范围是[1,n]。作为厨师，Phenix提前了解了m位同学的辣度接受范围，第i位同学的辣度接受范围被描述为[li,ri]，表示该同学可以接受辣度值位于这个区间的菜。由于众口难调，每天Phenix会选出部分同学，做出能让这部分同学都接受的辣度的菜。Phenix作为金牌厨师对每天工作的满意程度定义为选出的同学的人数k和能让这部分同学都接受的菜的种类数x（这里理解为一种辣度对应一种菜）两者中的最小值，即min(k,x)。

现在你需要想办法让Phenix的满意程度最大。

【输入格式】

第一行两个整数n,m，表示菜的辣度最大值和同学的人数。(1<=n,m<=300000)

接下来m行,每行两个整数li,ri依次表示第i个同学的辣度接受范围(1<=li,ri<=n)

【输出格式】

一行，表示满意度的最大值。

【输入样例】

5 53 51 22 52 54 5

【输出样例】

【样例解释】

最优策略为：选择第1，3，4位同学，他们的辣度接受范围分别是[3,5],[2,5],[2,5]，所以能让他们都接受的菜的辣度是3，4，5，此时k=3,x=3,满意度=min(k,x)=3

【代码】

难度：困难

题解：不是对手，最后三题直接上出题组给的题解和代码

L.WireConnection

【问题描述】

谷宝最近完成了ImmersiveEngineering（IE）的各种重型机械和发电机的建设，但是基地上空密密麻麻的电线让他觉得非常不美观。他决定用工程师剪线钳把所有电线全部拆除之后重新用高压电线设置电网。

每一个重型机械或发电机都有且只有一个接线器用来连接电线，谷宝的目标只有一个，那就是让整个基地的所有接线器连在同一个电网中所需求的电线总长度最短。由于电线在制作时只能制作整数长度，所以对于两接线器之间距离不为整数的，其需求的电线长度需要向上取整。

形式上，若两接线器A,B的坐标分别为(XA,YA,ZA),(XB,YB,ZB)，则他们之间的距离为sqrt( ⌈(XA−XB)2+(YA−YB)2+(ZA−ZB)2⌉ ) ，其中⌈⌉为向上取整，即不小于当前数字的最小整数。例如⌈3⌉=3,⌈3.14⌉=4。

注：c++的cmath头文件中的ceil函数可以实现浮点数的向上取整，例如：ceil(x)返回x向上取整的结果。

【输入格式】

第一行包含一个正整数n(n≤2000)，表示接线器的数量。

接下来n行，每行包含三个整数x、y和z（∣x∣,∣y∣,∣z∣≤1000000000）表示接线器的空间坐标。

【输出格式】

需求的电线的最短总长度。

【输入样例】

50 0 01 0 0-1 0 00 1 00 -1 0

【输出样例】

【代码】

#include using namespace std;const int MAXN = 10001;struct node {long long x, y, z;};long long distCalc(node x, node y) {return ceil(sqrt((double)((x.x - y.x) * (x.x - y.x)) + ((x.y - y.y) * (x.y - y.y)) + ((x.z - y.z) * (x.z - y.z))));}int main() {int n;cin >> n;node p[MAXN];for (int i = 0; i < n; ++i) {cin >> p[i].x >> p[i].y >> p[i].z;}bool vis[MAXN];long long len[MAXN];memset(vis, 0, sizeof(vis));memset(len, 0x7f7f7f7f, sizeof(len));len[0] = 0;long long ans = 0;for (int i = 0; i < n; ++i) {long long minLen = INT_MAX;int newNode = 0;for (int j = 0; j < n; ++j) {if (!vis[j] && len[j] < minLen) {minLen = len[j];newNode = j;}}ans += minLen;vis[newNode] = 1;for (int j = 0; j < n; ++j) {len[j] = min(len[j], distCalc(p[j], p[newNode]));}}cout << ans << endl;return 0;}

难度：困难

题解：完全图的最小生成树，数据保证O（n^2）可以通过。

M.NuclearReactor

【问题描述】

谷宝最近在研究IndustrialCraft2（IC2）的核反应堆，但是技巧并不娴熟的他经常发生堆芯熔毁炸掉基地。他在Wiki上找到了核反应堆各组件的属性说明提供给你，希望你帮他做一个核反应堆运行模拟器判断他设计的核反应堆能否安全运行一个周期。

IC2的核反应堆设置界面为一个6×9的网格，每个网格可以放置一个组件或者空置。核反应堆本身在运行中可以至多吸纳10000点热量，当热量超限时就会发生堆芯熔毁的爆炸奇观。

为了方便收集材料，谷宝的核反应堆只打算使用三种组件——铀燃料棒、中子反射板和散热片。

全新的铀燃料棒可以运行20000秒，即一个周期。铀燃料棒可以联合为双联燃料棒或者四联燃料棒使用以节约空间。在运行时，铀燃料棒会向相邻的四个网格中各发射1个中子，联合燃料棒发射的中子数随联数增加至2个或4个。同时，燃料棒的热量会平均分配给相邻的A类散热片，A类散热片无法吸收的热量会成为核反应堆自身的热量。

设燃料棒的发电量为W，发热量为Q，接收中子数为n，联数为m，基础效率系数为η，那么有

W=5m(η+n)，Q=2m(η+n)(η+n+1)

其中，m的取值为1、2或4，对应的基础效率系数为1、2和3。

中子反射板自身不产生任何电量或热量，但是它会将接收到的中子反射回燃料棒。

散热片共有三大类，散热片具有最大吸热速度、最大散热速度和热量缓存（除C类散热片）。

A类散热片会吸收相邻燃料棒的热量，其最大吸热速度和最大散热速度相等。普通的A类散热片热交换速度为6点每秒，而高级的A类散热片热交换速度为12点每秒。由于最大吸热速度和最大散热速度相等，当A类散热片与超过一个燃料棒相邻时可能会无法全部散去吸收的热量，当热量超过1000点时自身会熔毁，熔毁时，超过部分的热量不会进入核反应堆的热量缓存。

B类散热片会吸收核反应堆自身的热量。普通的B类散热片每秒最多吸收并散去5点热量。高级的B类散热片则每秒最多吸收32点热量并散去20点热量，当热量超过1000点时自身会熔毁，熔毁时，超出部分的热量不会进入核反应堆的热量缓存。核反应堆可以智能调控B类散热片，保证同种B类散热片吸收的热量是相等的并且普通的B类散热片会被优先使用，以达到最大化利用B类散热片的目的。此外，B类散热片只能吸收已有的核反应堆热量，换言之，某一时刻进入核反应堆热量缓存的热量至少要到下一时刻才可以被散去。

C类散热片用于协助另外两类散热片工作，每秒最多可以散去每个相邻的其他散热片4点热量。

为了简化问题，核反应堆不存在启动问题，即第一秒时燃料棒就可以接收到来自相邻燃料棒和中子反射板的中子。此外，不考虑散热片和核反应堆某一时刻由于热量超限无法接收该时刻热量的问题，换言之，热交换的结算先于熔毁。

【输入格式】

一个六行九列的网格，每个网格包含一个字符表示该网格内的组件情况。

“#”代表空，“U”表示铀燃料棒，“D”表示双联燃料棒，“Q”表示四联燃料棒,“N”表示中子反射板，“A”表示高级的A类散热片，“a”表示普通的A类散热片，“B”表示高级的B类散热片，“b”表示普通的B类散热片，“C”表示C类散热片。

【输出格式】

1、是否会发生熔毁，如果会熔毁，则在第一行输出Boom!，若可以安全运行一个周期，则给出运行结束时核反应堆的热量（保留两位小数）。 2、熔毁时或运行结束时的总发电量。

【输入样例1】

BBNNCaCaNNDQBbUa#NAQAQQNNU#AUAQ#QAQNQDNCNNUCBQQNUbUaCa

【输出样例1】

Boom!4550

【输入样例2】

####################ADA#######a#######################

【输出样例2】

Boom!100020

【输入样例3】

############UaU#######################################

【输出样例3】

Boom!17520

【代码】

#include #include #include #include using namespace std;const int MAXX = 6 + 2;const int MAXY = 9 + 2;const int MAXTemp = 10000;const int MAXTime = 20000;const int MAXVentTemp = 1000;const int dx[4] {0, -1, 0, 1};const int dy[4] {-1, 0, 1, 0};char map[MAXX][MAXY];long long mapRodHeat[MAXX][MAXY];double mapVentHeat[MAXX][MAXY];long long mapVentANum[MAXX][MAXY];long long ventBNum, ventbNum;long long mapVentCNum[MAXX][MAXY];int main() {memset(map, 0, sizeof(map));for (int i = 1; i < MAXX - 1; ++i) {for (int j = 1; j < MAXY - 1; ++j) {map[i][j] = getchar();}getchar();}long long answ = 0;memset(mapRodHeat, 0, sizeof(mapRodHeat));memset(mapVentANum, 0, sizeof(mapVentANum));memset(mapVentCNum, 0, sizeof(mapVentCNum));for (int i = 1; i < MAXX - 1; ++i) {for (int j = 1; j < MAXY - 1; ++j) {if (map[i][j] == 'U' || map[i][j] == 'D' || map[i][j] == 'Q') {int n = 0, m = 1, eta = 1;if (map[i][j] == 'D') {m = 2;eta = 2;} else if (map[i][j] == 'Q') {m = 4;eta = 3;}for (int di = 0; di < 4; ++di) {if (map[i + dx[di]][j + dy[di]] == 'U') {n += 1;} else if (map[i + dx[di]][j + dy[di]] == 'D') {n += 2;} else if (map[i + dx[di]][j + dy[di]] == 'Q') {n += 4;} else if (map[i + dx[di]][j + dy[di]] == 'N') {n += m;}}answ += 5 * m * (eta + n);mapRodHeat[i][j] = 2 * m * (eta + n) * (eta + n + 1);} else if (map[i][j] == 'A' || map[i][j] == 'a') {for (int di = 0; di < 4; ++di) {++mapVentANum[i + dx[di]][j + dy[di]];}} else if (map[i][j] == 'B') {++ventBNum;} else if (map[i][j] == 'b') {++ventbNum;} else if (map[i][j] == 'C') {for (int di = 0; di < 4; ++di) {++mapVentCNum[i + dx[di]][j + dy[di]];}}}}long long ansW = 0;double ansQ = 0;bool isBoom = 0;memset(mapVentHeat, 0, sizeof(mapVentHeat));for (int k = 0; k < MAXTime; ++k) {ansW += answ;ansQ = max((double)0, ansQ - (5 * ventbNum));double heatToVentB = ansQ;if (ventBNum != 0)ansQ = 0;for (int i = 1; i < MAXX - 1; ++i) {for (int j = 1; j < MAXY - 1; ++j) {if (mapRodHeat[i][j] != 0 && mapVentANum[i][j] == 0) {ansQ += mapRodHeat[i][j];} else if (mapVentHeat[i][j] > MAXVentTemp)continue;else if (map[i][j] == 'A') {for (int di = 0; di < 4; ++di) {if (mapRodHeat[i + dx[di]][j + dy[di]] != 0) {mapVentHeat[i][j] += min((double)12, (double)mapRodHeat[i + dx[di]][j + dy[di]] / mapVentANum[i + dx[di]][j + dy[di]]);ansQ += max((double)0, (double)mapRodHeat[i + dx[di]][j + dy[di]] / mapVentANum[i + dx[di]][j + dy[di]] - 12);}}} else if (map[i][j] == 'a') {for (int di = 0; di < 4; ++di) {if (mapRodHeat[i + dx[di]][j + dy[di]] != 0) {mapVentHeat[i][j] += min((double)6, (double)mapRodHeat[i + dx[di]][j + dy[di]] / mapVentANum[i + dx[di]][j + dy[di]]);ansQ += max((double)0, (double)mapRodHeat[i + dx[di]][j + dy[di]] / mapVentANum[i + dx[di]][j + dy[di]] - 6);}}} else if (map[i][j] == 'B') {mapVentHeat[i][j] += min((double)32, (double)heatToVentB / ventBNum);ansQ += max((double)0, (double)heatToVentB / ventBNum - 32);}}}for (int i = 1; i < MAXX - 1; ++i) {for (int j = 1; j < MAXY - 1; ++j) {if (mapVentHeat[i][j] > MAXVentTemp + 10000)continue;else if (map[i][j] == 'A') {mapVentHeat[i][j] = max((double)0, mapVentHeat[i][j] - 12 - 4 * mapVentCNum[i][j]);if (mapVentHeat[i][j] > MAXVentTemp) {mapVentHeat[i][j] += 10000;for (int di = 0; di < 4; ++di) {--mapVentANum[i + dx[di]][j + dy[di]];}}} else if (map[i][j] == 'a') {mapVentHeat[i][j] = max((double)0, mapVentHeat[i][j] - 6 - 4 * mapVentCNum[i][j]);if (mapVentHeat[i][j] > MAXVentTemp) {mapVentHeat[i][j] += 10000;for (int di = 0; di < 4; ++di) {--mapVentANum[i + dx[di]][j + dy[di]];}}} else if (map[i][j] == 'B') {mapVentHeat[i][j] = max((double)0, mapVentHeat[i][j] - 20 - 4 * mapVentCNum[i][j]);if (mapVentHeat[i][j] > MAXVentTemp) {mapVentHeat[i][j] += 10000;--ventBNum;}}}}if (ansQ > MAXTemp) {isBoom = 1;break;}}if (isBoom)cout << "Boom!";elseprintf("%.2lf", ansQ);cout << endl << ansW << endl;return 0;}

难度：极难

题解：确认过眼神，是我不会的题

上一篇：算法提高之搜索：多源BFS、最小步数模型、双端队列广搜

下一篇：智乃的密码（longlong模拟双指针