Educational Codeforces Round 80 (Rated for Div. 2)部分题解

A. Deadline

题目大意

给你\(n,d\)两个数,问是否存在\(x\)使得\(x+\frac{d}{x+1}\leq n\)，其中\(\frac{d}{x+1}\)向上取整。

解题思路

方案一：利用均值不等式公式推导

\(x+\frac{d}{x+1}=x+1+\frac{d}{x+1}-1\geq2\sqrt{d}-1\)

所以 \(\min(x+\frac{x}{d+1})=2\sqrt{d}-1\)

因此去判断\(2\sqrt{d}-1\leq n\)是否成，即\(4\times n^2\leq (n+1)^2\)是否成立即可。
方案二：暴力判断

很明显的一点就是\(x\)的值不会超过\(\sqrt{d}\)，所以遍历判断一下即可。

AC代码1

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int t;

    cin>>t;

    while(t--){

        long long n,d;

        cin>>n>>d;

        if(4*d<=(n+1)*(n+1)){

            cout<<"YES"<<endl;

        }else{

            cout<<"NO"<<endl;

        }

    }

    return 0;

}

AC代码2

#include<bits/stdc++.h>

const int maxn=1e3+100;

typedef long long ll;

typedef unsigned long long ull;

using namespace std;

int main()

{

    // freopen("data.txt","r",stdin);

    int t;

    cin>>t;

    while(t--){

        int n,d;

        cin>>n>>d;

        bool flag=false;

        for(int i=0;i*i<=d;i++){

            if((i+d/(i+1)+(d%(i+1)==0?0:1))<=n){

                flag=true;

            }

        }

        if(flag)cout<<"YES"<<endl;

        else cout<<"NO"<<endl;

    }

    return 0;

}

总结

最开始拿到这道题的时候居然有点懵，其实应该理所应当的想到\(x\)的值不会超过\(\sqrt{d}\)

B. Yet Another Meme Problem

题目链接

题目大意

给你两个数\(A,B\)，求满足\(1\leq a \leq A\)，\(1\leq b \leq B\)并且 \(a\times b+ a+b = a\times 10^{b的位数}+b\)的个数。

解题思路

在做这道题的时候其实出题人已经给了提示，所以很轻松的想到了结论，即找到满足\(\leq b\)并且每一位都是\(9\)的数字个数\(\times a\)即为答案。

结论推导：

\(a\times b+a+b=a\times 10^{b的位数}+b\)

\(a\times b+a = a\times 10^{b的位数}\)

\(a\times (b+1) = a\times 10^{b的位数}\)

\(b+1 = 10^{b的位数}\)

所以只有所有位都是\(9\)的数字才能满足，即\(9,99,999,\cdots\)

AC代码

#include<bits/stdc++.h>

const int maxn=1e3+100;

typedef long long ll;

typedef unsigned long long ull;

using namespace std;

int main()

{

    // freopen("data.txt","r",stdin);

    int t;

    cin>>t;

    while(t--){

        ll a,b;

        cin>>a>>b;

        string str = to_string(b);

        int len = str.size()-1;

        bool flag = true;

        for(int i=0;i<str.size();i++){

            if(str[i]!='9'){

                flag=false;

                break;

            }

        }

        if(flag)len++;

        cout<<a*len<<endl;

    }

    return 0;

}

总结

这道题自己在求数字个数的时候用的是字符串求法，其实如果不是大数的话，个人认为用整数运算即可，还方便点。丢个代码出来。

int cnt=0;

int number=9;

while(number<=b){

    number = number*10+9;

    cnt++;

}

C. Two Arrays

题目链接

题目大意

给你两个数字\(n,m\)，求用\(1\cdots n\)这\(n\)个数（数字可以重复）构造出两个长度为\(m\)的数组\(a,b\)满足一下要求的数组数量。

对于数组\(a,b\)中所有元素都满足\(a_i\leq b_i\)
数组\(a\)是非递减的
数组\(b\)是非递增的

解题思路

啊啊啊，这道题自己在做的时候没有想到把两个数组给合起来，思维太线性了，没有转过弯。数组\(a\)是非递减的，数组\(b\)是非递增的，如果将数组\(b\)反转连接在数组\(a\)的后面就是一个非递减数组，那么题目要求就转化为求用\(1\cdots n\)这\(n\)个数构造一个长度为\(2\times m\)的非递减数组的个数。

复杂度为\(O(n^2m)\)的转移方程

\(dp[i][j]\)表示第\(i\)个位置放数字\(j\)的方案数，那么\(dp[i][j]=\sum_{k=1} ^j dp[i-1][k]\)
复杂度为\(O(nm)的转移方程\)

\(dp[i][j]\)表示第\(i\)个位置放数字\(j\)的方案数，那么\(dp[i][j]=dp[i-1][j]+dp[i][j-1]\)，这里利用了前缀和的思想。

推导如下：

\(dp[i][j]=\sum_{k=1} ^j dp[i-1][k]=\sum_{k=1}^{j-1}dp[i-1][k]+dp[i-1][j]\)

因为\(dp[i][j-1]=\sum_{k=1} ^{j-1} dp[i-1][k]\)

所以 \(dp[i][j]=dp[i-1][j]+dp[i][j-1]\)

又或者在不知道如何推导的情况下可以从思维上这样想

在第\(i\)个位置上可以放\(j-1\)，那么在第\(i\)个位置上肯定也可以放\(j\)，所以放\(j\)的个数肯定会包含放\(j-1\)的个数，但这样得到的所有方案在\(i-1\)这个位置上最大的是\(j-1\)，其实在\(i-1\)这个位置可以放\(j\)，所以再加上第\(i-1\)位置上放\(j\)的方案数。

AC代码

#include<bits/stdc++.h>

const int mod=1e9+7;

const int maxn=2e1+10;

const int maxm=1e3+20;

typedef long long ll;

typedef unsigned long long ull;

using namespace std;

int dp[maxn][maxm];

int main()

{

    // freopen("data.txt","r",stdin);

    int n,m;

    cin>>n>>m;

    for(int i=1;i<=n;i++)dp[1][i]=1;

    for(int i=2;i<=2*m;i++){

        for(int j=1;j<=n;j++){

            dp[i][j]=(dp[i][j-1]+dp[i-1][j])%mod;

        }

    }

    ll ans=0;

    for(int i=1;i<=n;i++){

        ans+=dp[2*m][i];

        ans%=mod;

    }

    cout<<ans<<endl;

    return 0;

}

总结

后悔拿到这道题没思考，再仔细思考一下，在理解题目的意思之后应当建立对应的模型，思维不能太线性了。

巴特西

Educational Codeforces Round 80 (Rated for Div. 2)部分题解

A. Deadline

题目大意

解题思路

AC代码1

AC代码2

总结

B. Yet Another Meme Problem

题目大意

解题思路

AC代码

总结

C. Two Arrays

题目大意

解题思路

AC代码

总结

最新文章

热门文章