感觉自己还是太菜了。。。
最近考试一直想不出来正解。难受（然而蒟蒻的博客没人看也要不来小猪peiqi的图）
模拟75：血炸。。。
考场上推了快两个小时的T1式子，然后心态炸裂，然后我也不知道自己干了什么，反正T1瞎打了一发，没过小样例
然后康T3，qj了部分分，不会打暴力，瞎码了一发，没过小样例。然后赶紧开T2，然后码了半天读入然后qj掉部分分
然后就没有然后了，然后考试就结束了，然后我就垫底了。然后改题该了一天。。。
注意考试时间和考试心态，不能慌
题确实挺好
T1：正解为凸包，然后卡精，把输入的a和b取倒数得到z=Ax+By，然后维护一个左下凸包就可以了。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<queue>
6 #include<vector>
7 #define N 300050
8 //#define double long double
9 using namespace std;
10 const double eps=0;
11 vector<int>v[N];
12 struct node{int a,b,id;}q[N];
13 bool cmp(const node &x,const node &y)
14 {
15 return x.a==y.a?x.b>y.b:x.a>y.a;
16 }
17 inline int read()
18 {
19 int s=0;char c=getchar();
20 while(c<'0'||c>'9')c=getchar();
21 while(c>='0'&&c<='9')s=s*10+c-'0',c=getchar();
22 return s;
23 }
24 bool check(double a,double b)
25 {
26 double k;
27 if(a>b)k=a-b;
28 else k=b-a;
29 return b<eps;
30 }
31 inline double work1(double x1,double x2,double x3,double y1,double y2,double y3)
32 {
33 return (y1-y2)*(x3-x2)/y2/y1/x2/x3;
34 }
35 inline double work2(double x1,double x2,double x3,double y1,double y2,double y3)
36 {
37 return (x2-x1)*(y2-y3)/y2/y3/x2/x1;
38 }
39 int n;
40 int ans[N];
41 priority_queue<int>qq;
42 int d[N],ba;
43 int main()
44 {
45 // freopen("da.in","r",stdin);
46 n=read();
47 for(int i=1;i<=n;++i)
48 {
49 q[i].a=read();
50 q[i].b=read();
51 q[i].id=i;
52 }
53 sort(q+1,q+n+1,cmp);
54 int ma2=0,ma1=0;
55 for(int i=1;i<=n;++i)
56 {
57 if(q[i].b>ma2)
58 {
59 ma2=q[i].b;ma1=q[i].a;
60 ans[++ans[0]]=i;
61 }
62 else if(q[i].b==ma2)
63 {
64 if(ma1==q[i].a)ans[++ans[0]]=i;
65 }
66 }
67 for(int i=1,t,p;i<=ans[0];++i)
68 {
69 double a1,a2,a3,b1,b2,b3;
70 double x1,x2,x3,y1,y2,y3;
71 t=ans[i];
72 a1=1.0/q[t].a;b1=1.0/q[t].b;
73 x1=q[t].a;y1=q[t].b;
74 if(!ba){
75 d[++ba]=t;
76 continue;
77 }
78 while(ba>1)
79 {
80 a2=1.0/q[d[ba]].a;
81 b2=1.0/q[d[ba]].b;
82 x2=q[d[ba]].a;y2=q[d[ba]].b;
83 if(a1>a2&&b1>b2)break;
84 if(x1==x2&&y1==y2){v[d[ba]].push_back(q[t].id);break;}
85 a3=1.0/q[d[ba-1]].a;
86 b3=1.0/q[d[ba-1]].b;
87 x3=q[d[ba-1]].a;y3=q[d[ba-1]].b;
88 if(check(work1(x1,x2,x3,y1,y2,y3),work2(x1,x2,x3,y1,y2,y3)))
89 {
90 d[++ba]=t;break;
91 }
92 if(work1(x1,x2,x3,y1,y2,y3)-work2(x1,x2,x3,y1,y2,y3)>eps)
93 {
94 --ba;
95 }
96 else
97 {
98 d[++ba]=t;break;
99 }
100 }
101 if(ba==1)
102 {
103 d[++ba]=t;
104 }
105 }
106 for(int i=1;i<=ba;++i)
107 {
108 qq.push(-q[d[i]].id);
109 for(int j=0;j<v[d[i]].size();++j)
110 {
111 qq.push(-v[d[i]][j]);
112 }
113 }
114
115 while(!qq.empty()){
116 printf("%d ",-qq.top());
117 qq.pop();
118 }
119 return 0;
120 }T2：注意输入。。。正解为Gauss消元，把答案矩阵的系数消掉，则最后等式右面就是答案的相反数
证明为啥可以直接进行高斯消元，首先答案行可以表示为每个已知行乘以一个系数相加得到。那么感性理解一下，考虑每个已知方程的贡献，当它下传时，下面的方程其实已经
累积了该方程的贡献，而题目又保证有解，所以考虑完每个方程后最后答案方程的系数一定会被消完
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<queue>
6 #include<cmath>
7 #define N 300
8 #define ull unsigned long long
9 using namespace std;
10 int n;
11 ull p=13331;
12 ull po[N];
13 ull lsh[190050];
14 int ls;
15 int a[N];
16 int pd[N];
17 double c[N][N],cc[N];
18 struct node{
19 ull ha;
20 int t;
21 double x;
22 }b[N][N];
23 void init()
24 {
25 sort(lsh+1,lsh+ls+1);
26 ls=unique(lsh+1,lsh+ls+1)-lsh-1;
27 for(int i=1;i<=n;++i)
28 {
29 for(int j=1;j<a[i];++j)
30 {
31 b[i][j].t=lower_bound(lsh+1,lsh+ls+1,b[i][j].ha)-lsh;
32 c[i][b[i][j].t]=b[i][j].x;
33 }
34 cc[i]=b[i][a[i]].x;
35 }
36 cc[n]=0;
37 }
38 double ks[N];
39 void pr()
40 {
41 for(int i=1;i<=n;++i)
42 {
43 for(int j=1;j<=ls;++j)
44 printf("%.1lf ",c[i][j]);
45 printf("%.1lf\n",cc[i]);
46 }
47 puts("");
48 }
49 void Gauss()
50 {
51 const int nn=n-1;
52 int ts=1;
53 // pr();
54 //while(1)
55 for(int o=1;o<=3;++o)
56 {
57 for(int i=1,t;i<=ls&&ts<n;++i)
58 {
59 if(!c[n][i])continue;
60 t=ts;
61 for(int j=t+1;j<n;++j){
62 if(fabs(c[j][i])>fabs(c[t][i])){
63 // printf("i:%d j::::%d\n",i,j);
64 for(int k=1;k<=ls;++k)
65 swap(c[t][k],c[j][k]);
66 swap(cc[t],cc[j]);
67 }
68 }
69 if(!c[t][i])continue;
70 for(int j=1;j<=n;++j)
71 {
72 if(!c[j][i]||j==t)continue;
73 double p=c[j][i]/c[t][i];
74 for(int k=1;k<=ls;++k)
75 c[j][k]-=c[t][k]*p;
76 cc[j]-=cc[t]*p;
77 }
78 ++ts;
79 // pr();
80 }
81 int ok=1;
82 for(int i=1;i<=ls;++i){if(c[n][i])ok=0;}
83 if(ok)break;
84 // pr();
85 }
86 if(fabs(cc[n])<0.0000000001){puts("0.0");return;}
87 printf("%.1lf\n",-cc[n]);
88 // pr();
89 }
90 int main()
91 {
92 // freopen("knight2.in","r",stdin);
93 scanf("%d",&n);++n;
94 for(int i=1,j,pd;i<=n;++i)
95 {
96 double x;char c;
97 j=0;pd=1;
98 while(1){
99 ++j;
100 scanf("%lf",&x);
101 b[i][j].x=x*pd;
102 c=getchar();
103 while(c<'A'||c>'Z')c=getchar();
104 while(c!=' '){
105 b[i][j].ha=b[i][j].ha*p+c;
106 c=getchar();
107 }
108 lsh[++ls]=b[i][j].ha;
109 while(c!='='&&c!='+'&&c!='H')c=getchar();
110 if(c=='=')pd=-1;
111 else if(c=='H')
112 {
113 ++j;if(i==n)break;
114 while(c!='=')c=getchar();
115 scanf("%lf",&b[i][j].x);
116 break;
117 }
118 }
119 a[i]=j;
120 }
121 init();
122 Gauss();
123 }T3：把老司机按照x排序，第一问即为最长上升子序列。
第二问考虑如何构造，发现最优情况下所有的老司机构成森林，扫描到当前老司机，考虑接在哪个lsj后面，
则可以倍增法对符合条件的lsj求lca，顺便维护一下覆盖的链的最值即可。
1 #include<bits/stdc++.h>
2 #define N 100050
3 #define LL long long
4 using namespace std;
5 const LL inf=200000000;
6 int n,k;
7 LL b[N],c[N];
8 int dp[N];
9 struct node{LL x,a;int id;}q[N];
10 bool cmp(const node &c,const node &d){return c.x<d.x;}
11 inline int check(const LL t)
12 {
13 for(int i=1;i<=n;++i)b[i]=q[i].x*2+t*q[i].a;
14 int ret=1;c[1]=b[1];
15 for(int i=2,po;i<=n;++i)
16 {
17 if(b[i]>c[ret])
18 {
19 c[++ret]=b[i];
20 continue;
21 }
22 if(b[i]<c[1]){
23 c[1]=b[i];
24 }
25 else{
26 po=lower_bound(c+1,c+ret+1,b[i])-c;
27 c[po]=b[i];
28 }
29 }
30 return ret;
31 }
32 int fa[N][22],mn[N][22];
33 int rt[N],tot;
34 int lc[N*30],rc[N*30],mi[N*30];
35 inline int getmin(const int xx,const int yy)
36 {
37 int x=xx,y=yy,mx=xx,my=yy;
38 for(int i=18;~i;--i)
39 {
40 if(fa[x][i]==fa[y][i])continue;
41 mx=min(mx,mn[x][i]);
42 my=min(my,mn[y][i]);
43 x=fa[x][i];y=fa[y][i];
44 }
45 // printf("xx:%d yy:%d mx:%d my:%d x:%d y:%d\n",xx,yy,mx,my,x,y);
46 if(mx<my)return xx;
47 return yy;
48 }
49 inline int upd(int x,int y)
50 {
51 if(!x||!y)return x|y;
52 return getmin(x,y);
53 }
54 void add(int &g,int l,int r,int pos,int id)
55 {
56 if(!g)g=++tot;
57 if(l==r){mi[g]=id;return;}
58 const int m=l+r>>1;
59 if(pos<=m)add(lc[g],l,m,pos,id);
60 else add(rc[g],m+1,r,pos,id);
61 mi[g]=upd(mi[lc[g]],mi[rc[g]]);
62 }
63 int ask(int g,int l,int r,int pos)
64 {
65 if(!g)return 0;
66 if(r<pos)return mi[g];
67 if(l>=pos)return 0;
68 const int m=l+r>>1;
69 return upd(ask(lc[g],l,m,pos),ask(rc[g],m+1,r,pos));
70 }
71 int ks[N];
72 inline void getans(int ans)
73 {
74 const LL t=1ll*ans*ans;
75 for(int i=1;i<=n;++i)c[i]=b[i]=q[i].x*2+t*q[i].a;
76 sort(c+1,c+n+1);
77 for(int j=1;j<=n;++j)b[j]=lower_bound(c+1,c+n+1,b[j])-c;
78 int ret=1;c[1]=b[1];dp[1]=1;
79 add(rt[1],1,n,b[1],q[1].id);
80 for(int i=2,po;i<=n;++i)
81 {
82 if(b[i]>c[ret])
83 {
84 c[++ret]=b[i];dp[i]=ret;
85 fa[q[i].id][0]=ask(rt[ret-1],1,n,b[i]);
86 mn[q[i].id][0]=fa[q[i].id][0];
87 for(int j=1;j<=17;++j)
88 {
89 fa[q[i].id][j]=fa[fa[q[i].id][j-1]][j-1];
90 mn[q[i].id][j]=min(mn[q[i].id][j-1],mn[fa[q[i].id][j-1]][j-1]);
91 }
92 add(rt[dp[i]],1,n,b[i],q[i].id);
93 }
94 else
95 {
96 if(b[i]<c[1])dp[i]=1;
97 else dp[i]=lower_bound(c+1,c+ret+1,b[i])-c;
98 c[dp[i]]=b[i];
99 fa[q[i].id][0]=ask(rt[dp[i]-1],1,n,b[i]);
100 mn[q[i].id][0]=fa[q[i].id][0];
101 for(int j=1;j<=17;++j)
102 {
103 fa[q[i].id][j]=fa[fa[q[i].id][j-1]][j-1];
104 mn[q[i].id][j]=min(mn[q[i].id][j-1],mn[fa[q[i].id][j-1]][j-1]);
105 }
106 add(rt[dp[i]],1,n,b[i],q[i].id);
107 }
108 // printf("i:%d b:%lld dp:%d\n",i,b[i],dp[i]);
109 // printf("%d %d\n",fa[q[i].id][0],q[i].id);
110 }
111 int an=0;
112 for(int i=n;i>=1;--i)
113 if(dp[i]==k)an=upd(an,q[i].id);
114 // printf("an:%d\n",an);
115 // an=5;
116 while(an){
117 ks[++ks[0]]=an;
118 an=fa[an][0];
119 }
120 sort(ks+1,ks+ks[0]+1);
121 for(int i=1;i<=ks[0];++i)
122 {
123 printf("%d\n",ks[i]);
124 }
125 }
126 int main()
127 {
128 // freopen("da.in","r",stdin);
129 //freopen("my.out","w",stdout);
130 scanf("%d%d",&n,&k);
131 if(k==1){puts("86400\n-1\n");return 0;}
132 for(int i=1;i<=n;++i)
133 scanf("%lld%lld",&q[i].x,&q[i].a),q[i].id=i;
134 sort(q+1,q+n+1,cmp);
135 int l=0,r=86400+1,mid;
136 while(l+1<r)
137 {
138 mid=l+r>>1;
139 if(check(1ll*mid*mid)>=k)l=mid;
140 else r=mid;
141 }
142 cout<<l<<endl;
143 // cout<<check(1ll*l*l)<<endl;
144 if(check(1ll*l*l)>k+1){puts("-1");return 0;}
145 getans(l);
146 return 0;
147 }模拟76：集训时间已过1/3（莫名紧张
T1：构造题，找规律，发现n=a*b显然可以直接构造，n>a*b必然无解,n==a+b-1必然有解，且两个序列共用一个数，n<a+b-1必然无解
剩下的情况按照类似n==a+b-1构造即可
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #define N 100050
6 using namespace std;
7 int n,a,b;
8 int ans[N];
9 void work1()
10 {
11 puts("Yes");
12 int al=0;
13 for(int i=n+1-a;i>=1;i-=a)
14 {
15 for(int j=i;j<i+a;++j)
16 ans[j]=++al;
17 }
18 for(int i=1;i<=n;++i)
19 printf("%d ",ans[i]);
20 puts("");
21 return;
22 }
23 int dp[N],f[N];
24 inline bool judge()
25 {
26 int an1=0,an2=0;
27 for(int i=1;i<=n;++i)
28 {
29 dp[i]=f[i]=1;
30 for(int j=1;j<i;++j)
31 {
32 if(ans[j]<ans[i])
33 {
34 f[i]=max(f[i],f[j]+1);
35 }
36 else
37 {
38 dp[i]=max(dp[i],dp[j]+1);
39 }
40 }
41 an1=max(an1,f[i]);
42 an2=max(an2,dp[i]);
43 }
44 return an1==a&&an2==b;
45 }
46 void work2()
47 {
48 for(int i=1;i<=n;++i)ans[i]=i;
49 int ok=0;
50 do{
51 if(judge()){ok=1;break;}
52 }while(next_permutation(ans+1,ans+n+1));
53 if(!ok){puts("No");return;}
54 puts("Yes");
55 for(int i=1;i<=n;++i)printf("%d ",ans[i]);
56 puts("");
57 }
58 void work3()
59 {
60 int al=n;
61 for(int i=1;i<a;++i)
62 ans[i]=i;
63 for(int i=a+1;i<=n;++i)
64 {
65 ans[i]=al;--al;
66 }
67 puts("Yes");
68 for(int i=1;i<=n;++i)printf("%d ",ans[i]);
69 puts("");
70 }
71 void work4()
72 {
73 int al=n-(a+b-1)+1,i,j;
74 for(i=al;i<al+a-1;++i)
75 ans[i]=i-al+1;
76
77 // for(int j=1;j<=n;++j)printf("%d ",ans[j]);puts("");
78 for(j=n;j>n-b;--j)
79 ans[i++]=j;
80 int fr=a,to=n-b,aa=a-1,bb=b-1,k;
81 // printf("aa:%d bb:%d\n",aa,bb);
82 i=n-(a+b-1);
83 // printf("i:%d fr:%d to:%d\n",i,fr,to);
84 while(1)
85 {
86 // printf("i:%d\n",i);
87 k=max(i-bb+1,1);
88 for(int j=1;j<=bb;++j)
89 {
90 ans[k]=to;
91 if(fr==to)break;
92 --to;++k;
93 }
94 i-=bb;
95 if(i<=0)break;
96 // if(fr==to)break;//&&ans[k]==to
97 --aa;
98 k=max(i-aa+1,1);
99 for(int j=1;j<=aa;++j)
100 {
101 ans[k]=fr;
102 if(fr==to)break;
103 ++fr;++k;
104 }
105 i-=aa;
106 if(i<=0)break;
107 // if(fr==to)break;
108 --bb;
109 }
110 puts("Yes");
111 for(int i=1;i<=n;++i)printf("%d ",ans[i]);
112 puts("");
113 }
114 void work()
115 {
116 if(n<=10){work2();return;}
117 if(1ll*a*b==n){work1();return;}
118 if(1ll*a*b<n){puts("No");return;}
119 if(a+b>n+1){puts("No");return;}
120 if(a+b==n+1){work3();return;}
121 work4();return;
122 }
123 int main()
124 {
125 int T;scanf("%d",&T);
126 while(T--)
127 {
128 scanf("%d%d%d",&n,&a,&b);
129 work();
130 }
131 }T2：结论题。子任务一：暴力跑背包，二：单调队列优化多重背包，三：暴搜
结论：排序后考虑每个物品的一半和前面所有物品的sum的关系，看有没有断档即可。（摘自DeepinC的blogs）
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #define N 100050
6 using namespace std;
7 int a[N];
8 int n,an;
9 inline void work4()
10 {
11 long long l=(a[1]+1)/2,r=a[1],sum=0;
12 for(int i=2;i<=n;++i)
13 {
14 if((a[i]+1)/2>r+1)
15 {
16 sum+=r-l+1;
17 l=(a[i]+1)/2;
18 }
19 r+=a[i];
20 }
21 sum+=r-l+1;
22 cout<<sum<<endl;
23 }
24 int main()
25 {
26 scanf("%d",&n);
27 for(int i=1;i<=n;++i)scanf("%d",&a[i]);
28 sort(a+1,a+n+1);
29 work4();return 0;
30 }T3：考试时一直没想出来怎么搞掉限制，然后skyh大声地在纸上写AK，然后就拼命想正解，然后就想到了，然后就没时间打了，然后skyh就AK了。。。
我们发现先序遍历有很多优美的性质，然后考虑yy它，因为序列递增，把限制拍到序列上，dp[i][j]表示以i为根，子树大小为j的方案数，利用先序遍历和中序遍历的性质进行转移
对每个点记录它后面的中序限制在它前面的最大的点，和它后面的中序限制在它后面的最小的点然后就可以kx地转移了，注意子树大小为1也需要转移
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #define N 450
6 const int mod=1000000007;
7 using namespace std;
8 int a[N];
9 int n,m,ok;
10 int dp[N][N],f[N][N];
11 void init()
12 {
13 ok=1;
14 for(register int i=400;i;--i){
15 f[i][0]=f[i][1]=1;
16 for(register int j=2;j<=400;++j)
17 for(register int k=0;k<j;++k)
18 (f[i][j]+=1ll*f[i+1][k]*f[i+1][j-k-1]%mod)%=mod;
19 }
20 }
21 inline void work1()
22 {
23 if(!ok){init();}
24 cout<<f[400-n+1][n]<<endl;
25 }
26 struct node{int x,y;}ed[N][N];
27 int pre[N],las[N];
28 inline void work2()
29 {
30 memset(dp,0,sizeof(dp));
31 dp[n][1]=dp[n][0]=dp[n+1][0]=1;
32 for(int i=n-1;i;--i)
33 {
34 dp[i][0]=1;
35 for(int j=1;j+i-1<=n;++j)
36 {
37 dp[i][j]=0;
38 for(int k=max(pre[i]-i,0);k<las[i]-i&&k<j;++k)
39 {
40 dp[i][j]+=1ll*dp[i+1][k]*dp[i+k+1][j-k-1]%mod;
41 if(dp[i][j]>=mod)dp[i][j]-=mod;
42 }
43 // printf("dp[%d][%d]:%d\n",i,j,dp[i][j]);
44 }
45 }
46 cout<<dp[1][n]<<endl;
47 }
48 int main()
49 {
50 // freopen("sample.in","r",stdin);
51 int T;scanf("%d",&T);
52 while(T--)
53 {
54 scanf("%d%d",&n,&m);
55 if(!m){work1();continue;}
56 for(int i=1;i<=n;++i)las[i]=n+1,pre[i]=0;
57 for(int i=1,x,y;i<=m;++i){
58 scanf("%d%d",&x,&y);
59 if(y>x)las[x]=min(las[x],y);
60 pre[y]=max(pre[y],x);
61 }
62 int ok=0;
63 for(int i=1;i<=n;++i)
64 {
65 if(pre[i]>=las[i]){
66 ok=1;break;
67 }
68 }
69 if(ok){puts("0");continue;}
70 work2();
71 }
72 }ps：RP守恒，不要太飘
pps：做难题，填坑