Back to Blog

XCU 12.7日练习赛题解

头文件这个不用管，不写是怕有些变量我没写，引起误会里面的$constepxr$我会修改他的参数$n,m,x$我也会修改 这道题是一道签到题，出这道题是想让同学们了解一下 赛制的简单规则。是很简单的直接模拟就行 这道题是比较思维的一道题，如果直接暴力求的话就会超时，因为我们知道他把$|a i - a j|$都加到了...

Type 题解

Created Dec 08, 2025, 03:00:00 / Updated Dec 08, 2025, 03:00:00

Views — / Comments — / Words 534

12.7日练习赛题解

头文件这个不用管，不写是怕有些变量我没写，引起误会里面的constepxrconstepxr我会修改他的参数n,m,xn,m,x我也会修改

#include <bits/stdc++.h>

#define endl '\n'
#define x first
#define y second
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

namespace {
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(x, ...)
#define debug2(a, b)
#define debugv(v)
#define debugp(p)
#define debugm(mp)
#define debugum(umap)
#define debugs(s)
#define debug2d(v)
#define debugvp(vp)
#endif
} // namespace

namespace QuickRead {
    char buf[1 << 21], *p1 = buf, *p2 = buf;
    inline int getc() {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
    }
    // #define getc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin)), p1 == p2 ? EOF : *p1++)
    template <typename T>
    inline void read(T &a) {
        T ans = 0;
        bool f = 0;
        char c = getc();
        for (; c < '0' || c > '9'; c = getc()) {
            if (c == '-')
                f = 1;
        }
        for (; c >= '0' && c <= '9'; c = getc()) {
            ans = ans * 10 + c - '0';
        }
        a = f ? -ans : ans;
    }

    template <typename T, typename... Args>
    inline void read(T &a, Args &...args) {
        read(a), read(args...);
    }
    template <typename T>
    void write(T x) {
        if (x < 0)
            putchar('-'), x = -x;
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
} // namespace QuickRead
using namespace QuickRead;

using i64 = long long;
using ll = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
typedef pair<int, int> pii;
typedef pair<int, string> pis;
typedef pair<int, i64> pil;
typedef pair<i64, i64> pll;
typedef tuple<int, int, int> tpii;
constexpr int N = 1e6 + 10, M = 1e3 + 10, INF = 0x3f3f3f3f, mod = 1e9 + 7, MOD = 998244353;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MAXT = 1e6 + 10;
int n, m, x, y, k, c, d, t;
int w[N], nums[N];

A - ICPC Rank

这道题是一道签到题，出这道题是想让同学们了解一下icpc赛制的简单规则。是很简单的直接模拟就行

void solve() {
    i64 x, y, p1, p2;
    read(x, y, p1, p2);
    if (x > y) {
        cout << "A" << endl;
    } else if (x < y) {
        cout << "B" << endl;
    } else {
        if (p1 == p2) {
            cout << "C" << endl;
        } else if (p1 > p2) {
            cout << "B" << endl;
        } else {
            cout << "A" << endl;
        }
    }
}

B - 小苯的序列极值

这道题是比较思维的一道题，如果直接暴力求的话就会超时，因为我们知道他把∣ai−aj∣|a_i - a_j|都加到了里面，即对于每一个aia_i都对应一个aja_j,要求最大值的话，就是让aia_i最大（最小）aja_j最小（最大）就行了

void solve() {
    read(n);
    for (int i = 0; i < n; i++)
        read(w[i]);
    int mx = *max_element(w, w + n), mn = *min_element(w, w + n);
    cout << mx - mn << endl;
}

C - Domino

C题多米诺骨牌，是一个指针题，维护一个往右边最大的右指针r就行，遍历的时候只要超出了这个界限，就停止。答案就是这个

void solve() {
    read(n);
    for (int i = 1; i <= n; i++)
        read(w[i]);
    int r = 1;
    for (int i = 1; i <= n; i++) {
        if (r >= i) {
            r = max(r, i + w[i] - 1);
        } else {
            cout << i - 1 << endl;
            return;
        }
    }
    cout << n << endl;
}

D - 全排列问题

出过两次了，我就不多说了用dfs

void solve() {
    read(n);
    vector<int> arr(n);
    iota(arr.begin(), arr.end(), 1);
    do {
        for (int x: arr)
            printf("%5d", x);
        printf("\n");
    } while (next_permutation(arr.begin(), arr.end()));
}

E - 查找

我上次出的题里面有这种题的类型，如果没有写出来的话。。。那我上次出题的意义在哪。 这道题是一个经典的二分查找类问题。没写出来的学学二分查找

int Binary(vector<int>& arr, int target,int L,int R) {
	int res = -1;
	while (L <= R) {
		int mid = L + ((R - L) >> 1);
		if (arr[mid] >= target) {
			res = mid;
			R = mid - 1;
		}
		else if (arr[mid] < target) {
			L = mid + 1;
		}
	}
	if (arr[res] == target) return res + 1;
	res = -1;
	return res;
}
void solve()
{
	int n, m;
	cin >> n >> m;
	vector<int> arr(n);
	vector<int> arr1(m);
	int* count = new int[m] {0};
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> arr1[i];

		count[i] = Binary(arr, arr1[i], 0, arr.size() - 1);
	}
	for (int i = 0; i < m; i++) {
		cout << count[i] << " ";
	}
}
void solve() {
    read(n, m);
    vector<int> arr(n);
    for (int& x: arr)
        read(x);
    while (m --) {
        read(x);
        int idx = lower_bound(arr.begin(), arr.end(), x) - arr.begin();
        if (arr[idx] == x)
            cout << idx + 1 << ' ';
        else
            cout << -1 << ' ';
    }
}

F - 小红有无穷无尽的字符串

这道题思维上难度不打，最主要的是如何将ll, rr分离出来

tpii calc(int x) {
    int res = x / 3;
    int ret = x % 3;
    return tpii{res + (ret >= 1), res + (ret >= 2), res};
}

void solve() {
    int l, r;
    read(l, r);
    // abc
    auto [a, b, c] = calc(l - 1);
    auto [d, e, f] = calc(r);
    cout << d - a << ' ' << e - b << ' ' << f - c << endl;
}
商业转载请联系站长获得授权，非商业转载请注明本文出处及文章链接，您可以自由地在任何媒体以任何形式复制和分发作品，也可以修改和创作，但是分发衍生作品时必须采用相同的许可协议。本文采用 CC BY-NC-SA 4.0 - 非商业性使用 - 相同方式共享 4.0 国际 进行许可。

Comments

Notes, questions, and follow-ups are welcome here.

Comments are temporarily unavailable because WALINE_SERVER_URL or PUBLIC_WALINE_SERVER_URL is not configured.