A

by ?

B

by ?

• 先Floyd求出两两之间最短路。
• 二分答案，新建一个图，<=x点对连距离为1的边
• 再施展Floyd，判断，最远两点距离<=k

C

by ?

概率DP

• 第一问，以逆序对个数作为状态。
• 第二问，每种排列作为一个状态。

D

by ?

删掉一些边，答案等于2乘以剩下的边，边权之和。

比赛的时候写了个贪心，显然不对，但这样居然过！

应该拿DP搞，提起一个度数大于等于2的节点作为根。用dp[u][cnt]表示在以u为根的子树中，删除cnt条边，且保证图连通，最大的权值和。

然后就是一个树形dp+背包了。对一个节点的儿子做一次背包就好。另外当size[u]=cnt时，dp[u][cnt]=Sum cost of subtree of u

#include 
    
     #include 
     
      #include 
      
       using namespace std;typedef long long LL;typedef pair
       
         pii;const int INF=1000000007;const int N = 10000+10;int t,n,k;vector
        
          g[N];LL dp[N][22],cost[N],size[N],costSum[N];void process(int u,int p){    size[u]=1, costSum[u]=cost[u];    for(auto x:g[u]) if(x.first!=p){        cost[x.first] = x.second;        process(x.first,u);        size[u]+=size[x.first];        costSum[u]+=costSum[x.first];    }}LL dfs(int u,int cnt,int p){    if(dp[u][cnt]!=-1) return dp[u][cnt];    LL res=0,son=0;    LL f[g[u].size()+1][22];    for(int i=0;i<=cnt;i++) f[0][i]=0;    for(auto x:g[u]) if(x.first!=p){        ++ son;        for(int i=0;i<=cnt;i++) {            f[son][i]=0;            for(int j=0;j<=i;j++) if (i-j<=size[x.first])                f[son][i]=max(f[son-1][j]+dfs(x.first,i-j,u),f[son][i]);        }    }    res = f[son][cnt];    if(cnt==size[u]) res=costSum[u];    //printf("u=%d, cnt=%d, res=%d\n", u, cnt, res);    return dp[u][cnt]=res;}int main() {    scanf("%d",&t);    while(t--) {        scanf("%d%d",&n,&k);        memset(dp,-1,sizeof(dp));        LL sum=0;        for(int i=1;i<=n;i++) g[i].clear();        for(int i=1;i
         
          =1) printf("0\n"); else printf("%d\n", g[1][0].second*2); continue; } int rt=-1; for(int i=1;i<=n;i++) if(g[i].size()>=2) rt=i; cost[rt]=0; process(rt,-1); sum -= dfs(rt,k,-1); cout<<(2LL*sum)<
         
        
       
      
     
    

E

by ?

建炒鸡汇点，跑最短路就好了。

F

by ?

直接分解因数，暴力check

G

by ?

H

by ?

DFS从两侧向中间搜索。

#include 
    
     using namespace std;typedef long long LL;int t; LL n;LL dfs(LL n,LL d,bool flag){    if (d==0) {        return n==0?1:0;    }    if (d==1) {        if(n%2==1||n>=20||n<0) return 0;        return 1;    }    LL ans=0;    int x = n%10;    ans += dfs((n-x-d*x)/10, d/100, 0) * (x+1-flag);    ans += dfs((n-(x+10)-d*(x+10))/10, d/100, 0) * (9-x);    return ans;}int main() {    cin>>t;    while(t--) {        cin>>n; LL res=0;        for(LL d=1;d<=n;d*=10) {            res += dfs(n,d,1);        }        cout<
     
      <
     
    

I

by ?

枚举分界点P，答案等于max(L,R),L表示，P左端的点之间最大距离，R表示P右端的点之间的最大距离。

J

不会。

K

还没读题。

L

by ?

M

比赛半天读不懂题，囍！

其实意识到sum a=sum b这个条件，题意就该明白了吧....

然后思路......笨死了，一直卡在怎样把经过一个点的流量二等分【动态容量上限最小费用最大流问题（雾）】，再流出去。其实也意识到了这个题和流量守恒定律有一点点关系。

做法

把图分成三层。

• 第一层：A船需要的零件。
• 第二层：M个模板。
• 第三次：B船需要的零件。

意识到了吗？

---

So？

• 读题优先级放高一点。
• 手算样例，及时刹车！
• 碰键盘之前尽量把思路传达清楚。

emmm...

?还是日常划水。

?还是日常捣乱。

?还是日常过神仙题。

配合得好差。