牛客OI周赛7-普及组

这一场感觉良好

也只能打这种普及组长长信心这样子

A:救救喵咪
给你坐标轴上的个点，求出对于每个点，有多少个点的坐标和坐标都大于它。（）

是开玩笑的吧
直接

#include <iostream>
#define
 
using namespace std;
typedef long long ll;
int x[A], y[A], n;
 
int main(int argc, char const *argv[]) {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        for (int j = 1; j <= n; j++)
            if (x[j] > x[i] and y[j] > y[i]) cnt++;
        cout << cnt << endl;
    }
}

B:救救兔子
一个由个数组成的序列，给你个询问，每个询问会给你一个数，对于每个询问，你要回答出序列中与这个值最接近的元素

二分

#include <iostream>
#include <algorithm>
#define
 
using namespace std;
typedef long long ll;
int a[A], n, T, t;
int search(int x) {
    int l = 1, r = n, m = (n + 1) >> 1;
    while (l < r - 1) {
        if (x < a[m]) r = m;
        else l = m;
        m = (l + r) >> 1;
    }
    if (abs(a[l] - x) <= abs(a[l + 1] - x) and l < n) return a[l];
    else return a[l + 1];
}
 
int main(int argc, char const *argv[]) {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    cin >> T;
    while (T--) {
        cin >> t;
        cout << search(t) << endl;
    }
}

直接lower_bound也可以

#include <iostream>
#include <algorithm>
#define

using namespace std;
typedef long long ll;
int f[A], n, m, a;

int main(int argc, char const *argv[]) {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> f[i];
    sort(f, f + n);
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> a;
        int nxt = lower_bound(f, f + n, a) - f; int las = nxt - 1;
        if (nxt >= n) nxt = n - 1;
        if (las < 0) las = 0;
        if (f[nxt] - a < a - f[las]) cout << f[nxt];
        else cout << f[las];
    }
}

C:救救企鹅
将字符串a中的b都换成c

考察string函数的应用

#include <iostream>
#define
#define
 
using namespace std;
typedef long long ll;
string a, b, c;

int main(int argc, char const *argv[]) {
    cin >> a >> b >> c;
    while (1) {
        int x = a.find(b);
        if (x >= a.length()) break;
        a.erase(x, b.length());
        a.insert(x, c);
    }
    cout << a;
}

D:数糖纸
元素不重复区间的最长长度

尺取法
不了解可自行百度

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define
#define

using namespace std;
typedef long long ll;
int n, l = 1, r = 1, nxt[A], ans, a[A], pos[A], pre[A];

int main(int argc, char const *argv[]) {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  memcpy(pos, a, sizeof a);
  sort(pos + 1, pos + n + 1);
  for (int i = 1; i <= n; i++) {
    int k = lower_bound(pos + 1, pos + n + 1, a[i]) - pos - 1;
    pre[i] = nxt[k], nxt[k] = i;
  }
  while (l <= n and r <= n) {
    while (pre[r] < l and r <= n) ans = max(ans, r - l + 1), r++;
    l = pre[r] + 1;
  }
  printf("%d\n", ans);
}