T1 地衣体

小小的贪心：每次肯定从深度较小的点向深度较大的点转移更优。

模拟一下，把边按链接点的子树最大深度排序，发现实际上只有上一个遍历到的点是对当前考虑的点有影响的，且它们的$LCA$即为当前点的父亲。$DFS$时记录即可。

$code:$

 1 #include<bits/stdc++.h>

 2 #define x first

 3 #define y second

 4 #define mp make_pair

 5 #define pb push_back

 6 using namespace std;

 7 typedef pair<int,int> ii;

 8

 9 namespace IO{

10     inline int read(){

11         int x=0,f=1; char ch=getchar();

12         while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

13         while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

14         return x*f;

15     }

16     inline void write(int x,char sp){

17         char ch[20]; int len=0;

18         if(x<0){ putchar('-'); x=~x+1; }

19         do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x);

20         for(int i=len-1;~i;i--) putchar(ch[i]); putchar(sp);

21     }

22 } using namespace IO;

23

24 const int NN=1e5+5;

25 int n,lfn,ans,pos,dep[NN],mxdep[NN];

26 bool vis[NN];

27 vector<ii>e[NN];

28

29 void dfinit(int s,int f){

30     for(int i=0;i<e[s].size();i++){

31         int v=e[s][i].y;

32         if(v==f) continue;

33         mxdep[v]=dep[v]=dep[s]+1;

34         dfinit(v,s);

35         e[s][i].x=mxdep[v];

36         mxdep[s]=max(mxdep[s],mxdep[v]);

37     }

38     sort(e[s].begin(),e[s].end());

39 }

40 void solve(int s,int f){

41     if(!pos) ans+=dep[s];

42     else ans+=dep[s]<(dep[s]+dep[pos]-2*dep[f])?dep[s]:(dep[s]+dep[pos]-2*dep[f]);

43     pos=s;

44 }

45 void dfs(int s,int f){

46     solve(s,f);

47     for(int i=0;i<e[s].size();i++){

48         int v=e[s][i].y;

49         if(v==f) continue;

50         dfs(v,s);

51     }

52 }

53 signed main(){

54     n=read();

55     for(int a,b,i=1;i<n;i++){

56         a=read(); b=read();

57         e[a].pb(mp(0,b));

58         e[b].pb(mp(0,a));

59     }

60     dfinit(1,0);

61     dfs(1,0);

62     write(ans,'\n');

63     return 0;

64 }

T2 帝儿啼

二分答案，可以运用$spfa$思想，迭代最终必将收敛，每次暴力扫描修改，直到所有点符合$mid$或不能再改。

考场上以为复杂度炸了，数组只开了$500$，讲题时听到这种方法能$A$人都傻了。。。

$code:$

 1 #include<bits/stdc++.h>

 2 #define int long long

 3 using namespace std;

 4

 5 namespace IO{

 6     inline int read(){

 7         int x=0,f=1; char ch=getchar();

 8         while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

 9         while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

10         return x*f;

11     }

12     inline void write(int x,char sp){

13         char ch[20]; int len=0;

14         if(x<0){ putchar('-'); x=~x+1; }

15         do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x);

16         for(int i=len-1;~i;i--) putchar(ch[i]); putchar(sp);

17     }

18 } using namespace IO;

19

20 const int NN=1e5+5;

21 int r,c,k,a[NN],L,R,ans,ext;

22 inline int id(int x,int y){ return (x-1)*c+y; }

23 bool check(int mid){

24     bool flag=1;

25     int kk=k,tmp[NN];

26     for(int i=1;i<=ext;i++) tmp[i]=a[i];

27     while(kk>=0&&flag){

28         flag=0;

29         for(int i=1;i<=r;i++) for(int j=1;j<=c;j++){

30             int now=id(i,j);

31             if(i>1) if(tmp[id(i-1,j)]-tmp[now]>mid){

32                 flag=1;

33                 int t=tmp[id(i-1,j)]-tmp[now];

34                 tmp[now]+=t-mid; kk-=t-mid;

35                 if(kk<0) return 0;

36             }

37             if(j>1) if(tmp[id(i,j-1)]-tmp[now]>mid){

38                 flag=1;

39                 int t=tmp[id(i,j-1)]-tmp[now];

40                 tmp[now]+=t-mid; kk-=t-mid;

41                 if(kk<0) return 0;

42             }

43             if(i<r) if(tmp[id(i+1,j)]-tmp[now]>mid){

44                 flag=1;

45                 int t=tmp[id(i+1,j)]-tmp[now];

46                 tmp[now]+=t-mid; kk-=t-mid;

47                 if(kk<0) return 0;

48             }

49             if(j<c) if(tmp[id(i,j+1)]-tmp[now]>mid){

50                 flag=1;

51                 int t=tmp[id(i,j+1)]-tmp[now];

52                 tmp[now]+=t-mid; kk-=t-mid;

53                 if(kk<0) return 0;

54             }

55             if(i>1&&j<c) if(tmp[id(i-1,j+1)]-tmp[now]>mid){

56                 flag=1;

57                 int t=tmp[id(i-1,j+1)]-tmp[now];

58                 tmp[now]+=t-mid; kk-=t-mid;

59                 if(kk<0) return 0;

60             }

61             if(i<r&&j>1) if(tmp[id(i+1,j-1)]-tmp[now]>mid){

62                 flag=1;

63                 int t=tmp[id(i+1,j-1)]-tmp[now];

64                 tmp[now]+=t-mid; kk-=t-mid;

65                 if(kk<0) return 0;

66             }

67         }

68     }

69     return 1;

70 }

71 signed main(){

72     r=read(); c=read(); k=read(); ext=r*c;

73     for(int i=1;i<=r;i++) for(int j=1;j<=c;j++)

74         a[id(i,j)]=read();

75     for(int i=1;i<=r;i++) for(int j=1;j<=c;j++){

76         if(i>1) R=max(R,abs(a[id(i-1,j)]-a[id(i,j)]));

77         if(i<r) R=max(R,abs(a[id(i+1,j)]-a[id(i,j)]));

78         if(j>1) R=max(R,abs(a[id(i,j-1)]-a[id(i,j)]));

79         if(j<c) R=max(R,abs(a[id(i,j+1)]-a[id(i,j)]));

80         if(i>1&&j<c) R=max(R,abs(a[id(i-1,j+1)]-a[id(i,j)]));

81         if(i<r&&j>1) R=max(R,abs(a[id(i+1,j-1)]-a[id(i,j)]));

82     }

83     while(L<=R){

84         int mid=L+R>>1;

85         if(check(mid)) ans=mid, R=mid-1;

86         else L=mid+1;

87     }

88     write(ans,'\n');

89     return 0;

90 }

T3 滴伞涕

数位$DP$。得到区间后求以$a-1$，$b$为下界的答案最后相减。可以按数中$1$的个数分段，逐段得到答案。

预处理前$i$位选$j$个$1$，是否卡紧上下界的方案数和和，然后$DFS$。

虽然说得很简单，但写出来有些难度，但写完了还行。

$code:$

 1 #include<bits/stdc++.h>

 2 #define mp make_pair

 3 #define x first

 4 #define y second

 5 using namespace std;

 6 typedef long long LL;

 7 typedef pair<LL,LL> pii;

 8

 9 namespace IO{

10     inline int read(){

11         int x=0,f=1; char ch=getchar();

12         while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

13         while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

14         return x*f;

15     }

16     inline void write(LL x,char sp){

17         char ch[20]; int len=0;

18         if(x<0){ putchar('-'); x=~x+1; }

19         do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x);

20         for(int i=len-1;~i;i--) putchar(ch[i]); putchar(sp);

21     }

22 } using namespace IO;

23

24 const LL inf=1e18;

25 int t,l,r,a,b;

26 pii f[35][35][2][2];

27

28 pii dfs(int i,int j,bool s,bool t,LL lmt,bool flag){

29     if(i<0||j<0||!lmt) return mp(0ll,0ll);

30     if(flag&&f[i][j][s][t].x<=lmt) return f[i][j][s][t];

31     int dn=s&(l>>i),up=t&((r>>i)^1);

32     pii fr=dn?mp(0ll,0ll):dfs(i-1,j,s&(((l>>i)^1)&1),t&(((r>>i)^1)&1),lmt,1);

33     pii af=up?mp(0ll,0ll):dfs(i-1,j-1,s&((l>>i)&1),t&((r>>i)&1),lmt-fr.x,1);

34     return mp(fr.x+af.x,fr.y+af.y+af.x*(1ll<<i));

35 }

36 LL ans(int x){

37     LL res=0;

38     for(int i=0;i<=30;i++)

39         if(x>=f[30][i][1][1].x){

40             res+=f[30][i][1][1].y;

41             x-=f[30][i][1][1].x;

42         }

43         else{ res+=dfs(30,i,1,1,x,0).y;break; }

44     return res;

45 }

46 signed main(){

47     t=read();

48     while(t--){

49         l=read(); r=read(); a=read(); b=read();

50         a=r-l-a+2; b=r-l-b+2; if(a>b)swap(a,b);

51         memset(f,0,sizeof(f));

52         f[0][0][0][0]=f[0][0][0][1]=mp(1ll,0ll);

53         f[0][0][1][0]=f[0][0][1][1]=mp((l^1ll)&1ll,0ll);

54         f[0][1][0][0]=f[0][1][1][0]=mp(1ll,1ll);

55         f[0][1][0][1]=f[0][1][1][1]=mp(r&1ll,r&1ll);

56         for(int i=1;i<=30;i++) for(int j=0;j<=i+1;j++){

57             f[i][j][0][0]=dfs(i,j,0,0,inf,0);

58             f[i][j][1][0]=dfs(i,j,1,0,inf,0);

59             f[i][j][0][1]=dfs(i,j,0,1,inf,0);

60             f[i][j][1][1]=dfs(i,j,1,1,inf,0);

61         }

62         write(ans(b)-ans(a-1),'\n');

63     }

64     return 0;

65 }

T4 堤寺梯

好像有两种做法。这里讲一种（因为只会一种

定义$f_{i,j}$表示选了$i$个数，最大值为$j$的方案，$g_{i,j}$表示在最大值为$j$的基础上再选$i$个数的方案。都不难维护。

然后考虑如何得到答案。

首先考虑特定数字$x$的答案，一个序列中有$k$个$x$，对答案贡献为$k^2$，有$k^2=\binom{k}{2}\times 2+k$。

发现可以将这些贡献独立分摊到每个$x$上，类似在等式右边提出一个$k$，即为“$1+$在后面再选一个$x$的方案数”。

接下来就可以单独考虑位于$i$的$x$对答案的贡献，并乘上方案数。

（应该不难理解的）式子：

$ans_x=\sum_{i=1}^n(\sum_{y \geq x}f[i-1][y]\times (g[n-i][y]+2\times (n-i)\times g[n-i-1][y])+f[i-1][x-1]\times (g[n-i][x-1]+2\times (n-i)\times g[n-i-1][x-1]))$

后缀和优化成$O(n^2)$。

（$i=n$时$C++11$不会$RE$

$code:$

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3

 4 namespace IO{

 5     inline int read(){

 6         int x=0,f=1; char ch=getchar();

 7         while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

 8         while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

 9         return x*f;

10     }

11     inline void write(int x,char sp){

12         char ch[20]; int len=0;

13         if(x<0){ putchar('-'); x=~x+1; }

14         do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x);

15         for(int i=len-1;~i;i--) putchar(ch[i]); putchar(sp);

16     }

17 } using namespace IO;

18

19 const int NN=3005;

20 int n,m;

21 long long f[NN][NN],g[NN][NN],p[NN][NN],ans[NN];

22 signed main(){

23     n=read(); m=read(); f[0][0]=g[0][0]=1;

24     for(int i=1;i<=n;i++){

25         g[0][i]=1;

26         for(int j=1;j<=i;j++)

27             f[i][j]=(f[i-1][j]*j%m+f[i-1][j-1])%m;

28     }

29     for(int i=1;i<=n;i++)

30         for(int j=1;j<=n-i;j++)

31             g[i][j]=(g[i-1][j]*j%m+g[i-1][j+1])%m;

32     for(int i=1;i<=n;i++)

33         for(int j=i;j;j--){

34             p[i][j]=(p[i][j+1]+f[i-1][j]*(g[n-i][j]+2*(n-i)*g[n-i-1][j]%m)%m)%m;

35             ans[j]=(ans[j]+p[i][j]+f[i-1][j-1]*(g[n-i][j]+2*(n-i)*g[n-i-1][j]%m)%m)%m;

36         }

37     for(int i=1;i<=n;i++) write(ans[i],' '); puts("");

38     return 0;

39 }

巴特西

8.18考试总结[NOIP模拟43]

T1 地衣体

T2 帝儿啼

T3 滴伞涕

T4 堤寺梯

最新文章

热门文章