首页 > 代码库 > Codeforces 620F Xors on Segments(暴力+DP)
Codeforces 620F Xors on Segments(暴力+DP)
题目链接 Xors on Segments
预处理出x[i] = 1 ^ 2 ^ 3 ^ …… ^ i;
(话说这题O(N^2居然能过))
先对询问离线。
然后dp[i]表示以a[i]为开头的所有连续序列中最大答案。
然后依次处理到a[j]的时候如果以j为右端点的询问的左端点小于等于i则更新。
复杂度O(N^2)
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define rep(i, a, b) for (int i(a); i <= (b); ++i) 6 7 int x[1000010], a[50010], l[50010], r[50010], ans[5010]; 8 vector < pair <int, int> > v[50010]; 9 int n, q; 10 11 int main(){ 12 13 rep(i, 1, 1000001) x[i] = x[i - 1] ^ i; 14 scanf("%d%d", &n, &q); 15 rep(i, 1, n) scanf("%d", a + i); 16 rep(i, 1, q){ 17 scanf("%d%d", l + i, r + i); 18 v[r[i]].push_back({l[i], i}); 19 } 20 21 rep(i, 1, n){ 22 int dp = 0; 23 rep(j, i, n){ 24 dp = max(dp, x[a[i]] ^ x[a[j]] ^ min(a[i], a[j])); 25 for (auto u : v[j]){ 26 if (u.first <= i) ans[u.second] = max(ans[u.second], dp); 27 } 28 } 29 } 30 31 rep(i, 1, q) printf("%d\n", ans[i]); 32 return 0; 33 }
Codeforces 620F Xors on Segments(暴力+DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。