神秘比赛，以《哈利波特》为主题……有点难。
C题我熬夜切终于是写出来了，可惜比赛结束了，气啊。
比赛链接：点我。
【A】汤姆·里德尔的日记
题意：
哈利波特正在摧毁神秘人的分灵体（魂器）。第一个他见到的魂器是在密室中的日记本，现在这本日记令金妮打开了密室。
哈利波特想要知道哪些人没有被日记施魔，以确保他们不会被日记影响。
哈利波特有一个名单，依次记录了那些被日记本施魔的人，对于每个人，他想知道这个人的名字在之前有没有出现过。
如果第\(i\)个字符串之前有相同的字符串，那么输出"YES"，否则输出"NO"。
输入：
第一行，一个正整数\(n(1\leq n\leq100)\)——名单中的字符串数量。
接下来\(n\)行，每行一个字符串，长度在\(1\)到\(100\)之间。
输出：
对于每个字符串，判断它在之前有没有出现过。
题解：
暴力判，你也可以扔到set里面查找，甚至建一棵trie树，我反正暴力判，其实用set写的更方便。
#include<cstdio>
int n;
char str[][];
int main(){
scanf("%d",&n);
for(int i=;i<=n;++i){
scanf("%s",str[i]);
int ok=;
for(int j=;j<i;++j){
int o=,k;
for(k=;str[i][k]!='\0'&&str[j][k]!='\0';++k){
if(str[j][k]!=str[i][k]) {o=; break;}
}
if((str[i][k]=='\0'&&str[j][k]!='\0')||(str[j][k]=='\0'&&str[i][k]!='\0')) o=;
if(o==) {ok=; break;}
}
if(ok==) puts("Yes");
else puts("No");
}
return ;
}
【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\)。
#include<cstdio>
int n,p,q,r,a[],min1[],max1[],min2[],max2[];
long long ans=-3100000000000000000ll;
inline int Min(int x,int y){return x<y?x:y;}
inline int Max(int x,int y){return x>y?x:y;}
int main(){
scanf("%d%d%d%d",&n,&p,&q,&r);
for(int i=;i<=n;++i) scanf("%d",a+i);
for(int i=;i<=n+;++i) min1[i]=min2[i]=, max1[i]=max2[i]=-;
for(int i=;i<=n;++i) min1[i]=Min(min1[i-],a[i]), max1[i]=Max(max1[i-],a[i]);
for(int i=n;i>=;--i) min2[i]=Min(min2[i+],a[i]), max2[i]=Max(max2[i+],a[i]);
for(int j=;j<=n;++j){
long long sum=1ll*q*a[j];
if(p>) sum+=1ll*p*max1[j];
else sum+=1ll*p*min1[j];
if(r>) sum+=1ll*r*max2[j];
else sum+=1ll*r*min2[j];
if(ans<sum) ans=sum;
}
printf("%I64d",ans);
return ;
}
【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}\)。
直接转移比较困难，我选择了左孩子右兄弟，然后再分别处理，导致代码其丑无比，不想拿出来看……
#include<cstdio>
const int Mod=;
int n,m,k,X,left[],rr[],right[],dp[][][];
int h[],to[],nxt[],tot=;
int vis[];
inline void Ins(int x,int y){nxt[++tot]=h[x]; to[tot]=y; h[x]=tot;}
inline void ins(int x,int y){
if(!left[x]) left[x]=y, rr[x]=y;
else right[rr[x]]=y, rr[x]=y;
}
void dfs1(int u){
vis[u]=;
for(int i=h[u];i;i=nxt[i]){
if(vis[to[i]]) continue;
ins(u,to[i]); dfs1(to[i]);
}
}
void dfs2(int u){
if(left[u]) dfs2(left[u]);
if(right[u]) dfs2(right[u]);
if(left[u]){
if(right[u]){
dp[u][][]=((long long)(k-)*(dp[left[u]][][]+dp[left[u]][][])%Mod)*dp[right[u]][][]%Mod;
dp[u][][]=(((long long)(m-k)*(dp[left[u]][][]+dp[left[u]][][])%Mod)*(dp[right[u]][][]+dp[right[u]][][])+
((long long)(k-)*(dp[left[u]][][]+dp[left[u]][][])%Mod)*dp[right[u]][][])%Mod;
for(int x=;x<=X;++x){
for(int y=;y<=x;++y)
dp[u][x][]=(dp[u][x][]+
((long long)(k-)*((long long)dp[left[u]][y][]+dp[left[u]][y][]+dp[left[u]][y][]))%Mod*
dp[right[u]][x-y][])%Mod;
for(int y=;y<=x-;++y)
dp[u][x][]=(dp[u][x][]+
(long long)dp[left[u]][y][]*((long long)dp[right[u]][x-y-][]+dp[right[u]][x-y-][]+dp[right[u]][x-y-][]))%Mod;
for(int y=;y<=x;++y)
dp[u][x][]=(dp[u][x][]+
((long long)(k-)*((long long)dp[left[u]][y][]+dp[left[u]][y][]+dp[left[u]][y][]))%Mod*
dp[right[u]][x-y][]%Mod+
((long long)(m-k)*(dp[left[u]][y][]+dp[left[u]][y][]))%Mod*dp[right[u]][x-y][]%Mod)%Mod;
for(int y=;y<=x;++y)
dp[u][x][]=(dp[u][x][]+
((long long)(k-)*((long long)dp[left[u]][y][]+dp[left[u]][y][]+dp[left[u]][y][]))%Mod*
dp[right[u]][x-y][]%Mod+
((long long)(m-k)*(dp[left[u]][y][]+dp[left[u]][y][]))%Mod*(dp[right[u]][x-y][]+dp[right[u]][x-y][])%Mod)%Mod;
}
}
else{
dp[u][][]=(long long)(k-)*(dp[left[u]][][]+dp[left[u]][][])%Mod;
dp[u][][]=(long long)(m-k)*(dp[left[u]][][]+dp[left[u]][][])%Mod;
for(int x=;x<=X;++x){
dp[u][x][]=(long long)(k-)*((long long)dp[left[u]][x][]+dp[left[u]][x][]+dp[left[u]][x][])%Mod;
dp[u][x][]=dp[left[u]][x-][];
dp[u][x][]=(long long)(m-k)*(dp[left[u]][x][]+dp[left[u]][x][])%Mod;
}
}
}
else{
if(right[u]){
dp[u][][]=(long long)(k-)*dp[right[u]][][]%Mod;
dp[u][][]=((long long)(m-k)*(dp[right[u]][][]+dp[right[u]][][])+(long long)(k-)*dp[right[u]][][])%Mod;
for(int x=;x<=X;++x){
dp[u][x][]=(long long)(k-)*dp[right[u]][x][]%Mod;
dp[u][x][]=((long long)dp[right[u]][x-][]+dp[right[u]][x-][]+dp[right[u]][x-][]+
(long long)(m-)*dp[right[u]][x][])%Mod;
dp[u][x][]=((long long)(m-k)*(dp[right[u]][x][]+dp[right[u]][x][])+(long long)(k-)*dp[right[u]][x][])%Mod;
}
}
else{
dp[u][][]=k-;
dp[u][][]=;
dp[u][][]=m-k;
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=,x,y;i<n;++i) scanf("%d%d",&x,&y), Ins(x,y), Ins(y,x);
scanf("%d%d",&k,&X);
dfs1();
dfs2();
/* for(int i=1;i<=n;++i) printf("(%d,%d)\n",left[i],right[i]);
for(int i=1;i<=n;++i){
for(int j=0;j<=X;++j){
printf("%d, %d : %d, %d, %d\n",i,j,dp[i][j][0],dp[i][j][1],dp[i][j][2]);
}
}*/
long long Ans=;
for(int i=;i<=X;++i) Ans+=(long long)dp[][i][]+dp[][i][]+dp[][i][];
printf("%I64d",Ans%Mod);
return ;
}
而学长的就画风清奇，看上去舒服至极，我实在是自愧不如。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<queue>
#include<map>
#include<set>
#define MN 100000
#define mod 1000000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int f[MN+][],F[MN+][],s[MN+][],S[MN+][],l[MN+][],L[MN+][],n,K,m,Mx,cnt=,head[MN+];
struct edge{int to,next;}e[MN*+];
inline void ins(int f,int t)
{
e[++cnt]=(edge){t,head[f]};head[f]=cnt;
e[++cnt]=(edge){f,head[t]};head[t]=cnt;
}
inline void R(int&x,int y){x+=y;x>=mod?x-=mod:;}
void Dp(int x,int fa)
{
f[x][]=;s[x][]=K-;l[x][]=m-K;
for(int i=head[x];i;i=e[i].next)
if(e[i].to!=fa)
{
Dp(e[i].to,x);
for(int j=;j<=Mx;++j)
for(int k=;k+j<=Mx;++k)
{
R(F[x][j+k],1LL*f[x][j]*s[e[i].to][k]%mod);
R(S[x][j+k],1LL*s[x][j]*((f[e[i].to][k]+s[e[i].to][k])%mod+l[e[i].to][k])%mod);
R(L[x][j+k],1LL*l[x][j]*(s[e[i].to][k]+l[e[i].to][k])%mod);
}
for(int j=;j<=Mx;++j)
{
f[x][j]=F[x][j],F[x][j]=;
s[x][j]=S[x][j],S[x][j]=;
l[x][j]=L[x][j],L[x][j]=;
}
}
} int main()
{
n=read();m=read();
for(int i=;i<n;++i) ins(read(),read());
K=read();Mx=read();
Dp(,);int ans=;
for(int i=;i<=Mx;++i) R(ans,f[][i]),R(ans,l[][i]),R(ans,s[][i]);
printf("%d\n",ans);
return ;
}
【D】【E】【F】目前不会。