AtCoder Beginner Contest 164题解

题目链接

A.Sheep and Wolves

题意:

题解:

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int s,w;
    cin>>s>>w;
    if(w>=s)cout<<"unsafe";
    else cout<<"safe";

    return 0;
}


B. Battle

题意:




题解:


AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int cnt=1;
    while(a>0&&c>0){
        if(cnt&1)c-=b;
        else a-=d;
        cnt^=1;
    }
    if(a<=0)cout<<"No";
    else cout<<"Yes";
    return 0;
}


C.gacha

题意:

题解:

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    set<string> s;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        string x;
        cin>>x;
        s.insert(x);
    }
    cout<<s.size();
    return 0;
}


D. Multiple of 2019

题意:



题解:





AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    string s;
    cin>>s;
    int p=2019;
    map<int,ll> m;
    m[0]++;
    ll ans=0,sum=0,d=1;
    for(int i=s.length()-1;i>=0;i--){
        sum=(sum+d*(s[i]-'0')%p)%p;
        ans+=m[sum];
        m[sum]++;
        d=(d*10)%p;
    }
    cout<<ans;
    return 0;
}


E.Two Currencies

题意:




题解:











AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

struct edge{
    int v,nx;
    ll a,b;
}e[210];
int head[60],cnt;
ll c[60],d[60];
ll dis[60][3000];
void add(int u,int v,ll a,ll b){
    e[++cnt].v=v;
    e[cnt].a=a;
    e[cnt].b=b;
    e[cnt].nx=head[u];
    head[u]=cnt;
}
struct node{
    int u;
    ll s,t;
    bool operator <(const node &x)const{
        return t>x.t;
    }
};
ll dis1[100];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n,m;
    ll s;
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v;
        ll a,b;
        cin>>u>>v>>a>>b;
        add(u,v,a,b);
        add(v,u,a,b);
    }
    for(int i=1;i<=n;i++)cin>>c[i]>>d[i];
    if(s>2500){
        for(int i=1;i<=n;i++)dis1[i]=inf*inf;
        dis1[1]=0;
        priority_queue<pii,vector<pii>,greater<pii> > q;
        q.push(mp(0,1));
        while(!q.empty()){
            pii p=q.top();
            q.pop();
            int u=p.se;
            if(dis1[u]<p.fi)continue;
            for(int i=head[u];i;i=e[i].nx){
                int v=e[i].v;
                if(dis1[v]>dis1[u]+e[i].b){
                    dis1[v]=dis1[u]+e[i].b;
                    q.push(mp(dis1[v],v));
                }
            }
        }
        for(int i=2;i<=n;i++)
            cout<<dis1[i]<<endl;
        return 0;
    }
    priority_queue<node> q;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=50*n;j++)
            dis[i][j]=1e18;
    dis[1][s]=0;
    q.push((node){1,s,0});
    while(!q.empty()){
        node p=q.top();
        q.pop();
        int u=p.u;
        if(p.t>dis[u][p.s])continue;
        for(int i=head[u];i;i=e[i].nx){
            int v=e[i].v;
            if(p.s>=e[i].a&&dis[v][p.s-e[i].a]>dis[u][p.s]+e[i].b){
                dis[v][p.s-e[i].a]=dis[u][p.s]+e[i].b;
                q.push((node){v,p.s-e[i].a,dis[u][p.s]+e[i].b});
            }
        }
        ll ts=min(p.s+c[u],50ll*n);
        if(dis[u][ts]>dis[u][p.s]+d[u]){
            dis[u][ts]=dis[u][p.s]+d[u];
            q.push((node){u,ts,dis[u][p.s]+d[u]});
        }
    }
    for(int i=2;i<=n;i++){
        ll ans=1e18;
        for(int j=0;j<=50*n;j++)
            ans=min(ans,dis[i][j]);
        cout<<ans<<endl;
    }
    return 0;
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
2024-12-30 18:02
程序员牛肉:1.可以标记一下自己的学校是985,有一些hr可能没想到你这个院校是985的。 2.简历所呈现出来的能力还是有点差的,苍穹外卖+黑马点评。这在java技术域里面也就是刚学三四个月的样子,大厂现在招人少,小厂又更加希望你能直接过来干活。就你简历上呈现出来的能力,确实是有点难找,肉眼可见的不懂技术。 第一个项目中:简单的使用redis也算是亮点嘛?使用jwt,threadlocal也算是亮点?你不就是调了几个包嘛?Nginx作为服务器也能写出来,这不是前端的活嘛? 第二个项目中:分布式锁+mq消息队列+Lua队列。真没啥好问的。属于面试官看一眼就阳痿的简历,没有任何想提问的欲望。 我给你建议是好好的挖一挖这个项目吧,其实苍穹外卖和黑马点评这两个项目很不错了,只不过是太烂大街了导致面试官没啥问的兴趣,所以不太推荐写简历上。
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

更多
牛客网
牛客企业服务