Codeforces Round #654 (Div. 2)

A:http://codeforces.com/contest/1371/problem/A

题意:

1~n个棒子,长度依次为1~n。可两两合成,求能得到的最多相同长度棒子数。

解析:

偶数,直接/2即可。

奇数,比如对5,

1,2,3,4,5

1~4,可合成为:5,5,加上末尾5,结果为3。

所以奇数时为n/2+1

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int main()
{    // 4 0 20
    int t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        if(n%2==0)
            cout<<n/2<<endl;
        else
        {
            cout<<n/2+1<<endl;
        }
    }
}

B:http://codeforces.com/contest/1371/problem/B

题意:

n天,r:一周的天数依次定为1~r,即1<=k<=r

问所能组成的不同图案数。要求是每个块都不能被孤立,两两要相邻。

解析:

当n>r时,对于每一个k来讲,种类数==k,即k=1,1种,k=2,2种......

所以,这种情况,直接等差数列求和:(r*r+r)/2

当n<=r时,画图得出,r==n时,算一种,r>n时,没有其他情况了,因为一周的天数>n,n除了排成一排,是不能再换行了,两两必须要相邻。

所以这个时候,等差数列求和求到n-1项,再+1即可。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{    // 4 0 20
    int t;
    cin>>t;
    while(t--)
    {
        ll n,r;
        cin>>n>>r;
        if(n>r)
            cout<<(r*r+r)/2<<endl;
        else
            {
                ll md=n-1;
                cout<<(md*md+md)/2+1<<endl;
            }
    }
}

C:http://codeforces.com/contest/1371/problem/C

题意:

a个香草,b个巧克力。

两种客人,分别n个,m个。

设v个香草,c个巧克力。

v>c,第一种客人吃香草,否则吃巧克力。

v>c,第二种客人吃巧克力,否则吃香草。

问是否有这么一种进场顺序,能保证所有人都有得吃。

解析:

可以看出,第一种客人,吃多的那一方,第二种客人,吃较少的那一方,

所以看第二种客人:对于初始较少的一方,吃完后,他们就没得吃了,所以为了每个人都有的吃,min(a,b)>=m

假设min(a,b)==b,当b==m时,需要a>=n

当b>m时,a+b-m>=n

总的来讲,就是:a+b>=n+m

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int main()
{    // 4 0 20
    int t;
    cin>>t;
    while(t--)
    {
        ll a,b,n,m;
        cin>>a>>b>>n>>m;
        if(min(a,b)>=m&&a+b>=n+m)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
}

D:http://codeforces.com/contest/1371/problem/D

题意:

构造n*n的01矩阵,要求包含k个1

使得f=(含1最大行-最小)^2+(含1最大列-最小)^2最小。

解析:

第一时间想到的,肯定是平均放。之前做过类似的:

Codeforces Round #654 (Div. 2)

当k%n==0的时候,f一定为0,直接按上图放即可。

k%n!=0时,f一定为1^2+1^2。因为先平均放后,余数依次往上加,一定能保证最大与最小的差距为1。

令b=k/n,yu=k%n

前yu行,每行放b+1个,其他的行均放b个,即可。

#include<iostream>
#include<set>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=4e2;int a[maxn][maxn];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        memset(a,0,sizeof(a));
        if(k%n==0)
            cout<<"0"<<endl;
        else
            cout<<"2"<<endl;
        int yu=k%n;
        int b=k/n;
        for(int i=0;i<yu;i++)
            for(int j=i;j<=i+b;j++)
                a[i][j%n]=1;
        for(int i=yu;i<n;i++)
            for(int j=i;j<b+i;j++)
                a[i][j%n]=1;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
                cout<<a[i][j];
                cout<<endl;
        }
    } 
}

 

上一篇:leetcode 654——最大二叉树


下一篇:654. 最大二叉树