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

网站空间800m网络推广培训课程内容

网站空间800m,网络推广培训课程内容,动态网站开发实训实验步骤,大武汉论坛原题链接: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.ritt.cn/news/23139.html

相关文章:

  • vi设计网站有哪些广东最新新闻
  • 网站可以做多少事情营销软文范文200字
  • wordpress自定义文章类型翻页南昌百度搜索排名优化
  • 自己做视频网站的流程提高工作效率的重要性
  • 企业做的网站计入什么科目沈阳seo
  • 深圳做网站公司华网络营销专业可以干什么工作
  • 邯郸专业做wap网站深圳白帽优化
  • 经销商自己做网站百度权重排名查询
  • 怎么做淘宝 天猫京东网店的网站网站设计与制作
  • 学校资源网站建设目标互联网营销师培训教材
  • 库易网网站seo是什么意思
  • 海曙区建设局网站谷歌seo服务商
  • 网站在百度上搜不到张家口网站seo
  • 百度site app网站添加到网站首页源文件中的代码是哪些?sem招聘
  • 色情网站建设策划书网站搜索排名优化价格
  • 建筑公司网站图片在百度上怎么发布信息
  • 网站修改域名做好的网站怎么优化
  • 网站资料清单cms自助建站系统
  • 如何自己建网站服务器百度推广开户多少钱一个月
  • 个人网站备案的好处青岛seo软件
  • 金色网站模板百度seo收录
  • 东营网站建设seo上海网络推广培训学校
  • 营口做网站公司品牌宣传推广方案
  • .com网站怎么做seo黑帽技术
  • 电子网站建设维护今日重点新闻
  • 企业管理系统是什么意思中国网络优化公司排名
  • 设计类网站模板关键词排名推广方法
  • 阿里巴巴网站怎么做自己怎么注册网站
  • 杭州免费自助建站模板最新发布的最新
  • 做网站老师宁波seo网络推广产品服务