6月4号总结

目录

刷题记录(Codeforces Round 916 (Div. 3)A~D)

1.A. Problemsolving Log

2.B. Preparing for the Contest

3.C. Quests

4.D. Three Activities

---

刷题记录(Codeforces Round 916 (Div. 3)A~D)

1.A. Problemsolving Log

Problem - A - Codeforces

A问题要学1分钟，Z问题要学26分钟，按照这个规律，看字符串问题出现的次数，如果出现次数大于要学的时间，那么意味这解决了这个问题。

下面是AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve()
{
	ll ans=0;
	ll n;
	cin>>n;
	string s;
	cin>>s;
	map<char,ll>q;
	for(int i=0;i<s.size();i++){
		if(q[s[i]]!=-1)
		q[s[i]]++;
		if(q[s[i]]>=(s[i]-'A'+1)) ans++,q[s[i]]=-1;
	}
	cout<<ans<<"\n";
}
int main()
{
	
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

2.B. Preparing for the Contest

Problem - B - Codeforces

查找兴奋次数，因为有多种答案，我们可以指定一种模式，当消费次数为0次或者n-1次时，直接逆序或者顺序输出1到n，其他情况按照下面这个方式：

举例：n=5

k=1,2 1 5 4 3

k=2,1 2 5 4 3

k=3,1 2 3 5 4

下面是AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve()
{
	ll n,k;
	cin>>n>>k;
	if(k==n-1)
	{
		for(int i=1;i<=n;i++){
			cout<<i<<" ";
		}
		cout<<"\n";
		return;
	}
	if(k==0)
	{
		for(int i=n;i>=1;i--){
			cout<<i<<" ";
		}
		return;
	}
	if(k==1)
	{
		cout<<2<<" "<<1<<" ";
		for(int i=n;i>=3;i--){
			cout<<i<<" ";
		}
		cout<<"\n";
		return;
	}
	for(int i=1;i<=k;i++){
		cout<<i<<" ";
	}
	for(int i=n;i>=k+1;i--){
		cout<<i<<" ";
	}
	cout<<"\n";
}
int main()
{
	
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

3.C. Quests

Problem - C - Codeforces

题意：题目给出两个数组，a数组为任务第一次完成加的经验，b数组为第2次或者以上完成这个任务所加的经验，并且第i个任务必须i-1个任务完成后才能解锁，一开始时，任务1是可以完成的，k是可以完成的任务次数，求最大经验。

一个公式

就是数学加贪心，每次循环取优的结果，最后答案为最优结果的最大值。

下面是AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[200010],b[200010];
void solve()
{
	ll n,k;
	cin>>n>>k;
	for(ll i=0;i<n;i++) cin>>a[i];
	for(ll i=0;i<n;i++) cin>>b[i];
	ll ans=0,sum=0,cnt=0;
	for(int i=0;i<n;i++){
		
		sum+=a[i];
		cnt=max(cnt,b[i]);
		k--;
		if(k>=0)
		ans=max(ans,k*cnt+sum);
	}
	cout<<ans<<"\n";
}
int main()
{
	
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

4.D. Three Activities

Problem - D - Codeforces

需要我们找到三个数组中的都选出来一个数，这三个数之和的最大值，但是这三个数所处的下标都各不相同。

n的范围是1x10^5，所以不能暴力，但是我们需要找出的是最大值，那么我们只需要找到每个数字最大的三个数字的下标，再进行一个三重for循环即可。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
#define pii pair<int,int>
 
int a[N];
int b[N];
int c[N];
 
void solve(){
    int n;cin >> n;
    for(int i = 1;i <= n;i++)cin >> a[i];
    for(int i = 1;i <= n;i++)cin >> b[i];
    for(int i = 1;i <= n;i++)cin >> c[i];
    int a1 = -1,a2 = -1,a3 = -1;
    for(int i = 1;i <= n;i++){
        if(a1 == -1 || a[i] > a[a1]){
            a3 = a2;
            a2 = a1;
            a1 = i;
        }else if(a2 == -1 || a[i] > a[a2]){
            a3 = a2;
            a2 = i;
        }else if(a3 == -1 || a[i] > a[a3]){
            a3 = i;
        }
    }
 
    int c1 = -1,c2 = -1,c3 = -1;
    for(int i = 1;i <= n;i++){
        if(c1 == -1 || c[i] > c[c1]){
            c3 = c2;
            c2 = c1;
            c1 = i;
        }else if(c2 == -1 || c[i] > c[c2]){
            c3 = c2;
            c2 = i;
        }else if(c3 == -1 || c[i] > c[c3]){
            c3 = i;
        }
    }
 
    int b1 = -1,b2 = -1,b3 = -1;
    for(int i = 1;i <= n;i++){
        if(b1 == -1 || b[i] > b[b1]){
            b3 = b2;
            b2 = b1;
            b1 = i;
        }else if(b2 == -1 || b[i] > b[b2]){
            b3 = b2;
            b2 = i;
        }else if(b3 == -1 || b[i] > b[b3]){
            b3 = i;
        }
    }
 
    vector<int>posA(3);
    posA[0] = a1,posA[1] = a2,posA[2] = a3;
    vector<int>posB(3);
    posB[0] = b1,posB[1] = b2,posB[2] = b3;
    vector<int>posC(3);
    posC[0] = c1,posC[1] = c2,posC[2] = c3;
 
    int res = 0;
    for(int i = 0;i < 3;i++){
        for(int j = 0;j < 3;j++){
            for(int k = 0;k < 3;k++){
                int aa = posA[i],bb = posB[j],cc = posC[k];
                if(aa != bb && aa != cc && bb != cc){
                    res = max(res,a[aa] + b[bb] + c[cc]);
                }
            }
        }
    }
    
    cout << res << endl;
}
 
int main(){
    int T;cin >> T;
    while(T--){
        solve();
    }
    return 0;
}