A.

直接写就完了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve() {
  int n, a, q;
  cin >> n >> a >> q;
  int b=a,mx=a;
  rp(i,q){
    char c;
    cin>>c;
    if(c=='-')a--;
    if(c=='+')a++,b++;
    cmax(mx,a);
  }
  if(mx==n){
    cout<<"YES\n";
  }else if(b>=n){
    cout<<"MAYBE\n";
  }else{
    cout<<"NO\n";
  }
}

B.

考虑至多 $n-1$ 次，然后其实有些操作是不必要的，然后减掉这些不必要的就可以，但是这个实际上就是计算必要的部分。（下图写的是计算必要的。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve(){
  int n;
  cin>>n;
  vi p(n);
  rp(i,n){
    int x;
    cin>>x;
    --x;
    p[x]=i;
  }
  int w=0;
  rep(i,1,n)if(p[i-1]>p[i])++w;
  cout<<w<<"\n";
}

C.

考虑每次操作其实是向前平移一位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve() {
  int n,k;
  cin>>n>>k;
  vi a(n);
  rp(i,n)cin>>a[i];
  set<int>s;
  rp(i,n+2)s.insert(i);
  rp(i,n)if(s.count(a[i]))s.erase(a[i]);
    rp(j,n){
      int x=a[j];
      a[j]=*s.begin();
      s.erase(s.begin());
      s.insert(x);
    }
  a.pb(*s.begin());
  // debug(a);
  rp(i,n){
    cout<<a[((i-k+1)%(n+1)+n+1)%(n+1)]<<" \n"[i+1==n];
  }
}

D.

考虑到横竖相互不影响。

所以我们优先考虑竖着的，横着的同理。

对于竖着的，我们存一下上面的那个 $(x, y)$，如果 $x$ 相同的没有偶数个，那么必定构造不出来，因为你可以考虑第一个只有奇数个的那一行，就已经构造失败了。

然后考虑竖着的构造方式，比如说

1
2
3
4
UU
DD
UU
DD

如果 $(x1)$ 这一行和 $(x2)$ 这一行采用相同策略，那么就会构造出一个错误的答案，但是我们可以考虑更换行的时候翻转，这样就没有问题了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
void solve() {
  int n,m;
  cin>>n>>m;
  vc<pii> a;
  vc<pii> b;
  rp(i,n)rp(j,m){
    char c;
    cin>>c;
    if(c=='U')
      a.pb(i,j);
    if(c=='L')
      b.pb(i,j);
  }
  vc<vi> ans(n,vi(m,-1));
  int c=0;
  int p=-1;
  for(auto [x,y]:a){
    if(x!=p){p=x,c^=1;}
    ans[x][y]=c;
    ans[x+1][y]=c^1;
    c^=1;
  }
  c=0;
  p=-1;
  sort(all(b),[&](auto A,auto B){
    return A.second<B.second;
  });
  for(auto [x,y]:b){
    if(y!=p){p=y,c^=1;}
    ans[x][y]=c;
    ans[x][y+1]=c^1;
    c^=1;
  }
  vi row(n),col(m);
  rp(i,n)rp(j,m){
    if(ans[i][j]==1){
      row[i]++;
      col[j]++;
    }else if(ans[i][j]==0){
      row[i]--;
      col[j]--;
    }
  }
  bool ok=true;
  rp(i,n)if(row[i])ok=false;
  rp(i,m)if(col[i])ok=false;
  if(!ok)cout<<"-1\n";
  else{
    rp(i,n){
      rp(j,m){
        if(ans[i][j]==1){
          cout<<'W';
        }else if(ans[i][j]==0){
          cout<<'B';
        }else{
          cout<<'.';
        }
      }
      cout<<"\n";
    }
  }
}

E.

建立反图，那么把反图中没有入度的点塞进去，用拓扑排序跑最长路，然后每个点得到一个距离 $d_u$，然后知道如果从 $u$ 这个地方开始走，走到最后一定是 $[h_u, h_u+d_u]$ 才能完成，然后把这些区间都塞进去。

容易知道每个的起点只可能是 $[h_u, h_u + k]$，然后就可以枚举左端点来做出这个题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
void solve() {
  int n,m,k;
  cin>>n>>m>>k;
  vc<ll> h(n),d(n,0);
  rp(i,n)cin>>h[i];
  vc<vc<pair<ll,ll>>>g(n);
  vi deg(n),out(n);
  rp(i,m){
    int x,y;
    cin>>x>>y;
    --x,--y;
    ll cost=h[y]-h[x];
    if(cost<0)cost+=k;
    g[y].pb(x,cost);
    out[y]++;
    deg[x]++;
  }
  queue<int>q;
  rp(i,n)if(deg[i]==0)q.emplace(i);
  while(sz(q)){
    int u=q.front();q.pop();
    // debug(u);
    for(auto [v,w]:g[u]){
      // debug(v,w);
      cmax(d[v],d[u]+w);
      if(--deg[v]==0){
        q.emplace(v);
      }
    }
  }
  // debug(d);
  vc<pair<ll,ll>>t;
  rp(i,n)if(out[i]==0)t.pb(h[i],h[i]+d[i]);
  // debug(t);
  sort(all(t));
  ll R=0;
  for(auto [x,y]:t)cmax(R,y);
  ll ans=lnf;
  for(auto [x,y]:t){
    cmin(ans,R-x);
    cmax(R,y+k);
  }
  cout<<ans<<"\n";
}

F.

分情况讨论。

令 $s = a_l \oplus … \oplus a_r$。

$x = a_l\oplus…\oplus a_k$。

$y=a_{k+1}\oplus…a_r$。

  • $s=0$，我们可以选择任意的一个 $k$，因为随便怎么选都是 $x=y$。
  • $s \neq 0$，那么可以选择左边这样的 $k$，使得 $s$ 的最高位和 $x$ 的某一位相同。因为 $y$ 没有这个位，所以比 $x$ 要小。右侧对 $y$ 也同理。

我们将长度不递增的办法来遍历所有子数组。记录 $l_L$ 为左端点为 $L$ 的所有异或和的最高位的并，然后检查 $s$ 和这个位置开始的有没有相交的部分，如果有的话，那么他肯定是可以更新的，如果他可以更新，那么可以考虑下一步的转移，也就是把可行的部分的 $s$ 的最高位，扔到 $l_L$ 和 $r_R$ 里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
const ll U = (1LL << 61) - 1;
void solve() {
  int n;
  cin >> n;
  vc<ll> a(n);
  rp(i, n) cin >> a[i];
  if (n == 1) {
    cout << 1 << "\n";
    return;
  }

  vc<ll> b(n + 1), l(n), r(n);
  b[0] = 0;
  rp(i, n) b[i + 1] = b[i] ^ a[i], l[i] = r[i] = 0;
  if (b[n] == 0)
    l[0] = r[n - 1] = U;
  else
    l[0] = r[n - 1] = 1LL << __lg(b[n]);
  for (int len = n - 1; len >= 1; len--) {
    for (int L = 0, R = len - 1; R < n; L += 1, R += 1) {
      ll val = b[R + 1] ^ b[L];
      bool ok = false;
      if (l[L] & val)
        ok = true;
      if (l[L] == U)
        ok = true;
      if (r[R] & val)
        ok = true;
      if (r[R] == U)
        ok = true;
      ll hb = __lg(val);
      if (ok) {
        if (val == 0) {
          l[L] = r[R] = U;
        } else {
          l[L] |= 1LL << hb;
          r[R] |= 1LL << hb;
        }
      }
      if (len == 1) {
        cout << (ok ? '1' : '0');
      }
    }
  }
  cout << "\n";
}

注意对 $s=0$ 的处理即可。