2023-08-08 23:01:17

2023.8.8

前言

\(Div_3\) 太简单了，但是因为我太菜了想到了但来不及写最后一题，然后 F 题因为用 unordered_map 被卡哈希 hack T 了，最后结果出来只过了 \(5\) 题，排到了 \(rk1365\)。

A

题意：

给你一个序列，判断是否将其分为非空的两部分，使得两部分的和的奇偶性相同。

思路：

看所有元素总和的奇偶性即可，如果总和是奇数那显然不可能分成奇偶相同的两部分。太简单了，代码不放。

B

题意：

给你一个数，可以任意次的对任意位置进行四舍五入，求最大值。

思路：

从低位往高位扫，能进位则进位，对于下一个数位是 \(9\) 的情况，因为我们下一步肯定会将其进位，所以可以直接不考虑。

\(Code\)

int T;
char l[200005];
int main(){
    for(T=read();T--;){
        scanf("%s",l+1);
        int zero=20000000,n=strlen(l+1);
        l[0]='0';
        for(int i=n;i;--i){
            if(l[i]<='4')continue;
            zero=i;
            if(l[i-1]<'9')l[i-1]++;
            else continue;
        }
        for(int i=0;i<=n;i++){
            if(i==0&&l[i]=='0')continue;
            if(i>=zero)printf("0");
            else printf("%c",l[i]);
        }
        puts("");
    }
}

后话

感觉之前郑宇轩好像跟我说过一个类似的题，就是说两个人报身高问你这样四舍五入后的最大值？

C

思路：

考虑到一个最小值对答案的贡献，发现如果是序列最小值，因为配对了 \(n-1\) 次，而每次配对的结果都是它，所以在 \(b\) 中会出现 \(n-1\) 次。

同理，次小值（可能与最小值相同）出现 \(n-2\) 次，第三小出现 \(n-3\) 次等。因为保证有解，所以我们只需要给 \(b\) 数组排好序后跳相应的步数并且输出当前数即可，最后注意 \(a\) 数组最大值只需要大于等于 \(b\) 数组最大值即可，这里我出于方便直接取等了。

\(Code\)

int T,n,m,a[1000006];
int main(){
    for(T=read();T--;){
        n=read();
        m=n*(n-1)>>1;
        for(int i=1;i<=m;i++){
            a[i]=read();
        }
        sort(a+1,a+1+m);
        int o=0;
        for(int i=1;i<=m;i+=n-o){
            printf("%d ",a[i]);
            o++;
            if(i==m){
                printf("%d\n",a[i]);
                break;
            }
        }
    }
}

D

思路：

第一眼拓扑，发现数据太大，肯定有特殊性质。关注到连边条件：\(a_u-a_v\ge b_u-b_v\)，移项后可得连边条件：\(a_u-b_u\ge a_v-b_v\)。

所以 \(a_u-b_u\) 最大的肯定可以和所有点连边，而比它小的显然无法到达它，所以我们只需要找 \(a_u-b_u\) 最大的几个即可。

\(Code\)

struct node{
    int v,id;
    inline bool operator <(const node&w)const{
        if(v==w.v)return id<=w.id;
        return v>w.v;
    }
}a[200005];
int T,n;
int main(){
    for(T=read();T--;){
        n=read();
        for(int i=1;i<=n;i++){
            a[i].v=read();
        }
        for(int i=1;i<=n;i++){
            a[i].v-=read();
            a[i].id=i;
        }
        sort(a+1,a+1+n);
        int cnt=0;
        for(int i=1;i<=n;i++){
            if(i==1||a[i].v==a[i-1].v)cnt++;
            else break;
        }
        printf("%d\n",cnt);
        for(int i=1;i<=cnt;i++){
            printf("%d ",a[i].id);
        }
        puts("");
    }
}

E

思路

我们发现每个点的答案其实是它与之前的点的答案加上与后面的点的答案加上与自己的答案。而与前面和与后面的前后缀答案都是可以通过递推的方式得到的，我们令 \(pre_i\) 表示 \(i\) 点的前缀答案，\(sub_i\) 表示 \(i\) 点的后缀答案，\(x_i\) 表示 \(i\) 点的坐标，那么有：

\[pre_i=pre_{i-1}-(x_i-x_{i-1})\times(n-i+1)-1\\ sub_i=sub_{i+1}-(x_{i+1}-x_i)\times i-1 \]

代码有点丑，见谅。

\(Code\)

struct node{
    ll v,id,ans1,ans2;
    inline bool operator <(const node &w)const{
        return v<w.v;
    }
}a[200005];
ll ans[200005];
ll T,n;
int main(){
    for(T=read();T--;){
        n=read();
        for(ll i=1;i<=n;i++){
            a[i].v=read();
            a[i].id=i;
            a[i].ans1=a[i].ans2=0;
        }
        sort(a+1,a+1+n);
        for(ll i=2;i<=n;i++){
            a[1].ans1+=a[i].v-a[1].v+1;
        }
        for(ll i=1;i<n;i++){
            a[n].ans2+=a[n].v-a[i].v+1;
        }
        for(ll i=2;i<n;i++){
            a[i].ans1+=a[i-1].ans1-1ll*(a[i].v-a[i-1].v)*(n-i+1)-1;
        }
        for(ll i=n-1;i>=2;--i){
            a[i].ans2+=a[i+1].ans2-1ll*(a[i+1].v-a[i].v)*i-1;
        }
        for(ll i=1;i<=n;i++)ans[a[i].id]=a[i].ans1+a[i].ans2;
        for(ll i=1;i<=n;i++){
            printf("%lld ",ans[i]+1);
        }
        puts("");
    }
}

F

题意：

给定整数序列 \(a\)，多组询问给出 \(x,y\)，每次询问求有多少对 \(a_i,a_j\) 满足：\(i\ne j,a_i+a_j=x,a_i\times a_j=y\)。

思路

因为 \(x,y\) 已知，所以不难想到这是一个二元二次方程求解问题。

由 \(a_i+a_j=x\) 得 \(a_i=x-a_j\)，所以 \(a_i\times a_j=y\) 即 \((x-a_j)a_j=y\) 得到 \(a_j^2-xa_j+y=0\)，假设 \(a_i\le a_j\)，那么由求根公式可得:

\[\begin{cases} a_i=\frac{x-\sqrt{x^2-4y}}{2}\\ a_j=\frac{x+\sqrt{x^2-4y}}{2}\\ \end{cases}\]

只需要用个 map 去判断两个解是否都存在然后统计答案即可。

注：不要用 unordered_map，会被 hack 的！

\(Code\)

ll T,n,m,q;
map<ll,ll>M;
int main(){
    for(T=read();T--;){
        n=read();
        M.clear();
        for(int i=1;i<=n;i++){
            M[read()]++;
        }
        q=read();
        while(q--){
            ll x=read(),y=read(),o=0;
            if(x*x-4*y>=0)o=sqrtl(x*x-4*y);
            if(o*o!=x*x-4*y||(x+o)%2==1)printf("0 ");
            else{
                ll a=(x+o)/2,b=(x-o)/2;
                if(M.find(a)==M.end()||M.find(b)==M.end())printf("0 ");
                else{
                    if(a==b)printf("%lld ",(M[a]-1)*M[a]/2);
                    else printf("%lld ",M[a]*M[b]);
                }
            }
        }
        puts("");
    }
}

G

题意：

求有多少个有 \(n\) 个节点的无向图，使其满足以下条件：

无重边自环。
有且只有一个最小生成树，且为给定树。
最大边权不大于 \(S\)。

对 \(998244353\) 取模。

思路：

其实就是让我们在给定的树加边使得最小生成树不改变。

考虑到在整棵树上我们可以加大于最大边权的任意边使得满足条件，那显然我们断掉最大边后，在各个联通块内随意加大于连通块最大边的边也可以满足条件。

那么我们可以先按照边权将所有边排序，一条一条加入边将节点合并。现在我们先考虑对于两个大小分别为 \(siz_x,siz_y\) 的连通块，用目前最大边 \(w\) 合并，对答案的贡献。

因为 \(x,y\) 内部的贡献已经算过了，所以合并之后显然我们最多只能在 \(x,y\) 之间新增 \(siz_x\times siz_y-1\) 条边，按照上面的理论，每条选了的边可以选 \(S-w\) 个边权，我们令 \(siz_x\times siz_y-1=m\)，那么贡献就为：

\[\binom{m}{0}(S-w)^0+\binom{m}{1}(S-w)^1+\dots+\binom{m}{m}(S-w)^{m} \]

这显然是一个二项式定理的形式，所以可以将其转化为 \((S-w+1)^m\)。

最后将所有贡献相乘即可。

\(Code\)

struct edge{
    int u,v;ll w;
    inline bool operator <(const edge &o)const{return w<o.w;}
}F[200005];
int T,n,fa[200005];
ll fac[200005],ifac[200005],siz[200005],S;
inline int find(int x){return (x==fa[x]?x:(fa[x]=find(fa[x])));}
inline int merge(int x,int y){
    if((x=find(x))==(y=find(y)))return siz[x];
    if(siz[x]>siz[y])x^=y^=x^=y;
    siz[y]+=siz[x],siz[x]=0,fa[x]=y;
    return siz[y]; 
}
ll qpow(ll x,ll w){
    ll res=1;
    for(;w;w>>=1,x=x*x%mod)if(w&1)res=res*x%mod;
    return res;
}
int main(){
    for(T=read();T--;){
        n=read(),S=read();
        fa[n]=n,siz[n]=1;
        for(int i=1;i<n;i++){
            fa[i]=i,siz[i]=1;
            int u=read(),v=read(),w=read();
            F[i]={u,v,w};
        }
        sort(F+1,F+n);
        ll ans=1;
        for(int i=1;i<n;i++){
            int u=find(F[i].u),v=find(F[i].v);
            ll sume=siz[u]*siz[v]-1;//可以加入的边数
            ll sum=qpow(S-F[i].w+1,sume);//二项式定理
            ans=ans*sum%mod;
            merge(u,v);
        }
        printf("%lld\n",ans);
    }
}