• 周四. 4月 25th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

2021暑假模拟赛7

admin

11月 28, 2021

A[CF1155A(1000)]

枚举相邻两项,如果存在逆序对则可以。

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  string s;
  cin >> s;
  vector<int> p(26, -1);
  for (int i = 0; i < n; ++i) {
    for (int j = s[i] - 'a' + 1; j < 26; ++j) {
      if (p[j] != -1) {
        cout << "YES" << '
';
        cout << p[j] + 1 << ' ' << i + 1 << '
';
        exit(0);
      }
    }
    p[s[i] - 'a'] = i;
  }
  cout << "NO" << '
';
}

View Code

B[CF1110B(1400)]

如果$K=N$,那么每个点自己覆盖就行。那么$K$每减少$1$,可以看作将相邻的两段合并,也就是增加一个空隙的距离,那么取走$N-K$个最小的空隙即可。

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N, M, K;
  cin >> N >> M >> K;
  vector<int> B(N);
  for (int i = 0; i < N; ++i) {
    cin >> B[i];
  }
  int Ans = N;
  vector<int> S;
  for (int i = 0; i < N - 1; ++i) {
    S.push_back(B[i + 1] - B[i] - 1); 
  }
  sort(S.begin(), S.end());
  for (int i = 0; i < N - K; ++i) {
    Ans += S[i];
  }
  cout << Ans << '
';
}

View Code

C[CF1025D(2100)]

对于二叉搜索树,可以把每个子树理解成一个子问题。于是可以考虑一个区间$dp[l][r][x]$表示这棵子树的根是$x$,$[l,r]$是否能被合并。仔细观察一下,发现之前的根肯定是$l-1$或$r+1$,于是可以把状态变成$dp[l][r][0/1]$表示根是$l-1$还是$r+1$,转移枚举当前子树的根即可,时间复杂度$O(N^3)$。

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
int dp[2][705][705];
int g[705][705];
int main() {
  int N;
  cin >> N;
  vector<int> A(N + 1);
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
  }
  for (int i = 0; i <= N; ++i) {
    for (int j = 0; j <= N; ++j) {
      g[i][j] = __gcd(A[i], A[j]);
    }
  }
  for (int i = 0; i < N; ++i) {
    if (g[i + 1][i] >= 2) {
      dp[1][i][i] = 1;
    }
    if (i >= 1 && g[i - 1][i] >= 2) {
      dp[0][i][i] = 1; 
    }
  }
  for (int L = 2; L <= N; ++L) {
    for (int i = 0; i + L - 1 < N; ++i) {
      int j = i + L - 1;
      for (int l = 0; l < 2; ++l) {
        for (int k = i; k <= j; ++k) {
          if (g[k][(l == 0 ? i - 1 : j + 1)] >= 2) {
            dp[l][i][j] |= ((k > i ? dp[1][i][k - 1] : 1) & (k < j ? dp[0][k + 1][j] : 1));
            if (dp[l][i][j]) {
              break;
            }
          } 
        }
      }
    }
  }
  if (dp[1][0][N - 1]) {
    cout << "Yes" << '
';
  } else {
    cout << "No" << '
';
  }
}

View Code

D[CF1473E(2400)]

直接跑最短路比较困难,这里可以考虑一个类似「松弛」的操作,对于减$max$和加$min$变成选任意一条边减去和任意一条边加上。那么这样可以重新设计这张图,$dp[x][0/1][0/1]$表示到$x$点是否选了减去的和加上的,类似分层图,跑最短路即可,最终结果就是答案。最短路会在过程中自动地选上路径的最小边和最大边。

#include <bits/stdc++.h>

using namespace std;

const long long inf = 1000000000000000000;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int> > > G(n);
    for (int i = 0; i < m; ++i) {
        int x, y, w;
        cin >> x >> y >> w;
        x --;
        y --;
        G[x].emplace_back(y, w);
        G[y].emplace_back(x, w);
    }

    vector<vector<long long> > d(n, vector<long long> (4, inf));
    d[0][0] = 0;

    priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>> , greater<tuple<long long, int, int> > > q;
    q.emplace(0, 0, 0);

    while (!q.empty()) {
        auto [cur, x, s] = q.top();
        q.pop();

        if (cur > d[x][s]) {
            continue;
        }

        for (auto [y, w] : G[x]) {
            if (d[y][s] > d[x][s] + w) {
                d[y][s] = d[x][s] + w;
                q.emplace(d[y][s], y, s);
            }
            if (!(s & 1)) {
                if (d[y][s ^ 1] > d[x][s] + w + w) {
                    d[y][s ^ 1] = d[x][s] + w + w;
                    q.emplace(d[y][s ^ 1], y, s ^ 1);
                }
            }
            if (!(s & 2)) {
                if (d[y][s ^ 2] > d[x][s]) {
                    d[y][s ^ 2] = d[x][s];
                    q.emplace(d[y][s ^ 2], y, s ^ 2);
                }
            }
            if (s == 0) {
                if (d[y][3] > d[x][s] + w) {
                    d[y][3] = d[x][s] + w;
                    q.emplace(d[y][3], y, 3);
                }
            }
        }
    }

    for (int i = 1; i < n; ++i) {
        cout << d[i][3] << " 
"[i == n - 1];
    }

    return 0;
}

View Code

最后两个题难度比较大,不过涉及的套路比较有用,代码难度不大,可以学习一下。

《2021暑假模拟赛7》有一个想法
  1. Wow, amazing blog structure! How lengthy have you ever been running a blog for?
    you make blogging look easy. The entire look of your web site is excellent, let
    alone the content material! You can see similar here sklep internetowy

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注