Acwing 第 91 场周赛

A AcWing 4861. 构造数列

题意

略
思路

将每个数的每一位全部拆出来即可

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-02-18 18:59:30
* @FilePath: \Acwing\91cp\a\a.cpp
* @LastEditTime: 2023-02-18 19:03:25
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

signed main()
{
    IOS;
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        int cnt = 0;
        vector<int> ans;
        while (n)
        {
            int k = n % 10;
            int x = k * pow(10, cnt);
            if (x)
                ans.push_back(x);
            n /= 10;
            cnt++;
        }
        cout << SZ(ans) << '\n';
        for (auto i : ans)
            cout << i << " ";
        cout << '\n';
    }
    return 0;
}

B AcWing 4862. 浇花

题意

CF 44 Holidays
略
思路

差分裸题，没什么好说的

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-02-18 18:59:30
* @FilePath: \Acwing\91cp\b\b.cpp
* @LastEditTime: 2023-02-18 19:10:40
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int p[N], sum[N];
signed main()
{
    IOS;
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int a, b;
        cin >> a >> b;
        p[a]++;
        p[b + 1]--;
    }
    for (int i = 1; i <= n; ++i)
    {
        sum[i] = sum[i - 1] + p[i];
        if (sum[i] != 1)
        {
            cout << i << " " << sum[i];
            return 0;
        }
    }
    cout << "OK";
    return 0;
}

C AcWing 4863. 构造新矩阵

题意

略
思路

在B站视频中有详细的解说，这里我就简单提几句
二分L，由于最多抽n-1行，那么根据题意和贪心思想，抽越多越好，那么就抽n-1行
矩阵满足两个条件
- 第一个条件：要使得新矩阵满足 每一列都至少存在一个元素不小于 L，则原矩阵也必须满足每一列至少存在一个元素不小于 L
  接下来的突破点在于n - 1这个限制，也就是说得到的新矩阵，就是 $(n-1) x n$
  假设这n-1行每一行都分别提供了一列的需求，那也还差一行，所以必须有一行提供了至少两列的需求
- 第二个条件：原矩阵中必须至少有一行满足有两个及两个以上的元素不小于L
时间复杂度: $O(nmlog(1e9))$

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-02-18 18:59:30
* @FilePath: \Acwing\91cp\c\c.cpp
* @LastEditTime: 2023-02-18 21:09:06
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

void solve()
{
    int m, n;
    cin >> m >> n;
    vector<vector<int>> g(m + 1, vector<int>(n + 1));

    auto check = [&](int x) {
        vector<int> cnt1(n);
        vector<int> cnt2(m);

        for (int j = 0; j < n; ++j)
        {
            for (int i = 0; i < m; ++i)
            {
                if (g[i][j] >= x)
                {
                    cnt1[j] = 1;
                    cnt2[i] += 1;
                }
            }
            if (!cnt1[j])
                return false;
        }

        for (int i = 0; i < m; ++i)
        {
            if (cnt2[i] >= 2)
                return true;
        }
        return false;
    };

    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            cin >> g[i][j];
    int l = 1, r = 1e9;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    cout << l << '\n';
}

signed main()
{
    IOS;
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

Acwing 第 91 场周赛

A AcWing 4861. 构造数列

题意

思路

代码

B AcWing 4862. 浇花

题意

思路

代码

C AcWing 4863. 构造新矩阵

题意

思路

代码