CF300 Div.2 全场题解

T1

题面

Vitaly 有 _n_ 个不同的整数数组。Vitaly 希望将此数组分成三个非空集合，以便满足以下条件：

1. 第一组所有数字的乘积小于零 （ < 0）。
2. 第二组中所有数字的乘积大于零 （ > 0）。
3. 第三组所有数字的乘积等于零。
4. 初始数组中的每个数字必须恰好出现在一组中。
   帮助维塔利。除以给定的数组。

   题解

   分别统计小于0等于0和大于0的数，然后如果小于0的是偶数个直接丢给0一个，然后如果没有大于0的那就分给大于0的两个负数，最后去重输出即可。

   Code

   #include<bits/stdc++.h>  
   using namespace std;  
     
   int main() {  
       int n;  
       cin >> n;  
       vector<int>s(n);  
       set<int> a, b, c;  
       for (int i = 0; i < n; i++) {  
           cin >> s[i];  
           if (s[i] < 0) {  
               a.insert(s[i]);  
           } else if (s[i] > 0) {  
               b.insert(s[i]);  
           } else {  
               c.insert(s[i]);  
           }  
       }  
       if (a.size() % 2 == 0) {  
           int y;  
           for (int x : a) {  
               y = x;  
               break;  
           }  
           c.insert(y);  
           a.erase(y);  
       }  
       if (b.size() == 0) {  
           int y;  
           for (int x : a) {  
               y = x;  
               break;  
           }  
           b.insert(y);  
           a.erase(y);  
           for (int x : a) {  
               y = x;  
               break;  
           }  
           b.insert(y);  
           a.erase(y);  
       }  
       cout << a.size() << " ";  
       for (int i : a)cout << i << " ";  
       cout << endl;  
       cout << b.size() << " ";  
       for (int i : b)cout << i << " ";  
       cout << endl;  
       cout << c.size() << " ";  
       for (int i : c)cout << i << " ";  
       cout << endl;  
       return 0;  
   }

   T2

   题面

   一个编程教练有 _n_ 个学生要教。我们知道 _n_ 可以被 3 整除。假设所有学生的编号都从 1 到 _n_（含）。
   在大学编程锦标赛之前，教练希望将所有学生分成三人一组。对于某些学生，我们知道他们想在同一个团队中。此外，如果第 _i_ 个学生想和第 _j_ 个学生在同一个团队，那么第 _j_ 个学生想和第 _i_ 个学生在同一个团队。教练希望球队表现出良好的成绩，因此他希望满足以下条件：如果第 _i_ 个学生想与_第 j_ 个学生在同一个团队中，那么第 _i_ 个学生和第 _j_ 个学生必须在同一个团队中。此外，很明显，每个学生必须只属于一个团队。
   帮助教练并按照他想要的方式划分球队。

   题解

   看到分组直接想并查集，直接判断是否能恰好分完，然后我们分讨3个全的，2个的，1个落单的，这些情况能凑的凑，3个的不用管，最后多余了直接-1，然后输出即可。

   Code

   #include <bits/stdc++.h>
   using namespace std;
   int fa[114], sz[114];
   int n, m;
   
   int find(int x) {
       if (fa[x] != x) {
           fa[x] = find(fa[x]);
       }
       return fa[x];
   }
   
   void hb(int x, int y) {
       x = find(x);
       y = find(y);
       if (x == y) return;
       if (sz[x] < sz[y]) swap(x, y);
       fa[y] = x;
       sz[x] += sz[y];
   }
   
   int main() {
       cin >> n >> m;
       for (int i = 1; i <= n; i++) {
           fa[i] = i;
           sz[i] = 1;
       }
       for (int i = 0; i < m; i++) {
           int a, b;
           cin >> a >> b;
           hb(a, b);
       }
       for (int i = 1; i <= n; i++) {
           find(i);
       }
       map<int, vector<int >> mp;
       for (int i = 1; i <= n; i++) {
           mp[fa[i]].push_back(i);
       }
       vector<int> one;
       vector<vector<int >> two;
       vector<vector<int >> ret;
       bool f = 1;
       for (auto i : mp) {
           int size = i.second.size();
           if (size > 3) {
               f = 0;
               break;
           } else if (size == 1) {
               one.push_back(i.second[0]);
           } else if (size == 2) {
               two.push_back(i.second);
           } else if (size == 3) {
               ret.push_back(i.second);
           }
       }
       if (!f || two.size() > one.size()) {
           cout << -1;
           return 0;
       }
       for (int i = 0; i < two.size(); i++) {
           vector<int> zu = two[i];
           zu.push_back(one.back());
           one.pop_back();
           ret.push_back(zu);
       }
       for (int i = 0; i < one.size(); i += 3) {
           ret.push_back({one[i], one[i + 1], one[i + 2]});
       }
       for (auto zu : ret) {
           for (int i = 0; i < 3; i++) {
               cout << zu[i] << " ";
           }
           cout << endl;
       }
       return 0;
   }

R1T1:

题意：

​ 给你好几种种类的物品，每个物品有个体积和价值，但是购买某种种类之前需要先支付一个前置代价，问你最多能获得多少价值。

题解：

​ 一个依赖背包的模版题，我们设 $dp_{i,j}$ 表示当前选了 $i$ 种类物品，花费 $j$ 能获得的价值。我们可以先处理出选择当前这一组支付代价的情况，然后进行模版 $0/1$ 背包就可以了。

Code：

#include<bits/stdc++.h>
using namespace std;
const int INF=1e9+7;
struct node{
    int c,w;
}num[55][15];
int dp[55][100005],val[1145140],s[1145140],n,m;

signed main()
{
    while(cin>>n>>m)
    {
        for(int i=1;i<=n;i++)
        {
            cin>>val[i]>>s[i];
            for(int j=1;j<=s[i];j++)cin>>num[i][j].c>>num[i][j].w;
        }
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=m;j++)
                dp[i][j]=-INF;
            for(int j=val[i];j<=m;j++)
                dp[i][j]=dp[i-1][j-val[i]];
            for(int j=1;j<=s[i];j++)
                for(int k=m;k>=num[i][j].c;k--)
                    dp[i][k]=max(dp[i][k],dp[i][k-num[i][j].c]+num[i][j].w);
            for(int j=0;j<=m;j++)dp[i][j]=max(dp[i][j],dp[i-1][j]);
        }
        int ans=-1;
        for(int i=1;i<=n;i++)
            for(int j=0;j<=m;j++)
                ans=max(ans,dp[i][j]);
        cout<<ans<<endl;
    }
    return 0;
}

R1T4：

题意：

​ 每个节点有个点权，每条边有边权，每个点有个松鼠，你需要把某些点权运送到各个点，然后让所有点权的方差最小。

题解：

​ 方差最小即为尽量平均分配，那么最优情况肯定是 $sum(mod)n$ 个多出来的点，那么我们不妨设 $dp_{i,j}$ 为以 $i$ 为子树，$j$ 个点权为 $sum(mod)n$ 个点的最小操作代价。考虑树形背包，假设前面和下面都算好了，对于一个新的点 $v$，我们有 $dp_{now,i+j}=dp_{v,j}+dp_{now,i}+pnum\times w$ 其中，$pnum=abs(ave\times (sz[now]+sz[v])-a[now]-a[v]+i+j)-abs(ave\times sz[now]-a[now]+i)$。不难理解，我们给之前点分配 $i$ 容量，当前的 $v$ 分配 $j$ 容量，转移只需要加上边的经过次数乘边权即可。所以答案就是 $dp_{1,sum(mod)n}$，即根节点的价值。

Code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1e18;
int n,a[1145140],x,y,z,sum,sz[1145140],dp[105][100005],dp2[105][100005],ave,s;
vector<pair<int,int>> v[1145140];

void dfs(int now,int fa,int w)
{
    sz[now]=1;
    for(int i=0;i<=min(sz[now],s);i++)dp[now][i]=abs(ave+i-a[now])*w;
    for(auto go:v[now])
    {
        if(go.first==fa)continue;
        dfs(go.first,now,go.second);
        int v=go.first;
        for(int i=0;i<=min(sz[now]+sz[v],s);i++)dp2[now][i]=INF;
        for(int i=0;i<=sz[now];i++)
            for(int j=0;j<=sz[v];j++)
                if(i+j<=s)
                {
                    int val1=abs(ave*(sz[now]+sz[v])-a[now]-a[v]+i+j);
                    int val2=abs(ave*sz[now]-a[now]+i);
                    dp2[now][i+j]=min(dp2[now][i+j],dp[now][i]+dp[v][j]+(val1-val2)*w);
                }
        for(int i=0;i<=min(sz[now]+sz[v],s);i++)dp[now][i]=dp2[now][i];
        sz[now]+=sz[v];a[now]+=a[v];
    }
}

signed main()
{
    while(cin>>n)
    {
        sum=0;
        for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}
        for(int i=1;i<n;i++)
        {
            v[i].clear();
            cin>>x>>y>>z;
            x++,y++;
            v[x].push_back({y,z});
            v[y].push_back({x,z});
        }
        ave=sum/n,s=sum%n;
        dfs(1,0,0ll);
        cout<<dp[1][s]<<endl;
    }
    return 0;
}

E - Empire Strikes Back

Problem - E - Codeforces

题意

求满足下式的最小 $n$ ：

$$\prod_{i=1}^k a_i! \mid n!$$

题解

显然 $n$ 有单调性，考虑二分和 Check，不难有初版代码：

int cnt[MaxN];

inline ll Calc(ll a, ll p) {
    ll ans = 0;
    while(a) {
        ans += a / p;
        a /= p;
    }
    return ans;
}

inline bool Check(ll mid) {
    for(auto &p : prm) {
        if(Calc(mid, p) < cnt[p]) {
            return false;
        }
    }
    return true;
}

inline void Work() {
    Init(); // 素数筛
    for(auto &p : prm) {
        for(int i = 1; i <= n; i++) {
            cnt[p] += Calc(a[i], p);
        }
    }
    ll l = 1, r = 1e13, best = -1;
    while(l <= r) {
        ll mid = (l + r) >> 1;
        if(Check(mid)) {
            best = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    printf("%lld\n", best);
}

很显然 cnt 的初始化出锅了，考虑优化。于是平铺阶乘整体计算：

for(int i = MaxN - 10; i >= 1; i--) cnt[i] += cnt[i+1];
for(int i = MaxN - 10; i >= 2; i--) {
    if(lep[i] != i) cnt[lep[i]] += cnt[i];
    cnt[i/lep[i]] += cnt[i];
}

于是本题结束了。