又是一篇姗姗来迟的atcoder题解。

Link:ABC338

Problem A:

妥妥的签到题。

#include <bits/stdc++.h>
using namespace std;
int main(){string str;cin>>str;if(int(str[0])<65 || int(str[0])>90){cout<<"NO"<<endl;return 0;}for(int i=1;i<str.size();i++){if(int(str[i])<97 || int(str[i])>122){cout<<"NO"<<endl;return 0;}}cout<<"YES"<<endl;return 0;
}

Problem B:

还是签到题。打个擂台就是了。

#include <bits/stdc++.h>
using namespace std;
int cnt[200];
int main(){string str;cin>>str;for(int i=0;i<str.size();i++)cnt[int(str[i])]++;int mx=-1,ans=0;for(int i=0;i<200;i++){if(mx<cnt[i]){mx=cnt[i];ans=i;}}cout<<ans<<endl;return 0;
}

Problem C:

场上以为是爆搜或者dp，最后喜提300pts......

首先，会TLE(我有亲身经历)。所以，考虑贪心。

设我们最后做了x道菜品a，y道菜品b，就可以表示成如下形式:

由于a,b,q都不超过，所以枚举x或y(这里选择y)，得到这个式子:

到这，此题就基本解决了。最后，注意特判为0的情况。

#include <bits/stdc++.h>
using namespace std;
long long q[15],a[15],b[15];
int main(){int n;cin>>n;for(int i=1;i<=n;i++)	cin>>q[i];for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)	cin>>b[i];long long ans=0;for(int y=0;y<=1e6;y++){bool flag=true;for(int i=1;i<=n;i++){if(y*b[i]>q[i]){flag=false;break;}}if(!flag)break;long long x=LONG_LONG_MAX;for(int i=1;i<=n;i++){if(a[i]>0)x=min(x,floor(q[i]-b[i]*y)*1.0/a[i]);//注意要用fmin}if(x>=0)ans=max(ans,x+y);//同理，要用fmax}cout<<ans<<endl;	return 0;
}

Problem D:

本题的思路来自SSRS的代码。思路大概就是用dis数组记录长度，枚举删除一条边的影响，最后求一遍前缀和，再打个擂台就OK了。可能不太详细，看代码吧。

#include <bits/stdc++.h>
using namespace std;
int x[200005];
int main(){int n,m;cin>>n>>m;for(int i=0;i<m;i++){cin>>x[i];x[i]--;}vector<long long> dis(n+1,0);for(int i=0;i<m-1;i++){//枚举删除边的影响int a=x[i];int b=x[i+1];if(a>b)swap(a,b);dis[a]+=n-(b-a);dis[b]-=n-(b-a);dis[0]+=b-a;dis[a]-=b-a;dis[b]+=b-a;dis[n]-=b-a;}for(int i=0;i<n;i++)//前缀和dis[i+1]+=dis[i];long long ans;//注意设置初始值for(int i=0;i<n;i++)ans=min(ans,dis[i]);cout<<ans<<endl;return 0;
}

完结撒花~

温馨提示:本期的全部代码直接提交均无法AC，请不要无脑Ctrl C+Ctrl V