前言
- 连第二机房房主也不是了，该高兴还是该呵呵？
- 板子不会还是硬伤，不会高斯消元的我看到T2都绝望了，YY还写错了……
- T3特判都打错，佛啦。
- 咳咳。还有为什么还是这么颓废。
- 还有%%%文化课巨佬FlashHu。
以上纯属CD。
T1
- 先把(a,b)按a单调下降排序，然后将不符合b单调上升的点删除，因为这些点不可能成为答案。
- 然后将给出的(a,b)抽象成$(\frac{1}{a},\frac{1}{b})$的点，因为a单调下降b单调上升所以新点集的横坐标单调上升纵坐标单调递减。
- 直接用栈维护左下凸包，栈内斜率单调递增即可。
- 时间复杂度$\Theta(NlogN)$，空间复杂度$\Theta(N)$。
- 本题精度稍GS，蒟蒻博主的垃圾代码开__float128才能AC……
#include<cstdio> #include<algorithm> #include<vector> #define ll long long #define db __float128 using namespace std; typedef pair<pair<int,int>,int> pi; int const N=3e5+5; db const lar=2e16,eps=-1e-6; int n,t; pi b[N]; pair<int,int>a[N]; vector<int>bs[N]; int ans[N]; int stk[N],tp; db xp[N],yp[N],xl[N]; inline int read(){ int ss(0);char bb(getchar()); while(bb<48||bb>57)bb=getchar(); while(bb>=48&&bb<=57)ss=(ss<<1)+(ss<<3)+(bb^48),bb=getchar(); return ss; } inline db _max(db x,db y){ return x>y?x:y; } inline db _min(db x,db y){ return x<y?x:y; } int main(){ //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); n=read(); for(register int i=1;i<=n;++i)b[i].first.first=read(),b[i].first.second=read(),b[i].second=i; sort(b+1,b+n+1,[](pi skyh,pi yxs){ return (skyh.first.first^yxs.first.first)?skyh.first.first>yxs.first.first:skyh.first.second>yxs.first.second; }); for(register int i=1;i<=n;++i) if(b[i].first.second>a[t].second)a[++t]=b[i].first,bs[t].push_back(b[i].second); else if(b[i].first.first==a[t].first && b[i].first.second==a[t].second)bs[t].push_back(b[i].second); n=t,t=0; for(register int i=1;i<=n;++i) xp[i]=1.0/(db)a[i].first,yp[i]=1.0/(db)a[i].second; for(register int i=1;i<=n;++i){ while(tp>1 && (yp[i]-yp[stk[tp]])/(xp[i]-xp[stk[tp]])<xl[tp])--tp; stk[++tp]=i,xl[tp]=(yp[i]-yp[stk[tp-1]])/(xp[i]-xp[stk[tp-1]]); } /*for(register int i=1;i<=n;++i){ db minx=lar,maxx=0; const db xn=xp[i],yn=yp[i]; for(register int j=1;j<i;++j) maxx=_max(maxx,(xn-xp[j])/(yp[j]-yn)); for(register int j=i+1;j<=n;++j) minx=_min(minx,(xn-xp[j])/(yp[j]-yn)); //printf("%.15lf %.15lf %d %d\n",maxx,minx,a[i].first,a[i].second); if(minx-maxx>=eps) for(auto&j:bs[i])ans[++t]=j; }*/ for(register int i=1;i<=tp;++i) for(auto &j:bs[stk[i]])ans[++t]=j; sort(ans+1,ans+t+1); for(register int i=1;i<=t;++i)printf("%d ",ans[i]); puts(""); return 0; }
T2
- 体验到了板子不会打的绝望。
- 裸的高斯消元。
- 不过会高斯消元也得不了多少分因为自己不会得到一个方程的解。
- 正解直接将目标方程的元消去，最终得到的解就是答案的相反数，因为保证有解所以一定可以消干净。
- 时间复杂度$\Theta(N^3)$，空间复杂度$\Theta(N^2)$。
- 听说不少人觉得读入难，其实吧，只要用一个map映射string就可以了，挺简单的，考试5分钟就打完了。
#include<cstdio> #include<string> #include<map> #include<iostream> #include<algorithm> #define ll long long using namespace std; int const N=203; int n,tot; double a[N][N],c[N]; map<string,int>qj; bool vis[N]; inline double _abs(double x){ return x<0?-x:x; } inline void _swap(double &x,double &y){ double z=x; x=y,y=z; return ; } inline void Gauss(){ for(register int i=1,now=1;i<n;now=++i){ for(register int j=i+1;j<n;++j) if(_abs(a[j][i])>_abs(a[now][i]))now=j; if(!_abs(a[now][i]))continue; double x=a[now][i]; for(register int j=1;j<=n;++j) _swap(a[i][j],a[now][j]),a[i][j]/=x; for(register int j=1;j<=n;++j){ if(j==i)continue; x=a[j][i]; for(register int k=i;k<=n;++k) a[j][k]-=a[i][k]*x; } } return ; } int main(){ //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); scanf("%d",&n); string s; char ss[5];double zz; int xs=1; for(register int i=1;i<=n;++i,xs=1) while(1){ scanf("%lf",&zz);zz*=xs; cin>>s; if(qj[s])a[i][qj[s]]=zz; else a[i][qj[s]=++tot]=zz; scanf("%s",ss); if(ss[0]=='=')xs=-1; else if(ss[0]=='H'){ scanf("%lf",&c[i]); break; } } n=(tot>n?tot:n)+1; for(register int i=1;i<n;++i)a[i][n]=c[i]; while(1){ scanf("%lf",&zz),zz*=xs; cin>>s; if(qj[s])a[n][qj[s]]=zz; else a[n][qj[s]=++tot]=zz; scanf("%s",ss); if(ss[0]=='=')xs=-1; else if(ss[0]=='H')break; } n=max(n,tot+1); Gauss(); a[n][n]?printf("%.1lf",-a[n][n]):puts("0.0"); return 0; }
T3
- dfs+信仰-1成功30。
- 首先时间显然随k的增加单调不降，所以可以二分答案。
- 因为选出的k个人的位置在t时刻后的相对位置不能发生改变，所以题意可以转化成最长上升子序列。
- 求出时间后，我们考虑如何构造字典序最小的最优解。
- LIS可以看成一棵树，每次转移相当于新加一个叶节点。
- 对于两个深度都为k的节点x,y，设lca(x,y)=fa。
- 那么如果x到fa路径上的最小编号小于y到fa路径上的最小编号，那么深度为k的解x比y优。
- 于是我们可以求出任意深度的最优解，但这个最优解的转移位置任意，而LIS的解必须保证权值单调上升。
- 我们可以对于每个深度开一棵动态开点线段树，维护前缀最优解就可以正确转移了。
- 由于博主太垃圾不会树状数组所以无论是LIS还是构造字典序最小的解都用的线段树而且不是zkw，所以常数巨大会T。
- 所以博主用了一个优化lca的常用方法。
- 可能大家不是很在意倍增lca的log，但事实上直接设一个极值比如log100000的做法常数很大。
- 优化很简单，预处理出1～n每个数的log值，进行倍增时只倍增到log[dep]。进行这种优化后博主可以通过本题。
- 时间复杂度$\Theta(NlogNlogT+Nlog^2N)$，空间复杂度$\Theta(NlogN)$。
#include<cstdio> #include<algorithm> #include<cstring> #define ll long long #define L tr[k].lc #define R tr[k].rc #define LC Tr[k].ls #define RC Tr[k].rs using namespace std; int const N=1e5+5,M=86400; int n,k; struct node{ int a,id; ll c; }q[N]; int p[N]; pair<long double,int>b[N]; struct Ljj{ int lc,rc,w; }tr[N<<3]; struct S_Tree{ int ls,rs,val,f; }Tr[N*100]; int tot,rt[N],Log[N],dep[N],f[N][18],mx[N][18]; int ans[N]; inline ll read(){ ll ss(0),pp(1);char bb(getchar()); for(;bb<48||bb>57;bb=getchar())if(bb=='-')pp=-1; while(bb>=48&&bb<=57)ss=(ss<<1)+(ss<<3)+(bb^48),bb=getchar(); return ss*pp; } inline void _swap(int &x,int &y){ int z=x; x=y,y=z; return ; } inline int min(int x,int y){ return x<y?x:y; } inline int max(int x,int y){ return x>y?x:y; } void build(int x,int y,int k){ L=x,R=y; if(x==y)return ; int mid=x+y>>1; return build(x,mid,k<<1),build(mid+1,y,k<<1|1); } void clear(int k){ if(!L||!tr[k].w)return ; tr[k].w=0; return clear(k<<1),clear(k<<1|1); } int ask(int x,int y,int k){ if(L>=x&&R<=y)return tr[k].w; int mid=L+R>>1,as=0; if(x<=mid)as=ask(x,y,k<<1); if(y>mid)as=max(as,ask(x,y,k<<1|1)); return as; } void add(int x,int y,int k){ if(L==R){tr[k].w=max(tr[k].w,y);return ;} int mid=L+R>>1; if(x<=mid)add(x,y,k<<1); else add(x,y,k<<1|1); tr[k].w=max(tr[k<<1].w,tr[k<<1|1].w); return ; } inline bool check(int x){ clear(1); for(register int i=1;i<=n;++i)b[i].first=0.5*x*x*q[i].a+q[i].c,b[i].second=i; sort(b+1,b+n+1); int now=0; b[0].first=b[1].first+1; for(register int i=1;i<=n;++i) p[b[i].second]=now=now+(b[i].first!=b[i-1].first); for(register int i=1,z;i<=n;++i){ z=0; if(p[i]!=1)z=ask(1,p[i]-1,1); add(p[i],++z,1); if(z>=k)return 1; } return 0; } inline int getmin(int x,int y){ if(!x||!y)return x+y; if(x==y)return x; int xm=x,ym=y,xx=x,yy=y; for(register int i=Log[dep[x]];~i;--i) if(f[x][i]^f[y][i]){ xm=min(xm,mx[x][i]),ym=min(ym,mx[y][i]); x=f[x][i],y=f[y][i]; } return xm<ym?xx:yy; } inline void down(int k){ if(!LC)LC=++tot; if(!RC)RC=++tot; int x=Tr[k].f; Tr[k].f=0; Tr[LC].val=getmin(Tr[LC].val,x),Tr[LC].f=getmin(Tr[LC].f,x); Tr[RC].val=getmin(Tr[RC].val,x),Tr[RC].f=getmin(Tr[RC].f,x); return ; } int Query(int l,int r,int x,int k){ if(!k)return 0; if(r<=x)return Tr[k].val; if(Tr[k].f&&l^r)down(k); int mid=l+r>>1,zz=Query(l,mid,x,LC); if(x>mid)zz=getmin(zz,Query(mid+1,r,x,RC)); return zz; } void Insert(int l,int r,int x,int y,int &k){ if(!k)k=++tot; if(l>=x){ Tr[k].val=getmin(y,Tr[k].val),Tr[k].f=getmin(y,Tr[k].f); return ; } if(Tr[k].f&&l^r)down(k); int mid=l+r>>1; if(x<=mid)Insert(l,mid,x,y,LC); Insert(mid+1,r,x,y,RC); Tr[k].val=getmin(Tr[LC].val,Tr[RC].val); return ; } int main(){ //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); n=read(),k=read(); Log[0]=-1; for(register int i=1;i<=n;++i)q[i].c=read(),q[i].a=read(),q[i].id=i,Log[i]=Log[i>>1]+1; sort(q+1,q+n+1,[](node skyh,node yxs){ return skyh.c<yxs.c; }); build(1,n,1); int l=0,r=M; while(l<r){ int mid=l+r+1>>1; if(check(mid))l=mid; else r=mid-1; } printf("%d\n",l); ++k; if(check(l))return puts("-1"),0; clear(1),memset(mx,0x3f,sizeof(mx)); for(register int i=1;i<=n;++i)b[i].first=0.5*l*l*q[i].a+q[i].c,b[i].second=i; sort(b+1,b+n+1); int now=0; b[0].first=b[1].first+1; for(register int i=1;i<=n;++i) p[b[i].second]=now=now+(b[i].first!=b[i-1].first); for(register int i=1,z,x,y;i<=n;++i){ z=0,y=q[i].id; if(p[i]!=1)z=ask(1,p[i]-1,1); add(p[i],z+1,1); if(p[i]!=1)f[y][0]=Query(1,n,p[i]-1,rt[z]); mx[y][0]=min(y,f[y][0]),dep[y]=z+1; for(register int j=0;j<Log[z];++j) f[y][j+1]=f[f[y][j]][j],mx[y][j+1]=min(mx[y][j],mx[f[y][j]][j]); Insert(1,n,p[i],y,rt[z+1]); } now=Query(1,n,n,rt[k-1]); for(register int i=1;i<k;++i) ans[i]=now,now=f[now][0]; sort(ans+1,ans+k); for(register int i=1;i<k;++i) printf("%d\n",ans[i]); return 0; }