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 ()); rp (i,n){ cout<<a[((i-k+1 )%(n+1 )+n+1 )%(n+1 )]<<" \n" [i+1 ==n]; } }
D. 考虑到横竖相互不影响。
所以我们优先考虑竖着的,横着的同理。
对于竖着的,我们存一下上面的那个 $(x, y)$,如果 $x$ 相同的没有偶数个,那么必定构造不出来,因为你可以考虑第一个只有奇数个的那一行,就已经构造失败了。
然后考虑竖着的构造方式,比如说
如果 $(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 (); for (auto [v,w]:g[u]){ cmax (d[v],d[u]+w); if (--deg[v]==0 ){ q.emplace (v); } } } vc<pair<ll,ll>>t; rp (i,n)if (out[i]==0 )t.pb (h[i],h[i]+d[i]); 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$ 的处理即可。