南工程程序设计竞赛补题

本文主要是介绍南工程程序设计竞赛补题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

C++快读，有些题目会有限制，如果不快读会出现一定的问题。

   ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

校赛地址
南工程程序设计竞赛

#include <bits/stdc++.h>
using namespace std;
int main()
{// 同号详见int n;cin >> n;int mi = 1e7;//不用进行分类讨论while (n--){int x, y;cin >> x >> y;mi = min(mi, abs(x - y));}cout << mi;
}

C区间最大值
RMQ求区间最大值，时间复杂度为O（N）
ST算法它的本质相当于是动态规划，下面我们以求最大值为例（最小值求法和最大值差不多）

我们用 f [ i ][ j ] 表示以 i 为起点，连续 2^j 个数中的最大值，例如 f [ 2 ][ 2 ] 就表示第 2 个数到第 5 个数的最大值

我们用A表示原序列，由于20= 1，按照 f 数组的定义，f [ i ][ 0 ] 就等于 A[ 0 ]（初始化）

#include <bits/stdc++.h>
using namespace std;
int n, t, q;
const int N = 2e5 + 10;
const int M = 25;
int a[N], Log[N];
int f[N][M];
void GetLog()
{int i;Log[1] = 0;for (i = 2; i <= n + 1; ++i)Log[i] = Log[i / 2] + 1;
}
void RMQ()
{int i, j;for (i = 1; i <= n; ++i)f[i][0] = a[i];for (j = 1; (1 << j) <= n; ++j)for (i = 1; i + (1 << (j - 1)) <= n; ++i)f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
int main()
{cin >> n >> t >> q;for (int i = 1; i <= n; ++i)cin >> a[i];GetLog();RMQ();for (int i = 1; i <= t; ++i){int l, r;scanf("%d%d", &l, &r);int k = Log[r - l + 1]; //长度int ans = max(f[l][k], f[r - (1 << k) + 1][k]);if (ans >= q){cout << ans << ' ' << "YES" << endl;}else{cout << ans << ' ' << "NO" << endl;}}return 0;
}