A. Problemsolving Log
map枚举字母
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n;
string s;
cin>>n>>s;
int ans=0;
s=" "+s;
map<char,int>mp;
for(int i=1;i<=n;i++){
mp[s[i]]++;
}
for(auto c:mp){
char x=c.first;
int y=c.second;
if(x-'A'+1<=y)ans++;
}
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
for(int i=1;i<=t;i++)solve();
return 0;
}
B. Preparing for the Contest
很简单的构造
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n,k;
cin>>n>>k;
int i;
if(k==0){
for(int i=n;i>=1;i--){
cout<<i<<" ";
}
}else if(k==n-1){
for(int i=1;i<=n;i++){
cout<<i<<" ";
}
}else{
int i;
for(i=1;i<=k;i++){
cout<<i<<" ";
}
i--;
for(int j=n;j>i;j--){
cout<<j<<" ";
}
}
cout<<"\n";
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
for(int i=1;i<=t;i++)solve();
return 0;
}
C. Quests
通过观察提示发现，最优的情况一定是1x的和加上（k-x）*1x这个范围里b[i]的最大值
所以枚举即可
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],b[N],sum[N];
void solve(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
for(int i=1;i<=n;i++){
b[i]=max(b[i],b[i-1]);
}
int ans=0;
for(int i=1;i<=min(n,k);i++){
int cnt=sum[i];
int x=abs(i-k);
cnt+=b[i]*x;
ans=max(ans,cnt);
}
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
for(int i=1;i<=t;i++)solve();
return 0;
}
D. Three Activities
通过观察数据很好知道题目的意思，就是选a，b，c里不在同一下标的值，加起来最大，看一眼数据范围1e5，显然暴力肯定是不行
但是转化一下思路，要求最大，其实只需要把每组最大的几个数暴力一下就行了，因为最优解一定是在这个里面
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
vector<pair<int,int>>a[4];
void solve(){
int n;
cin>>n;
for(int i=1;i<=3;i++){
a[i].clear();
}
for(int i=1;i<=n;i++){
int x;
cin>>x;
a[1].push_back({x,i});
}
for(int i=1;i<=n;i++){
int x;
cin>>x;
a[2].push_back({x,i});
}
for(int i=1;i<=n;i++){
int x;
cin>>x;
a[3].push_back({x,i});
}
for(int i=1;i<=3;i++){
sort(a[i].begin(),a[i].end(),greater<pair<int,int>>());
}
int ans=0;
for(int i=0;i<=2;i++){
for(int j=0;j<=2;j++){
for(int z=0;z<=2;z++){
if(a[1][i].second!=a[2][j].second&&a[1][i].second!=a[3][z].second&&a[2][j].second!=a[3][z]){
int x=a[1][i].first+a[2][j].first+a[3][z].first;
ans=max(ans,x);
}
}
}
}
cout<<ans<<"\n";
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
for(int i=1;i<=t;i++)solve();
return 0;
}