Day 4 高中部寒假集训

浏览 1180 | 评论 0 | 字数 7817

Snowflake_Pink

2019年01月26日

Day4：

先放课程表：

2019.1.25

上午

讲解订正$Day3$晚上考试的题目。

下午

图论： RMQ问题、LCA问题、ST表。

晚上

考试：动态规划

考试（选讲）

时空限制：1000ms/128MB

幻方（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;
}

二分图匹配（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 来审核鸭~

评论列表

暂无评论