A. 贪心问题

程序设计：轻重搭配
2019 蓝桥杯省赛 A 组模拟赛
这道题主要是考贪心的思路，首先我们知道答案最多就n/2， 所以最多就在n - n/2 与n匹配， 所以我们就先将数组排序，然后从头遍历到中间的位置，然后利用双指针同时指向两个元素进行比较，如果满足题意，那么我们就选择这对元素，如果不满足，那么我们就应该让后面的指针往后移，因为前面的指针指向的元素的后面所有元素都不满足条件，而后面的指针却有可能满足条件，所以移动后面的指针即可，就这样一直已知遍历下去即可求出最终答案。

#include <bits/stdc++.h>
using namespace std;

const int N = 5E5 + 10;
int a[N], n;

bool vis[N];
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i ++ ) scanf("%d", a + i);
  sort(a, a + n); // 排序
  int l = 0; // 左指针
  int r = n - n / 2; // 边界
  int cur = r; // 右指针
  int res = 0; // 答案
  while (l <= r && cur < n) { // 如果左指针没有超界并且右指针也没有超界
  	if (a[l] * 2 <= a[cur]) {
  		vis[l] = vis[cur] = true; // 选择这队元素
  		l ++;
  		cur ++;
  		res ++;
    } else cur ++; // 移动右指针
  }
  for (int i = 0; i < n; i ++ ) {
    if (!vis[i]) res ++; // 遍历获得所有没有被选中的元素，这些元素都需要
  }
  printf("%d", res);
  return 0;
}

B. 快速幂

快速幂模板题：原理：https://yumingxi.xyz/posts/4b6e402f.html#B-幂乘问题

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int mul(ll x, ll n) {
  int res = 1;
  while (n) {
    if (n & 1) res = res * x % 10;
    x = x * x % 10;
    n >>= 1;
  }
  return res;
}
int muls(ll x, ll n) {
  if (n == 1) return x % 10;
  int res = muls(x, n / 2);
  if (n & 1) return (res * res % 10)* x % 10;
  return res * res % 10;
}

int main() {
  ll a;
  scanf("%lld", &a);
//	cout << mul(a, a) << endl;
  cout << muls(a, a) << endl;
  return 0;
}

C. 贪心或者bfs（建议用贪心）

这道题明显是bfs的题目，使用bfs的思想就能通过，但是也有贪心的成分，我们直接每次跳最大可能，这样就可以保证最少次数了。

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
bool vis[N];
string s;
int main() {
  scanf("%d%d", &n, &m);
  cin >> s;
  for (int i = 0; i < s.size(); i ++ ) {
    if (s[i] == '1') vis[i + 1] = true;
    else vis[i + 1] = false; // 从 1 开始
  }
  int f = 1;
  int res = 0;
  while (true) {
    int t = f; // 当前状态
    for (int i = m; i > 0; i -- ) { // 从最大步数开始跳，不行就少跳点，一直到1为止
      if (f + i < n && vis[f + i]) { // 如果可以跳并且没有超界
        f += i;
        res ++;
        break;
      }
      if (f + i == n) { // 如果下一步是终点
        res ++;
        cout << res << endl;
        return 0;
      }
    }
    if (f == t) { // 如果当前没有发生改变说明不能跳了，无法动弹
      cout << "-1" << endl;
      return 0;
    }
  }
  return 0;
}

D.求三角形的内切圆和外接圆

初中高中三角形数学问题。自行百度

E.最短路径问题

最短路径问题，但是针对于这道题而言数据范围1w，如果开二维数组存路径n^2,必爆，太多浪费的空间了，而是压缩成一维离散的数组就行(4*n)。
除了这个问题就纯模板题了，没什么讲的。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;

int n, m, dist[N];
int e[N], ne[N], w[N], h[N], idx;
bool vis[N];
void init() {
  memset(h, -1, sizeof h);
  memset(dist, 0x3f, sizeof dist);
  idx = 1;
}

void add(int a, int b, int c) {
  e[idx] = b, ne[idx] = h[a], h[a] = idx, w[idx ++ ] = c;
}

void djikstra() {
  dist[1] = 0;
  while (true) {
    int v = -1;
    for (int i = 1; i <= n; i ++ ) if (!vis[i] && (v == -1 || dist[v] > dist[i])) v = i;
    if (v == -1) break;
    vis[v] = true;
    for (int i = h[v]; i != -1; i = ne[i]) dist[e[i]] = min(dist[e[i]], w[i] + dist[v]);
  }
}

int main() {
  init();
  scanf("%d%d", &n, &m);
  while (m -- ) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    add(a, b, c), add(b, a, c);
  }
  djikstra();
  int res = 0;
  for (int i = 2; i <= n; i ++ ) res += dist[i];
  cout << res * 2 << endl;
  return 0;
}

F.线段树模板题

G.后缀字符串

这道题如果每一个都字符串都去遍历所有的字符串进行判断，对应时间复杂度o(n^2)， n <= 1e5，必超时(2s)， 所以必须找一个o(nlogn) or o(nsqrt(n))的算法。
分析一下，如果对应每一个字符串我们都去存一下他所有的后缀出现的次数，那么最后直接去拿这个字符出现的次数（如果是某一个字符串的后缀，那么他必然在对应字符串的后缀中存了一下次数），那么就是对应的答案了（时间复杂度: o(10nlogn) => o(nlogn)(对于每一个字符我们遍历他的所有后缀存储到map中，map存储logn，字符串长度最长也就10)）。

#include <bits/stdc++.h>
#define engl '\n'
using namespace std;
const int N = 1e5 + 10;
int n;
string s[N];
map<string, int> mp;

void solve(string s) {
  for (int i = 0; i < s.size(); i ++ ) mp[s.substr(i)] ++;
}

int main() {
  scanf("%d", &n);
  getchar();
  for (int i = 0; i < n; i ++ ) getline(cin, s[i]), solve(s[i]);
  for (int i = 0; i < n; i ++ ) cout << mp[s[i]] << endl;
  return 0; 
}

H.区间DP

如果要反转这个区间的元素并求和，那么我们就应该从这个区间的开始一直遍历到结束，很明显我们反转[1, 5]和[2, 4] 的时候 [2, 4]这段区间的内容如果是已经被计算过了， 那么我们就只需要计算他外层的两个元素就可以了
所以我们用dp[i][j]用来表示反转a数组时，a[i]*b[i] + ... a[j]*b[j] 的值是多少；
他的状态转移方程就是 dp[i][j] = dp[i + 1][j - 1] + a[i] * b[j] + a[j] * b[i]
而对于总体来说，反转[i, j]这端区间的a数组，总和应该是dp[i][j] + s[n] + s[i - 1] - s[j], s为前n项和（因为我们每次都要去计算没有被反转的数组乘积，不如用前缀和直接存一下就可以了，然后查询的时候直接删除区间加上dp[i][j]就可以了），但是我们每次都去计算反转后的值是多少，所以我们应该用一个变量去存一下所有反转后的最大值，最终打印这个最大值就行了。
但是这个dp的规律应该怎么去循环呢？
我们如果计算[1, 5], 就得先计算[2, 4]，就得先计算[3, 3]，所以对应每一个区间，我们都应该先去dp他的子区间，所以我们应该先从区间长度为1的区间dp，然后再去遍历区间长度为2、3、4…就可以了。

#include <bits/stdc++.h>
#define engl '\n'
using namespace std;
const int N = 5e3 + 10;
typedef long long ll;
ll n;
ll a[N], b[N];
ll dp[N][N], s[N];
void init() {
  scanf("%lld", &n);
  for (ll i = 1; i <= n; i ++ ) scanf("%lld", a + i);
  for (ll i = 1; i <= n; i ++ ) {
    scanf("%lld", b + i);
    dp[i][i] = a[i] * b[i];
    s[i] = s[i - 1] + dp[i][i];
  }
}

int main() {
  init();
  ll res = s[n];
  for (ll len = 2; len <= n; len ++ ) {
    for (ll l = 1; l + len - 1 <= n; l ++ ) {
      ll r = l + len - 1;
      dp[l][r] = dp[l + 1][r - 1] + a[l] * b[r] + a[r] * b[l];
      res = max(res, dp[l][r] + s[l - 1] + s[n] - s[r]);
    }
  }
  cout << res << endl;
  return 0;
}