头像

c_56




离线:22小时前


活动打卡代码 AcWing 1532. 找硬币

c_56
22小时前

nlogn 双指针算法
另外 n 是哈希表做法,自己从来没想过可以这么用 留意y总的这个代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    int bj=n;
    for(int i=1;i<=n;i++)
    {
        while(bj>i&&a[i]+a[bj]>m)bj--;
        if(bj==i)
        {
            cout<<"No Solution"<<endl;
            return 0;
        }
        if(a[i]+a[bj]==m)
        {
            cout<<a[i]<<" "<<a[bj]<<endl;
            return 0;
        }
    }

}


活动打卡代码 AcWing 1098. 城堡问题

c_56
2天前
#include<iostream>
#include<queue>
using namespace std;
typedef pair<int ,int>PII;
const int N=60;
int a[N][N];
bool vis[N][N];
int cnt;
int area;
    int m,n;
int dx[]={0, -1, 0, 1};
int dy[]={-1,0,1,0};
int bfs(int x,int y)
{
    queue<PII> q;
    q.push({x,y});
    vis[x][y]=1;
    int ans=0;
    while(q.size())
    {
        PII tmp=q.front();
        q.pop();
        ans++;
        for(int i=0;i<4;i++)
        {
            int xx=tmp.first+dx[i];
            int yy=tmp.second+dy[i];
            if(xx>=1&&xx<=m&&yy>=1&&yy<=n&&!vis[xx][yy]&&!(a[tmp.first][tmp.second]>>i&1))
            {
                vis[xx][yy]=1;
                q.push({xx,yy});
            }
        }
    }
    return ans;
}
int main()
{

    cin>>m>>n;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            if(!vis[i][j])
            {
                area=max(area,bfs(i,j));
                cnt++;
            }
        }
    cout<<cnt<<endl;
    cout<<area<<endl;
}



活动打卡代码 AcWing 1097. 池塘计数

c_56
2天前

注意唯一的一个坑是,要在入队前进行标记。否则会出现大量进队不操作的 情况,然后T掉

#include<iostream>
#include<queue>
using namespace std;
typedef   pair<int,int> PII;
const int N=1010;
char a[N][N];
bool vis[N][N];
int cnt;
int n,m;
void bfs(int x,int y)
{
    queue<PII> q;
    q.push({x,y});
    vis[x][y]=1;
    while(q.size())
    {   int xx=q.front().first;
        int yy=q.front().second;

        q.pop();
        for(int i=-1;i<=1;i++)
            for(int j=-1;j<=1;j++)
            {
                if(i==0&&j==0)continue;
                int xxx=xx+i;
                int yyy=yy+j;
                if(xxx>=1&&xxx<=n&&yyy>=1&&yyy<=m&&!vis[xxx][yyy]&&a[xxx][yyy]=='W')
                {
                    vis[xxx][yyy]=1;
                    q.push({xxx,yyy});
                }
            }
    }
}
int main()
{

    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(!vis[i][j]&&a[i][j]=='W')
            {
                bfs(i,j);
                cnt++;
            }
        }
    cout<<cnt<<endl;
}


活动打卡代码 AcWing 429. 奖学金

c_56
2天前

重载小于号的写法

#include<iostream>
#include<algorithm>
using namespace std;
const int N=310;

struct student
{
    int chinese,sum,xh;
    bool operator <(const student & p) const
    {
        if(sum !=p.sum)return sum>p.sum;
        if(chinese!=p.chinese)return chinese>p.chinese;
        if(xh!=p.xh)return xh<p.xh; 
    }
}a[N];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int q,w,e;
        cin>>q>>w>>e;
        a[i]={q,q+w+e,i};
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=5;i++)
    {
        cout<<a[i].xh<<" "<<a[i].sum<<endl;
    }
}


活动打卡代码 AcWing 756. 蛇形矩阵

c_56
9天前
#include<iostream>
using namespace std;
const int N=110;
int cnt=1;
int n,m;
int a[N][N];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
pair<int,int> bj[5];
int main()
{   
    cin>>n>>m;
    int zt=0;
    int xx=1;
    int yy=1;

    bj[0]={1,m};
    bj[1]={n,m};
    bj[2]={n,1};
    bj[3]={2,1};
    for(int k=1;k<=n*m;k++)
    {

        a[xx][yy]=k; 
        //cout<<a[xx][yy]<<"asd"<<xx<<" "<<yy<<endl;
        xx=xx+dx[zt];
        yy=yy+dy[zt];
        while(xx==bj[zt].first&&yy==bj[zt].second)
        {     bj[zt].first-=dx[zt]-dx[(zt+1)%4];
              bj[zt].second-=dy[zt]-dy[(zt+1)%4];
              //cout<<zt<<"asdaaaaaaaaaaaa"<<bj[zt].first<<" "<<bj[zt].second<<endl;
            zt=(zt+1)%4;

        }

    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            cout<<a[i][j]<<" ";

        cout<<endl;
    }

}


活动打卡代码 AcWing 104. 货仓选址

c_56
9天前
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N];
int ans;
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)ans+=abs(a[i]-a[1+n>>1]);
    cout<<ans<<endl;
}


活动打卡代码 AcWing 898. 数字三角形

c_56
9天前
#include<iostream>
using namespace std;
const int N=510;
int f[N][N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)cin>>f[i][j];
    for(int i=n;i>=1;i--)
        for(int j=1;j<=i;j++)
        {
            f[i][j]+=max(f[i+1][j],f[i+1][j+1]);
        }
    cout<<f[1][1]<<endl;
}


活动打卡代码 AcWing 898. 数字三角形

c_56
9天前

不等式 写公式

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N];
int ans;
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)ans+=abs(a[i]-a[1+n>>1]);
    cout<<ans<<endl;
}


分享 寒假一题

c_56
11天前

还有人和我拼团吗!!!!
AcWing《寒假每日一题》拼团优惠!https://www.acwing.com/activity/content/introduction/37/group_buy/4752/



活动打卡代码 AcWing 238. 银河英雄传说

c_56
1个月前

这里再复习一下并查集的知识点
1、find+路径压缩操作
2、size类,根节点维护其整个类的信息
3、d类,维护节点和其父节点的信息。类似军队维护上下级关系,避免了n^2个关系对

#include<iostream>
using namespace std;
const int N=30010;
int m;
int f[N],Size[N],d[N];

int find(int x)
{
    if(x==f[x])return x;
    int root=find(f[x]);
    d[x]+=d[f[x]];
    return f[x]=root;
}
int main()
{
    int t;
    cin>>t;
    for(int i=1;i<N;i++)
    {
        f[i]=i;
        Size[i]=1;
    }
    while(t--)
    {
        char op;
        int a,b;
        cin>>op>>a>>b;
        if(op=='M')
        {
            int fa=find(a);
            int fb=find(b);
            d[fa]=Size[fb];
            Size[fb]+=Size[fa];
            f[fa]=fb;
        }
        else
        {
            int fa=find(a);
            int fb=find(b);
            if(fa!=fb)puts("-1");
            else cout<<max(0,abs(d[a]-d[b])-1)<<endl;
        }
    }
}