文章目錄

• A - Tiny Arithmetic Sequence
• B - Do you know the second highest mountain?
• C - Secret Number
• D - Game in Momotetsu World
• E - Xor Distances
• F - Insertion Sort

Mynavi Programming Contest 2021（AtCoder Beginner Contest 201）

A - Tiny Arithmetic Sequence

$if?else$直接判

B - Do you know the second highest mountain?

$sort$排序

C - Secret Number

本來以為要計數$DP$/生成函數，但是仔細一看密碼位數固定只有$4$位，直接暴力枚舉判斷

D - Game in Momotetsu World

考試時一直正著跑兩人交替，總是錯；考慮過倒著跑回去，但是沒有實現出來（自己想要的效果）

每個人都是聰明的，都想盡可能拉開與對方的正差距，縮小與對方的負差距

$c_{i,j}?d{p}_{i,j}$寫得真的很妙

#include <cstdio> #include <iostream> using namespace std; #define maxn 2005 int dp[maxn][maxn], c[maxn][maxn]; char s[maxn]; int n, m;int main() {scanf( "%d %d", &n, &m );for( int i = 1;i <= n;i ++ ) {scanf( "%s", s + 1 );for( int j = 1;j <= m;j ++ )c[i][j] = ( s[j] == '+' ? 1 : -1 );}for( int i = n;i;i -- )for( int j = m;j;j -- ) {if( i == n && j == m ) continue;else if( i == n ) dp[i][j] = c[i][j + 1] - dp[i][j + 1];else if( j == m ) dp[i][j] = c[i + 1][j] - dp[i + 1][j];else dp[i][j] = max( c[i + 1][j] - dp[i + 1][j], c[i][j + 1] - dp[i][j + 1] );}if( dp[1][1] > 0 ) printf( "Takahashi\n" );else if( dp[1][1] < 0 ) printf( "Aoki\n" );else printf( "Draw\n" );return 0; }

E - Xor Distances

$E$竟然比$D$簡單凸(艸皿艸 )eggs

$d_{i,j}=d_{j,i}?d_{i,j}=d_{k,i}?d_{k,j}=d_{k,i}?d_{k,j}?d_{x,k}?d_{x,k}=d_{x,i}?d_{x,j}$

兩個點之間的最短距離異或等于任選一個點做超級點，超級點到兩個點的最短距離異或和(不妨就設為$1$)

異或是二進制操作，各位獨立，考慮拆解每一位$i$

如果$i$位有貢獻$2^i$，那么一定是兩個點到$1$的距離第$i$位異或為$1^0=1$

所以拆開每位分別統計有多少個點的距離該位為$1$，乘法原理，任何一個都可以和該位不是$1$的任何一個組起來

#include <cstdio> #include <vector> using namespace std; #define maxn 200005 #define int long long #define mod 1000000007 vector < pair < int, int > > G[maxn]; int n; int dep[maxn];void dfs( int u, int fa ) {for( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i].first, w = G[u][i].second;if( v == fa ) continue;else dep[v] = dep[u] ^ w, dfs( v, u );} }signed main() {scanf( "%lld", &n );for( int i = 1, u, v, w;i < n;i ++ ) {scanf( "%lld %lld %lld", &u, &v, &w );G[u].push_back( make_pair( v, w ) );G[v].push_back( make_pair( u, w ) );}dfs( 1, 0 );int ans = 0;for( int j = 0;j < 60;j ++ ) {int cnt = 0;for( int i = 1;i <= n;i ++ )if( 1ll << j & dep[i] ) cnt ++;else;ans = ( ans + ( 1ll << j ) % mod * cnt % mod * ( n - cnt ) % mod ) % mod;}printf( "%lld\n", ans );return 0; }

F - Insertion Sort

顯然，對于每個數最多只會操作一次，假設不動數的集合為$S$，且$S_1<S_2<...<S_x$

那么其必定滿足$po{s}_{S_1}<po{s}_{S_2}<...<po{s}_{S_x}$且對于某個點$i,i\in /S$

• $i:A_i$
• $po{s}_i<S_1:B_i$
• $S_x<po{s}_i:C_i$

設$d{p}_i:S$中最大下標為$i$時的最小操作數

$d{p}_i=min({\sum }_{j=1}^{i?1}min(A_j,B_j),{\min }_{j<i,po{s}_j<po{s}_i}(d{p}_j+{\sum }_{k=j+1}^{i?1}{A}_k)$

對$po{s}_i$建線段樹，$log$查詢

最后的答案即為$min(d{p}_i+{\sum }_{j=i+1}^{n}min(A_j,C_j))$

#include <cstdio> #include <iostream> using namespace std; #define inf 1e15 #define maxn 200005 #define int long long int n; int P[maxn], A[maxn], B[maxn], C[maxn]; int Asum[maxn], Bsum[maxn], Csum[maxn], pos[maxn]; int dp[maxn], t[maxn << 2];void modfiy( int num, int l, int r, int p, int v ) {if( l == r ) {t[num] = v;return;}int mid = ( l + r ) >> 1;if( p <= mid ) modfiy( num << 1, l, mid, p, v );else modfiy( num << 1 | 1, mid + 1, r, p, v );t[num] = min( t[num << 1], t[num << 1 | 1] ); }int query( int num, int l, int r, int L, int R ) {if( L <= l && r <= R ) return t[num];int mid = ( l + r ) >> 1, ans = inf;if( L <= mid ) ans = min( ans, query( num << 1, l, mid, L, R ) );if( mid < R ) ans = min( ans, query( num << 1 | 1, mid + 1, r, L, R ) );return ans; }signed main() {scanf( "%lld", &n );for( int i = 1;i <= n;i ++ ) {scanf( "%lld", &P[i] );pos[P[i]] = i;}for( int i = 1;i <= n;i ++ )scanf( "%lld %lld %lld", &A[i], &B[i], &C[i] );for( int i = 1;i <= n;i ++ ) {Asum[i] = Asum[i - 1] + A[i];Bsum[i] = Bsum[i - 1] + min( A[i], B[i] );Csum[i] = Csum[i - 1] + min( A[i], C[i] );}int ans = inf;for( int i = 1;i <= n;i ++ ) {dp[i] = min( Bsum[i - 1], query( 1, 1, n, 1, pos[i] ) + Asum[i - 1] );ans = min( ans, dp[i] + Csum[n] - Csum[i] );modfiy( 1, 1, n, pos[i], dp[i] - Asum[i] );}printf( "%lld\n", ans );return 0; }

總結

以上是生活随笔為你收集整理的Mynavi Programming Contest 2021（AtCoder Beginner Contest 201）题解的全部內容，希望文章能夠幫你解決所遇到的問題。

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