CCPC2018-湖南全国邀请赛

时间:2022-09-10 16:28:04

solved 6 

rank 3

 

打了仨小时溜了。。

 

A

题意:S为满足区间中有大于等于x个大于等于x的数x的集合,h为S中最大的数。

给出数列,ai表示有ai个值为i的数,求h

 

做后缀和,从后向前扫,如果i位置的后缀和大于等于i,h即为i。(定义有点难懂,看BC题有助于理解)

CCPC2018-湖南全国邀请赛CCPC2018-湖南全国邀请赛
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define ll long long

const int N=2e5+7;

ll a[N];


int main(){
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n){
        for(int i=0;i<=n;i++)cin>>a[i];
        for(int i=n-1;i>=0;i--)a[i]+=a[i+1];
        for(int i=n;i>=0;i--){
            if(a[i]>=i){
                cout<<i<<'\n';
                break;
            }
        }
    }
} 
View Code

 

00:09(1A)

 

B

题意:找规律

 

(a+n)/2(因为有人一分钟A了,看样例猜规律就过了)

CCPC2018-湖南全国邀请赛CCPC2018-湖南全国邀请赛
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define ll long long

const int N=1e3+7;


int main(){
    ios::sync_with_stdio(false);
    ll a,n;
    while(cin>>n>>a){
        cout<<(n+a)/2<<'\n';
    }
} 
View Code

01:14(1A)

 

C

题意:给出数列,多次询问区间[l,r]的h。

 

h显然有单调性,考虑二分。对于当前答案h,如果有h个大于等于h个数就行,直接主席树。

(第一次用读入优化的板子莫名其妙T了。。)

CCPC2018-湖南全国邀请赛CCPC2018-湖南全国邀请赛
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define ll long long

const int N=2e5+7;
const int M=2e7+7;

int a[N],n,m,tot,q;

int t[N],c[M],T[N],lson[M],rson[M];

void init_hash(){
    rep(i,n)t[i]=a[i];
    sort(t+1,t+1+n);
    m=unique(t+1,t+1+n)-t-1;
}

int build(int l,int r){
    int root=tot++;
    c[root]=0;
    if(l!=r){
        int mid=(l+r)>>1;
        lson[root]=build(l,mid);
        rson[root]=build(mid+1,r);
    }
    return root;
}

int _hash(int x){
    return lower_bound(t+1,t+1+m,x)-t;
}

int update(int root,int pos,int val){
    int newroot=tot++,tmp=newroot;
    c[newroot]=c[root]+val;
    int l=1,r=m;
    while(l<r){
        int mid=(l+r)>>1;
        if(pos<=mid){
            lson[newroot]=tot++;rson[newroot]=rson[root];
            newroot=lson[newroot];root=lson[root];
            r=mid;
        }
        else {
            rson[newroot]=tot++;lson[newroot]=lson[root];
            newroot=rson[newroot];root=rson[root];
            l=mid+1;
        }
        c[newroot]=c[root]+val;
    }
    return tmp;
}

int query(int lroot,int rroot,int k){
    int l=1,r=m;
    while(l<r){
        int mid=(l+r)>>1;
        if(c[lson[lroot]]-c[lson[rroot]]>=k){
            r=mid;
            lroot=lson[lroot];
            rroot=lson[rroot];
        }
        else {
            l=mid+1;
            k-=c[lson[lroot]]-c[lson[rroot]];
            lroot=rson[lroot];
            rroot=rson[rroot];
        }
    }
    return l;
} 

int main(){
    while(scanf("%d%d",&n,&q)==2){
        tot=0;
        rep(i,n)scanf("%d",&a[i]);
        init_hash();
        T[n+1]=build(1,m);
        for(int i=n;i;i--){
            int pos=_hash(a[i]);
            T[i]=update(T[i+1],pos,1);
        }
        while(q--){
            int l,r;
            scanf("%d%d",&l,&r);
            int L=1,R=r-l+1,ans;
            while(L<=R){
                int mid=(L+R)>>1;
                //cout<<query(T[l],T[r+1],mid)<<'\n';
                if(t[query(T[l],T[r+1],r-l+2-mid)]>=mid){
                    ans=mid;
                    L=mid+1;
                }
                else R=mid-1;
            }
            printf("%d\n",ans);
        }
    }
} 
View Code

02:03(4A)

 

D

unsolved

 

E

unsolved

 

F

题意:给出若干个三元组(a,b,c),按照(a+b)/(a+b+c)排序

 

不能直接排序,会卡精度。移项除变乘sort就行,但需要再化简一下,否则会爆long long。

CCPC2018-湖南全国邀请赛CCPC2018-湖南全国邀请赛
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define ll long long

const int N=1e3+7;

struct node{
    long double a,b,c;
    int id;
};

node w[N];

int cmp(node x,node y){
    if((x.a+x.b)*y.c!=(y.a+y.b)*x.c)return (x.a+x.b)*y.c<(y.a+y.b)*x.c;
    return x.id<y.id;
}

int main(){
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n){
        rep(i,n)cin>>w[i].a>>w[i].b>>w[i].c,w[i].id=i;
        sort(w+1,w+1+n,cmp);
        rep(i,n){
            cout<<w[i].id;
            if(i!=n)cout<<" ";
        }
        cout<<'\n';
    }
} 
View Code

00:56(5A)

 

G

题意:给出两个只含abc的字符串S和T,可以删除或添加aa,bb,abab,问S是否可以变成T。

 

首先以c为间隔把两个字符串拆开,因为c不会改变,两个字符串拆分的结果应该数量相等且对应等价。然后考虑只含ab字符串的等价性。首先,通过前两种操作一定可以化成abababab这种,然后通过第三种操作,就只剩下空串,a,b,ab,ba,aba,bab这几种情况,观察到ab=aababb=ba,因此ab和ba也等价,显然aba和b等价,bab和a等价,那么只剩下空串,a,b,ab四种情况。因为所有操作都不改变a,b的奇偶性,所以只要a,b的奇偶性分别相同,就等价。

CCPC2018-湖南全国邀请赛CCPC2018-湖南全国邀请赛
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define ll long long

string s,t;

int equal(string a,string b,char c){
    int sa=0,sb=0;
    for(int i=0;i<a.size();i++)if(a[i]==c)sa++;
    for(int i=0;i<b.size();i++)if(b[i]==c)sb++;
    return (sa&1)==(sb&1);
}

int main(){
    while(cin>>s>>t){
        s+='c';
        t+='c';
        vector<string> a,b;
        string now;
        for(int i=0;i<s.size();i++){
            if(s[i]=='c'){
                a.push_back(now);
                now.clear();
            }
            else now+=s[i];
        } 
        
        for(int i=0;i<t.size();i++){
            if(t[i]=='c'){
                b.push_back(now);
                now.clear();
            }
            else now+=t[i];
        } 
        
        if(a.size()!=b.size()){
            cout<<"No"<<'\n';
            continue;
        }
        int f=0;
        for(int i=0;i<a.size();i++){
            string x=a[i],y=b[i];
            if(!equal(x,y,'a')||!equal(x,y,'b')){
                cout<<"No"<<'\n';
                f=1;
                break;
            }
        }
        if(!f){
            cout<<"Yes"<<'\n';
        }
    }
} 
View Code

02:47(1A)

 

H

unsolved

 

I

unsolved

 

J

unsolve

 

K

题意:x∈[a,b],y∈[c,d],有多少数对(x,y)满足x*y|2018。

 

2018=1009*2,容斥求一下方案就行。

CCPC2018-湖南全国邀请赛CCPC2018-湖南全国邀请赛
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define ll long long

const int N=2e5+7;


vector<int> v;

ll sum(int l,int r,int x){
    return r/x-(l-1)/x;
}


int main(){
    ios::sync_with_stdio(false);
    int a,b,c,d;
    while(cin>>a>>b>>c>>d){
        ll ans=0;
        ans+=sum(a,b,2018)*sum(c,d,1);
        ans+=(sum(a,b,1009)-sum(a,b,2018))*sum(c,d,2);
        ans+=(sum(a,b,2)-sum(a,b,2018))*sum(c,d,1009);
        ans+=(sum(a,b,1)-sum(a,b,1009)-sum(a,b,2)+sum(a,b,2018))*sum(c,d,2018); 
        cout<<ans<<'\n';
    }
} 
View Code

00:49(1A)