题解 | #牛客练习赛Round 122 A-D#

A-黑白配

思路:

• 跳过

以下是代码部分

#include <bits/stdc++.h>
using namespace std;
#define endl '\n';
using ll = long long;
const int N = 1e5 + 10;
int a[N];
void solve()
{
    int n, t;
    cin >> t >> n;
    while(t --)
    {
        int sum1 = 0, sum2 = 0;
        for(int i = 0; i < n; i ++)
        {
            int x; cin >> x;
            if(x == 0) sum1 ++;
            else sum2 ++;
        }
        cout << abs(sum1 - sum2) << endl;
    }

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t --)
        solve();

    return 0;
}

B-映射

思路：

-如果一个key映射的值有两种及以上，则为NO, 为1种， 则为YES。

以下是代码部分

#include <bits/stdc++.h>
using namespace std;
#define endl '\n';
using ll = long long;
const int N = 1e5 + 10;
int a[N], b[N];
map<int, int> mp;
void solve()
{
    mp.clear();
    int n; cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) cin >> b[i];
    for(int i = 1; i <= n; i ++)
    {
        if(mp[a[i]])
        {
            if(mp[a[i]] != b[i])
            {
                cout << "No\n";
                return;
            }
        }
        else
            mp[a[i]] = b[i];
    }
    cout << "Yes\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while(t --)
        solve();

    return 0;
}

C-马走日

思路:

• 一道找规律 分类讨论题
  • 1.在只有1行 or 1列时的情况
  • 2.在3*3时的情况
  • 3.在小于2*2时的情况
  • 4.在大于3*3时的情况

以下是代码部分

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
const int N = 1e5 + 10;

void solve()
{
    ll n, m;
    cin >> n >> m;
    if(n == 1 || m == 1) cout << "1\n";
    else if(n < 3 && m < 3) cout << "1\n";
    else if(n == 2 || m == 2) cout << max(n, m) / 2 + (max(n, m) & 1) << endl;
    else if(n == 3 && m == 3) cout << "8\n";
    else cout << n * m << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while(t --)
        solve();

    return 0;
}

D - 圆

思路:

• 区间dp
  • 为第i个点到第j个点的区间的不相连的线的权值和

以下是代码部分

#include <bits/stdc++.h>
using namespace std;

const int N = 2e3 + 5;
using ll = long long;
//存储l, r, w
struct line {
    ll l, r, w;
} a[N];

bool cmp (line x, line y) { return x.r < y.r;}
//dp[i][j] 代表从i指向j的直线
ll dp[N][N];

void solve()
{
    int n, m, t = 0;
    cin >> n >> m;
    //sum记录总权值
    ll sum = 0, ans = 0;
    //输入
    for (int i = 1; i <= m; i++)
    {
        int l, r, w;
        cin >> l >> r >> w;
        a[i] = {min(l, r), max(r, l), w};
        sum += w;
    }
    //按照线的大的结点的大小排序，升序
    sort (a + 1, a + 1 + m, cmp);
    for (int i = 1; i <= m; i++)
    {
        //复制给l, r, w
        auto [l, r, w] = a[i];
        //从k连接的所有点
        for (int j = t + 1; j <= r; j++)
            for (int k = 1; k <= n; k++)
                dp[k][j] = dp[k][j - 1];

        for (int j = 1; j <= l; j++)
        {
            //
            ll s = 0;
            //
             s += dp[j][l - 1];
            //
            s += dp[l + 1][r - 1];
            //
            dp[j][r] = max (dp[j][r], s + w);
        }
        t = (int)r;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            ans = max (ans, dp[i][j]);
    ans = sum - ans;
    cout << ans << '\n';
}

int main() {solve();return 0;}