Code Monkey Day 8

省流：这回不唐了。

估分 100 + 100 + 100 + 0 + 10 = 310

实际 100 + 100 + 100 + 10 + 10 = 320

666 还有反向挂分，这次不微距了。

T1

既然正解是 $O(n)$ 为什么不卡掉 $O(n log n)$ 呢，那我二分你不炸了吗。

#include <bits/stdc++.h>
using namespace std;
int n, m, a[100005];
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i]; a[i] += a[i - 1];
  }
  cin >> m;
  while(m--) {
    int x; cin >> x;
    int l = 1, r = n;
    while(l < r) {
      int mid = (l + r) / 2;
      if (a[mid] >= x) r = mid;
      else l = mid + 1; 
    }
    cout << l << " ";
  }
  return 0;
}

T2

前缀和后缀和，小唐诗 wzj 不会算后缀和 /kk

#include <bits/stdc++.h>
using namespace std;
int n, a[100005], Q[100005], H[100005];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i]; Q[i] = H[i] = 1;
  }
  if (n == 1) {
    cout << 1 << "\n"; return 0;
  }
  for (int i = 2; i <= n; ++i) {
    if (a[i] > a[i - 1]) Q[i] = Q[i - 1] + 1;
  }
  for (int i = n - 1; i >= 1; --i) {
    if (a[i] < a[i + 1]) H[i] = H[i + 1] + 1;
  }
  int ans = 1;
  for (int i = 1; i <= n; ++i) {
    if (i == 1) {
      ans = max(ans, H[i + 1] + 1);
    } else if (i == n) {
      ans = max(ans, Q[i - 1] + 1);
    } else {
      if (a[i + 1] > a[i - 1] + 1) {
        ans = max(ans, Q[i - 1] + H[i + 1] + 1);
      } else {
        ans = max(ans, max(Q[i - 1] + 1, H[i + 1] + 1));
      }
    }
  }
  ans = min(ans, n);
  cout << ans;
  return 0;
}

T3

细节 $a_i$ 在 $1e6$ 以内，所以可以数论。

但是不去重会 T 一个点，要不是主页显示我没 A 我就唐了。

#include <bits/stdc++.h>
#define B begin
#define E end
#define Bk back
using namespace std;
int n, ans, k[3005];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  cin >> n;
  if (n <= 3000) {
    for (int i = 1; i <= n; i++) cin >> k[i];
    for (int i = 1; i <= n; i++) {
      for (int j = i + 1; j <= n; j++) {
        ans = max(ans, max(k[i], k[j]) % min(k[i], k[j]));
      }
    }
    cout << ans; return 0;
  }
  vector<int> a(n); //必须定义大小不然排序会出问题
  for (int i = 0; i < n; ++i) cin >> a[i];
  sort(a.B(), a.E());
  a.erase(unique(a.B(), a.E()), a.E()); 
  for (int i = 0; i < a.size(); ++i) {
    for (int j = 2 * a[i]; j <= a.Bk() + a[i]; j += a[i]) {
      auto Gues = lower_bound(a.B(), a.E(), j);
      if (Gues != a.B()) {
        --Gues;
        if (*Gues > a[i]) ans = max(ans, *Gues % a[i]);
      }
    }
  }
  if (!ans && a.size() >= 2) {
    ans = a[a.size() - 2] % a.Bk();
  }
  cout << ans;
  return 0;
}

T4

思维难度还好吧，怎么那么多人说不会思路啊。

给 cch 欣赏一下我的赛时屎山。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9 + 9;
struct node {
  int a, b, z;
  bool operator < (const node &x) const{
    return z < x.z;
  }
} g[100005];
int m, di[100005], h[100005];
map<pair<int, int>, bool> mp;
map<pair<int, int>, int> biao;
set<node> s;
bool R (int x, int y, int z) {
  if (mp[{x, y + 1}] == 1 && mp[{x - 1, y}] == 0 && mp[{x + 1, y}] == 0) return 0;
  if (mp[{x + 1, y + 1}] == 1 && mp[{x + 1, y}] == 0 && mp[{x + 2, y}] == 0) return 0;
  if (mp[{x - 1, y + 1}] == 1 && mp[{x - 1, y}] == 0 && mp[{x - 2, y}] == 0) return 0;
  h[z] = 1; return 1;
}
void Z (int x, int y, int z) {
  if (mp[{x - 1, y - 1}] == 1 && mp[{x - 1, y}] == 0 && mp[{x - 2, y}] == 0 && h[biao[{x - 1, y - 1}]] == 0) {
    h[biao[{x - 1, y - 1}]] = 1; s.insert({x - 1, y - 1, biao[{x - 1, y - 1}]});
  }
  if (mp[{x, y - 1}] == 1 && mp[{x - 1, y}] == 0 && mp[{x + 1, y}] == 0 && h[biao[{x, y - 1}]] == 0) {
    h[biao[{x, y - 1}]] = 1; s.insert({x, y - 1, biao[{x, y - 1}]});
  }
  if (mp[{x + 1, y - 1}] == 1 && mp[{x + 1, y}] == 0 && mp[{x + 2, y}] == 0 && h[biao[{x + 1, y - 1}]] == 0) {
    h[biao[{x + 1, y - 1}]] = 1; s.insert({x + 1, y - 1, biao[{x + 1, y - 1}]});
  }
  if (mp[{x, y + 1}] == 1 && (mp[{x - 1, y}] == 1 || mp[{x + 1, y}] == 1) && !(mp[{x - 1, y}] && mp[{x + 1, y}])) {
    if(s.find({x - 1, y, biao[{x - 1, y}]}) != s.end()){
      s.erase({x - 1, y, biao[{x - 1, y}]}); h[biao[{x - 1, y}]] = 0;
    } else {
      s.erase({x + 1, y, biao[{x + 1, y}]}); h[biao[{x + 1, y}]] = 0;
    }
  }
  if (mp[{x + 1, y + 1}] == 1 && (mp[{x + 1, y}] == 1 || mp[{x + 2, y}] == 1) && !(mp[{x + 1, y}] && mp[{x + 2, y}])) {
    if(s.find({x + 2, y, biao[{x + 2, y}]}) != s.end()){
      s.erase({x + 2, y, biao[{x + 2, y}]}); h[biao[{x + 2, y}]] = 0;
    } else {
      s.erase({x + 1, y, biao[{x + 1, y}]}); h[biao[{x + 1, y}]] = 0;
    }
  }
  if (mp[{x - 1, y + 1}] == 1 && (mp[{x - 1, y}] == 1 || mp[{x - 2, y}] == 1) && !(mp[{x - 1, y}] && mp[{x - 2, y}])) {
    if(s.find({x - 1, y, biao[{x - 1, y}]}) != s.end()){
      s.erase({x - 1, y, biao[{x - 1, y}]}); h[biao[{x - 1, y}]] = 0;
    } else {
      s.erase({x - 2, y, biao[{x - 2, y}]}); h[biao[{x - 2, y}]] = 0;
    }
  }
}
int F() {
  long long ans = 0;
  for (int i = 1; i <= m; i++) ans = (ans * m + di[i]) % MOD;
  return ans;
}
signed main() {
  cin >> m;
  for (int i = 0; i < m; i++) {
    cin >> g[i].a >> g[i].b; g[i].z = i;
    mp[{g[i].a, g[i].b}] = 1;
    biao[{g[i].a, g[i].b}] = i;
  }
  for (int i = 0; i < m; i++) {
    if (R(g[i].a, g[i].b, g[i].z)) {
      s.insert({g[i].a, g[i].b, g[i].z});
    }
  }
  int tot = 1;
  while(!s.empty()) {
    if (tot % 2 == 1) { //蜗蜗 大
      node A = *--s.end(); h[A.z] = 2;
      di[tot] = A.z; mp[{A.a, A.b}] = 0;
      s.erase(A);
      Z(A.a, A.b, A.z);
    } else { //哞哞 小
      node A = *s.begin(); h[A.z] = 2;
      di[tot] = A.z; mp[{A.a, A.b}] = 0;
      s.erase(A);
      Z(A.a, A.b, A.z);
    }
    tot++;
  }
  cout << F();
  return 0;
}

显然考虑太复杂了，还有一个 return 0 写成 return 1 糖丸了。

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N = 2e5 + 10, X = 1e9 + 9;
multiset<int> S;
pair<int, int> a[N];
bool vis[N];
map<pair<int, int>, int> h;
int n;
int ksm(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) res = res * a % X;
    a = a * a % X; b >>= 1;
  }
  return res;
}
bool Z(int u) {
  int x = a[u].x, y = a[u].y;
  if (h[{x, y + 1}]) {
    if (!h[{x - 1, y}] && !h[{x + 1, y}]) return 0;
  }
  if (h[{x + 1, y + 1}]) {
    if (!h[{x + 1, y}] && !h[{x + 2, y}]) return 0;
  }
  if (h[{x - 1, y + 1}]) {
    if (!h[{x - 1, y}] && !h[{x - 2, y}]) return 0;
  }
  return 1;
}
void R(int nx, int ny) {
  h[{nx, ny}] = 0;
  if (h[{nx, ny - 1}] && Z(h[{nx, ny - 1}])) S.insert(h[{nx, ny - 1}]);
  if (h[{nx - 1, ny - 1}] && Z(h[{nx - 1, ny - 1}])) S.insert(h[{nx - 1, ny - 1}]);
  if (h[{nx + 1, ny - 1}] && Z(h[{nx + 1, ny - 1}])) S.insert(h[{nx + 1, ny - 1}]);
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].x >> a[i].y;
    h[{a[i].x, a[i].y}] = i;
  }
  for (int i = 1; i <= n; i++) {
    S.insert(i); vis[i] = 1;
  }
  int ans = 0, D = n - 1; bool tot = 1;
  for (int i = 1; i <= n; i++) {
    int tmp;
    if (tot) {
      do {
        tmp = *--S.end();
        vis[tmp] = 0; S.erase(tmp);
      } while (!Z(tmp));
      (ans += (tmp - 1) * ksm(n, D) % X) %= X;
    } else {
      do {
        tmp = *S.begin();
        vis[tmp] = 0; S.erase(tmp);
      } while (!Z(tmp));
      (ans += (tmp - 1) * ksm(n, D) % X) %= X;
    }
    int nx = a[tmp].x, ny = a[tmp].y;
    R(nx, ny); tot ^= 1; D--;
  }
  cout << ans;
  return 0;
}

T5

我只会 10 分暴力，lzh 居然会 30 pts，膜拜了。 /bx /bx /bx

总结

这下不糖了，但是补题的时候还是思路太混了。