T1 随（Rand）

由杠哥大定理可得，这题目前不可做，先跳走啦，咕咕。。。。

T2 单（single）

考场上，简单看一眼就看出是个高斯消元，然后。。。。。

板子没记住！！！

然而这不是最糟糕的。。。。

执着的我进行了对高斯消元的推演与运行，在大把时间荒废后，发现自己终于将样例中的一半答对了！！

然而，考试接近了尾声，匆匆地蒙了下其他几个题的答案就结束了。。。

然而，高斯消元推假了。。。。

就这样达成成就———爆〇！！

其实上，这题做法比较多（部分分数），然而这题的ac代码是dfs。看了题解之后思路清晰展了，很快码完，但想想这题思维量，考上上暂时还做不到呢。。。。。

正确思路：

t=0的时候知道a数组，这时候可以求出所有点到根（1）的距离，这样可以生猛的算出b[1],

接着找（1）和他儿子们的关系，列出表达式发现以儿子（2）为根点的子树上对（2）的距离（称为贡献）都少了1，

于是，我们记录一个size数组表示以i为根节点的子树上的点权和

由于父子间的关系可以推出b[son]=b[fa]+size[1]-2*size[son];

dfs一遍就可以求出b；

t=1时，将上面柿子移项可得b[son]-b[fa]=size[1]-2*size[son]；

插一句嘴，我们可以发现b[1]=size[2]+size[3]+size[4]+...+size[n]

就和之前的那个概率期望的神仙推柿子题一样，将size展开然后合并同类项发现每个点加的次数都为那个点的深度减一，及到根节点距离；

将c[i]=size[1]-2*size[i]; i！=1；

将除了c[1]的c数组加和得： tot=(n-1)size[1]-2*(size[2]+size[3]+...+size[n])

呕吼，可以化简了！！ tot=(n-1)size[1]-2*b[1]；

这样，原本未知的size便可以求了 size[i]=(size[1]-c[i])/2

求出size，将size倒着求a就可以知道a是啥了；

这种思维量大的题不多见，考场上还是要仔细思考，别放过任何一点新奇的想法，才有可能想对吧。。。。

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

  2 #define int long long

  3 using namespace std;

  4 const int NN=1e5+5;

  5 int T,n,dis[NN],a[NN],b[NN],size[NN],c[NN];

  6 struct SNOW{

  7     int to,next;

  8 }; SNOW e[NN<<1]; int r[NN<<1],tot;

  9 inline void add(int x,int y){

 10     e[++tot]=(SNOW){y,r[x]};

 11     r[x]=tot;

 12 }

 13 inline void dfs(int fa,int x){

 14     for(int i=r[x];i;i=e[i].next)

 15         if(e[i].to!=fa){

 16             dis[e[i].to]=dis[x]+1;

 17             dfs(x,e[i].to);

 18         }

 19 }

 20 inline void dfs1(int fa,int x){

 21     for(int i=r[x];i;i=e[i].next)

 22         if(e[i].to!=fa){

 23             dfs1(x,e[i].to);

 24             size[x]+=size[e[i].to];

 25         }

 26 }

 27 inline void dfs2(int fa,int x){

 28     for(int i=r[x];i;i=e[i].next)

 29         if(e[i].to!=fa){

 30             b[e[i].to]=b[x]+size[1]-2*size[e[i].to];

 31             dfs2(x,e[i].to);

 32         }

 33 }

 34 inline void dfs3(int fa,int x){

 35     for(int i=r[x];i;i=e[i].next)

 36         if(e[i].to!=fa){

 37             c[e[i].to]=a[e[i].to]-a[x];

 38             dfs3(x,e[i].to);

 39         }

 40 }

 41 inline void dfs4(int fa,int x){

 42     for(int i=r[x];i;i=e[i].next)

 43         if(e[i].to!=fa){

 44             b[e[i].to]=size[e[i].to]=(size[1]-c[e[i].to])/2;

 45             dfs4(x,e[i].to);

 46         }

 47 }

 48 inline void dfs5(int fa,int x){

 49     for(int i=r[x];i;i=e[i].next)

 50         if(e[i].to!=fa){

 51             dfs5(x,e[i].to);

 52             b[x]-=size[e[i].to];

 53         }

 54 }

 55 inline int read(){

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

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

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

 59     return x*f;

 60 }

 61 namespace WSN{

 62     inline int main(){

 63         T=read();

 64         while(T--){

 65             memset(b,0,sizeof(b));

 66             memset(c,0,sizeof(c));

 67             memset(size,0,sizeof(size));

 68             memset(dis,0,sizeof(dis));

 69             memset(r,0,sizeof(r)); tot=0;

 70             n=read();

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

 72                 int x=read(),y=read();

 73                 add(x,y); add(y,x);

 74             }

 75             int t=read();

 76             for(int i=1;i<=n;i++) a[i]=read();

 77             if(!t){

 78                 dfs(0,1);

 79                 for(int i=2;i<=n;i++) b[1]+=dis[i]*a[i];

 80                 for(int i=1;i<=n;i++) size[i]=a[i];

 81                 dfs1(0,1);

 82                 dfs2(0,1);

 83                 for(int i=1;i<=n;i++) printf("%lld ",b[i]);

 84                 putchar('\n');

 85             }

 86             if(t){

 87                 dfs3(0,1); int cnt=0;

 88                 for(int i=2;i<=n;i++) cnt+=c[i];

 89                 size[1]=(cnt+2*a[1])/(n-1);

 90                 dfs4(0,1);

 91                 dfs5(0,1);

 92                 b[1]=size[1];

 93                 for(int i=2;i<=n;i++) b[1]-=b[i];

 94                 for(int i=1;i<=n;i++) printf("%lld ",b[i]);

 95                 putchar('\n');

 96             }

 97         }

 98         return 0;

 99     }

100 }

101 signed main(){return WSN::main();}

然而，六个dfs就很淦，感觉打完这道题对xin_team的理解又加深了不少呢

T3 题（problem）

这题就是相当于考了一个卡特兰数，然而我们这一批人还没学。。。

怎么办呢？那就学呗

大佬传送门

t=0，枚举向横向移动步数，必须是偶数，则纵向步数n-i。

从中选1/2向正方向走，另一半反向走C(n,i)C(i,i/2)C((n-i),(n-i)/2)

t=1，卡特兰数公式走起即可catalan(n)=C(2n,n)/(n+1)，至于有一个奇怪的错误就是另一个表达式他用了会错，不明白为什么

t=2，使用dp，注意是四个方向

            f[0]=1;

            for(int i=0;i<=n;i+=2){

                for(int j=0;j<=i;j+=2){

                    f[i]=(f[i]+f[i-j]*4%p*catlan(j/2-1)%p)%p;

                }

t=3，数据累加加卡特兰数，~~思路较简单~~（当时重点不知道卡特兰数是啥，汗）

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

 2 #define int long long

 3 using namespace std;

 4 const int p=1e9+7;

 5 int hi[3000000],n,typ;

 6 inline int jie(int x){

 7     if(x==1||x==0) return 1;

 8     if(hi[x]) return hi[x];

 9     return hi[x]=((jie(x-1)%p)*(x%p))%p;

10 }

11 inline int fima(int a){

12     int ans=1,b=p-2; a=a%p;

13     while(b){

14         if(b&1) ans=(ans*a)%p;

15         b>>=1,a=(a*a)%p;

16     } return ans;

17 }

18 inline int C(int n,int m){

19     if(n==m) return 1;

20     return jie(n)*fima(jie(m)*jie(n-m)%p)%p;

21 }

22 inline int catlan(int n){

23     return C(2*n,n)*fima(n+1)%p;

24 }

25 inline int read(){

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

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

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

29     return x*f;

30 }

31 namespace WSN{

32     inline int main(){

33         n=read(),typ=read();

34         if(typ==1) printf("%lld\n",catlan(n/2));

35         if(typ==0){

36             int ans=0;

37             for(int i=0;i<=n;i++)

38                 if(!(i&1)) ans=(ans+C(n,i)*C(i,i/2)%p*C((n-i),(n-i)/2)%p)%p;

39             printf("%lld\n",ans);

40         }

41         if(typ==3){

42             int ans=0;

43             for(int i=0;i<=n;i++)

44                 if(!(i&1)) ans=(ans+C(n,i)*catlan(i/2)%p*catlan((n-i)/2)%p)%p;

45             printf("%lld\n",ans);

46         }

47         if(typ==2){

48             int f[1005]={};

49             f[0]=1;

50             for(int i=0;i<=n;i+=2){

51                 for(int j=0;j<=i;j+=2){

52                     f[i]=(f[i]+f[i-j]*4%p*catlan(j/2-1)%p)%p;

53                 }

54             }

55             printf("%lld\n",f[n]);

56         }

57         return 0;

58     }

59 }

60 signed main(){return WSN::main();}

马の思

考完试挺不爽的，居然（——————），看这次考试经历发现还是不能死干一道题的，风险太大了

而且T4的得分率较高，虽然是黑的，但事后想一想，六维xin队是真的好冲

保底分拿到不是问题，可到考试结束我连第四题还没看，真是。。。。

总结下经验，考试打暴力，板子要记牢。。。。

巴特西

Noip模拟4（忁靈霁） 2021.6.6

T1 随（Rand）

由杠哥大定理可得，这题目前不可做，先跳走啦，咕咕。。。。

T2 单（single）

正确思路：

T3 题（problem）

马の思

END

最新文章

热门文章