多年不考試，一夜回到解放前

• T1：花園
• • title
  • solution
  • code
• T2：月亮神樹
• • title
  • solution
  • code
• T3：保護出題人
• • title
  • solution
  • code

T1：花園

title

小 L 有一座環形花園，沿花園的順時針方向，他把各個花圃編號為 1～n。花圃 1 和 n 是相鄰的。
他的環形花園每天都會換一個新花樣，但他的花園都不外乎一個規則：任意相鄰 m 個花圃中都只有不超過 k 個 C 形的花圃，其余花圃均為 P 形的花圃。
例如，若 n=10 , m=5 , k=3 ，則
CCPCPPPPCC 是一種不符合規則的花圃。
CCPPPPCPCP 是一種符合規則的花圃。
請幫小 L 求出符合規則的花園種數對 109+7 取模的結果。
【輸入格式】
只有一行三個整數，分別表示 n, m, k。
【輸出格式】
輸出一行一個整數表示答案。
【樣例1】
garden.in garden.out
10 5 3 458
【樣例2】
garden.in garden.out
6 2 1 18
【數據規模與約定】
對于 40% 的數據，保證 n≤20。
對于 80% 的數據，保證 n≤105。
對于 100% 的數據，保證 2≤n≤1015 ，2≤m≤min(n,5)，1≤k≤m。

solution

不得不說一句，這個出題人是很有良心的

---

首先40分，直接暴力枚舉出每一種花圃裝修，然后進行$check$

---

接著80分，看數據范圍就可以明顯被$n,m$的量級差給沖擊到，$m$極其小，花圃不是$C$就是$P$
順其自然的聯想到狀壓$dp$求解，設$dp[i][s]$表示到第$i$個花圃為止，最后連續的$m$個花圃狀態為$s$
$$dp[i][s]=\sum _{s=0}^{(1<<m)?1}dp[i?1][s]$$
當然這中間的轉移需要判斷一下$s$中是否$1$過多（假設$C$為1）
兩者是否有轉移關聯性，因為對于$i$而言的前$m?1$個花圃應該是與$i?1$的后$m?1$個花圃是一樣的

---

最后100分
顯而易見，我們需要消除掉$n$帶來的巨大不可承受的時間復雜度，一般來說這么大的$n$
要么發現實現根本與$n$不掛鉤（通過某些轉移方程式），要么壓縮成$log$，亦或各種優化
在80分狀壓的時候，我畫了個示意圖，要求轉移之間某些花圃必須一一對應，連線段之間的相同
讓我的靈感一瞬閃過——矩陣快速冪！！！

只要兩個之間可以轉移我就置為$1$，最后把對角線的值加起來即可

code

#include <cstdio> #include <cstring> using namespace std; #define mod 1000000007 #define ll long long ll n, ans; int m, k, cnt; int t[205];bool count( int S ) {int tot = 0;while( S ) tot += S & 1, S >>= 1;return tot > k; }bool comp( int s1, int s2 ) {for( int i = 0;i <= m - 2;i ++ ) {int x1 = ( s1 >> i ) & 1;int x2 = ( s2 >> ( i + 1 ) ) & 1;if( x1 != x2 ) return 1;}return 0; } struct Matrix {ll c[50][50];Matrix() {memset( c, 0, sizeof( c ) );}Matrix operator * ( const Matrix &p ) {Matrix res;for( int i = 1;i <= cnt;i ++ )for( int k = 1;k <= cnt;k ++ )for( int j = 1;j <= cnt;j ++ )res.c[i][j] = ( res.c[i][j] + c[i][k] * p.c[k][j] % mod ) % mod;return res;}}A, B;Matrix qkpow( Matrix x, ll y ) {Matrix res;for( int i = 1;i <= cnt;i ++ ) res.c[i][i] = 1;while( y ) {if( y & 1 ) res = res * x;x = x * x;y >>= 1;}return res; }int main() {scanf( "%lld %d %d", &n, &m, &k );int S = 1 << m;for( int i = 0;i < S;i ++ )if( count( i ) ) continue;else t[++ cnt] = i;for( int i = 1;i <= cnt;i ++ )for( int j = 1;j <= cnt;j ++ )if( comp( t[i], t[j] ) ) continue;else A.c[i][j] = 1;B = qkpow( A, n );for( int i = 1;i <= cnt;i ++ )ans = ( ans + B.c[i][i] ) % mod;printf( "%lld", ans );return 0; }

T2：月亮神樹

title

JM今天過得實在是太慘了，他肥腸不爽，因此他搬出了他祖傳的月亮神樹。月亮神樹的光輝照耀XJTUACM，每分鐘都可以從所有被照射的人的手中奪取他1%的財產。JM覺得他很快就能賺得盆滿缽滿。然而月亮神樹不久后突然失控了，不僅不把它奪來的財產交給JM，甚至開始奪取JM的財產，把JM氣瘋了，趕緊關閉了月亮神樹。
因為月亮神樹沒運行多久就被關掉了，所以大家并沒有損失多少，迫于月亮神樹的威壓，并沒有人去理它。可是wzk昨天剛中了彩票，賺了100000000000￥，轉眼就被剝奪了很多。因為wzk太rich了，所以他的損失格外大。為了奪回財產，無敵的wzk決定消滅月亮神樹。
月亮神樹的構造非常神奇，它的枝杈交錯縱橫，樹上甚至存在環路，可以視為一個無向帶權連通圖的結構。月亮神樹有一個核心節點，記為 s 。要想消滅月亮神樹，必須找到月亮神樹的嚴格最不科學生成樹，這是它的弱點，這樣就能將其一舉摧毀。
定義：一個圖 G 的不科學生成樹是 G 的一棵子樹，在這棵子樹上，從核心節點 s 到任意一個節點 u 的最短路徑長度，和在原圖上是等長的。其中節點 s 是月亮神樹的核心節點。
定義：一個圖 G 的最不科學生成樹是 G 的所有不科學生成樹中，邊權和最小的一棵樹。
定義：一個圖 G 的嚴格最不科學生成樹是 G 的所有最不科學生成樹中，有序邊序列的字典序最小的一棵樹。
定義：一個圖 G 的有序邊序列是指，將圖上所有邊按編號從小到大排序后得到的編號序列。當然，子圖子樹也適用。
現在給定月亮神樹，即給定一個 n 個點 m 條邊的無向帶權連通圖，點的編號從1到n，邊的編號從1到m，給定核心節點的編號 s ，求其嚴格最不科學生成樹。
?
【輸入格式】
第一行三個正整數 n,m,s 。
接下來 m 行，第 i 行三個正整數 u,v,w ，表示編號為 i 的邊。
輸入保證圖是連通的，保證圖上不含重邊和自環。。
【輸出格式】
第一行兩個正整數 cnt 和 sum ，用空格隔開，其中 cnt 表示嚴格最不科學生成樹的邊的個數， sum 表示嚴格最不科學生成樹的邊權和。
接下來一行 cnt 個正整數，用空格隔開，為樹上所有邊的編號，按編號從小到大輸出。
【樣例1】
moontree.in moontree.out
3 3 3
1 2 1
2 3 1
1 3 2 2 2
1 2
【樣例2】
moontree.in moontree.out
4 4 4
2 3 1
1 2 1
3 4 1
4 1 2 3 4
1 3 4
【數據規模與約定】
對于25%的數據， 1≤n,m≤10 。
另有25%的數據， 1≤n,m≤100 。
對于100%的數據， 1≤n,m≤3*105 ，1≤wi≤109 。

solution

老師說這道題最水，可我這道題的分最少

聽完題解后覺得——確實很水
堆優化$dijkstra$時間復雜度$O(nlogn)$凸(艸皿艸 )！！！考試時我就想著先求出最短路，但我想著$dijkstra$時間復雜度不是$O(n^2)$嘜，我連堆優化寫法都想好了！！但是我敗在了時間復雜度上面，我就沒敲，靠！！一直寫的這種，我竟不知是堆優化，鴨血！！！

---

首先跑出每個點距離超級源點的最短路，然后思考對于每個點可能存在不止一條最短路
此時就要保證權值最小，權值最小的保證下又要編號最小
所以當同時多條最短路出現時，取權值最小，更新編號數組
權值一樣時，選編號更小者即可

---

code

#include <queue> #include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; #define ll long long #define MAXN 300005 struct Gragh {int v, id;ll w;Gragh(){}Gragh( int V, ll W, int ID ) {v = V, w = W, id = ID;} }; struct node {int v;ll w;node(){}node( int V, ll W ) {v = V, w = W;}bool operator < ( const node &t ) const {return w > t.w;} }; struct edge {int u, v, id;ll w;edge(){}edge( int U, int V, ll W, int ID ) {u = U, v = V, w = W, id = ID;} }E[MAXN]; priority_queue < node > q; vector < Gragh > G[MAXN]; int n, m, s, tot, cnt; ll ans; int flag[MAXN]; ll dis[MAXN]; bool vis[MAXN], used[MAXN];void dijkstra() {memset( dis, 0x3f, sizeof( dis ) );dis[s] = 0;q.push( node( s, 0 ) );while( ! q.empty() ) {int u = q.top().v; q.pop();if( vis[u] ) continue;vis[u] = 1;for( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i].v, w = G[u][i].w, id = G[u][i].id;if( dis[v] > dis[u] + w ) {dis[v] = dis[u] + w;q.push( node( v, dis[v] ) );flag[v] = id;}else if( dis[v] == dis[u] + w ) {if( w < E[flag[v]].w ) flag[v] = id;else if( w == E[flag[v]].w && id < E[flag[v]].id )flag[v] = id;}}} }int main() {scanf( "%d %d %d", &n, &m, &s );for( int i = 1;i <= m;i ++ ) {int u, v; ll w;scanf( "%d %d %lld", &u, &v, &w );G[u].push_back( Gragh( v, w, i ) );G[v].push_back( Gragh( u, w, i ) );E[i] = edge( u, v, w, i );}dijkstra();for( int i = 1;i <= n;i ++ )if( flag[i] ) {++ tot, ans += E[flag[i]].w;used[flag[i]] = 1;}printf( "%d %lld\n", tot, ans );for( int i = 1;i <= m;i ++ )if( used[i] ) printf( "%d ", i );return 0; }

T3：保護出題人

title

出題人銘銘認為給 SDOI2012 出題太可怕了，因為總要被罵，于是他又給 SDOI2013 出題了。
參加 SDOI2012 的小朋友們釋放出大量的僵尸，企圖攻擊銘銘的家。而你作為 SDOI2013的參賽者，你需要保護出題人銘銘。
僵尸從唯一一條筆直道路接近，你們需要在銘銘的房門前放置植物攻擊僵尸，避免僵尸碰到房子。第一關，一只血量為 a1 點的僵尸從距離房子 x1 米處勻速接近，你們放置了攻擊力為 y1點/秒的植物進行防御；第二關，在上一關基礎上，僵尸隊列排頭增加一只血量為 a2 點的僵尸，與后一只僵尸距離 d 米，從距離房子 x2 米處勻速接近，你們重新放置攻擊力為y2 點/秒的植物；……；第 n 關，僵尸隊列共有 n 只僵尸，相鄰兩只僵尸距離 d 米，排頭僵尸血量為 an 點，排第二的僵尸血量 an-1 ，以此類推，排頭僵尸從距離房子 xn 米處勻速接近，其余僵尸跟隨排頭同時接近，你們重新放置攻擊力為 yn 點/秒的植物。
每只僵尸直線移動速度均為 1 米/秒，由于植物射擊速度遠大于僵尸移動速度，可忽略植物子彈在空中的時間。所有僵尸同時出現并接近，因此當一只僵尸死亡后，下一只僵尸立刻開始受到植物子彈的傷害。
游戲得分取決于你們放置的植物攻擊力的總和，和越小分數越高，為了追求分數上界，你們每關都要放置攻擊力盡量小的植物。
作為 SDOI2013 的參賽選手，你們能保護出題人么？
【輸入格式】
第一行兩個空格隔開的正整數 n 和 d，分別表示關數和相鄰僵尸間的距離。
接下來 n 行每行兩個空格隔開的正整數，第 i + 1 行為 ai和 xi，分別表示相比上一關在僵尸隊列排頭增加血量為 ai 點的僵尸，排頭僵尸從距離房子 xi 米處開始接近。
【輸出格式】
一個數，n 關植物攻擊力的最小總和 ，保留到整數。
?
【樣例1】
protect.in protect.out
5 2
3 3
1 1
10 8
4 8
2 3 7

【樣例1 說明】
第一關：距離房子 3 米處有一只血量 3 點的僵尸，植物最小攻擊力為 1.00000；
第二關：距離房子 1 米處有一只血量 1 點的僵尸、3 米處有血量 3 點的僵尸，植物最小攻擊力為 1.33333；
第三關：距離房子 8 米處有一只血量 10 點的僵尸、10 米處有血量 1 點的僵尸、12 米處有血量 3 點的僵尸，植物最小攻擊力為 1.25000；
第四關：距離房子 8 米處有一只血量 4 點的僵尸、10 米處有血量 10 點的僵尸、12 米處有血量 1 點的僵尸、14 米處有血量 3 點的僵尸，植物最小攻擊力為 1.40000；
第五關：距離房子 3 米處有一只血量 2 點的僵尸、5 米處有血量 4 點的僵尸、7 米處有血量 10 點的僵尸、9 米處有血量 1 點的僵尸、11 米處有血量 3 點的僵尸，植物最小攻擊力為 2.28571。
【數據規模與約定】
對于 30%的數據，n≤103 。
對于 50%的數據，n≤104 。
對于 70%的數據，1≤n≤105 ，1≤d≤106 ，1≤x≤106 ，1≤a≤106 。
對于 100%的數據， 1≤n≤105 ，1≤d≤1012 ，1≤x≤1012 ，1≤a≤1012 。

solution

此題的$x,a$我們可以抽象在二維平面上，就很想我們做的三分燈泡模型↓↓
設$dp[i][j]$表示消滅第$i$關卡前$i?j$個僵尸所需要的攻擊力
為了保證自己不被吃掉，我們就要求第$i$關卡的$maxdp[i][j]$
對于$j$而言，攻擊力要求為$$(a_i+a_{i?1}+...+a_j)/(x_i+d?(i?j))$$
對于另一個$k$而言，假設$j<k$，則攻擊力要求為
$$(a_i+a_{i?1}+...a_j+...a_k)/(x_i+d?(i?j+j?k))$$
令$A=a_i+a_{i?1}+...+a_j,B=x_i+d?(i?j)$
則兩個式子分別為
$$A/B,(A+a_{j?1}+...+a_k)/(B+d?(j?k))$$
交叉相成
$$A?B+A?d?(j?k),A?B+B?(a_{j?1}+...+a_k)$$
相抵消
$$A?d?(j?k),B?(a_{j?1}+...a_k)$$
在轉化
$$A/B,(a_{j?1}+...+a_k)/(d?(j?k))$$
最后推出我們想要的方程式
$$y_i?=(1\le j\le i)max?\{(su{m}_i??su{m}_{j?1}?)/(x_i?+d\times (i?j)\}$$
類似于斜率優化一樣去維護一個下凸包，然后三分找最大斜率即可

code

#include <cstdio> #include <iostream> using namespace std; #define MAXN 100005 int n, top; double ans; long long d; int st[MAXN]; long long x[MAXN], a[MAXN], sum[MAXN];double calc1( int i, int j ) {return 1.0 * ( sum[i - 1] - sum[j - 1] ) / ( d * ( i - j ) ); }double calc2( int i, int j ) {return 1.0 * ( sum[i] - sum[j - 1] ) / ( x[i] + d * ( i - j ) ); }int main() {scanf( "%d %lld", &n, &d );for( int i = 1;i <= n;i ++ ) {scanf( "%lld %lld", &a[i], &x[i] );sum[i] = sum[i - 1] + a[i];}for( int i = 1;i <= n;i ++ ) {while( top > 1 && calc1( i, st[top] ) < calc1( st[top], st[top - 1] ) )top --;st[++ top] = i;int l = 1, r = top;while( l <= r ) {int tmp = ( r - l + 1 ) / 3;int mid1 = l + tmp - 1, mid2 = l + ( tmp << 1 ) - 1;if( mid1 == mid2 ) break;if( calc2( i, st[mid1] ) < calc2( i, st[mid2] ) ) l = mid1 + 1;else r = mid2 - 1;}ans += max( calc2( i, st[l] ), calc2( i, st[r] ) );}printf( "%0.f", ans );return 0; }

總結

以上是生活随笔為你收集整理的[选拔赛1]花园（矩阵快速幂），JM的月亮神树（最短路），保护出题人（斜率优化）的全部內容，希望文章能夠幫你解決所遇到的問題。

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