T1：
水题；
代码：
#include <cstdio> #include <iostream> #include <algorithm> using namespace std; #define maxn 100005 int 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 1005 int 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 long ll 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 ",bi[query(root[pos],1,size,i)]); return 0; }