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：

   CPP

   #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

   CPP

   #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]$$(1\leq i \leq n)$；递归：$f[i][j]=min⁡(f[i][j-1],f[i+2^{j-1}][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$：很显然是上面的好用啊
    CPP

    //普通方法
    for (int i  = 0; i < arr.size(); i++)
           cout << arr[i] << " ";

    CPP

    //使用迭代器
    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了，嘤嘤嘤。