2022.2.11 模拟赛 解题报告

翼德天尊 · 2022-02-11 15:39:33 · 个人记录

本场比赛的体验……一言难尽

感觉就是一个 pj 场，但是题意的不完整表述性和不严谨性使难度硬生生的上了一个台阶。

还是分别说一下每一道题吧。

1. \text{Blackoj}

T1 一眼看到 n-1 条关系，从而想到树，再由相邻排斥的关系，联想到某经典树上 dp，设 dp_{i,0} 表示以 i 为根节点的子树中该点不选时最多可以选择的节点数，dp_{i,1} 表示该点选择时最多可以选择的节点数，正常转移即可。

时间复杂度 O(n)，不太明白为什么数据范围这么小（

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 205
int n,head[N],tot,dp[N][2],fa[N];
struct node{
    int to,next;
    node (int to=0,int next=0)
        :to(to),next(next){}
}e[N<<1];
int read(){
    int w=0,f=1;
    char c=getchar();
    while (c>'9'||c<'0'){
        if (c=='-') f=-1;
        c=getchar();
    }
    while (c>='0'&&c<='9'){
        w=(w<<3)+(w<<1)+(c^48);
        c=getchar();
    }
    return w*f;
}
void adde(int u,int v){
    e[++tot]=node(v,head[u]);
    head[u]=tot;
}
void dfs(int u){
    dp[u][1]=1;
    for (int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if (v!=fa[u]){
            fa[v]=u;
            dfs(v);
            dp[u][0]+=max(dp[v][0],dp[v][1]);
            dp[u][1]+=dp[v][0];
        }
    }
}
int main(){
    freopen("blackoj.in","r",stdin);
    freopen("blackoj.out","w",stdout);
    n=read();
    for (int i=1;i<n;i++){
        int u=read()+1,v=read()+1;
        adde(u,v),adde(v,u);
    }
    dfs(1);
    printf("%d\n",max(dp[1][0],dp[1][1]));
    return 0;
}

2. \text{Greatunion}

这道题是一个一眼欧拉回路，当入度为奇数的节点为 0 个或 2 个时可能存在方案，否则不存在。简单建图，以数字为节点，以每个人的两面为边，跑欧拉回路即可。

但值得一提的是，这道题并没有spj，给的样例也是有误的。。。而中间要求也一改再改，导致甚至发生了如下惨案：

以上代码因规则修改在考试结束前半个小时被全部删除（（

幸好最后还是改完了/fad

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 105
int n,in[N],b[N][N],jl[N],tot,g,st,cur[N],cnt=1;
bool vis[N],vis2[N*N];
struct node{
    int x,y;
}p[N];
struct node1{
    int to,next;
    node1 (int to=0,int next=0)
        :to(to),next(next){} 
}e[N*N];
int read(){
    int w=0,f=1;
    char c=getchar();
    while (c>'9'||c<'0'){
        if (c=='-') f=-1;
        c=getchar();
    }
    while (c>='0'&&c<='9'){
        w=(w<<3)+(w<<1)+(c^48);
        c=getchar();
    }
    return w*f;
}
void dfs(int now){
    jl[++tot]=now;
    for (int i=cur[now];i;i=cur[now]){
        cur[now]=e[i].next;
        int v=e[i].to;
        if (vis2[i]==1) continue;
        vis2[i]=1,vis2[i^1]=1;
        in[v]--,in[now]--;
        dfs(v);
    }
}
void adde(int u,int v){
    e[++cnt]=node1(v,cur[u]);
    cur[u]=cnt;
}
int main(){
  freopen("greatunion.in","r",stdin);
  freopen("greatunion.out","w",stdout);
    n=read();
    for (int i=1;i<=n;i++){
        p[i].x=read()+1,p[i].y=read()+1;
        in[p[i].x]++,in[p[i].y]++;
    }
    for (int i=n;i>=1;i--){
        adde(p[i].x,p[i].y),adde(p[i].y,p[i].x);
    }
    for (int i=1;i<=7;i++)
        if (in[i]&1) g++;
    if (g>2){
        printf("No Solution");
        return 0;
    }else if (g==0) st=p[1].x;
    else
        for (int i=1;i<=n;i++)
            if (in[p[i].x]&1){
                st=p[i].x;
                break;
            }else if (in[p[i].y]&1){
                st=p[i].y;
                break;
            }
    dfs(st);
    for (int i=1;i<=7;i++)
        if (in[i]){
            printf("No Solution");
            return 0;
        }
    for (int i=1;i<tot;i++){
        for (int j=1;j<=n;j++){
            if (vis[j]) continue;
            bool flag1=(jl[i]==p[j].x&&jl[i+1]==p[j].y),flag2=(jl[i]==p[j].y&&jl[i+1]==p[j].x);
            if (flag1||flag2){
                printf("%d ",j);
                vis[j]=1;
                if (flag1) puts("+");
                else if (flag2) puts("-");
                break;
            }
        }
    }
    return 0;
}

3. \text{King}

这道题题意实在有些模糊了，，至少我是没有太理解，题面大概可以看懂，但是样例完全不知道为什么要输出 2 1，感觉应该是 3 4 才对啊%%%

也没有样例解释（

直接弃掉了

4. \text{Smallunion}

小清新板子 dp 题。

因为每次使用治疗糖豆时可以清空之前的贡献，所以我们完全可以将每次使用治疗糖豆的地方到上一个使用的地方的后一位为一个区间单独考虑答案，就可以很容易的写出一个 dp 方程。

设 dp_{i,k} 表示吃了前 i 个“教授糖豆”，使用了 k 个 “治疗糖豆”时，最小的破坏值。

转移方程为：

其中 1\le j \le i-1。

关于 p 数组的计算，我们可以 O(n^2) 前缀和预处理，即可在 O(n^2k) 的时间复杂度内解决本题。