2021 年百度之星·程序设计大赛

久违一更,距离上次更新已经半年了。

这次题目竟然不是按照难度排序

A. 迷失 Hdu 6996)

题目大意

给定一张无向图,边的边权为0)1),在图上随机游走,问从1号点经过k条边到达n号点,经过的边的异或和为1的概率。

解题思路

第一眼,图上随机游走,循环概率,点数不超过100,高斯消元,不想写,跳了。

做完后面的回来看第二眼,哦,恰好经过k条边,设dp[i][j][k])表示当前第i)号点,当前边权异或和为k),经过j)条边到达n)号点且边权异或和为1)的概率。

忽然看到k leq 10^6),空间爆了。注意到dp[i][j][k])总是从dp[?][j-1][?])转移过来的,于是可以用循环队列压成两维,即dp[cur][i][k])表示当前状态j))dp[cur^1][i][k])表示上一个状态j – 1)),空间问题解决了,但时间复杂度Omk))On^2k))还是爆了时间。

忽然发现给定一张图,转移方程式是确定且线性的,矩阵快速幂优化就可以了。时间复杂度为On^3log k))

具体而言,矩阵规模是200 imes 200),根据转移方程式dp[i][j][k] = frac{1}{du[i]}sumlimits_{v in i, v)}dp[v][j-1][k oplus cost[i,v)])构造即可。

下面代码中是根据方程式两边乘以了du[i])构造的。du[i])表示i)号点的度。

结果卡常,中途运算从long long)改成int),矩阵乘法减少不必要的取模才过了。

神奇的代码
#include <bits/stdc++.h>
#include <vector>
using namespace std;
typedef long long LL;

template <typename T>
void readT &x) {
    int s = 0, c = getchar);
    x = 0;
    while isspacec)) c = getchar);
    if c == 45) s = 1, c = getchar);
    while isdigitc)) x = x << 3) + x << 1) + c ^ 48), c = getchar);
    if s) x = -x;
}

template <typename T>
void writeT x, char c = ' ') {
    int b[40], l = 0;
    if x < 0) putchar45), x = -x;
    while x > 0) b[l++] = x % 10, x /= 10;
    if !l) putchar48);
    while l) putcharb[--l] | 48);
    putcharc);
}

const int MO = 998244353;
const int N = 1e2 + 8;
const int M = 2e4 + 8;

int head[N], nxt[M], ty[M], cnt[N], to[M];

int inv[N];

int n, m, k, num;

inline int qpowint a, int b) {
    int ans = 1;
    whileb) {
        ifb & 1) {
            ans = 1ll * ans * a % MO;
        }
        a = 1ll * a * a % MO;
        b = b >> 1;
    }
    return ans;
}

struct matrix {
    int n, m;
    int data[N * 2][N * 2];
    inline void clear) {
        for int i = 0; i <= n; i++)
            for int j = 0; j <= m; j++) data[i][j] = 0;
    }
}ff, eye;

inline matrix operator *matrix a, matrix b) {
    matrix qwq;
    qwq.n = a.n;
    qwq.m = b.m;
    qwq.clear);
    LL tmp = 0;
    for int i = 1; i <= a.n; i++)
        for int j = 1; j <= b.m; j++){
            tmp = qwq.data[i][j];
            for int k = 1; k <= a.m; k++){
                tmp += 1ll * a.data[i][k] * b.data[k][j]));
                if k % 15 == 0)
                    tmp %= MO;
            }
            if tmp >= MO)
                tmp %= MO;
            qwq.data[i][j] = tmp;
        }
    return qwq;
}

inline void addint u, int v, int w){
    num ++;
    nxt[num] = head[u];
    to[num] = v;
    ty[num] = w;
    head[u] = num;
    num ++;
    nxt[num] = head[v];
    to[num] = u;
    ty[num] = w;
    head[v] = num;
    cnt[u] ++;
    cnt[v] ++;
}


int mainvoid) {
    forint i = 1; i <= 105; ++ i)
        inv[i] = qpowi, MO - 2);
    int kase; readkase);
    for int ii = 1; ii <= kase; ii++) {
        readn);
        readm);
        readk);
        num = 0;
        forint i = 1; i <= n; ++ i){
            head[i] = 0;
            cnt[i] = 0;
        }
        forint u, v, w, i = 1; i <= m; ++ i){
            readu);
            readv);
            readw);
            addu, v, w);
        }
        ff.n = ff.m = 2 * n;
        ff.clear);
        forint i = 1; i <= n; ++ i)
            forint j = head[i]; j; j = nxt[j]){
                int v = to[j];
                int kin = ty[j];
                forint s = 0; s <= 1; ++ s){
                    int yuan = i;
                    if s)
                        yuan += n;
                    int nxt = v;
                    if s ^ kin)
                        nxt += n;
                    ff.data[yuan][nxt] = inv[cnt[v]];
                }
            }
        eye.n = eye.m = 2 * n;
        eye.clear);
        forint i = 1; i <= 2 * n; ++ i)
            eye.data[i][i] = 1;
        whilek){
            if k & 1)
                eye = eye * ff;
            ff = ff * ff;
            k >>= 1;
        }
        int ans = eye.data[1][n + n] * 1ll * cnt[n] % MO * inv[cnt[1]] % MO;
        writeans, '
');
    }
    return 0;
}


B. 愿望幽灵 Hdu 6997)

题目大意

咕咕咕

解题思路

神奇的代码
咕咕咕


C. 鸽子 Hdu 6998)

题目大意

n)台电脑,第k)台坏了。m)次操作,每次操作交换第u_i)和第v_i)台电脑,你可以跳过若干次操作。

问对于每个j in [1,n]),最终坏的电脑的位置是第j)台的最小跳过次数是多少。无法实现输出-1。

解题思路

dp[i][j])表示前i)次操作后,坏的电脑是第j)台的最小跳过次数。容易发现每次操作只会更改两个dp)值,即dp[i])dp[i-1])只有dp[i][u_i])dp[i][v_i])会发生变化,所以复用dp)数组转移其实是O1))的,总时间复杂度为On))

具体而言,转移时考虑是否跳过本次操作,于是dp[u_i] = mindp[v_i], dp[u_i] + 1))dp[v_i] = mindp[u_i], dp[v_i] + 1)),注意等式右边的dp)值是原来的dp)值,不是本次更新后的dp)值。注意无法实现的情况。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <typename T>
void readT &x) {
    int s = 0, c = getchar);
    x = 0;
    while isspacec)) c = getchar);
    if c == 45) s = 1, c = getchar);
    while isdigitc)) x = x << 3) + x << 1) + c ^ 48), c = getchar);
    if s) x = -x;
}

template <typename T>
void writeT x, char c = ' ') {
    int b[40], l = 0;
    if x < 0) putchar45), x = -x;
    while x > 0) b[l++] = x % 10, x /= 10;
    if !l) putchar48);
    while l) putcharb[--l] | 48);
    putcharc);
}

const int N = 1e5 + 8;

int n, m, k;

int dp[N];

int mainvoid) {
    int kase; readkase);
    for int ii = 1; ii <= kase; ii++) {
        readn);
        readm);
        readk);
        forint i = 1; i <= n; ++ i)
            dp[i] = -1;
        dp[k] = 0;
        forint u, v, i = 1; i <= m; ++ i){
            readu);
            readv);
            int su = dp[u];
            int sv = dp[v];
            if su == -1 && sv == -1)
                continue;
            if sv == -1){
                dp[u] = su + 1;
                dp[v] = su;
            }
            else if su == -1){
                dp[v] = sv + 1;
                dp[u] = sv;
            }
            else{
                dp[u] = minsu + 1, sv);
                dp[v] = minsv + 1, su);
            }
        }
        forint i = 1; i <= n; ++ i)
            printf"%d%c", dp[i], i == n ? '
' : ' ');
    }
    return 0;
}


D. 萌新 Hdu 6999)

题目大意

给定两个正整数a,b),求最小和最大的c)满足a mod c = b mod c),且2 le c le maxa,b))

不存在则输出-1)

解题思路

假设ageq b),题意即为aequiv b mod c)a-b) equiv 0 mod c)c|a-b)),所以最小c)即为a-b))的最小质因数,最大c)即为a-b))

a-b=1)c)无解$。

a=b)时特判a=1)时无解,否则最小c)2),最大c)a)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <typename T>
void readT &x) {
    int s = 0, c = getchar);
    x = 0;
    while isspacec)) c = getchar);
    if c == 45) s = 1, c = getchar);
    while isdigitc)) x = x << 3) + x << 1) + c ^ 48), c = getchar);
    if s) x = -x;
}

template <typename T>
void writeT x, char c = ' ') {
    int b[40], l = 0;
    if x < 0) putchar45), x = -x;
    while x > 0) b[l++] = x % 10, x /= 10;
    if !l) putchar48);
    while l) putcharb[--l] | 48);
    putcharc);
}

int mainvoid) {
    int kase; readkase);
    for int ii = 1; ii <= kase; ii++) {
        int a, b;
        reada);
        readb);
        int dis = max{a,b}) - min{a, b});
        if dis == 1){
            puts"-1 -1");
        }else if dis == 0){
            if a == 1){
                puts"-1 -1");
            }
            else
                printf"2 %d
", a);
        }else{
            int ans = 2;
            int up = sqrtdis);
            whiledis % ans != 0 && ans <= up)
                ++ ans;
            if dis % ans != 0)
                ans = dis;
            printf"%d %d
", ans, dis);
        }
    }
    return 0;
}


E. 二分 Hdu 7000)

题目大意

n)个格子,你现在在第x)个格子,想跳到第y)个格子。

每次,如果你当前的格子编号小于y),你会等概率跳到比当前编号更大的一个格子中,反之则等概率跳到比当前编号更小的一个格子中。

求期望跳的次数。

解题思路

看上去挺有趣的题,结果被A卡常卡得莫得时间思考,咕咕咕。

神奇的代码
咕咕咕


F. 毒瘤数据结构题 Hdu 7001)

题目大意

一个长为n),初始全为0)的序列,有n)次操作,每次可以:

1 x) 表示把x)位置修改为1)

2 x) 表示查询,如果将x)位置修改为1),求最大的i)满足序列位置1)i-1)上的值均为1)。注意只是如果,实际并不做修改。

解题思路

上来先写的题

其实这并不毒瘤呀,用并查集维护连通性就可以了。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <typename T>
void readT &x) {
    int s = 0, c = getchar);
    x = 0;
    while isspacec)) c = getchar);
    if c == 45) s = 1, c = getchar);
    while isdigitc)) x = x << 3) + x << 1) + c ^ 48), c = getchar);
    if s) x = -x;
}

template <typename T>
void writeT x, char c = ' ') {
    int b[40], l = 0;
    if x < 0) putchar45), x = -x;
    while x > 0) b[l++] = x % 10, x /= 10;
    if !l) putchar48);
    while l) putcharb[--l] | 48);
    putcharc);
}

const int N = 5e6 + 8;

int f[N], n;

int findfaint x){
    return f[x] == x ? x : f[x] = findfaf[x]);
}

int mainvoid) {
    readn);
    forint i = 1; i <= n; ++ i){
        int x, y;
        readx);
        ready);
        if x == 1){
            if f[y] == 0){
                f[y] = y;
                int nxt = findfay + 1);
                if nxt != 0)
                    f[y] = nxt;
                int la = findfay - 1);
                if la != 0)
                    f[la] = f[y];
            }
        }else{
            int ans = findfa1);
            if ans == y - 1)
                ++ ans;
            int nxt = findfay + 1);
            if nxt != 0 && ans >= y)
                ans = nxt;
            ++ ans;
            writeans, '
');
        }
    }    
    return 0;
}


G. 流年烹茶 Hdu 7002)

题目大意

咕咕咕

解题思路

咕咕咕

神奇的代码
咕咕咕


H. 猎人杀 Hdu 7003)

题目大意

n)个人,其中一个是狼人,其余是猎人。

每个人都会有一个想干掉的人的编号列表,是一个1-n)的全排列。

首先狼人干掉自己编号列表的第一人,记为target)

随后,target)会干掉自己列表中,从左到右第一个活着的人,这人会成为新的target),重复此步骤。

如果期间狼人被干掉了,则猎人胜利。

若某一个猎人被干掉后,场上除了狼人还有另一个猎人活着,则狼人胜利。

给定一个局面,问你最终谁胜。

解题思路

就是个模拟题,不过题意写得晦涩难懂。一开始在疑惑就一晚狼人干掉人吗?不过注意到每个人想干掉的列表是个全排列,那么白天就一定会游戏结束了,狼人不会再干掉第二个人。

看样例时看到有狼人自刀的情况出现,嗯???

神奇的代码
#include <bits/stdc++.h>
#include <exception>
#include <vector>
using namespace std;
typedef long long LL;

template <typename T>
void readT &x) {
    int s = 0, c = getchar);
    x = 0;
    while isspacec)) c = getchar);
    if c == 45) s = 1, c = getchar);
    while isdigitc)) x = x << 3) + x << 1) + c ^ 48), c = getchar);
    if s) x = -x;
}

template <typename T>
void writeT x, char c = ' ') {
    int b[40], l = 0;
    if x < 0) putchar45), x = -x;
    while x > 0) b[l++] = x % 10, x /= 10;
    if !l) putchar48);
    while l) putcharb[--l] | 48);
    putcharc);
}

const int N = 55;

bool dead[N];

int cur[N];

int fav[N][N];

int n, lang;

int mainvoid) {
    int kase; readkase);
    for int ii = 1; ii <= kase; ii++) {
        readn);
        forint i = 1; i <= n; ++ i){
            int a;
            reada);
            if a == 1)
                lang = i;
        }
        forint i = 1; i <= n; ++ i)
            forint j = 1; j <= n; ++ j){
                readfav[i][j]);
            }
        forint i = 1; i <= n; ++ i){
            dead[i] = false;
            cur[i] = 1;
        }
        int cnt = n;
        int tar = fav[lang][1];
        dead[tar] = true;
        -- cnt;
        whilecnt > 2 && !dead[lang]){
            whiledead[fav[tar][cur[tar]]])
                ++ cur[tar];
            tar = fav[tar][cur[tar]];
            dead[tar] = true;
            -- cnt;
        }
        if dead[lang])
            puts"lieren");
        else 
            puts"langren");
    }
    return 0;
}


Published by

风君子

独自遨游何稽首 揭天掀地慰生平