codeforces Round500(Div2)

昨天打了cf,然后太菜了,挂了一题,然后有一题差点调出来。。。

T1:Piles With Stones

题意:

有一堆石子,你可以从中拿走或者移动一些石子。。。给你原来石子的排列,和之后的排列,问你是否成立。。。

分析:

我们要看前后两次的石子个数大小就好了。。。

代码:

#include<bist/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e4+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO
{
    template inline void read(tp &x)
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
int x[100],y[100],sum;
main()
{
    int n;
    read(n);
    for(int i=1;i<=n;i++)
        read(x[i]),sum+=x[i];
    for(int i=1;i<=n;i++)
        read(y[i]),sum-=y[i];
    if(sum<0)puts("No");
    else puts("Yes");
    return 0;
}

T2:And

题意:

问你给你n个数组成的数列,你可以把其中任意的数字或上一个数,然后为出现两个相同的数最少要操作几次。。。

分析:

直接暴力搜就好了。。。

代码:

#include<bist/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e4+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO
{
    template inline void read(tp &x)
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
int x[100010],n,m;
int vis[300010],ans;
main()
{
    read(n);read(m);
    for(int i=1;i=2)
        {
            puts("0");
            return 0;
        }
    }
    for(int i=1;i<=n;i++)
        if((x[i]&m)!=x[i])
        {
            if(vis[x[i]&m]==1)
            {
                puts("1");
                return 0;
            }
        }
    for(int i=1;i<=n;i++)
        if((x[i]&m)!=x[i])
        {
            if(vis[x[i]&m]==2)
            {
                puts("2");
                return 0;
            }
            else vis[x[i]&m]=2;
        }
    puts("-1");
    return 0;
}

T3:Photo of The Sky

题意:

给你2×n个数,拼成n个坐标,问你可以包住他们的最小矩阵面积大小。。。

分析:

我们可以知道最小值和最大值不管实在横坐标还是纵坐标上都是上下界。。。那么我们直接考虑最大值和最小值在不在同一个坐标域内。。。如果在,那么直接枚举另一个坐标域的最小值就好了。。。如果不在,直接看代码吧,讲不清。。。

代码:

#include<bist/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e4+10;
const LL mod=1e9+7;
const LL inf=1e18;
namespace FastIO
{
    template inline void read(tp &x)
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
LL x[200010],n,ans;
main()
{
    read(n);
    for(int i=1;i<=n*2;i++)
        read(x[i]);
    sort(x+1,x+2*n+1);
    ans=(x[2*n]-x[n+1])*(x[n]-x[1]);
    for(int i=n+1;i<2*n;i++)
        ans=min(ans,(x[n*2]-x[1])*(x[i]-x[i-n+1]));
    writeln(ans);
    return 0;
}

T4:Chemical table

题意:

给出一个长宽给定的大矩形,已知如果你有一个小矩阵的三点角,那么可以制造出第四个角。。。刚开始给了你几个填好的格子问你还需要填几个格子才能填满所有格子。。。

分析:

我们思考一下,我们加入一个点把所有点组成了矩形,加入一个新个点我们就可以把矩形每行边话一下,发现题目的变化规律是一样的。。。那么我们用一个并查集来维护相同的行列。。。就好了。。。

代码:

#include<bist/stdc++.h>
#define LL long long
using namespace std;
const LL N=4e5+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f;
namespace FastIO
{
    template inline void read(tp &x)
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
int x,y,father[N],n,m,q;
inline int id(int x,int y) {return x + y * n;}
int getfa(int pos) {return pos == father[pos] ? pos : father[pos] = getfa(father[pos]);}
int main() 
{
    read(n),read(m),read(q);
    for (int i = 1 ; i <= n + m ; ++ i)
        father[i] = i;
    for (int i = 1 ; i <= q ; ++ i) 
    {
        read(x),read(y);
        x = id(x,0),y = id(y,1);
        x = getfa(x),y = getfa(y);
        father[x] = y;
    }
    int ans = -1;
    for (int i = 1 ; i <= n + m ; ++ i)
        if (getfa(i) == i) ++ ans;
    writeln(ans);
    return 0;
}

T5:Hills

题意:

给你n座山,你可以在1时间内把一座山挖矮一高度,一个房子只能建在高山上(两边是山都没他高)。。。然后问你建一个房子到建(n/2+2%2)个房子,的最小代价。。。

分析:

我们设dp[i][j][k],i表示当前到了第i座山,j表示现在有j座山上有房子,k=1表示当前山上没有房子,k=2边上山上有房子。。。我们思考dp方程。。。

dp[i][j][1]=min(dp[i-1][j][1],dp[i-1][j][2]);

dp[i][j][2]=min(dp[i-2][j-1][1]+建房代价,dp[i-2][j-1][2]+建房代价);

这其中有一些细节,考虑一下就好。。。(代码太恶心,你们别多看)

代码:

#include<bist/stdc++.h>
#define LL long long
using namespace std;
const LL N=5e3+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO
{
    template inline void read(tp &x)
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
int h[N],n;
int dp[N/2+4000][N][3];
int ans[N/2+4000];
main()
{
    read(n);
    for(int i=1;i<=n;i++)
        read(h[i]),ans[i/2+1]=inf;
    for(int i=0;i<=n;i++)
        for(int j=1;j<=n/2+2;j++)
            dp[i][j][1]=dp[i][j][2]=inf,dp[i][0][2]=inf;
    h[0]=h[n+1]=-inf;
    for(int i=1;i<=n;i++)
        for(int j=1;jh[i]&&h[i-1]>=h[i])
                ch=min(h[i-2]-h[i],h[i-1]-h[i]+1);
            if(h[i+1]>=h[i])
                ch+=h[i+1]-h[i]+1;
            dp[i][j][1]=min(dp[i-1][j][2],dp[i-1][j][1]);
            if(j==1)
                dp[i][j][2]=max(0,h[i-1]-h[i]+1)+max(0,h[i+1]-h[i]+1);
            else 
            {
                if(i>3) dp[i][j][2]=min(dp[i-2][j-1][1]+max(0,h[i-1]-h[i]+1)+max(0,h[i+1]-h[i]+1),dp[i-2][j-1][2]+ch);
                else if(i==1)dp[i][j][2]=max(0,h[2]-h[1]+1);
                else if(i==3)
                {
                    if(j==1)dp[i][j][2]=max(0,h[2]-h[3]+1)+max(h[4]-h[3]+1,0);
                    else dp[i][j][2]=max(0,h[2]-min(h[1],h[3])+1)+max(h[4]-h[3]+1,0);
                }
                else dp[i][j][2]=max(0,h[1]-h[2]+1)+max(h[3]-h[2]+1,0);
            }
            ans[j]=min(ans[j],min(dp[i][j][1],dp[i][j][2]));
        }
    for(int i=1;i<=n/2+n%2;i++)
        printf("%d ",ans[i]);
    puts("");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注