2019牛客国庆集训派对day2

时间：2020-12-19 14:55:53

A（模拟）:

#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;

const double eps = 1e-6;

const int N = 2e5+7;

typedef long long ll;

const ll mod = 1e9+7;

using namespace std;

int a[N];

ll suf[N];

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    int n;

    while(cin>>n){

        for(int i=0;i<=n;i++){

            cin>>a[i];

        }

        for(int i=n;i>=0;i--)

            suf[i]=suf[i+1]+a[i];

        int ans;

        for(int i=0;i<=n;i++){

            if(suf[i]>=i){

                ans=i;

            }

        }

        cout<<ans<<endl;

    }

}

B（思维）：

#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;

const double eps = 1e-6;

const int N = 2e5+7;

typedef long long ll;

const ll mod = 1e9+7;

using namespace std;

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    ll n;

    while(cin>>n){

        ll a; cin>>a;

        cout<<min(n,n%2==0?(n/2+a/2):(n/2+(a+1)/2))<<endl;

    }

}

C（可持久化线段树）：

#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;

const double eps = 1e-6;

const int N = 1e5+7;

typedef long long ll;

const ll mod = 1e9+7;

using namespace std;

struct tree{

    int l,r,v,ls,rs;

}t[N<<5];

ll a[N];

int rt[N];

int nico=0;

int cnt=0;

void build(int &p,int l,int r){

    p=++nico;

    t[p].l=l; t[p].r=r; t[p].v=0;

    if(l==r){

        return ;

    }

    int mid=(l+r)>>1;

    build(t[p].ls,l,mid);

    build(t[p].rs,mid+1,r);

    t[p].v=t[t[p].ls].v+t[t[p].rs].v;

}

void update(int &p,int last,int x,int v){

    p=++cnt;

    t[p]=t[last];

    if(t[p].l==t[p].r&&t[p].l==x){

        t[p].v+=v;

        return ;

    }

    int mid=(t[p].l+t[p].r)>>1;

    if(x<=mid) update(t[p].ls,t[last].ls,x,v);

    else update(t[p].rs,t[last].rs,x,v);

    t[p].v=t[t[p].ls].v+t[t[p].rs].v;

}

int query(int p,int last,int val){

    if(t[p].l==t[p].r){

        return t[p].l;

    }

    int mid=(t[p].l+t[p].r)>>1;

    int tt=t[t[p].rs].v-t[t[last].rs].v;

    if(tt+val<=mid) return query(t[p].ls,t[last].ls,tt+val);

    else return query(t[p].rs,t[last].rs,val);

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    int n,q;

    while(cin>>n>>q){

        build(rt[0],1,n+1);

        cnt=nico;

        for(int i=1;i<=n;i++){

            cin>>a[i];

            update(rt[i],rt[i-1],a[i],1);

        }

        for(int i=1;i<=q;i++){

            int l,r; cin>>l>>r;

            int ans=query(rt[r],rt[l-1],0);

            cout<<ans<<"\n";

        }

    }

}

F（排序）：

#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;

const double eps = 1e-6;

const int N = 1e3+7;

typedef long long ll;

const ll mod = 1e9+7;

using namespace std;

struct node{

    ll a,b,c;

    int id;

    friend bool operator < (node i,node j){

        if((__int128)(i.a+i.b)*(j.a+j.b+j.c)==(__int128)(j.a+j.b)*(i.a+i.b+i.c)) return i.id<j.id;

        return (__int128)(i.a+i.b)*(j.a+j.b+j.c)<(__int128)(j.a+j.b)*(i.a+i.b+i.c);

    }

}t[N];

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    int n;

    while(cin>>n){

        for(int i=0;i<n;i++){

            cin>>t[i].a>>t[i].b>>t[i].c;

            t[i].id=i+1;

        }

        sort(t,t+n);

        for(int i=0;i<n;i++){

            if(i==0) cout<<t[i].id;

            else cout<<" "<<t[i].id;

        }

        cout<<endl;

    }

}

G（思维题）：

#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;

const double eps = 1e-6;

const int N = 1e3+7;

typedef long long ll;

const ll mod = 1e9+7;

using namespace std;

vector<pair<int,int> > ss,tt;

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    string s,t;

    while(cin>>s>>t){

        ss.clear(); tt.clear();

        int lens=s.size();

        int lent=t.size();

        int cnt=0;

        for(int i=0;i<lens;i++){

            if(s[i]=='c') cnt++;

        }

        for(int i=0;i<lent;i++)

            if(t[i]=='c') cnt--;

        if(cnt!=0){

            cout<<"No"<<endl;

            continue;

        }

        int numa=0,numb=0;

        for(int i=0;i<=lens;i++){

            if(i==lens||s[i]=='c'){

                ss.push_back(make_pair(numa&1,numb&1));

                numa=0;

                numb=0;

            }else{

                if(s[i]=='a') numa++;

                else numb++;

            }

        }

        numa=0; numb=0;

        for(int i=0;i<=lent;i++){

            if(i==lent||t[i]=='c'){

                tt.push_back(make_pair(numa&1,numb&1));

                numa=0;

                numb=0;

            }else{

                if(t[i]=='a') numa++;

                else numb++;

            }

        }

        bool f=1;

        for(int i=0;i<ss.size();i++){

            if(ss[i].first==tt[i].first&&ss[i].second==tt[i].second){

            }else{

                f=0;

            }

        }

        if(!f){

            cout<<"No"<<endl;

        }else{

            cout<<"Yes"<<endl;

        }

    }

}

K（数学题）：

#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;

const double eps = 1e-6;

const int N = 2e5+7;

typedef long long ll;

typedef __int128 ull;

const ll mod = 1e9+7;

using namespace std;

ull work(ll a,ll b,ll num){

    return b/num-(a-1)/num;

}

void print(__int128 x)

{

    if (!x) return ;

    if (x < 0) putchar('-'),x = -x;

    print(x / 10);

    putchar(x % 10 + '0');

}

int main(){

//    ios::sync_with_stdio(false);

//    cin.tie(0); cout.tie(0);

    ll a,b,c,d;

    while(~scanf("%lld%lld%lld%lld",&a,&b,&c,&d)){

        ull x=b-a+1,y=d-c+1;

        ull num18=work(a,b,2018);

        ull num19=work(a,b,1009);

        ull num12=work(a,b,2);

        ull num28=work(c,d,2018);

        ull num29=work(c,d,1009);

        ull num22=work(c,d,2);

        print(num18*(y-num28)+num28*(x-num18)+num18*num28+(num12-num18)*(num29-num28)+(num22-num28)*(num19-num18));

        puts("");

    }

}

相关文章