依然倒一，虽然比上次完全不会强一些了，但是挂了一堆分……
T1
奇怪地挂掉了，但是也反映了代码能力还是不行，求个子树内最大最小都要错，而且还把问题复杂化了。就是先并查集找根，记录子树内最值然后看子树大小等不等于极差就完事儿了，没那么多别的。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=114514,M=1919810,inf=1145141919810;
struct xx{
ll next,to;
}e[2*N];
ll head[2*N],cnt;
void add(ll x,ll y){
e[++cnt].next=head[x];
e[cnt].to=y;
head[x]=cnt;
}
ll f[N];
ll find(ll x){
return x==f[x]?x:f[x]=find(f[x]);
}
ll mx[N],mn[N],siz[N],n,ans,rt;
void dfs(ll u){
mx[u]=mn[u]=u,siz[u]=1;
for(int i=head[u];i;i=e[i].next){
ll v=e[i].to;
dfs(v);
siz[u]+=siz[v];
mx[u]=max(mx[u],mx[v]);
mn[u]=min(mn[u],mn[v]);
}
if(mx[u]-mn[u]+1==siz[u]) ++ans;
}
int main(){
//freopen("A.in","r",stdin);
//freopen("A.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i) f[i]=i,mx[i]=0,mn[i]=inf;
for(int i=1;i<n;++i){
ll a,b;
cin>>a>>b;
add(a,b);
ll x=find(a),y=find(b);
if(x!=y) f[y]=x;
}
rt=find(1);
dfs(rt);
cout<<ans;
return 0;
}
T2
这个题其实是做过类似的，但是之前做那个题的时候就没怎么搞清楚，然后吃亏了，问题显露出来了，而且想法其实已经比较逼近正解了，就是 DP 能力不够。我们设 \(dp_{i,j}\) 表示 DP 到第 \(i\) 位，前 \(i\) 位填 \(\mathbf{1}\sim i\) 并且这位为 \(j\) 时的方案数。其实思路很显然，考虑刷表法，我们枚举上一位填什么数，然后直接求和就行了，具体而言枚举 \(dp_{i-\mathbf{1},k}\)，若上一位是上升则 \(dp_{i,j}=\sum\limits_{k=\mathbf{1}}^{j-\mathbf{1}}dp_{i-\mathbf{1},k}\)，下降则是 \(dp_{i,j}=\sum\limits_{k=j}^{i-\mathbf{1}}dp_{i-\mathbf{1},k}\)，如果是问号就全部求和，考虑维护一个前缀和去掉这个枚举 \(k\) 的过程，复杂度 \(O(n^{\mathbf{2}})\) 能过。我主要在思考转移上界为什么是 \(dp_{i,i-\mathbf{1}}\)，这是因为我们计算排列数地时候是没有管排列的具体形态的，每次转移的时候我们珂以看作是将 \(a_{\mathbf{1}}\sim a_i\) 的数都加上了一以此保证是个排列，这个时候不用想多了我们就珂以直接按上面的式子转移了，但是前面的数最大也就 \(i-\mathbf{1}\)，记得是从第二位开始 DP，第一位初始全设成 \(\mathbf{1}\)。
感觉写得还是有点抽象，慢慢消化罢。
顺便一说有多倍经验：AT_dp_t，UVA1650，卡老师的题 其实这个是假的要难得多。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=3001,M=1919810,mod=1e9+7;
ll n;string s;
ll dp[N][N]; //dp到第i位,第i位填j
ll sum[N][N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
while(cin>>s){
n=s.size()+1;
s=" "+s;
for(int i=0;i<=n;++i)
for(int j=0;j<=n;++j)
dp[i][j]=0;
for(int i=1;i<=n;++i) dp[1][i]=sum[1][i]=1;
for(int i=2;i<=n;++i)
for(int j=1;j<=i;++j){
if(s[i]=='I') dp[i][j]+=sum[i-1][j-1],dp[i][j]%=mod;
else if(s[i]=='D') dp[i][j]+=(sum[i-1][i-1]-sum[i-1][j-1]+mod)%mod,dp[i][j]%=mod;
else dp[i][j]+=sum[i-1][i-1],dp[i][j]%=mod;
sum[i][j]=sum[i][j-1]+dp[i][j],sum[i][j]%=mod;
}
ll ans=0;
for(int i=1;i<=n;++i) ans+=dp[n][i],ans%=mod;
cout<<ans%mod<<'\n';
}
return 0;
}
T3
这个题有难度没推出来。首先 \(O(n^\mathbf{2})\) DP 求一遍 LCS 没问题，然后如果直接模拟麻烦得要死，我们考虑再进行一遍动规，设 \(f[i][j]\) 表示在 \(A\) 串的前 \(i\) 个中和 \(B\) 串的前 \(j\) 个中的最长子序列的数量，转移：若 \(dp[i-\mathbf{1}][j]=dp[i][j]\)（注意是第一遍求的 \(dp\) 数组）则 \(f[i][j]+=f[i-\mathbf{1}][j]\) 表示不选 \(i\) 这个字符，我们再考虑找到 \(B\) 串前 \(j\) 个字符中最后面的与 \(A[i]\) 相同的位置 \(p\)，若 \(dp[i][j]=dp[i-\mathbf{1}][p-\mathbf{1}]+\mathbf{1}\) 则 \(f[i][j]+=f[i-\mathbf{1}][p-\mathbf{1}]\)，最后答案为 \(f[n][m]\)，记得边界都初始化为 \(\mathbf{1}\)
这个做不出来就是真做不出来了，都没想到去 DP 求个数，只能继续积累了，唉……
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1145,M=1919810,mod=1e9+7;
string sa,tb;
ll n,m,a[N],b[N],dp[N][N],las[N],p[26][N];
ll dp2[N][N]; //在a的前i个中和b的前j个中的最长子序列的数量
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>sa>>tb;
n=sa.size(),m=tb.size();
for(int i=1;i<=n;++i) a[i]=sa[i-1]-'a';
for(int i=1;i<=m;++i) b[i]=tb[i-1]-'a';
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
if(a[i]==b[j]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
}
memset(las,-1,sizeof(las));
for(int i=1;i<=m;++i){
las[b[i]]=i;
for(int j=0;j<26;++j) p[j][i]=las[j];
}
for(int i=0;i<=n;++i) dp2[i][0]=1;
for(int i=0;i<=m;++i) dp2[0][i]=1;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
dp2[i][j]=0;
if(dp[i][j]==dp[i-1][j]) dp2[i][j]+=dp2[i-1][j];
ll pos=p[a[i]][j];
if(dp[i-1][pos-1]+1==dp[i][j]&&pos!=-1) dp2[i][j]+=dp2[i-1][pos-1];
dp2[i][j]%=mod;
}
cout<<dp2[n][m];
return 0;
}/*abcabc abc*/