T1 能量获取
简单的树形 DP，设 $dp_{i,j}$ 表示向 $i$ 节点传递了 $j$ 点能量并全部花费完后能激活的封印石的数量。
显然有：$ans=\sum \max_{j=0}^{j\leq W_i}{dp_{i,j}}(i \in son_0)$，转移的初始状态为 $dp_{i,E_i}=E_i$。
设当前枚举到的节点为 $x$，子节点为 $y$，有经典树上背包转移式：$dp_{x,i}=\max_{j=0}^{j\leq \min(W_j,i)}{dp_{y,j},dp_{x,i-j}}(0\leq i \leq W_x)$。
主要代码如下，时间复杂度 $O(nV_w)$(100pts)：
#define N 1005
vector<int> v[N];//v存储树
int n,sum,ans,e[N],w[N],dp[N][105];
void dfs(int x,int fa){
dp[x][e[x]]=1;
for(auto y:v[x]){
if(y==fa) continue;
dfs(y,x);
for(int i=100;i>=0;i--)
for(int j=min(i,w[y]);j>=0;j--)
dp[x][i]=max(dp[x][i],dp[x][i-j]+dp[y][j]);
}
}
int main(){
for(auto x:v[0]){
ans+=sum,sum=0,dfs(x,0);
for(int i=0;i<=w[x];i++) sum=max(sum,dp[x][i]);
}
printf("%d\n",ans+sum);
}
T2 封印一击
设 $sum_i$ 表示封印力度为 $i$ 时的总能量值，则有 $ans=max{sum_i}$。
考虑枚举 $i$，我们用 $in$ 表示 $i$ 被包含在了多少个区间的 $(l,r]$ 中间，则有如果 $i$ 不为任何一个区间的端点时的转移：$sum_i=sum_{i-1}+in$。
对于 $i$ 为一个区间的左端点的情况，我们只需要在 $sum_i$ 计算完毕后 ++$in$ 就可以了。
而对于 $i$ 为一个区间的右端点个情况，我们不仅需要在 $sum_i$ 计算完毕后 --$in$，还需要在 $ans$ 和 $sum_i$ 取了最大值过后，将 $sum_i$ 减去一个 $i$ 值，因为这个区间无法对后面产生贡献了。
这样的时间复杂度是 $O(V)$ 的，我们考虑怎么优化。
已知只有在 $i$ 作为一个区间的左右端点时，才会对 $in$ 以及 $sum$ 的转移产生影响。
所以我们枚举的 $i$ 值就只需要是区间的左右端点了，而 $sum$ 的转移则变成了：$sum_i=sum_{lst}+in*(i-lst)$。
以上就是全部做法了，注意本体的坑点：$ans$ 和 $num$ 的初始化：$ans=\sum a_i$，$num=1$，不然如果只有一个区间的话，将 $ans$ 初始化为 $0$ 就会挂掉。
不多说了，代码贴在下面,时间复杂度 $O(n\log n)$，瓶颈在排序：
#define N 100005
#define LL long long
LL lst,sum,ans;
int n,in,num=1,a[N],b[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",a+i,b+i),sum+=a[i];
ans=sum,sort(a+1,a+n+1),sort(b+1,b+n+1);
for(int i=1,j=1;j<=n;){
if(i<=n&&a[i]<=b[j])
sum+=(a[i]-lst)*in,lst=a[i],in++,i++;
else{
sum+=(b[j]-lst)*in;
if(sum>ans) ans=sum,num=b[j];
lst=b[j],in--,sum-=b[j],j++;
}
}
printf("%d %lld\n",num,ans);
}
T3 归途与征程
我们可以发现题意是可以被转化的：对于 $A$ 中所有被 '*' 分割开的字符串，我们需要在 $B$ 的循环同构串，找到每个字符串对应的 $B$ 中子串。
且这些子串要满足条件：不能互相重叠，且起始位置的顺序要与对应字符串在 $A$ 中的顺序相同。
所以题目要求的就是有多少个 $B$ 的循环同构串能达成以上的条件。
考虑通过 KMP 找到所有的字符串在 $B$ 中的所有匹配位置，并用一个 bool 数组 $cld$ 存储起来。
接下来对于所有 $B$ 循环同构串，我们可以通过 DP 来判断是否条件，但这样太慢了，复杂度不满足，所以我们要考虑如何加速。
用数组 $nxt_{i,j}$ 记录 $A$ 中的第 $i$ 个串，在 $B$ 中出现的第一个大于等于 $j$ 的位置，这个数组可以通过 $cld$ 计算求出。
然后对于每个同构串，我们就可以枚举 $A$ 中的每个串，判断在上一个串的位置之后是否有当前枚举的这个串，如果都有就 $ans$++。
值得注意的是，如果 $A$ 的第一个字符不是 "*"，那么 $A$ 中的第一个串就必须出现在 $B$ 的开头。
同样，如果 $A$ 的最后字符不是 "*"，那么 $A$ 中的最后一个串就必须出现在 $B$ 的末尾。
这道题就是这样了，时间复杂度 $O(nm)$，代码贴在下面，具体细节看代码(100pts)：
#define N 105
#define M 200005
char a[N],b[M];
int n,m,lst,ans,cnt,len[N],Next[M],cld[N][M],nxt[N][M];
void get_next(char* p,int plen){//求字符串p的Next值，或者叫pi值
Next[0]=Next[1]=0;
for(int i=1;i<plen;i++){
int j=Next[i];
while(j&&p[i]!=p[j]) j=Next[j];
Next[i+1]=(p[i]==p[j])*(j+1);
}
}
void KMP(char* s,char* p,int slen,int plen,int pos){//在字符串s中匹配字符串p
get_next(p,plen);
for(int i=0,j=0;i<slen;i++){
while(j&&s[i]!=p[j]) j=Next[j];
if(s[i]==p[j]) j++;
if(j==plen) cld[pos][i-plen+1]=1;
}
}
int main(){
scanf("%s%s",a,b),n=strlen(a),m=strlen(b),a[n]='*';
for(int i=m;i<m+m-1;i++) b[i]=b[i-m];
for(int i=0;i<=n;i++){
if(a[i]=='*'){
if(i!=lst){
KMP(b,a+lst,m+m-1,i-lst,++cnt);
nxt[cnt][m+m-1]=m+m-1,len[cnt]=i-lst;
for(int j=m+m-2;j>=0;j--){
nxt[cnt][j]=nxt[cnt][j+1];
if(cld[cnt][j]) nxt[cnt][j]=j;
}
}
lst=i+1;
}
}
for(int l=0;l<m;l++){
int r=l+m-1,now=l;
if(a[0]!='*'&&!cld[1][l]) continue;
if(a[n-1]!='*'&&!cld[cnt][r-len[cnt]+1]) continue;
for(int i=1;i<=cnt;i++){
if(nxt[i][now]+len[i]-1>r) goto cant;
else now=nxt[i][now]+len[i];
}
ans++;cant:;
}
printf("%d\n",ans);
}
T4 IIIDX(本题题解是此文的 Latex 修复版本)
转载声明：本题题解是此文的 Latex 修复版本，也是全文唯一一篇转载题解，因为原作者写的是真的很好，所以选择了转载。
首先有一个比较明显的 60pts 贪心：
先把 $d$ 排好序，然后按从小到大的顺序贪心的给每个点选值，同等条件下优先编号大的，于是越小的值会越趋近于放在编号越大的上面。
但是这样在数字重复的情况下是不对的， 比如下面这组数据：
4 3.0
1 1 2 2
贪心会得到 1 1 2 2,而正确答案是 1 2 2 1。
因此换个角度考虑，在什么情况下一个点可以取到一个值 $x$？
设这个点的子树大小为 $Size_i$,那么这个点可以取到值 $x$，当且仅当大于等于 $x$ 的还没被取的值的个数 $\geq Size_i$，原因应该是很好理解的，毕竟还要有 $Size_i-1$ 和比 $x$ 大的值放在 $i$ 的子树上才行。
因此我们先对 $d$ 从小到大排序去重，统计每个值的出现次数 $cnt_x$, 然后对于每个数统计一个 $f_x$ 表示大于等于x的还没被取的值的个数为 $f_x$.
假设我们给节点 $i$ 匹配上了一个值 $x$，那么这个策决策对小于等于 $x$ 的值的影响是确定的，因此将所有小于等于 $x$ 的值的 $f$ 数组都减小 $Size_i$,表示这些值的右边可以取的值又减小了 $Size_i$ 个。
我们将和这个操作称为“预定”，因为我们现在并不知道点 $i$ 的子树分别会选择哪些值，但我们知道它们要选几个值，所以我们相当于先告诉后面的人，这个节点 $i$ 已经坐到了 $x$ 这个值上，并且要求后面的人为它的子树留 $Size_i-1$ 个座位。
因为这个决策对大于 $x$ 的值的影响是不确定的，我们暂时没有修改它，但其实这个决策会对它产生影响，那么对于一个值 $k$，在取它之前的决策到底对它产生了什么样的影响呢？
对于一个值 $k$，它的真正的 $f_k$ 其实是 $\min_{i=1}^n{f_i}$，因为每个 $f$ 值都相当于一个后缀和，一个合法的值不能使得 $f_k$ 反而比它前面的 $f$ 值更大，因为前面的 $f$ 值要比 $f_k$ 统计了更多的数。
因为题目要求使得字典序最大，所以我们按照编号从小到大给节点分配值显然是最优的。
因此我们每次就是要在剩下的数上寻找一个最靠右的，并且使得 $\min_{i=1}^n{f_i} \geq Size_i$ 的 $k$。
因为涉及区间修改和查询，我们使用线段树来维护所有的 $f$ 值，每次选好一个值，我们就把一些已经确定的影响从线段树中删除（对一个区间进行 $-Size_i$ 的操作）。
对于每次选值，我们都可以在线段树上进行二分来查找满足上述粗体字要求的最靠右的值。
值得注意的是，在每次查询前，如果一个节点的父亲的影响还没有被撤销的话，应该要撤销它父亲的影响。（即把父亲给子树占的座给加回来 ：给 $1$ 到父亲匹配值的 $f$ 值加上 $Size_{fa}-1$）
为什么呢？
想象一下，如果不撤销父亲的影响的话，岂不是相当于别人特意给你占了座，结果你自己还不能坐上去？
因为一个节点的儿子都是连续的，所以我们在撤销的父亲的影响后，会马上把不应该撤销的部分给补上（儿子的子树在不断的加上来），所以不用担心对之后的决策造成影响。
代码如下(代码是贴的我的代码，因为原作者码风有些许诡异，100pts)：
#define N 500005
double k;
bool vis[N];
int n,tot,d[N],fa[N],sz[N],cnt[N],ans[N];
struct Segment_tree{//维护区间最小值
int tr[N<<2],tag[N<<2];
void build(int l,int r,int p){
if(l==r) return tr[p]=cnt[l],void();
int mid=(l+r)>>1,ls=p<<1,rs=p<<1|1;
build(l,mid,ls),build(mid+1,r,rs),tr[p]=min(tr[ls],tr[rs]);
}
void pushdown(int p,int ls,int rs){
for(auto son:{ls,rs}) tr[son]+=tag[p],tag[son]+=tag[p];
tag[p]=0;
}
void update(int sl,int sr,int x,int l,int r,int p){
if(sl<=l&&r<=sr) return tr[p]+=x,tag[p]+=x,void();
int mid=(l+r)>>1,ls=p<<1,rs=p<<1|1;
pushdown(p,ls,rs);
if(sl<=mid) update(sl,sr,x,l,mid,ls);
if(sr>mid) update(sl,sr,x,mid+1,r,rs);
tr[p]=min(tr[ls],tr[rs]);
}
int query(int x,int l,int r,int p){//线段树二分第一个满足min(cnt[1],cnt[2]...cnt[i])>=x的点
if(l==r) return (tr[p]<x?l-1:l);
int mid=(l+r)>>1,ls=p<<1,rs=p<<1|1;
pushdown(p,ls,rs);
if(tr[ls]>=x) return query(x,mid+1,r,rs);
return query(x,l,mid,ls);
}
}SGT;
int main(){
scanf("%d%lf",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",d+i);
sort(d+1,d+n+1);
for(int i=1;i<=n;i++){
if(d[i]!=d[i-1]) d[++tot]=d[i];//去重
cnt[tot]++;
}
for(int i=tot;i>0;i--) cnt[i]+=cnt[i+1];//cnt是>=d[i]的数
SGT.build(1,tot,1);
for(int i=n;i>0;i--) sz[i]++,fa[i]=int(i/k),sz[fa[i]]+=sz[i];//处理父子关系
for(int i=1;i<=n;i++){//下一行是为了解除预先占的位，注意每个结点的占位直接出一次，所以用了vis数组
if(fa[i]&&!vis[fa[i]]) vis[fa[i]]=1,SGT.update(1,ans[fa[i]],sz[fa[i]]-1,1,tot,1);
vis[fa[i]]=1,ans[i]=SGT.query(sz[i],1,tot,1),SGT.update(1,ans[i],-sz[i],1,tot,1);//占位及得出答案
}
for(int i=1;i<=n;i++) printf("%d ",d[ans[i]]);
}