526互联

CF#892 div2

发布时间 2023-08-14 00:31:33作者: devilran

过了abc，卡在了d

A

将数组a拆分乘数组b和c，使得满足任意c[i]不是b[j]的因子，b和c中至少存在一个数。

如果不能输出-1

法一：

巧妙构造：

因为一个大的数不可能是一个小的数的因子，所以我把最大的数(最大的数数量可能有很多个，需要全都放在c里面，因为两个相等的数之间也互为因子)放在c后，其他剩下的数放在b，即构造成功。

只有当所有的数都是最大的数(也就是a中所有数都相等)，没有数放到b，输出-1

// 赛时代码
#include <bits/stdc++.h>

#define LL long long
#define ULL unsigned long long
#define x first
#define y second
#define endl "\n"

using namespace std;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int INF = 0x3f3f3f3f;

void solve()
{
    int n;
    cin >> n;

    vector<int> a(n);
    int maxv = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        maxv = max(maxv, a[i]);
    }

    sort(a.begin(), a.end());
    if (maxv == a[0])
    {
        cout << "-1" << endl;
        return;
    }

    int pos = 0;
    for (int i = 0; i < a.size(); i++)
        if (a[i] == maxv)
        {
            pos = i;
            break;
        }

    cout << pos << ' ' << n - pos << endl;
    for (int i = 0; i < pos; i++)
        cout << a[i] << ' ';
    cout << endl;
    for (int i = pos; i < a.size(); i++)
        cout << a[i] << ' ';
    cout << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}

法二： from jiangly

SCC

如果 x % y == 0，连接一条 x -> y 的有向边。

一个强连通分量里面的点互相之间都满足 x % y == 0，所以一个强连通分量里面的点需要全放在b或者c里面。

如果整个图只有一个强连通分量的话，故输出-1

如果大于一个的话，因为SCC后按照下标递减的顺序就是拓扑排序

所以 bel[i] == 0 => 表示的是只有入度没有出度的那个点

除了这个强连通分量里的点都不是这些点的因子，其他点都只可能是这些点的倍数

#include <bits/stdc++.h>

#define LL long long
#define ULL unsigned long long
#define x first
#define y second
#define endl "\n"

using namespace std;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int INF = 0x3f3f3f3f;

struct SCC
{
    int n;
    vector<vector<int>> adj;
    vector<int> stk;
    vector<int> dfn, low, bel;
    int cur, cnt;

    SCC() {}
    SCC(int n)
    {
        init(n);
    }

    void init(int n)
    {
        this->n = n;
        adj.assign(n, {});
        dfn.assign(n, -1);
        low.resize(n);
        bel.assign(n, -1);
        stk.clear();
        cur = cnt = 0;
    }

    void addEdge(int u, int v)
    {
        adj[u].push_back(v);
    }

    void dfs(int x)
    {
        dfn[x] = low[x] = cur++;
        stk.push_back(x);

        for (auto y : adj[x])
        {
            if (dfn[y] == -1)
            {
                dfs(y);
                low[x] = min(low[x], low[y]);
            }
            else if (bel[y] == -1)
            {
                low[x] = min(low[x], dfn[y]);
            }
        }

        if (dfn[x] == low[x])
        {
            int y;
            do
            {
                y = stk.back();
                bel[y] = cnt;
                stk.pop_back();
            } while (y != x);
            cnt++;
        }
    }

    vector<int> work()
    {
        for (int i = 0; i < n; i++)
        {
            if (dfn[i] == -1)
            {
                dfs(i);
            }
        }
        return bel;
    }
};

void solve()
{
    int n;
    cin >> n;

    SCC g(n);
    vector<int> a(n);

    for (int i = 0; i < n; i++)
        cin >> a[i];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (a[i] % a[j] == 0)
                g.addEdge(i, j);

    auto bel = g.work();
    if (bel == vector(n, 0))
    {
        cout << -1 << endl;
        return;
    }

    vector<int> b, c;
    for (int i = 0; i < n; i++)
    {
        if (bel[i] == 0)
            b.push_back(i);
        else
            c.push_back(i);
    }

    cout << b.size() << ' ' << c.size() << endl;

    for(auto i : b)
        cout << a[i] << " \n"[i == b.back()];
    for(auto i : c)
        cout << a[i] << " \n"[i == c.back()];
    
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int t;
    cin >> t;

    while (t--)
    {
        solve();
    }

    return 0;
}

B

最小的 + 选 n-1 组中的次小值

  • 如果最小的不动，那么就是最小的加上其他所有组的次小值
  • 如果最小的动，这组变成加次小值，最小的移动到的组变成加最小值

两种情况是等价的

比赛的时候我是暴力枚举把哪 n-1 行的最小值扔到 另外一行 在加上这一行(包括被扔过来的)的最小值

// 赛时代码
#include <bits/stdc++.h>

#define LL long long
#define ULL unsigned long long
#define x first
#define y second
#define endl "\n"

using namespace std;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int INF = 0x3f3f3f3f;

void solve()
{
    int n, m;
    cin >> n;

    vector<int> vm1(n + 1), vm2(n + 1);
    vector<vector<int>> a(n + 1);

    for (int i = 1; i <= n; i++)
    {
        cin >> m;
        int minv1 = INF, minv2 = INF;

        a[i].resize(m + 1);
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];

            if (a[i][j] < minv1)
            {
                minv2 = minv1;
                minv1 = a[i][j];
            }
            else if (a[i][j] < minv2)
            {
                minv2 = a[i][j];
            }
        }

        vm1[i] = minv1;
        vm2[i] = minv2;
    }

    LL ans = 0;
    for (int i = 1; i <= n; i++)
    {
        LL res = 0;
        int minv = vm1[i];
        for (int j = 1; j <= n; j++)
            if (i != j)
            {
                res = res + (LL)vm2[j];
                minv = min(minv, vm1[j]);
            }
        res = res + (LL)minv;
        ans = max(ans, res);
    }

    cout << ans << endl;

    // for (int i = 1; i <= n; i++)
    //     cerr << i << ' ' << vm1[i] << ' ' << vm2[i] << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int t;
    cin >> t;

    while (t--)
    {
        solve();
    }

    return 0;
}

from jiangly