神秘比赛，以《哈利波特》为主题……有点难。

C题我熬夜切终于是写出来了，可惜比赛结束了，气啊。

比赛链接：。

【A】汤姆·里德尔的日记

题意：

哈利波特正在摧毁神秘人的分灵体（魂器）。第一个他见到的魂器是在密室中的日记本，现在这本日记令金妮打开了密室。

哈利波特想要知道哪些人没有被日记施魔，以确保他们不会被日记影响。

哈利波特有一个名单，依次记录了那些被日记本施魔的人，对于每个人，他想知道这个人的名字在之前有没有出现过。

如果第\(i\)个字符串之前有相同的字符串，那么输出"YES"，否则输出"NO"。

输入：

第一行，一个正整数\(n(1\leq n\leq100)\)——名单中的字符串数量。

接下来\(n\)行，每行一个字符串，长度在\(1\)到\(100\)之间。

输出：

对于每个字符串，判断它在之前有没有出现过。

题解：

暴力判，你也可以扔到set里面查找，甚至建一棵trie树，我反正暴力判，其实用set写的更方便。

1 #include
     
       2 int n; 3 char str[105][105]; 4 int main(){ 5     scanf("%d",&n); 6     for(int i=1;i<=n;++i){ 7         scanf("%s",str[i]); 8         int ok=0; 9         for(int j=1;j
     

【B】马沃罗·冈特的戒指

题意：

邓布利多教授正在帮助哈利摧毁分灵体。他侦测到了一个分灵体在冈特家，于是他去了那儿。他看到了马沃罗·冈特的戒指，并认定那是一个分灵体。虽然他摧毁了分灵体，但是自己也身中了黑魔法诅咒。斯内普教授正帮助邓布利多消除诅咒，他需要给邓布利多滴正好\(x\)滴药水，\(x\)的计算方法如下：

\(x\)是\(p\cdot a_{i}+q\cdot a_{j}+r\cdot a_{k}\)的最大值，其中\(1\leq i\leq j\leq k\leq n\)。

帮助斯内普教授计算\(x\)的值，注意，\(x\)可能是负数。

输入：

第一行，四个数，\(n,p,q,r(-10^9\leq p,q,r\leq10^9,1\leq n\leq10^5)\)。

第二行，\(n\)个数，表示\(a_{1},a_{2},\cdots,a_{n}(-10^9\leq a_{i}\leq10^9)\)。

输出：

输出\(x\)。

题解：

枚举\(j\)，通过\(p\)的正负性算出\(i\)，通过\(r\)的正负性算出\(k\)。

1 #include
     
       2 int n,p,q,r,a[100005],min1[100005],max1[100005],min2[100005],max2[100005]; 3 long long ans=-3100000000000000000ll; 4 inline int Min(int x,int y){
   return x
      
       y?x:y;} 6 int main(){ 7     scanf("%d%d%d%d",&n,&p,&q,&r); 8     for(int i=1;i<=n;++i) scanf("%d",a+i); 9     for(int i=0;i<=n+1;++i) min1[i]=min2[i]=2147483647, max1[i]=max2[i]=-2147483647;10     for(int i=1;i<=n;++i) min1[i]=Min(min1[i-1],a[i]), max1[i]=Max(max1[i-1],a[i]);11     for(int i=n;i>=1;--i) min2[i]=Min(min2[i+1],a[i]), max2[i]=Max(max2[i+1],a[i]);12     for(int j=1;j<=n;++j){13         long long sum=1ll*q*a[j];14         if(p>0) sum+=1ll*p*max1[j];15         else sum+=1ll*p*min1[j];16         if(r>0) sum+=1ll*r*max2[j];17         else sum+=1ll*r*min2[j];18         if(ans
      
     

【C】赫尔加·赫奇帕奇的金杯

题意：

哈利，罗恩和赫敏发现赫尔加·赫奇帕奇的金杯是一个分灵体。通过赫敏与贝拉特里克斯·莱斯特兰奇的遭遇，她知道了金杯被存放在古灵阁巫师银行中的贝拉特里克斯的金柜中。

古灵阁可以看做是有着\(n\)个金柜的一棵树，每个金柜有一个型号，范围在\(1\)到\(m\)之中。

最高安全的金柜的型号为\(k\)，并且所有型号为\(k\)的金柜都是最高安全的。

最多有\(x\)个金柜是最高安全的。

另：如果一个金柜是最高安全的，那么与它直接相连的所有金柜都不是最高安全的，且它们的型号一定小于\(k\)。

哈利想知道所有的金柜型号的可能性，这样他能规划出去到贝拉特里克斯的金柜的最佳路线。所以，你需要告诉他，给定古灵阁的结构，所有可能的金柜型号总数。

输入：

第一行，两个正整数\(n,m(1\leq n\leq10^5,1\leq m\leq10^9)\)，表示金柜的数量，即树中的节点数，和金柜的型号范围。

接下来\(n-1\)行，每行两个正整数\(u_{i},v_{i}(1\leq u_{i},v_{i}\leq n)\)，表示第\(i\)条边，表示了金柜\(u_{i},v_{i}\)之间有连边。保证给定图是一棵树。

接下来一行，两个正整数\(k,x(1\leq k\leq m,1\leq x\leq10)\)，表示最高安全的金库的型号和最高安全的金库的最多个数。

输出：

输出一个非负整数，表示方案数对\(10^9+7\)取模的结果。

题解：

这题难度较大，适合做提高组练习……

考虑树形DP，用\(f[i][j][x\!=\!0\!/1\!/2]\)表示在以\(i\)为根的子树中，有\(j\)个最高安全的金柜，而金柜\(i\)的型号是\(\left\{\begin{matrix}x\!=\!0&1\leq type<k\\x\!=\!1&type=k\\x\!=\!2&k<type\leq m\end{matrix}\right.\)。

转移方程如下：\(\begin{matrix}f[i][j][0]=&\left(k-1\right)\sum_{j_{1}+j_{2}+\cdots+j_{i.sons}=j}\left(\prod_{k=1}^{i.sons}f[i.son_k][j_k][0]+f[i.son_k][j_k][1]+f[i.son_k][j_k][2]\right)\\f[i][j][1]=&\sum_{j_{1}+j_{2}+\cdots+j_{i.sons}=j-1}\left(\prod_{k=1}^{i.sons}f[i.son_k][j_k][0]\right)\\f[i][j][2]=&(m-k)\sum_{j_{1}+j_{2}+\cdots+j_{i.sons}=j}\left(\prod_{k=1}^{i.sons}f[i.son_k][j_k][0]+f[i.son_k][j_k][2]\right)\end{matrix}\)。

直接转移比较困难，我选择了左孩子右兄弟，然后再分别处理，导致代码其丑无比，不想拿出来看……

1 #include
      
        2 const int Mod=1000000007; 3 int n,m,k,X,left[100005],rr[100005],right[100005],dp[100005][12][4]; 4 int h[100005],to[200005],nxt[200005],tot=0; 5 int vis[100005]; 6 inline void Ins(int x,int y){nxt[++tot]=h[x]; to[tot]=y; h[x]=tot;} 7 inline void ins(int x,int y){ 8     if(!left[x]) left[x]=y, rr[x]=y; 9     else right[rr[x]]=y, rr[x]=y;10 }11 void dfs1(int u){12     vis[u]=1;13     for(int i=h[u];i;i=nxt[i]){14         if(vis[to[i]]) continue;15         ins(u,to[i]); dfs1(to[i]);16     }17 }18 void dfs2(int u){19     if(left[u]) dfs2(left[u]);20     if(right[u]) dfs2(right[u]);21     if(left[u]){22         if(right[u]){23             dp[u][0][0]=((long long)(k-1)*(dp[left[u]][0][0]+dp[left[u]][0][2])%Mod)*dp[right[u]][0][0]%Mod;24             dp[u][0][2]=(((long long)(m-k)*(dp[left[u]][0][0]+dp[left[u]][0][2])%Mod)*(dp[right[u]][0][0]+dp[right[u]][0][2])+25                             ((long long)(k-1)*(dp[left[u]][0][0]+dp[left[u]][0][2])%Mod)*dp[right[u]][0][2])%Mod;26             for(int x=1;x<=X;++x){27                 for(int y=0;y<=x;++y)28                     dp[u][x][0]=(dp[u][x][0]+29                                     ((long long)(k-1)*((long long)dp[left[u]][y][0]+dp[left[u]][y][1]+dp[left[u]][y][2]))%Mod*30                                     dp[right[u]][x-y][0])%Mod;31                 for(int y=0;y<=x-1;++y)32                     dp[u][x][1]=(dp[u][x][1]+33                         (long long)dp[left[u]][y][0]*((long long)dp[right[u]][x-y-1][0]+dp[right[u]][x-y-1][1]+dp[right[u]][x-y-1][2]))%Mod;34                 for(int y=0;y<=x;++y)35                     dp[u][x][1]=(dp[u][x][1]+36                         ((long long)(k-1)*((long long)dp[left[u]][y][0]+dp[left[u]][y][1]+dp[left[u]][y][2]))%Mod*37                         dp[right[u]][x-y][1]%Mod+38                         ((long long)(m-k)*(dp[left[u]][y][0]+dp[left[u]][y][2]))%Mod*dp[right[u]][x-y][1]%Mod)%Mod;39                 for(int y=0;y<=x;++y)40                     dp[u][x][2]=(dp[u][x][2]+41                         ((long long)(k-1)*((long long)dp[left[u]][y][0]+dp[left[u]][y][1]+dp[left[u]][y][2]))%Mod*42                         dp[right[u]][x-y][2]%Mod+43                         ((long long)(m-k)*(dp[left[u]][y][0]+dp[left[u]][y][2]))%Mod*(dp[right[u]][x-y][0]+dp[right[u]][x-y][2])%Mod)%Mod;44             }45         }46         else{47             dp[u][0][0]=(long long)(k-1)*(dp[left[u]][0][0]+dp[left[u]][0][2])%Mod;48             dp[u][0][2]=(long long)(m-k)*(dp[left[u]][0][0]+dp[left[u]][0][2])%Mod;49             for(int x=1;x<=X;++x){50                 dp[u][x][0]=(long long)(k-1)*((long long)dp[left[u]][x][0]+dp[left[u]][x][1]+dp[left[u]][x][2])%Mod;51                 dp[u][x][1]=dp[left[u]][x-1][0];52                 dp[u][x][2]=(long long)(m-k)*(dp[left[u]][x][0]+dp[left[u]][x][2])%Mod;53             }54         }55     }56     else{57         if(right[u]){58             dp[u][0][0]=(long long)(k-1)*dp[right[u]][0][0]%Mod;59             dp[u][0][2]=((long long)(m-k)*(dp[right[u]][0][0]+dp[right[u]][0][2])+(long long)(k-1)*dp[right[u]][0][2])%Mod;60             for(int x=1;x<=X;++x){61                 dp[u][x][0]=(long long)(k-1)*dp[right[u]][x][0]%Mod;62                 dp[u][x][1]=((long long)dp[right[u]][x-1][0]+dp[right[u]][x-1][1]+dp[right[u]][x-1][2]+63                                 (long long)(m-1)*dp[right[u]][x][1])%Mod;64                 dp[u][x][2]=((long long)(m-k)*(dp[right[u]][x][0]+dp[right[u]][x][2])+(long long)(k-1)*dp[right[u]][x][2])%Mod;65             }66         }67         else{68             dp[u][0][0]=k-1;69             dp[u][1][1]=1;70             dp[u][0][2]=m-k;71         }72     }73 }74 int main(){75     scanf("%d%d",&n,&m);76     for(int i=1,x,y;i
      

而学长的就画风清奇，看上去舒服至极，我实在是自愧不如。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
          
         
        
       
      
     

【D】【E】【F】目前不会。