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$ 的处理即可。