欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

牛客NOIP提高组(三)题解

程序员文章站 2022-04-14 22:37:19
心路历程 预计得分:$30 + 0 + 0 = 30$ 实际得分:$0+0+0= 0$ T1算概率的时候没模爆long long了。。。 A 我敢打赌这不是noip难度。。。 考虑算一个位置的概率,若想要$k$步把它干掉,那么与他距离为$1$到$k - 1$的点都必须阻塞 且距离为$k$的点至少有一 ......

心路历程

预计得分:$30 + 0 + 0 = 30$

实际得分:$0+0+0= 0$

t1算概率的时候没模爆long long了。。。

a

我敢打赌这不是noip难度。。。

考虑算一个位置的概率,若想要$k$步把它干掉,那么与他距离为$1$到$k - 1$的点都必须阻塞

且距离为$k$的点至少有一个没被阻塞

概率的处理可以用前缀和优化。

这样看似是$o(n^3 logn)$,但是却不能通过,考虑在前缀和处理的时候有很多没用的状态(超出边界)

加一些剪枝即可

牛客NOIP提高组(三)题解
#include<cstdio>
#define max(a, b) (a < b ? b : a)
#define ll long long
using namespace std;
const int maxn = 201, mod = 1e9 + 7, inf = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m, a[maxn][maxn], g[maxn][maxn][maxn], vis[maxn][maxn];
ll fastpow(ll a, ll p) {
    ll base = 1;
    while(p) {
        if(p & 1) base = 1ll * base * a % mod;
        a = 1ll * a * a % mod; p >>= 1;
    }
    return base;
}
ll inv(ll a) {
    return fastpow(a, mod - 2);
}
int mul(int a, int b) {
    if(1ll * a * b > mod) return 1ll * a * b % mod;
    else return a * b;
}
void pre() {
    //cout << a[1][1] << endl;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            g[0][i][j] = a[i][j] % mod;
 
    for(int k = 1; k <= max(n, m); k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++) {
                if((i - k < 0) || (j - k < 0) || (i + k > n + 1) || (j + k > m + 1)) {vis[i][j] = 1; continue;}
                if(vis[i][j]) continue;
                g[k][i][j] = mul(g[k - 1][i - 1][j], g[k - 1][i + 1][j]);
                if(k > 2) g[k][i][j] = mul(g[k][i][j], inv(g[k - 2][i][j]));
                if(k >= 2) g[k][i][j] = mul(mul(g[k][i][j], inv(a[i][j + k - 2])), inv(a[i][j - k + 2]));
                g[k][i][j] = mul(mul(g[k][i][j], a[i][j + k]), a[i][j - k]);
            }
}
ll calc(int x, int y) {
    ll ans = 0, s = a[x][y];
    for(int i = 1; i <= max(n, m); i++) {
        if((x - i < 0) || (y - i < 0) || (x + i > n + 1) || (y + i > m + 1)) break;
        int now = g[i][x][y];
        ans = (ans + mul(mul(i, (1 - now + mod)), s)) % mod;
        s = mul(s, now);
    }
    return ans;
}
int main() {
//  freopen("a.in", "r", stdin);
    n = read(); m = read();
    for(ll i = 1; i <= n; i++) {
        for(ll j = 1; j <= m; j++) {
            ll x = read(), y = read();
            a[i][j] = mul(x, inv(y));
        }
    }
    pre();
    for(ll i = 1; i <= n; i++, puts(""))
        for(ll j = 1; j <= m; j++)
            printf("%lld ", calc(i, j) % mod);
    return 0;
}
a

 

b

考场上根本就没时间做。。

题目给出的模型太难处理了,考虑转化成一个较为普通的模型

遇到这种每个点有两个状态的题不难想到拆点,分别表示赢 / 输

当$a$赢了$b$,就从$a$赢向$b$输连边。

这样会得到一个新的无环图,可以证明,两个图中的环是等价的。

直接暴力找最小环即可,时间复杂度:$o(n^2 t)$

牛客NOIP提高组(三)题解
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10005, bit = 13;
int n, m, dep[maxn], fa[maxn][21], mc, u, v;
vector<int> v[maxn];
int lca(int x, int y) {
    if(dep[x] < dep[y]) swap(x, y);
    for(int i = bit; i >= 0; i--) if(dep[fa[x][i]] >= dep[y]) x = fa[x][i];
    if(x == y) return x;
    for(int i = bit; i >= 0; i--) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}
void bfs(int x) {
    queue<int> q;
    q.push(x); dep[x] = 1; fa[x][0] = 0;
    while(!q.empty()) {
        int p = q.front(); q.pop();
        for(int i = 0, to; i < v[p].size(); i++) {
            if(!dep[to = v[p][i]]) {
                fa[to][0] = p; dep[to] = dep[p] + 1;
                for(int j = 1; j <= bit; j++) fa[to][j] = fa[fa[to][j - 1]][j - 1];
                q.push(to);
            }
            else if(to != fa[p][0]) {
                int lca = lca(p, to), dis = dep[p] + dep[to] - 2 * dep[lca] + 1;
                if(dis < mc) mc = dis, u = p, v = to;
            }
        }
    }
}
int main() {
    int meiyong; scanf("%d", &meiyong);
    while(scanf("%d", &n) && n) {//tag
        scanf("%d", &m);
           
        mc = maxn;
        for(int i = 1; i <= 2 * n; i++) v[i].clear();
        memset(dep, 0, sizeof(dep));
        memset(fa, 0, sizeof(fa));
           
        for(int i = 1; i <= m; i++) {
            int x, y; scanf("%d %d", &x, &y);
            v[x].push_back(y + n); v[y + n].push_back(x);
        }
           
        for(int i = 1; i <= 2 * n; i++) if(!dep[i]) bfs(i);
        if(mc == maxn) {puts("-1");continue;}
        int lca = lca(u, v);
        vector<int> ans; ans.clear();
        printf("%d\n", mc);
        while(u != lca) printf("%d ", (u - 1) % n + 1), u = fa[u][0];
        printf("%d", (lca - 1) % n + 1);
        while(v != lca) ans.push_back((v - 1) % n + 1), v = fa[v][0];
        for(int i = ans.size() - 1; i >= 0; i--) printf(" %d", ans[i]);
        puts("");
    }
    return 0;
}
/*
*/
b

c

$k=2$的时候是斐波那契博弈

$k \not = 2$的时候是神仙结论

考虑$k \not = 2$怎么做。

结论:

若$l = n$时先手必输,那么我们找到一个$m = \frac{n}{k} >= n$,且最小的$m$,当$l = n+m$先手也一定必输

证明:

我们把多着的$m$个单独考虑,若$n < l < n+m$时,先手拿走多余的$m$个,后手必败。

但当$l = n +m$时,先手不能拿走$m$个,因为此时后手可以一步拿走剩余的。

不断往下推就行了

牛客NOIP提高组(三)题解
#include<bits/stdc++.h>
#define ll long long  
using namespace std;
const int maxn = 1e7 + 10;
int t, k, top;
ll l, sta[maxn];
int main() {
    cin >> t;
    while(t--) {
        cin >> k >> l;
        ll now = 1;
        sta[top = 1] = 1;
        while(now < l) {
            int nxt = lower_bound(sta + 1, sta + top + 1, (now % k == 0) ? now / k : (now / k + 1)) - sta;
            sta[++top] = (now = (now + sta[nxt]));
        }
        puts(now == l ? "dog" : "god");
    }
    return 0;
}
/*
1
2 21
*/
c