总结
考试策略
T1 暴力显然，因为好写而且没有想到正解所以直接跳过。T2 因为题意一直在强调几个东西，把这些当做状态就切掉了。仔细阅读 T3 之后没有好想法，所以回到 T1，想到一种正解。写了三分查找，过了大样例后时间剩余不多，紧急回头写 T3 暴力与骗分。
结果反思
T1：期望得分 ，实际得分 ，三分查找挂掉了。代码实现能力需加强。
T2：期望得分 ，实际得分 。
T3：期望得分 ，实际得分 。没骗到分，题目不会属于个人能力问题。
题解
T1：斯
给定两个长度为 的实数序列 。对于任意一个序列的任意一个数，你都可以用 的代价标记这个数。记 序列标记的数之和为 ， 序列标记的数之和为 。你的到的收益为 减去花费的代价。求收益最大值。。
考虑到选择一个数的代价都是 。那么对于属于同一序列的数，显然优先选择数值更大的。本题的重点就是显然不能全部选择，因为代价随选择个数线性增长，可能选到后面就有些入不敷出。因为一定优先选择最大的，所以不妨先给 按大到小排个序，此时一个符合贪心策略的选择方案就是在 数组选前若干个， 数组选前若干个。
因为是选择前若干个，还可以用前缀和跑一下，记录 ，，题意简化成，确定一个有序二元组 ，使得 最大。
还有一点要注意的是因为允许不选择，所以答案一定不会小于 。
不妨假设我们已经确定的二元组中 取什么值，考虑求 的范围。因为当 较小的时候， 函数会取到 ，因为 ，所以 每减小 ，虽然代价减少了 ，但是少选的数的贡献不少于一，整体是不上升的。换句话说此时答案随 减小而不升；当 较大的时候， 函数会取到 ，此时 再大也无济于事， 增大只会让代价随之增大。换句话说此时答案随 增大而增大。
整体上看， 固定时，前一部分答案随 减小而不上升，后一部分答案随 增大而减小。 和答案的关系是一个不严格的 单峰函数。管他严不严格，只要是单峰函数，三分查找都可以解决。
这里的三分查找也不是什么很严格的三分查找，不是每次将序列缩短为原来的三分之一，而是缩短三分之一，具体情况如下：我们三分一个 和 ，考虑其在单峰函数上可能的关系即可。
三分查找单峰函数峰值
假设我们的单峰函数长这样：
我才不会告诉你这就是一个二次函数和一次函数拼起来得到的
对于 的情况，有两种可能：
- 二者在同侧：
- 二者在异侧：
不难发现这两种情况都直接将左端点移动到 的位置即可。
对于 的情况，也有两种可能：
- 二者在同侧：
- 二者在异侧：
不难发现这两种情况都直接将右端点移动到 的位置即可。
现在对于某一个 ，我们可以通过三分查找得到 ，从而算出这个情况下的最优答案。这样的不严格三分（其实也是三分）的复杂度是 的。（因为考虑到每次把原区间缩短为原来的三分之二，所以 的底数是三分之二的倒数，也就是 ）
显然 直接枚举即可。总的复杂度是 。
代码：
#include<bits/stdc++.h>
using namespace std;
const int max_n=100005;
inline bool cmp(double a,double b){ // 大到小排序
return a>b;
}
int n;
double a[max_n*2],s1[max_n],s2[max_n],ans;
// 原题题不是 a,b 数组，是 a 数组的 1-n 和 n+1-2n 两个部分
inline double ck(int k,int p){ // 求 i=p,j=k 时的答案
return min(s1[p],s2[k-n])-1.0*(k-n+p);
}
inline int sf(int l,int r,int p){
while(l<=r){
int ml=l+(r-l)/3,mr=ml+(r-l+2)/3; // 注意细节
if(ck(ml,p)<ck(mr,p)) l=ml+1; // lmid贡献<rmid
else r=mr-1; // 反之
}
return l;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(register int i=1;i<=n*2;++i)
cin>>a[i];
sort(a+1,a+1+n,cmp),
sort(a+1+n,a+1+2*n,cmp); // 分别大到小排序
for(register int i=1;i<=n;++i)
s1[i]=s1[i-1]+a[i]; // 前缀和，题解里的 sa
for(register int i=n+1;i<=n*2;++i)
s2[i-n]=s2[i-n-1]+a[i]; // 题解里的 sb
for(register int i=1;i<=n;++i){
int p=sf(n+1,2*n,i); // 枚举 i，三分 j，更新答案
ans=max(ans,min(s1[i],s2[p-n])-1.0*(p-n+i));
}
printf("%.4lf",ans);
return 0;
}
T2：给
求有多少个区分左右儿子我的二叉树，恰好有 个叶子节点，且每个节点要么没有儿子，要么有两个儿子，同时不存在任意一个节点，使得从这个节点到根的路径上有不少于 条向左的边。对于每一个 ，都要计算答案。。
题目提到的两个关键元素，一个是“叶子数”，另一个是“向左走的路径数”。而数据范围刚好可以进行平方级别的 DP，不妨把这个当成状态一试。确切地说，边模拟一个建树的过程边 DP，设 表示现在的树有 个叶子，且当前考虑的节点到根节点有 条向左的边。
假设模拟建树的过程，对于某一棵树， 号节点的左子树已经全部考虑完，现在考虑建完 号点，考虑 号点建在哪里：
有两种转移：
- 在 号点下面直接新建 号点，因为每个节点要么没有儿子要么两个儿子都要有，不妨先考虑建一个右儿子，因为右儿子到父亲的路径是向左走的好像一些（建左儿子的情况会在第二个转移提到），叶子数没有发生改变，但是 号点到根的路径上左走边比 号点多 。因此可以转移到 。
- 在没有补齐儿子也不是叶子的 号点下面加 号点，此时建了一个左儿子。叶子数增加 ，但是 号点到根的的路径上左走边比 号点少 。因此可以转移到 。
于是有 DP 转移：
注意 ，当 时这个状态是无效的，当做 处理。
这时可能会有疑问： 号点的左儿子怎么处理？在建立了 的右儿子 后，我们一定要保证最后的答案状态下 号点（代指所有没有左儿子的非叶子节点）的左儿子都要有。换句话说，到底哪些状态才是答案状态？
考虑到第二种转移是在补齐没有左儿子的点的左儿子，当 时，说明此时这个点到根的路径上没有左走。因此只有可能是当前考虑的节点是根节点或根节点的若干重左儿子。注意到第二个转移是“补齐”了没有左儿子的点，说明这个点在进行第二个转移时说明它原本已经有一个右儿子了，转移的时候让它两个儿子都有了。于是 的情况说明这个树已经合法了（为什么只要根和根的几重左儿子有右儿子就合法？因为 的情况一定是由第二种转移得到的，说明其他点已经补齐了）。
因此答案就是 。代码如下：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=5003,mod=998244353;
inline int read(){
int x=0;bool w=0;char c=getchar();
while(c<'0' || c>'9') w|=c=='-',c=getchar();
while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return w?-x:x;
}
inline void write(int x){
if(x<0) x=-x,putchar('-');
if(x>9) write(x/10);
putchar(x%10^48);
}
int n,m,f[max_n][max_n]; // DP 数组
signed main(){
m=read(),n=read(),f[1][0]=1; // 初始化，该状态表示只有一个节点
for(register int i=1;i<=n;++i) // 一棵树不可能是 0 叶子，从 1 开始循环
for(register int j=0;j<m;++j){ // j=0 是答案状态，不能漏掉，从 0 开始循环
if(j>0){
f[i][j]+=f[i][j-1],
f[i][j]%=mod;
}
f[i][j]+=f[i-1][j+1],
f[i][j]%=mod;
} // 转移
for(register int i=1;i<=n;++i)
write(f[i][0]),putchar('\n');
return 0;
}
T3：普
给定一个长度为 的序列 。定义一个序列的权值是该序列第奇数项的数之和减去第偶数项的数之和（从 编号）。求 中所有长度为 的子序列中的最大权值。对于所有 ，都要求其答案。。
这里有一个重要的结论：设 为 的一个答案对应的子序列，那么一定存在一种情况，满足 是 的子集。这个结论证明非常不好证，有意愿的可以自行分类讨论证明。（我才不会告诉你是我不会证）
此时可以考虑用 CDQ 分治处理这个题目。设 表示 CDQ 分治递归到了第 层，此时 CDQ 分治的左端点为 ，以 为起点 为终点的最优答案。其中 表示第奇数个的系数为 ，第偶数个的系数为 ； 表示第奇数个的系数为 ，第偶数个的系数为 。
每次转移的时候，因为一个点在 一层内最多只会属于一段区间，且一定会属于一段区间。这段区间往下递归的时候左端点是固定的。因此分层转移时，在区间范围内找出若干个数字（设为 ），并转移到 处。具体地说，应该在 和 这两段区间里面找数字填进去。为什么是 而不是 ，因为有可能选出来的数字在目前子序列第一个数左边，或最后一个数右边。
代码如下：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=500005,inf=10000000000000000LL;
inline int read(){
int x=0;bool w=0;char c=getchar();
while(c<'0' || c>'9') w|=c=='-',c=getchar();
while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return w?-x:x;
}
inline void write(int x){
if(x<0) x=-x,putchar('-');
if(x>9) write(x/10);
putchar(x%10^48);
}
int n,a[max_n];
int f[20][3][max_n];
inline void cdq(int x,int l,int r){ // cdq 分治
if(l==r){ // 边界
f[x][0][l]=a[l],
f[x][1][l]=-a[l];
return;
}
int mid=(l+r)>>1,L=mid-l+1,R=r-mid;
cdq(x+1,l,mid),
cdq(x+1,mid+1,r);
for (register int i=0;i<=1;++i){ // 这里的 i 其实是题解的 t
int l2=0,r2=0;
while (l2<L || r2<R){
int jl,jr,mx=-inf,dn=max(0LL,l2-2),up=min(L,l2+2);
// 这里要是没有取max和min就可能会从不合法下标开始找
for(register int j=dn;j<=up;++j){
int k=l2+r2-j+1; // 确定下标
if(k<0 || k>R) continue; // 不合法
int res=0;
if(j) res+=f[x+1][i][l+j-1];
if(k) res+=f[x+1][(j&1)^i][mid+k]; // 转移
if(res>mx){ // 更新最优转移的答案
mx=res,
jl=j,
jr=k;
}
}
l2=jl,r2=jr;
f[x][i][l+jl+jr-1]=mx;
}
}
}
signed main(){
n=read();
for(register int i=1;i<=n;++i)
a[i]=read();
cdq(0,1,n);
for(register int i=1;i<=n;++i)
write(f[0][0][i]),putchar(' ');
return 0;
}
总的复杂度在 CDQ 上，是 的。
