T1 导弹袭击（数学）
显然，我们要找到最优的A,B使得一组a，b优于其他组那么可以列出：
$\frac{A}{a_i}+\frac{B}{b_i}<\frac{A}{a_j}+\frac{B}{b_j}$
然后化简可得：
$-\frac{A}{B}<\frac{\frac{1}{b_i}-\frac{1}{b_j}}{\frac{1}{a_i}-\frac{1}{a_j}}$
就是裸斜率式
考场上想到维护凸包，但并未打出。。。
正解还要有好多预先步骤，用经典指针+经典排序扫描将显然不能成为最优的导弹去掉
1.a一样而b不是最大的
2.b一样而a不是最大的
3.有一组是a，b均大于另一组a，b的
扫描过后用单调栈维护斜率为负的单调递增的左下凸包即可
注意的就是将斜率式化简通分，否则大数据值过小而无法判断
1 #include<bits/stdc++.h>
2 #define LD long double
3 using namespace std;
4 inline int read(){
5 int x=0,f=1; char ch=getchar();
6 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
7 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
8 return x*f;
9 }
10 const int NN=3e5+5,inf=0x7fffffff;
11 int n,top; bool vis[NN];
12 struct point{
13 LD x,y;int id;
14 friend bool operator<(point a,point b){return a.x==b.x? a.y<b.y:a.x>b.x;}
15 };point p[NN],sta[NN];
16 struct SNOW{int a,b,tag,id;}s[NN];
17 inline bool cmp1(SNOW x,SNOW y){return x.a==y.a?x.b>y.b:x.a>y.a;}//以a排列
18 inline bool cmp2(SNOW x,SNOW y){return x.b==y.b?x.a>y.a:x.b>y.b;}//以b排列
19 inline bool cmp3(SNOW x,SNOW y){return x.a==y.a?x.b>y.b:x.a<y.a;}
20 inline LD calc(point p1,point p2){return (p1.x*p2.x)/(p1.y*p2.y)*((p1.y-p2.y)/(p1.x-p2.x));}
21 vector<int> kin[NN];
22 inline void pai_a(){
23 sort(s+1,s+n+1,cmp1); int pp=s[1].a,i=1,maxn=s[1].b;
24 while(i<=n){
25 int j=1; while(pp==s[i+j].a){
26 if(s[i+j].b!=s[i].b) s[i+j].tag=1;
27 if(maxn<s[i+j].b) maxn=s[i+j].b;
28 if(s[i+j].b<maxn) s[i+j].tag=1;
29 j++;
30 }
31 if(maxn<s[i].b) maxn=s[i].b;
32 if(s[i].b<maxn) s[i].tag=1;
33 pp=s[(i=i+j)].a;
34 }
35 }
36 inline void pai_b(){
37 sort(s+1,s+n+1,cmp2); int pp=s[1].b,i=1,maxn=s[1].a;
38 while(i<=n){
39 int j=1; while(pp==s[i+j].b){
40 if(s[i+j].a!=s[i].a) s[i+j].tag=1;
41 if(maxn<s[i+j].a) maxn=s[i+j].a;
42 if(s[i+j].a<maxn) s[i+j].tag=1;
43 j++;
44 }
45 if(maxn<s[i].a) maxn=s[i].a;
46 if(s[i].a<maxn) s[i].tag=1;
47 pp=s[(i=i+j)].b;
48 }
49 }
50 inline int getrange(int x){
51 sort(s+1,s+n+1,cmp3); int i=1,pp=s[1].a;
52 while(i<=n){
53 if(s[i].a==inf) break;
54 int j=1; while(pp==s[i+j].a){
55 kin[s[i].id].push_back(s[i+j].id);
56 s[i+j].a=s[i+j].b=inf;
57 j++;
58 }
59 pp=s[(i=i+j)].a;
60 } x=--i;
61 sort(s+1,s+x+1,cmp3);
62 i=1; while(i<=x){
63 if(s[i].a==inf) break;
64 i++;
65 } x=--i;
66 return x;
67 }
68 namespace WSN{
69 inline int main(){
70 n=read(); int tot=n;
71 for(int i=1;i<=n;i++) s[i].a=read(),s[i].b=read(),s[i].id=i;
72 pai_a(); pai_b();
73 for(int i=1;i<=n;i++) if(s[i].tag==1) s[i].a=s[i].b=inf;
74 n=getrange(n);
75 for(int i=1;i<=n;i++) p[i].x=(LD)s[i].a,p[i].y=(LD)s[i].b,p[i].id=s[i].id;
76 sort(p+1,p+n+1); top=2; sta[1]=p[1]; sta[2]=p[2];
77 for(int i=3;i<=n;i++){
78 while(top>1&&(calc(sta[top],sta[top-1])>calc(p[i],sta[top-1]))) top--;
79 sta[++top]=p[i];
80 }
81 for(int i=1;i<=top;i++){
82 vis[sta[i].id]=1;
83 for(int j=0;j<kin[sta[i].id].size();j++) vis[kin[sta[i].id][j]]=1;
84 }
85 for(int i=1;i<=tot;i++) if(vis[i]) printf("%d ",i);
86 return 0;
87 }
88 }
89 signed main(){return WSN::main();}
T2 炼金术士的疑惑
输入直接看傻，然后一看高斯消元板子不会就直接跳了。
不过自认为这题除了输入比较miao以外没啥难的
想到将方程式所有的元素移到左侧，变符号，那么一列一列消元
最后剩下的一列得出的答案便是最后一个反应的焓变（性感理解一下）
技巧：
1.使用map去掉重复元素
2.根据读入字符进行添加行列式项
1 #include<bits/stdc++.h>
2 using namespace std;
3 inline int read(){
4 int x=0,f=1; char ch=getchar();
5 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
6 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
7 return x*f;
8 }
9 int n,cnt;
10 double a[205][205];
11 map<string,int> has;
12 inline void init(){
13 n=read();
14 string chm,opt;
15 bool flag=0;
16 double x;
17 for(int i=1;i<=n;i++){
18 flag=0;
19 while(1){
20 cin>>x>>chm>>opt;
21 if(!has[chm]) has[chm]=++cnt;
22 a[i][has[chm]]=flag?-x:x;
23 if(opt[0]=='=') flag=1;
24 if(opt[0]=='H'){
25 cin>>a[i][201];
26 break;
27 }
28 }
29 }
30 ++n; flag=0;
31 while(1){
32 cin>>x>>chm>>opt;
33 if(!has[chm]) has[chm]=++cnt;
34 a[n][has[chm]]=flag?-x:x;
35 if(opt[0]=='=') flag=1;
36 if(opt[0]=='H'){
37 cin>>opt;
38 break;
39 }
40 }
41 for(int i=1;i<=n;i++)
42 a[i][cnt+1]=a[i][201];
43 }
44 inline void guass(){
45 int num=1;
46 for(int i=1;i<=cnt;i++){
47 int r=num;
48 for(int j=num;j<n;j++)
49 if(fabs(a[j][i])>fabs(a[r][i])) r=j;
50 if(fabs(a[r][i])<1e-10) continue;
51 for(int j=i;j<=cnt+1;j++) swap(a[r][j],a[num][j]);
52 for(int j=cnt+1;j>=i;j--) a[num][j]/=a[num][i];
53 for(int j=num+1;j<=n;j++)
54 if(fabs(a[j][i])>1e-10)
55 for(int k=cnt+1;k>=i;k--) a[j][k]-=a[num][k]*a[j][i];
56 num++;
57 }
58 }
59 namespace WSN{
60 inline int main(){
61 init();
62 guass();
63 if(fabs(a[n][cnt+1])<0.05) puts("0.0");
64 else printf("%.1lf",-a[n][cnt+1]);
65 return 0;
66 }
67 }
68 signed main(){return WSN::main();}
T3 老司机的狂欢
题目第一问在问老司机不撞车的最大时间，
可以二分判断在当前时间下成立与否，左右端点确定
判断可以将其看作一段序列，在进行了t时间移动后这段序列的最长上升子序列是否大于k
那么我们用数状数组快速求出最长上升子序列长度判断即可
第二问就比较牛皮
我们知道最优时间以后进行二次判断，如果当前上升序列的个数大于k直接判断老司机造反
剩下的我们需要求字典序最小方案
把它看作一个树形结构，每个节点的父亲表示其最优转移方案，这样的话使用倍增思想建树
查询过程与求LIS类似，只是多增加一个编号的维护，minn和fa分别为维护最小编号的数组和第$2^i$级爹
再就是miin函数的返还值问题
技巧：
1.数状数组优化求LIS
2.倍增建树及LIS编号维护
3.二分答案
1 #include<bits/stdc++.h>
2 #define int long long
3 #define pii pair<int,int>
4 using namespace std;
5 const int NN=700005,inf=1e18+5;
6 int n,k;
7 int tr[NN];
8 int a[NN],dis[NN],new_n;
9 int anss,fa[NN][21],minn[NN][21];
10 int con[NN];
11 pii t[NN];
12 //pair中存储的first表示值，second表示编号
13 //fa，minn数组表示的内容都是编号间的关系，minn是维护最小编号用的
14 struct node{
15 int x,a,id;
16 friend bool operator<(node m,node n){return m.x<n.x;}
17 };node d[NN];
18 inline int max(int a,int b){return a>b?a:b;}
19 inline int min(int a,int b){return a<b?a:b;}
20 inline int lowbit(int x){return x&(-x);}
21 inline void update(int x,int val){for(int i=x;i<=new_n;i+=lowbit(i)) tr[i]=max(tr[i],val);}
22 inline int query(int x){int ans=0;for(int i=x;i;i-=lowbit(i)) ans=max(ans,tr[i]);return ans;}
23 inline bool check(int t){
24 memset(tr,0,sizeof(tr));
25 for(int i=1;i<=n;i++) dis[i]=a[i]=2*d[i].x+d[i].a*t*t;
26 sort(dis+1,dis+n+1); new_n=unique(dis+1,dis+n+1)-dis-1;
27 for(int i=1;i<=n;i++) a[i]=lower_bound(dis+1,dis+new_n+1,a[i])-dis;
28 for(int i=1;i<=n;i++) update(a[i],query(a[i]-1)+1);
29 anss=query(new_n);
30 return anss>=k;
31 }
32
33 inline bool miin(pii a,pii b){
34 if(a.first!=b.first) return a.first<b.first;
35 int mina=a.second,minb=b.second;
36 int x=a.second,y=b.second;
37 for(int i=20;i>=0;i--){
38 if(fa[x][i]!=fa[y][i]){
39 mina=min(mina,minn[x][i]);
40 minb=min(minb,minn[y][i]);
41 x=fa[x][i]; y=fa[y][i];
42 }
43 }
44 return mina>minb;
45 }
46 inline void build(int x,int f){
47 fa[x][0]=minn[x][0]=f;
48 for(int i=1;i<=20;i++){
49 fa[x][i]=fa[fa[x][i-1]][i-1];
50 minn[x][i]=min(minn[fa[x][i-1]][i-1],minn[x][i-1]);
51 }
52 }
53 inline void merge(int x,pii val){
54 for(int i=x;i<=new_n;i+=lowbit(i))
55 if(miin(t[i],val)) t[i]=val;
56 }
57 inline pii search(int x){
58 pii ans=make_pair(0,0);
59 for(int i=x;i;i-=lowbit(i))
60 if(miin(ans,t[i])) ans=t[i];
61 return ans;
62 }
63 namespace WSN{
64 inline int main(){
65 // freopen("1.in","r",stdin);
66 scanf("%lld%lld",&n,&k);
67 for(int i=1;i<=n;i++) scanf("%lld%lld",&d[i].x,&d[i].a),d[i].id=i;
68 sort(d+1,d+n+1);
69 int l=0,r=86400,ans=l;
70 while(l<=r){
71 int mid=l+r>>1;
72 if(check(mid)) ans=mid,l=mid+1;
73 else r=mid-1;
74 }
75 printf("%lld\n",ans); check(ans);
76 if(anss>k) {printf("-1\n");return 0;}
77 for(int i=1;i<=n;i++) dis[i]=a[i]=2*d[i].x+d[i].a*ans*ans;
78 sort(dis+1,dis+n+1); new_n=unique(dis+1,dis+n+1)-dis-1;
79 for(int i=1;i<=n;i++) a[i]=lower_bound(dis+1,dis+new_n+1,a[i])-dis;
80 // for(int i=1;i<=n;i++) cout<<a[i]<<" "<<d[i].id<<endl;
81 for(int i=1;i<=n;i++){
82 pii now=search(a[i]-1);
83 build(d[i].id,now.second);
84 merge(a[i],make_pair(now.first+1,d[i].id));
85 }
86 int wsn=search(new_n).second;
87 for(int i=1;i<=k;i++){
88 con[i]=wsn;
89 wsn=fa[wsn][0];
90 }
91 sort(con+1,con+k+1);
92 for(int i=1;i<=k;i++) printf("%lld\n",con[i]);
93 return 0;
94 }
95 }
96 signed main(){return WSN::main();}
![[考试反思]0801NOIP模拟测试11](https://www.kunjuke.com/file/css/thumb/2.jpg/280-180.jpg)
![[NOI.AC省选模拟赛3.23] 染色 [点分治+BFS序]](https://www.kunjuke.com/file/css/thumb/11.jpg/280-180.jpg)
![[CSP-S模拟测试]:Cover（单调栈++单调队列+DP）](https://www.kunjuke.com/file/css/thumb/5.jpg/280-180.jpg)