A

算法标签: 模拟

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	string s1, s2;
	cin >> s1 >> s2;

	if (s1 == "sick" && s2 == "fine") cout << 2 << "\n";
	else if (s1 == "fine" && s2 == "sick") cout << 3 << "\n";
	else if (s1 == "fine" && s2 == "fine") cout << 4 << "\n";
	else cout << 1 << "\n";

	return 0;
}

B

算法标签: 模拟

思路

每次找到$B$的位置, 以$B$为中心向两侧扩展, 然后删除该位置

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	string s;
	cin >> s;

	int res = 0;
	while (s.find('B') != -1) {
		int u = s.find('B');
		
		int n = s.size();
		for (int i = 1; i <= n; ++i) {
			if (u - i < 0 || u + i >= n) continue;
			if (s[u - i] == 'A' && s[u + i] == 'C') res++;
		}

		s[u] = ' ';
	}

	cout << res << "\n";

	return 0;
}

C

算法标签: 哈希映射, 哈希表

思路

注意计算哈希值的时候转化成$longlong$

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>
#include <utility>

using namespace std;

typedef long long LL;
const int N = 2e5 + 10, M = 5e5 + 10;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int n, m;
	cin >> n >> m;

	unordered_set<LL> s;
	int res = 0;

	while (m--) {
		int u, v;
		cin >> u >> v;

		if (u == v) {
			res++;
			continue;
		}

		LL hash1 = (LL)u * N + v;
		LL hash2 = (LL)v * N + u;
		if (!s.count(hash1) && !s.count(hash2)) {
			s.insert(hash1);
			s.insert(hash2);
		}
		else res++;
	}

	cout << res << "\n";

	return 0;
}

D

算法标签: 贪心, 模拟

思路

因为最后一定是一段$1$连接到一起, 因此设$1$的数量是$cnt$, 最后$1$的起始位置$l$, 那么终点坐标就是$l+cnt-1$, 设初始时每个$1$的位置是$a_i$, 那么目标就是最小化

$$ans=\min \left\{\sum _{i=1}^n|a_i-(l+i-1)|\right\}$$

整理后得到

$$ans=\min \left\{\sum _{i=1}^n|a_i-i-(l-1)|\right\}$$

设$b_i=a_i-i$, $x=l-1$, 那么原式变为

$$ans=\min \left\{\sum _{i=1}^n|b_i-x|\right\}$$

$x$取中位数就是最小值

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

typedef long long LL;
const int N = 5e5 + 10;

int n;
string s;
vector<int> nums;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> s;
	int k = 1;
	for (int i = 0; i < n; ++i) {
		if (s[i] == '1') {
			nums.push_back(i - k);
			k++;
		}
	}
	
	sort(nums.begin(), nums.end());
	int x = nums[nums.size() / 2];
	
	LL res = 0;
	for (int val : nums) res += abs(val - x);
	
	cout << res << "\n";
	return 0;
}

E

算法标签: 倍数, 数论, $gcd$, 调和级数

思路

首先看$A_i$的最大值范围不超过$10^6$, 也就是答案$gcd\le 10^6$, 因此可以枚举$gcd$, 题目要求$k$个元素中必须包含$A_i$, 设$d=gcd$, 必须满足$d|A_i$, 并且在剩余元素中至少有$k-1$个$d$的倍数

设$cnt[x]$表示$A$中$x$出现的次数, $mul[x]$表示$A$中$x$倍数出现的次数, 那么有$mul[x]=cnt[x]+cnt[2x]+cnt[3x]+...+cnt[nx]$, 调和级数枚举每个$x$的倍数, 时间复杂度$O(n\ln n)$, 可以放缩为$O(n\log n)$

算法过程

• 首先枚举$d$
• 然后检查$mul[d]\ge k$, 如果满足条件, 更新$d$的倍数的$A_i$的答案

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1.2E6 + 10, M = 1e6 + 10;

int n, k;
int w[N], cnt[N], mul[N];
int res[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		cin >> w[i];
		cnt[w[i]]++;
	}

	// 调和级数枚举所有数倍数出现的次数
	for (int i = 1; i < M; ++i) {
		for (int j = i; j < M; j += i) {
			mul[i] += cnt[j];
		}
	}

	for (int d = 1; d < M; ++d) {
		if (mul[d] < k) continue;
		for (int x = d; x < N; x += d) {
			res[x] = max(res[x], d);
		}
	}

	for (int i = 1; i <= n; ++i) cout << res[w[i]] << "\n";
	return 0;
}

F

算法标签: 离线, 树状数组, 离散化, 动态规划, $LIS$

思路

注意到, 查询数量和序列长度都是$2\times 10^5$, $O(n^2)$的直接做法会超时
$LIS$问题有一个树状数组优化做法, 设$f[j]$表示以$j$结尾的最长上升子序列的长度, 更新方式f[a[j]]=max⁡k<a[i]{f[k]}+1f[a[j]] = \max _{k < a[i]} \left \{ f[k] \right \} + 1f[a[j]]=maxk<a[i]​{f[k]}+1, 取$max$的过程可以使用树状数组优化

树状数组求最长上升子序列问题

树状数组求$LIS$

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 1010;

int n, w[N];
vector<int> nums;
int tr[N];

int get(int val) {
	return lower_bound(nums.begin(), nums.end(), val) - nums.begin() + 1;
}

void disc() {
	for (int i = 1; i <= n; ++i) nums.push_back(w[i]);
	sort(nums.begin(), nums.end());

	for (int i = 1; i <= n; ++i) w[i] = get(w[i]);
}

int lowbit(int val) {
	return val & -val;
}

void update(int u, int val) {
	for (int i = u; i < N; i += lowbit(i)) tr[i] = max(tr[i], val);
}

int get_max(int u) {
	int res = 0;
	for (int i = u; i; i -= lowbit(i)) res = max(res, tr[i]);
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> w[i];

	disc();

	int res = 1;
	for (int i = 1; i <= n; ++i) {
		int curr = get_max(w[i] - 1) + 1;
		res = max(res, curr);
		update(w[i], curr);
	}

	cout << res << "\n";

	return 0;
}

因为当前问题是离线问题, 因此可以将查询顺序打乱, 考虑将查询按照$R$从小到大排序依次处理, 每次处理完$a[i]$后计算$R=i$的所有询问, 时间复杂度$O((N+Q)logM)$, $M$是树状数组大小

树状数组做法

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 2e5 + 10;

int n, q;
int w[N];
struct Query {
    int x, id;
};
vector<Query> qs[N];
int tr[N << 1], ans[N];

// 离散化
void disc() {
    vector<int> nums;
    for (int i = 1; i <= n; ++i) nums.push_back(w[i]);

    for (int i = 1; i <= n; ++i) {
        for (auto [x, id] : qs[i]) {
            nums.push_back(x);
        }
    }

    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    for (int i = 1; i <= n; ++i) {
        w[i] = lower_bound(nums.begin(), nums.end(), w[i]) - nums.begin() + 1;
    }

    for (int i = 1; i <= n; ++i) {
        for (Query &q : qs[i]) {
            q.x = lower_bound(nums.begin(), nums.end(), q.x) - nums.begin() + 1;
        }
    }
}

int lowbit(int val) {
    return val & -val;
}

void update(int u, int val) {
    for (int i = u; i < N * 2; i += lowbit(i)) {
        tr[i] = max(tr[i], val);
    }
}

int get_max(int u) {
    int res = 0;
    for (int i = u; i > 0; i -= lowbit(i)) {
        res = max(res, tr[i]);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> w[i];

    for (int i = 1; i <= q; ++i) {
        int r, x;
        cin >> r >> x;
        // 记录最大值范围和查询id
        qs[r].push_back({x, i});
    }

    disc();

    for (int i = 1; i <= n; ++i) {
        int curr = get_max(w[i] - 1) + 1;
        update(w[i], curr);
        for (Query q : qs[i]) {
            ans[q.id] = get_max(q.x);
        }
    }

    for (int i = 1; i <= q; ++i) cout << ans[i] << "\n";
    return 0;
}

动态规划 + 二分做法

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 2e5 + 10;

int n, q, w[N];
struct Query {
	int r, x, id;
	int ans;
} qs[N];

bool cmp_r(Query &q1, Query &q2) {
	return q1.r < q2.r;
}

bool cmp_id(Query &q1, Query &q2) {
	return q1.id < q2.id;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> q;
	for (int i = 1; i <= n; ++i) cin >> w[i];

	for (int i = 1; i <= q; ++i) {
		int r, x;
		cin >> r >> x;
		qs[i] = {r, x, i};
	}

	sort(qs + 1, qs + q + 1, cmp_r);

	vector<int> f;
	f.push_back(0);

	int qi = 1;
	for (int i = 1; i <= n; ++i) {
		// 第一个大于等于w[i]的位置
		auto it = lower_bound(f.begin(), f.end(), w[i]);
		if (it == f.end()) f.push_back(w[i]);
		else *it = w[i];

		while (qi <= q && qs[qi].r == i) {
			qs[qi].ans = upper_bound(f.begin(), f.end(), qs[qi].x) - f.begin() - 1;
			qi++;
		}
	}

	sort(qs + 1, qs + q + 1, cmp_id);
	for (int i = 1; i <= q; ++i) cout << qs[i].ans << "\n";

	return 0;
}

---

G

先鸽, 因为是黑题, 有时间补上