文章目錄

• CF1251C Minimize The Integer
• acwing164：可達性統計
• Facebook Hacker Cup 2016 Round 1 Boomerang Tournament
• [Zjoi2012]小藍的好友(mrx)

CF1251C Minimize The Integer

…………………

給你一個大整數$a$，它由$n$位數字，也可能有前導零。

現在給你一種操作規則：如果相鄰的兩個數字的奇偶性不同，那么你就可以交換它們。

現在可以做任意次操作（可能一次都不做），求出通過這些操作可以獲得的最小整數是多少。

答案可以包含前導零

---

observation : 相鄰位才能交換，且要奇偶不同，所以同奇偶間的順序一定不會改變（不滿足交換條件）

奇偶不同之間的數就可以相互交換

這其實是一個歸并排序的過程，兩個隊列模擬即可

---

#include <cstring> #include <cstdio> #include <queue> using namespace std; #define maxn 300005 queue < int > odd, even, ans; char s[maxn]; int n;int main() {scanf( "%s", s + 1 );n = strlen( s + 1 );for( int i = 1;i <= n;i ++ ) {int x = s[i] - '0';if( x & 1 ) odd.push( x );else even.push( x );}while( ! odd.empty() and ! even.empty() ) {if( odd.front() < even.front() ) ans.push( odd.front() ), odd.pop();else ans.push( even.front() ), even.pop();}while( ! odd.empty() ) ans.push( odd.front() ), odd.pop();while( ! even.empty() ) ans.push( even.front() ), even.pop(); while( ! ans.empty() ) printf( "%d", ans.front() ), ans.pop();return 0; }

acwing164：可達性統計

給定一張$n$個點$m$條邊的有向無環圖，你需要分別統計從每個點出發能夠到達的點的數量

---

observation : 保證是有向無環圖，明顯可以用拓撲解決有向圖問題

但是很有可能多個點到的點有重復，那么單純的用$d{p}_i$($i$所能到達的點)進行累加便不可取，會算重

數據范圍$n\le 30000$，發現$n^2/32$其實是可以接受的

那么就可以用bitset優化，直接記錄能到達的點集，那么轉移就是取并

最后統計1的個數就行，這就直接知道到哪些點，便不會算重了

---

#include <iostream> #include <bitset> #include <vector> #include <cstdio> #include <queue> #include <map> using namespace std; #define maxn 30005 map < pair < int, int >, int > mp; bitset < maxn > dp[maxn]; vector < int > G[maxn]; queue < int > q; int n, m; int ans[maxn], d[maxn];int main() {scanf( "%d %d", &n, &m );for( int i = 1, u, v;i <= m;i ++ ) {scanf( "%d %d", &u, &v );if( mp[make_pair( u, v )] ) continue;else mp[make_pair( u, v )] = 1;G[v].push_back( u );d[u] ++;}for( int i = 1;i <= n;i ++ ) if( ! d[i] ) q.push( i );while( ! q.empty() ) {int u = q.front(); q.pop();dp[u][u] = 1;for( auto v : G[u] ) {d[v] --;dp[v] |= dp[u];if( ! d[v] ) q.push( v );}}for( int i = 1;i <= n;i ++ )printf( "%d\n", dp[i].count() );return 0; }

Facebook Hacker Cup 2016 Round 1 Boomerang Tournament

這個周末，期待已久的BIT（回旋鏢邀請賽）將舉行！$N$個回旋鏢選手將隨機配對,進行單淘汰賽。

可以按以下方式解釋這種錦標賽規則：

$N$個選手以某種順序排列在隊列中（有序列表）

如果隊列當前僅包含$1$個選手，則比賽結束,該選手作為冠軍

否則，取出排在隊列最前面的$2$名選手，讓他們比賽

比賽的獲勝者重新插入到隊列的最后面

從步驟$2$重復

當第$i$個和第$j$個選手比賽時

• 如果$W_{i,j}=1$時則第$i$個選手將獲勝
• 否則，第j個選手將獲勝。
• 請注意，對于所有$（1\le i，j\le N），W_{i,j}=0/1$，并且$W_{i,i}=0$（無論如何也不會與自己對戰），并且$Wi，j=Wj，i$（如果$i=j$）

注意: A擊敗B，B擊敗C，C擊敗A是有可能的

比賽結束后，每個選手都會獲得排名（即使他們在比賽中沒能幸存下來）

某個選手T的排名是一個整數，這個整數比排在他前面的且離他最近的某個選手S排名大1,

S贏得比賽的場數嚴格大于T贏得比賽的場數.

因為初始對局的順序未知,所以對于每個選手，想知道他們最終可能會獲得的最好（最小）和最差（最大）排名.

$T,n\le 16$，保證$n$為2的冪

---

最壞名次很好求，只要有人能打敗他，他就可以在第一輪被淘汰

最好名次用狀壓

設$d{p}_{s,i}:$ 在對抗人數集合為$s$狀態時，$i$成為最后勝者的可行性0/1 不可以/可以

• 顯然對抗人數一定是$2$的冪，這可以剪枝掉很多不必要的狀態

寫法嘗試了很多種

• 寫法一

  枚舉狀態$s$，枚舉$i$，再枚舉狀態$t$，并保證$s,t$的$1$個數一樣（是同一層的角逐），還要枚舉$j$表示$t$的優勝者

  就算加了很多剪枝，判斷優勝者是否屬于集合，是否可行

  但仍有很多不必要的枚舉

• 優化寫法一后的寫法二

  $bi{t}_k$：$1$的個數為$k$的所有集合$s$

  $nu{m}_s$：$s$狀態中為$1$的位置，相當于預處理出所有參賽人員，最后的優勝者一定對應位置為$1$

  當$n$達到$16$的時候$s,t$的枚舉還是會超時

• 優化寫法二的最終寫法

  枚舉狀態$now$，以及該層比賽的上一次比賽（半決賽）$s$，通過$?$可以求得另一半決賽的狀態$t$

  然后枚舉兩場半決賽的各自的優勝者

  根據優勝者之間$g$的關系，決出最后的勝者成為$now$狀態的優勝者

  再配合上一下集合完全包含的剪枝即可通過了

$n=16$狀態數為$65536$剪枝后又無法承受平方的枚舉

但是如果枚舉一次后，里面枚舉的只有一半，狀態數就會銳減為$2^8$

最后對于每一個$i$找出自己是優勝者的所有比賽中參賽人員最多的（$1$最多的狀態）

就是最好成績

---

#include <cstdio> #include <vector> #include <cstring> #include <iostream> #include <algorithm> using namespace std; vector < int > bit[20], num[1 << 20]; int dp[1 << 16][20], g[20][20]; int T, n; bool ok[20];int lowbit( int x ) { return x & -x; }int main() {ok[1] = ok[2] = ok[4] = ok[8] = ok[16] = 1;scanf( "%d", &T );for( int Case = 1;Case <= T;Case ++ ) {scanf( "%d", &n );for( int i = 0;i < n;i ++ )for( int j = 0;j < n;j ++ )scanf( "%d", &g[i][j] );memset( dp, 0, sizeof( dp ) );for( int i = 0;i < n;i ++ ) dp[1 << i][i] = 1;for( int i = 1;i <= n;i ++ ) bit[i].clear();for( int s = 1;s < ( 1 << n );s ++ ) if( ! ok[__builtin_popcount( s )] ) continue;else {bit[__builtin_popcount( s )].push_back( s );if( num[s].size() ) continue;elsefor( int i = 0;i < n;i ++ )if( s >> i & 1 ) num[s].push_back( i );}for( int k = 2;k <= n;k <<= 1 )for( int now : bit[k] )for( int s : bit[k >> 1] ) {if( ( now & s ) != s ) continue;int t = now ^ s;if( s > t ) continue;for( int i : num[s] ) {if( ! dp[s][i] ) continue;for( int j : num[t] ) {if( ! dp[t][j] ) continue;if( g[i][j] ) dp[now][i] = 1;else dp[now][j] = 1;}}}printf( "Case #%d:\n", Case );for( int i = 0;i < n;i ++ ) {bool flag = 1;for( int j = 0;j < n;j ++ )if( i == j ) continue;else flag &= g[i][j];int best, worst, cnt = 0;if( flag ) worst = 1;else worst = ( n >> 1 ) + 1;for( int s = 1;s < ( 1 << n );s ++ )if( dp[s][i] ) cnt = max( cnt, __builtin_popcount( s ) );if( cnt == n ) best = 1;else if( cnt == ( n >> 1 ) ) best = 2;else if( cnt == ( n >> 2 ) ) best = 3;else if( cnt == ( n >> 3 ) ) best = 5;else best = 9;printf( "%d %d\n", best, worst );}}return 0; }

[Zjoi2012]小藍的好友(mrx)

終于到達了這次選拔賽的最后一題，想必你已經厭倦了小藍和小白的故事，為了回饋各位比賽選手，此題的主角是貫穿這次比賽的關鍵人物——小藍的好友。

在幫小藍確定了旅游路線后，小藍的好友也不會浪費這個難得的暑假。與小藍不同，小藍的好友并不想將時間花在旅游上，而是盯上了最近發行的即時戰略游戲——SangoCraft。但在前往通關之路的道路上，一個小游戲擋住了小藍的好友的步伐。

“國家的戰爭其本質是搶奪資源的戰爭”是整款游戲的核心理念，這個小游戲也不例外。簡單來說，用戶需要在給定的長方形土地上選出一塊子矩形，而系統隨機生成了N個資源點，位于用戶所選的長方形土地上的資源點越多，給予用戶的獎勵也越多。悲劇的是，小藍的好友雖然擁有著極其優秀的能力，但同時也有著極差的RP，小藍的好友所選的區域總是沒有一個資源點。

終于有一天，小藍的好友決定投訴這款游戲的制造廠商，為了搜集證據，小藍的好友想算出至少包含一個資源點的區域的數量。作為小藍的好友，這自然是你分內之事。

Input

第一行包含兩個由空格隔開的正整數R,C,N，表示游戲在一塊[1,R]x[1,C]的地圖上生成了N個資源點

接下來有N行，每行包含兩個整數 x,y，表示這個資源點的坐標(1<=x<=R,1<=Y<=c)

Output

輸出文件應僅包含一個整數，表示至少包含一個資源點的區域的數量

具體的說，設N個資源點的坐標為(i=1…n),你需要計算有多少個四元組(LB,DB,RB,UB)滿足1<=LB<=RB<=R,1<=DB<=UB<=C，且存在一個i使得LB<=Xi<=RB,DB<=Yi<=UB均成立

Sample Input

5 5 4 1 2 2 3 3 5 4 1

Sample Output

139

Hint

【數據范圍】

對于100%的數據，R,C<=40000,N<=100000，資源點的位置兩兩不同，且位置為隨機生成

---

首先轉換成，總矩陣數量減去一條魚都不包含的矩陣數量

然后枚舉每一行$i$，當做矩陣的底

這就有點像求最大全$1$矩陣了

對于每一列處理出在$i$行以上最近的魚的距離，當成這一列的高

那這就是剛做的笛卡爾樹了

根據笛卡爾樹的根，把左右兒子分開獨立計算

貢獻為$(h[x]?h[fa[x]])?siz[x]?(siz[x]+1)/2$

當枚舉行往下移的時候，相當于整體+1，如果某列在當前枚舉行有魚，高度設為$0$就可以了

相當于對笛卡爾樹進行兩種操作，全局+1和單點修改為$0$

這可以用fhq-treap暴力不動樹

但是笛卡爾樹作為一種二叉樹，又滿足小根堆性質，發現用帶旋treap維護樹不會改變本質

---

#include <cstdio> #include <vector> using namespace std; #define maxn 100005 #define int long long #define lson t[x].son[0] #define rson t[x].son[1] vector < int > g[maxn]; struct node { int l, r, h, f, tag, siz, son[2]; }t[maxn]; int dp[maxn]; int n, m, N;int calc( int x ) { return x * ( x + 1 ) >> 1; }void pushup( int x ) {t[x].siz = t[lson].siz + t[rson].siz + 1;dp[x] = dp[lson] + dp[rson] + ( t[x].h - t[t[x].f].h ) * calc( t[x].siz ); }void rotate( int x ) {int fa = t[x].f;int Gfa = t[fa].f;int k = t[fa].son[1] == x;if( Gfa ) t[Gfa].son[t[Gfa].son[1] == fa] = x;t[x].f = Gfa;t[fa].son[k] = t[x].son[k ^ 1];t[t[x].son[k ^ 1]].f = fa;t[x].son[k ^ 1] = fa;t[fa].f = x;if( t[fa].son[k] ) pushup( t[fa].son[k] );pushup( fa );pushup( x ); }void add( int x, int val ) {t[x].h += val;t[x].tag += val;pushup( x ); }void pushdown( int x ) {if( t[x].f ) pushdown( t[x].f );if( lson ) add( lson, t[x].tag );if( rson ) add( rson, t[x].tag );t[x].tag = 0; }int build( int l, int r ) {if( l > r ) return 0;int x = ( l + r ) >> 1;lson = build( l, x - 1 );rson = build( x + 1, r );if( lson ) t[lson].f = x;if( rson ) t[rson].f = x;pushup( x );return x; }signed main() {scanf( "%lld %lld %lld", &n, &m, &N );int rt = build( 1, m );for( int i = 1, x, y;i <= N;i ++ ) {scanf( "%lld %lld", &x, &y );g[x].push_back( y );}int ans = 0;for( int i = 1;i <= n;i ++ ) {add( rt, 1 );for( int x : g[i] ) {pushdown( x );while( t[x].f ) rotate( x );t[x].h = 0;if( lson ) pushup( lson );if( rson ) pushup( rson );pushup( x );rt = x;}ans += dp[rt];}printf( "%lld\n", calc( n ) * calc( m ) - ans );return 0; }

總結

以上是生活随笔為你收集整理的[2021-09-02 contest]CF1251C，可达性统计(bitset优化dp)，Boomerang Tournament(状压dp)，小蓝的好友(mrx)(treap平衡树)的全部內容，希望文章能夠幫你解決所遇到的問題。

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