赞
踩
目录
刷题记录(Codeforces Round 916 (Div. 3)A~D)
2.B. Preparing for the Contest
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;
- }
查找兴奋次数,因为有多种答案,我们可以指定一种模式,当消费次数为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;
- }
题意:题目给出两个数组,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;
- }
需要我们找到三个数组中的都选出来一个数,这三个数之和的最大值,但是这三个数所处的下标都各不相同。
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;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。