1. 好像当人了，一发没判等，但是很快发现了，一发数组开小了。
2. 中间去上了个厕所跟老师说了两句话耽误了十多分钟写E
3. 这套基本上只有最后一题有点意思吧
4. 下周可以上强度了
5. 但是下周好像是个CTF周

Marathon

给四个整数，找比a大的有几个。

摁模拟

void solve() {
  int a[4];
  cin >> a[0];
  int ans = 0;
  for (int i = 1; i < 4; i++) {
    cin >> a[i];
    ans += a[i] > a[0];
  }
  cout << ans << endl;
}

All Distinct

一个数组，每次可以去除2个数字，多次操作后，数组能留下多少个不同的数字

最终结果要么是不同的数字数，要么是不同的数-1

如果出现次数为偶数的数字量是偶数，那么这几个数自己可以去掉为2个，剩下的数需要组合去除。

如果出现次数为偶数的话，则组合去除有一个数去不掉，要额外去除一个

void solve() {
  map<int, int> mp;
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    mp[x]++;
  }
  int c = 0;
  for (auto& y : mp) {
    if (y.se % 2 == 0) {
      c++;
    }
  }
  cout << mp.size() - (c % 2 == 1) << endl;
}

Where's the Bishop?

有一个8*8的矩阵，两个对角线可以攻击，交叉点就是目标点位

因为目标点位不在边界，则左上，右上，左下，右下和本身的5个点都是#

void solve() {
  string s[8];
  for (int i = 0; i < 8; i++) {
    cin >> s[i];
  }
  for (int i = 1; i < 7; i++) {
    for (int j = 1; j < 7; j++) {
      if (s[i][j] == '#') {
        if (s[i - 1][j - 1] == '#' && s[i - 1][j + 1] == '#' &&
            s[i + 1][j - 1] == '#' && s[i + 1][j + 1] == '#') {
          cout << i + 1 << " " << j + 1 << endl;
          return;
        }
      }
    }
  }
}

The Clock

给定一个时间，然后每$s$秒读一次时间，能看到多少次回文数

首先这个确定可以读到多少个不重复的数，因为$lcm(s,1440)$是间隔时间和一天的最小公倍数，则总共看$lcm(s,1440)$分钟看完，次数为$lcm(s,1440)/s$

然后按照/60， %60去补0判断时间，得到回文数个数

void solve() {
  string s;
  cin >> s;
  int t;
  cin >> t;
  int h = (s[0] - '0') * 10 + s[1] - '0';
  int m = (s[3] - '0') * 10 + s[4] - '0';
  int mi = h * 60 + m;
  int lc = 1440ll * t / __gcd(1440, t);
  int times = lc / t;
  int ans = 0;
  set<int> e;
  for (int i = 0; i < times + 1; i++) {
    string x;
    mi %= 1440;
    if (e.count(mi)) {
      break;
    }
    e.insert(mi);
    int hh = mi / 60, mm = mi % 60;
    if (hh < 10) {
      x += '0';
    }
    x += to_string(hh);
    if (mm < 10) {
      x += '0';
    }
    x += to_string(mm);
    string y = x;
    reverse(y.begin(), y.end());
    if (x == y) ans++;
    mi += t;
  }
  cout << ans << endl;
}

Binary Deque

给一个长度为$n$的01数组，可以去掉前面的也可去掉后面的，问最少去掉多少个能让和为$s$

即去掉一个前缀和一个后缀，且前缀和后缀的和为$s-sum(arr)$。

构造前缀和后缀和，枚举每个去掉的可能性判定即可，可以哈希，可以二分，无所谓

void solve() {
  int n, s;
  cin >> n >> s;
  vector<int> a(n), pre(n + 1), suf(n + 1);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    pre[i] = pre[i - 1] + a[i - 1];
  }
  for (int i = n - 1; i >= 0; i--) {
    suf[i] = suf[i + 1] + a[i];
  }
  reverse(suf.begin(), suf.end());
  if (pre.back() == s) {
    cout << 0 << endl;
    return;
  }
  if (pre.back() < s) {
    cout << -1 << endl;
    return;
  }
  int sub = pre.back() - s;
  int ans = 0x3f3f3f3f;
  for (int i = 0; i <= sub; i++) {
    int j = sub - i;
    int l = lower_bound(pre.begin(), pre.end(), i) - pre.begin();
    int r = lower_bound(suf.begin(), suf.end(), j) - suf.begin();
    r = r;
    ans = min(ans, l + r);
    // cout << l << " " << r << " " << i << " " << j << endl;
  }
  cout << ans << endl;
}

3SUM

给一组数，选3个，让其尾数为3

根据$a+b \mod m = a\mod m + b \mod m$ 的性质

先对每个数都$mod 10$

则有选取三个0-9的数的和的尾数为3

1. 3个相同的数$a$, $3a \mod 10 = 3$
2. 2个数，$aab$, $2a + b \mod 10 =3$
3. 3个数 abc $a +b +c \mod 10 =3$

枚举即可

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  map<int, int> mp;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i] %= 10;
    mp[a[i]]++;
  }
  for (int i = 0; i <= 9; i++) {
    if ((3 * i) % 10 == 3) {
      if (mp[i] >= 3) {
        cout << "YES\n";
        return;
      }
    }
  }
  for (int i = 0; i <= 9; i++) {
    for (int j = 0; j <= 9; j++) {
      if (i == j) continue;
      if ((2 * i + j) % 10 == 3) {
        if (mp[i] >= 2 && mp[j] >= 1) {
          cout << "YES\n";
          return;
        }
      }
    }
  }
  for (int i = 0; i <= 9; i++) {
    for (int j = i + 1; j <= 9; j++) {
      for (int k = j + 1; k <= 9; k++) {
        if ((i + j + k) % 10 == 3) {
          if (mp[i] > 0 && mp[j] > 0 && mp[k] > 0) {
            cout << "YES\n";
            return;
          }
        }
      }
    }
  }
  cout << "NO\n";
}

2^Sort

给一个数组$a$和一个$k$,找有多少个数组$ai,...a{i+k}$满足
$$
2^0 \cdot ai < 2^1 \cdot a{i+1}< 2^2 \cdot a{i+2}< \dots < 2^k \cdot a{i+k}.
$$

从相邻的两个数$ai,a{i+1}$来说，如果满足$ai \times 2 < a{i+1}$则这两项可以是这个组合中的一个元素

首先判定有多少个相邻元素满足条件。然后滑动窗口判断连续满足$k$个计数即可

void solve() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  vector<int> dp(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i < n; i++) {
    if (a[i] * 2 > a[i - 1]) {
      dp[i] = 1;
    }
  }

  int ans = 0;

  int cnt = 0;
  for (int i = 0; i <= k; i++) {
    cnt += dp[i];
  }
  ans += cnt == k;
  for (int i = k + 1; i < n; i++) {
    cnt -= dp[i - k];
    cnt += dp[i];
    ans += cnt == k;
  }
  cout << ans << endl;
}

Gambling

翻译完就是找数组$x$中，选定三个数$a,l,r$,使得数组$x_l,...,x_r$中$a$的个数- 非$a$的个数最大

对于每个数字a，我们可以通过其出现的所有位置来计算可能的区间贡献。贡献值为2m - k，其中m是该区间内a的出现次数，k是区间长度。

分组前缀和1和-1维护

void solve() {
  map<int, vector<int>> M;
  int n;
  cin >> n;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    M[a[i]].push_back(i);
  }
  int ans = 1, anskey = a[1], ansl = 1, ansr = 1;
  for (auto [key, v] : M) {
    vector<int> sum(v.size());
    sum[0] = 1;
    for (int i = 1; i < v.size(); i++) {
      sum[i] = sum[i - 1] - (v[i] - v[i - 1] - 1) + 1;
    }
    int j = 0;
    for (int i = 1; i < v.size(); i++) {
      if (ans < sum[i] - sum[j] + 1) {
        ans = sum[i] - sum[j] + 1;
        ansl = v[j], ansr = v[i];
        anskey = key;
      }
      if (sum[j] > sum[i]) j = i;
    }
  }
  cout << anskey << ' ' << ansl << ' ' << ansr << '\n';
}