T1
考试假贪心，20pts，能摧毁就摧毁，不管前边已经摧毁的水晶。
正解：
首先肯定要离散化，然后考虑dp,设 \(dp_{i,j}\) 表示当前处理到了i，摧毁掉的水晶的a最小为j，则转移方程：
\[a_{i}\le b_{i} \] \[dp_{i,a_{i}}=\max\left(dp_{i-1,b_{i+1}},dp_{i-1,b_{i+2}}...dp_{i-1,MAX}\right)+1 \] \[a_{i}< b_{i} \] \[dp_{i,a_{i}}=\max\left(dp_{i-1,a_{i}+1},dp_{i-1,a_{i+2}}...dp_{i-1,MAX}\right)+1 \]直接转移有60pts。
考虑优化，我们发现，第二维可放到线段树上去维护，转移就可以通过区间取最值，单点修改，区间加来完成。
有个sb坑点，单点修改的时候记得判断点是否比离散化后的点数大，如果大，则没有能够用来更新的它的点，直接break，或者一开始建树的时候，让右端点大一亿些
Code
#include<cstdio>
#include<algorithm>
#define MAX 100010
#define re register
namespace OMA
{
int a[MAX],b[MAX];
int n,cnt,tmp[MAX<<1];
inline int read()
{
int s=0,w=1; char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); }
while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); }
return s*w;
}
struct Segment_Tree
{
struct TREE
{
int val;
int l,r;
int lazy;
}st[MAX<<4];
inline int ls(int p)
{ return p<<1; }
inline int rs(int p)
{ return p<<1|1; }
inline int max(int a,int b)
{ return a>b?a:b; }
inline void Push_up(int p)
{ st[p].val = max(st[ls(p)].val,st[rs(p)].val); }
inline void Push_down(int p)
{
if(st[p].lazy)
{
st[ls(p)].val += st[p].lazy;
st[rs(p)].val += st[p].lazy;
st[ls(p)].lazy += st[p].lazy;
st[rs(p)].lazy += st[p].lazy;
st[p].lazy = 0;
}
}
inline void build(int p,int l,int r)
{
st[p].l = l,st[p].r = r;
if(l==r)
{ return ; }
int mid = (l+r)>>1;
build(ls(p),l,mid),build(rs(p),mid+1,r);
}
inline int query(int p,int l,int r)
{
if(l<=st[p].l&&st[p].r<=r)
{ return st[p].val; }
int xam = 0,mid = (st[p].l+st[p].r)>>1;
Push_down(p);
if(l<=mid)
{ xam = max(xam,query(ls(p),l,r)); }
if(r>mid)
{ xam = max(xam,query(rs(p),l,r)); }
return xam;
}
inline void update1(int p,int pos,int val)
{
if(pos==st[p].l&&st[p].r==pos)
{ st[p].val = max(st[p].val,val); return ; }
int mid = (st[p].l+st[p].r)>>1;
Push_down(p);
if(pos<=mid)
{ update1(ls(p),pos,val); }
if(pos>mid)
{ update1(rs(p),pos,val); }
Push_up(p);
}
inline void update2(int p,int l,int r)
{
if(l<=st[p].l&&st[p].r<=r)
{ st[p].val++,st[p].lazy++; return ; }
int mid = (st[p].l+st[p].r)>>1;
Push_down(p);
if(l<=mid)
{ update2(ls(p),l,r); }
if(r>mid)
{ update2(rs(p),l,r); }
Push_up(p);
}
}Tree;
signed main()
{
n = read();
for(re int i=1; i<=n; i++)
{ tmp[++cnt] = a[i] = read(),tmp[++cnt] = b[i] = read(); }
std::sort(tmp+1,tmp+1+cnt);
cnt = std::unique(tmp+1,tmp+1+cnt)-tmp;
for(re int i=1; i<=n; i++)
{
a[i] = std::lower_bound(tmp+1,tmp+1+cnt,a[i])-tmp;
b[i] = std::lower_bound(tmp+1,tmp+1+cnt,b[i])-tmp;
}
Tree.build(1,1,cnt+cnt);
for(re int i=n; i>=1; i--)
{
int val;
if(a[i]<=b[i])
{
val = Tree.query(1,1,a[i])+1;
//if(b[i]+1>cnt)
//{ continue ; }
Tree.update1(1,b[i]+1,val);
}
else
{
val = Tree.query(1,1,b[i])+1;
Tree.update1(1,b[i],val),Tree.update2(1,b[i]+1,a[i]);
}
}
printf("%d\n",Tree.st[1].val);
return 0;
}
}
signed main()
{ return OMA::main(); }
T2
没改出来，咕了，正解是主席树。
T3
正解是sbdp。
设 \(dp_{i,j}\) 表示处理到i位置，长度为j的方案数，那么转移方程：
方程右侧前两项统计方案数，后一项做减法，容斥掉重复的。其中 \(p_{i}\) 表示该字符上一次出现的位置。别忘了取模。
Code
#include<cstdio>
#include<cstring>
#define MAX 3010
#define re register
namespace OMA
{
char s[MAX];
int p[MAX],d;
int dp[MAX][MAX];
const int mod = 998244353;
inline int min(int a,int b)
{ return a<b?a:b; }
signed main()
{
scanf("%s%d",s+1,&d);
int len = strlen(s+1);
for(re int i=1; i<=len; i++)
{
dp[i][0] = 1;
for(re int j=i-1; j>=1; j--)
{
if(s[j]==s[i])
{ p[i] = j; break ; }
}
}
dp[0][0] = dp[1][1] = 1;
for(re int i=2; i<=len; i++)
{
for(re int j=1; j<=min(i,d); j++)
{
dp[i][j] = dp[i-1][j]+dp[i-1][j-1];
if(p[i])
{ dp[i][j] -= dp[p[i]-1][j-1]; }
dp[i][j] = (dp[i][j]%mod+mod)%mod;
}
}
printf("%d\n",dp[len][d]);
return 0;
}
}
signed main()
{ return OMA::main(); }