文章目錄

• T1：圖
• • solution
  • code
• T2：劫富濟貧
• • solution
  • code
• T3：小A的樹
• • solution
  • code
• T4：游戲
• • solution
  • code

T1：圖

【問題描述】
給你一個n個點，m條邊的無向圖，每個點有一個非負(fù)的權(quán)值ci，現(xiàn)在你需要選擇一些點，使得每一個點都滿足：
如果這個點沒有被選擇，則與它有邊相連的所有點都必須被選擇。
問：滿足上述條件的點集中，所有選擇的點的權(quán)值和最小是多少？
QYQ很快就解決了這個問題，但是他已經(jīng)回到了左下角……沒有留下答案，現(xiàn)在只好請你來解決這個問題啦！
【輸入描述】
從文件graph.in中輸入數(shù)據(jù)。
輸入的第一行包含兩個整數(shù)n，m
輸入的第二行包含n個整數(shù)，其中第i個整數(shù)代表ci
輸入的第三行到第m+2行，每行包含兩個整數(shù)u，v，代表點u和點v之間有一條邊
【輸出描述】
輸出到文件graph.out中。
輸出的第一行包含一個整數(shù)，代表最小的權(quán)值和
【樣例】
Sample Input
3 1
1 2 3
3 1
Sample Output
1
【樣例解釋】
只選擇1號點，滿足題意
【數(shù)據(jù)規(guī)模】
對于20% 的數(shù)據(jù)：n<=10
對于40%的數(shù)據(jù)：n<=20
對于100%的數(shù)據(jù)：1<=n<=50， 1<=m<=500， 0<=c<=1000
圖中可能會有重邊，自環(huán)。
點的編號為1—n。

solution

直接大法師 搜索即可
當(dāng)然不是指純$O(2^n)$那么頭鐵的暴搜
其實也差不多啦~
可以加入兩個強勁剪枝
①：當(dāng)前搜索的值已經(jīng)大于了已經(jīng)找到的最小值，就沒有搜下去的意義了
②：當(dāng)$u$點強制不選后，所有與$u$點直接相連的點就必須選，這也可以剪掉很多情況
最后就發(fā)現(xiàn)跑的賊nm快，但是就很玄學(xué)，懂？——算不了時間復(fù)雜度
直接幫你從$O(2^{50})$$T$飛直接剪進$AC$

這道題告訴我，有的時候正解真的就是普普通通的搜索，只不過平時因為都是思維方面的訓(xùn)練
所以搜索一般是用來想不出正解搞簡單的部分分用的算法
搜索——正解算法思考下優(yōu)先級可能沒那么高，但是當(dāng)什么算法都不行的時候，可能就要嘗試一下了
而且一般很小的范圍，除掉很巧妙的結(jié)論或者技巧題——貪心，狀壓，搜索就很大概率是正解
因為搜索的時間復(fù)雜度加上剪枝后就變得很玄學(xué)
所以考場上，就算知道暴搜點強制選了后，與之直接相連的點必須不選的情況下
我也沒敢直接就大法師沖，平時就是直接剛了，莫名這個時候穩(wěn)如一匹翻車的老狗

code

#include <cstdio> #include <vector> using namespace std; #define maxn 55 #define inf 0x3f3f3f3f vector < int > G[maxn]; int n, m, ans, minn, cnt; int c[maxn], p[maxn], tot[maxn]; bool vis[maxn], flag[maxn]; int g[maxn][maxn];void dfs1( int u, int fa ) {vis[u] = 1, p[++ cnt] = u;for( int i = 0;i < G[u].size();i ++ )if( vis[G[u][i]] ) continue;else dfs1( G[u][i], u ); }void dfs2( int u, int cost ) {if( cost > minn ) return;if( u > cnt ) {minn = min( minn, cost );return;}dfs2( u + 1, cost + c[p[u]] );if( ! flag[p[u]] && ! tot[p[u]] ) {for( int i = 0;i < G[p[u]].size();i ++ )tot[G[p[u]][i]] ++;dfs2( u + 1, cost );for( int i = 0;i < G[p[u]].size();i ++ )tot[G[p[u]][i]] --;} }int main() {scanf( "%d %d", &n, &m );for( int i = 1;i <= n;i ++ )scanf( "%d", &c[i] );for( int i = 1, u, v;i <= m;i ++ ) {scanf( "%d %d", &u, &v );g[u][v] = g[v][u] = 1;if( u == v ) flag[u] = 1; }for( int i = 1;i <= n;i ++ )for( int j = 1;j <= n;j ++ )if( g[i][j] ) G[i].push_back( j );for( int i = 1;i <= n;i ++ )if( ! vis[i] ) {cnt = 0, minn = inf;dfs1( i, 0 );dfs2( 1, 0 );ans += minn;}printf( "%d\n", ans );return 0; }

T2：劫富濟貧

【問題描述】
呂弗·普自小從英國長大，受到騎士精神的影響，呂弗·普的夢想便是成為一位劫富濟貧的騎士。
呂弗·普拿到了一份全國富豪的名單(不在名單上的都是窮人)，上面寫著所有富豪的名字以及他們的總資產(chǎn)，比如豪特斯·珀去年資產(chǎn)有86E，呂弗·普就會準(zhǔn)備搶來資助貧困的伯恩兄弟……
現(xiàn)在呂弗·普做了M次打劫計劃，每次要打劫若干個人，他想知道每次能打劫到的總資產(chǎn)是多少
【輸入格式】
第一行一個正整數(shù)N，代表富豪的個數(shù)
接下來N行，每行一個由小寫字母組成的字符串Si和一個非負(fù)整數(shù)Wi，分別代表第i個富豪的名字和第i個富豪的資產(chǎn)數(shù)量
然后一個正整數(shù)M，代表呂弗·普的打劫次數(shù)
接下來M行，每行第一個數(shù)為正整數(shù)Xi，代表這次要打劫Xi個人，接下來有X個字符串，說明了這Xi個人是誰
【輸出格式】
對于每次打劫任務(wù)，輸出一行一個整數(shù)表示打劫到的總資產(chǎn)
如果這次打劫任務(wù)中打劫了一個窮人，那就輸出-1
【樣例輸入】
2
a 10
b 20
3
2 a b
1 b
2 a c
【樣例輸出】
30
20
-1
【數(shù)據(jù)范圍與約定】
對于30% 的數(shù)據(jù)，輸入中每個名字的長度均為1
對于60% 的數(shù)據(jù)，N,∑Xi<= 100,輸入中每個名字的長度<=10
對于100%的數(shù)據(jù)，N,∑Xi<= 10^5 ，輸入中所有名字的總長<=2*10^6 ，Wi<=10^9，保證任意兩個富豪名字不同,但不保證打劫計劃中會不會有重復(fù)的人（重復(fù)的人會被重復(fù)打劫）

solution

法一：
直接$map$就跑，應(yīng)該是只能拿到$70\%$，但是我旁邊的香香mm就莫名卡過去了，我就沒卡過去
明知字典樹可做的情況下還是以為$3s$，再怎么說$map$也綽綽有余的

法二：$hash$應(yīng)該是能$A$的
法三：正解——$trie$字典樹
還是很裸的了，大部分人在一看到這句話肯定就知道怎么寫了

這里提一句關(guān)于數(shù)組大小的問題——此題只給了256MB
也就是說只允許一個$trie[2e6][26]$大小的數(shù)組再加點其他小數(shù)組
還必須留有一定的運行空間
剛開始我的$flag$數(shù)組開得跟$trie$一樣大，然后就自然地$MLE$
后面才領(lǐng)悟到——其實只用開$n$大小的就可以了
因為雖然字典樹是每個節(jié)點都有$26$個兒子，但是我總點數(shù)就等于總名字長度，不會超過$2e6$

code

#include <cstdio> #include <cstring> #define maxm 2000005 #define maxn 500005 int n, m, cnt; int trie[maxm][26], w[maxn]; char s[maxm]; int flag[maxm];void insert( char *s, int id ) {int p = 0, len = strlen( s );for( int i = 0;i < len;i ++ ) {int c = s[i] - 'a';if( ! trie[p][c] ) trie[p][c] = ++ cnt;p = trie[p][c];}flag[p] = id; }int query( char *s ) {int p = 0, len = strlen( s );for( int i = 0;i < len;i ++ ) {int c = s[i] - 'a';if( ! trie[p][c] ) return 0;p = trie[p][c];}return flag[p]; }int main() {scanf( "%d", &n );for( int i = 1;i <= n;i ++ ) {scanf( "%s %d", s, &w[i] );insert( s, i );}scanf( "%d", &m );for( int i = 1, x;i <= m;i ++ ) {scanf( "%d", &x );long long ans = 0;bool no = 0;for( int j = 1;j <= x;j ++ ) {scanf( "%s", s );int id = query( s );if( id ) ans += w[id];else no = 1;}if( no ) printf( "-1\n" );else printf( "%lld\n", ans );}return 0; }

T3：小A的樹

【問題描述】
給出一棵n個點的樹，每個點有黑白兩種顏色。q次詢問，每次詢問給出x和y，問能否選出一個x個點的聯(lián)通子圖，使得其中黑點數(shù)目為y。
【輸入描述】
第一行一個正整數(shù) T 表示數(shù)據(jù)組數(shù)。
對于每一組數(shù)據(jù)，第一行有兩個用空格隔開的正整數(shù)，分別是 n 和 q ，表示樹的節(jié)點數(shù)和詢問次數(shù)。
接下來 n-1 行，每行兩個用空格隔開的正整數(shù)和，表示和間有一條邊相連。
接下來一行有 n 個用空格隔開的整數(shù)，其中值若0，則表示第 i 個點為白色，否則為黑色。
接下來 q 行，每行兩個用空格隔開的整數(shù) x 和 y 。
T=1,n<=5000，q<=10^5
【輸出描述】
對于每一組數(shù)據(jù)，輸出 q 行，每行為 “YES” 或者 “NO” （不含雙引號），表示對于給定的和，能否滿足小A 的要求。
每相鄰兩組數(shù)據(jù)的輸出之間空一行。
【樣例輸入】
1
9 4
4 1
1 5
1 2
3 2
3 6
6 7
6 8
9 6
0 1 0 1 0 0 1 0 1
3 2
7 3
4 0
9 5
【樣例輸出】
YES
YES
NO
NO

solution

$T=1$就挺離譜兒的

這道題如果發(fā)現(xiàn)了一個性質(zhì)👇就很簡單了 然并卵，我既沒有發(fā)現(xiàn)也不覺得發(fā)現(xiàn)后就簡單了

對于某一大小的連通子圖，其包含黑點數(shù)的最小值與最大值之間的所有點數(shù)目都能夠取得到
簡單感性證明一下哈哈哈哈
一個連通子圖可以刪除一個點再加入一個點，保證連通子圖的大小依然不變
且此時黑點的數(shù)目變化最多只為$1$

然后此題就搖身一變?yōu)楹唵蔚臉湫蝑p帶背包

如果對樹形dp+背包不熟悉的可以先去做一下洛谷的選課

定義$f[i][j]$表示：$i$子樹中選$j$個點（即大小為$j$的連通子圖）中包含黑點個數(shù)的最大值
定義$g[i][j]$表示：$i$子樹中選$j$個點（即大小為$j$的連通子圖）中包含黑點個數(shù)的最小值

注意樹形背包的正確枚舉：只使用已經(jīng)遍歷過的點數(shù)目和當(dāng)前子樹中的點數(shù)目轉(zhuǎn)移
否則會被鏈卡到 $O(n^3)$

code

#include <cstdio> #include <vector> #include <cstring> using namespace std; #define maxn 5005 vector < int > G[maxn]; int T, n, Q; int w[maxn], siz[maxn]; int f[maxn][maxn], g[maxn][maxn];void dfs( int u, int fa ) {siz[u] = 1;f[u][1] = g[u][1] = w[u];for( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i];if( v == fa ) continue;dfs( v, u );for( int j = siz[u];j;j -- )for( int k = siz[v];k;k -- ) {f[u][j + k] = max( f[u][j + k], f[v][k] + f[u][j] );g[u][j + k] = min( g[u][j + k], g[v][k] + g[u][j] );}siz[u] += siz[v];}for( int i = 1;i <= n;i ++ ) {f[0][i] = max( f[0][i], f[u][i] );g[0][i] = min( g[0][i], g[u][i] );} }int main() {scanf( "%d", &T );while( T -- ) {scanf( "%d %d", &n, &Q );for( int i = 1, u, v;i < n;i ++ ) {scanf( "%d %d", &u, &v );G[u].push_back( v );G[v].push_back( u );}for( int i = 1;i <= n;i ++ )scanf( "%d", &w[i] );memset( g, 0x3f, sizeof( g ) );dfs( 1, 0 );for( int i = 1, x, y;i <= Q;i ++ ) {scanf( "%d %d", &x, &y );if( g[0][x] <= y && y <= f[0][x] ) printf( "YES\n" );else printf( "NO\n" );}}return 0; }

T4：游戲

【問題描述】
WYF從小就愛亂頂，但是頂是會造成位移的。他之前水平有限，每次只能頂出k的位移，也就是從一個整點頂?shù)搅硪粋€整點上。我們現(xiàn)在將之簡化到數(shù)軸上，即從 一個整點可以頂?shù)脚c自己相隔在k之內(nèi)的數(shù)軸上的整點上。現(xiàn)在WYF的頭變多了，于是他能頂?shù)礁h的地方，他能頂?shù)饺我庹c上。現(xiàn)在他在玩一個游戲，這個游 戲里他只能向正方向頂，同時如果他從i頂?shù)絡(luò)，他將得到a[j] * (j - i)的分?jǐn)?shù)，其中a[j]是j點上的分?jǐn)?shù)，且要求j > i, 他最后必須停在n上。
現(xiàn)給出1～n上的所有分?jǐn)?shù)，原點沒有分?jǐn)?shù)。他現(xiàn)在在原點，沒有分。WYF想知道他最多能得多少分。
【輸入描述】
第一行一個整數(shù)n。
第二行有n個整數(shù)，其中第i個數(shù)表示a[j]。
【輸出描述】
一個整數(shù)，表示W(wǎng)YF最多能得到的分?jǐn)?shù)。
【樣例輸入】
3
1 1 50
【樣例輸出】
150
【數(shù)據(jù)范圍】
對于60%的數(shù)據(jù)，n<=1000；
對于100%的數(shù)據(jù)，n<=100000,0<=a[j]<=50

solution

本場最簡單的題沒有之一——因為我A了

法一：我的做法——貪心
在$[1,n]$間，最大值的地方假設(shè)為$i$，我肯定直接從$0$飛到$i$上面，中間不會有中轉(zhuǎn)點
然后就從$i$再繼續(xù)飛到$[i+1,n]$ 中最大值的地方，以此類推，實現(xiàn)方法很多，不贅述

法二：斜率優(yōu)化
考場上我也推出來了，因為這個樣子長得就在暗示我用斜率優(yōu)化搞他
但是我發(fā)現(xiàn)貪心不更簡單嗎，所以我就沒敲

$f[i]=max(f[i],f[j]+a[i]?(i?j))$
假設(shè)$j<k<i$且選擇$j$優(yōu)于選擇$k$，翻譯成C++👇
$f[j]+a[i]?(i?j)>f[k]+a[i]?(i?k)$
$f[j]?f[k]>a[i]?(j?k)$ 注意符號變化哦~
$(f[j]?f[k])/(j?k)<a[i]$

法三：我覺得特別巧妙——香香mm的做法
她的心路歷程：看這個$a$范圍這么小，在暗示她時間復(fù)雜度跟$a$掛鉤，那肯定是$O(n?a)$了

考慮從式子本身進行變形
$f[i]=f[j]+a[i]?(i?j)=f[j]?j?a[i]+a[i]?i$
發(fā)現(xiàn)$a[i]?i$與$j$無關(guān)，所以就考慮求$f[j]?j?a[i]$的最大值
但是因為$j<i$，所以在$j$的時候是無法知道$a[i]$的值的
那么就直接硬剛
是男人就硬剛

暴力枚舉$a[i]$的大小
去求出當(dāng)$a[i]=x$的時候，$f[j]?j?a[i]$的最大值究竟是多少
存下來就可以了，我們不想知道是誰轉(zhuǎn)移的，我們只想要轉(zhuǎn)移后的最大值

for( int i = 1;i <= n;i ++ ) {scanf( "%d", &a );ans = max( ans, pre[a] + a * i );for( int j = 1;j <= 50;j ++ )pre[a] = max( pre[a], ans - i * j ); } printf( "%d", ans );

code

#include <cstdio> #include <iostream> #include <algorithm> using namespace std; #define maxn 100005 struct node {int v, id;node() {}node( int V, int Id ) {v = V, id = Id;} }b[maxn]; int n; int a[maxn];bool cmp( node x, node y ) {return x.v > y.v; } int main() {scanf( "%d", &n );for( int i = 1;i <= n;i ++ )scanf( "%d", &a[i] );for( int i = 1;i <= n;i ++ )b[i] = node( a[i], i );sort( b + 1, b + n + 1, cmp );int p = 0, ans = 0;for( int i = 1;i <= n;i ++ ) {int val = b[i].v, ip = b[i].id;if( ip < p ) continue;else ans += val * ( ip - p ), p = ip;}printf( "%d\n", ans );return 0; }

總結(jié)

以上是生活随笔為你收集整理的[2020-11-23 contest]图（dfs剪枝），劫富济贫（字典树），小A的树（树形DP），游戏（贪心/斜率优化）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。