2021 BUAA Winter Training 5赛后补题

2021 BUAA Winter Training 5

${A\ -\ Diverse\ Strings}$ ${\scriptstyle [\ CodeForces\ -\ 1144A\ ]}$

题意

给你一个小写字母的字符串，问这个祖字符串中每个字母是否只出现了一次，且所有出现的字母连续。

多组询问。

解法

$n<=100$ ，瞎暴力都能过。。。

暴力大法好！

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 110
using namespace std;
int len,num[26];
char str[MAXN];
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
bool solve(){
    for(int i=1;i<=len;i++)num[str[i]-'a']++;
    for(int i=0;i<=25;i++)if(num[i]>1)return false;
    int l=0,r;
    while(num[l]==0&&l<=25)l++;
    r=l;
    while(num[r]==1&&r<=25)r++;
    if(r>25)return true;
    l=r;
    while(num[l]==0&&l<=25)l++;
    if(l<=25)return false;
    else return true;
}
void init(){
    scanf("%s",str+1);
    len=strlen(str+1);
    memset(num,0,sizeof(num));
}
int main(){
    int t=read();
    while(t--){
        init();
        if(solve())printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

$\text{ }$

${B\ -\ Cutting}$ ${\scriptstyle [\ CodeForces\ -\ 998B\ ]}$

题意

给你 $n$ 个数字的数列，要求分成若干段，每段中奇数和偶数的个数相同，每次分割的代价是分割两侧数字的差的绝对值。

求在代价不超过某个预算值且代价花费最大的情况下，最多能分多少段。

解法

显然我们可以先把所有能分割的位置搞出来，然后按照代价丢进一个小根堆里，每次取出堆顶即可。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#define MAXN 110
using namespace std;
priority_queue<int,vector<int>,greater<int>> q;
int n,m,ans=0,val[MAXN],num[MAXN];
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
    return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
void work(){
    while(!q.empty()){
        int x=q.top();
        q.pop();
        if(x>m)break;
        m-=x;
        ans++;
    }
    printf("%d\n",ans);
}
void init(){
    n=read();m=read();
    num[0]=0;
    for(int i=1;i<=n;i++){
        val[i]=read();
        if(val[i]&1)num[i]=num[i-1]+1;
        else num[i]=num[i-1]-1;
        if(i>=2&&num[i-1]==0)q.push(abs(val[i-1]-val[i]));
    }
}
int main(){
    init();
    work();
    return 0;
}

$\text{ }$

${C\ -\ Linova\ and\ Kingdom}$ ${\scriptstyle [\ CodeForces\ -\ 1336A\ ]}$

题意

给一颗 $n$ 个点的根为 $1$ （首都）的树，把 $k$ 个点选为工业城市，剩下的为旅游城市，求所有工业城市到首都的路径上旅游城市的个数的总和。

解法

首先首都肯定是旅游城市。

其次旅游城市一定要尽可能地靠近首都，这样才更可能被重复计数。

然后把问题转化一下：如果所有的城市都是工业城市，那么我们只要选出 $n-k$ 个旅游城市即可。

这和原问题不是差不多么？！

但是这样我们就能考虑假如把一个城市设为旅游城市，对答案的贡献是多少。

很容易发现这个贡献就是 $+\text{子树大小}-\text{该点深度}$ 。

所以我们把每个点按照 $size[i]-deep[i]$ 排个序，从大到小选 $n-k$ 个即可。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 200010
using namespace std;
int n,m,c=1;
int head[MAXN],deep[MAXN],size[MAXN],pos[MAXN];
long long ans=0;
struct Tree{
    int next,to;
}a[MAXN<<1];
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
    return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
inline bool cmp(const int &x,const int &y){
    return size[x]-deep[x]>size[y]-deep[y];
}
void add_edge(int x,int y){
    a[c].to=y;a[c].next=head[x];head[x]=c++;
    a[c].to=x;a[c].next=head[y];head[y]=c++;
}
void dfs(int rt){
    size[rt]=1;
    for(int i=head[rt];i;i=a[i].next){
        int will=a[i].to;
        if(!deep[will]){
            deep[will]=deep[rt]+1;
            dfs(will);
            size[rt]+=size[will];
        }
    }
}
void work(){
    for(int i=1;i<=n;i++)pos[i]=i;
    sort(pos+1,pos+n+1,cmp);
    for(int i=1;i<=n-m;i++)ans+=1LL*(size[pos[i]]-deep[pos[i]]);
    printf("%lld\n",ans);
}
void init(){
    n=read();m=read();
    for(int i=1,x,y;i<n;i++){
        x=read();y=read();
        add_edge(x,y);
    }
    deep[1]=1;
    dfs(1);
}
int main(){
    init();
    work();
    return 0;
}

$\text{ }$

${D\ -\ Restore\ Permutation}$ ${\scriptstyle [\ CodeForces\ -\ 1208D\ ]}$

题意

有一个长度为 $n$ ，各个数字值域为 $[1,n]$ 的全排列序列 $a$ ，给出序列 $b$ ， $b_i=\sum_{j=1}^{i-1}a_j\times[a_j<a_i]$ ，请求出序列 $a$ 。保证有解。

解法

对于一开始 $a$ 序列最后一个数 $x$ ， $b$ 最后一个数的值必为 $\frac{x(x+1)}{2}$ 。

但是对于 $x$ 之前的数 $y$ ，它有可能大于 $x$ ，这使得 $b$ 这个位置上的值不是 $\frac{y(y+1)}{2}$ ，而是少了一个 $x$ 。

所以我们需要从后往前推，并且动态维护前缀和。

前缀和？树状数组，请开始你的表演。

可以用树状数组维护的 $\frac{y(y+1)}{2}-\sum_{x<y}x$ 。

找最后那个未知的数在外面套一个二分就行了。

复杂度 $O(n\log_2^2n)$ ，树状数组常数极小，还是能轻松过的。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 200010
using namespace std;
int n,ans[MAXN];
long long val[MAXN],sum[MAXN];
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
    return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline long long read(){
    long long date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
inline int lowbit(int x){return x&(-x);}
inline void update(int x,int v){for(;x<=n;x+=lowbit(x))sum[x]+=v;}
inline long long query(int x){long long s=0;for(;x;x-=lowbit(x))s+=sum[x];return s;}
void work(){
    for(int i=n,l,r,mid,s;i>=1;i--){
        l=1;r=n;s=0;
        while(l<=r){
            mid=l+r>>1;
            if(query(mid-1)<=val[i]){
                s=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        update(s,-s);
        ans[i]=s;
    }
    for(int i=1;i<=n;i++)printf("%d ",ans[i]);
    printf("\n");
}
void init(){
    n=read();
    for(int i=1;i<=n;i++){
        val[i]=read();
        update(i,i);
    }
}
int main(){
    init();
    work();
    return 0;
}

$\text{ }$

${E\ -\ Multipliers}$ ${\scriptstyle [\ CodeForces\ -\ 615D\ ]}$

题意

给你一堆素数 ${a_n}$ ，求这些数的乘积 $s=\prod\limits_{i=1}^n a_i$ 的所有因子的乘积 $\prod\limits_{x|s}x$ 模 $10^9+7$ 的值。

解法

因为给出的都是素数，所以我们不用质因数分解了，直接排序去重，统计每个数出现多少次即可。

对于每个数 $a_i$ ，我们知道它出现了 $p_i$ 次，可以取它的 $b_i(0<=b_i<=p_i)$ 次方。

而其他数的所有取法有 $\prod\limits_{j=1}^n (p_j+1)[j!=i]$ 种。

所以我们设：

$f[i]=\prod\limits_{j=1}^{i-1} (p_j+1)\\$ $g[i]=\prod\limits_{j=i+1}^n (p_j+1)\\$

那么 $a_i$ 对答案的贡献就是：

$a_i^{f[i]g[i]\times\frac{p_i(p_i+1)}{2}}\\$

最终答案就是：

$Ans=\sum\limits_{i=1}^n a_i^{f[i]g[i]\times\frac{p_i(p_i+1)}{2}}\mod(10^9+7)\\$

但是那个幂次太大了， $long\ long$ 也无能为力啊。。。

这个时候就要拿出费马小定理了：

当 $gcd(a,p)==1$ 时， $a^{(p-1)}\mod p\equiv 1$ 。

所以：

$Ans=\sum\limits_{i=1}^n a_i^{f[i]g[i]\times\frac{p_i(p_i+1)}{2}\mod (10^9+6)}\mod(10^9+7)\\$

这样就完成了。

一开始有个地方 $long\ long$ 没开直接 $WA$ ，药丸。。。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 200010
#define MOD 1000000007LL
using namespace std;
int n,val[MAXN],num[MAXN];
long long ans=1,f[MAXN],g[MAXN],s[MAXN];
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
    return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline long long read(){
    long long date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
long long mexp(long long a,long long b,long long c){
    long long s=1;
    while(b){
        if(b&1)s=s*a%c;
        a=a*a%c;
        b>>=1;
    }
    return s;
}
void work(){
    f[0]=1;
    for(int i=1;i<=n;i++)f[i]=f[i-1]*(num[val[i]]+1)%(MOD-1);
    g[n+1]=1;
    for(int i=n;i>=1;i--)g[i]=g[i+1]*(num[val[i]]+1)%(MOD-1);
    for(int i=1;i<=n;i++){
        long long k=f[i-1]%(MOD-1)*g[i+1]%(MOD-1)*(1LL*(1LL*num[val[i]]*(num[val[i]]+1)/2)%(MOD-1))%(MOD-1);
        ans=ans*mexp(val[i],k,MOD)%MOD;
    }
    printf("%lld\n",ans);
}
void init(){
    memset(num,0,sizeof(num));
    n=read();
    for(int i=1;i<=n;i++){
        val[i]=read();
        num[val[i]]++;
    }
    sort(val+1,val+n+1);
    n=unique(val+1,val+n+1)-val-1;
}
int main(){
    init();
    work();
    return 0;
}