本期开始整体降到cspj难度 每个人都可以尝试全部的题目

题解

T1

根据题意可以发现,4个4个买比2个2个买更优,所以可以贪心的去买,每次买4个,直到剩下的不足4个,再买剩下的。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T;  // T=数据组数
    cin >> T;
    
    while (T--) {
        int x, y;  // x=2个装价格 y=4个装价格
        cin >> x >> y;
        cout << 2 * y + x << endl;
    }
    
    return 0;
}

T2

题目分析

我们需要分析函数 $f(l, r)$ 的表达式，并判断子区间 $[l, r]$ 是否为不稳定的。首先，展开 $f(l, r)$ 的求和式：

$ f(l, r) = \sum_{i=l}^{r-1} (a_i - a_{i+1}) = (a_l - a_{l+1}) + (a_{l+1} - a_{l+2}) + \dots + (a_{r-1} - a_r) $

观察发现，这是一个** telescoping series（望远镜求和）**，中间项会相互抵消，最终结果为：

$f(l, r) = a_l - a_r$

题目中定义，若 $f(l, r) \neq (a_r - a_l)$，则区间 $[l, r]$ 是不稳定的。代入 $f(l, r) = a_l - a_r$ 后，条件变为：

$ a_l - a_r \neq a_r - a_l \implies 2(a_l - a_r) \neq 0 \implies a_l \neq a_r $

因此，不稳定子区间的定义等价于：区间的左右端点元素不相等（$a_l \neq a_r$）。

问题转化

现在问题简化为：计算数组 $a$ 中满足 $a_l \neq a_r$ 的子区间 $[l, r]$ 的数量。

总子区间数

首先，数组中长度为 $n$ 的数组的总子区间数为：

$ \text{总区间数} = \sum_{r=1}^n \sum_{l=1}^r 1 = \frac{n(n+1)}{2} $

稳定子区间数（$a_l = a_r$）

我们需要先计算稳定子区间的数量，即满足 $a_l = a_r$ 的子区间数，然后用总区间数减去稳定区间数，得到不稳定区间数。

对于每个元素 $a_i$，统计以 $a_i$ 为右端点且 $a_l = a_i$ 的左端点 $l$ 的数量。假设在 $i$ 之前（包括 $i$），值为 $a_i$ 的元素共有 $c$ 个（包括 $a_i$ 本身），则以 $a_i$ 为右端点的稳定区间数为 $c$（因为每个左端点 $l$ 对应的 $a_l$ 都等于 $a_i$）。

例如，若数组中前 $i$ 个元素中有 $k$ 个等于 $a_i$，则以 $i$ 为右端点的稳定区间数为 $k$。

算法思路

1. 统计稳定区间数：

   • 使用哈希表（或数组，若值域较小）记录每个值最后出现的位置及出现次数。
   • 遍历数组，对于每个位置 $i$（从 1 到 $n$），统计当前值 $a_i$ 之前（包括 $i$）的出现次数 $c$，则稳定区间数增加 $c$。
   • 这里的 $c$ 表示以 $i$ 为右端点，且左端点 $l$ 满足 $a_l = a_i$ 的区间数（即 $l$ 可以是前 $c-1$ 个相同值的位置加上当前位置）。

2. 计算不稳定区间数： $\text{不稳定区间数} = \text{总区间数} - \text{稳定区间数}$

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

const int N = 101000;
int a[N], dp[N];

int main() {

    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }

        // 总区间数减去稳定区间数即为答案
        long long total = (long long)n * (n - 1) / 2;
        long long stable = 0;    // 稳定区间数

        // 统计每相同元素的数量
        unordered_map<int,int> mp;
        for (int i = 1; i <= n; ++i) {
            pos[a[i]]++;
        }

        // 计算稳定区间数   这里可以表示某个数,val表示这个数的个数
        for (auto &[key, val] : pos) {
            stable += (long long)val * (val - 1) / 2;
        }

        long long ans = total - stable;
        cout << ans << endl;
    }

    return 0;
}

T3

标准模版题 前序中序找后序

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

int n;
int pre[100010];
int ino[100010];

void dfs(int pl, int pr, int il, int ir) {
    if (pl > pr) {
        return;
    }
    int root = pl;  // 根节点一定是前序的第1个元素
    int ipos = il;  // 中序的根节点位置
    while (ino[ipos] != pre[root]) {
        ipos++;
    }

    int llen = ipos - il;  // 左子树长度
    int rlen = ir - ipos;  // 右子树长度

    dfs(pl + 1, pl + llen, il, ipos - 1);  // 左子树
    dfs(pl + llen + 1, pr, ipos + 1, ir);  // 右子树
    cout << pre[root] << ' ';  // 输出根节点

}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> pre[i];
    }
    for(int i = 1; i <= n; i++) {
        cin >> ino[i];
    }
    dfs(1, n, 1, n);

    return 0;
}

T4

一般来说这题就是一个简单的递归遍历每一种组合情况,复杂度$(2^n)$,然而这里的n最大为40,显然直接暴力求解不可取. 这里有一个比较巧妙的办法,我们将40个数分为两组,分别求出每种组合情况,每种最多就$2^{20}$. 我们将第一组排序,然后遍历第二组的$b_j$,在第一组中找到一个数$a_i$,使得$(a_i+b_j)$最大,显然这可以使用二分查找,时间复杂度$O(2^nlog(2^n))$

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

int n;
int mod;
long long a[50];
vector<long long> a1;
vector<long long> a2;


void dfs(int s, int e, long long sum, vector<long long>& c) {
    if (s > e) {
        c.push_back(sum);
        return;
    }
    dfs(s + 1, e, (sum + a[s]) % mod, c);
    dfs(s + 1, e, sum, c);
}

int main() {
    cin >> n >> mod;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    // 预留a1空间
    a1.reserve(1 << 21);
    a2.reserve(1 << 21);

    dfs(1, (n + 1) / 2, 0, a1);
    dfs((n + 1) / 2 + 1, n, 0, a2);

    sort(a1.begin(), a1.end());
    sort(a2.begin(), a2.end());

    long long ans = 0;
    int l = 0, r = a2.size() - 1;
    while (l < a1.size() && r >= 0) {

        if (a1[l] + a2[r] < mod) {
            l++;
        } else {
            r--;
        }
        ans = max(ans, (a1[l] + a2[r]) % mod);

    }
    cout << ans << endl;


    return 0;
}

T5

首先 按花色分组：对每种花色，统计其所有牌的数字。 可以使用unordered_map进行分组。 其次 滑动窗口优化：对于每个花色的数字列表，排序后使用滑动窗口找出长度为n的连续区间中包含最多已有数字(注意有重复数字)，从而确定最少需要补充的数字（即更换次数）。

#include<bits/stdc++.h>
using namespace std;
unordered_map<int, vector<int>> mp;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x,y;
        cin >> x >> y;
        mp[x].push_back(y);
    }

    int ans = 0;
    for (auto [x,y] : mp) {
        sort(y.begin(), y.end());
        queue<int> q;

        for (int i = 0; i < y.size(); i++) {
            if (i && y[i] == y[i-1]) {
                continue;
            }
            while (!q.empty() && y[i] - q.front() >= n ) {
                q.pop();
            }
            q.push(y[i]);
            ans = max(ans, (int)q.size());
        }

    }
    cout << n- ans << endl;
    return 0;
}

T6

请参考前缀中位数,此题和前缀中位数几乎一模一样,不再赘述

#include <bits/stdc++.h>
using namespace std;
long long a[100010];
int main() {
	long long n;
	cin >> n;
	for (long long i = 1; i <= n; i++) {
		cin >> a[i];
	}
	sort(a + 1, a + 1 + n);
	priority_queue<long long> maxp;
	priority_queue<long long, vector<long long>, greater<long long >> minp;
	for (long long i = 1; i <= n; i++) {
		if (i <= (n + 1) / 2) {
			maxp.push(a[i]);
		}
		else {
			minp.push(a[i]);
		}
	}
	long long m;
	cin >> m;
	string op;
	for (long long i = 1; i <= m; i++) {
		cin >> op;
		if (op == "add") {
			long long x;
			cin >> x;
			if (maxp.empty() || x <= maxp.top()) {
				maxp.push(x);
				while (maxp.size() > minp.size() + 1) {
					minp.push(maxp.top());
					maxp.pop();
				}
			} else {
				minp.push(x);
				while (minp.size() > maxp.size()) {
					maxp.push(minp.top());
					minp.pop();
				}
			}
		} else {
			cout << maxp.top() << endl;
		}
	}
	return 0;
}