1. 发现的问题最大的就是不会写代码了，E和G2好像是当时测O1的智商的时候交的，忽略，B就开始WA， EF Wa上天，交互不会写控制，三指针不会拆分。
2. 完全忘了交互题咋写了（反正之前写的也少）
3. lucas定理忘记推到（TODO补一下
4. 大概从上午十点半做到十一点半，中午打了两把王者，下午两点半到三点五十AK，唯一欣慰的AK了

A A+B Again?

有一个两位数，求两位数的和

读入字符，直接加 - 2*'0'，较简单

void solve() {
  string s;
  cin >> s;
  cout << s[0] + s[1] - 2 * '0' << endl;
}

B. Card Game

有4个卡片，每个人两张，数字是1-10。

由2个回合组成。在一轮游戏中，双方随机抽取一张未翻开的牌并翻开。翻开的牌中数字严格意义上更大的一方获胜。如果数字相等，则无人获胜。

如果一名玩家赢得的回合数最多(即严格意义上大于另一名玩家)，则该玩家赢得游戏。如果相等，则无人获胜。

计算A获胜的可能性有几种

由于就2*2 = 4 个组合，枚举一下不同的组合就可以了，AB分别选一张后，另外一轮的结果也确定了

因此直接枚举第一轮的选择，判定a是不是能赢1次平一次或赢两次即可

void solve() {
  int a[2], b[2];
  cin >> a[0] >> a[1] >> b[0] >> b[1];
  int ans = 0;
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      if (a[i] > b[j] && a[!i] >= b[!j]) {
        //一胜一不输
        ans++;
      }
      if (a[i] == b[j] && a[!i] > b[!j]) {
        //一平一胜
        ans++;
      }
    }
  }
  cout << ans << endl;
}

C. Showering

一天共有$m$分钟，需要$s$分钟去洗澡，这一天中共有$n$个区间时刻$[l_i,r_i]$要忙，并且工作时刻不重叠，判断是不是能找到这么一段时间可以去洗澡。

因为不重叠，所以可以按要忙的区间对区间先后顺序排序，然后判定相邻的区间的停止时间是不是不小于$s$即可

特殊判定为第一个区间到0和最后一个区间结束到$m$是否满足即可

void solve() {
  int n, m, s;
  cin >> n >> s >> m;
  vector<array<int, 2>> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i][0] >> a[i][1];
  }
  sort(a.begin(), a.end());
  int cnt = 0;
  a.push_back({m, m});
  for (auto& x : a) {
    if (x[0] - cnt >= s) {
      cout << "YES\n";
      return;
    }
    cnt = x[1];
  }
  cout << "NO\n";
}

D. Slavic's Exam

有一个字符串$s$，其中？可以替换成任意字符，另一个字符串$t$是否可以在$s$中匹配到一个子序列

由于有先后顺序的子序列，不能直接统计

双指针分别判定找公共序列，按照先后顺序即可；如果s中无法匹配$t$​中的任意一个字符，即跳出，无法满足。、

最终将未使用的？替换为任意字符

void solve() {
  string s, t;
  cin >> s >> t;
  int i = 0, j = 0;
  while (i < s.size() && j < t.size()) {
    bool ok = false;
    while (s[i] != t[j] && i < s.size()) {
      if (s[i] == '?') {
        s[i] = t[j];
        break;
      }
      i++;
    }
    if (s[i] == t[j]) {
      j++;
      i++;
    }
  }
  for (auto& ch : s) {
    if (ch == '?') ch = 'a';
  }
  if (j == t.size()) {
    cout << "YES\n" << s << endl;
  } else {
    cout << "NO\n";
  }
}

E. Triple Operations

给一个区间$[l,r]$，区间中可以选择两个数字$x,y$,使$x=3x$ and $y=\lfloor \frac{y}{3} \rfloor$，问需要多少次操作后可以把所有数字变为0

对于一个数字变为0，肯定要执行$t$次$y=\lfloor \frac{y}{3} \rfloor$操作。同时会伴随非0数变大， 并且变大的数字若变回原数字的范围要执行$t$次同样的出发操作，从而选择非0数字的代价使一个数变为0的代价为$2t$,因此应先得到一个0后执行$t$次操作得到其他的0.

对于第一个0，则执行第一个数的次数即可，

然后发现区间$[3^\ell,3^\ell-1]$需要执行$\ell$次操作变为0，因此直接二分$\ell$统计结果

ll p[20];
void solve() {
  int l, r;
  cin >> l >> r;
  int ans = 0;
  int a0 = l;
  while (a0 != 0) {
    a0 /= 3;
    ans += 2;
  }
  l++;
  while (l <= r) {
    int idx = lower_bound(p, p + 20, l - 1) - p;
    if (p[idx] > l) {
      idx--;
    }
    int right = min(1ll * r, p[idx + 1] - 1);
    ans += 1ll * (right - l + 1) * (idx + 1);
    l = right + 1;
  }
  cout << ans << endl;
}

F. Expected Median

一个二进制字符串，问有所有长度为$k$（奇数）的子序列的中位数的和，mod $1e9+7$

对于长度$n$变为$k$来说，需要去掉$n-k$个数字，二进制序列中如果1的个数大于0，则中位数为1，否则为0，0对求和没有贡献，只考虑去掉的组合情况中去掉后1比0多的情况。

对于$n-k$个待去除的数字，假设去掉$i$个1，则去掉$n-k-1$个0，在可去除的情况下（1和0够用/去除后大于0个）时则执行操作计算当前的去除可能性。最终答案
$ \sum {C_{c0}^i \times C{c_1}^j | c0-i < c1-j \And i+j = n-k } $
其中$c_0$是0的个数，$c_1$是1的个数

const int mod = 1e9 + 7;
const int MAX_N = 2e5 + 10;

vector<long long> fact(MAX_N + 1);
vector<long long> inv_fact(MAX_N + 1);
long long pow_mod(long long a, long long b) {
  long long result = 1;
  while (b > 0) {
    if (b & 1) result = (result * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return result;
}

void precompute() {
  fact[0] = 1;
  for (int i = 1; i <= MAX_N; ++i) {
    fact[i] = (fact[i - 1] * i) % mod;
  }

  inv_fact[MAX_N] = pow_mod(fact[MAX_N], mod - 2);
  for (int i = MAX_N - 1; i >= 0; --i) {
    inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % mod;
  }
}

long long C(int n, int k) {
  // if (k == 0) return 0;
  if (k < 0 || k > n) return 0;
  ll res = (fact[n] * inv_fact[k] % mod) * inv_fact[n - k] % mod;
  return res;
}
void solve() {
  int n, k;
  cin >> n >> k;
  int c1 = 0, c0 = 0;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    c1 += (x == 1);
  }
  c0 = n - c1;
  int sub = n - k;
  int ans = 0;
  for (int i = 0; i <= sub; i++) {
    int j = sub - i;
    if (j > c0 || j < 0 || i > c1) continue;
    if (c1 - i < c0 - j) continue;
    ans = (ans + 1ll * C(c1, i) * C(c0, j)) % mod;
  }
  cout << ans << endl;
}

G. Expected Median

两个版本，简单版本可以询问10次，困难版本7次

有一把尺子，其中某个刻度$x\in[2,999]$​不存在，但量程不变

• 如果是 $y<x$，标尺(正确)测量的物体长度为 $y$ 。
• 如果为 $y\geq x$，则标尺错误地测量出物体的长度为 $y+1$ 。

每次可以询问一个实际大小为$a\times b$的矩形的面积，返回按照缺少刻度的尺子的面积，交互确定$x$

由于询问的$a\times b$的计算结果有3个可能

$ask(a,b) = a\times b$，则$x< \min(a,b)$

$ask(a,b) = (\min(a,b)+1)\times \max(a,b)$，则$x\in[\min(a,b),\max(a,b))$

$ask(a,b) = (\max(a,b)+1)\times (\min(a,b)+1)$，则$x\in(\max(a,b),999]$

返回结果恰好将当前区间分为3份额，因此可以通过三分区间进行二分查找判定具体位置

先计算每个区间的长度$(r-l)\div 3 $，枚举第二个区间和第三个区间的左端点分别作为$a$和$b$，根据返回结果更新区间。

由于$999<3^7$，则可以在7次内完成查找

void solve() {
  int l = 2, r = 999;
  while (l < r) {
    int mid = (r - l) / 3;
    int lmid = l + mid, rmid = l + mid + mid;
    cout << '?' << ' ' << lmid << ' ' << rmid << endl;
    int ans = ask(lmid, rmid);
    cin >> ans;
    if (ans == (lmid + 1) * (rmid + 1)) {
      r = lmid;
    }
    if (ans == (lmid) * (rmid + 1)) {
      l = lmid + 1;
      r = rmid;
    }
    if (ans == lmid * rmid) {
      l = rmid + 1;
    }
  }
  cout << "! " << l << endl;
}