https://codeforces.com/contest/811/problems
最后一场会从A题开始做的cf啦，因为觉得A、B题简单题做多了也多大意义。
主要还是C题D题这些稍微高于自己的题比较重要，另一方面也是减负。
学一些姿势水平高一点的题
不用做完整的一次round了
A. Vladik and Courtesy
题意
签到题。
解法
模拟1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 3e5 + 10;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int a, b;
cin >> a >> b;
int cnt = 1;
for(int i = 1;;i++)
{
if(i % 2)
{
a -= cnt++;
if(a < 0)
{
cout << "Vladik" << endl;
break;
}
}
else
{
b -= cnt++;
if(b < 0)
{
cout << "Valera" << endl;
break;
}
}
}
return 0;
}
B. Vladik and Complicated Book
题意
一个区间$m$个数。$n$次query，每次query将一个区间内$[l, r]$内的数字进行排序，问第$x$个数是否发生变化$(n, m \leq 10000)$。每次query排序都是独立的。
解法
一遍扫计数有多少个数小于第$x$个数，判断一下就好了。
时间复杂度为$O(n^m)$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
using namespace std;
const int maxn = 1e4 + 10;
int p[maxn], q[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> p[i];
while(m--)
{
int l, r, x;
cin >> l >> r >> x;
int loc = 0;
for(int i = l; i <= r; i++)
if(p[i] < p[x])
loc++;
if(loc + l == x)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
C. Vladik and Memorable Trip
题意
给定一个数组，你需要选择一些区间满足以下几点要求：
- 如果区间内包含数$x$，则所有$x$都必须包含在这个区间内
- 即相同数要不被包含在同一个区间内，要不不在任何区间内
在所有满足要求的不同区间中求出区间内所有不同的数异或和的最大值
解法
一个线性dp
将原问题分解成若干子问题，$dp[i]$表示前i个数能组成的最大值
预处理每个数第一次出现的位置$beg[a[i]]$，和最后一个出现的位置$ter[a[i]]$
需要计算$a[i]$时，从后往前扫。
如果新的数不需要被纳入，$dp[i] = dp[i - 1]$
然后向前扫，不断构成一个新的区间。
如果当前数出现的最后的出现为止在$i$后面，则向前不能继续构成区间了，直接break。
然后用st记录区间里所有出现的数最先出现的位置
如果当前数就是st了就进行更新
$dp[i] = max(dp[i], dp[j - 1] + res)$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
using namespace std;
const int maxn = 1e4 + 10;
int a[maxn];
int beg[maxn], ter[maxn];
int dp[maxn];
bool vis[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
if(beg[a[i]] == 0)
beg[a[i]] = i;
ter[a[i]] = i;
}
for(int i = 1; i <= n; i++){
dp[i] = dp[i - 1];
memset(vis, 0, sizeof(vis));
int res = 0, st = i;
for(int j = i; j >= 1; j--)
{
if(!vis[a[j]]){
if(ter[a[j]] > i)
break;
st = min(st, beg[a[j]]);
res = res xor a[j];
vis[a[j]] = 1;
}
if(j == st)
dp[i] = max(dp[i], dp[j - 1] + res);
}
}
cout << dp[n] << endl;
return 0;
}