Powered by:NEFU AB-IN

B站直播录像！

Link

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)xn$
      假设这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;
    }