A题
传送门
题意简述：把262626个英文字母分成两类A,BA,BA,B，AAA类字符可以转成AAA类字符，BBB类字符可以转成BBB类字符，问给出的两个字符串SSS能不能转换成TTT
思路：先判长度，然后把S,TS,TS,T中AAA类转成aaa，BBB类转成bbb然后看一不一样。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=1005;
int n,m;
char s[N],t[N];
const char ch[5]={'a','e','i','o','u'};
int main(){
scanf("%s%s",s+1,t+1);
n=strlen(s+1),m=strlen(t+1);
if(n!=m)return puts("No"),0;
for(ri i=1;i<=n;++i){
bool f=0;
for(ri j=0;j<5;++j)if(s[i]==ch[j]){f=1;break;}
if(f==1)s[i]='a';
else s[i]='b';
}
for(ri i=1;i<=n;++i){
bool f=0;
for(ri j=0;j<5;++j)if(t[i]==ch[j]){f=1;break;}
if(f==1)t[i]='a';
else t[i]='b';
if(s[i]!=t[i])return puts("No"),0;
}
puts("Yes");
return 0;
}
B题
传送门
题意简述：给你nnn个数，你可以操作至多mmm次，每次可以给一个数加111或者删去一个数，问最后剩下的数的最大平均值。
思路：把所有数排序，然后枚举删去前iii个数更新答案即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
typedef long long ll;
const int N=1e5+5;
ll a[N];
ll sum[N];
int n,k,m;
int main(){
n=read(),k=read(),m=read();
for(ri i=1;i<=n;++i)a[i]=read();
sort(a+1,a+n+1);
for(ri i=1;i<=n;++i)sum[i]=sum[i-1]+a[i];
double ans=0.0;
for(ri i=1;i<=min(n,m+1);++i){
ll up=min((ll)m-i+1,(ll)(n-i+1)*k);
ans=max(ans,1.0*(sum[n]-sum[i-1]+up)/(n-i+1));
}
printf("%.10lf\n",ans);
return 0;
}
C题
传送门
题意简述：给一个2n2^n2n长的序列，n≤30n\le30n≤30，其中有kkk个特殊点k≤100000k\le100000k≤100000，现在要求消除整个序列，对于当前的序列有几种操作方式。
- 将当前的序列等分分别消除
- 消除当前的序列，如果当前序列无特殊点花费AAA，否则花费B∗特殊点个数∗当前序列长度B*特殊点个数*当前序列长度B∗特殊点个数∗当前序列长度
保证A,B≥0A,B\ge0A,B≥0问消除整个序列最小花费。
思路：如果当前区间只剩一个特殊点直接返回BBB,如果无特殊点直接返回AAA，否则按题意模拟。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=1e6+5;
ll n,k,m,a[N];
ll A,B;
inline ll cnt(ll l,ll r){return upper_bound(a+1,a+k+1,r)-lower_bound(a+1,a+k+1,l);}
inline ll solve(ll l,ll r){
ll mid=l+r>>1,tmp=cnt(l,r);
if(!tmp)return A;
ll ret=B*(r-l+1)*tmp;
if(l==r)return ret;
return min(ret,solve(l,mid)+solve(mid+1,r));
}
int main(){
n=read(),k=read(),A=read(),B=read();
for(ri i=1;i<=k;++i)a[i]=read();
sort(a+1,a+k+1);
cout<<solve(1,1<<n);
return 0;
}
D题
传送门
题意简述：给你n,n≤1e5n,n\le1e5n,n≤1e5个带颜色（颜色最多525252种）的点（nnn是偶数），可以任意排列，规定一个合法的排列是对于每种颜色，所有该颜色的点同在前一半或者同在后一半，现在有qqq次询问q≤100000q\le100000q≤100000，每次指定两种颜色x,yx,yx,y要求这两种颜色对应的所有点必须同在前一半或者同在后一半，问该条件下合法序列个数。
思路：考虑把每种颜色的个数存下来，做一个010101背包，fif_ifi表示凑出iii的方案数。
这样不考虑顺序和x,yx,yx,y的限制fn2f_{\frac n2}f2n就是所有合法序列数，
然后我们枚举每一对x,yx,yx,y扣掉它们的贡献记成ansx,yans_{x,y}ansx,y就完了。
最后考虑一下顺序的问题，对于一种合法序列数，显然可以对应(n2!)2∗∏i=0,52invfaccnti(\frac n2!)^2*\prod_{i=0,52}invfac_{cnt_i}(2n!)2∗∏i=0,52invfaccnti中放法。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int mod=1e9+7;
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
const int N=1e5+5;
char s[N];
int tmp,n,q,cnt[52],fac[N],ifac[N],f[N],ans[52][52],tim;
inline int idx(char x){return x>='a'&&x<='z'?x-'a':x-'A'+26;}
int main(){
scanf("%s",s+1),n=strlen(s+1);
for(ri i=1;i<=n;++i)++cnt[idx(s[i])];
fac[1]=ifac[1]=fac[0]=ifac[0]=1;
for(ri i=2;i<=n;++i)fac[i]=mul(fac[i-1],i),ifac[i]=mul(ifac[mod%i],mod-mod/i);
for(ri i=2;i<=n;++i)ifac[i]=mul(ifac[i],ifac[i-1]);
f[0]=1;
for(ri i=0;i<52;++i){
if(!cnt[i])continue;
for(ri j=n;j>=cnt[i];--j)f[j]=add(f[j],f[j-cnt[i]]);
}
tim=mul(fac[n/2],fac[n/2]);
for(ri i=0;i<52;++i)tim=mul(tim,ifac[cnt[i]]);
for(ri i=0;i<52;++i){
if(!cnt[i])continue;
ans[i][i]=f[n/2];
for(ri j=cnt[i];j<=n;++j)f[j]=dec(f[j],f[j-cnt[i]]);
for(ri j=0;j<i;++j){
if(!cnt[j])continue;
for(ri k=cnt[j];k<=n;++k)f[k]=dec(f[k],f[k-cnt[j]]);
ans[i][j]=ans[j][i]=mul(2,f[n/2]);
for(ri k=n;k>=cnt[j];--k)f[k]=add(f[k],f[k-cnt[j]]);
}
for(ri j=n;j>=cnt[i];--j)f[j]=add(f[j],f[j-cnt[i]]);
}
for(ri x,y,i=read();i;--i){
x=idx(s[read()]),y=idx(s[read()]);
cout<<mul(ans[x][y],tim)<<'\n';
}
return 0;
}
E题
传送门
题意简述：给你一棵树，每次给你一些关键点和一个根和一个m，要求你把这些点分成至多m组满足每一组的任意2个数没有祖先关系，求方案数。
满足关键点总数≤100000,n≤100000,m≤min{n,300}\le100000,n\le100000,m\le min\{n,300\}≤100000,n≤100000,m≤min{n,300}
思路：直接考虑111为根的情况，把当前的所有关键点提出来组成一个集合，记一个fi,jf_{i,j}fi,j表示把集合中前iii个数分成jjj个组且分组方式满足题意的方案数，gig_igi表示集合中iii的祖先的个数，显然有：
fi,j=fi−1,j−1+fi−1,j∗(j−gi)f_{i,j}=f_{i-1,j-1}+f_{i-1,j}*(j-g_i)fi,j=fi−1,j−1+fi−1,j∗(j−gi)，这样每次只用考虑求出ggg数组即可。
我们把所有点的dfsdfsdfs序搞出来然后用树状数组维护ggg，至于换根用lcalcalca差分一下即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int mod=1e9+7;
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
const int N=2e5+5;
int n,q,dep[N],g[N],f[N],siz[N],hson[N],fa[N],top[N],in[N],out[N],a[N],tot=0;
bool mk[N];
vector<int>e[N];
void dfs1(int p){
siz[p]=1;
for(ri i=0,v;i<e[p].size();++i){
if((v=e[p][i])==fa[p])continue;
fa[v]=p,dep[v]=dep[p]+1,dfs1(v),siz[p]+=siz[v];
if(siz[v]>siz[hson[p]])hson[p]=v;
}
}
void dfs2(int p,int tp){
top[p]=tp,in[p]=++tot;
if(!hson[p]){out[p]=++tot;return;}
dfs2(hson[p],tp);
for(ri i=0,v;i<e[p].size();++i)if((v=e[p][i])!=fa[p]&&v!=hson[p])dfs2(v,v);
out[p]=tot;
}
inline int lca(int x,int y){
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
namespace Bit{
int bit[N]={0};
inline int lowbit(const int&x){return x&-x;}
inline void update(const int&x,const int&v){for(ri i=x;i<=tot;i+=lowbit(i))bit[i]=add(bit[i],v);}
inline int query(const int&x){int ret=0;for(ri i=x;i;i-=lowbit(i))ret=add(ret,bit[i]);return ret;}
}
int main(){
n=read(),q=read();
for(ri i=1,u,v;i<n;++i)u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
dfs1(1),dfs2(1,1);
while(q--){
int k=read(),m=read(),rt=read(),ans=0;
for(ri i=1;i<=k;++i)mk[a[i]=read()]=1,Bit::update(in[a[i]],1),Bit::update(out[a[i]]+1,-1);
for(ri i=1,t;i<=k;++i)t=lca(a[i],rt),g[i]=Bit::query(in[a[i]])+Bit::query(in[rt])-2*Bit::query(in[t])+mk[t]-1;
sort(g+1,g+k+1);
for(ri i=1;i<=k;++i)Bit::update(in[a[i]],-1),Bit::update(out[a[i]]+1,1),mk[a[i]]=0;
bool flag=g[k]>=m;
if(flag){puts("0");continue;}
for(ri i=0;i<=m;++i)f[i]=0;
f[0]=1;
for(ri i=1;i<=k;++i){
for(ri j=min(i,m);~j;--j){
if(j<=g[i])f[j]=0;
else f[j]=add(f[j-1],mul(f[j],j-g[i]));
}
}
for(ri i=1;i<=m;++i)ans=add(ans,f[i]);
cout<<ans<<'\n';
}
return 0;
}