Codeforces Round #643 (Div. 2) (A模拟+B贪心+C(差分数组+前缀和/枚举)+D(思维))

2021-01-17 13:12

阅读：580

标签：http algo 通过 mes algorithm 种类 i++ target 子序列

A：http://codeforces.com/contest/1355/problem/A

题意：

每次加这个数每一位的最大和最小的乘积，求第K次的结果。

解析：

直接模拟即可，但是有一个TLE点，就是当最大或最小=0时，就需要终止了，因为再加下去值就不变了。

#include
#include
#include
#includestring>
#include
#includeset>
#include
#include
#include
typedef long long ll;
using namespace std;
const int maxn=2e5+10;
int a[maxn];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=0;i)
            cin>>a[i];
        int cnt=0;
        sort(a,a+n);
        int sum=0;
        for(int i=0;i)
        {
            cnt++;
            if(cnt==a[i])
            {
                sum++;
                cnt=0;
            }
        }
        coutendl;
    }
}

B：http://codeforces.com/contest/1355/problem/B

题意：

分组，每个人的e值不能大于当前组人数，求最大组数。

解析：

贪心取，当前组人数==e[]时，就算一个组，组数++，组人数清0。

#include
#include
#include
#includestring>
#include
#includeset>
#include
#include
#include
typedef long long ll;
using namespace std;
const int maxn=2e5+10;
int a[maxn];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=0;i)
            cin>>a[i];
        int cnt=0;
        sort(a,a+n);
        int sum=0;
        for(int i=0;i)
        {
            cnt++;
            if(cnt==a[i])
            {
                sum++;
                cnt=0;
            }
        }
        coutendl;
    }
}

C：http://codeforces.com/contest/1355/problem/C

题意：A

解析：

差分数组+前缀和解法：

首先x+y>z才能是一个三角形。

那么如果知道了x+y的种类数，那么直接枚举x+y>c的c的数目，就是答案。

用差分数组来记录a+b的种类数。对于一个x，x+y的范围就是：[x+b,x+c]。

这里通过差分数组维护，然后通过两次前缀和还原。对于cc的数目，累加即可。

#include
#include
#include
#includeusing namespace std;
typedef long long ll;
const int maxn=1e6+10;
ll x[maxn];
int main()
{
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    for(int i=a;i)
    {
        x[i+b]++;
        x[i+c+1]--;
    }
    for(int i=1;i)
        x[i]+=x[i-1];
    for(int i=1;i)
        x[i]+=x[i-1];
    ll cnt=0;    
    for(int i=c;i)    
        cnt+=x[maxn-1]-x[i];
    coutendl;
}

枚举：

如果确定了x+y而且确定了x,那么y是确定的。所以x的数目*z的数目，就是答案。通过枚举x+y，此时可取的c的数目为：min(i-1,d)-c+1。x的数目，需要通过区间：

x+y=m

y=m-x

m-C

又A

所以这里取个交集即可，即为可取的x的数目。

x的数目*c的数目，累加即可。

#include
#include
#include
#includeusing namespace std;
typedef long long ll;
const int maxn=1e6+10;
ll x[maxn];
int main()
{
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll sum=0;
    for(ll i=a+b;i)
    {
        ll m1=min(i-1,d)-c+1;
        ll m2=min(i-b,b)-max(i-c,a)+1;
        if(m10||m20)
            continue;
        sum+=m1*m2;
    }
    coutendl;
}

D：http://codeforces.com/contest/1355/problem/D

题意：

构造一个含有n个数，和为s的数组，能否找到一个K，使得没有子序列的和为K或者S-K。

解析：

先放n-1个1，最后一个是s-(n-1)

那么我们假设k为n，可以保证前n-1个1加不到n。

如果n>(s-n+1)

有子序列和范围：[s-n+1,s]

n>=s-n+1，很明显，n在范围里面，就算前n-1个1加不到n，s-n也还是可以被加到。

如果n

就可以保证s-n不会被加到

#include
#include
#include
#includestring>
#include
#includeset>
#include
#include
#include
typedef long long ll;
using namespace std;
const int maxn=2e5+10;
int a[maxn];
int main()
{
    int n,s;
    cin>>n>>s;
    if(n==s)
        cout"NO"endl;
    else
    {
        int md=n-1;
        int md2=s-(n-1);
        if(md+1>=md2)
            cout"NO"endl ;
        else
        {
            cout"YES"endl;
            for(int i=1;i)
                cout"1"" ";
            coutendl;
            coutendl;
        }
    }
}

Codeforces Round #643 (Div. 2) (A模拟+B贪心+C(差分数组+前缀和/枚举)+D(思维))

标签：http algo 通过 mes algorithm 种类 i++ target 子序列

原文地址：https://www.cnblogs.com/liyexin/p/12918350.html

上一篇：产生10个随机数，用冒泡法排序，从大到小输出(降序)

下一篇：Python-网易音乐下载

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Codeforces Round #643 (Div. 2) (A模拟+B贪心+C(差分数组+前缀和/枚举)+D(思维))
文章链接：http://soscw.com/index.php/essay/43198.html

亲，登录后才可以留言！

Codeforces Round #643 (Div. 2) (A模拟+B贪心+C(差分数组+前缀和/枚举)+D(思维))

评论

热门文章

推荐文章

最新文章

置顶文章