nowcoder提高第六场

比赛总结

T1

80暴力->0分。
当时判断一个点是否能访问到：dis[i]!=-1，这样是不对的！！！
因为可能一个点在环上，这个点的dis会被更新！！！

正解：路径最大直接反图上拓扑，顺便判了环（一个点在不在环上不能用dis判！！！）主要是比较路径的字典序最小。
可以倍增加hash找到第一个不同的字符，然后比较大小。
还有一种更为简单的方法：记录拓扑中每一层的点，从小的层数往大的扫，每扫到一个点，在原图中找到它连向的点，确定从哪个点转移。
每个点记录一个pair第一关键字为这条边的权值，第二关键字为前面n-1条边合起来的排名。从一层到下一层的时候，假设我们当前知道了当前层的每个点排名r2，然后下一层的排名就是让这一层到下一层的边上的字符作为第一关键字r1，然后对这个pair排序。第一层的pair当然是(w,0)，w为与第0层边上的权值。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
#define pa pair<int,int>
#define mp make_pair
const int N = 1000005;
const int mod = 998244353;
int q[N], deg[N], dis[N], rnk[N], ans[N];
bool vis[N];
vector<int> vec[N];
pa a[N];
struct Edge{
    int head[N], to[N], nxt[N], w[N], En;
    inline void add_edge(int u,int v,int c) {
        ++En; to[En] = v; w[En] = c; nxt[En] = head[u]; head[u] = En;
    }
}G, R;
inline bool cmp(int i,int j) { return a[i] < a[j]; }
int main() {
    int n = read(), m = read();
    for (int i=1; i<=m; ++i) {
        int u = read(), v = read(), w = read();
        G.add_edge(u, v, w); R.add_edge(v, u, w); deg[u] ++;
    }
    int l = 1, r = 0;
    for (int i=1; i<=n; ++i) if (!deg[i]) q[++r] = i;
    while (l <= r) {
        int u = q[l ++];
        vis[u] = true;
        vec[dis[u]].push_back(u);
        a[u] = mp(2e9, 0);
        for (int i=R.head[u]; i; i=R.nxt[i]) {
            int v = R.to[i];
            dis[v] = max(dis[v], dis[u] + 1);
            if (!(--deg[v])) q[++r] = v;
        }
    }
    pa tmp;
    for (int i=1; i<=n; ++i) {
        if (!vec[i].size()) break;
        for (int j=0,sz=vec[i].size(); j<sz; ++j) {
            int u = vec[i][j];
            for (int i=G.head[u]; i; i=G.nxt[i]) {
                int v = G.to[i];
                tmp = mp(G.w[i], rnk[v]);
                if (dis[u] == dis[v] + 1 && tmp < a[u])
                    a[u] = tmp, ans[u] = (1ll * (ans[v] + a[u].first) % mod * 29) % mod;
            }
        }
        sort(vec[i].begin(), vec[i].end(), cmp);
        for (int j=0, sz=vec[i].size(); j<sz; ++j) rnk[vec[i][j]] = j;
    }
    for (int i=1; i<=n; ++i) {
        if (vis[i]) printf("%d\n",ans[i]);
        else puts("Infinity");
    }
    return 0;
}

T2

课件讲的挺详细的。
1、考虑计算每个人的贡献，就是$\sum\limits_{mx}\sum\limits_{cx} \times p_x( mx, cx)$就是当前mx的情况下，x选了cx的贡献，$cnt[mx]>\frac{n}{2}$

2、考虑如何计算$p_x(mx,cx)$。
$f_x(mx,cnt)$表示除了x这个人，其他人选了cnt个mx的贡献。
那么就可以如下求出p

3、考虑如何计算f数组：显然可以背包。所以可以对n个人都进行一次$O(n^2)$的背包，总复杂度$O(n^3)$。
正解：一个叫做“退背包”的东西，就是知道了考虑n个人后的数组，去掉一个人后的f数组。
$dp'$是加入一个数后的数组，dp0是以前的数组，那么又转移方程：

去掉一个数的dp数组就是：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 2005;
const int mod = 998244353;
LL P[N][5], w[N][5], f[N], g[N], ans[N], n;
int INV(int x) {
    int b = mod - 2, res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * x % mod;
        x = 1ll * x * x % mod;
        b >>= 1;
    }
    return res;
}
void solve(int mx) {
    memset(f, 0, sizeof(f));
    f[0] = 1;
    for (int i=1; i<=n; ++i) {
        int p = P[i][mx];
        for (int j=i; j; --j) 
            f[j] = (1ll * p * f[j - 1] % mod + 1ll * (1 - p) * f[j] % mod) % mod;
        f[0] = 1ll * (1 - p) * f[0] % mod;
    }
    for (int i=1; i<=n; ++i) {
        int p = P[i][mx];
        if (p == 1) { // 一定选的时候 
            for (int j=0; j<n; ++j) g[j] = f[j + 1];
            g[n] = 0;
        } else { // 可以不选 
            int inv = INV((1 - p + mod) % mod);
            g[0] = 1ll * inv * f[0] % mod;
            for (int j=1; j<=n; ++j) g[j] = 1ll * inv * (f[j] - p * g[j - 1] % mod + mod) % mod;
        }
        LL sum = 0;
        for (int j=(n>>1)+1; j<=n; ++j) sum += g[j]; sum %= mod;
        for (int j=1; j<=4; ++j) 
            (ans[i] += 1ll * w[mx][j] * P[i][j] % mod * (sum + (mx == j ? g[n >> 1] : 0))) %= mod;
    }
}
int main() {
    n = read();
    for (int i=1; i<=n; ++i) 
        for (int j=1; j<=4; ++j) P[i][j] = read();
    for (int i=1; i<=4; ++i) 
        for (int j=1; j<=4; ++j) w[i][j] = read();
    for (int mx=1; mx<=4; ++mx) solve(mx);
    for (int i=1; i<=n; ++i) printf("%d\n",(ans[i] + mod) % mod);
    return 0;
}