T1 沙雕题

T2

我们令sum[i][j]表示i字母在j之前出现的次数，显然，我们要使得选择区间i，j，字母a，b使得(sum[a,i]-sum[a,j])-(sum[b,i]-sum[b,j])的值最大。我们转换一下：

(sum[a,i]-sum[b,i])-(sum[a,j]-sum[b,j])

我们显然要求(sum[a,j]-sum[b,j])的最小值，这样我们就可以愉快的dp了！

收获：

暴力dp的式子往往通过移项等等操作就能优化一下。

T3

是一道神题：我们考虑暴力：枚举每一朵花，bfs找到其能覆盖的点。但是这棵树有5000000个点！显然我们不能求出每一朵花能到达的点。我们考虑一下性质：如果一个点是两个相距最远的花都能到达的点，那么这个点就一定能到达所有的花：显然得证。考虑找两颗相距最远的花：我们可以通过寻找树的直径的方式来找：两遍bfs就可以了。

code：

// luogu-judger-enable-o2// luogu-judger-enable-o2#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          //#define int long long using namespace std;const int maxn=5000006;int head[maxn*2],cur,cnt,ans;struct hzw{ int to,next; }e[maxn*2]; int n,k,dd,d[maxn],flo[maxn];inline void add(int a,int b){ e[cur].to=b; e[cur].next=head[a]; head[a]=cur++;}typedef pair
          
           p;bool vis[maxn],pan[maxn];int fina,mx,col[maxn];inline void bfs1(int now){ queue
           
q; memset(vis,0,sizeof(vis)); fina=0; mx=-23333; q.push(p(now,0)); while (!q.empty()) { p all=q.front(); q.pop(); int s=all.first,cost=all.second; vis[s]=1; if (pan[s]&&cost>mx) { mx=cost; fina=s; } for (int i=head[s];i!=-1;i=e[i].next) { int vv=e[i].to; if (vis[e[i].to]) continue; q.push(p(e[i].to,cost+1)); } }}inline void bfs2(int now){ queue
           
q; memset(vis,0,sizeof(vis)); mx=-23333; q.push(p(now,0)); while (!q.empty()) { p all=q.front(); q.pop(); int s=all.first,cost=all.second; vis[s]=1; if (cost<=dd) { col[s]++; } for (int i=head[s];i!=-1;i=e[i].next) { int vv=e[i].to; if (vis[e[i].to]) continue; q.push(p(e[i].to,cost+1)); } }}signed main(){ // freopen("blossom.in","r",stdin);// freopen("blossom.out","w",stdout); memset(head,-1,sizeof(head)); cin>>n>>k>>dd; for (int i=1;i<=k;++i) { scanf("%d",&flo[++cnt]); pan[flo[cnt]]=1; } for (int i=1,a,b;i<=n-1;++i) { scanf("%d%d",&a,&b); add(a,b); add(b,a); } bfs1(1); int tmp=fina; bfs1(fina); bfs2(fina); bfs2(tmp); for (int i=1;i<=n;++i) { if (col[i]==2) ans++; } cout<
          
         
        
       
      
     
    

收获：一些看似不可能维护的信息可以考虑观察性质，用局部代替整体