其实……这篇是真咕了。
反思：
××我$T1$两个小时构造$xiebi$了（虽然我觉得如果干仨小时可能行？）
……如果$T1$用时过长的话那考试多半不行……
结果：
|
35
|
Miemeng | 50
03:08:09
|
0
03:08:09
|
20
03:08:10
|
70
03:08:10
|
T1显然交的暴力……
题解:
T1
好题
构造一下，分分块就可以辣。
#include <iostream>
#include <cstring>
#include <cstdio>
#define N 111111
using namespace std;
int nn,un,dn;
int arr[N];
int epl[N];
void revset(int l,int r){
for(int i=l,j=r;i<=r;i++,j--)
arr[i]=j;
}
int main(){
int T;
cin>>T;
while(T--){
scanf("%d%d%d",&nn,&un,&dn);
if(un*dn>=nn && un+dn<=nn+1){
puts("Yes");
revset(nn-dn+1,nn);
if(un-1!=0){
int pl=(nn-dn)/(un-1),
pn=un-1,
prn=nn-dn-pl*pn;
for(int i=1;i<=pn;i++)
epl[i]=pl;
for(int i=1;i<=prn;i++)
epl[i]++;
// for(int i=1;i<=pn;i++)
cout<<epl[i]<<" ";
cout<<endl;
for(int i=1;i<=pn;i++)
epl[i]=epl[i]+epl[i-1];
for(int i=1;i<=pn;i++){
// cout<<epl[i-1]+1<<" "<<epl[i]<<endl;
revset(epl[i-1]+1,epl[i]);
}
}
for(int i=1;i<=nn;i++)
printf("%d ",arr[i]);
puts("");
}
else puts("No");
}
}
T2
性质题，通过找规律证明了有一段不连续的区间并求解。
至于证明请去模大佬的博客（右方翻友链）
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define N 111111
#define LL long long
using namespace std;
int nn;
LL arr[N],
pre[N],
ans;
int main(){
scanf("%d",&nn);
for(int i=1;i<=nn;i++)
scanf("%lld",arr+i);
sort(arr+1,arr+nn+1);
for(int i=1;i<=nn;i++)
pre[i]=pre[i-1]+arr[i];
ans=pre[nn]-(arr[1]-1)/2;
for(int i=2;i<=nn;i++){
if((arr[i]-1)/2>pre[i-1])
ans-=(arr[i]-1)/2-pre[i-1];
}
printf("%lld
",ans);
}
T3
二叉树计数可得$20$
正解$dp$
将树上的位置关系转化成子树的大小关系。
（显然我是水果的……）
#include <iostream>
#include <cstring>
#include <cstdio>
#define LL long long
#define N 888
using namespace std;
const int Mod=1e9+7;
LL dp[N][N];
int pn,lin,minn[N],maxn[N];
int main(){
int T,a,b;
cin>>T;
while(T--){
memset(dp,0,sizeof dp);
scanf("%d%d",&pn,&lin);
for(int i=1;i<=pn;i++)
minn[i]=0,maxn[i]=pn;
for(int i=1;i<=lin;i++){
scanf("%d%d",&a,&b);
if(a<b){
// for (int i=1; i<x; ++i) mn[i]=max(mn[i],i-x);
maxn[a]=min(maxn[a],b-a-1);
}//minn[a]=max(minn[a],b-a-1);
else minn[b]=max(minn[b],a-b);
}
for(int i=1;i<=2*pn+1;i++)
dp[i][0]=1;
for(int i=pn;i>=1;i--){
for(int j=1;j<=pn;j++){
for(int k=minn[i];k<=min(maxn[i],j);k++){
if(j-1-k<0)break;
dp[i][j]=(dp[i][j]+dp[i+1][k]*dp[i+1+k][j-1-k]%Mod)%Mod;
}
}
}
printf("%lld
",dp[1][pn]);
}
}