Gym-100506解题报告

发表于 2022-12-22 分类于解题报告

A. Average distance

题意：有一棵 $n$ 节点的带边权树，求不同点对的平均距离。

平均距离即为总距离除以数量，所以考虑总距离。显然可以树形 DP，让点对的贡献在 LCA 处统计。维护 $f[u]$ 表示以 $u$ 为根的子树内所有节点到 $u$ 的距离之和， $sz[u]$ 表示子树大小，转移显然。统计答案时，对于每个儿子 $u\to v(w)$ ，考虑从 $v$ 内的每个节点往其他子树的贡献都需要先到 $u$ ，而往其他子树贡献的次数为 $sz[u]-sz[v]$ ，所以每个子树 $v$ 造成 $(f[v]+w)*(sz[u]-sz[v])$ 的贡献。

By cxm1024

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int,int> > a[10010];
int f[10010],sz[10010];
int dfs(int now,int fa) {
    vector<pair<int,int> > to;
    sz[now]=1;
    for(auto [v,w]:a[now]) {
        if(v==fa) continue;
        int tmp=dfs(v,now);
        to.push_back({v,tmp+w*sz[v]});
        sz[now]+=sz[v];
    }
    int res=0;
    for(auto [v,w]:to) {
        res+=w;
        f[now]+=w*(sz[now]-sz[v]);
    }
    return res;
}
signed main() {
    int t;
    scanf("%lld",&t);
    while(t--) {
        int n,ans=0;
        scanf("%lld",&n);
        for(int i=0;i<n;i++)
            a[i].clear();
        memset(f,0,sizeof(f));
        memset(sz,0,sizeof(sz));
        for(int i=1;i<n;i++) {
            int x,y,z;
            scanf("%lld%lld%lld",&x,&y,&z);
            a[x].push_back({y,z});
            a[y].push_back({x,z});
        }
        dfs(0,0);
        for(int i=0;i<n;i++)
            ans+=f[i];
        printf("%.7Lf\n",(long double)ans/(n*(n-1)/2));
    }
    return 0;
}

B. Bus Pass

给你一个 $n$ 个点 $m$ 条边的无向连通图，没有边权。选中了 $k$ 个特殊点，你需要确定一个中心点，使其到特殊点的距离最大值最小。距离为最短路长度。答案相同输出编号较小的中心点。 $T\le 100,n\le 10^4,m\le 5\times 10^4,k\le 200$ 。

显然可以对于每个特殊点跑一遍 BFS，更新每个节点到最远的特殊点的距离，最后统计最远距离最小的点作为答案即可。复杂度 $O(Tkm)$ 。

By cxm1024

#include<bits/stdc++.h>
using namespace std;
vector<int> a[10010];
int dis[10010];
bool vis[10010];
signed main() {
    int t;
    cin>>t;
    while(t--) {
        for(int i=1;i<=10000;i++)
            a[i].clear();
        int n,m;
        cin>>n>>m;
        set<int> ver;
        for(int i=1;i<=n;i++) {
            int x,y,cnt;
            cin>>x>>cnt;
            ver.insert(x);
            while(cnt--) {
                cin>>y;
                a[x].push_back(y);
            }
        }
        set<int> st;
        for(int i=1;i<=m;i++) {
            int cnt,x;
            cin>>cnt;
            while(cnt--) {
                cin>>x;
                st.insert(x);
            }
        }
        memset(dis,0,sizeof(dis));
        for(int s:st) {
            memset(vis,0,sizeof(vis));
            queue<pair<int,int> > q;
            q.push({s,1});
            while(!q.empty()) {
                auto [u,d]=q.front();q.pop();
                if(vis[u]) continue;
                vis[u]=1,dis[u]=max(dis[u],d);
                for(int v:a[u])
                    if(!vis[v]) q.push({v,d+1});
            }
        }
        int ans=0,mind=1e9;
        for(int i:ver)
            if(dis[i]<mind) ans=i,mind=dis[i];
        cout<<mind<<" "<<ans<<endl;
    }
    return 0;
}

C. Cutting Banknotes

题意：有 $n$ 种不同的钞票 $a_1,a_2\cdots a_n$ ，每种任意张，可以将钞票砍成面值为原来 $1/2$ 的两半，可以有找零，问有限次操作是否能购买价值为 $x$ 的物品。 $x$ 小数点后最多 $2$ 位。

转化一下，即为 $k_1a_1+k_2a_2+\cdots+k_na_n=2^px$ 。为了避免两位小数的影响，同时乘 $100$ ，得 $25(k_1a_1+k_2a_2+\cdots k_na_n)=2^p\cdot 100x$ （左边因数 $4$ 可以归到右边 $2^p$ 内），其中 $100x$ 为整数。

首先判断右边 $100x$ 是否为 $25$ 的倍数。如果是则可以除到右边，转化为 $k_1a_1+k_2a_2+\cdots+k_na_n=2^p\cdot 4x$ ，其中 $4x$ 为整数。这个式子显然为裴蜀定理的形式，有解的充要条件为 $2^p\cdot 4x$ 是 $\gcd(a_1,a_2,\cdots,a_n)$ 的倍数。由于有一个 $2^p$ ，所以可以将 $\gcd$ 中所有 $2$ 的因数全部消掉，判断剩下的 $4x$ 是否为删掉 $2$ 的因数的 $\gcd$ 的倍数即可。

By cxm1024

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b) {
    if(b==0) return a;
    return gcd(b,a%b);
}
signed main() {
    int t;
    cin>>t;
    while(t--) {
        double x;
        int n,m,d=0;
        cin>>x>>n;
        m=int(x*100+0.5);
        for(int i=1;i<=n;i++) {
            int k;
            cin>>k;
            d=gcd(d,k);
        }
        while(d%2==0) d/=2;
        if(m%25!=0) cout<<"no"<<endl;
        else if(m/25%d==0) cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
    return 0;
}

D. Dice Password Security

题意：给你一个 $n$ 个单词的集合，每个单词可以使用任意多次，只能使用恰好 $m$ 个单词。每次询问组成长度为 $k$ 的字符串的方案数。

每个单词只有长度信息有用，所以存数组 $a[i]$ 表示第 $i$ 个单词的长度。考虑 DP：设 $f[i][j][k]$ 表示考虑前 $i$ 个单词，已经用了 $j$ 个，长度为 $k$ 的方案数。则转移枚举这一个单词使用几次，用插板法组合数求这些单词放置的位置即可。

By cxm1024

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXV=5;
int jc[MAXV+5];
int ksm(int a,int b,int res=1) {
    for(;b;a=a*a,b>>=1)
        if(b&1) res=res*a;
    return res;
}
void init() {
    jc[0]=1;
    for(int i=1;i<=MAXV;i++)
        jc[i]=jc[i-1]*i;
}
int C(int x,int y) {
    return jc[x]/jc[y]/jc[x-y];
}
int a[10010],f[2][6][52];
signed main() {
    init();
    int t;
    cin>>t;
    while(t--) {
        memset(f,0,sizeof(f));
        int n,m,q;//n个单词，用m个，q次询问
        cin>>n>>m>>q;
        for(int i=1;i<=n;i++) {
            string s;
            cin>>s;
            a[i]=s.size();
        }
        f[0][0][0]=1;
        for(int i=1;i<=n;i++) {
            int x=i%2,y=1-x;
            for(int j=0;j<=m;j++)
                for(int k=0;k<=50;k++) {
                    f[x][j][k]=0;
                    for(int cnt=0;cnt<=j&&cnt*a[i]<=k;cnt++)
                        f[x][j][k]+=f[y][j-cnt][k-cnt*a[i]]*C(j,cnt);
                }
        }
        while(q--) {
            int l;
            cin>>l;
            cout<<f[n%2][m][l]<<endl;
        }
    }
    return 0;
}

G. Pachinko

题意：有一个矩阵，有些格子有障碍，有些格子有洞，每个洞有权值。你可以将一个小球放在任意一列的顶端，经过洞会掉进洞里，得分为该洞的权值，碰到障碍会随机向左或向右。问最大期望得分。

显然可以 DP。 $f[i][j]$ 表示如果当前走到 $(i,j)$ 的期望得分，则如果有洞直接得到答案；如果没有障碍， $f[i][j]=f[i+1][j]$ ；如果有障碍， $f[i][j]=\frac{1}{2}f[i+1][j-1]+\frac{1}{2}f[i+1][j+1]$ 。

By cxm1024

#include<bits/stdc++.h>
using namespace std;
string s[110];
double f[110][110];
signed main() {
    int t;
    cin>>t;
    while(t--) {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++) {
            cin>>s[i];
            s[i]=" "+s[i];
            for(int j=1;j<=m;j++)
                f[i][j]=0;
        }
        for(int j=1;j<=m;j++)
            if(s[n][j]!='*'&&s[n][j]!='.')
                f[n][j]=s[n][j]-'0';
        for(int i=n-1;i>0;i--)
            for(int j=1;j<=m;j++) {
                if(s[i][j]=='*') continue;
                if(s[i][j]!='.') f[i][j]=s[i][j]-'0';
                else if(s[i+1][j]=='*') f[i][j]=f[i+1][j-1]*0.5+f[i+1][j+1]*0.5;
                else f[i][j]=f[i+1][j];
            }
        double ans=0;
        for(int j=1;j<=m;j++)
            ans=max(ans,f[1][j]);
        printf("%.7lf\n",ans);
    }
    return 0;
}

I. Ranking

题意：给定 $n$ 个人在比赛中的提交记录，输出排名信息。排名规则如下：

做题数越多越好。

做题相同，罚时越低越好。每道题罚时为，这道题的第一次 AC 时间，加上在第一次 AC 之前的错误提交次数*20min。总罚时为每道 AC 的题目的罚时之和。

罚时相同，考虑两队最晚的“得分/罚时不同”的时刻，此时得分越高越好，得分相同罚时越低越好。

得分罚时的时间完全相同，则被认为平局。输出时排名要相同，但要先输出名字字典序较小的。

按照题意模拟即可。需要充分利用 STL 中的容器。

By cxm1024

#include<bits/stdc++.h>
using namespace std;
struct node {
    int pen;
    string st;
    vector<pair<int,int> > sub;
} a[55];
signed main() {
    int t;
    cin>>t;
    while(t--) {
        int n,m;
        cin>>n>>m;
        map<string,pair<int,vector<pair<int,int> > > > mp;
        map<pair<string,char>,pair<bool,int> > done;
        map<string,int> ind;
        for(int i=1;i<=n;i++) {
            string s;
            cin>>s;
            mp[s]={0,vector<pair<int,int> >()};
            ind[s]=i,a[i].st=s;
        }
        for(int i=1;i<=m;i++) {
            int t;
            string tm,op;
            char pr;
            cin>>t>>tm>>pr>>op;
            if(op=="rejected") {
                if(!done[{tm,pr}].first)
                    done[{tm,pr}].second+=20;
            }
            else {
                if(!done[{tm,pr}].first) {
                    done[{tm,pr}].first=1;
                    mp[tm].first+=t+done[{tm,pr}].second;
                    mp[tm].second.push_back({t,-done[{tm,pr}].second});
                }
            }
        }
        for(auto tmp:mp) {
            int x=ind[tmp.first];
            a[x].pen=tmp.second.first;
            a[x].sub=tmp.second.second;
            reverse(a[x].sub.begin(),a[x].sub.end());
        }
        sort(a+1,a+n+1,[](node p,node q) {
            if(p.sub.size()!=q.sub.size()) return p.sub.size()>q.sub.size();
            if(p.pen!=q.pen) return p.pen<q.pen;
            if(p.sub!=q.sub) return p.sub<q.sub;
            return p.st<q.st;
        });
        for(int i=1,now=0;i<=n;i++) {
            if(i==1||a[i].sub!=a[i-1].sub) now=i;
            cout<<now<<" "<<a[i].st<<" "<<a[i].sub.size()<<" "<<a[i].pen<<endl;
        }
    }
    return 0;
}

J. Stock

题意：有一个股票，第 $i$ 天你会获得 $x_i$ 股（可以保存到后面），当天卖价为 $p_i$ ，当天最多能卖 $m_i$ 股。问最大赚钱量。

考虑最后一天获得的股票必须最后一天卖，剩下卖不掉的只能舍弃。倒数第二天可以选择当天卖还是到最后一天卖（如果有剩余），显然应该贪心地选最贵的那一天卖，用完剩余量了再选次贵的那一天卖，以此类推。

这个做法的本质在于股票之间没有区别，所以可以贪心选最贵的。如果这个不卖给最贵的而将前面几天的卖给最贵的，没有任何区别。

By cxm1024

#include<bits/stdc++.h>
using namespace std;
#define int long long
int x[100010],p[100010],m[100010];
signed main() {
    int t;
    cin>>t;
    while(t--) {
        int n,ans=0;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>x[i]>>p[i]>>m[i];
        map<int,int> mp;
        for(int i=n;i>0;i--) {
            mp[p[i]]+=m[i];
            auto tmp=--mp.end();
            while(x[i]>0&&!mp.empty()) {
                if(x[i]<(*tmp).second)
                    (*tmp).second-=x[i],ans+=(*tmp).first*x[i],x[i]=0;
                else x[i]-=(*tmp).second,ans+=(*tmp).first*(*tmp).second,mp.erase(tmp);
                if(!mp.empty()) tmp=--mp.end();
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}