1.21闲话暨模拟赛题解

未卜先知

推歌： 二重变革/洛天依,言和 by DELA

上午写了模拟赛，下午不给我发代码不让我改题不让我看题面，smjb

模拟赛一共9道题，4道原题(2道原题，2道"原"题)，抛去3道不写的一共6道题

• T1「尘世闲游」(原神题)

  没让写

• T2「一心净土」(原神题&&原题「CF740C」)

  • 题解

    我这里一共找到两种解法

    • 第一种(考场解法)

      首先对所有雷电将军的询问去进行离线然后按照区间长度去排序

      排序之后直接对判断查看那些数已经被填，按照++tot的顺序填没填过的数

      (不确定能不能100pts，但是造的几组hack都过了)

    • 第二种

      直接找到最小的区间，mex就是最小的区间长度+1，然后直接循环往复的填\([\) \(0 \sim\) 区间长度 \(]\) 就行

      #include<bits/stdc++.h>
      #define int long long
      inline int read(){
          int f=1,s=0;char ch=getchar();
          while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}
          while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
          return f*s;
      }
      using namespace std;
      const int INF=0x66CCFF;
      signed main(){
          int n,m,l,r,mex=INF;
          cin>>n>>m;
          while(m--){
              cin>>l>>r;
              mex=min(mex,r-l+1);
          }
          for(int i=1;i<=n;++i)
              cout<<i%mex<<" ";
      }
      

• T3 「小L玩红警」

  • 题解

    考场上貌似很多人都读错了题目？

    • 40pts

      应该读错题的都是这个分数了

      作为微操大师，小L当然可以一只手指控制多辆坦克啦，怎么可能只能控制一个

      类比：双指解四押

    • 50pts

      观察题面发现对于 \(50\%\) 的数据 \(n \le 10\) ,直接大力搜索即可

    • 100pts

      先咕咕咕了

• T4 「最大生成树」

  • 题解

    • 70pts

      直接对其建图，跑最大生成树，然后因为\(O(n^2)\)的建图导致死了

    • 100pts

      完全图所以直接去找到最大和最小的节点分别做根，然后连上所有节点之后把边权相加求出这两个里较大的即可

• T5 「括号战争」

  • 题解

    根据\(\textbf {K8He}\)之言，本题为区间DP，但是疑似不用

    进行一个模拟，若读入的是 \((\) 则直接在数组里存入 \(1\) ， \([\) 则存入 \(2\)

    在存入 \()\) 时去找到存入的 \(1\) ，如果没有就存入 \(3\)

    存入 \(]\) 时类比上面即可

    最后扫一遍数组输出剩余的个数即可，时间复杂度\(O(|S|^2)\)可以通过此题

• T6 「校门外的树」

  • 题解

    • 30pts做法

      • 做法1

        唐氏做法，肯定要用线段树维护，按照正常的思路维护区间加和区间求和，然后发现很难用lazy标记维护grow，那么直接一直grow(1,i,i)

        复杂度\(O(m \log n + mn \log n)\)，不如暴力

      • 做法2

        直接对其进行数组模拟即可

    • 50pts做法

      离线所有询问看有没有修改操作，特判没有的情况，如果没有就grow(1,1,n)然后带lazy，有就grow(1,i,i)即可

      复杂度对于\(80\%\)的数据\(O(m \log n + mn \log n)\)，对于\(20\%\)的数据\(O(m \log n)\)

    • 100pts做法

      • 做法1？

        线段树这么难维护，那么为啥不分块呢？

        考虑一个简单的做法，首先对数列进行分块

        然后每次操作前都对其进行一个grow操作，此处只在块上修改，附带一个总体的time++

        接下来的操作都比较板，只要在增加的时候让块内的所有都\(time\)降为\(0\)同时乘上\(time*v_i\)即可

        在查询时直接查块，若查小块就直接让time降到0然后乘上\(time*v_i\)即可

        复杂度 \(O(m \sqrt n)\) 疑似可以通过此题，但是考场上没写完不知道

      • 做法2

        观察分块的思路发现可以直接搬到线段树上，复杂度\(O(m \log n)\)可以通过此题

• T7 「异或(xor)」

  • 50pts 做法

    按照题意模拟即可

  • 60pts 做法

    按照题意模拟+特判即可

  • 100pts 做法

    我想到两个做法，但是没写完

    • 二维树状数组

      不会写

    • 线段树套线段树

      树套树太难写了，刚写了个动态开点就死了没写完

      看出来树套树之后就是比较板的题了应该

• T8 「」

  没让写，题目居然是东方，还出现了帕秋莉和十六夜咲夜

• T9 「」

  没让写