文章目錄

• A - Lexicographic Order
• B - AtCoder Quiz
• C - Inverse of Permutation
• D - Cutting Woods
• E - Sorting Queries
• F - Make Pair
• G - Groups

網址鏈接

A - Lexicographic Order

簽到題

#include <cstdio> #include <iostream> using namespace std; int main() {string s, t;cin >> s >> t;if( s < t ) printf( "Yes\n" );else printf( "No\n" );return 0; }

B - AtCoder Quiz

簽到題

#include <cstdio> #include <iostream> using namespace std; char s1[10], s2[10], s3[10];int main() {scanf( "%s %s %s", s1, s2, s3 );if( 'R' != s1[1] and 'R' != s2[1] and 'R' != s3[1] )printf( "ARC\n" );if( 'B' != s1[1] and 'B' != s2[1] and 'B' != s3[1] )printf( "ABC\n" );if( 'H' != s1[1] and 'H' != s2[1] and 'H' != s3[1] )printf( "AHC\n" );if( 'G' != s1[1] and 'G' != s2[1] and 'G' != s3[1] )printf( "AGC\n" );return 0; }

C - Inverse of Permutation

簽到題

#include <cstdio> #define maxn 200005 int n; int p[maxn], ans[maxn];int main() {scanf( "%d", &n );for( int i = 1;i <= n;i ++ )scanf( "%d", &p[i] ), ans[p[i]] = i;for( int i = 1;i <= n;i ++ )printf( "%d ", ans[i] );return 0; }

D - Cutting Woods

簽到題

剛開始想歪了，打算不思考直接暴力線段樹cao

后來一看1e9的長度，打擾了

再一想，直接set不也可以做到線段樹的功能嗎

直接把操作點扔進去，找左右最近的分割點即可

#include <set> #include <cstdio> using namespace std; set < int > s; int n, Q, c, x;int main() {scanf( "%d %d", &n, &Q );s.insert( 0 ), s.insert( n );while( Q -- ) {scanf( "%d %d", &c, &x );if( c == 1 ) s.insert( x );else {auto l = s.lower_bound( x );auto r = l; l --;printf( "%d\n", *r - *l );}}return 0; }

E - Sorting Queries

簽到題

可能會被排序操作嚇到TLE

實際上轉個彎就知道序列一定是前面有序后面無序的狀態

那么分開存進隊列即可，遇到排序就把無序的全都丟進有序隊列

每個點最多被操作入隊兩次

復雜度只有有序隊列的log罷了

這都是表面上嚇唬人的

#include <queue> #include <cstdio> using namespace std; priority_queue < int, vector < int >, greater < int > > q; queue < int > New; int Q, opt, x;int main() {scanf( "%d", &Q );while( Q -- ) {scanf( "%d", &opt );switch( opt ) {case 1 : {scanf( "%d", &x );New.push( x );break;}case 2 : {if( ! q.empty() )printf( "%d\n", q.top() ), q.pop();else printf( "%d\n", New.front() ), New.pop();break;}case 3 : {while( ! New.empty() )q.push( New.front() ), New.pop();break;}}} }

F - Make Pair

中檔題

必須要兩人是好關系，并且相鄰才行

果斷區間$dp$，根據范圍$200$果斷猜測時間復雜度應為$O(N^3)/O(N^3\log N)$

$d{p}_{i,j}:[i,j]$區間的人都成功配對離開的方案數，答案自然為$d{p}_{1,2n}$

考慮枚舉與$i$配對的是$k$，則$k$將區間$[i,j]$隔絕成兩個互相獨立的子問題，$d{p}_{i+1,k?1};;d{p}_{k+1,r}$

定義$d{p}_{i+1,i}=1$

假設$[i+1,k?1]$配對個數為$x(k?1?(i+1)+1=k?i?1)$，$[k+1,r]$的配對個數為$y(r?(k+1)+1=r?k)$

$$d{p}_{i,j}=\sum _{k=i+1}^{r}d{p}_{i+1,k?1}?d{p}_{k+1,r}?\left(\genfrac{}{}{0ex}{}{x+y+1}{y}\right)$$

$\left(\genfrac{}{}{0ex}{}{x+y+1}{y}\right)$：區間$[i,j]$的配對次數為$x+y+1$($i,k$的一次配對)，從中選擇$y$次操作右子區間

為什么不是從中選擇$x$次操作左子區間？

因為左子區間的操作事關$i,k$的相鄰問題，而右子區間無關

必須左子區間都操作完了才能操作$(i,k)$配對

所以說就不可能出現最后$x$次操作全都是操作左子區間，反而先操作$(i,k)$的配對，這樣是錯誤的，那么選$x$的組合數$\left(\genfrac{}{}{0ex}{}{x+y+1}{x}\right)$計算的方案數就是錯誤的

選擇右子區間操作的輪數后，剩下的$x+1$位置就固定了，最后一個一定是$(i,k)$的配對

#include <cstdio> #define int long long #define mod 998244353 #define maxn 405 int fac[maxn], inv[maxn]; bool good[maxn][maxn]; bool vis[maxn][maxn]; int dp[maxn][maxn]; int n, m;int qkpow( int x, int y ) {int ans = 1;while( y ) {if( y & 1 ) ans = ans * x % mod;x = x * x % mod;y >>= 1;}return ans; }void init() {fac[0] = inv[0] = 1;for( int i = 1;i < maxn;i ++ ) fac[i] = fac[i - 1] * i % mod;inv[maxn - 1] = qkpow( fac[maxn - 1], mod - 2 );for( int i = maxn - 2;i;i -- )inv[i] = inv[i + 1] * ( i + 1 ) % mod; }int C( int n, int m ) {return fac[n] * inv[m] % mod * inv[n - m] % mod; }int dfs( int l, int r ) {if( vis[l][r] ) return dp[l][r];if( l > r ) return vis[l][r] = dp[l][r] = 1;int &ans = dp[l][r];for( int i = l + 1;i <= r;i += 2 ) {if( ! good[l][i] ) continue;int x = i - l - 1 >> 1, y = r - i >> 1;ans = ( ans + dfs( l + 1, i - 1 ) * dfs( i + 1, r ) % mod * C( x + y + 1, y ) ) % mod; }vis[l][r] = 1;return ans; }signed main() {init();scanf( "%lld %lld", &n, &m );for( int i = 1, a, b;i <= m;i ++ ) {scanf( "%lld %lld", &a, &b );good[a][b] = good[b][a] = 1;}n <<= 1;printf( "%lld\n", dfs( 1, n ) );return 0; }

G - Groups

簡單題

設$d{p}_{i,j}:$ 前$i$個數一共使用了$j$個非空集合

那么轉移只會分為兩種

• $i$單獨成一個新集合
  • $d{p}_{i,j}+=d{p}_{i?1,j?1}$
• $i$放進前$j$個集合中的某一個
  • 集合無差別
  • 每一個取模$m$相同的數都在不同的集合
  • 前面與$i$同余的個數顯然為$?\frac{i?1}{m}?$
  • 不能放那些數所在的集合，剩下的集合都是可以放的
  • $d{p}_{i,j}+=d{p}_{i?1,j}?\max (0,j??\frac{i?1}{m}?)$

#include <cstdio> #include <iostream> using namespace std; #define int long long #define mod 998244353 #define maxn 5005 int n, m; int dp[maxn][maxn];signed main() {scanf( "%lld %lld", &n, &m );dp[0][0] = 1;for( int i = 1;i <= n;i ++ )for( int j = 1;j <= i;j ++ )dp[i][j] = ( dp[i - 1][j - 1] + dp[i - 1][j] * max( 0ll, j - ( i - 1 ) / m ) ) % mod;for( int i = 1;i <= n;i ++ )printf( "%lld\n", dp[n][i] );return 0; }

說實話，我覺得F G的題目分值給反了，前面竟然全是簽到水題，后面的經典DP還是可以給個好評的

總結

以上是生活随笔為你收集整理的[2021-09-04 AtCoder Beginner Contest 217] 题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。