20191015+
分类:
IT文章
•
2025-01-17 09:01:37
前言
- 连第二机房房主也不是了，该高兴还是该呵呵？
- 板子不会还是硬伤，不会高斯消元的我看到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
",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;
}
View Code
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;
}
View Code
![]()
#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
",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
",ans[i]);
return 0;
}
