Codeforces Round 787 (Div. 3) - Codeforces
A. Food for Animals
題意
有a袋狗糧,b袋貓糧,c袋通用糧食，問現在有x只狗y只貓,每一個動物都要吃一袋糧食,問糧食夠不夠吃
思路
首先肯定考慮貓吃貓糧，狗吃狗糧。然后再考慮如果不夠吃的話才會去吃通用糧食
代碼
#include<bits/stdc++.h>
using namespace std;
void solve(){int a,b,c,x,y;cin>>a>>b>>c>>x>>y;x-=a;y-=b;if(x>0)c-=x;if(y>0)c-=y;if(c>=0){cout<<"YES\n";return;}cout<<"NO\n";
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T__=1;cin>>T__;while(T__--)solve();return 0;
}
B. Make It Increasing
題意
給定一個序列,問需要多少次操作才能使得整個序列嚴格單調遞增
每次操作可以將a[i]變成a[i]/2(下取整）
思路
貪心,因為元素不能變大,所以我們肯定對最后一個元素不進行操作最優，對倒數第二個元素必須操作成比最后一個元素小,倒數第三個元素必須操作成比倒數二個元素小…依次類推就可以求解出最后的操作次數,注意,如果后一個數字已經是0,則說明無論當前數怎么操作都不能變小,所以輸出-1
代碼
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve(){int n;cin>>n;vector<int>a(n+1,0);for(int i=1;i<=n;i++)cin>>a[i];int res=0;for(int i=n-1;i>=1;i--){if(a[i+1]==0){cout<<-1<<"\n";return;}while(a[i]>=a[i+1])a[i]/=2,res++;}cout<<res<<"\n";
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T__=1;cin>>T__;while(T__--)solve();return 0;
}
C. Detective Task
題意
有n個人先后進入房間,等第n個人結束以后發現原本在墻上的畫不見了，現在詢問n個人進門是否看到了畫,每個人的答案在yes，no，不記得三種情況之一（保證沒有偷畫的人一定說的是真話，偷畫的人答案可以任意）,問有多少人有可能偷畫
思路
思考一下我們發現,實際上不記得這種情況的線索對于我們來說是不能直接確定答案的,如果對于一個人來說在他前面的人說yes或者?并且在他后面的人說no或者?則說明這個人有可能偷畫,我們只需要從前往后標記前綴yes直到出現no停止標記,從后往前標記no直到出現yes停止標記即可
代碼
/*
是否為小偷?
假設當前這個人是小偷,那么在他之前/之后的所有操作都是合法的,即在之前只能是1或者?,在其之后只能是0或者?
從前往后標記是否出現0,從后往前標記是否出現1
*/
#include<bits/stdc++.h>
using namespace std;
void solve(){string s;cin>>s;int n=s.size();s=" "+s;vector<int>vis1(n+2,0),vis2(n+2,0);int fla1=0,fla2=0;for(int i=1;i<=n;i++){if(s[i]=='0')fla1=1;vis1[i]=fla1;}for(int i=n;i>=1;i--){if(s[i]=='1')fla2=1;vis2[i]=fla2;}int cnt=0;for(int i=1;i<=n;i++){if(vis1[i-1]+vis2[i+1]==0)cnt++;}cout<<cnt<<'\n';
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T__=1;cin>>T__;while(T__--)solve();return 0;
}
D. Vertical Paths
題意
給定一棵樹問至少能分成幾條不重復的鏈（鏈中相鄰兩個元素滿足是父子關系）
思路
我們發現無論如何對于葉子節點來說,是一定要產生一條新的鏈的,所以鏈的最小條數就是葉子節點的個數。至于如何輸出,我們只需要找到葉子節點后從葉子節點往上一直走直到走到被標記過的點（說明這個點已經被其他鏈占有）停止。簡單模擬一下即可
代碼
/*
葉子節點有幾個就說明要拆為幾條路徑
我們考慮從葉子節點往上摘鏈*/
#include<bits/stdc++.h>
using namespace std;
// #define int long long
const int mxn=1e6+5;
vector<vector<int>>res;
vector<int>edge[mxn];
int rt;
int vis[mxn];
vector<int>leaf;
void dfs(int u,int fa){int fla=0;for(auto v:edge[u]){if(v==fa)continue;dfs(v,u);fla=1;}if(!fla)leaf.push_back(u);
}
void solve(){int n;cin>>n;res.clear(),leaf.clear();for(int i=1;i<=n;i++)edge[i].clear(),vis[i]=0;vector<int>fa(n+1,0);for(int i=1;i<=n;i++){cin>>fa[i];if(i==fa[i]){rt=fa[i];fa[i]=-1;continue;}else{edge[fa[i]].push_back(i);edge[i].push_back(fa[i]);}}dfs(rt,0);for(auto lef:leaf){int now=lef;vector<int>kk;while(now!=-1&&vis[now]==0){vis[now]=1;kk.push_back(now);now=fa[now];}if(kk.size()){reverse(kk.begin(),kk.end());res.push_back(kk);}}cout<<res.size()<<"\n";for(auto v:res){cout<<v.size()<<"\n";for(auto x:v){cout<<x<<" ";}cout<<"\n";}cout<<"\n";}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T__=1;cin>>T__;while(T__--)solve();return 0;
}
E. Replace With the Previous, Minimize
題意
給定一個字符串,每次操作可以操作一種字母x使得字符串中所有的x都變成x-1(b變成a，c變成b，d變成c…)，最多能進行k次操作,問怎么樣才能使得最后得到的字符串字典序最小
思路
首先我們考慮k很大的時候,如果k>=25，說明一定可以從z變成y，y變成x…c變成b，b變成a的操作使得所有字符都變成a，那么這一定是字典序最小的時候
再考慮k小的時候我們怎么處理。首先肯定考慮優先把第一個字符變成a，然后再考慮第二個字符能不能變成a…直到最后操作次數用完,那么我們會發現一個問題,我們要保證在第一個字母能變成a的基礎上還要保持有盡可能多的前面的數字變小,我們實際上可以先把大于s[1]的字母Px（Px是我們假定的一個字母）盡可能變成s[1]然后再一起從s[1]變成a,那么我們只需要讓Px盡可能大即可,找到Px值以后我們就可以直接模擬從Px到a的過程即可。因為有可能會出現k能滿足從前i個字母變成a但不滿足從s[i+1]到a，且k在操作完以后還有剩余,所有我們優先把s[i+1]盡可能往小的方向調整即可。
代碼
/*
如果K(K>=25)很大,則一定可以變成aaaaa
*/
#include<bits/stdc++.h>
using namespace std;
// #define int long long
void solve(){int n,k;cin>>n>>k;string s;cin>>s;s=" "+s;if(k>=25){for(int i=1;i<=n;i++){cout<<"a";}cout<<'\n';return;}//否則的話K很小,那么就可以直接模擬了//先考慮第一位變到a需要多少步,再考慮第二位變成第一位需要多少步,再考慮第三位變成第二位需要多少步....//直到這個數值>kint r=0;int ma=0;for(int i=1;i<=n;i++){if(s[i]-'a'<=k)r=i,ma=max(ma,s[i]-'a');else break;}k-=ma;for(int i=1;i<=n;i++){if(s[i]<=char('a'+ma))s[i]='a';}if(r+1<=n){for(int tt=1;tt<=k;tt++){char tmp=s[r+1];for(int i=1;i<=n;i++){if(s[i]==tmp)s[i]=char(s[i]-1);}//cout<<s<<"\n";}}for(int i=1;i<=n;i++)cout<<s[i];cout<<"\n";
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T__=1;cin>>T__;while(T__--)solve();return 0;
}
F. Vlad and Unfinished Business
題意
給定起點和終點,問從起點到終點必須經過點a[1]…a[k]的最短路
思路
一開始以為這道題是無向圖，但又看了一眼數據范圍2e5覺得完全無從下手,然后再看了一眼題目發現給定的是一棵樹，那么這道題就變得有說法了
首先因為沒有對根節點的要求，我們為了方便可以將起點作為根節點,那么我們實際上就是要從起點經過若干個特定點最后再到終點,然后我們發現一個很有意思的現象,我們把從起點到終點的簡單路徑稱為主干,那么只要這個目標節點不在主干上，我們就需要從主干上的某個節點x出發去訪問這個節點的子樹然后再走回x，相當于在非主干的路上我們必須每條路徑都走兩次,結合樹形DP的一些思路,尋思著要維護一些什么方便我們求最后的答案。我們發現最后要求的答案實際上就是從起點走到若干個目標點（包括終點）再回到起點的路程-從起點走到終點的路程。那么問題就容易解決了,我們維護每顆子樹下是否存在目標節點,如果存在目標節點,就說明從當前節點到其兒子節點的這條路徑是必須要走的并且是要走兩次的（來回）并且還需要加上從子樹內部到這個目標點所需要走的距離（即這棵子樹中往下要走至少多少路程到達目標節點后再回到這個子樹的根節點）至于如何求解這些信息，我們只需要從葉子節點往上更新信息直到最后在根節點處停止。最后只需要在根節點（起點）統計我們需要的這個值然后再減去終點的深度（即起點到終點的最短路徑）即為答案
代碼
/*
給定起點和終點,問從起點到終點必須經過a[1]....a[k]的最短路
經過從起點走到目標點再回到起點的最短路
把中點也算作一個目標頂點,
那么最好的答案就是從起點走到目標點再回到起點的最短路-從起點到終點的最短路
*/
#include<bits/stdc++.h>
using namespace std;
const int mxn=1e6+5;
vector<int>edge[mxn];
int vis[mxn];
int ans[mxn];
int dep[mxn];
void dfs(int u,int fa){for(auto v:edge[u]){if(v==fa)continue;dep[v]=dep[u]+1;dfs(v,u);vis[u]=max(vis[v],vis[u]);if(vis[v])ans[u]+=2+ans[v];}
}
void solve(){int n,k;cin>>n>>k;int st,ed;cin>>st>>ed;for(int i=1;i<=n;i++)edge[i].clear(),vis[i]=0,dep[i]=0,ans[i]=0;for(int i=1;i<=k;i++){int x;cin>>x;vis[x]=1;}vis[ed]=1;for(int i=1;i<n;i++){int u,v;cin>>u>>v;edge[u].push_back(v);edge[v].push_back(u);}dfs(st,0);cout<<ans[st]-dep[ed]<<"\n";
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T__=1;cin>>T__;while(T__--)solve();return 0;
}
G. Sorting Pancakes
題意
給定一個長度為n的序列,每個位置上都有a[i]個餡餅，每次可以選擇相鄰兩個元素一個減1一個加1，問經過至少多少次操作能使得序列非遞增
思路
我們可以考慮統一方向，只考慮位置i和i+1兩個元素,每次操作實際上就是從i盤中取（正數）個餡餅放入i+1盤，或者從i盤取（負數）個餡餅放入i+1盤（等價于從右邊往左放整數個餡餅）
考慮到沒有貪心策略，而且n的范圍很小，故我們想到可以采用DP,我們需要維護的狀態有：已經考慮了多少個盤子,在這之前的盤子總共裝了多少個，當前盤子裝了多少個，故我們需要用三維DP
定義dp[i][j][k]dp[i][j][k]dp[i][j][k]:表示前i個盤子中，總共放了j個餡餅，且當前第i個盤子放了k個餡餅（并且保證前i個盤子已經構成了非遞增的序列）
那么我們如何考慮相鄰兩個盤子的交換操作過程呢？
前i盤子中只有盤i是靈活的，因為只要前i-1個盤子總數固定，第i-1個盤子數量固定,那么前i-1個盤子就是不可再動的了。唯一可以調節的就是第i個盤子里面的個數,調節盤子之間餡餅的個數是有代價的，且必須經過 i+1(因為前i-1個盤子已經固定，i只能和i+1交換)
假設前i個盤子有j個餡餅且當前第i個盤子有k個餡餅，那么他可以從前i-1個盤子有j-k個餡餅且當前第i-1個盤子有w個餡餅轉移得到（k<=w<=j-k）,但因為原來的前i個盤子中有S[i]個餡餅,但當前總共只有j個餡餅，所以還要從i+1交換∣s[i]?j∣|s[i]-j|∣s[i]?j∣次操作使得當前前i個盤子總共只有j個餡餅(實際上在轉移過程中只會因為調節總數j和實際S[i]不一致而產生代價)
即轉移方程為dp[i][j][k]=min?w=kmdp[i?1][j?k][w]+∣j?S[i]∣dp[i][j][k] = \min_{w=k}^{m} dp[i-1][j-k][w] + |j - S[i]|dp[i][j][k]=minw=km?dp[i?1][j?k][w]+∣j?S[i]∣
但這樣做的復雜度會超時，因為需要枚舉i,j,k,w,復雜度為O(nm3)O(nm^{3})O(nm3)
我們發現因為只會在i和i-1層之間轉移，那么我們可以用滾動數組滾掉第一維i,那么我們僅僅需要維護min?w=kmdp[j?k][w]\min_{w=k}^{m} dp[j-k][w]minw=km?dp[j?k][w]即可,所以我們只需要單獨開一個數組維護后綴最小值即可
代碼
#include<bits/stdc++.h>
using namespace std;
#define int long long
int mi[405][405];
int dp[405][405];
int s[405];//前綴和
void solve(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++)cin>>s[i],s[i]+=s[i-1];for(int i=0;i<=m;i++)dp[0][i]=1;for(int i=1;i<=n;i++){//當前在處理第i層,那么mi維護的就是第i-1層的信息//具體的,mi[j-k][k]表示w=k~m的最小dp[i-1][j-k][w]for(int j=0;j<=m;j++){//前i個盤子總共餡餅數量for(int k=0;k<=j;k++){//第i個盤子的餡餅數量//dp[i][j][k]=min(dp[i-1][j-k][w])+|j-s[i]| (k<=w<=m)dp[j][k]=mi[j-k][k]+abs(s[i]-j);}}memset(mi,0x3f,sizeof mi);//清空第i-1層的信息,準備維護第i層的信息for(int j=0;j<=m;j++){for(int k=j;k>=0;k--)mi[j][k]=min(mi[j][k+1],dp[j][k]);//維護后綴最小值}}int ans=0x3f3f3f3f3f3f3f3f;for(int i=0;i<=m;i++) ans=min(ans,dp[m][i]);//最后一個盤子的數量是不確定的,我們要從中枚舉挑選最小cout<<ans<<"\n";
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T__=1;//cin>>T__;while(T__--)solve();return 0;
}
的巧妙運用)
