个人网站购买,wordpress 更新媒体库,wordpress 个人站,进一步加强网站建设管理原题链接#xff1a;https://codeforces.com/contest/2116/problem/B
题目背景#xff1a; 给定两个长度为 n 的数组 p、q#xff0c;他们都是0 ~ n - 1的排列。 构造一个数组 r #xff0c; 。
思路#xff1a; 直接暴力枚举的时间复杂度肯定是O(n^2)的#xff0c;必然…原题链接https://codeforces.com/contest/2116/problem/B
题目背景 给定两个长度为 n 的数组 p、q他们都是0 ~ n - 1的排列。 构造一个数组 r 。
思路 直接暴力枚举的时间复杂度肯定是O(n^2)的必然超时。 通过观察可发现 因为
因此我们通过这个对比来对比两个数对(a,b)、(c,d)谁更大 比较 和 谁的大。 如果相等再比较 和 。 说人话就是如果a b所以直接选择两个数组前缀中最大的元素即可。 具体实现就是枚举 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 pairint, int pii;
typedef vectorvectorint vvi;
typedef vectorint vi;
typedef vectorbool 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 vectorT a) noexcept
{for (int i 0; i sz(a) - 10; i)std::cout a[i] ;return os;
}template class T
istream operator(istream in, vectorT 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;
}
