首页 > 代码库 > 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解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。