网站开发的可行性,网络推广合作协议范本,最近三天的新闻大事摘抄,市场咨询公司排名一种比较无脑暴力点的方法#xff0c;时间复杂度是(nm)。 (注意的优先级比^高#xff0c;记得加括号(a[i]^a[j])x#xff09;
#include iostream
#include vector
#include bits/stdc.h // 包含一些 C 标准库中未包含的特定实现的函数的头文件
usi…
一种比较无脑暴力点的方法时间复杂度是(n²m)。 (注意的优先级比^高记得加括号(a[i]^a[j])x
#include iostream
#include vector
#include bits/stdc.h // 包含一些 C 标准库中未包含的特定实现的函数的头文件
using namespace std;int main() {int n, m, x;// 输入 n数组长度、m查询次数、x给定的异或值cin n m x;// 定义数组 a 存储 n 个整数int a[n 1];// 输入 n 个整数到数组 a 中for (int i 1; i n; i) {cin a[i];}// 定义动态规划数组 dp初始化为 INT_MAX记录a[i]第一次能异或为x的位置j。vectorint dp(n 1, INT_MAX);// 对于每对 i、j判断 a[i] 和 a[j] 是否异或等于给定的 x// 如果等于则更新 dp[i] 为 j表示 a[i] 和 a[j] 可以异或得到 xfor (int i 1; i n; i) {for (int j i 1; j n; j) {if ((a[i] ^ a[j]) x) {dp[i] j;break; // 找到第一个符合条件的 j 即可跳出内层循环}}}// 对于每次查询输入左右边界 l、r// 如果 l 不等于 r 并且 dp[l] 小于等于 r则输出 yes否则输出 nofor (int i 0; i m; i) {int l, r;cin l r;if (l ! r dp[l] r)cout yes endl;elsecout no endl;}return 0;
}但是显然这样是不能得满分的那么我们就要优化一下思路。 思路分析
定义数组 a 存储 n 个整数。定义一个 mapint, int用于记录数组元素和它们的位置信息。(注意map当某个键不存在时其值会被初始为0从标准输入流中读取 n 个整数到数组 a 中。定义动态规划数组 dp初始化为 0用于记录满足条件的[1,i]最远位置。遍历数组 a更新动态规划数组 dp 和 map。查询部分从标准输入流中读取左右边界 l 和 r判断是否存在满足条件的位置对输出相应的结果。
#includeiostream
#includebits/stdc.h
using namespace std;int main() {int n, m, x;// 输入数组长度 n、查询次数 m 和给定的异或值 xcin n m x;// 定义数组 a 存储 n 个整数int a[n 1];// 定义 map用于记录数组元素和它们的位置信息mapint, int map;// 输入 n 个整数到数组 a 中for(int i 1; i n; i) {cin a[i];}// 定义动态规划数组 dp初始化为 0用于记录满足条件的最远位置vectorint dp(n 1, 0);// 对数组 a 进行遍历for(int i 1; i n; i) {// 更新动态规划数组 dp// dp[i] 表示在位置 i 时可以得到的满足条件的最远位置// 比较当前位置和之前出现的值对应位置的较大值更新 dp[i]dp[i] max(dp[i - 1], map[a[i] ^ x]);// 更新 map记录当前元素的位置信息map[a[i]] i;}// 查询部分for(int i 0; i m; i) {int l, r;cin l r;// 如果左右边界不相等并且 dp[r] 大于等于左边界 l则输出 yes否则输出 noif(l ! r dp[r] l)cout yes endl;elsecout no endl;}return 0;
}时间复杂度是Onm)大大优化了。
