纸牌
#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=0; char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch<='9'&&ch>='0')i=i*10+ch-'0',ch=getchar(); return i; } struct node{ int x,y; }q[maxn]; int find(int x){ int l=1,r=cnt,res; while(l<=r){ int mid=(l+r)>>1; if(h[mid]<=x)res=mid,l=mid+1; else r=mid-1; } 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+1)/2; for(int i=1;i<=n;i++){ scanf("%d%d",&a[i],&b[i]); w[++num]=a[i]; w[++num]=b[i]; } sort(w+1,w+num+1); h[++cnt]=w[1]; for(int i=2;i<=num;i++) if(w[i]!=w[i-1])h[++cnt]=w[i]; for(int i=1;i<=n;i++){ int pos1=find(a[i]); int pos2=find(b[i]); q[pos1].x++; q[pos2].y++; } sort(q+1,q+cnt+1,cmp); int ans=100000000; for(int i=1;i<=cnt;i++){ if(q[i].x+q[i].y<limit)continue; else { ans=max(0,limit-q[i].x); printf("%d",ans); return 0; } } puts("Impossible"); return 0; }
后缀数组
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 50010 using namespace std; int n,m,tr[maxn<<4],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=0; while(pos){ res+=tr[pos]; pos-=pos&-pos; } return res; } void add(int pos){ while(pos<=n){ tr[pos]+=1; 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=1;i<=n;i++){ a[i].s=ss.substr(i-1,min(m,n-i+1)); a[i].id=i; } sort(a+1,a+n+1,cmp); a[1].rank=++cnt; for(int i=2;i<=n;i++){ if(a[i].s!=a[i-1].s) a[i].rank=++cnt; else a[i].rank=a[i-1].rank; } sort(a+1,a+n+1,cmp1); long long ans=0; for(int i=1;i<=n;i++){ ans+=query(n)-query(a[i].rank); add(a[i].rank); } cout<<ans; }
巧克力
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 11 using namespace std; int T,n,m,k,w[maxn][maxn],a[20],p[1000],cnt,b[20],c[20]; int qian[maxn]; bool flag,vis[1001];//是否wij=1； int work1(){ for(int i=1;i<=k;i++){ for(int j=1;j<=cnt;j++){ while(a[i]%p[j]==0)a[i]/=p[j]; if(p[j]>n&&p[j]>m)return 0; if(a[i]==1)break; } } return 1; } void prepare(){ for(int i=2;i<=1000;i++){ if(!vis[i])vis[i]=1,p[++cnt]=i; for(int j=1;j<=cnt&&i*p[j]<=1000;j++){ vis[i*p[j]]=1; if(i%p[j]==0)break; } } } int count(int sta){ int res=0; while(sta){ if(sta&1)res++; sta>>=1; } 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=1; int sum=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ scanf("%d",&w[i][j]); if(w[i][j]!=1)flag=0; sum+=w[i][j]; } int s=0; for(int i=1;i<=k;i++){ scanf("%d",&a[i]); s+=a[i]; } sort(a+1,a+k+1); if(s!=sum){ puts("no"); continue; } if(flag){ int ans=work1(); if(ans==0)puts("no"); else puts("yes"); continue; } if(n==1){ bool ok=0; for(int i=1;i<=m;i++)qian[i]=qian[i-1]+w[1][i]; for(int sta=0;sta<(1<<m-1);sta++){ if(count(sta)!=k-1)continue; int now=sta,pos=0; int tmp=0; while(now){ pos++; if(now&1)b[++tmp]=pos; now>>=1; } c[1]=qian[b[1]]; for(int j=2;j<=tmp;j++){ c[j]=qian[b[j]]-qian[b[j-1]]; } c[k]=qian[m]-qian[b[k-1]]; sort(c+1,c+k+1); bool f=0; for(int j=1;j<=k;j++){ if(c[j]!=a[j])f=1; } if(f==0){ puts("yes"); ok=1; break; } } if(ok==0)puts("no"); continue; } puts("yes"); } }
预计得分100+80+50 实际得分40+30+20 今天的题有很多坑，T1T2都掉坑里了，T3骗分策略有误 这次考试出了很多失误，以后一定要把情况考虑全面