当前位置：首页 > news >正文

网站空间800m百度网页高级搜索

news 2025/7/10 17:42:58

网站空间800m,百度网页高级搜索,邢台seo,如何开发app应用原题链接：https://codeforces.com/contest/2116/problem/B 题目背景： 给定两个长度为 n 的数组 p、q，他们都是0 ~ n - 1的排列。构造一个数组 r ， 。思路： 直接暴力枚举的时间复杂度肯定是O(n^2)的，必然…

原题链接：https://codeforces.com/contest/2116/problem/B

题目背景：

给定两个长度为 n 的数组 p、q，他们都是0 ~ n - 1的排列。

构造一个数组 r ， $r_i = \max_{0 \leq j \leq i} \left(2^{p_j} + 2^{q_{i - j}}\right)$ 。

思路：

直接暴力枚举的时间复杂度肯定是O(n^2)的，必然超时。

通过观察可发现 $2^a + 2^b \leq 2^{\max(a, b) + 1}$ ，因为 $2^a + 2^b \leq 2*2^{\max(a, b)} = 2^{\max(a, b) + 1}$ ，

因此我们通过这个对比来对比两个数对(a,b)、(c,d)谁更大：

比较 $\max(a, b)$ 和 $\max(c, d)$ （谁的大）。
如果相等，再比较 $\min(a, b)$ 和 $\min(c, d)$ 。

说人话就是如果a > b， $2^a \geq 2 * 2 ^ b$ ，所以直接选择两个数组前缀中最大的元素即可。

具体实现就是，枚举 i 代表 $r_i$ ，pos1、pos2分别代表p、q中1 ~ i的最大值，每次判断如果p[pos1] == q[pos2] 输出更大的与之配对的即可，否则直接输出更大的即可。

时间复杂度：

O(n)。

ac代码：

#include <bits/stdc++.h>#define ioscc ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define me(a, x) memset(a, x, sizeof a)
#define all(a) a.begin(), a.end()
#define sz(a) ((int)(a).size())
#define pb(a) push_back(a)
using namespace std;typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<bool> vb;const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int MAX = (1ll << 31) - 1;
const int MIN = 1 << 31;
const int MOD = 998244353;
const int N = 1e5 + 10;template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cout << a[i] << ' ';return os;
}template <class T>
istream &operator>>(istream &in, vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cin >> a[i];return in;
}/* ----------------- 有乘就强转，前缀和开ll ----------------- */vi sqr(N);void init()
{sqr[0] = 1;for (int i = 1; i <= 1e5 + 1; ++i)sqr[i] = sqr[i - 1] * 2 % MOD;
}void solve()
{int n;cin >> n;vi p(n + 10), q(n + 10);cin >> p >> q;int pos1 = 0, pos2 = 0;for (int i = 0; i < n; ++i){if (p[i] > p[pos1]) // p前缀最大值pos1 = i;if (q[i] > q[pos2]) // q前缀最大值pos2 = i;if (p[pos1] == q[pos2])cout << (sqr[p[pos1]] + sqr[max(q[i - pos1], p[i - pos2])]) % MOD << ' ';else if (p[pos1] > q[pos2])cout << (sqr[p[pos1]] + sqr[q[i - pos1]]) % MOD << ' ';elsecout << (sqr[q[pos2]] + sqr[p[i - pos2]]) % MOD << ' ';}cout << endl;
}int main()
{ioscc;init();int T;cin >> T;while (T--)solve();return 0;
}

查看全文

http://www.khdw.cn/news/24594.html