链接：
https://ac.nowcoder.com/acm/contest/44007

B. Card

前缀和

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;
using i128 = __int128;

void solve() {
  int n, k;
  cin >> n >> k;
  vector<i64> a(n + 1), b(n + 1);
  i64 sum = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    sum += a[i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> b[i];
  }
  vector<pair<i64, int>> c(n + 1);
  for (int i = 1; i <= n; i++) {
    c[i].first = b[i] - a[i];
    c[i].second = i;
  }
  sort(c.begin() + 1, c.end(), greater<>());
  vector<int> id(n + 1);
  for (int i = 1; i <= n; i++) {
    id[i] = c[i].second;
  }
  vector<int> pos(n + 1);
  for (int i = 1; i <= n; i++) {
    pos[id[i]] = i;
  }
  vector<i64> pre(n + 1);
  for (int i = 1; i <= n; i++) {
    pre[i] = c[i].first;
    pre[i] += pre[i - 1];
  }
  int m;
  cin >> m;
  for (int i = 0; i < m; i++) {
    int len;
    cin >> len;
    int more = 0;
    i64 add = 0;
    vector<int> d;
    for (int j = 0; j < len; j++) {
      int x;
      cin >> x;
      if (pos[x] <= k) {
        more++;
        add += c[pos[x]].first;
      } else {
        d.push_back(pos[x]);
      }
    }
    sort(d.begin(), d.end());
    for (auto di : d) {
      if (di <= k + more) {
        more++;
        add += c[di].first;
      } else {
        break;
      }
    }
    cout << pre[k + more] - add + sum << '\n';
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
    solve();
  }
  return 0;
}

D. Hash

进制转换

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int mod = 5999993;

i64 get(string s) {
  i64 res = 0;
  for (char c : s) {
    res = (res * 29 + (c - 'a' + 1)) % mod;
  }
  return res;
}

void solve() {
  string s;
  cin >> s;
  i64 h1 = get(s);
  i64 ori = h1;
  for (int i = 0; i < 6; i++) {
    h1 = h1 * 29 % mod;
  }
  i64 h2 = ori - h1;
  if (h2 < 0) {
    h2 += mod;
  }
  for (int i = 0; i < 200; i++) {
    i64 tmp = h2 + i * mod;
    string ans;
    bool ok = 1;
    for (int j = 0; j < 6; j++) {
      int num = tmp % 29;
      if (num == 0 || num > 26) {
        ok = 0;
        break;
      }
      tmp -= num;
      ans += (char) (num + 'a' - 1);
      tmp /= 29;
    }
    if (ok) {
      cout << s;
      for (int i = 5; i >= 0; i--) {
        cout << ans[i];
      }
      cout << '\n';
      return;
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int tt = 1;
  cin >> tt;
  while (tt--) {
    solve();
  }
  return 0;
}

G. 2D-Lake

二分

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;
using i128 = __int128;

constexpr i64 N = 1E18;

void print(i128 x) {
  i64 num1 = x / N;
  i64 num2 = x % N;
  if (x <= N) {
    cout << (i64) x << '\n';
    return;
  }
  cout << num1 << setw(18) << setfill('0') << num2;
}

void solve() {
  i64 n, m;
  cin >> n >> m;
  i128 n1 = n, m1 = m;
  if (n1 != 1 && n1 != 2) {
    if (n1 % 2 == 1 && (n1 - 1) * (n1 - 1) / 4 >= m1) {
      print((n1 - 1) * (n1 - 1) / 4);
      return;
    } else if (n1 % 2 == 0 && n1 * (n1 - 2) / 4 >= m1) {
      print(n1 * (n1 - 2) / 4);
      return;
    }
  }
  // odd
  i128 ans1 = 0;
  i128 l = 2, r = 1E10;
  while (l <= r) {
    i128 mid = (l + r) >> 1;
    auto check1 = [&](i128 x) {
      i128 tmp = x * 2 - 1;
      if ((tmp - 1) * (tmp - 1) / 4 >= m) {
        return true;
      }
      return false;
    };
    if (check1(mid)) {
      r = mid - 1;
      ans1 = mid;
    } else {
      l = mid + 1;
    }
  }

  // even
  l = 3, r = 1E10;
  i128 ans2 = 0;
  while (l <= r) {
    i128 mid = (l + r) >> 1;
    auto check2 = [&](i128 x) {
      i128 tmp = (x - 1) * 2;
      if (tmp * (tmp - 2) / 4 >= m) {
        return true;
      }
      return false;
    };
    if (check2(mid)) {
      r = mid - 1;
      ans2 = mid;
    } else {
      l = mid + 1;
    }
  }
  i128 ans = min(2 * ans1 - 1, (ans2 - 1) * 2);
  print(ans);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
    solve();
  }
  return 0;
}

H. Cute Rabbit

数据过弱

J. Make it Equal

签到

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  set<int> s;
  for (int i = 0; i < n ;i++) {
    cin >> a[i];
    s.insert(a[i]);
  }
  if ((int) s.size() == 1) {
    cout << n << '\n';
    return;
  }
  cout << n - 1 << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
    solve();
  }
  return 0;
}

原文地址：http://www.cnblogs.com/kiddingma/p/16820100.html