头像

qym2008


访客:2293

离线:14小时前


新鲜事 原文

qym2008
1天前
为啥用不了 $\texttt{AC Editor}$ 了qwq



qym2008
7天前

直接进行 sort ,从 l~r 即可。难度应该是 简单

代码一会写吧QwQ




qym2008
9天前

有排行榜吗qwq




qym2008
12天前

这题最朴素暴力的方法就是对每个点做一次搜索,代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1}; 
int n,m,st[N][N];
char g[N][N];
void init()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)   
            st[i][j]=1e9;
}
void BFS(int sx,int sy)
{
    st[sx][sy]=0;
    queue<int> q1,q2;
    q1.push(sx);q2.push(sy);
    while(!q1.empty())
    {
        int x=q1.front(),y=q2.front();
        q1.pop(),q2.pop();
        for(int i=0;i<4;i++)
        {
            int tx=x+dx[i],ty=y+dy[i];
            if(tx>=1 and tx<=n and ty>=1 and ty<=m and st[x][y]+1<=st[tx][ty] and g[tx][ty]!='1')
            {
                st[tx][ty]=st[x][y]+1;
                q1.push(tx);
                q2.push(ty);
            }   
        } 
    } 
}
int main()
{
    scanf("%d%d",&n,&m);
    init();
    for(int i=1;i<=n;i++)
        scanf("%s",g[i]+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(g[i][j]=='1')
                BFS(i,j);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            printf("%d ",st[i][j]);
        printf("\n");
    }   
    return 0;
}

然后不出所料的TLE了

那么怎么办呢?就是把每一个是 “1” 的点都入队,之后挨个进行搜索即可。

这个比较好理解,不懂可以看yxc的讲解:link

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
char g[N][N];
int dist[N][N],n,m;
const int dx[]={-1,0,1,0};
const int dy[]={0,1,0,-1};
void BFS()
{
    queue<int> q1,q2;
    memset(dist,-1,sizeof dist);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(g[i][j]=='1')
            {
                dist[i][j]=0;
                q1.push(i),q2.push(j); 
            }
    while(!q1.empty())
    {
        int x=q1.front(),y=q2.front();
        q1.pop(),q2.pop();
        for(int i=0;i<4;i++)
        {
            int tx=x+dx[i],ty=y+dy[i];
            if(tx>=1 and tx<=n and ty>=1 and ty<=m and dist[tx][ty]==-1)
            {
                dist[tx][ty]=dist[x][y]+1;
                q1.push(tx),q2.push(ty);    
            } 
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>g[i][j];
    BFS();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            cout<<dist[i][j]<<" ";
        printf("\n");
    } 
    return 0;
}



qym2008
1个月前

如果我要求的是 $C_m^n$ 但是不想取模一个数怎么做。。不要说mod开到最大。。。qwq




qym2008
1个月前

为什么这个代码会WA:

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,f[N],a[N],d[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<i;j++)
            if(a[i]>a[j])
                f[i]=max(f[i],f[j]+1);
    }
    for(int i=1;i<=n;i++)
    {
        d[i]=1;
        for(int j=1;j<i;j++)
            if(a[i]<a[j])
                d[i]=max(d[i],d[j]+1);
    }
    int res=-1;
    for(int i=1;i<=n;i++) res=max(res,f[i]+d[i]-1);
    cout<<res;
    return 0;
}

而这个代码却AC了?

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,f[N],a[N],d[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<i;j++)
            if(a[i]>a[j])
                f[i]=max(f[i],f[j]+1);
    }
    for(int i=n;i>=1;i--)
    {
        d[i]=1;
        for(int j=n;j>i;j--)
            if(a[i]>a[j])
                d[i]=max(d[i],d[j]+1);
    }
    int res=-1;
    for(int i=1;i<=n;i++) res=max(res,f[i]+d[i]-1);
    cout<<res;
    return 0;
}

都是求最长下降子序列。。为什么第二个就对了呢?照理说应该一样啊。。

唯一的区别就是第二层循环不一样。。




qym2008
2个月前

那个。。《全国信息学线上测试》那个比赛是在AcWing举行吗?QAQ



活动打卡代码 AcWing 1140. 最短网络

qym2008
2个月前
#include<bits/stdc++.h>
using namespace std;
const int N=510,INF=0x3f3f3f3f; 
int n,m,g[N][N],dist[N];
bool st[N];
int Prim()
{
    memset(dist,0x3f,sizeof dist);
    int res=0;
    for(int i=1;i<=n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!st[j] and (t==-1 or dist[t]>dist[j]))
                t=j;
        if(i!=1 and dist[t]==INF) return INF;
        if(i!=1) res+=dist[t];
        st[t]=true;
        for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);  
    }
    return res;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>g[i][j];
    int t=Prim();
    if(t==INF) cout<<"impossible";
    else cout<<t;
    return 0;
}





qym2008
3个月前
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int primes[N],cnt;
bool st[N];
void init(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]*i<=n;j++)
        {
            st[i*primes[j]]=true;
            if(i%primes[j]==0) break;
        }
    }   
} 
int main()
{
//  freopen("Sherlock.in","r",stdin);
//  freopen("Sherlock.out","w",stdout); 
    int n;
    cin>>n;
    init(n+1);
    if(n<=2) printf("1\n");
    else printf("2\n");
    for(int i=2;i<=n+1;i++)
        if(!st[i]) printf("1 ");
        else printf("2 ");
    return 0;
}


活动打卡代码 AcWing 102. 最佳牛围栏

qym2008
3个月前
#include<bits/stdc++.h>

using namespace std;
const int N=100010;
int n,F;
double a[N],s[N];
bool check(double avg)
{
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]-avg;
    double mins=0;
    for(int i=F;i<=n;i++)
    {
        mins=min(mins,s[i-F]);
        if(s[i]>=mins) return true;
    }
    return false;
}
int main()
{
    scanf("%d%d",&n,&F);
    double l=0,r=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf",&a[i]);
        r=max(r,a[i]);
    }
    while(r-l>1e-5)
    {
        double mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%d",(int)(r*1000));
    return 0;
}