本次模考包含5题
以下是我的得分情况
| <9388> 我家门牌号 |
<20430> 小信的礼物区间总价值(1) |
<20431> 小信抗辐射(2) |
<20425> 小信找硬币 |
<20429> 小信小友躲洪水(4) |
|---|---|---|---|---|
| Accepted 100 | Accepted 100 | Wrong Answer 50 | Accepted 100 | Wrong Answer 0 |
说实话 这次模考难度不大
但由于我的思维漏洞和畏难心理
使考试中第3题50分 第4题更是一分没有 
我这里分享下T3和T5的思路
T3
读完题后 拥有绝对题感的你肯定能想到二分查找最小满足条件的防辐射值
int l=a[1],r=maxx;
while(l<r){
int mid=(l+r)/2;
if(check(mid)==true) r=mid;
else l=mid+1;
}
(一定要注意二分边界 l是从小信起始位置的辐射值开始 不是从1开始的）
考试时我就因为少考虑了这一步少拿了35分
写完二分 代码的80%就结束了
但同时整题中唯一的难点也就来了
check()函数该怎么写
我们只需判断一个点能否到达和是否已经到达两种情况即可
枚举起始位置 判断当前位置能否到达和当前位置的辐射值是否小于等于mid
如果下一步可以直接到达终点 return true
即判断
i+r>n
从i+l到i+r都是可能到达的位置 等待下次判断
防止i+r的值超过n 所以最大能到达的位置dex
dex=min(n,i+r)
如果遍历完n个点都无法到达的话就 return false
(具体代码如下）
for(int i=1;i<=n;i++){
if(!vis[i]||mid<a[i]) continue;
if(i+r>n) return vis[n+1]=1;
for(int j=i+l;j<=min(n,i+r);j++){
vis[j]=1;
}
}
return false;
(注意 vis[1]的值应置1 且每次check判断前都要将vis数组清零）
T5
写代码前我们先思考一个问题
A和B到某点的时间分别为a,b
那AB相遇的时间就为max(a,b)
即
f(A,B)=max(a,b)
懂了这个 这题你就能迎刃而解了
我们只用先把该题看成一道普通的bfs 再考虑洪水到达每个位置的时间即可
(关于洪水的dfs代码如下）
queue<Node> water_qu;
void water(){
while(water_qu.empty()!=true){
Node now=water_qu.front();
water_qu.pop();
for(int i=0;i<4;i++){
int now_x=now.x+dx[i];
int now_y=now.y+dy[i];
if(now_x<1||now_y<1||now_x>n||now_y>m||mapn[now_x][now_y]!=-1) continue;
mapn[now_x][now_y]=mapn[now.x][now.y]+1;
water_qu.push({now_x,now_y});
}
}
}
考虑小信和小友时与普通dfs一样只需判断在到达某位置之前该位置是否被淹没
即
if(play[now_x][now_y]>=mapn[now_x][now_y]) continue;
