狂歡2

• T1：冒泡排序
• • 題目
  • 題解
  • CODE
• T2：概率充電器
• • 題目
  • 題解
  • CODE
• T3：不勤勞的圖書管理員
• • 題目
  • 題解
  • CODE

我不這么認為。。。。

T1：冒泡排序

題目

下面是一段實現冒泡排序算法的 C++代碼：

for(int i=1; i<n; i++)for(int j=1; j<=n-i; j++)if(a[j]>a[j+1])swap(a[j],a[j+1]);

其中待排序的a數組是一個1,2…n的排列，swap 函數將交換數組中對應位置的值。
對于給定的數組 a 以及給定的非負整數k ，使用這段代碼執行了正好k次 swap 操作之后數組 a 中元素的值會是什么樣的呢？

題解

首先我們要了解冒泡排序的原理，舉個例子

3421

首先3會與4進行比較，不交換
接著4與2比較，交換
4往后移了一位，j下標也+1，所以j還是映射的是4，與1比較交換

外層第一輪i循環后的結果如下

3214

3與2比較，交換
j+1，3也右移了一位，j仍映射著3，與1比較交換
接著與4比較，小于4中斷，把接力棒給4，4是最后一位停止交換

外層第二輪i循環后的結果如下

2134

---

接下來，讓我們用理論來推導這個過程的一些規律
1.外層循環在第i次結束后，對應的第i大的數就會出現在自己應該在的位置，并且$[n?i+1,n]$這一區間是嚴格不下降序列（此題中是嚴格上升），👉每一次交換是成單調不下降的
換言之，即x會一直與右邊交換直到遇到一個比x大的y，然后x停下，y又與右邊交換直到遇到與x相似的情況…

2.對于每一個x，最多只會發生一次左移，因為它只會有一次與左邊的數進行比較，但是對于一個x可能發生多次右移，但x發生多少次右移就代表著有多少個數發生了左移，👉對于x，它左移的次數為左邊比它大的數的個數，因為那些比它大的數必須要越過x才能到達自己應該在的位置
最后如果x左邊沒有比它大的數后，它就會固定在這個位置，因為沒有數會越過它了

3.我們只考慮x左邊比它大的數，因為如果x要右移的話就意味著有其他的數會左移，把其他數左移后留下來的位置就是x的位置啦！

---

考慮用樹狀數組去求$[1,i?1]$區間比$a[i]$大的個數
然后用二分去枚舉外層循環的i，看能最多跑滿多少次外層循環
剩下的就是跑不滿的，那我們就暴力轉移一次即可

CODE

#include <queue> #include <cstdio> #include <iostream> using namespace std; #define LL long long #define MAXN 1000005 priority_queue < int > q; int n, ans; int a[MAXN], result[MAXN]; LL k; int maxx[MAXN], tree[MAXN];int lowbit ( int x ) {return x & ( -x ); }LL query ( int x ) {LL tot = 0;for ( int i = x;i >= 1;i -= lowbit ( i ) )tot += tree[i];return tot; }void add ( int x ) {for ( int i = x;i <= n;i += lowbit ( i ) )tree[i] ++; }LL check ( int x ) {LL tot = 0;for ( int i = 1;i <= n;i ++ )tot += min ( x, maxx[i] );return tot; }void solve ( int l, int r ) {if ( l > r )return;int mid = ( l + r ) >> 1;if ( check ( mid ) <= k ) {ans = mid;solve ( mid + 1, r );}elsesolve ( l, mid - 1 ); }int main() {scanf ( "%d %lld", &n, &k );for ( int i = 1;i <= n;i ++ ) {scanf ( "%d", &a[i] );maxx[i] = query ( n ) - query ( a[i] );add ( a[i] );}LL sum = 0;for ( int i = 1;i <= n;i ++ )sum += maxx[i];if ( sum < k )return ! printf ( "Impossible!" );solve ( 1, n - 1 );for ( int i = 1;i <= n;i ++ )if ( maxx[i] >= ans )result[i - ans] = a[i];elseq.push ( a[i] );for ( int i = n;i >= 1;i -- )if ( ! result[i] ) {result[i] = q.top();q.pop();if ( q.empty() )break;}k -= check ( ans );for ( int i = 1;i < n;i ++ )if ( result[i] > result[i + 1] ) {if ( ! k )break;swap ( result[i], result[i + 1] );k --;}for ( int i = 1;i <= n;i ++ )printf ( "%d ", result[i] );return 0; }

T2：概率充電器

題目

Luogu走一波
著名的電子產品品牌SHOI 剛剛發布了引領世界潮流的下一代電子產品—— 概率充電器：
“采用全新納米級加工技術，實現元件與導線能否通電完全由真隨機數決 定！SHOI 概率充電器，您生活不可或缺的必需品！能充上電嗎？現在就試試看 吧！”

SHOI 概率充電器由n-1 條導線連通了n 個充電元件。進行充電時，每條導 線是否可以導電以概率決定，每一個充電元件自身是否直接進行充電也由概率 決定。隨后電能可以從直接充電的元件經過通電的導線使得其他充電元件進行 間接充電。

作為SHOI 公司的忠實客戶，你無法抑制自己購買SHOI 產品的沖動。在排 了一個星期的長隊之后終于入手了最新型號的SHOI 概率充電器。你迫不及待 地將SHOI 概率充電器插入電源——這時你突然想知道，進入充電狀態的元件 個數的期望是多少呢？

輸入格式
第一行一個整數：n概率充電器的充電元件個數。充電元件由1-n 編號。
之后的n-1 行每行三個整數a, b, p，描述了一根導線連接了編號為a 和b 的 充電元件，通電概率為p%。
第n+2 行n 個整數：qi。表示i 號元件直接充電的概率為qi%。

輸出格式
輸出一行一個實數，為能進入充電狀態的元件個數的期望，四舍五入到小 數點后6 位小數。

輸入輸出樣例
輸入
3
1 2 50
1 3 50
50 0 0
輸出
1.000000

輸入
5
1 2 90
1 3 80
1 4 70
1 5 60
100 10 20 30 40
輸出
4.300000
說明/提示
對于30%的數據，n≤5000
對于100%的數據，n≤500000，0≤p,qi≤100

題解

又是期望，哎😔，先引入一些關于概率的計算，我用通俗易懂的文字幫助大家理解，不用去搞那么死板的事件我不會告訴你因為我也不是很清楚

事件A與事件B同時發生的概率=事件A發生的概率*事件B發生的概率
事件A和事件B只其中一件發生的概率=事件A發生的概率+事件B發生的概率-事件AB同時發生的概率
（可以不用看， 反正下面我不用）

---

設$dp[u]$表示$u$號充電器亮的期望
那么我們思考轉移方程式，如果$u$要亮，只需要任意一個兒子或者父親給它供電，所以$u$點亮的期望等于自己本身亮加上父親點亮加上任何一個兒子點亮的概率和，即
$dp[u]=\prod (v\in son[u])dp[v]?p_{u,v}+q[u]+dp[fa]?p_{u,fa}$

但是這么想，其實是錯誤的，因為這個轉移方程式的前提是$fa$與$u$的這一條充電線是好的，但是當我們用$u$在往上去轉移$fa$的時候，又不能保證這一條充電線是好的，并且這個轉移方程式中各個兒子間會重復，可能同時多個兒子供電的事件發生

---

因此我們反著來，設$dp[u]$表示$u$號充電器不亮的期望

那么轉移方程式也是類似的，如果$u$不亮，要所有兒子和父親都不給它供電，又有父親，算了我們先不管父親，重新定義$dp[u]$表示$u$號充電器不亮的期望，且只考慮u的兒子不給它供電導致的
$dp[u]=\prod (v\in son[u])(1?(1?dp[v])?p_{u,v})?(1?q[u])$

分條來理解含義，$(1?dp[v])$兒子$v$亮的概率，$p_{u,v}$這條充電線是好的，相乘就是兒子$v$給$u$供電的概率，再用$1?()$表示兒子不供電的概率，

為什么是相乘呢？因為所有兒子都不給它供電才能使得$u$不亮，所以這個事件是要同時發生的，并且要建立在$u$本身不亮的基礎上，所以是相乘，結果還是用到了之前的鋪墊打臉了

---

接下來我們必須去面對父親了，設$f[u]$表示$u$號充電器不亮的概率，且是只考慮父親不給它供電導致的
我們知道父子關系是相互的，$u$是$fa$的一個兒子，相反$fa$也是$u$的唯一父親，
所以$dp[fa]$的更新會有$u$的參與，那么我們現在又是考慮$fa$給$u$供電，
就必須把$u$給$fa$供電的概率給去掉，
$fa$給$u$供電的概率且不考慮$u$，是由$fa$的父親或者$fa$的其它兒子供應的
轉移方程式就出來了：
$f[u]=1?(1?(dp[fa]?f[fa]/(1?(1?dp[u])?f{a}_w)))?f{a}_w$

再分條理解：
$dp[fa]?f[fa]$則是父親不亮的期望(包含有父親的父親和父親的其他兒子給父親供電的兩種情況)
$(dp[fa]?f[fa]/(1?(1?dp[u])?f{a}_w)$則是排除掉$u$給$fa$供電的概率
$1?(dp[fa]?f[fa]/(1?(1?dp[u])?f{a}_w))$則是表示$fa$亮的期望，排除掉$u$供電使父親亮起來的概率
$(1?(dp[fa]?f[fa]/(1?(1?dp[u])?f{a}_w)))?f{a}_w$表示$fa$與$u$相連的充電線是好的，相乘則表示父親讓$u$亮的概率
最后減掉就是不亮的概率了

---

最后把$f[u]$和$dp[u]$相乘就表示沒有任何一個親戚能給該點供電，就是不亮的期望，最后把每個點用
1-不亮期望加起來就是亮起來的期望即答案
精度問題就定義一個極小值即可。。。

CODE

#include <cmath> #include <cstdio> #include <vector> using namespace std; const int eps = 1e-8; #define MAXN 1000005 struct node {int v;double w;node ( int V, double W ) {v = V;w = W;} }; vector < node > G[MAXN]; int n; double result; double dp[MAXN], f[MAXN];void dfs1 ( int u, int fa ) {f[u] = 1;dp[u] = 1 - dp[u];for ( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i].v;double w = G[u][i].w;if ( v == fa )continue;dfs1 ( v, u );dp[u] *= ( 1 - ( 1 - dp[v] ) * w );} }void dfs2 ( int u, int fa, double fa_w ) {if ( fabs ( 1 - ( 1 - dp[u] ) * fa_w ) > eps ) //維護精度 f[u] = 1 - ( 1 - ( dp[fa] * f[fa] / ( 1 - ( 1 - dp[u] ) * fa_w ) ) ) * fa_w;elsef[u] = 1 - fa_w;result -= dp[u] * f[u];for ( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i].v;if ( v == fa )continue;dfs2 ( v, u, G[u][i].w );} } int main() {scanf ( "%d", &n );for ( int i = 1;i < n;i ++ ) {int a, b;double w;scanf ( "%d %d %lf", &a, &b, &w );G[a].push_back( node ( b, w / 100 ) );G[b].push_back( node ( a, w / 100 ) );}for ( int i = 1;i <= n;i ++ ) {scanf ( "%lf", &dp[i] );dp[i] /= 100;}result = n;dfs1 ( 1, 0 );dfs2 ( 1, 0, 0 );printf ( "%.6f", result );return 0; }

T3：不勤勞的圖書管理員

題目

luogu鏈接
加里敦大學有個帝國圖書館，小豆是圖書館閱覽室的一個書籍管理員。他的任務是把書排成有序的，所以無序的書讓他產生厭煩，兩本亂序的書會讓小豆產生這兩本書頁數的和的厭煩度。現在有n本被打亂順序的書，在接下來m天中每天都會因為讀者的閱覽導致書籍順序改變位置。因為小豆被要求在接下來的m天中至少要整理一次圖書。小豆想知道，如果他前i天不去整理，第i天他的厭煩度是多少，這樣他好選擇厭煩度最小的那天去整理。

輸入格式
第一行會有兩個數，n，m分別表示有n本書，m天
接下來n行，每行兩個數，ai和vi，分別表示第i本書本來應該放在ai的位置，這本書有vi頁，保證不會有放置同一個位置的書
接下來m行，每行兩個數，xj和yj，表示在第j天的第xj本書會和第yj本書會因為讀者閱讀交換位置

輸出格式
一共m行，每行一個數，第i行表示前i天不去整理，第i天小豆的厭煩度，因為這個數可能很大，所以將結果模10^9 +7后輸出

輸入輸出樣例
輸入
5 5
1 1
2 2
3 3
4 4
5 5
1 5
1 5
2 4
5 3
1 3
輸出
42
0
18
28
48
說明/提示
對于20%的數據，1 ≤ ai; xj; yj ≤ n ≤ 5000, m ≤ 5000, vi ≤ 10^5
對于100%的數據，1 ≤ ai; xj; yj ≤ n ≤ 50000, m ≤ 50000, vi ≤ 10^5

題解

這道題與動態逆序對是類似的，也是一道樹套樹板題
$l$與$r$的交換只會影響$[l+1,r?1]$區間，$l$與$r$我們單獨判斷
1.原本$x$的優先級比$l$小的在交換后會與$l$形成逆序對，厭煩度則是這些$x$的頁數和加上滿足條件的$x$的個數乘以$l$的頁數
2.原本$x$的優先級比$l$大的在交換后會與$l$不再形成逆序對，要減去它的厭煩度，厭煩度則是這些$x$的頁數和加上滿足條件的$x$的個數乘以$l$的頁數
3.原本$x$的優先級比$r$小的在交換后會與$r$形成逆序對，厭煩度則是這些$x$的頁數和加上滿足條件的$x$的個數乘以$r$的頁數
4.原本$x$的優先級比$r$大的在交換后會與$r$不再形成逆序對，減去厭煩度，厭煩度則是這些$x$的頁數和加上滿足條件的$x$的個數乘以$r$的頁數

因為線段樹套平衡樹和線段樹套權值線段樹都要T，所以我被迫選擇樹狀數組套線段樹

CODE

#include <cstdio> #include <iostream> using namespace std; #define LL long long #define mod 1000000007 #define MAXN 500005 struct node {int l, r;LL v, cnt; }tree[MAXN * 100]; int n, m, Size; int root[MAXN * 100]; //注意開log級或者大一點，不然就會TLE/RE LL ans; LL a[MAXN], v[MAXN]; /*內層線段樹*/ void modify ( int &t, int l, int r, int id, LL w1, LL w2 ) {if ( ! t )t = ++ Size;tree[t].v = ( tree[t].v + w1 ) % mod;tree[t].cnt = ( tree[t].cnt + w2 ) % mod;if ( l == r )return; int mid = ( l + r ) >> 1;if ( id <= mid )modify ( tree[t].l, l, mid, id, w1, w2 );elsemodify ( tree[t].r, mid + 1, r, id, w1, w2 ); }void query ( int &t, int l, int r, int L, int R, LL &s1, LL &s2 ) {if ( ! t )return;if ( L <= l && r <= R ) {s1 = ( s1 + tree[t].v ) % mod;s2 = ( s2 + tree[t].cnt ) % mod;return;}int mid = ( l + r ) >> 1;if ( L <= mid )query ( tree[t].l, l, mid, L, R, s1, s2 );if ( mid < R )query ( tree[t].r, mid + 1, r, L, R, s1, s2 ); } /*外層樹狀數組*/ int lowbit ( int x ) {return x & ( -x ); }void Modify ( int x, int id, LL w1, LL w2 ) {for ( int i = x;i <= n;i += lowbit ( i ) )modify ( root[i], 1, n, id, w1, w2 ); }void Query ( int l, int r, int L, int R, LL &s1, LL &s2 ) {if ( L > R )return;LL w1 = 0, w2 = 0;//[l,r]=[1,r]-[1,l-1]for ( int i = r;i >= 1;i -= lowbit ( i ) )query ( root[i], 1, n, L, R, s1, s2 );for ( int i = l - 1;i >= 1;i -= lowbit ( i ) )query ( root[i], 1, n, L, R, w1, w2 );s1 = ( s1 - w1 + mod ) % mod;s2 = ( s2 - w2 + mod ) % mod; } //以下標作為外層樹狀數組，以優先級作為內層線段樹（樹狀數組套線段樹） int main () {scanf ( "%d %d", &n, &m );for ( int i = 1;i <= n;i ++ )scanf ( "%lld %lld", &a[i], &v[i] );for ( int i = 1;i <= n;i ++ ) {LL s1 = 0, s2 = 0;Modify ( i, a[i], v[i], 1 );Query ( 1, i - 1, a[i] + 1, n, s1, s2 );ans = ( ans + s1 + v[i] * s2 % mod ) % mod;}for ( int i = 1;i <= m;i ++ ) {int l, r;scanf ( "%d %d", &l, &r );if ( l == r ) {printf ( "%lld\n", ans );continue;}if ( l > r )swap ( l, r );//l和r進行交換，只會對(l,r)區間帶來影響 LL s1 = 0, s2 = 0, w1 = 0, w2 = 0;Query ( l + 1, r - 1, a[l] + 1, n, s1, s2 );//原本比l優先級高的在l交換后就形成了逆序對 Query ( l + 1, r - 1, 1, a[l] - 1, w1, w2 );//原本比l優先級低的在交換后就不再形成逆序對 ans = ( ans + s1 - w1 + mod ) % mod;ans = ( ans + s2 * v[l] % mod - w2 * v[l] % mod + mod ) % mod;//注意l和r的情況剛好是相反的 s1 = s2 = w1 = w2 = 0;Query ( l + 1, r - 1, 1, a[r] - 1, s1, s2 );//原本比r優先級低的在交換后就形成了逆序對 Query ( l + 1, r - 1, a[r] + 1, n, w1, w2 );//原本比r優先級高的在交換后就不再形成逆序對 ans = ( ans + s1 - w1 + mod ) % mod;ans = ( ans + s2 * v[r] % mod - w2 * v[r] % mod + mod ) % mod;//單獨考慮l和r之間的關系 if ( a[l] < a[r] )ans = ( ans + v[l] + v[r] ) % mod;if ( a[l] > a[r] )ans = ( ans - v[l] - v[r] + mod ) % mod;//很巧妙，如果要刪掉某一個數的信息，就傳mod-(...)，這樣相加再取模就剛好消成了0實現了刪除操作 Modify ( l, a[l], mod - v[l], mod - 1 );Modify ( r, a[r], mod - v[r], mod - 1 );Modify ( l, a[r], v[r], 1 );Modify ( r, a[l], v[l], 1 );swap ( a[l], a[r] );swap ( v[l], v[r] );printf ( "%lld\n", ans );}return 0; }

有什么問題歡迎評論，byebye

總結

以上是生活随笔為你收集整理的周末狂欢赛2（冒泡排序，概率充电器，不勤劳的图书管理员）的全部內容，希望文章能夠幫你解決所遇到的問題。

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