Educational Codeforces Round 50

A. Function Height
题意:x轴正方向上的一条线段一共含有2n个点,长度为n,每次操作定义为将这条线段上任意一个下标为奇数的点向上平移一个单位。经过若干次操作后会形成许多三角形。现给定正整数k,要求通过若干次操作使得三角形的面积之和大于等于k,求其中高最大的三角形其高的最小值是多少

题解:显然当所有三角形的高度一样,且每个三角形的底边有相邻的两个点组成,于是根据三角形面积公式得到ans为K/N,注意向上取整

#include <bits/stdc++.h>

using namespace std;

long long N,K,ans;

int main()
{
    scanf("%I64d %I64d",&N,&K);
    ans = K/N;
    if(K%N) ans++; 
    printf("%I64d\n",ans);
    
    return 0;
}

B. Diagonal Walking v.2

题意:给你一个q代表q次询问,然后给出三个数n,m, k。(n,m)代表终点,k代表最多移动的步数。让你求出到达终点的过程中,走对角线的最大步数。

题解:画图找规律

#include <bits/stdc++.h>

using namespace std;

long long T,N,M,K,MAX,MIN;

inline long long read()
{
    long long x = 0;char ch = getchar();
    while(ch < '0' || '9' < ch){ch = getchar();}
    while('0' <= ch&& ch <='9'){x = x * 10 + ch - '0';ch = getchar();}
    return x;
}

int main()
{
    T = read();
    while(T--)
    {
        N = read();M = read();K = read();
        if(N < M) swap(N,M); 
        if(K < N) {printf("-1\n");continue;}
        
        if((N - M) & 1) K--;
        else if((K - N) & 1) K -= 2;
        printf("%lld\n",K);
        
    }
    return 0;
} 

C. Classy Numbers
题意:问你在L-R中存在多少个Classy Numbers,Classy Numbers的定义是:该数字各位上只存在不超过3个非零数字
题解:数位动规

数组含义解释:
a[i]:第i位的数字是多少,换句话说就是第i最大可以取到的值
dp[pos][cnt]:从最大的一位到pos这一位出现了cnt个非零位的总方案数
dfs参数中的limit则从前面到当前位是否达到了循环的上限
然后就用记忆化搜索就可以了
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

ll T,L,R;
ll a[20],dp[20][20];

inline ll read(){
    ll x = 0;char ch = getchar();
    while(ch < '0' || '9' < ch){ch = getchar();}
    while('0' <= ch&& ch <='9'){x = x * 10 + ch - '0';ch = getchar();}
    return x;
}

ll dfs(ll pos,ll limit,ll cnt){
    if(cnt > 3)return 0;
    if(pos == -1) return 1;
    if(!limit && dp[pos][cnt] != -1) return dp[pos][cnt];
    ll tmp = 0,up = limit ? a[pos] : 9;
    
    for(ll i = 0;i <= up;i++)
        tmp += dfs(pos-1,limit && (i == up),cnt + (i!=0));
        
    dp[pos][cnt] = tmp;
    return tmp;
}

inline ll slove(ll N){
    memset(dp,-1,sizeof(dp));
    ll tot = 0;
    while(N){
        a[tot++] = N % 10;
        N /= 10;
    }
    return dfs(tot-1,1,0);
}

int main()
{
    T = read();
    while(T--)
    {
        L = read();R = read();
        printf("%lld\n",slove(R)-slove(L-1));
    }
    return 0;
} 

D. Vasya and Arrays
题意:在数列A和数列B中选择将一部分数字相加,之后得到的新数列A和B完全相等,问你最终得到的数列的最长长度为多少

题解:对于第一组样例
对于每一个数列将需要合并的用空格隔开
A:11  2 3 5   7
B:11  7 3     7
显然:我们从第一个数字开始求一个区间和,并且上下调整直到两个区间和相等就结束,这就是一次合并。如果最后两个数列刚好完全用完,那么区间和个数就是答案直接输出就好了,否则答案不存在
#include <bits/stdc++.h>
#define pb push_back

const int MAXN = 300005;

using namespace std;

typedef long long ll;

ll n,m,suma,sumb,l,r,va,vb;
ll a[MAXN],b[MAXN];

inline ll read(){
    ll x = 0;char ch = getchar();
    while(ch < '0' || '9' < ch){ch = getchar();}
    while('0' <= ch&& ch <='9'){x = x * 10 + ch - '0';ch = getchar();}
    return x;
}

inline void init(){
    n = read();
    for(int i = 1;i <= n;i++) a[i] = read();
    m = read();
    for(int i = 1;i <= m;i++) b[i] = read();
} 

int main(){
    init();
    l = r = 1;
    while(1)
    {
        suma = a[l];
        sumb = b[r];
        while(suma != sumb && l <= n && r <= m){
            if(suma > sumb){r++;sumb += b[r];continue;}
            if(suma < sumb){l++;suma += a[l];continue;}
        }
        va++;vb++;
        l++;r++;
        if(l > n || r > m)break;
    }
    if(l != n+1 || r != m+1) {printf("-1\n");return 0;}
    printf("%lld\n",va);
    return 0;
} 
Last modification:October 1st, 2018 at 04:51 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment