Day 4 高中部寒假集训
浏览 82 | 评论 0 | 字数 7817
Snowflake_Pink
2019年01月26日
  • Day4:

    先放课程表:

    2019.1.25

    上午
    • 讲解订正$Day3$晚上考试的题目。
    下午
    • 图论: RMQ问题LCA问题ST表
    晚上
    • 考试:动态规划

    考试(选讲)

    • 时空限制:1000ms/128MB
    1. 幻方(sqr.cpp/sqr.in/sqr.out):

      • 题目描述:求出第$k$个按照字典序排序的$4*4$幻方。
      • 输入格式:一个正整数$k$。
      • 输出格式:一个4*4的幻方矩阵。
      • 输入样例:

      1

      • 输出样例:

      1 2 15 16

      12 14 3 5

      13 7 10 4

      8 11 6 9

      • 数据范围:$1 \leq k \leq 100$
      • 分析:这是一道基础的搜索题,没错,我爆0了,样例都没过。我搜索题都写得挺丑的,根本无法$debug$。这题主要考剪枝(我都剪了3个枝了为什么1min都没能弄出来?!),对于一行,填完前三个数,第四个数直接用34($\frac{1+2+3+....+16}{4}=34$)减去前三个数之和即可得到;对于最后一行,直接由34减去前三行对应数之和得到。对于每一次$dfs$,如果该行之和已超过34,直接retrun(在My Classmate's Code中没有用到这一剪枝)。
      • My Classmate's Code:
      #include <bits/stdc++.h>
      using namespace std;
      int used[17];  
      int k;
      int ary[4][4];
      int found=0;
      void print(){
          int i,j;
          for (i=0;i<4;i++){
              for(j=0;j<3;j++){
                  cout<<ary[i][j]<<" ";
              }
              cout<<ary[i][3]<<endl;;
          }
          return;
      }
      
      void dfs(int n) {
          int x= n/4,y=n%4;
          int i;
          if (found) return;
          if (n==16) {
              k--;
              if (k==0) {
                  print();
                  found=1;
              }
              return;
          }
          for (i=1;i<=16;i++){
              if (!used[i]){
                  if(x==3&&(ary[0][y]+ary[1][y]+ary[2][y]+i)!=34)
                      continue;
                  if(y==3&&(ary[x][0]+ary[x][1]+ary[x][2]+i)!=34)
                      continue;
                  if(x==3&&y==0&&(ary[0][3]+ary[1][2]+ary[2][1]+i)!=34)
                      continue;
                  if(x==3&&y==3&&(ary[0][0]+ary[1][1]+ary[2][2]+i)!=34)
                      continue;
                  used[i]=1;
                  ary[x][y]=i;
                  dfs(n+1);
                  used[i]=0;
              }
          }
      }
      
      
      int main(){
          freopen("sqr.in","r",stdin);
          freopen("sqr.out","w",stdout);
          int i;
          cin>>k;
          for (i=1;i<=16;i++)
              used[i]=0;
          dfs(0);
          return 0;
      }
    2. 二分图匹配(match.cpp/match.in/match.out):

      • 题目描述:给定n个点和m条无向边,从中选出尽可能多的边,使得选出的边两两不共顶点。

      保证图中不存在自环。

      • 输入格式:第一行为两个整数,$n$和$m$。接下来$m$行,每行两个整数$u$,$v$,代表一条连接顶点u和v的无向边。
      • 输出格式:第一行一个数$k$,代表最多能选多少条边,第二行$k$个数,代表所选边的编号(按照输入顺序编号),要求输出字典序最小的方案(例如样例中,也可以选第2、4条边,但序列2 4的字典序比1 3大,故最后需输出1 3)
      • 输入样例:

      4 4

      1 2

      2 3

      3 4

      4 1

      • 输出格式:

      2

      1 3

      • 数据范围:对于30%的数据,有$1 \leq n \leq 5$,$1 \leq m \leq 10$;对于100%的数据,有$1 \leq n \leq 20$,$1 \leq m \leq 20$。
      • 分析:看到数据范围了吗,这题不用专门的二分图匹配算法做,直接$dfs$即可。为了输出字典序最小的方案,要先$dfs$选这条边,然后再$dfs$不选这条边,如果找到一个方案比现最佳方案优,就更新。
      • STD
      #include <bits/stdc++.h>
      using namespace std;
      
      const int MAXN = 30;
      const int MAXM = 30;
      
      struct edge {
          int u, v;
      };
      
      int n, m, ans = 0;
      edge e[MAXM];
      bool vis[MAXN], sel[MAXM], sel_ans[MAXM];
      
      void dfs(int x, int cnt) {
          if (x == m + 1) {
              if (cnt > ans) {
                  ans = cnt;
                  for (int i = 1; i <= m; i++)
                      sel_ans[i] = sel[i];
              }
              return;
          }
          if (!vis[e[x].u] && !vis[e[x].v]) {
              vis[e[x].u] = vis[e[x].v] = 1;
              sel[x] = 1;
              dfs(x + 1, cnt + 1);
              vis[e[x].u] = vis[e[x].v] = 0;
          }
          sel[x] = 0, dfs(x + 1, cnt);
      }
      
      int main() {
          freopen("match.in", "r", stdin);
          freopen("match.out", "w", stdout);
          
          cin >> n >> m;
          for (int i = 1; i <= m; i++)
              cin >> e[i].u >> e[i].v;
      
          dfs(1, 0);
          cout << ans << endl;
          for (int i = 1; i <= m; i++)
              if (sel_ans[i])
                  cout << i << " ";
          
          return 0;
      }

    总结

    这次考试突出我最大的问题是Code写得丑,比较简单的$dfs$总是写得很长。我的剪枝也要多练习吧(这几天好像都说要多练习),今天和明天的笔记和考试订正可能会缩水,我会多写一些题目的题解。


    笔记

    1. 前缀和:$s[k]=a[1]+a[2]+a[3]+....+a[k]$

    • 作用:解决序列区间和问题
    • 算法:

      1. 预处理:$s[i]=s[i-1]+a[1]$
      2. 查询:$ans=s[r]-s[l]$
    • 时间复杂度:预处理:$O(n)$;查询:$O(1)$。

    2. 差分

    • 作用:解决区间修改问题(代表将$a[l],a[l+1], …,a[r]$全部加上$k$)
    • 算法:

      1. 预处理:令$d[k]=a[k]-a[k-1],d[1]=a[1]$;那么就会有$a[k]=d[1]+d[2]+…+d[k]$
      2. 修改:$d[l]=d[l]+k$,$d[r+1]=d[r+1]-k$
    • 时间复杂度:预处理:$O(n)$;修改:$O(1)$。

    3. 二分查找

    • 作用:解决元素查找问题
    • 算法:先对数据进行升序排列

      1. 取$mid=(1+n)/2$,则$[1,n]$被分为两个区间$[1,mid]$,$[mid+1,n]$。
      2. 如果$v \leq a[mid]$则往左边区间查找;如果$v>a[mid]$则往右边区间查找。
      • 如此反复,直到$l=r=mid$
    • 模板:
    int l = 1, r = n;
    while (l < r) {
        int mid = (l +r) / 2;
        if (v <= a[mid])
            r = mid;
        else
            l = mid + 1;
    }
    • 时间复杂度:$O(\log n)$

    4. ST表

    • 作用:解决$RMQ$问题($Range$ $Minimum$ $Query$,区间最小(大)值查询)
    • 算法:

      1. 先开一个数组:$f[i][j]=min⁡ (a[i],a[i+1], …,a[i+2^j-1]) $(表示从下标为i的位置开始往后$2^j$的最小值)
      2. 预处理:初值:$f[i][0]=a[i]$$(1leq i leq n)$;递归:$fi=min⁡(fi,fi+2^{j-1})$,$(1 leq i leq n-2^j+1)$。
      3. 查询$a[l,r]$的最小值时,找到一个最大的j,使得$2^j \leq r-l+1$,此时,$ans=min(f[l][j],f[r-2^j+1][j])$(即使用2个长度为$2^j$的区间覆盖这个区间)。
    • 时间复杂度:预处理:$O(n \log n)$;查询:$O(\log n)$。
    • 3865 【模板】ST表
    #include <iostream>
    #include <cstdio>
    #include <cmath>
    using namespace std;
    inline int in(){
        int X=0,w=0; char ch=0;
        while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
        while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
        return w?-X:X;
    }
    
    inline void out(int x){
        if(x<0) putchar('-'),x=-x;
        if(x>9) out(x/10);
        putchar(x%10+'0');
        return;
    }
    int f[100005][50],n,m,data[100005],l,r;
    
    int main(){
        n=in();
        m=in();
        for (int i=1;i<=n;i++)
            data[i]=in(),f[i][0]=data[i];
        int t=n,Max=0;;
        for(int j=1;j<=21;j++)
            for(int i=1;i+(1<<j)-1<=n;i++)
                f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        for (int i=1;i<=m;i++){
            l=in();
            r=in();
            int k=log2(r-l+1);
            out(max(f[l][k],f[r-(1<<k)+1][k]));
            printf("\n");
        }
        return 0;
    }

    5. LCA问题($Lowest$ $Common$ $Ancestors$,最近公共祖先)

    6. STL

    • $Vector$变长数组:

      • 声明:

        1. vector<int> arr;// 声明初始长度为0的int类型的vector
        2. vector<int>arr(7); // 声明初始长度为7的vector,所有元素进行默认初始化
        3. vector<int>arr(4,2); // 声明初始长度为4,且所有元素全部为2的vector
      • 用法:

        1. $arr[i]$(可以直接像普通数组一样,用[下标]的语法取元素)
        2. $arr.size()$(返回数组长度)
        3. $arr.push$_$back(v)$(将 v 加入到数组末尾,增加数组长度的方法)
        4. $arr.begin()$(返回数组头部的迭代器;实指,类型为$vector<...>::iterator$)
        5. $arr.end()$(返回数组尾部的迭代器;虚指,指向数组最后一个元素的下一个位置)
        6. 遍历一个$vector$:很显然是上面的好用啊
        //普通方法
        for (int i  = 0; i < arr.size(); i++)
               cout << arr[i] << " ";
    //使用迭代器
    for (vector<int>::iterator it = arr.begin(); it != arr.end(); it++)
           cout << *it << endl;
    • $stack$栈

      • 声明:stack<int>s;
      • 用法:

        1. $s.push(x)$(把一个元素压入栈)
        2. $s.top()$(返回栈顶元素)
        3. $s.pop()$(弹出栈顶元素)
        4. $s.size()$(返回栈的大小)
        5. $s.empty()$(返回栈是否为空)
    • $queue$队列

      • 声明:queue<int>q;
      • 用法:

        1. $q.push(x)$(把一个元素加到队尾)
        2. $q.front()$(返回队首的元素)
        3. $q.pop()$(弹出队首元素)
        4. $q.size()$(返回队列的长度)
        5. $q.empty()$(返回队列是否为空)
    • $priority$_$queue$优先队列

      • 声明:priority_queue<int>q;(默认为大根堆)
      • 用法:

        1. $q.push(x)$(加入一个元素$x$)
        2. $q.top()$(返回优先队列里最大的元素)
        3. $q.pop()$(删除优先队列里最大的元素)
      • 扩展:priority_queue<int,vector<int>,greater<int>>q;

    总结

    今天的模拟赛有点难吧,T2是用$dfs$做的,只能50分了QAQ。最后一题好像是$LCA$问题,数据范围应该允许使用暴力解决$LCA$问题,然鹅我打了个$Floyd$。不能上200了,嘤嘤嘤。

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