Codeforces Round #602 (Div. 2, based on Technocup 2020 Elimination Round 3) E. Arson In Berland Forest
A destructive fire raged through the Forest, and several trees were damaged by it. Precisely speaking, you have a n×mn×m rectangle map which represents the damaged part of the Forest. The damaged trees were marked as "X" while the remaining ones were marked as ".". You are sure that all burnt trees are shown on the map. All the trees outside the map are undamaged.
The firemen quickly extinguished the fire, and now they are investigating the cause of it. The main version is that there was an arson: at some moment of time (let's consider it as 00) some trees were set on fire. At the beginning of minute 00, only the trees that were set on fire initially were burning. At the end of each minute, the fire spread from every burning tree to each of 88 neighboring trees. At the beginning of minute TT, the fire was extinguished.
The firemen want to find the arsonists as quickly as possible. The problem is, they know neither the value of TT (how long the fire has been raging) nor the coordinates of the trees that were initially set on fire. They want you to find the maximum value of TT (to know how far could the arsonists escape) and a possible set of trees that could be initially set on fire.
Note that you'd like to maximize value TT but the set of trees can be arbitrary.
The first line contains two integer nn and mm (1≤n,m≤1061≤n,m≤106, 1≤n?m≤1061≤n?m≤106) — the sizes of the map.
Next nn lines contain the map. The ii-th line corresponds to the ii-th row of the map and contains mm-character string. The jj-th character of the ii-th string is "X" if the corresponding tree is burnt and "." otherwise.
It's guaranteed that the map contains at least one "X".
In the first line print the single integer TT — the maximum time the Forest was on fire. In the next nn lines print the certificate: the map (n×mn×m rectangle) where the trees that were set on fire are marked as "X" and all other trees are marked as ".".
3 6 XXXXXX XXXXXX XXXXXX
1 ...... .X.XX. ......
10 10 .XXXXXX... .XXXXXX... .XXXXXX... .XXXXXX... .XXXXXXXX. ...XXXXXX. ...XXXXXX. ...XXXXXX. ...XXXXXX. ..........
2 .......... .......... ...XX..... .......... .......... .......... .....XX... .......... .......... ..........
4 5 X.... ..XXX ..XXX ..XXX
0 X.... ..XXX ..XXX ..XXX
題意：給一個n*m<=1e6的圖，"X"代表著火，"."代表沒著火，火只在這個范圍里面蔓延。著火的格子每回合會蔓延到周圍的8個格子，給出了最后的火情圖，求著火最多多少回合，并構造剛著火的圖。
想法：很明顯蔓延后的火都是一個矩形，所以我先橫著遍歷1遍，再豎著遍歷遍，基本可以確認這個火最多蔓延了多少回合，構造圖通過前綴和來判斷，比較簡單。然后我就被這組數據卡住了
7 5 ..XXX ..XXX ..XXX .XXX. XXX.. XXX.. XXX..
我一開始的輸出
1 ..... ...X. ..... ..... ..... .X... .....
答案
0 ..XXX ..XXX ..XXX .XXX. XXX.. XXX.. XXX..
被這個數據卡住是因為，橫著掃一遍豎著掃一遍只能確定最多蔓延回合不會超過這個數值，但是構造出來的圖不一定能蔓延回原來的圖。
做法：二分答案，先記錄終圖的前綴和，然后構造起始圖，該點為"X"意味著終圖中以該點為中心的m范圍全為"X"，用二維前綴和來判斷。否則為"."。構造的同時記錄起始圖的前綴和。
構造完起始圖后我們再檢查初始是否合法，同樣是用前綴和，該點為"X"意味著起始圖中以該點為中心的m范圍有"X"或者該點為"."意味著起始圖中以該點為中心的m范圍。
分析復雜度，每次二分我們需要構造1次和檢查1次，復雜度是2e6。對于1e6的圖需要二分20次復雜度是4e7，分析可得，蔓延最大不會超過1000回合，只需二分10次，復雜度變2e7。而橫著掃一遍豎著掃一遍可以確定二分上界，這個操作復雜度是2e6，這樣比純二分快點。。
#include <bits/stdc++.h> using namespace std; const int N=2e6+5; char p[N]; char v[N]; int u[N]; int z[N]; int n,m; inline bool solve(int zd) { for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { int t=i*(m+1)+j; v[t]='.'; if(p[t]=='X') { int flag=0; int rx=i+zd; int ry=j+zd; int lx=i-zd; int ly=j-zd; if(rx>n||ry>m||lx<=0||ly<=0)flag=1; if((u[rx*(m+1)+ry]-u[rx*(m+1)+ly-1]-u[(lx-1)*(m+1)+ry])+u[(lx-1)*(m+1)+ly-1]!=((zd*2+1)*(zd*2+1)))flag=1; if(!flag)v[t]='X'; } z[t]=(v[t]=='X'?1:0)+z[t-1]+z[t-m-1]-z[t-m-2]; } } for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { int t=i*(m+1)+j; if(p[t]=='X') { int rx=i+zd; int ry=j+zd; int lx=i-zd; int ly=j-zd; if(rx>n||ry>m||lx<=0||ly<=0)continue; if((z[rx*(m+1)+ry]-z[rx*(m+1)+ly-1]-z[(lx-1)*(m+1)+ry]+z[(lx-1)*(m+1)+ly-1])==0)return false; } } } return true; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { int t=i*(m+1)+j; scanf(" %c",&p[t]); u[t]=(p[t]=='X'?1:0)+u[t-1]+u[t-m-1]-u[t-m-2]; } } int zd=10000005; for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { int t=0; while(p[i*(m+1)+j]=='X') { j++; t++; if(j==m+1)break; } if(t&&zd>t)zd=t; } } for(int i=1;i<=m;++i) { for(int j=1;j<=n;++j) { int t=0; while(p[i+j*(m+1)]=='X') { j++; t++; if(j==n+1)break; } if(t&&zd>t)zd=t; } } zd=(zd-1)/2; if(zd==0) { printf("0\n"); for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j)printf("%c",p[i*(m+1)+j]); printf("\n"); } return 0; } int l=0,r=zd; int ans=0; while(l<=r) { int m=(l+r)>>1; if(solve(m)) { l=m+1; ans=m; } else r=m-1; } printf("%d\n",ans); solve(ans); for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j)printf("%c",v[i*(m+1)+j]); printf("\n"); } return 0; }
總結：直接開二維數組不可取，我是用了一維的來表示二維的，用vector應該會方便不少。然后就是要多練，此外對題目的復述要準確，問人時完全描述成了另一道題。。這都是值得努力的地方
浙公網安備 33010602011771號