8-20 东塘407--蒋 程皓楠考试总结

· · 个人记录

T0

AC

T1

AC

T2

AC

T3

AC

T4

两个dfs，第一个四联通，第二个八连通

100pts code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=55;
char mp[N][N];
bool vis1[N][N],vis2[N][N];
int dx4[]={0,1,0,-1};
int dy4[]={-1,0,1,0};
int dx8[]={1,1,1,0,0,-1,-1,-1};
int dy8[]={0,1,-1,1,-1,0,1,-1};
int n,m,ans,idx;
void dfs(int x,int y)
{
    vis1[x][y]=idx;
    for(int i=0;i<4;i++)
    {
        int nx=dx4[i]+x;
        int ny=dy4[i]+y;
        if(nx<=0||nx>n||ny<=0||ny>m)continue;
        if(vis1[nx][ny]||mp[nx][ny]=='0')continue;
        dfs(nx,ny);
    }
}
bool query(int x,int y)
{
    if(x<=0||y<=0||x>n||y>m)return 1;
    vis2[x][y]=1;
    for(int i=0;i<8;i++)
    {
        int nx=dx8[i]+x;
        int ny=dy8[i]+y;
        if(mp[nx][ny]=='1'&&vis1[nx][ny]!=idx)continue;
        if(vis2[nx][ny])continue;
        if(query(nx,ny))return 1;
    }
    return 0;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>mp[i][j];
                vis1[i][j]=0;
            } 
        }
        ans=idx=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(vis1[i][j]||mp[i][j]=='0')continue;
                idx++;
                dfs(i,j);
                memset(vis2,0,sizeof(vis2));
                if(query(i,j))ans++;
            }
        } 
        cout<<ans<<'\n'; 
    } 
    return 0;
}

T5

WA,0pts

正确思路

树状数组+二分+离散化+逆序对(6)

主函数

首先离散化去重，然后枚举n次，返回在1~idx区间内第一个大于等于a[i]的下标，然后将a[i]赋值为这个下标，然后二分，若check(mid),则右端点赋值，答案赋值，反之，左端点赋值，直至l+1>=r退出循环输出答案即可

int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
        sort(b+1,b+1+n);
        idx=unique(b+1,b+1+n)-b-1;
        for(int i=1;i<=n;i++)
        {
            int t=lower_bound(b+1,b+idx+1,a[i])-b;
            a[i]=t;
        }
        int l=-1,r=n*(n-1)/2;
        while(l+1<r)
        {
            int mid=(l+r)/2;
            if(check(mid))r=mid;
            else l=mid;
        }
        cout<<r<<"\n";
    }

check函数

二分划分块数

bool check(int x)
{
    int cnt=1,sum=0;
    int l=1;
    for(int i=1;i<=n;i++)
    {
        int num=get_sum(idx)-get_sum(a[i]);
        if(sum+num<=x)sum+=num;
        else
        {
            cnt++;
            sum=0;
            for(int j=l;j<=i-1;j++)modify(a[j],-1);
            l=i;
        }
        modify(a[i],1);
    }
    for(int j=l;j<=n;j++)modify(a[j],-1);
    return cnt<=k;
}

100pts code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,k,c[N],a[N],b[N],idx;
map<int,int> mp;
int lowbit(int x)
{
    return x&-x;
}
int get_sum(int x)
{
    int res=0;
    while(x)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
void modify(int x,int val)
{
    while(x<=n)
    {
        c[x]+=val;
        x+=lowbit(x);
    }
    return ;
}
bool check(int x)
{
    int cnt=1,sum=0;
    int l=1;
    for(int i=1;i<=n;i++)
    {
        int num=get_sum(idx)-get_sum(a[i]);
        if(sum+num<=x)sum+=num;
        else
        {
            cnt++;
            sum=0;
            for(int j=l;j<=i-1;j++)modify(a[j],-1);
            l=i;
        }
        modify(a[i],1);
    }
    for(int j=l;j<=n;j++)modify(a[j],-1);
    return cnt<=k;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
        sort(b+1,b+1+n);
        idx=unique(b+1,b+1+n)-b-1;
        for(int i=1;i<=n;i++)
        {
            int t=lower_bound(b+1,b+idx+1,a[i])-b;
            a[i]=t;
        }
        int l=-1,r=n*(n-1)/2;
        while(l+1<r)
        {
            int mid=(l+r)/2;
            if(check(mid))r=mid;
            else l=mid;
        }
        cout<<r<<"\n";
    }
    return 0;
}