当前位置: 代码迷 >> 综合 >> 模拟 Codeforces620F Xors on Segments
  详细解决方案

模拟 Codeforces620F Xors on Segments

热度:49   发布时间:2023-12-14 03:27:12.0

传送门:点击打开链接

题意:n个数,m次查询。n<=5e4,m<=1e3

每次查询为一个区间l,r,要在n的数的[l,r]区间内选出2个数a,b(a<=b),然后计算a^(a+1)^(a+2)^...^b,输出最大的这个值

思路:标准答案好像是莫队算法+trie

不过好多人复杂度都是O(n(n+m))的,,Tourist也是。。

只要你敢写就能过。大概就是i枚举第一个数a,然后j枚举第二个数b,mx记录另一个数所在的数组范围在[i,j]的对应的函数的最大值。

遍历所有的查询,看i是否在某个查询的区间范围内,如果在,那么就更新答案。

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;const int MAX = 1e6 + 5;
const int MX = 5e4 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3ff3f3f;int z[MAX], A[MX], B[MX];
int L[MX], R[MX], ans[MX];int main() {int n, m; //FIN;z[0] = 0;for(int i = 1; i < MAX; i++) z[i] = z[i - 1] ^ i;while(~scanf("%d%d", &n, &m)) {memset(ans, 0, sizeof(ans));for(int i = 1; i <= n; i++) {scanf("%d", &A[i]);}for(int i = 1; i <= m; i++) {scanf("%d%d", &L[i], &R[i]);}for(int i = 1; i <= n; i++) {int mx = 0;for(int j = i; j <= n; j++) {if(A[i] <= A[j]) {mx = max(mx, z[A[j]] ^ z[A[i] - 1]);}else mx = max(mx, z[A[j] - 1] ^ z[A[i]]);B[j] = mx;}for(int k = 1; k <= m; k++) {if(L[k] <= i && i <= R[k]) {ans[k] = max(ans[k], B[R[k]]);}}}for(int i = 1; i <= m; i++) {printf("%d\n", ans[i]);}}return 0;
}


  相关解决方案