头像

重柔道人

慢慢仙途




离线:2个月前


最近来访(13)
用户头像
zombotany
用户头像
zqc
用户头像
阿满


重柔道人
5个月前

bfs

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1010;
typedef pair<int,int> PII;
#define x first
#define y second
int n,m;
char g[N][N];
bool st[N][N];
int cnt;
int bfs(int sx,int sy)
{
    queue<PII> q;
    q.push({sx,sy});
    int dx[]={-1,0,1,0,-1,-1,1,1},dy[]={0,-1,0,1,-1,1,-1,1};
    st[sx][sy]=true;
    cnt++;
    while(!q.empty())
    {
        PII t=q.front();
        q.pop();
        for(int i=0;i<8;i++)
        {
            int x=t.x+dx[i],y=t.y+dy[i];
            if(x>=0 && x<n && y>=0 && y<m && !st[x][y] && g[x][y]=='W') 
            {
                q.push({x,y});
                st[x][y]=true;
            }
        }   
    }   

}
int main()
{

    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) scanf("%s",g[i]);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(g[i][j]=='W' && !st[i][j])
            {
                bfs(i,j);

            }

        }
    }
    printf("%d",cnt);

 } 




重柔道人
5个月前

解释y总de代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010;
typedef pair<int,int> PII;
int f[N];//表示店铺的优先级
int st[N];//判断店铺是否在有优先缓存中
int last[N];//last[i] 表示店铺i上一次有订单的时刻
PII order[N];//订单 


//同一批订单表示时刻和id都相同的外卖,
//由于进行了排序,所以同一时刻的所有订单是连续排列的 
int main()
{

    int n,m,T;
    scanf("%d%d%d",&n,&m,&T);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&order[i].first,&order[i].second);

    }
    sort(order,order+m);
    for(int i=0;i<m;)
    {
        int j=i;
        while(order[i]==order[j] && j<m) j++;//循环寻找同一批订单最后一个的位置 
        int t=order[i].first,id=order[i].second,cnt=j-i;//cnt表示同一批订单的外卖数量 
        i=j;
        f[id]-=t-last[id]-1;//时刻5   -- 时刻  7   中间只有一个数6 7-5-1=1
        if(f[id]<0) f[id]=0;
        if(f[id]<=3) st[id]=0;//把t时刻之前的处理完,然后就可以算t时刻的订单了 
        f[id] +=cnt*2;
        if(f[id]>5) st[id]=1;

        last[id]=t;//下个时刻减去这个时刻再减1就是优先级该减去的数目 
    }
    for(int i=1;i<=n;i++)
    {
        if(last[i]<T)
        {
            f[i]-=T-last[i];
            if(f[i]<=3) st[i]=0;
        }
     } 
     int ans=0;
     for(int i=1;i<=n;i++) ans+=st[i];
     cout <<ans << endl;
     return 0;
}




活动打卡代码 AcWing 1241. 外卖店优先级

重柔道人
5个月前
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010;
typedef pair<int,int> PII;
int f[N];//表示店铺的优先级
int st[N];//判断店铺是否在有优先缓存中
int last[N];//last[i] 表示店铺i上一次有订单的时刻
PII order[N];//订单 


//同一批订单表示时刻和id都相同的外卖,
//由于进行了排序,所以同一时刻的所有订单是连续排列的 
int main()
{

    int n,m,T;
    scanf("%d%d%d",&n,&m,&T);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&order[i].first,&order[i].second);

    }
    sort(order,order+m);
    for(int i=0;i<m;)
    {
        int j=i;
        while(order[i]==order[j] && j<m) j++;//循环寻找同一批订单最后一个的位置 
        int t=order[i].first,id=order[i].second,cnt=j-i;//cnt表示同一批订单的外卖数量 
        i=j;
        f[id]-=t-last[id]-1;//时刻5   -- 时刻  7   中间只有一个数6 7-5-1=1
        if(f[id]<0) f[id]=0;
        if(f[id]<=3) st[id]=0;//把t时刻之前的处理完,然后就可以算t时刻的订单了 
        f[id] +=cnt*2;
        if(f[id]>5) st[id]=1;

        last[id]=t;//下个时刻减去这个时刻再减1就是优先级该减去的数目 
    }
    for(int i=1;i<=n;i++)
    {
        if(last[i]<T)
        {
            f[i]-=T-last[i];
            if(f[i]<=3) st[i]=0;
        }
     } 
     int ans=0;
     for(int i=1;i<=n;i++) ans+=st[i];
     cout <<ans << endl;
     return 0;
}


活动打卡代码 AcWing 1231. 航班时间

重柔道人
5个月前
#include<iostream>
using namespace std;
int getTime(void)
{
    int h1,m1,s1,h2,m2,s2,d=0;
    scanf("%d:%d:%d %d:%d:%d (+%d)",&h1,&m1,&s1,&h2,&m2,&s2,&d);
    int time=d*24*3600+h2*3600+m2*60+s2-(h1*3600+m1*60+s1);
    return time;

}
int main()
{
    int t;
    scanf("%d",&t);
    for(int i=0;i<t;i++)
    {
        int time1=getTime();
        int time2=getTime();
        int t=(time1+time2)/2;
        printf("%02d:%02d:%02d\n",t/3600,t%3600/60,t%60);
    }
}


活动打卡代码 AcWing 1245. 特别数的和

重柔道人
5个月前
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        int t=i;

        while(t)
        {

            int s=t%10;
            t=t/10;
            if(s==1 || s==2 || s==9 ||s==0)
            {
                sum+=i;
                break;
            }
        }
    }
    cout << sum;
}



活动打卡代码 AcWing 466. 回文日期

重柔道人
5个月前
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int months[13]={0,31,28,31,30,31,30,3131,30,31,30,31};
bool check(int date)
{
    int year=date/10000;
    int month=date%10000/100;
    int day=date%100;
    if(month<0||month>12 || !day) return false;
    if(month!=2 && day>months[month]) return false;
    if(month==2)
    {
        bool leap=year%4==0 && year %100!=0 || year % 400==0;
        if(day>28+leap) return false;
    }
    return true;
}
int main()
{
    int date1,date2,date;
    cin >> date1 >> date2;
    int res=0;
    for(int i=0;i<10000;i++)
    {
        int x=i,r=i;
        for(int j=0;j<4;j++) r=r*10+r%10,r/=10;
        if(r>=date1 && r<=date2 && check(r)) res++;

    }
    printf("%d\n",res);
    return 0;

} 


活动打卡代码 AcWing 1229. 日期问题

重柔道人
5个月前
#include<iostream>
using namespace std;
int days[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check(int year,int month,int day)
{
    if(month>12|| !month || !day ) return false;
    if(month!=2 && day>days[month]) return false;
    if(month==2)
    {
        int leap=year%4==0 && year%100||year%400==0;
        if(day>28+leap) return false;

    }
    return true;

}
int main()
{
    int a,b,c;
    scanf("%d/%d/%d",&a,&b,&c);
    for(int date=19610101;date<=20591231;date++)
    {
        int year=date/10000,month=date%10000/100,day=date%100;

        if(check(year,month,day))
        {
            if(year%100==a && month==b && day==c || month==a && day==b && year%100==c||day==a && month == b &&year%100==c)
            {
                printf("%d-%02d-%02d\n",year,month,day);
            }

        }
    }
    return 0;
}


活动打卡代码 AcWing 1219. 移动距离

重柔道人
5个月前

曼哈顿距离

|x1-x2|+|y1-y2|

欧氏距离

2.png
1.png

红线是曼哈顿距离,绿线是欧氏距离
其他是等价曼哈顿距离

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int w,m,n;
    cin >> w>> m >>n;
    m--,n--;
    int x1=m/w,x2=n/w;
    int y1=m%w,y2=n%w;
    if(x1%2) y1=w-1-m%w;
    if(x2%2) y2=w-1-n%w;
    cout << abs(x1-x2)+abs(y1-y2) << endl;
    return 0;
}


活动打卡代码 AcWing 5. 多重背包问题 II

重柔道人
6个月前
#include<iostream>
using namespace std;
const int N=12010,M=2010;
int n,m;
int v[N],w[N],f[N];
int main()
{
    cin >> n >> m;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        int a,b,s;
        cin >>a >> b>>s;
        int k=1;
        while(k<=s)
        {
            cnt++;
            v[cnt] =a*k;
            w[cnt]=b*k;
            s-=k;
            k*=2;

        }
        if(s>0)
        {
            cnt++;
            v[cnt] =a*s;
            w[cnt]=b*s;

        }
    }
    n=cnt;
    for(int i=1;i<=n;i++)
        for(int j=m;j>=v[i];j--)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout <<f[m] <<endl;
    return 0; 
}


活动打卡代码 AcWing 2. 01背包问题

重柔道人
6个月前
#include<iostream>
using namespace std;
const int N=1010;
int v[N],w[N],f[N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&v[i],&w[i]);
    for(int i=1;i<=n;i++)
        for(int j=m;j>=v[i];j--)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout <<f[m] << endl;
    return 0;
}