首页 > 代码库 > NOIP模拟2017.6.11解题报告

NOIP模拟2017.6.11解题报告

T1:

  水题;

 

代码:

#include <cstdio>#include <iostream>#include <algorithm>using namespace std;#define maxn 100005int n,ai[maxn],Max[maxn],bi[maxn],size;int tree[maxn];inline void in(int &now){    char Cget=getchar();now=0;    while(Cget>9||Cget<0) Cget=getchar();    while(Cget>=0&&Cget<=9)    {        now=now*10+Cget-0;        Cget=getchar();    }}inline void add(int x){    while(x<=n) tree[x]++,x+=x&(-x);}inline bool judge(int l,int r){    int res=0;l--;    while(r) res+=tree[r],r-=r&(-r);    while(l) res-=tree[l],l-=l&(-l);    return res;}int lower_bound(int x){    int l=1,r=size,mid;    while(l<=r)    {        mid=l+r>>1;        if(bi[mid]==x) return mid;        if(bi[mid]<x) l=mid+1;        else r=mid-1;    }}int main(){    freopen("disk.in","r",stdin);    freopen("disk.out","w",stdout);    while(scanf("%d",&n)!=EOF)    {        for(int i=1;i<=n;i++) in(ai[n-i+1]),bi[i]=ai[n-i+1],tree[i]=0;        sort(bi+1,bi+n+1),size=unique(bi+1,bi+n+1)-bi-1;        for(int i=1;i<=n;i++) ai[i]=lower_bound(ai[i]);        Max[n+1]=0;        for(int i=n;i>0;i--) Max[i]=max(Max[i+1],ai[i]);        bool ans=true;        add(ai[1]);        for(int i=2;i<n;i++)        {            if(ai[i]+1<Max[i+1])            {                if(judge(ai[i]+1,Max[i+1]))                {                    ans=false;                    break;                }            }            add(ai[i]);        }        if(ans) puts("Y");        else puts("J");    }    return 0;}

 

T2:

  样例不过却ac,我也很无奈啊~~

 

 

代码:

#include <cstdio>#include <iostream>#include <algorithm>using namespace std;#define maxn 1005int x[maxn],y[maxn],bi[maxn<<1],size,n,cnt;int num[maxn<<1][maxn<<1],ans=0;inline void in(int &now){    int if_z=1;now=0;    char Cget=getchar();    while(Cget>9||Cget<0)    {        if(Cget==-)if_z=-1;        Cget=getchar();    }    while(Cget>=0&&Cget<=9)    {        now=now*10+Cget-0;        Cget=getchar();    }    now*=if_z;}int dge(int xx,int yy){    int xx_=lower_bound(bi+1,bi+size+1,xx)-bi;    int yy_=lower_bound(bi+1,bi+size+1,yy)-bi;    if(bi[xx_]==xx&&yy==bi[yy_]) return num[xx_][yy_];    return 0;}inline void Count(int a,int b){    int xa=x[a],ya=y[a],xb=x[b],yb=y[b];    num[xa][ya]--,num[xb][yb]--;    if(xa>xb) swap(xa,xb),swap(ya,yb);    int dx=bi[xb]-bi[xa],dy=bi[yb]-bi[ya];    int xxa,yya,xxb,yyb;    xxa=bi[xa]+dy,yya=bi[ya]-dx;    xxb=bi[xb]-dy,yyb=bi[yb]-dx;    if(xxa!=xxb||yya!=yyb) ans+=dge(xxa,yya)*dge(xxb,yyb);    else ans+=dge(xxa,yya)*(dge(xxb,yyb)-1);    xxa=bi[xa]-dy,yya=bi[ya]+dx;    xxb=bi[xb]+dy,yyb=bi[yb]+dx;    if(xxa!=xxb||yya!=yyb) ans+=dge(xxa,yya)*dge(xxb,yyb);    else ans+=dge(xxa,yya)*(dge(xxb,yyb)-1);    num[xa][ya]++,num[xb][yb]++;}int main(){    freopen("car.in","r",stdin);    freopen("car.out","w",stdout);    in(n);    for(int i=1;i<=n;i++)    {        in(x[i]),in(y[i]);        bi[++cnt]=x[i],bi[++cnt]=y[i];    }    sort(bi+1,bi+cnt+1),size=unique(bi+1,bi+cnt+1)-bi-1;    for(int i=1;i<=n;i++)    {        x[i]=lower_bound(bi+1,bi+size+1,x[i])-bi;        y[i]=lower_bound(bi+1,bi+size+1,y[i])-bi;        num[x[i]][y[i]]++;    }    for(int i=1;i<=n;i++)    {        for(int v=i+1;v<=n;v++)        {            if(v==i) continue;            Count(i,v);        }    }    cout<<ans/2;    return 0;}

 

 

T3:

  坑爹!!!!

 

代码:

#include <cstdio>#include <iostream>#include <algorithm>using namespace std;#define maxn 30005#define ll long longll n,ai[maxn],bi[maxn],size,root[maxn],tot;ll lc[maxn*30],rc[maxn*30],dis[maxn*30],m;inline void in(ll &now){    char Cget=getchar();now=0;    while(Cget>9||Cget<0)Cget=getchar();    while(Cget>=0&&Cget<=9)    {        now=now*10+Cget-0;        Cget=getchar();    }}void build(ll &now,ll l,ll r){    now=++tot;    if(l==r) return;    ll mid=l+r>>1;    build(lc[now],l,mid);    build(rc[now],mid+1,r);}void add(ll &now,ll pre,ll l,ll r,ll to){    now=++tot;dis[now]=dis[pre]+1;    if(l==r) return;ll mid=l+r>>1;    if(to<=mid) add(lc[now],lc[pre],l,mid,to),rc[now]=rc[pre];    else add(rc[now],rc[pre],mid+1,r,to),lc[now]=lc[pre];}ll query(ll now,ll l,ll r,ll k){    if(l==r) return l;    ll mid=l+r>>1;    if(k<=dis[lc[now]]) return query(lc[now],l,mid,k);    else return query(rc[now],mid+1,r,k-dis[lc[now]]);}int main(){    freopen("rollcall.in","r",stdin);    freopen("rollcall.out","w",stdout);    in(n),in(m);    for(ll i=1;i<=n;i++) in(ai[i]),bi[i]=ai[i];    sort(bi+1,bi+n+1),size=unique(bi+1,bi+n+1)-bi-1;    for(ll i=1;i<=n;i++) ai[i]=lower_bound(bi+1,bi+size+1,ai[i])-bi;    build(root[0],1,size);    for(ll i=1;i<=n;i++) add(root[i],root[i-1],1,size,ai[i]);    ll pos;    for(ll i=1;i<=m;i++) in(pos),printf("%I64d\n",bi[query(root[pos],1,size,i)]);    return 0;}

 

NOIP模拟2017.6.11解题报告