Educational Codeforces Round 122 (Rated for Div. 2)ABCD

59 阅读 0 评论 39 点赞

我是靠谱客的博主无心水杯，最近开发中收集的这篇文章主要介绍Educational Codeforces Round 122 (Rated for Div. 2)ABCD，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

文章目录

A

个位从0到9进行枚举，直到能被7整除

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl 'n'
const int N=100100;
int solve(){
   int n;
   cin>>n;
   if(n%7==0){
      return n;
   }
   else {
      n=n/10*10;
      for( int i=0;i<=9;i++){
         if((n+i)%7==0) return n+i;
      }
   }
}
int main(){
   //  ios_base::sync_with_stdio(0);
   //  cin.tie(0); cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        cout<<solve()<<endl;
    }
    return 0;
}

B

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl 'n'
const int N=100100;
int solve(){
   string s;
   cin>>s;
   int a=0,b=0;
   for( int i=0;i<s.size();i++){
      if(s[i]=='0') a++;
      else b++;
   }
   if(a!=b) return min(a,b);
   else return a-1;
}
int main(){
   //  ios_base::sync_with_stdio(0);
   //  cin.tie(0); cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        cout<<solve()<<endl;
    }
    return 0;
}

C

从0到k进行枚举，将几点技能点分配给攻击力，将几点技能点分配给生命值。计算玩家和怪兽能承受攻击的次数，看玩家和怪兽哪个可以胜利。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl 'n'
const int mod=998244353;
const int N= 200100;

int solve(){
    ll hc,dc,hm,dm;
    ll k,w,a;
    cin>>hc>>dc>>hm>>dm;
    cin>>k>>w>>a;
    for( int i=0;i<=k;i++){
        ll j=k-i;
        ll hc1=hc+a*i;
        ll dc1=dc+w*j;
        ll m=(hm+dc1-1)/dc1;
        ll c=(hc1+dm-1)/dm;
        if(c>=m) return 1;
    }
    return 0;

}
int main(){
    int t;
    cin>>t;
    while(t--){
        if(solve()) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

D

计算出每个点变到b所需要的操作数，然后使用01背包求解。
本题的复杂度不是n*k。
由于所有花费的和远小于k，所以不会超时。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl 'n'
const int mod=998244353;
const int N= 3010;
int b[N],c[N];
int Cost[N];
int cost[N];
int dp[1001000];
int n,k;
void pre_work(){
    memset(Cost,0x3f,sizeof Cost);
    Cost[1]=0;
    for( int i=1;i<=3000;i++){
        for( int j=i;j>=1;j--){
            if(i+i/j>3000) break;
            else Cost[i+i/j]=min(Cost[i+i/j],Cost[i]+1);
        }
    }
}
int solve(){
    
    cin>>n>>k;
    for( int i=0;i<n;i++) cin>>b[i];
    for( int i=0;i<n;i++) cin>>c[i];
    for( int i=0;i<n;i++){
        cost[i]=Cost[b[i]];
    }
    k=min(k,13*n);
    memset(dp,0,sizeof(dp));
    for( int i=0;i<n;i++){
        for( int j=k;j>=cost[i];j--){
            dp[j]=max(dp[j],dp[j-cost[i]]+c[i]);
        }
    }
    return dp[k];
}
int main(){
    pre_work();
    int t;
    cin>>t;
    while(t--){
        cout<<solve()<<endl;
    }
    return 0;
}