前言：
F,G 后续补充。
A
题意
判断一个字符串，是否满足只有第一位为大写字母，其余为小写字母。
Sol
字面意思模拟即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define N 200005
#define endl "\n"
#define fi first
#define se second
using namespace std;
const ll mod=1e9+7;
const ll inf=1e18;
const double eps=1e-6;
ll n,a[N];
string s;
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>s;
ll fl=0;
if((s[0]>='A'&&s[0]<='Z'))fl=1;
if(!fl){
cout<<"No\n";
return 0;
}
for(int i=1;i<s.size();i++){
if(s[i]<='z'&&s[i]>='a')continue;
cout<<"No\n";
return 0;
}
cout<<"Yes\n";
return 0;
}
B
题意
一个只含有小写字母的字符串吗，找到出现次数最多的字母。如果有出现次数相同的，输出字典序较小的。
Sol
字面意思模拟即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define N 200005
#define endl "\n"
#define fi first
#define se second
using namespace std;
const ll mod=1e9+7;
const ll inf=1e18;
const double eps=1e-6;
ll n,a[N];
string s;
map<char,ll>mp;
char ans;
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>s;
n=s.size();
s=" "+s;
ans='X';
for(int i=1;i<=n;i++){
mp[s[i]]++;
if(mp[s[i]]==mp[ans]&&ans>s[i])ans=s[i];
if(mp[s[i]]>mp[ans]){
ans=s[i];
}
}
cout<<ans;
return 0;
}
C
题意
你有 \(n\) \((n\le 10)\) 种调料，每种调料 \(q_i\) 个，制作一份 \(A\) 菜品，需要第 \(i\) 个调料 \(a_i\)个，制作一份 \(B\) 菜品，需要第 \(i\) 个调料 \(b_i\)个，求最多制作的菜品个数。
Sol
\(n\) 很小，枚举 \(A\) 做多少份，算出剩下的调料最多可做 \(B\) 多少份，答案取最大即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define N 1000005
#define endl "\n"
#define fi first
#define se second
using namespace std;
const ll mod=1e9+7;
const ll inf=1e18;
const double eps=1e-6;
ll n,a[N],b[N],q[N],cnt;
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
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];
ll ans=0;
for(int i=0;i<=N;i++){
cnt=inf;
for(int j=1;j<=n;j++){
if(q[j]-i*a[j]<0){
cout<<ans<<endl;
return 0;
}
if(b[j])cnt=min(cnt,(q[j]-i*a[j])/b[j]);
}
ans=max(ans,cnt+i);
}
cout<<ans<<endl;
return 0;
}
D
题意
一个有 \(n\) 个点的环，编号从 \(1\) 到 \(n\) 依次相连。同时选中 \(m\) 个点，你需要按顺序依次经过这 \(m\) 个点。求把环上某一条边删去后，走过的最少边数。
Sol
先不考虑删去那条边，直接求最小花费。\(x \rightarrow y\) 的方案有两种，钦定 \(x \le y\)，那么方案为:
\[x \rightarrow x+1 \rightarrow ...\rightarrow y-1\rightarrow y \]或者:
\[y \rightarrow y+1 \rightarrow ... \rightarrow n \rightarrow 1 \rightarrow x-1 \rightarrow x \]统计答案时先取最小值，也就是 \(\min(y-x,n-y+x)\)，得到 \(res=\sum_{i=2}^n \min(\lvert a_i-a_{i-1} \rvert,n-\lvert a_i-a_{i-1} \rvert )\)。然后考虑可以删边的情况，简单分类讨论一下，令第一种为 ①，第二种为 ②。
\(1.\) \(y-x \le n-y+x\)，走 ① 合适。
\((1)\) 删去 \([x,y]\) 之间的边，不能选择 ①，走过的边数会变成 \(n-y+x\)，对答案的影响是增加 \((n-y+x)-(y-x)\)。
\((2)\) 删去 \([y,x]\) 之间的边，可以选择 ①，对答案无影响，答案不变。
\(2.\) \(y-x > n-y+x\)，走 ② 合适。
\((1)\) 删去 \([x,y]\) 之间的边，可以选择 ②，对答案无影响，答案不变。
\((2)\) 删去 \([y,x]\) 之间的边，不能选择 ②，走过的边数会变成 \(y-x\)，对答案的影响是增加 \((y-x)-(n-y+x)\)。
注意到选择代价较小的一方，如果途径的路不走能，答案会增加两方案代价差，不妨给代价较小的方案的途径路径增加上这个差值，表示删去这条边，会导致答案增加。
任意方式维护区间加，单点查询即可，这里用了差分。
复杂度 \(O(m+n)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define N 300005
#define endl "\n"
#define fi first
#define se second
using namespace std;
const ll mod=1e9+7;
const ll inf=1e18;
const double eps=1e-6;
ll n,a[N],m;
ll c[N];
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>n>>m;
for(int i=1;i<=m;i++)cin>>a[i];
ll res=0,ans=inf;
for(int i=2;i<=m;i++){
ll t1=a[i],t2=a[i-1];
if(t1<t2)swap(t1,t2);
if(t1-t2>=n-t1+t2){
ll t=t1-t2-(n-t1+t2);
c[1]+=t;
c[t2]-=t;
c[t1]+=t;
res+=n-t1+t2;
}else{
ll t=(n-t1+t2)-(t1-t2);
c[t2]+=t,c[t1]-=t;
res+=t1-t2;;
}
}
ll now=0;
for(int i=1;i<=n;i++){
now+=c[i];
ans=min(ans,now);
}
cout<<res+ans<<endl;
return 0;
}
E
题意
一个圆，上面有 \(2n\) 个点均匀分布，给定 \(n\) 条弦，判断有无交点。
Sol
经典套路。
注意到实际上就是判断区间是否相交，保证区间 \([l,r]\)，\(l<r\)，左端点升序排序，依次增加右端点，每次判断区间内是否包含其他区间的右端点。
Code
#include<bits/stdc++.h>
#define ll long long
#define N 1200005
#define endl "\n"
#define x first
#define y second
using namespace std;
const ll mod=1e9+7;
const ll inf=1e18;
const double eps=1e-6;
ll n;
pair<ll,ll>p[N];
namespace tr{
#define mid ((l+r)>>1)
#define ls (p<<1)
#define rs (p<<1|1)
ll mx[N],lzy[N];
void lt(ll p,ll x){
mx[p]+=x;
lzy[p]+=x;
}
void build(ll p,ll l,ll r){
mx[p]=lzy[p]=0;
if(l==r){
mx[p]=0;
return ;
}
build(ls,l,mid);
build(rs,mid+1,r);
mx[p]=max(mx[ls],mx[rs]);
}
void pushdown(ll p){
lt(ls,lzy[p]);
lt(rs,lzy[p]);
lzy[p]=0;
}
void upd(ll p,ll l,ll r,ll le,ll ri,ll t){
if(le<=l&&ri>=r){
lt(p,t);
return ;
}
pushdown(p);
if(le<=mid)upd(ls,l,mid,le,ri,t);
if(ri>mid)upd(rs,mid+1,r,le,ri,t);
mx[p]=max(mx[ls],mx[rs]);
}
ll qr(ll p,ll l,ll r,ll le,ll ri){
if(le<=l&&ri>=r)return mx[p];
pushdown(p);
ll ans=-inf;
if(le<=mid)ans=max(ans,qr(ls,l,mid,le,ri));
if(ri>mid)ans=max(ans,qr(rs,mid+1,r,le,ri));
return ans;
}
}using namespace tr;
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++){
cin>>p[i].x>>p[i].y;
if(p[i].x>p[i].y)swap(p[i].x,p[i].y);
}
sort(p+1,p+n+1);
build(1,1,n);
for(int i=1;i<=n;i++){
if(qr(1,1,n+n,p[i].x,p[i].y)>0){
cout<<"Yes\n";
return 0;
}
upd(1,1,n+n,p[i].y,p[i].y,1);
}
cout<<"No\n";
return 0;
return 0;
}
F
题意
Sol
Code
G
题意
Sol
Code