2023ICPC杭州站G、H题详解

G 控制贪吃蛇

解题思路

这道题就是找头到该点所需要的最小步数

1.首先，我们先简化题目，假设说这条蛇只有一个头，再求解这道题，其实就是一个Bfs板子题
2.再考虑会触碰到身体的情况，简化这个情况，其实就是只有在k-i步之后我们才能触碰到身体所在的格子
3.所以最后的情况就并不是边权为1，不能用queue来维护，所以要用优先队列来维护当前取出的最小边权是多少

AC code

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>

using namespace std;

typedef unsigned long long LL;
typedef pair<int,int> PII;
typedef pair<int,PII> PIP;
const int N = 3005;

LL n,m,k;
LL dist[N][N],limit[N][N];
char g[N][N];
bool st[N][N],body[N][N];
int startx,starty;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
priority_queue<PIP,vector<PIP>,greater<PIP>> q;

void bfs(){
    st[startx][starty] = true;
    q.push({0,{startx,starty}});

    while(q.size()){
        auto t = q.top();
        q.pop();
        int x = t.second.first,y = t.second.second;
        for(int i = 0;i < 4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(st[nx][ny] || nx < 1 || nx > n || ny < 1 || ny > m || g[nx][ny] == '#') continue;
            st[nx][ny] = true;
            if(!body[nx][ny]) dist[nx][ny] = dist[x][y] + 1;
            else dist[nx][ny] = max(dist[x][y] + 1,limit[nx][ny] + 1);  //如果是身体的话就要取一下max
            q.push({dist[nx][ny],{nx,ny}});
        }
    }
}

void solve(){
    cin >> n >> m >> k;
    for(int i = 1;i <= k;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        body[a][b] = true;
        if(i == 1){
            startx = a;
            starty = b;
        }
        limit[a][b] = k - i;   //是身体，只有走了limit步数之后才能走到这点
    }
    for(int i = 1;i <= n;i++) scanf("%s",g[i] + 1);
    bfs();

    LL res = 0;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
            res += dist[i][j] * dist[i][j];

    cout << res << endl;
}

int main(){
    int T = 1;
    while(T--) solve();
    return 0;
}

H甜蜜的修噶

解题思路

这道题难想的就是求概率的问题，把情况分为三类

1.a[i] < a[b[i]] 一定会触发事件
2.a[i] >= a[b[i]] + w[b[i]] 一定不会触发事件
3.如果前一个事件发生，这个事件才会发生

我们根据第三个条件，建图，后一个点只有前一个点发生了才能发生，假设说这个点加上所有的祖先节点数为n
那么这个事件发生的概率就是1/n!因为前面必须按照严格的顺序排列才能发生当前的事件

AC code

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>

using namespace std;

typedef long long LL;
const int N = 5e5 + 5;
const int MOD = 1e9 + 7;

LL n,a[N],b[N],w[N],fac[N];
LL p[N];                    //事件发生的概率
vector<int> ne[N];

LL ksm(LL a,LL b,LL mod){
    a %= MOD;
    LL res = 1;
    while(b){
        if(b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

LL inv(LL x){
    return ksm(x,MOD - 2,MOD);
}

void init(){
    fac[1] = 1;
    for(int i = 2;i < N;i++) fac[i] = fac[i - 1] * i % MOD;
}

void dfs(int u,int pro){
    for(auto t : ne[u]){
        p[t] = fac[pro + 1];
        dfs(t,pro + 1);
    }
}

void solve(){
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i],p[i] = 0,ne[i].clear();
    for(int i = 1;i <= n;i++) cin >> b[i];
    for(int i = 1;i <= n;i++) cin >> w[i];

    for(int i = 1;i <= n;i++){
        if(a[b[i]] > a[i]) p[i] = 1;
        else if(a[i] >= a[b[i]] + w[b[i]]) p[i] = 0;
        else ne[b[i]].emplace_back(i);
    }

    for(int i = 1;i <= n;i++) 
        if(p[i] == 1) dfs(i,1);

    for(int i = 1;i <= n;i++){
        if(p[i] == 0) cout << a[i] << ' ';
        else cout << (a[i] + w[i] * inv(p[i]) % MOD) % MOD << ' ';
    }
    cout << endl;
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T = 1;
    init();
    cin >> T;
    while(T--) solve();
    return 0;
}