清北刷题冲刺 11-03 a.m

纸牌

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define maxn 300010

int n,a[maxn],b[maxn],w[maxn],num,h[maxn],cnt;

int qread(){

    int i=;

    char ch=getchar();

    while(ch<''||ch>'')ch=getchar();

    while(ch<=''&&ch>='')i=i*+ch-'',ch=getchar();

    return i;

}

struct node{

    int x,y;

}q[maxn];

int find(int x){

    int l=,r=cnt,res;

    while(l<=r){

        int mid=(l+r)>>;

        if(h[mid]<=x)res=mid,l=mid+;

        else r=mid-;

    }

    return res;

}

bool cmp(node u,node v){return u.x>v.x;}

int main(){

    freopen("card.in","r",stdin);freopen("card.out","w",stdout);

//    freopen("Cola.txt","r",stdin);

    n=qread();

    int limit=(n+)/;

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

        scanf("%d%d",&a[i],&b[i]);

        w[++num]=a[i];

        w[++num]=b[i];

    }

    sort(w+,w+num+);

    h[++cnt]=w[];

    for(int i=;i<=num;i++)

        if(w[i]!=w[i-])h[++cnt]=w[i];

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

        int pos1=find(a[i]);

        int pos2=find(b[i]);

        q[pos1].x++;

        q[pos2].y++;

    }

    sort(q+,q+cnt+,cmp);

    int ans=;

    for(int i=;i<=cnt;i++){

        if(q[i].x+q[i].y<limit)continue;

        else {

            ans=max(,limit-q[i].x);

            printf("%d",ans);

            return ;

        }

    }

    puts("Impossible");

    return ;

}

40分 忘了纸牌正反相同的情况

后缀数组

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 50010

using namespace std;

int n,m,tr[maxn<<],cnt,b[maxn];

string ss;

struct node{

    int id,rank;

    string s;

}a[maxn];

bool cmp(node x,node y){return x.s<y.s;}

bool cmp1(node x,node y){return x.id<y.id;}

int query(int pos){

    int res=;

    while(pos){

        res+=tr[pos];

        pos-=pos&-pos;

    }

    return res;

}

void add(int pos){

    while(pos<=n){

        tr[pos]+=;

        pos+=pos&-pos;

    }

}

int main(){

//    freopen("sort.in","r",stdin);freopen("sort.out","w",stdout);

//    freopen("Cola.txt","r",stdin);

    scanf("%d%d",&n,&m);

    cin>>ss;

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

        a[i].s=ss.substr(i-,min(m,n-i+));

        a[i].id=i;

    }

    sort(a+,a+n+,cmp);

    a[].rank=++cnt;

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

        if(a[i].s!=a[i-].s)

            a[i].rank=++cnt;

        else a[i].rank=a[i-].rank;

    }

    sort(a+,a+n+,cmp1);

    long long ans=;

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

        ans+=query(n)-query(a[i].rank);

        add(a[i].rank);

    }

    cout<<ans;

}

30分 树状数组，忘了字符串相等的情况

巧克力

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 11

using namespace std;

int T,n,m,k,w[maxn][maxn],a[],p[],cnt,b[],c[];

int qian[maxn];

bool flag,vis[];//是否wij=1；

int work1(){

    for(int i=;i<=k;i++){

        for(int j=;j<=cnt;j++){

            while(a[i]%p[j]==)a[i]/=p[j];

            if(p[j]>n&&p[j]>m)return ;

            if(a[i]==)break;

        }

    }

    return ;

}

void prepare(){

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

        if(!vis[i])vis[i]=,p[++cnt]=i;

        for(int j=;j<=cnt&&i*p[j]<=;j++){

            vis[i*p[j]]=;

            if(i%p[j]==)break;

        }

    }

}

int count(int sta){

    int res=;

    while(sta){

        if(sta&)res++;

        sta>>=;

    }

    return res;

}

int main(){

    freopen("chocolate.in","r",stdin);freopen("chocolate.out","w",stdout);

//    freopen("Cola.txt","r",stdin);

    scanf("%d",&T);

    prepare();

    while(T--){

        scanf("%d%d%d",&n,&m,&k);

        flag=;

        int sum=;

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

            for(int j=;j<=m;j++){

                scanf("%d",&w[i][j]);

                if(w[i][j]!=)flag=;

                sum+=w[i][j];

            }

        int s=;

        for(int i=;i<=k;i++){

            scanf("%d",&a[i]);

            s+=a[i];

        }

        sort(a+,a+k+);

        if(s!=sum){

            puts("no");

            continue;

        }

        if(flag){

            int ans=work1();

            if(ans==)puts("no");

            else puts("yes");

            continue;

        }

        if(n==){

            bool ok=;

            for(int i=;i<=m;i++)qian[i]=qian[i-]+w[][i];

            for(int sta=;sta<(<<m-);sta++){

                if(count(sta)!=k-)continue;

                int now=sta,pos=;

                int tmp=;

                while(now){

                    pos++;

                    if(now&)b[++tmp]=pos;

                    now>>=;

                }

                c[]=qian[b[]];

                for(int j=;j<=tmp;j++){

                    c[j]=qian[b[j]]-qian[b[j-]];

                }

                c[k]=qian[m]-qian[b[k-]];

                sort(c+,c+k+);

                bool f=;

                for(int j=;j<=k;j++){

                    if(c[j]!=a[j])f=;

                }

                if(f==){

                    puts("yes");

                    ok=;

                    break;

                }

            }

            if(ok==)puts("no");

            continue;

        }

        puts("yes");

    }

}

20分 暴力

预计得分100++

实际得分40++

今天的题有很多坑，T1T2都掉坑里了，T3骗分策略有误

这次考试出了很多失误，以后一定要把情况考虑全面

小结