前言
emmm，我着急吃饭赶了一篇题解，如果哪写的有问题欢迎大家指出，代码应该都是没问题的，如果有问题可以给我发私信或者评论，b站牛客竞赛应该也会有视频讲解）
题解
A.tb的区间问题
枚举所有长度为k的区间的和取max就好了，滑动窗口的写法
#include<bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
void solve() {
int n, k;
std::cin >> n >> k;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
}
i64 ans = -1, sum = 0;
for (int i = 1; i <= n; i++) {
sum += a[i];
if (i >= n - k) {
sum -= a[i - (n - k)];
ans = std::max(ans, sum);
}
// std::cout << sum << '\n';
}
std::cout << ans << '\n';
}
signed main() {
std::ios::sync_with_stdio(0);
std::cout.tie(0);
std::cin.tie(0);
i64 t = 1;
// std::cin >> t;
while (t--) {
solve();
}
}
B.tb的字符串问题
在我看来就是括号匹配问题，有两种括号罢了，大家不会的可以先去网上学习一下括号匹配的写法，用栈来维护
#include<bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
void solve() {
int n;
std::cin >> n;
std::string s;
std::cin >> s;
s = ' ' + s;
std::stack<char> st;
for (int i = 1; i <= n; i++) {
st.push(s[i]);
if (st.size() > 1) {
char q1 = st.top();
st.pop();
char q2 = st.top();
st.pop();
if ((q1 == 'c' && q2 == 'f') || (q1 == 'b' && q2 == 't')) {
continue;
}
st.push(q2);
st.push(q1);
}
}
std::cout << st.size() << '\n';
}
signed main() {
std::ios::sync_with_stdio(0);
std::cout.tie(0);
std::cin.tie(0);
i64 t = 1;
// std::cin >> t;
while (t--) {
solve();
}
}
C.tb的路径问题
这个规律很好找的，大家可以手玩样例或者打表观察一下，肯定是要根据2来跳的
#include<bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
void solve() {
int n;
std::cin >> n;
if (n == 1) {
std::cout << 0;
return;
}
if (n == 2) {
std::cout << 2;
return;
}
if (n == 3) {
std::cout << 4;
return;
}
if (n & 1) {
std::cout << 6;
}
else {
std::cout << 4;
}
}
signed main() {
std::ios::sync_with_stdio(0);
std::cout.tie(0);
std::cin.tie(0);
i64 t = 1;
// std::cin >> t;
while (t--) {
solve();
}
}
D.tb的平方问题
范围内的完全平方数一共也没多少嘛，那我们直接枚举所有的就好了，其余部分我们考虑一个板子题，有长度为n的数组，问你区间和为k的有多少，这题更简单，没有负数，那对于每一个确定的区间右端点来说，每一个完全平方数对应的肯定只有一个区间左端点，最后用一个差分数组来维护就好了。
#include<bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
void solve() {
int n, q;
std::cin >> n >> q;
std::vector<int> a(n + 1), c(n + 2);
std::map<int, int> mp;
mp[0] = 0;
int sum = 0;
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
sum += a[i];
for (int j = 1; j * j <= sum; j++){
if (mp.count(sum - j * j)) {
c[mp[sum - j * j] + 1]++;
c[i + 1]--;
}
}
mp[sum] = i;
}
for (int i = 1; i <= n; i++) {
c[i] += c[i - 1];
// std::cout << c[i] << ' ';
}
// std::cout << '\n';
while (q--) {
int x;
std::cin >> x;
std::cout << c[x] << '\n';
}
}
signed main() {
std::ios::sync_with_stdio(0);
std::cout.tie(0);
std::cin.tie(0);
i64 t = 1;
// std::cin >> t;
while (t--) {
solve();
}
}
E.tb的数数问题
这个题的话就去找每个没有出现的数，他的倍数都是false的，其余的都是true，调和级数log的复杂度。
#include<bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
void solve() {
int n;
std::cin >> n;
std::vector<int> vis(1000005, 0), flag(1000005, 0), a(n + 1);
bool f = 0;
int mx = -1;
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
if (a[i] == 1) {
f = 1;
}
mx = std::max(mx, a[i]);
vis[a[i]] = 1;
}
if (!f) {
std::cout << 0;
return;
}
for (int i = 2; i <= mx; i++) {
if (!vis[i] && !flag[i]) {
for (int j = i * 2; j <= mx; j += i) {
vis[j] = 0;
flag[j] = 1;
}
}
}
int ans = 0;
for (int i = 1; i <= mx; i++) {
if (vis[i]) {
ans++;
}
}
std::cout << ans << '\n';
}
signed main() {
std::ios::sync_with_stdio(0);
std::cout.tie(0);
std::cin.tie(0);
i64 t = 1;
// std::cin >> t;
while (t--) {
solve();
}
}
F.tb的排列问题
这个感觉我写的可能有点麻烦了，我的想法是按b的顺序看a中没出现的数字可以出现在哪几个位置，然后默认给他填到当前位置往后最近的没有填过的-1的位置，把这些乘起来，实现起来我用了个树状数组
#include<bits/stdc++.h>
#define lowbit(x) x & (-x)
using i64 = long long;
using u64 = unsigned long long;
struct Fenwick {
int n;
std::vector<int> tr;
std::stack<std::pair<int,int>> sta;
void reset(int m) {
n = m;
tr.clear();
tr.resize(n + 1);
clear();
}
void modify(int u, int x) {
sta.push(std::make_pair(u, x));
for (int i = u + 1; i <= n; i += lowbit(i))
tr[i] += x;
}
int query(int u) {
int x = 0;
for (int i = u + 1; i >= 1; i -= lowbit(i))
x += tr[i];
return x;
}
int query(int l, int r) { // [l, r]
return query(r) - query(l - 1);
}
void pop() {
while(!sta.empty()) {
auto cur = sta.top();
int x = cur.first, v = cur.second;
for (int i = x + 1 ;i <= n; i += lowbit(i))
tr[i] -= v;
sta.pop();
break;
}
}
void clear() {
while(!sta.empty()) {
auto cur = sta.top();
int x = cur.first, v = cur.second;
for (int i = x + 1 ;i <= n; i += lowbit(i))
tr[i] -= v;
sta.pop();
}
}
}tr;
template<class T>
constexpr T power(T a, i64 b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
constexpr i64 mul(i64 a, i64 b, i64 p) {
i64 res = a * b - i64(1.L * a * b / p) * p;
res %= p;
if (res < 0) {
res += p;
}
return res;
}
template<int P>
struct MInt {
int x;
constexpr MInt() : x{} {}
constexpr MInt(i64 x) : x{norm(x % getMod())} {}
static int Mod;
constexpr static int getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(int Mod_) {
Mod = Mod_;
}
constexpr int norm(int x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr int val() const {
return x;
}
explicit constexpr operator int() const {
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) & {
x = 1LL * x * rhs.x % getMod();
return *this;
}
constexpr MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) & {
return *this *= rhs.inv();
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
i64 v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
};
template<>
int MInt<0>::Mod = 998244353;
template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();
constexpr int P = 998244353;
using Z = MInt<P>;
void solve() {
int n, w;
std::cin >> n >> w;
tr.reset(n + 1);
std::vector<int> a(n + 1), vis(n + 1, 0);
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
}
for (int i = n; i >= 1; i--) {
if (a[i] == -1) {
tr.modify(i, 1);
}
else {
vis[a[i]] = i;
}
}
std::vector<int> b(n + 1);
for (int i = 1; i <= n; i++) {
std::cin >> b[i];
}
bool flag = 1;
Z ans = 1;
for (int i = 1; i <= n; i++) {
if (!vis[b[i]]) {
int num = tr.query(1, std::min(n, i + w));
if (num) {
ans *= num;
tr.pop();
}
else {
tr.pop();
flag = 0;
// std::cout << 0 << '\n';
// return;
}
}
else {
if (vis[b[i]] > i + w) {
flag = 0;
}
}
}
if (!flag) {
std::cout << 0 << '\n';
}
else {
std::cout << ans << '\n';
}
}
signed main() {
std::ios::sync_with_stdio(0);
std::cout.tie(0);
std::cin.tie(0);
i64 t = 1;
std::cin >> t;
while (t--) {
solve();
}
}
京公网安备 11010502036488号