xyq0220

分类

未归档(101) 题解(3)

/ 注册

全部文章（共104篇）

Codeforces 1054D Changing Array 贪心+异或和

题意给一个长度为\(n\)的位数为\(k\)的整数数列\(a\)，一次操作可将任意\(a_i\)取反，问经过任意次操作后最多有多少个区间异或和不为\(0\) 分析求出前缀异或和，区间异或和为\(0\)的区间数转化为求有多少对前缀异或和相等，然后用总区间数减一下，对一个\(a_i\)...

codeforces 贪心异或

2019-05-17

0 548

Codeforces 1054D Changing Array 贪心+异或和

题意给一个长度为\(n\)的位数为\(k\)的整数数列\(a\)，一次操作可将任意\(a_i\)取反，问经过任意次操作后最多有多少个区间异或和不为\(0\) 分析求出前缀异或和，区间异或和为\(0\)的区间数转化为求有多少对前缀异或和相等，然后用总区间数减一下，对一个\(a_i\)...

贪心异或

2019-05-17

0 537

Codeforces 1167 F Scalar Queries 计算贡献+树状数组

题意给一个数列\(a\),定义\(f(l,r)\)为\(b_1, b_2, \dots, b_{r - l + 1}\),\(b_i = a_{l - 1 + i}\),将\(b\)排序,\(f(l,r)\)=\(\sum\limits_{i = 1}^{r - l + 1}{b_i \cdot...

codeforces 计算贡献树状数组

2019-05-16

0 563

Codeforces 1167 F Scalar Queries 计算贡献+树状数组

题意给一个数列\(a\),定义\(f(l,r)\)为\(b_1, b_2, \dots, b_{r - l + 1}\),\(b_i = a_{l - 1 + i}\),将\(b\)排序,\(f(l,r)\)=\(\sum\limits_{i = 1}^{r - l + 1}{b_i \cdot...

计算贡献树状数组

2019-05-16

0 428

Codeforces 1167 E Range Deleting 双指针+思维

题意给一个数列\(a\),定义\(f(l,r)\)为删除\(a\)中所有满足\(l<=a_i<=r\)的数后的数列,问有多少对\((l,r)\),使\(f(l,r)\)是一个非递减的数列分析若\(f(l,r)\)合法，则\(f(l,r+1),f(l,r+2),\...

codeforces 双指针

2019-05-16

0 446

Codeforces 1167 E Range Deleting 双指针+思维

题意给一个数列\(a\),定义\(f(l,r)\)为删除\(a\)中所有满足\(l<=a_i<=r\)的数后的数列,问有多少对\((l,r)\),使\(f(l,r)\)是一个非递减的数列分析若\(f(l,r)\)合法，则\(f(l,r+1),f(l,r+2),\...

codeforces 双指针

2019-05-16

0 474

Comet OJ - Contest #3 D 可爱的菜菜子线段树+线性基

题意给你一个长度为 \(n\) 的整数序列 \(a_1, a_2, \ldots, a_n\)，你需要实现以下两种操作，每个操作都可以用四个整数 \(opt\ l\ r\ v\) 来表示： \(opt=1\) 时，代表把一个区间 \([l, r]\) 内的所有数都 \(xor\) 上 \...

线段树线性基

2019-05-15

0 447

Comet OJ - Contest #3 D 可爱的菜菜子线段树+线性基

题意给你一个长度为 \(n\) 的整数序列 \(a_1, a_2, \ldots, a_n\)，你需要实现以下两种操作，每个操作都可以用四个整数 \(opt\ l\ r\ v\) 来表示： \(opt=1\) 时，代表把一个区间 \([l, r]\) 内的所有数都 \(xor\) 上 ...

线段树线性基

2019-05-15

0 398

BZOJ 2651 城市改建树形DP+模拟？

题意给一颗树，删除一条边再加一条边，使它仍为一颗树且任意两点间的距离的最大值最小。题目数据范围描述有问题，n为1或重建不能使任意两点距离最大值变小，可以输出任意答案。分析删除一条边后会使它变成两颗树，两棵树的直径的中点相连一定是使距离最小的红色的边为删除重建的边在树上dp...

BZOJ 树形DP

2019-05-15

0 497

BZOJ 2651 城市改建树形DP+模拟？

题意给一颗树，删除一条边再加一条边，使它仍为一颗树且任意两点间的距离的最大值最小。题目数据范围描述有问题，n为1或重建不能使任意两点距离最大值变小，可以输出任意答案。分析删除一条边后会使它变成两颗树，两棵树的直径的中点相连一定是使距离最小的红色的边为删除重建的边在树上dp...

BZOJ 树形DP

2019-05-15

0 568