题解
A
x+y=n，共可以构造n-1对(x,y)，题目询问是否能构造k对，比较大小即可
B
摘一定数量的宝石，使手环破裂，贪心最近的相同宝石，暴力的思路，先选取一个宝石，找下一个相同的宝石，记录相邻的最小值，时间复杂度
\(O(n^2)\)
优化：我们将相同的宝石放在一起，记录他们在手环中的位置，这样每次遍历，每个宝石只会被枚举一次，统计时，每个宝石也只会被统计一次
注意：统计最后一个宝石的时候，由于是环，应该计算与第一个宝石的距离
#include<bits/stdc++.h>
using namespace std;
int n;
const int maxn=2e5+10;
char m[maxn];
vector<int>a[29];
int t;
int main(){
cin>>t;
while(t--){
for(int i=0;i<29;++i)a[i].clear();
cin>>n;
for(int i=1;i<=n;++i){
char c;c=getchar();if(c=='\n') c=getchar();
a[c-'a'].push_back(i);//统计相同宝石的位置
}
int ans=1e9+10;
for(int i=0;i<26;++i){//枚举每个宝石
int len=a[i].size();
if(len<=1) continue;
ans=min(ans,n-a[i][len-1]+a[i][0]-1);
for(int j=1;j<len;++j){
ans=min(ans,a[i][j]-a[i][j-1]-1);//记录最小距离
}
}
if(ans==1e9+10) puts("-1");
else cout<<ans<<endl;
}
return 0;
}
C
一个不难的思维题
\(\\\)
可以任意插入，这里操作空间就很大了
\(\\\)
我们思考一件事，在给定的字符串中插入后，会生成由若干个循环节组成的字符串，这个循环节应该满足什么条件，他应该包含原来字符串所有过的全部字母
否则我们我们循环节如何构造，组成的字符串都无法由原来的字符串插入形成
而对于每一个原来字符串中含有的字符，都可以插入任意字符组成循环节，而刚好包含所有已知字符的循环节最小
例子：
bhdsd
bhds bhds bhds bhds bhds
#include<bits/stdc++.h>
using namespace std;
string s;
map<int,int> mp;
int main(){
cin>>s;
int ans=0;
for(int i=0;i<s.length();++i)
if(mp[s[i]]==0) ++ans,mp[s[i]]=1;
cout<<ans<<endl;
return 0;
}
D
两种做法，前缀和，dp
思考
答案最后组成序列，我们是可以知道一些信息的，
- 最后一定是三段，
- 三段一定是\(0,1,2\)的某种排列
前缀和
前缀和的这个做法比较典型，而且优化也是典型，可以重点记忆学习
很自然的我们想到，枚举三个区间的中间的两个分割点，统计每一段染色的时间，求最小值即可
暴力是O(n3),用前缀和是O(n2)
着重讲最后这个优化
前缀和时会有两个指针,j,i(j<i),同时枚举两个指针，会是复杂度增加，这里就有典型的优化方式
枚举i的时候j已经被枚举过了，我们只需要记录下来使值最小的j就行
设\(a_0,a_1,a_2\)是0，1，2的某种排列,分别代表三段的颜色
sumt[i][j]表示前j个所有气球变为i所需时间
\(ans=min(ans,sum[a_0][i]+sum[a_1][j]-sum[a_1][i]+sum[a_2][n]-sum[a_2][j]\)
这时我们发现这个表达式中sum[a_0][i]和sum[a_1][i]都是以i下标为结尾，可以用pre[i]先统计一遍，再枚举一遍j时间复杂度就降到了O(n)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e5+10;
ll sumt[5][maxn];
ll pre[maxn];
int t[maxn];
int n;
int a[3]={0,1,2};
void solve(){
string s;cin>>s;
for(int i=1;i<=n;++i) cin>>t[i];
for(int i=1;i<=n;++i){
sumt[0][i]=sumt[0][i-1];
sumt[1][i]=sumt[1][i-1];
sumt[2][i]=sumt[2][i-1];
if(s[i-1]=='0') sumt[1][i]+=t[i],sumt[2][i]+=t[i];
else if(s[i-1]=='1') sumt[0][i]+=t[i],sumt[2][i]+=t[i];
else if(s[i-1]=='2') sumt[0][i]+=t[i],sumt[1][i]+=t[i];
}
ll ans=1e15;
do{
pre[1]=sumt[a[0]][1]-sumt[a[1]][1];
for(int i=2;i<=n;++i)
pre[i]=min(pre[i-1],sumt[a[0]][i]-sumt[a[1]][i]);
for(int i=n+1;i>=1;--i)
ans=min(ans,sumt[a[2]][n]-sumt[a[2]][i-1]+sumt[a[1]][i-1]+pre[i-1]);
}while(next_permutation(a,a+3));
cout<<ans<<endl;
}
int main(){
cin>>n;
solve();
return 0;
}
DP
这里dp的思路类似于逆向的dfs
dfs搜索
我们考虑当前 2，那前面可以是0，1，2
是1的话，前面可以是0，1
\(dfs(i)=dfs(i-1)+t[i] 如果颜色不同\)
\(dfs(i)=dfs(i-1)\)
但是直接的dfs会超时
此时用dp，状态转移一遍就可以了
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
const int maxn=2e5+10;
int a[8]={0,1,2};
string s;
ll t[maxn];
ll ans=1e18;ll dp[4][maxn];
void solve(){
do{
memset(dp,0x3f3f3f3f3f3f3f,sizeof(dp));
dp[0][0]=dp[1][0]=dp[2][0]=0;
for(int i=1;i<=n;++i){
for(int j=0;j<3;++j)
for(int k=0;k<=j;++k)
dp[a[j]][i]=min(dp[a[j]][i],dp[a[k]][i-1]+(a[j]!=s[i-1]-'0')*t[i-1]);
}
for(int i=0;i<3;++i) ans=min(ans,dp[i][n]);
}while(next_permutation(a,a+3));
}
int main(){
cin>>n;
cin>>s;for(int i=0;i<n;++i) cin>>t[i];
solve();
cout<<ans<<endl;
return 0;
}
E
纯模拟了，暴力不超时
貌似数据不够好，只用最长有两个等边就可以
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
const int maxn=1e6+10;
int t;
map<int,int>mp;
signed main(){
scanf("%lld",&t);
while(t--){
scanf("%lld",&n);double ans=0;
int l=0;mp.clear();
for(int i=1;i<=n;++i){
int x,y;
scanf("%lld %lld",&x,&y);
mp[x]+=y;
if(mp[x]>=2 && x>l) l=x;//记录最大的等腰边
}
for(auto [x,y]:mp){
if(x==l && y<=2) continue;
if(x>=2*l) continue;
double p=(x+l*2)*1.0/2;//海伦公式计算
ans=max(ans,(double)sqrt(p*(p-l)*(p-l)*(p-x)));
}
if(ans==0) puts("-1");
else printf("%.10lf\n",ans);
}
}