2022.08.13 提高组模拟赛 题解
前言
被 @Hooch @StayAlone @L_h_ 踩爆了。打得相当失败。本场我总分
T1
拼接
n 个只包含s与h的字符串，使得最终字符串中sh子序列最多。
做法很精妙，很有思维难度。场切
首先显然有一个想法就是把字符串都排序，然后顺着取就行了，怎么排序是重要的问题。
观察到确定两个字符串谁前谁后只需要确定谁的贡献更大即可，所以直接重载小于运算符，比较贡献大小即可。
这题我认为很经典，但是又有思维难度。
参考代码：
int n;
string ans;
int cnt,sum;
struct node{
string s;
int sn,hn;
bool operator<(const node &p) const{
return p.sn*hn<sn*p.hn;
}//重载运算符比较贡献
} s[N];
signed main(){
cin>>n;
fr1(i,1,n){
cin>>s[i].s;
fr1(j,0,s[i].s.length()-1){
s[i].hn+=(s[i].s[j]=='h');
s[i].sn+=(s[i].s[j]=='s');
}
}
sort(s+1,s+n+1);//排序
fr1(i,1,n){
ans+=s[i].s;
}
fr1(i,0,ans.length()-1){
if(ans[i]=='h'){
sum+=cnt;
}
else{
cnt++;
}
}//统计答案
cout<<sum<<endl;
ET;
}T2
给你
n 个名字和权值，输出每次对权值按从大到小选择排序后的整个名字序列。如果出现相同权值，按目前的先后顺序排列。n\leqslant 20
签到题，可是 ZYH 连到都没签。原因是原题没有目前这两个字，导致歧义。场切
选择排序核心思想就是选择最大的那个然后和目前没有排好序的第一个交换即可。
所以参考代码如下，非常简单，瞎搞就可以了：
int n;
struct node{
string name;
int id,val;
} s[30];
int maxn=uinf,id;
int las;
signed main(){
ios::sync_with_stdio(false);
cin>>n;
las=1;
fr1(i,1,n){
cin>>s[i].name>>s[i].val;
s[i].id=i;
}
fr1(i,1,n-1){
maxn=uinf;
// id=inf;
int who;
fr1(j,las,n){
maxn=max(maxn,s[j].val);//找到最大值
}
fr1(j,las,n){
if(maxn==s[j].val){
// id=s[j].id;
who=j;
break;//取目前第一个即可
}
}
swap(s[las],s[who]);//直接交换即可
las++;//排好序的部分增加一
fr1(j,1,n-1){
cout<<s[j].name<<" ";
}
cout<<s[n].name<<endl;//本题卡格式
}
return 0;
}T3
$n\leqslant 10^3$。
拿到之后没有思路，所以不妨打个大暴力，不妨定轮数最大为
然后它……过了……
不光是数据水的原因，本题似乎可以证明轮数不会超过某个值。详见 L_h_ 的本场题解。
最后二十分钟搞出来暴力，倒数四分钟的时候调通了正解然后极限翻盘（
本题场切
首先观察到答案序列
得到单峰性质之后，我们当然需要枚举峰。容易发现枚举峰之后直接贪心地去取答案了，我们以峰右侧的单调不增为例：
- 若
m_i<a_{i-1} ，令las 为m_i ，以后所有的a 都不可能超过las 。 - 若
m_i\geqslant a_{i-1} ，我仍然只能够取las 。
于是我们很容易可以写出暴力代码，时间复杂度
int n;
int a[500010];
int ans;
int maxn=LLONG_MIN;
int las;
signed main(){
ios::sync_with_stdio(false);
cin>>n;
fr1(i,1,n){
cin>>a[i];
}
fr1(i,1,n){
ans=0;
las=a[i];
ans+=a[i];
fr2(j,i-1,1){
if(a[j]>las){
ans+=las;
}
else{
las=a[j];
ans+=las;
}
}
las=a[i];
fr1(j,i+1,n){
if(a[j]>las){
ans+=las;
}
else{
las=a[j];
ans+=las;
}
}
maxn=max(maxn,ans);
}
cout<<maxn<<endl;
return 0;
}接下来考虑优化，不妨考虑 DP。令
单调队列优化 DP 板子题。场切
首先观察到做除法很麻烦，显然很难贪心，所以考虑 DP，而且时间倒流，我们从
不妨考虑线性 DP。令
然后观察到第二个式子最外面那个
参考代码：
int T;
int dp[1000010];
deque <pii> q;
int x,k,t;
void solve(){
cin>>x>>k>>t;
while(!q.empty()){
q.pop_front();
}
memset(dp,0x3f,sizeof dp);
dp[1]=0;
q.push_back(mp(1,0));
fr1(i,2,x){
if(i%k==0){
dp[i]=dp[i/k]+1;
}
while(!q.empty()&&q.front().fi<i-t){
q.pop_front();
}
// cout<<i<<"!"<<q.front().fi<<endl;
dp[i]=min(dp[i],q.front().se+1);
while(!q.empty()&&q.back().se>=dp[i]){
q.pop_back();
}
q.push_back(mp(i,dp[i]));
// cout<<i<<","<<dp[i]<<endl;
}
cout<<dp[x]<<endl;
}
int main(){
cin>>T;
while(T--){
solve();
}
return 0;
}总结
这次的题相比之前难度提高了很多，思维难度有些提升，让我这种思维水平低的无处存储（
恭喜 @L_h_ 五题总用时
ZYH 菜菜/kk