文章目錄

• T1：糖果機器
• • solution
  • code
• T2：手套
• • solution
  • code
• T3：甲蟲
• • solution
  • code
• T4：選舉
• • solution
  • code

T1：糖果機器

solution

考慮從第$i$個糖果出發能到達第$j$個，則有$T_j?T_i\ge |S_j?S_i|$
$$\{\begin{array}{r}{T}_j?T_i\ge S_j?S_i\\ T_j?T_i\ge S_i?S_j\end{array}=>\{\begin{array}{r}{T}_i+S_i\ge T_j+S_j\\ T_i?S_i\ge T_j?S_j\end{array}$$
發現這其實是函數同構體

令$A=T_i+S_i,B=T_i?S_i$，則👆可轉化為👇
$$\{\begin{array}{r}{A}_i\ge A_j\\ B_i\ge B_j\end{array}$$
又發現此題就是一個二維偏序問題
其實就是noip普及組1999導彈攔截

二維偏序問題，一般是一維時間軸有序，然后二維套樹狀數組，總體上復雜度是$log$級別

code

#include <set> #include <cstdio> #include <algorithm> using namespace std; #define maxn 100005 struct node {int s, t, id;friend bool operator < ( const node &x, const node &y ) {return x.s + x.t < y.s + y.t;} }p[maxn]; set < node > st; int n, tot;bool cmp( node x, node y ) {return ( x.t - x.s == y.t - y.s ) ? ( x.t + x.s < y.t + y.s ) : ( x.t - x.s < y.t - y.s ); }int main() {scanf( "%d", &n );for( int i = 1;i <= n;i ++ )scanf( "%d %d", &p[i].s, &p[i].t );sort( p + 1, p + n + 1, cmp );for( int i = 1;i <= n;i ++ ) {set < node > :: iterator it = st.upper_bound( p[i] );if( it == st.begin() ) p[i].id = ++ tot;else it --, p[i].id = it->id, st.erase( it );st.insert( p[i] );}printf( "%d\n", tot );for( int i = 1;i <= n;i ++ )printf( "%d %d %d\n", p[i].s, p[i].t, p[i].id );return 0; }

T2：手套

solution

code

#include <cstdio> #include <algorithm> using namespace std; #define maxn 20 struct node {int x, y; }p[1 << maxn]; int n; int a[maxn], b[maxn];bool cmp( node s, node t ) {return ( s.x == t.x ) ? ( s.y > t.y ) : ( s.x < t.x ); }void update( long long &ansx, long long &ansy, long long x, long long y ) {if( ( x + y < ansx + ansy ) || ( x + y == ansx + ansy && x < ansx ) )ansx = x, ansy = y; }int main() {scanf( "%d", &n );for( int i = 0;i < n;i ++ )scanf( "%d", &a[i] );for( int i = 0;i < n;i ++ )scanf( "%d", &b[i] );int m = 1 << n;for( int i = 0;i < m;i ++ )for( int j = 0;j < n;j ++ )if( i >> j & 1 ) p[i].x += a[j];for( int i = 0;i < m;i ++ )for( int j = 0;j < n;j ++ )if( i >> j & 1 ) p[m - 1 - i].y += b[j];long long flagx = p[m - 1].x, flagy = p[0].y, ansx = flagx, ansy = flagy;sort( p, p + m, cmp );for( int i = m - 1, y = 0;~ i;i -- ) {if( p[i].x != flagx && y != flagy )update( ansx, ansy, p[i].x + 1, y + 1 );y = max( p[i].y, y );}printf( "%lld\n%lld\n", ansx, ansy );return 0; }

T3：甲蟲

solution

區間dp還是一眼就看得出來，只不過不知道怎么處理時間問題，考場上錯誤代碼都能騙40

正著不行，就反著考慮

code

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define maxn 305 #define ll long long #define inf 0x3f3f3f3f int n, m, k; int x[maxn]; ll dp[2][maxn][maxn]; int vis[2][maxn][maxn];long long dfs( int t, int l, int r ) {if( r - l == k ) return 0;if( vis[t][l][r] == k ) return dp[t][l][r];vis[t][l][r] = k;int p = ( t ? r : l );ll &ans = dp[t][l][r];ans = inf;if( l != 1 ) ans = min( ans, dfs( 0, l - 1, r ) + ( x[p] - x[l - 1] ) * ( k - ( r - l ) ) );if( r != n ) ans = min( ans, dfs( 1, l, r + 1 ) + ( x[r + 1] - x[p] ) * ( k - ( r - l ) ) );return ans; }int main() {scanf( "%d %d", &n, &m );for( int i = 1;i <= n;i ++ )scanf( "%d", &x[i] );x[++ n] = 0;sort( x + 1, x + n + 1 );int pos;for( int i = 1;i <= n;i ++ )if( ! x[i] ) { pos = i; break; }ll ans = 0;for( k = 0;k < n;k ++ )ans = max( ans, 1ll * m * k - dfs( 0, pos, pos ) );printf( "%lld", ans );return 0; }

T4：選舉

solution

code

#include <cstdio> #include <iostream> using namespace std; #define maxn 500005 struct node {int minn, maxx, ans;node() {}node( int Min, int Max, int Ans ) {minn = Min, maxx = Max, ans = Ans;}friend node operator + ( const node &x, const node &y ) {return node( min( x.minn, y.minn ), max( x.maxx, y.maxx ), max( y.maxx - x.minn, max( x.ans, y.ans ) ) );} }t[maxn << 2]; int n, Q; char s[maxn]; int pre[maxn];void build( int num, int l, int r ) {if( l == r ) {t[num] = node( pre[l], pre[l], 0 );return;}int mid = ( l + r ) >> 1;build( num << 1, l, mid ), build( num << 1 | 1, mid + 1, r );t[num] = t[num << 1] + t[num << 1 | 1]; }node query( int num, int l, int r, int L, int R ) {if( L <= l && r <= R ) return t[num];int mid = ( l + r ) >> 1;if( R <= mid ) return query( num << 1, l, mid, L, R );else if( mid < L ) return query( num << 1 | 1, mid + 1, r, L, R );else return query( num << 1, l, mid, L, R ) + query( num << 1 | 1, mid + 1, r, L, R ); }int main() {scanf( "%d %s %d", &n, s + 1, &Q );for( int i = 1;i <= n;i ++ )pre[i] = pre[i - 1] + ( s[i] == 'T' ? -1 : 1 );build( 1, 0, n ); while( Q -- ) {int l, r;scanf( "%d %d", &l, &r );node ans = query( 1, 0, n, l - 1, r );printf( "%d\n", ans.ans - ( pre[r] - pre[l - 1] ) );}return 0; }

總結

以上是生活随笔為你收集整理的[2020-11-24 contest]糖果机器（二维偏序），手套（状压dp），甲虫（区间dp），选举（线段树 最大子段和）的全部內容，希望文章能夠幫你解決所遇到的問題。

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