欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces 1371 A,B,C,D,E1,E2题解

程序员文章站 2022-06-04 16:18:50
...

This way

A. Magical Sticks:

现在有n个木棒,第i个木棒的长度为i,你每次可以将两根木棒合并,从而得到一根长度为他们长度之和的木棒。最终希望长度相同的木棒最多,问这个答案是多少

A题解:

那么很明显,第一根木棒和最后一根合并,第二根和倒数第二根合并。。。以此类推于是答案就是(n+1)/2

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        printf("%d\n",(n+1)/2);
    }
    return 0;
}

B. Magical Calendar:

你可以将一个星期的长度定义为1~r,他现在要涂色连续的n天,如果超过了最后一天,那么就在下一行的第一天开始。他要使得所有涂色过的格子连在一起,问你最终本质不同的涂色方法有多少。

B题解:

那么我们可以知道最大只能取到min(n-1,r),
然后长度为1时答案是1,长度为2时答案是2…以此类推
超出n-1的部分的答案总共是1,因为都是一条线段。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        ll n,r;
        scanf("%lld%lld",&n,&r);
        if(r<n)
            printf("%lld\n",(1+r)*r/2);
        else
            printf("%lld\n",(1+n-1)*(n-1)/2+1);
    }
    return 0;
}

C. A Cookie for You

有a个香草饼,b个巧克力饼,现在有n个第一种客人,m个第二种客人按照你排好的次序来,每个客人来的时候都会拿一个饼,
如果来的客人是第一种,如果当前a>b,那么他会拿a,否则拿b
来的客人是第二种的话,如果当前a>b,那么他会拿b,否则拿a
如果这个客人没拿到饼,宴会失败。
问你最终宴会是否成功。

C题解:

首先如果a+b<n+m一定失败,然后如果m>min(a,b)的话,由于m每次都会拿比较少的那一个,所以其实m能够拿的数量是min(a,b).

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        ll a,b,n,m;
        scanf("%lld%lld%lld%lld",&a,&b,&n,&m);
        if(m>min(a,b)||n+m>a+b)
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}

D. Grid-00100

现在有n*n的格子,每个格子要么是0,要么是1,现在告诉你有k个1,并且定义
Codeforces 1371 A,B,C,D,E1,E2题解
Codeforces 1371 A,B,C,D,E1,E2题解
要使得f最小,问你构造方法。

D题解:

那么我们要使得f最小,肯定是要尽量让每行的1数量相同,每列的1数量相同,那么我们一次一次斜着放1即可,这样如果k%n=0的话,答案是0,否则答案是2.就像这个样子:
Codeforces 1371 A,B,C,D,E1,E2题解

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e2+5;
bool mp[N][N];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        memset(mp,0,sizeof(mp));
        int n,k;
        scanf("%d%d",&n,&k);
        if(k%n)
            printf("2\n");
        else
            printf("0\n");
        while(k){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++,k--){
                    if(!k)break;
                    mp[j][(j+i)%n]=1;
                }
                if(!k)break;
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++)
                printf("%d",mp[i][j]);
            printf("\n");
        }
    }
    return 0;
}

E1.Asterism (Easy Version):

定义f(x):
你一开始有x颗糖,现在有n个敌人,每个敌人有ai颗糖,你要去按照一个排列去战胜这些敌人,当你的糖的数量>=ai的时候,你就可以战胜他,赢了之后你就可以得到一颗糖。f(x)表示可以赢的排序的数量。
找到一些x使得f(x)不是p的倍数。

E1题解:

当然hard的题解也能用,但是数据范围不同就应该有不同的想法。
首先看到范围就知道是O(n2)O(n^2)的想法,那么我们首先可以选择枚举x,然后再从1到n枚举位置,用一个r维护我们当前右端第一个不能取到的位置,如果r-i是p的倍数,证明不行。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N];
vector<int>ans;
int main()
{
    int n,p;
    scanf("%d%d",&n,&p);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    int x=1;
    for(int i=1;i<=n;i++)
        x=max(a[i]-i+1,x);
    for(;x<=a[n];x++){
        int r=1,f=0;
        for(int i=1;i<=n;i++){
            while(r<=n&&x+i-1>=a[r])
                r++;
            if((r-i)%p==0){
                f=1;
                break;
            }
        }
        if(!f)
            ans.push_back(x);
    }
    printf("%d\n",ans.size());
    for(int i:ans)
        printf("%d ",i);
    printf("\n");
    return 0;
}

E2.Asterism (Hard Version)题解:

它写个hard version,我以为很难啊,没想到原来是个水题?绝了
首先按照a从大到小排序,然后赢过第ai的最少需要的x是ai-i+1.那么从所有中取个最大值
然后我们可以知道,你每次能赢过的人的数量不能大于等于p,因为这样的话,当能取的区间慢慢缩小时,一定能取到p。
对于第i个数,如果你的值>=ai-i+p的话,就是违法的。那么只要在其中取个最小值,然后从左界到右界输出一下即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N];
int main()
{
    int n,p;
    scanf("%d%d",&n,&p);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    int l=1,r=1e9;
    for(int i=1;i<=n;i++)
        l=max(l,a[i]-i+1);
    for(int i=p;i<=n;i++)
        r=min(r,a[i]-i+p);
    if(l<r){
        printf("%d\n",r-l);
        for(int i=l;i<r;i++)
            printf("%d%c",i," \n"[i==r-1]);
    }
    else
        printf("0\n");
    return 0;
}

F. Raging Thunder(待定)