2021-02-19-2月19日题解

A题

题解

数据量比较少，暴力做即可。

代码

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
int a[4][1000]={0};
int p[2000]={0};
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[1][i]);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[2][i]);        
        for(int i=1;i<=n;i++)
            scanf("%d",&a[3][i]);
        for(int i=1;i<=n;i++)
        {
            if(i!=n)
            {
                for(int j=1;j<=3;j++)
                {
                    if(a[j][i]!=p[i-1])
                    {
                        p[i]=a[j][i];
                        break;
                    }
                }
            }
            else
            {
                for(int j=1;j<=3;j++)
                {
                    if(a[j][i]!=p[i-1]&&a[j][i]!=p[1])
                    {
                        p[i]=a[j][i];
                        break;
                    }
                }
            }
        }
        for(int i=1;i<=n;i++)
            printf("%d ",p[i]);
        printf("\n");
    }
    return 0;
}

B题

题解

找规律，容易发现b数组的最少个数和a数组中数字跳跃的次数有关。

代码

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
int a[1005]={0};
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,k,sum=0;
        scanf("%d%d",&n,&k);
        a[0]=-1;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(a[i]!=a[i-1])
                sum++;
        }
        if(sum<=k)
        {
            printf("1\n");
            continue;
        }
        else
        {
            sum-=k;
            k--;
            if(k==0)
            {
                printf("-1\n");
                continue;
            }
            else
            {
                int ans=sum/k;
                ans++;
                if(sum%k!=0)
                    ans++;
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}

C题

题解

二分答案，二分两辆车最终相遇的位置，计算两车所用的时间。注意二分的精度！！！

代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[100500]={0};

int check(double mid)
{
    double t1=0,t2=0;
    int s1=1,s2=1,last1=1,last2=k+1;
    for(int i=1;a[i]<=mid&&i<=n;i++)
    {
        if(a[i]<=mid)
        {
            t1+=(a[i]-last1)*1.0/s1;
            s1++;
            last1=a[i];
        }
    }
    if(last1<=mid)
    {
        t1+=(mid-last1)*1.0/s1;
    }

    for(int i=n;a[i]>=mid&&i>=1;i--)
    {
        if(a[i]>=mid)
        {
            t2+=(last2-a[i])*1.0/s2;
            s2++;
            last2=a[i];
        }
    }
    if(last2>=mid)
    {
        t2+=(last2-mid)*1.0/s2;
    }

    if(t1>t2)
        return 1;
    else
        return 0;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            a[i]++;
        }
        double l=1,r=k+1;
        while(abs(r-l)>0.00001)
        {
            double mid=(l+r)/2;
            if(check(mid))
                r=mid;
            else
                l=mid+0.000001;
        }

        double t=0;
        int s1=1,last1=1;
        for(int i=1;a[i]<l&&i<=n;i++)
        {
            t+=(a[i]-last1)*1.0/s1;
            s1++;
            last1=a[i];
        }
        if(last1<l)
        {
            t+=(l-last1)*1.0/s1;
        }
        printf("%.15f\n",t);
    }
    return 0;
}

D题

题解

由于x的范围为1e6，可以 通过 枚举左移的数量 并 计算上移的数量 求和取最小 来确定答案。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
    ll x,y;
};
node a[2050]={0};
node b[2050]={0};
ll ans[1005000]={0};
int main()
{
    ll n,m;
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++)
        scanf("%lld%lld",&a[i].x,&a[i].y);
    for(ll j=1;j<=m;j++)
        scanf("%lld%lld",&b[j].x,&b[j].y);
    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=m;j++)
        {
            ll x=b[j].x-a[i].x;
            ll y=b[j].y-a[i].y;
            if(x>=0&&y>=0)
            {
                ans[x]=max(ans[x],y+1);
            }
        }
    }
    ll min1=999999999,max1=-10000000;
    for(ll i=1000500;i>=0;i--)
    {
        max1=max(max1,ans[i]);   ///ans数组肯定是不减的，枚举距离即可。
        min1=min(min1,max1+i);
    }
    cout<<min1<<endl;
}

I题

题解

由于操作次数上限为3 * n * m次，所以可以通过枚举每个小矩阵，让每个小矩阵变为0，最后便可以让整个矩阵变为0。但是J题要求上限为n*m次，无法通过，额。

另：代码写得比较恶心，额。

代码

#include<bits/stdc++.h>
using namespace std;
int a[200][200]={0};
int dx[5]={0,0,1,0,1};
int dy[5]={0,0,0,1,1};
struct node
{
    int p[10];
};
vector<node>ans;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%1d",&a[i][j]);
            }
        }
        for(int i=1;i<=n-1;i++)
        {
            for(int j=1;j<=m-1;j++)
            {
                int sum=0;
                for(int k=1;k<=4;k++)
                {
                    int x=i+dx[k],y=j+dy[k];
                    if(a[x][y]==1)
                        sum++;
                }
                if(sum==3)
                {
                    node z;
                    int id=0;
                    for(int k=1;k<=4;k++)
                    {
                        int x=i+dx[k],y=j+dy[k];
                        if(a[x][y]==1)
                            z.p[++id]=x,z.p[++id]=y;
                    }
                    ans.push_back(z);
                }
                else if(sum==4)
                {
                    node z;
                    z.p[1]=i,z.p[2]=j,z.p[3]=i+1,z.p[4]=j,z.p[5]=i,z.p[6]=j+1;
                    ans.push_back(z);  
                    z.p[1]=i+1,z.p[2]=j,z.p[3]=i,z.p[4]=j,z.p[5]=i+1,z.p[6]=j+1;
                    ans.push_back(z);                        
                    z.p[1]=i+1,z.p[2]=j+1,z.p[3]=i+1,z.p[4]=j,z.p[5]=i,z.p[6]=j+1;
                    ans.push_back(z);                        
                    z.p[1]=i,z.p[2]=j+1,z.p[3]=i,z.p[4]=j,z.p[5]=i+1,z.p[6]=j+1;
                    ans.push_back(z);
                }
                else if(sum==2)
                {
                    node z;
                    if(a[i+1][j]==1&&a[i][j]==1)
                    {
                        z.p[1]=i+1,z.p[2]=j+1,z.p[3]=i+1,z.p[4]=j,z.p[5]=i,z.p[6]=j+1;
                        ans.push_back(z);
                        z.p[1]=i,z.p[2]=j,z.p[3]=i+1,z.p[4]=j+1,z.p[5]=i,z.p[6]=j+1;
                        ans.push_back(z);
                    }
                    else if(a[i][j+1]==1&&a[i][j]==1)
                    {
                        z.p[1]=i,z.p[2]=j,z.p[3]=i+1,z.p[4]=j,z.p[5]=i+1,z.p[6]=j+1;
                        ans.push_back(z);
                        z.p[1]=i+1,z.p[2]=j+1,z.p[3]=i+1,z.p[4]=j,z.p[5]=i,z.p[6]=j+1;
                        ans.push_back(z);
                    }
                    else if(a[i+1][j+1]==1&&a[i][j+1]==1)
                    {
                        z.p[1]=i,z.p[2]=j,z.p[3]=i+1,z.p[4]=j,z.p[5]=i,z.p[6]=j+1;
                        ans.push_back(z);
                        z.p[1]=i+1,z.p[2]=j,z.p[3]=i,z.p[4]=j,z.p[5]=i+1,z.p[6]=j+1;
                        ans.push_back(z);
                    }
                    else if(a[i+1][j+1]==1&&a[i+1][j]==1)
                    {
                        z.p[1]=i,z.p[2]=j,z.p[3]=i+1,z.p[4]=j,z.p[5]=i,z.p[6]=j+1;
                        ans.push_back(z);
                        z.p[1]=i,z.p[2]=j+1,z.p[3]=i+1,z.p[4]=j+1,z.p[5]=i,z.p[6]=j;
                        ans.push_back(z);
                    }
                    else if(a[i+1][j+1]&&a[i][j])
                    {
                        z.p[1]=i,z.p[2]=j,z.p[3]=i+1,z.p[4]=j,z.p[5]=i,z.p[6]=j+1;
                        ans.push_back(z);
                        z.p[1]=i,z.p[2]=j+1,z.p[3]=i+1,z.p[4]=j,z.p[5]=i+1,z.p[6]=j+1;
                        ans.push_back(z);
                    }
                    else if(a[i][j+1]&&a[i+1][j])
                    {
                        z.p[1]=i+1,z.p[2]=j,z.p[3]=i,z.p[4]=j,z.p[5]=i+1,z.p[6]=j+1;
                        ans.push_back(z);
                        z.p[1]=i,z.p[2]=j+1,z.p[3]=i,z.p[4]=j,z.p[5]=i+1,z.p[6]=j+1;
                        ans.push_back(z);
                    }
                }
                else if(sum==1)
                {
                    if(a[i][j])
                    {
                        node z;
                        z.p[1]=i+1,z.p[2]=j,z.p[3]=i,z.p[4]=j,z.p[5]=i+1,z.p[6]=j+1;
                        ans.push_back(z);
                        z.p[1]=i,z.p[2]=j,z.p[3]=i+1,z.p[4]=j,z.p[5]=i,z.p[6]=j+1;
                        ans.push_back(z);
                        z.p[1]=i,z.p[2]=j+1,z.p[3]=i+1,z.p[4]=j+1,z.p[5]=i,z.p[6]=j;
                        ans.push_back(z);
                    }
                    else if(a[i+1][j])
                    {
                        node z;
                        z.p[1]=i+1,z.p[2]=j,z.p[3]=i,z.p[4]=j,z.p[5]=i,z.p[6]=j+1;
                        ans.push_back(z);
                        z.p[1]=i,z.p[2]=j,z.p[3]=i+1,z.p[4]=j,z.p[5]=i+1,z.p[6]=j+1;
                        ans.push_back(z);
                        z.p[1]=i+1,z.p[2]=j+1,z.p[3]=i+1,z.p[4]=j,z.p[5]=i,z.p[6]=j+1;
                        ans.push_back(z);
                    }
                    else if(a[i+1][j+1])
                    {
                        node z;
                        z.p[1]=i,z.p[2]=j+1,z.p[3]=i+1,z.p[4]=j+1,z.p[5]=i,z.p[6]=j;
                        ans.push_back(z);
                        z.p[1]=i,z.p[2]=j,z.p[3]=i+1,z.p[4]=j,z.p[5]=i+1,z.p[6]=j+1;
                        ans.push_back(z);
                        z.p[1]=i+1,z.p[2]=j+1,z.p[3]=i+1,z.p[4]=j,z.p[5]=i,z.p[6]=j+1;
                        ans.push_back(z);
                    }
                    else if(a[i][j+1])
                    {
                        node z;
                        z.p[1]=i,z.p[2]=j,z.p[3]=i+1,z.p[4]=j,z.p[5]=i,z.p[6]=j+1;
                        ans.push_back(z);
                        z.p[1]=i+1,z.p[2]=j+1,z.p[3]=i+1,z.p[4]=j,z.p[5]=i,z.p[6]=j+1;
                        ans.push_back(z);
                        z.p[1]=i,z.p[2]=j,z.p[3]=i+1,z.p[4]=j+1,z.p[5]=i,z.p[6]=j+1;
                        ans.push_back(z);
                    }
                }
                for(int k=1;k<=4;k++)
                {
                    int x=i+dx[k],y=j+dy[k];
                    a[x][y]=0;
                }
            }
        }
        printf("%d\n",ans.size());
        for(node i:ans)
        {
            for(int j=1;j<=6;j++)
            {
                printf("%d ",i.p[j]);
            }
            printf("\n");
        }
        ans.clear();
    }
    return 0;
}