• 2024年7月24日
• 分类于 模拟赛记录
• 需要 6 分钟阅读时间

2024.7.24 模拟赛记录

T1 - 采果子

采果子

Sol

注意到图是完全图，且我们只能从果子数低向果子数高走，因此先考虑将其按照 \(a[i]\) 从小到大排序，这样之后再进行操作可以确保无后效性

考虑 \(dp\)；题目问什么就设什么，尝试设 \(dp[i][j]\) 表示走到第 \(i\) 棵树 还剩 \(j\) 小时，同时 摘走第 \(i\) 棵树的果子 能获得的最大价值；其实转移比较类似 \(01\) 背包，考虑枚举当前第 \(i\) 棵树与容量 \(j\)，再枚举前面的某一棵树 \(k\)，转移即为从 \(k\) 走到 \(i\)；因此，转移方程为 \(dp[i][j]=dp[k][j-dis[k][i]-c[i]]+s[i]\)，其中 \(c[i]\) 表示摘第 \(i\) 棵树上果子的时间，\(s[i]\) 表示摘第 \(i\) 棵树上果子的价值

注意，因为我们可以从任何一棵树开始，比较方便的一种处理方法是建立一个超级原点 \(0\)，自身的所有信息都是 \(0\)，再向所有树都连一条权值为 \(0\) 的边

对于初值，直接赋 \(0\) 即可，因为浪费了一些时间的初始情况一定比不浪费是更劣的，不会对答案造成影响；对于答案，我们枚举每个状态，取最大值即可

时间复杂度 \(O(n^2m)\)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 105, MAXM = 1005, INF = 1e9;

int n, m;
ll ans;
ll d[MAXN][MAXN];
ll dp[MAXN][MAXM];

struct Tree{
    ll a, s, c, id;
}tree[MAXN];

bool cmp(Tree t1, Tree t2){
    return t1.a < t2.a;
}

int main(){
    scanf("%d%d", &n, &m);

    for (int i=1; i<=n; i++){
        scanf("%lld%lld%lld", &tree[i].a, &tree[i].s, &tree[i].c);
        tree[i].id = i;
    }
    for (int i=1; i<=n; i++){
        d[0][i] = 0;
        for (int j=1; j<=n; j++){
            scanf("%lld", &d[i][j]);
        }       
    }
    tree[0].a = tree[0].s = tree[0].c = tree[0].id = 0;
    sort(tree, tree+n+1, cmp);

    for (int i=0; i<=n; i++){
        for (ll j=m; j>=0; j--){
            for (int k=0; k<i; k++){
                if (j >= d[tree[k].id][tree[i].id]+tree[i].c && tree[k].a<tree[i].a){
                    dp[i][j] = max(dp[i][j], dp[k][j-d[tree[k].id][tree[i].id]-tree[i].c]+tree[i].s);
                }   
            }
        }
    }
    for (int i=1; i<=n; i++){
        for (int j=0; j<=m; j++){
            // cout << i << " " << j << " " << dp[i][j] <<endl;
            ans = max(dp[i][j], ans);
        }
    }

    printf("%lld", ans);
    return 0;
}

Record

别被图论限制了思路啊，这个 \(dp\) 还是比较明显的；现在 \(dp\) 的水平真的太差了，得多练。

T2 - 非常计划

非常计划

Sol

玩文字游戏是比较难评的……

最短路计数板子，注意 有重边就取最小值，这是由于所有边完全重合只算一次，因此有多条重边对结果没有影响；因为要取最小值，用邻接矩阵会比较方便，\(O(n^2)\) 是可以接受的

时间复杂度 \(O(n^2)\)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 2005, INF = 1e9;

int N, M;

struct Edge{
    int to;
    int weig;
};

int G[MAXN][MAXN];
int dis[MAXN], vis[MAXN];
ll cnt[MAXN];

void dijkstra(int start){
    memset(dis, 0x7f, sizeof(dis));
    dis[start] = 0;
    cnt[start] = 1;

    for (int i=1; i<=N; i++){
        int recent = 0, recentmin = INF;
        for (int j=1; j<=N; j++){
            if (vis[j] == false && dis[j] < recentmin){
                recent = j;
                recentmin = dis[j];
            }   
        }
        vis[recent] = true;
        for (int j=1; j<=N; j++){
            if (G[recent][j] != INF){
                if (dis[j] >= dis[recent]+G[recent][j]){
                    if (dis[j] == dis[recent]+G[recent][j]){
                        cnt[j] += cnt[recent];
                    }
                    else{
                        dis[j] = dis[recent]+G[recent][j];
                        cnt[j] = cnt[recent];
                    }
                }
            }
        }   
    }
}

int main(){
    scanf("%d%d", &N, &M);

    for (int i=1; i<=N; i++){
        for (int j=1; j<=N; j++){
            G[i][j] = INF;
        }
    }

    for (int i=1; i<=M; i++){
        int node1, node2, weig;
        scanf("%d%d%d", &node1, &node2, &weig);
        G[node1][node2] = min(G[node1][node2], weig);
    }

    dijkstra(1);

    if (dis[N] > INF){
        printf("No answer");
        return 0;
    }
    printf("%d %lld", dis[N], cnt[N]);
    return 0;
}

Record

\(what\ can\ I\ say?\) 抽象艺术出题人

T3 - 方程的解

P1771

Sol

首先，\(g(x)\) 可以直接上快速幂解决，即为求不定方程 \(\sum_{i=1}^k a_i= p\) 解的数量，\(p\) 是定值

题目要求 \(a_i (1 \le i \le k)\) 为正整数，即将 \(p\) 划分为 \(k\) 个正整数相加，这就是经典插板法；在 \(p-1\) 个空隙中插 \(k-1\) 个板，答案即为 \(C_{p-1}^{k-1}\)，别忘了上高精度，\(k\) 很小，一个一个乘完再一个一个除即可

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD = 1000, MAXL = 5e3+5;

int k, x, bas;
int ans[MAXL];

int QuickPow(int a, int b){
    ll res = 1;
    while (b){
        if (b&1) res = (res*a)%MOD;
        a = (a*a)%MOD;
        b >>= 1;
    }
    return res;
}

void mul(int x){
    int i;
    for (i=1; i<=5e3; i++){
        ans[i] = ans[i]*x;
    }
    for (i=1; i<=5e3; i++){
        ans[i+1] += ans[i]/10;
        ans[i] = ans[i]%10;
    }
}

void div(int x){
    int i, len, m;
    for (len=5e3; ans[len]==0&&len>=1; len--);  
    for (i=len, m=0; i>=1; i--){
        int tmp = ans[i];
        ans[i] = (m*10+tmp)/x;
        m = (m*10+tmp)%x;
    }
}

void prt(){
    int i;
    for (i=5e3; ans[i]==0&&i>1; i--);
    for (; i>=1; i--){
        printf("%d", ans[i]);
    }
}

int main(){
    scanf("%d%d", &k, &x);
    bas = QuickPow(x%MOD, x)-1;

    ans[1] = 1;
    for (int i=0; i<k-1; i++){
        int recent = bas-i; 
        mul(recent);
    }
    // prt();
    // cout << endl;
    for (int j=2; j<=k-1; j++){
        div(j);
    }
    prt();
    return 0;
}

Record

高精度不能忘啊，高精除单精还是得会的（

T4 - 染色

P3177

Sol

答案即求 \(\sum_{color} \sum_{1 \le i < j \le n} \sum_{e \in \delta(i, j)} w(e)\)，其中 \(i\) 与 \(j\) 都染了 \(color\) 这一颜色，\(\delta(i, j)\) 表示 \(i\) 与 \(j\) 间的简单路径；我们尝试求和换序，即求 \(\sum_{e \in tree} w(e) \sum_{color} \sum_{1 \le i < j \le n}\)，其中 \(\delta(i, j)\) 包含 \((s, t)\)；因此转化为统计 树上有多少同色点经过一条边

考虑记录 \(dp[i][j]\) 表示节点 \(i\) 的子树内有 \(j\) 个点染成黑色的最大贡献；对于当前节点 \(i\) 与其的一个孩子 \(child\)，设在 \(child\) 中选 \(k\) 个点染黑，则边 \((i, child)\) 会产生两部分贡献；黑色点的贡献为 \(k \times (m-k) \times w(e)\)，白色点的贡献为 \((siz[child]-k) \times (n-siz[child]-(m-k)) \times w(e)\) 其中 \(siz\) 表示子树大小；两部分加起来即为该边产生的贡献，记为 \(val\)；

设在当前节点 \(i\) 选 \(j\) 个染黑，在儿子 \(child\) 中选 \(k\) 个点染黑，则转移方程为 \(dp[i][j] = max(dp[i][j-k]+dp[child][k]+val)\)；注意需要倒序枚举 \(j\)，否则会产生重复贡献，与 \(01\) 背包滚动数组的原理类似

注意 \(int \times int\) 时爆 \(long long\)

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 2005, MAXM = 2005;

int n, m;

struct Edge{
    int to;
    int weig;
};

vector <Edge> G[MAXN];
ll dp[MAXN][MAXM];
int siz[MAXN];

void dfssiz(int node, int fa){
    siz[node] = 1;
    for (int i=0; i<G[node].size(); i++){
        if (G[node][i].to == fa) continue;
        dfssiz(G[node][i].to, node);
        siz[node] += siz[G[node][i].to];        
    }
}

void dfs(int node, int fa){
    dp[node][0] = dp[node][1] = 0;
    for (int i=0; i<G[node].size(); i++){
        if (G[node][i].to == fa) continue;
        dfs(G[node][i].to, node);
        for (int j=min(siz[node], m); j>=0; j--){
            for (int k=0; k<=min(siz[G[node][i].to], j); k++){
                if (dp[node][j-k] == -1) continue;
                ll cnt = ((siz[G[node][i].to]-k)*(n-siz[G[node][i].to]-(m-k)))*(ll)G[node][i].weig + k*(m-k)*(ll)G[node][i].weig;
                dp[node][j] = max(dp[node][j], dp[node][j-k]+dp[G[node][i].to][k]+cnt);
            }
        }
    }
}

int main(){
    scanf("%d%d", &n, &m);

    for (int i=1; i<=n-1; i++){
        int node1, node2, weig;
        scanf("%d%d%d", &node1, &node2, &weig);
        G[node1].push_back({node2, weig});
        G[node2].push_back({node1, weig});
    }

    memset(dp, -1, sizeof(dp));

    dfssiz(1, 1);
    dfs(1, 1);

    printf("%lld", dp[1][m]);
    return 0;
}

Record

这 \(dp\) 向来是会不了一点的；考场上注意读题！写链的部分分的时候糊的 \(dp\) 只考虑了一种颜色的点，什么实力（