专栏首页奇妙的算法世界AtCoder Beginner Contest 185 （手速场）

AtCoder Beginner Contest 185 （手速场）

2020-12-162020-12-16 17:27:51阅读 950

题目列表

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;
}

本文参与腾讯云自媒体分享计划，欢迎正在阅读的你也加入，一起分享。

展开阅读全文

我来说两句

0 条评论

登录后参与评论

codeforces 1443B（思维）
dejavu1zz
codeforces 1419C（贪心）
dejavu1zz
codeforces 1296D（贪心）
有n个怪物，a和b轮流对怪物造成a和b伤害，有k次超能力，超能力可以跳过对方的回合，如果a击败了怪物，则a获得一分，反之亦然。求a能够获得的最大点数
dejavu1zz
codeforces 1005D（数学）
我们发现，如果连续三位的数都不能被3整除，那么这三位加起来一定可以被整除。所以我们遍历一遍即可。
dejavu1zz
codeforces 1296D（贪心）
有n个怪物，a和b轮流对怪物造成a和b伤害，有k次超能力，超能力可以跳过对方的回合，如果a击败了怪物，则a获得一分，反之亦然。求a能够获得的最大点数
dejavu1zz
C程序之修改Windows的控制台大小
//change the console size #include <stdio.h> #include<stdlib.h> //必须有 int main(...
互联网金融打杂
codeforces 1384A（构造）
The length of the longest common prefix of two strings s=s1s2…sn and t=t1t2…tm i...
dejavu1zz
cf1042F. Leaf Sets(贪心)
考场上想的贪心是对的：考虑一棵子树，如果该子树内最深的两个节点的距离相加$>k$就删掉最深的那个点，向上update的时候只返回最深的点的深度
attack
LightOj_1317 Throwing Balls into the Baskets
　　每个人进球数的期望为：E = sigma （i * C(K, i) * p ^ i * (1 - p) ^ (k - i)）;
若羽
Android实现多维商品属性SKU选择
最近又做到这一块的需求，以前也做过类似仿淘宝的属性选择，当时在网上下载的demo参考，最多也支持两组商品属性，用的两个gridview结合，扩展性很差，这次不打...
砸漏

腾讯云·社区

dejavu1zz

AtCoder Beginner Contest 185 （手速场）

AtCoder Beginner Contest 185 （手速场）

题目列表

A

题意描述

思路

AC代码

B

题意描述

思路

AC代码

C

题意描述

思路

AC代码

D

题意描述

思路

AC代码

E

题意描述

AC代码

F

题意描述

思路

AC代码

codeforces 1443B（思维）

codeforces 1419C（贪心）

codeforces 1296D（贪心）

codeforces 1005D（数学）

codeforces 1296D（贪心）

C程序之修改Windows的控制台大小

codeforces 1384A（构造）

cf1042F. Leaf Sets(贪心)

LightOj_1317 Throwing Balls into the Baskets

Android实现多维商品属性SKU选择

dejavu1zz

云计算新趋势

2020 年度创作者报告请查收！

腾讯云自媒体分享计划

目录

社区

活动

资源

关于

归档

云+社区

热门产品

热门推荐

更多推荐