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]=minw=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=kmdp[i−1][j−k][w]+∣j−S[i]∣
但这样做的复杂度会超时，因为需要枚举i,j,k,w,复杂度为O(nm3)O(nm^{3})O(nm3)
我们发现因为只会在i和i-1层之间转移，那么我们可以用滚动数组滚掉第一维i,那么我们仅仅需要维护minw=kmdp[j−k][w]\min_{w=k}^{m} dp[j-k][w]minw=kmdp[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;
}
的巧妙运用)
