2019.8.1 集训解题报告
浏览 45 | 评论 0 | 字数 7627
Snowflake_Pink
2019年08月01日
  • Luogu P1801 黑匣子

    这道题是分在试炼场的”堆“模块里面,太菜了,没有想出来。

    看了题解后也感觉自己想到边了,既然是求第 $k$ 小,那么对于堆这么一个堆顶是 最大/最小 的一个结构来说,应该要用一个堆直接储存目前的前 $k$ 小,那么,在输出的时候,只需要输出堆顶就可以了。所以,这样就可以很自然的想到要用两个堆,一个堆 $A$,用作前面的用途,另一个堆 $B $要储存当前,前 $k$ 小以外的其他数据。每次 $Get$ 一次后,就要把 $A$ 的大小扩大 1 个,保证堆顶永远是第 $k$ 小。

    然后我们就可以得到一个似乎叫对顶堆的东西,如图:

    对顶堆

    把这两个堆这样放,就更好理解了,我们每次 $push$ 时,只需要维护中间两个堆顶,使这一整个对顶堆保持类似堆得性质(从下往上依次 变大/变小)。

    维护两个堆顶非常简单,只需要判断两个堆顶的大小是否合法即可,不合法就交换,一直到合法。

    Code:

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <queue>
    using namespace std;
    const int MAXN=2e5+5;
    int m,n,a[MAXN],u[MAXN],cnt_a,cnt_u=1;
    int main(){
        priority_queue<int>A;
        priority_queue<int , vector <int> , greater <int> >B;
        scanf ("%d%d",&m,&n);
        for (int i=1;i<=m;i++)
            scanf ("%d",&a[i]);
        for (int i=1;i<=n;i++)
            scanf ("%d",&u[i]);
        for (cnt_a=1;cnt_a<=m;cnt_a++){
            while (cnt_a-1==u[cnt_u]){
                cnt_u++;
                int t=B.top();
                B.pop();
                A.push(t);
                printf ("%d\n",A.top());
            }
            B.push(a[cnt_a]);
            if (A.empty()) continue; 
            while (A.top()>B.top()){
                int t=B.top();
                B.pop();
                B.push(A.top());
                A.pop();
                A.push(t);
            }
        }
        while (cnt_a-1==u[cnt_u]){
            cnt_u++;
            int t=B.top();
            B.pop();
            A.push(t);
            printf ("%d\n",A.top());
        }
        return 0;
    }
    • 代码写的非常丑,当然这道题可以使用平衡树,用 $Treap$ 就绰绰有余了。

    考试

    • 有三道题,如果我题目没有看错的话,应该不是特别毒瘤等我看完考试成绩后再说),

    水叮当的舞步

    水叮当的舞步

    题目里面已经提到联通块了,所以用 $dfs$ 或者 $bfs$ 求出每种颜色联通块的个数。看到分数后,又去看了下 $data$ ,然后我发现看题看错了 $qwq$

    Update(2019.8.14)

    看完题解之后:A 组我 cnm!

    要用 迭代加深启发式搜索 。。。。。

    nmsl。。。

    就记一下纪中的题解:等我学完了什么 $IDA*$ 、估价函数再回来写这道题......

    Solution From $lydrainbowcat$
    类型:IDA* (迭代加深启发式搜索)

    1. 枚举每次选取了哪种颜色,然后找出左上角的格子所在的联通块,改变颜色。
      为了避免来回改变、搜索深度过大,采用迭代加深的 $dfs$ 限制搜索步数。

    迭代加深也就是,依次限制搜索深度为 0、1、2、3…… 进行搜索,搜索过程中发现深度超过限制就马上退出。只要搜索成功就找到了答案,也可以立即退出。

    • 期望得分:0~10分。
    1. 加入一个小剪枝:如果改变颜色后,左上角格子所在的联通块大小没有改变,可以剪枝。这样可以避免来回往复地搜索。

      • 期望得分:10~20分。
    2. 采用 $IDA*$ 算法,设计估价函数。可以发现如果当前矩阵中除了左上角的联通块之外,共有 $M$ 种颜色,那么还需要的步数不小于 $M$。因此如果当前搜索深度 $+$ 估价函数的值 $>$ 深度限制,可以回溯。

      • 期望得分:50~70分。
    3. 我们可以发现,每次寻找左上角的格子所在的联通块耗费的时间常数巨大。因此我们在这里寻求突破。
      我们引入一个 $N \times N$的 $v$ 数组。左上角的格子所在的联通块里的格子标记为 1。左上角联通块周围一圈格子标记为 2,其它格子标记为 0。如果某次选择了颜色 $c$ ,我们只需要找出标记为 2 并且颜色为 $c$ 的格子,向四周扩展,并相应地修改 $v$ 标记,就可以不断扩大标记为 1 的区域,最终如果所有格子标记都是 1,那么显然找到了答案。

      • 期望得分:90~100分。

    Vani 和 Cl2 捉迷藏

    写了一个 20 分的,然后就超时了。

    先用 $Floyd$ 跑一遍题目中的 $DAG$,然后就可以得到一个被补完的邻接矩阵。这个时候,就可以知道任意两点之间的联通关系。最简单粗暴的方法就是我考场上写个 $dfs$ ,依次判断是否完全互不相连就可以了,但是只有 20 分。

    因此,我们就可以把这样的图看做二分图来匹配,最大匹配就是最多能选出多少个点相连。似乎最简单的就是匈牙利算法,以前学过,但是我忘了 qwq。需要一个公式:

    $$ DAG的最小路径覆盖数=DAG图中的节点数-相应二分图中的最大匹配数 $$

    这里是 $DAG$ 普通的有向图不是这样的,然后就可以了。

    后面因为不服我的代码,后面发现,因为考试时有个队列因为怕爆,加了一个次方,后面减去之后,分数直接到 60 。看来以后没有用的东西就不要去做了 $qwq$ 。

    $Test's$ $Code$:60%

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    using namespace std;
    const int MAXN = 2e2+5;
    const int MAXM = 3e4+5;
    const int MAXQ = 2e6+5;
    struct Edge{
        int v,next;
    }edge[MAXM];
    bool flag[MAXN][MAXN],bz[MAXN];
    int cnt,ans,head[MAXN],m,n,Max;
    int que[MAXN],tail;
    inline void AddEdge(int u, int v){
        cnt++;
        edge[cnt].v=v;
        edge[cnt].next=head[u];
        head[u]=cnt;
        return;
    }
    void dfs1(int u){
        for (int i=head[u];i!=0;i=edge[i].next){
            int v=edge[i].v;
            for (int j=1;j<=tail;j++){
                int t=que[j];
                flag[t][v]=true;
            }
            que[++tail]=v;
            dfs1 (v);
            tail--;
        }
        return;
    }
    void dfs2 (int u){
        for (int i=1;i<=n;i++){
            if (i==u) continue;
            if (bz[i]) continue;
            bool check=false;
            for (int j=1;j<=tail;j++){
                int t=que[j];
                if (flag[i][t]||flag[t][i]){
                    check=true;
                    break;
                }
            }
            if (check) continue;
            ans++;
            Max=max(Max,ans);
            bz[i]=true;
            que[++tail]=i;
            dfs2(i);
            tail--;
            ans--;
            bz[i]=false;
        }
        return;
    }
    int main(){
        scanf ("%d%d",&n,&m);
        for (int i=1;i<=m;i++){
            int u,v;
            scanf ("%d%d",&u,&v);
            AddEdge(u,v);
        }
        for (int i=1;i<=n;i++){
            memset(que,0,sizeof (que));
            tail=0;
            que[++tail]=i;
            dfs1(i);
        }
        for (int i=1;i<=n/2+1;i++){
            memset(que,0,sizeof (que));
            ans=1;
            tail=0;
            bz[i]=true;
            que[++tail]=i;
            dfs2 (i);
            bz[i]=false;
        }
        printf ("%d\n",Max);
        return 0;
    }

    $Fixed$ $Code$:100%

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    using namespace std;
    const int MAXN = 2e2+5;
    bool flag[MAXN][MAXN],bz[MAXN];
    int ans,m,n;
    int link[MAXN];
    int find (int x) {
        for (int i=1;i<=n;i++) {
            if (!flag[i][x]) continue;
            if (bz[i]) continue;
            bz[i]=true;
            if (!link[i]||find(link[i])){
                link[i]=x;
                return 1;
            }
        }
        return 0;
    }
    int main(){
        scanf ("%d%d",&n,&m);
        for (int i=1;i<=m;i++){
            int u,v;
            scanf ("%d%d",&u,&v);
            flag[u][v]=true;
        }
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                for (int k=1;k<=n;k++)
                    if (flag[i][k]&&flag[k][j]&&i!=j)
                        flag[i][j]=true;
        for (int i=1;i<=n;i++){
            memset(bz,0,sizeof (bz));
            ans +=find (i);
        }
        printf ("%d\n",n-ans);
        return 0;
    }
    • 我写的果然又臭又长

    三、粉刷匠(集体照)

    写了个暴力,没想到暴力的 40 分成了 3 道题目中分最高的 $qwq$

    一看数据就知道是 $dp$ 或者数学,当然不可能是数学啦~

    所以用 $dp$ ,设状态:$f[i][j]$ 为用完 $i$ 个颜料后,有 $j$ 个不合法情况的状态。

    那么当我们要使用下一个颜料 $i$ 的时候,把 $a[i]$ 份颜料分为 $k$ 组,把 $t$ 组放在原来不合法的 $j$ 个空上(这样就可以把它们隔开,就合法了)。

    至此,就可以列出一个方程:

    $$ f[i][j - t + a[i] - k]=f[i-1][j] \times C_{a[i]-1}^{k-1} \times C_j^t \times C_{s[i]+1-j}^{k-t} $$

    $C_{a[i]-1}^{k-1}$:在 $a[i]$ 中选出 $k$ 组的情况个数,使用隔板法,小奥知识即可。

    $C_j^t$:在 $j$ 个不合法的空中选出 $t$ 个的情况个数。

    $C_{s[i]+1-j}^{k-t}$:在剩下的空中把没有用完的补上的情况个数。

    Update(2019.8.12)

    打完代码后顺便记一下求组合的方法:

    inline void Init_C () {
        c[0][0] = 1;
        for (long long i = 1; i <= 100; i++) {
            c[i][0] = 1;
            for (long long j = 1; j <= i; j++) {
                c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % Mod;
            }
        }
        return;
    }

    还有这道题要开 long long qwq

    $Fixed$ $Code$:100%

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    const long long Mod = 1e9 + 7;
    const long long MAXN = 20;
    const long long MAXM = 105;
    
    long long n, a[MAXN], s[MAXN], c[MAXM][MAXM];
    long long f[MAXN][MAXM];
    
    inline void Init() {
        memset(s, 0, sizeof (s));
        memset(f, 0, sizeof (f));
        return;
    }
    
    inline void Init_C () {
        c[0][0] = 1;
        for (long long i = 1; i <= 100; i++) {
            c[i][0] = 1;
            for (long long j = 1; j <= i; j++) {
                c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % Mod;
            }
        }
        return;
    }
    
    int main(){
        Init_C ();
        
        long long T;
        scanf ("%lld", &T);
        while (T--) {
            Init ();
            
            scanf ("%lld", &n);
            for (long long i = 1; i <= n; i++) {
                scanf ("%lld", &a[i]);
            }
            
            for (long long i = 1; i <= n; i++) {
                s[i] = s[i - 1] + a[i];
            }
            
            f[0][0] = 1;
            for (long long i = 1; i <= n; i++) {
                for (long long j = 0; j <= s[i - 1]; j++) {
                    for (long long k = 1; k <= a[i]; k++) {
                        for (long long t = 0; t <= min (k, j); t++) {
                            f[i][j - t + a[i] - k] += ((f[i - 1][j] * c[a[i] - 1][k - 1] % Mod) * (c[j][t] * c[s[i - 1] + 1 - j][k - t] % Mod)) % Mod;
                            f[i][j - t + a[i] - k] %= Mod;
                        }
                    }
                }
            }
            
            printf ("%lld\n", f[n][0]);
        }
        return 0;
    }

    总结

    这么多天以后,我竟然在 8 月 12 日,把第 3 题做出来了 qwq

    A 组的人都是神仙,打死我也不去 A 组 > _ <

    本文作者:Snowflake_Pink
    本文链接:https://snowflake.pink/archives/76/
    最后修改时间:2020-04-14 08:57:32
    本站未注明转载的文章均为原创,并采用 CC BY-NC-SA 4.0 授权协议,转载请注明来源,谢谢!
    评论
    评论会由可爱的 AI 来审核鸭~
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论