Day 4 高中部寒假集训

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 条无向边,从中选出尽可能多的边,使得选出的边两两不共顶点。

      保证图中不存在自环。

    • 输入格式:第一行为两个整数,nm。接下来m 行,每行两个整数uv,代表一条连接顶点 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 51 \leq m \leq 10;对于 100% 的数据,有1 \leq n \leq 201 \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]+kd[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 很显然是上面的好用啊
    //普通方法
    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 了,嘤嘤嘤。

本文链接:https://snowflake.pink/archives/10/
This blog is under a CC BY-NC-ND 4.0 Unported License