高中部寒假集训Day4

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:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    #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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    #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$
  • 模板:

1
2
3
4
5
6
7
8
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表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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$:很显然是上面的好用啊
      1
      2
      3
      //普通方法
      for (int i = 0; i < arr.size(); i++)
      cout << arr[i] << " ";
      1
      2
      3
      //使用迭代器
      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了,嘤嘤嘤。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×