首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >AtCoder Beginner Contest 185 (手速场)

AtCoder Beginner Contest 185 (手速场)

作者头像
dejavu1zz
发布2020-12-16 17:27:51
2920
发布2020-12-16 17:27:51
举报

题目列表

A

题意描述

题意描述
题意描述

思路

输出a , b , c , d的最小值即可。

AC代码

#include "iostream"
#include "cstring"
#include "string"
#include "vector"
#include "cmath"
#include "algorithm"
#include "map"
#include "set"
#include "queue"
#include "stack"
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int N=1010;
const int M=1<<19;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const lll oone=1;
const double eps=1e-6;
const double pi=acos(-1);
void solve(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int res=min(a,b);
    res=min(res,c);
    res=min(res,d);
    cout<<res<<endl;
}
int main(){
    IOS;
    //freopen("try.in", "r", stdin);
    //freopen("try2.out", "w", stdout);
    //int t;cin>>t;
    //while(t--)
    solve();
    return 0;
}

B

题意描述

题意描述
题意描述

思路

根据题意模拟过程。需要注意的一点是,在咖啡店充电时,电量不能超过充电宝的上限。

AC代码

#include "iostream"
#include "cstring"
#include "string"
#include "vector"
#include "cmath"
#include "algorithm"
#include "map"
#include "set"
#include "queue"
#include "stack"
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int N=1010;
const int M=1<<19;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const lll oone=1;
const double eps=1e-6;
const double pi=acos(-1);
void solve(){
    ll n,m,t;
    cin>>n>>m>>t;
    ll cur=n,last=0;
    bool ok=true;
    rep(i,0,m){
        ll a,b;
        cin>>a>>b;
        cur-=(a-last);
        if(cur<=0) ok=false;
        cur+=(b-a);
        if(cur>n) cur=n;
        last=b;
    }
    if(cur) cur-=(t-last);
    if(cur<=0) ok=false;
    cout<<(ok ? "Yes" :"No")<<endl;
}
int main(){
    IOS;
    //freopen("try.in", "r", stdin);
    //freopen("try2.out", "w", stdout);
    //int t;cin>>t;
    //while(t--)
    solve();
    return 0;
}

C

题意描述

题意描述
题意描述

思路

直接算C ( l − 1 , l − 12 )即可。由于题目中没有模数,偷懒使用了JAVA的大整数

AC代码

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int l = cin.nextInt();
        int u=l-1,d=l-12;
        BigInteger big = new BigInteger("1");
        for(int i=u;i>=u-d+1;i--){
            big = big.multiply(new BigInteger(String.valueOf(i)));
        }
        for (int i = 1; i <= d; i++) big = big.divide(new BigInteger(String.valueOf(i)));
        System.out.println(big.toString());
    }
}

D

题意描述

题意描述
题意描述

思路

找到两个蓝色邮票之间最少的白色邮票个数,然后从前到后模拟,算下个数即可。

AC代码

#include "iostream"
#include "cstring"
#include "string"
#include "vector"
#include "cmath"
#include "algorithm"
#include "map"
#include "set"
#include "queue"
#include "stack"
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int N=3*1e5+10;
const int M=1<<19;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const lll oone=1;
const double eps=1e-6;
const double pi=acos(-1);
int a[N];
void solve(){
    int n,m;
    cin>>n>>m;
    rep(i,1,m+1) cin>>a[i];
    if(!m){
        cout<<1<<endl;
        return;
    }
    if(n==m){
        cout<<0<<endl;
        return;
    }
    sort(a+1,a+m+1);
    int mn=INF;
    if(a[1]!=1) mn=min(mn,a[1]-1);
    if(a[m]!=n) mn=min(mn,n-a[m]);
    rep(i,2,m+1){
        if(a[i]-a[i-1]-1==0) continue;
        mn=min(mn,a[i]-a[i-1]-1);
    }
    int ans=0;
    rep(i,2,m+1){
        int gap=a[i]-a[i-1]-1;
        ans+=gap/mn+(gap%mn!=0);
    }
    ans+=(n-a[m])/mn+((n-a[m])%mn!=0);
    ans+=(a[1]-1)/mn+((a[1]-1)%mn!=0);
    cout<<ans<<endl;
}
int main(){
    IOS;
    //freopen("try.in", "r", stdin);
    //freopen("try2.out", "w", stdout);
    //int t;cin>>t;
    //while(t--)
    solve();
    return 0;
}

E

题意描述

题意描述
题意描述

AC代码

#include "iostream"
#include "cstring"
#include "string"
#include "vector"
#include "cmath"
#include "algorithm"
#include "map"
#include "set"
#include "queue"
#include "stack"
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define uni(x) sort(all(x)), x.erase(unique(all(x)), x.end())
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int N=1010;
const int M=1<<19;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const lll oone=1;
const double eps=1e-6;
const double pi=acos(-1);
int f[N][N];
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n+1,0),b(m+1,0);
    rep(i,1,n+1) cin>>a[i];
    rep(i,1,m+1) cin>>b[i];
    mst(f,INF);
    f[0][0]=0;
    rep(i,1,n+1) f[i][0]=i;
    rep(i,1,m+1) f[0][i]=i;
    rep(i,1,n+1){
        rep(j,1,m+1){
            if(a[i]==b[j]) f[i][j]=min(f[i][j],f[i-1][j-1]);
            f[i][j]=min(f[i][j],f[i-1][j]+1);
            f[i][j]=min(f[i][j],f[i][j-1]+1);
            f[i][j]=min(f[i][j],f[i-1][j-1]+1);
        }
    }
    cout<<f[n][m]<<endl;
}
int main(){
    IOS;
    //freopen("try.in", "r", stdin);
    //freopen("try2.out", "w", stdout);
    //int t;cin>>t;
    //while(t--)
    solve();
    return 0;
}

F

题意描述

题意描述
题意描述

思路

模板题,线段树或者树状数组都可以做

AC代码

#include "iostream"
#include "cstring"
#include "string"
#include "vector"
#include "cmath"
#include "algorithm"
#include "map"
#include "set"
#include "queue"
#include "stack"
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define seteps(N) setprecision(N)
#define lson (ind<<1)
#define rson (ind<<1|1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int N=3*1e5+10;
const int M=1<<19;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const lll oone=1;
const double eps=1e-6;
const double pi=acos(-1);
int a[N];
struct Node{
    int l,r,cur;
}node[N * 4];
struct SegTree{

    void push_up(int ind){
        node[ind].cur=node[lson].cur^node[rson].cur;
    }

    void push_down(int ind){

    }

    void build(int l,int r,int ind){
        node[ind].l=l;
        node[ind].r=r;
        if(l==r){
            node[ind].cur=a[l];
        }else{
            int mid=l+r>>1;
            build(l,mid,lson);
            build(mid+1,r,rson);
            push_up(ind);
        }
    }

    void update(int l,int r,int ind,int val){
        if(l>node[ind].r || r<node[ind].l) return;
        if(l<=node[ind].l && r>=node[ind].r){
            node[ind].cur^=val;
        }else{
            push_down(ind);
            update(l,r,lson,val);
            update(l,r,rson,val);
            push_up(ind);
        }
    }

    void query(int l,int r,int ind,ll &ans){
        if(l>node[ind].r || r<node[ind].l) return;
        if(l<=node[ind].l && node[ind].r<=r){
            ans^=node[ind].cur;
        }else{
            push_down(ind);
            query(l,r,lson,ans);
            query(l,r,rson,ans);
            push_up(ind);
        }
    }
};

void solve(){
    int n,q;
    cin>>n>>q;
    rep(i,1,n+1) cin>>a[i];
    SegTree seg;
    seg.build(1,n,1);
    while(q--){
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1){
            seg.update(x,x,1,y);
        }else{
            ll ans=0;
            seg.query(x,y,1,ans);
            cout<<ans<<endl;
        }
    }
}
int main(){
    IOS;
    //freopen("try.in", "r", stdin);
    //freopen("try2.out", "w", stdout);
    //int t;cin>>t;
    //while(t--)
    solve();
    return 0;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-12-14 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目列表
  • A
    • 题意描述
      • 思路
        • AC代码
        • B
          • 题意描述
            • 思路
              • AC代码
              • C
                • 题意描述
                  • 思路
                    • AC代码
                    • D
                      • 题意描述
                        • 思路
                          • AC代码
                          • E
                            • 题意描述
                              • AC代码
                              • F
                                • 题意描述
                                  • 思路
                                    • AC代码
                                    领券
                                    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档