8.20测试总结

· · 算法·理论

8.20测试总结

T638487 打扫卫生

得分:20

应得:100

考点:模拟

错误思路:骗分（输出10）

正确思路:从左上角查询是否有k*k的由"*"组成的正方形，如果有都变为".",最后如果还有"*"便失败，没有便成功

正确代码:

#include<bits/stdc++.h>
using namespace std;
char a[5005][5005];
int ans,n,m,k;
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {

        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    if(n*m<k)
    {
        cout<<"-1";
        return 0;
    }
    for(int zsx=1;zsx+k-1<= n;zsx++)
    {
        for(int zsy=1;zsy+k-1<=m;zsy++)
        {
            int yxx=zsx+k- 1;
            int yxy=zsy+k-1; 
            bool flag=1;
            bool flag1=0;
            for(int i=zsx;i<=yxx;i++)
            {
                if(flag==0)
                {
                    break;
                } 
                for(int j=zsy;j<=yxy;j++)
                {
                    if(a[i][j]=='*')
                    {
                        flag1=1 ;
                    }
                    if(a[i][j]!='*')
                    {

                        flag=0; 
                        break;
                    }   
                }   
            }
            if(flag1==1&&flag==0)
            {
                cout<<-1;
                return 0;
            }
            if(flag)
            {
                for(int i=zsx;i<=yxx;i++)
                {
                    for(int j=zsy;j<=yxy;j++)
                    {
                        a[i][j]='.';
                    }   
                }
                ans++;  
            }           
        }
    }
    cout<<ans;
    return 0 ;
}

T643658 落落的去的数学题1

得分:50

应得:100

考点:数学（二进制）

错误思路:模拟

正确思路:

推断公式：b-c+1

正确代码:

#include<bits/stdc++.h>
using namespace std;
int a,b,c;
int main()
{
    cin>>a>>b>>c;
    cout<<b-c+1;
    return 0;
}

T640726 落落的去的围栏

得分:0

应得:100

考点:二分

错误思路:模拟（爆0了QAQ）

正确思路:由于可能性是镜像的，因此使用二分时间复杂度会降低（避免TLE）

正确代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,m,a[200005];
signed main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=0;i<m;i++)
        {
            cin>>a[i];
        }
        sort(a,a+m);
        int ans=0;
        for(int i=1;i<n;i++)
        {
            int l=m-(lower_bound(a,a+m,i)-a);
            int r=m-(lower_bound(a,a+m,n-i)-a);
            ans+=l*r-min(l,r);
        }
        cout<<ans<<endl;
    }
    return 0;
}