VP-ACM-ICPC-WUHAN

A

思路:求公共区间的并集,取最小值.

小模拟,签到.

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
using namespace std;
#define ll long long
#define ld long double
#define PI acos(-1.0)
#define mem(x) memset(x, 0, sizeof(x))
#define  MOD   1000000007
#define  ER  0.00001
#define N 200005
#define inf 0x7FFFFFFF
int dir[4][2] = { {0,-1},{0,1},{1,0},{-1,0} };
struct poss
{
    int pos;
    int l;
    int r;
};
void func()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, q;
        cin >> n >> q;
        int a[105];
        poss pp[105];
        map<int, pair<int, int>>posMap;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
        for (int i = 0; i < q; i++)
        {
            cin >> pp[i].pos >> pp[i].l >> pp[i].r;
            if (posMap.find(pp[i].pos) == posMap.end())
            {
                posMap[pp[i].pos] = make_pair(pp[i].l,pp[i].r);
            }
            else
            {
                posMap[pp[i].pos].first = max(posMap[pp[i].pos].first, pp[i].l);
                posMap[pp[i].pos].second = min(posMap[pp[i].pos].second, pp[i].r);
            }
        }
        ll ans = 0;//呜呜,不开long long 见祖宗!
        bool flag = 1;
        for (auto it = posMap.begin(); it != posMap.end(); ++it) 
        {
            if (it->second.first > it->second.second)
            {
                flag = 0;
                break;
            }
            else
            {
                if (a[it->first] <= it->second.second && it->second.first <= a[it->first])
                {
                    continue;
                }
                else
                {
                    ans += min(fabs(a[it->first] - it->second.first), fabs(a[it->first] - it->second.second));

                }
                
            }
            //cout << it->first << " " << it->second.first << " " << it->second.second << "\n";
        }
        if (flag)
        {
            cout << ans << "\n";
        }
        else
        {
            cout << "-1\n";
        }      
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    func();
  
    return 0;
}

B

首先考虑无解的情况。kn(n−1)+1也不行,因为根据鸽笼原理,涂到n(n−1)+1 时一定至少有一行或一列已经是满的.剩下的情况可以这样构造:把对角线留空,剩下的位置从1 开始填.这样只要把k往对角线上一放,就能填上一行.

签到(bushi)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
using namespace std;
#define ll long long
#define ld long double
#define PI acos(-1.0)
#define mem(x) memset(x, 0, sizeof(x))
#define  MOD   1000000007
#define  ER  0.00001
#define N 200005
#define inf 0x7FFFFFFF
int dir[4][2] = { {0,-1},{0,1},{1,0},{-1,0} };


void func()
{
    int t;
    cin >> t;
    while (t--)
    {
        int a[105][105] = { 0 };
        int n, k;
        cin >> n >> k;

        if (k < n || n * n - n + 1 < k)
        {
            cout << "No" << "\n";
            
        }
        else
        {
            int cur = k;
            for (int i = 0; i < n; i++)
            {
                a[i][i] = cur++;
            }
            cout << "Yes\n";
            cur = 1;
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (i == j)
                    {
                        continue;
                    }
                    if (cur == k)
                    {
                        cur += n;
                    }
                    a[i][j] = cur;
                    cur++;
                }
            }
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    cout << a[i][j] << " ";
                }
                cout << "\n";
            }
        }      
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    func();
    return 0;
}