Educational Codeforces Round 103 (Div. 2)

A K-divisible Sum

思路

n个数相加能够整除k，求n个数中最大的数最小时的值，其实就是求一下n个数相加能整除k时的和，然后平均给n个数，求出每个数的值，如果还有余数就+1。

Code

#include <iostream>
#include<vector>
using namespace std;
#define ll long long
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n,x,y,i;
    cin>>n;
    while(n--){
    cin>>x>>y;
    if(x%y==0){
    cout<<1<<endl;
    continue;    
    }
    if(x<y)
    {
      /* for(i=2;;++i)    //会超时 
      {
          if(x*i>=y){
          cout<<i<<endl;
          break;    
          }
      } */
      cout<<y/x+(y%x>0)<<endl;
    }
    if(x>y)
        cout<<2<<endl;        
}
    return 0;    
}

B. Inflation

思路

就是要保证数组每一个除以其前面所有的元素的和小于等于阈值，如果大于阈值就调整（增加前面的和）到符合阈值，求增加数目的最小值即可。

Code

#include <iostream>
#include<vector>
using namespace std;
#define ll long long
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n,t,k,flag=0,sum;
    cin>>n;
    while(n--){
        cin>>t>>k;
        vector<ll> p(t);
        p.clear();
        for(int i=0;i<t;++i)
        cin>>p[i];

        sum=p[0];
        ll ans=0;
        for(int i=1;i<t;++i)
        {
            //如果超过阀值，计算出超过多少，并与之前的比较，若大于之前的，则更新数据
             if (p[i] * 100 > k * sum && ans < (p[i] * 100 % k == 0 ? p[i] * 100 / k : p[i] * 100 / k + 1) - sum)
                ans = (p[i] * 100 % k == 0 ? p[i] * 100 / k : p[i] * 100 / k + 1) - sum;

        sum+=p[i]; 
        }
        cout<<ans<<endl;        
    }
    return 0;
}

C. Longest Simple Cycle

没看

D. Journey

题意

就是给长度为n的字符串，L表示向左走，R表示向右走，问0到n每个点最多可以走几个点。每走一次，字符串各个点方向变一次。

思路

可以考虑前缀和，分为两部分，分别维护两个数组，一直向左，和一直向右的最远到达数目，结果相加就行了。向左时，如果为L , 则左一那个点的左边为R的话，加上左二那个点的结果，因为题目说取反，取两次不变，所以不影响左二左边的结果。右边同样如此。

Code

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int maxn = 3e5 + 10 ;
int t , n ;
string s ;
int a[maxn] = {0} ;
int b[maxn] = {0} ;
int c[maxn] = {0} ;

int main(){
    cin >> t ;
    while(t--){
        cin >> n ;
        cin >> s ;
        memset(a , 0 , sizeof(a)) ;
        memset(b , 0 , sizeof(b)) ;             
        memset(c , 0 , sizeof(c)) ;
        for(int i = 0 ; i < n ; i++){
            if(s[i] == 'L')    a[i] = 1 ;        //1代表向左 
            else    a[i] = 2 ;                //2代表向右 
        }
        for(int i = 0 ; i <= n ; i++){        //向左 
            b[i] = 1 ;                        //它本身 
            if(i == 0)    continue ;
            else if(i == 1){
                if(a[i-1] == 1)    b[i]++ ;
            }
            else{
                if(a[i-1] == 1){
                    b[i]++ ;
                    if(a[i-2] == 2)    b[i] += b[i-2] ;
                }
            }
        }
        for(int i = n ; i >= 0 ; i--){        //向右  
            c[i] = 1 ;
            if(i == n)    continue ;
            else if(i == n - 1){
                if(a[i] == 2)    c[i]++ ;
            }
            else{
                if(a[i] == 2){
                    c[i]++ ;
                    if(a[i+1] == 1)    c[i] += c[i+2] ;
                }
            }
        }
        for(int i = 0 ; i <= n ; i++){
        //    cout << "c" << c[i] << " b " << b[i] << endl ; 
            b[i] = b[i] + c[i] - 1 ;        //因为加了两次它本身 ，所以减一次 
            cout << b[i] << " " ;
        }
        cout << endl ;
    }
    return 0 ;
}