526互联

武汉大学2023年新生程序设计竞赛

发布时间 2023-10-17 15:11:15作者: PHarr

A-教科书般的亵渎

#include <bits/stdc++.h>

using namespace std;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;
using i32 = int32_t;

int32_t main() {
    int n;
    cin >> n;
    vi a(n);
    for (auto &i: a) cin >> i;
    sort(a.begin(), a.end());
    a.resize(unique(a.begin(), a.end()) - a.begin());
    if( a.front() != 1 ){
        cout << "NO\n";
        return 0;
    }
    for( int i = 1 ; i < a.size() ; i ++ ){
        if( a[i] != a[i-1] + 1 ){
            cout << "NO\n";
            return 0;
        }
    }
    cout << "YES\n";
    return 0;
}

C-覆叶之交

容斥原理

#include <bits/stdc++.h>

using namespace std;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;
using i32 = int32_t;
using i64 = long long;
using i128 = __int128;

int res = 0;

using node = array<i128, 4>;


int area(const node &x) {
    return max(x[2] - x[0], (i128) 0) * max(x[3] - x[1], (i128) 0);
}

int read() {
    int x = 0, f = 1, ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

node operator&(const node &x, const node &y) {
    node z;
    z[0] = max(x[0], y[0]);
    z[1] = max(x[1], y[1]);
    z[2] = min(x[2], y[2]);
    z[3] = min(x[3], y[3]);
    return z;
}

int32_t main() {
    vector<node> p(3);
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++) p[i][j] = read();
        if (p[i][0] > p[i][2]) swap(p[i][0], p[i][2]);
        if (p[i][1] > p[i][3]) swap(p[i][1], p[i][3]);
    }
    i128 res = 0;
    res = area(p[0]) + area(p[1]) + area(p[2]);
    res -= area(p[0] & p[1]);
    res -= area(p[0] & p[2]);
    res -= area(p[1] & p[2]);
    res += area(p[0] & p[1] & p[2]);
    cout << (i64) res << "\n";
    return 0;
}

E-不是n皇后问题

直接按顺序放置

#include <bits/stdc++.h>

using namespace std;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;
using i32 = int32_t;


int32_t main() {
    int n ;
    cin >> n;
    for( int i = 0 ; i < n ; i ++ ){
        for( int j = 1 ; j <= n ; j ++ )
            cout << i * n + j << " ";
        cout << "\n";
    }
    return 0;
}

J-放棋子

对于一维来说，按照顺序放置最优，同理可以类推到二维，对于贡献，我们用前缀和维护一下即可

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m, res = 0;
    cin >> n >> m;
    vi cnt(m, 0);
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0, pre = 0; j < m; j++) {
            if (s[j] == '#') {
                pre++, cnt[j]++;
                res += pre * pre + cnt[j] * cnt[j];
            } else pre = cnt[j] = 0;
        }
    }
    cout << res << "\n";
    return 0;
}

K-矩形分割

每次按照短边尽可能的切分就好了

#include <bits/stdc++.h>

using namespace std;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;
using i32 = int32_t;

int res = 0;

void dfs(int x, int y) {
    if (x > y) swap(x, y);
    if( x == 0 ) return ;
    int t = y / x;
    res += t * x;
    dfs(x, y % x);
    return ;
}

int32_t main() {
    int n, m;
    cin >> n >> m;
    dfs(n, m);
    cout << res << "\n";
    return 0;
}

L-小镜的数学题

要想使得每一位都为零，则至少要让每一位都至少有一个零，所以最高为零一定要使得最高位发生一次进位

#include <bits/stdc++.h>

using namespace std;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;
using i32 = int32_t;


int32_t main() {
    int n , cnt = 0;
    cin >> n;
    while( n ) cnt ++ , n >>= 1;
    cout << (1ll << cnt) << "\n";
    return 0;
}