\(\color{white}{\mathbb{曲径通幽，星汉隐约，缥缈灯影，朦胧缺月，名之以：薄雾}}\)

放眼望去前十被我弃掉的 \(t2\) 基本都上85了……

开考就以为 \(t2\) 是个大毒瘤模拟，而且不会读入，根本没多想

还好 \(t1\)、\(t3\) 挂分不多，要不然又是考很砸的一场

A. 导弹袭击

考场上看见像凸包，连推柿子带胡猜了好几种都不对

正解是这样的：

柿子是 \(\displaystyle t=\frac{A}{a_i}+\frac{B}{b_i}\)

那么应该把每个点的横纵坐标取个倒数，所以 \(t=Ax+By\)

那么 \(\displaystyle y=-\frac{A}{B}x+\frac{t}{B}\)

转化成了斜率优化经典式，斜率为负要使截距最大，那么维护下凸包即可

这道题比较卡精度，把斜率式换一下，写成：

\[\frac{a_ia_j(b_i-b_j)}{b_ib_j(a_i-a_j)}
\]

还有一个小优化，如果一个导弹两个速度都小，那么一定不优，直接排除掉即可

代码实现

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n,sta[maxn],tp,mx;
bool vis[maxn],flag[maxn];
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=x*10+ch-48;
        ch=getchar();
    }
    return x*f;
}
struct P{
    int x,y,id;
}a[maxn];
bool cmp(P a,P b){
    return a.x==b.x?a.y>b.y:a.x>b.x;
}
double slope(int i,int j){
    return 1.0*a[i].x*a[j].x*(a[i].y-a[j].y)/(1.0*a[i].y*a[j].y*(a[i].x-a[j].x));
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        a[i].x=read();
        a[i].y=read();
        a[i].id=i;
    }
    sort(a+1,a+n+1,cmp);
    mx=0;
    for(int i=1;i<=n;i++){
        if(a[i].y>mx){
            vis[i]=true;
            mx=a[i].y;
        }
    }
    sta[++tp]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i])continue;
        if(slope(i,sta[tp])>0)continue;
//        cout<<i<<" ";
        while(tp>1&&slope(i,sta[tp])<slope(sta[tp-1],sta[tp]))tp--;
        sta[++tp]=i;
    }
    for(int i=1;i<=tp;i++){
        flag[a[sta[i]].id]=true;
        for(int j=sta[i]+1;j<=n&&a[j].x==a[sta[i]].x&&a[j].y==a[sta[i]].y;j++)flag[a[j].id]=true;
    }
    for(int i=1;i<=n;i++){
        if(flag[i])printf("%d ",i);
    }
    return 0;
}

/*
7
6 6
5 7
3 13
4 12
2 13
12 4
3 13
*/ 

---

B. 炼金术士的疑惑

第一眼看上去什么奇奇怪怪的东西以为是个大模拟，再加上奇奇怪怪的读入我很有自信读人写不出来，于是这道题基本没想，就最后十分钟水了个15分的暴力

正解是高斯消元，把每个方程式都可以看成一些未知数加减的方程，答案也是一个要求得数的方程

那么把系数写成矩阵进行高斯消元，并把答案的系数也顺便消掉

由于保证有解，最后一行未知数系数一定会被消成零，那么此时等号右边的数的相反数即为答案

代码实现

#include<bits/stdc++.h>
using namespace std;
const int maxn=300;
const double eps=1e-10;
int n,m,tot,op;
double a[maxn][maxn],val[maxn],x;
string s;
char c[10];
map<string,int>mp;
double fabs(double x){
    if(x<0)return -x;
    return x;
}
void gauss(){
    for(int i=1;i<=n-1;i++){
        int mx=i;
        for(int j=i+1;j<=n-1;j++){
            if(fabs(a[j][i])>fabs(a[mx][i]))mx=j;
        }
        swap(a[i],a[mx]);
        if(fabs(a[i][i])<eps)continue;
        double chu=a[i][i];
        for(int j=i;j<=m;j++){
            a[i][j]/=chu;
        }
        for(int j=1;j<=n;j++){
            if(i==j)continue;
            chu=a[j][i]/a[i][i];
            for(int k=i;k<=m;k++){
                a[j][k]-=a[i][k]*chu;
            }
        }
//        for(int i=1;i<=n;i++){
//            for(int j=1;j<=m;j++){
//                cout<<a[i][j]<<"    ";
//            }
//            cout<<endl;
//        }
    }
}
int main(){
    cin>>n;
    int t=n;
    for(int i=1;i<=n+1;i++){
        op=1;
        while(1){
            cin>>x;
            cin>>s;
            if(mp.find(s)==mp.end()){
                mp[s]=++tot;
                a[i][tot]=x*op;
            }
            else{
                a[i][mp[s]]=x*op;
            }
            scanf("%s",c+1);
            if(c[1]=='=')op=-1;
            if(c[1]=='H'&&c[2]=='=')break;
        }
        if(i!=n+1)cin>>val[i];
    }
    m=tot+1;
    for(int i=1;i<=n;i++){
        a[i][m]=val[i];
    }
    n++;

    gauss();
    a[n][m]=-a[n][m];
//    cout<<a[n][m]<<endl;
    if(a[n][m]>=-0.09&&a[n][m]<=0)cout<<"0.0";
    else printf("%.1lf",a[n][m]);
    return 0;
}

/*
2
1 C + 1 O2 = 1 CO2 H= -393.5
1 CO + 0.5 O2 = 1 CO2 H= -283.0
2 C + 1 O2 = 2 CO H= ?
*/ 

---

C. 老司机的狂欢

考场上想到二分，想到了按 \(x\) 轴排序后 \(dp\)，但是转移状态条件太复杂，没有优化空间

由于二分完时间已知，那么每个人的终点位置已知，那么如果两人相撞，一定形成逆序对，于是转化成 \(LIS\) 问题。

后半部分才是最毒瘤的，因为排过序，所以不能贪心地从上一个转移，题解介绍了神奇的倍增法

由于 \(LIS\) 的最优转移形成了一棵树，从根节点到这个节点的链即为答案的字典序，那么要比较字典序即是比较链上最小值，排除 \(LCA\) 以上的部分，从分叉处开始比较

这是经典的树上倍增问题

代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=x*10+ch-48;
        ch=getchar();
    }
    return x*f;
}
const int maxn=2e5+5;
int n,k,f[maxn],sta[maxn],tp,c1[maxn],tot,lsh[maxn],b[maxn];
bool flag;
struct Driver{
    int x,a,id;
}d[maxn];
bool cmp(Driver a,Driver b){
    return a.x<b.x;
}
int ask1(int x){
    int ans=0;
    for(;x;x-=x&-x)ans=max(ans,c1[x]);
    return ans;
}
void add1(int x,int w){
    for(;x<=tot;x+=x&-x)c1[x]=max(c1[x],w);
    return ;
}
bool check(int t){
    memset(c1,0,sizeof c1);
    int mx=0;
    for(int i=1;i<=n;i++){
        lsh[i]=b[i]=2*d[i].x+d[i].a*t*t;
    }
    sort(lsh+1,lsh+n+1);
    tot=unique(lsh+1,lsh+n+1)-lsh-1;
    for(int i=1;i<=n;i++){
        b[i]=lower_bound(lsh+1,lsh+tot+1,b[i])-lsh;
    }
    for(int i=1;i<=n;i++){
        int x=ask1(b[i]-1)+1;
        add1(b[i],x);
        mx=max(mx,x);
    }
    if(mx>=k){
        if(mx>k)flag=true;
        else flag=false;
        return true;
    }
    return false;
}
struct Node{
    int dis,id;
    Node(){}
    Node(int x,int y):dis(x),id(y){}
}c[maxn];
int fa[maxn][25],minn[maxn][25];
bool operator < (const Node &aa,const Node &bb){
    if(aa.dis!=bb.dis)return aa.dis<bb.dis;
    int xx=aa.id;
    int yy=bb.id;
    int mina=aa.id,minb=bb.id;
    for(int i=20;i>=0;i--){
        if(fa[xx][i]!=fa[yy][i]){
            mina=min(mina,minn[xx][i]);
            minb=min(minb,minn[yy][i]);
            xx=fa[xx][i];
            yy=fa[yy][i];
        }
    }
    return mina>minb;
}
Node ask(int x){
    Node ans=Node(0,0);
    for(;x;x-=x&-x)ans=max(ans,c[x]);
    return ans;
}
void add(int x,Node w){
    for(;x<=tot;x+=x&-x)c[x]=max(c[x],w);
    return ;
}
void solve(int t){
    for(int i=1;i<=n;i++){
        lsh[i]=b[i]=2*d[i].x+d[i].a*t*t;
    }
    sort(lsh+1,lsh+n+1);
    tot=unique(lsh+1,lsh+n+1)-lsh-1;
    for(int i=1;i<=n;i++){
        b[i]=lower_bound(lsh+1,lsh+tot+1,b[i])-lsh;
//        cout<<b[i]<<" ";
    }
    for(int i=1;i<=n;i++){
        Node x=ask(b[i]-1);
        fa[d[i].id][0]=minn[d[i].id][0]=x.id;
        for(int j=1;j<=20;j++){
            fa[d[i].id][j]=fa[fa[d[i].id][j-1]][j-1];
            minn[d[i].id][j]=min(minn[fa[d[i].id][j-1]][j-1],minn[d[i].id][j-1]);
        }
//        cout<<i<<" "<<x.id<<" "<<x.dis<<endl;
        Node y=Node(x.dis+1,d[i].id);
        add(b[i],y);
    }
    int x=ask(n).id;
    while(x){
        sta[++tp]=x;
        x=fa[x][0];
    }
    sort(sta+1,sta+tp+1);
    for(int i=1;i<=tp;i++){
        printf("%d\n",sta[i]);
    }
    return ;
}
signed main(){
//    freopen("my.out","w",stdout);
    n=read();
    k=read();
    for(int i=1;i<=n;i++){
        d[i].x=read();
        d[i].a=read();
        d[i].id=i;
    }
    sort(d+1,d+n+1,cmp);
    int l=0,r=86400,last=0;
    while(l<r){
        int mid=l+r+1>>1ll;
        if(check(mid))l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    if(flag){
        puts("-1");
        return 0;
    }
    solve(l);
    return 0;
}

/*
4 3
-69 2
75 -2
-85 1
96 -1
*/ 

\(\color{white}{\mathbb{拣尽寒枝不肯栖，寂寞沙洲冷。}}\)