Solved:4
Rank:143
A Equivalent Prefixes
题意:求一个最大的r满足在A,B两个数组中1,r里所有的子区间RMQ相等
题解:单调队列秒
#include <bits/stdc++.h>
using namespace std;
int n;
int q[100005];
int w[100005];
int que[100005]; int main() {
while(~scanf("%d", &n)) {
for(int i = 1; i <= n; i++) scanf("%d", &q[i]);
for(int i = 1; i <= n; i++) scanf("%d", &w[i]); int l = 1, r = 0;
int ans = n;
for(int i = 1; i <= n; i++) {
while(l <= r && q[i] < q[que[r]] && w[i] < w[que[r]]) r--;
if(l > r) que[++r] = i;
else if(q[i] > q[que[r]] && w[i] > w[que[r]]) {
que[++r] = i;
} else {
ans = i - 1;
break;
}
}
printf("%d\n", ans);
}
return 0;
}
A
H XOR (线性基)
题意:1e5个数 求所有xor和为0的子集 元素数量的和
题解:先求出线性基 社线性基里有x个数 对于线性基以外的数 算出每个数 对多少个集合做了贡献
因为 不管这个数和什么集合组合 都能被线性基表示出来 所以单个数的贡献是2^n-x-1
对于线性基里的数 除去这个数以外的n-1个数求一次线性基 如果这个数能被这个线性基表示出来 那么他的贡献也是2^n-x-1
因为如果一组数有多种线性基 那么每种的秩是一样的
然后在求线性基里的x个数时 可以先把n-x个数求一次线性基 加速运算
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7; ll a[100005];
ll b[100005];
ll c[70], d[70];
ll val[70];
ll val2[70]; ll pow_mod(ll x, ll y) {
ll res = 1;
while(y) {
if(y & 1) res = res * x % mod;
x = x * x % mod;
y >>= 1;
}
return res;
} bool insert(ll x) {
for(int i = 60; i >= 0; i--) {
if(x & (1LL << i)) {
if(!val[i]) {
val[i] = x;
return true;
}
x ^= val[i];
}
}
return false;
} void inser(ll x) {
for(int i = 60; i >= 0; i--) {
if(x & (1LL << i)) {
if(!val2[i]) {
val2[i] = x;
return;
}
x ^= val2[i];
}
}
} bool query(ll x) {
for(int i = 60; i >= 0; i--) {
if(x & (1LL << i)) x ^= val2[i];
}
return !x;
} int main() {
int n;
while(~scanf("%d", &n)) {
ll ans = 0;
int cnt = 0, tot = 0, cnt2 = 0;
memset(val, 0, sizeof(val));
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for(int i = 1; i <= n; i++) {
if(insert(a[i])) c[++tot] = a[i];
else b[++cnt] = a[i];
}
if(tot != n) ans = 1LL * cnt * pow_mod(2LL, n - tot - 1) % mod; memset(val, 0, sizeof(val));
for(int i = 1; i <= cnt; i++) {
if(insert(b[i])) d[++cnt2] = b[i];
}
for(int i = 1; i <= tot; i++) {
memset(val2, 0, sizeof(val2));
for(int j = 1; j <= tot; j++) {
if(i == j) continue;
inser(c[j]);
}
for(int j = 1; j <= cnt2; j++) inser(d[j]);
if(query(c[i])) {
ans = (ans + pow_mod(2LL, n - tot - 1)) % mod;
}
}
printf("%lld\n", ans);
}
return 0;
}
H XOR
I Points Division (线段树维护DP)
题意:平面上1e5个点 分成AB两个集合 使得相对B集合中每个点的第四象限含边界的地方没有A集合的点
每个点分别在A,B集合中点的贡献不同 求所有点贡献的最大和
题解:把B集合点的控制区域并在一起 可以发现是一条沿着B集合边界上点的单调不减折线
题解说对这条折线dp dp_i表示以i为折线上点的最大值 那么它是由前面x比他小且y比他小的点转移来的
首先按x从小到大排序 然后对离散化后的纵坐标建线段树维护dp值 转移就只需要查询一下最大值就降为log了
然后比较难理解的是转移 首先单点更新i点的dp值后 我们考虑一下i之前更新的点j 如果yj>yi 那么i就相当于考虑以j作为最优点的B集合里
所以为了不损失对前面yj>yi的点贡献 我们在yi + 1到结尾区间加上bi 同理在0到yi-1区间加上ai
还有一个坑点就是当x相等时 先处理y大的点 因为这条折线上的点是B集合的 如果先更新y小的点 y大的点给y小的点贡献是在A集合的
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; int n, cnt;
struct node {
int x, y, a, b, ty;
}e[100005]; bool cmp1(node A, node B) {
if(A.x == B.x) return A.y > B.y;
return A.x < B.x;
}
bool cmp2(node A, node B) {
return A.y < B.y;
} ll zd[400005];
ll lz[400005];
void pushup(int rt) {
zd[rt] = max(zd[rt << 1], zd[rt << 1 | 1]);
}
void pushdown(int rt) {
if(lz[rt]) {
zd[rt << 1] += lz[rt];
zd[rt << 1 | 1] += lz[rt];
lz[rt << 1] += lz[rt];
lz[rt << 1 | 1] += lz[rt];
lz[rt] = 0;
}
} void build(int l, int r, int rt) {
lz[rt] = zd[rt] = 0;
if(l == r) return;
int mid = l + r >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
} void update(int k, ll v, int l, int r, int rt) {
if(l == r) {
zd[rt] = max(zd[rt], v);
return;
}
pushdown(rt);
int mid = l + r >> 1;
if(k <= mid) update(k, v, l, mid, rt << 1);
else update(k, v, mid + 1, r, rt << 1 | 1);
pushup(rt);
} ll query(int ql, int qr, int l, int r, int rt) {
if(ql <= l && qr >= r) return zd[rt]; pushdown(rt);
ll res = 0;
int mid = l + r >> 1;
if(ql <= mid) res = max(res, query(ql, qr, l, mid, rt << 1));
if(qr > mid) res = max(res, query(ql, qr, mid + 1, r, rt << 1 | 1));
return res;
} void segment_update(int ql, int qr, ll v, int l, int r, int rt) {
if(ql <= l && qr >= r) {
lz[rt] += v; zd[rt] += v;
return;
}
pushdown(rt);
int mid = l + r >> 1;
if(ql <= mid) segment_update(ql, qr, v, l, mid, rt << 1);
if(qr > mid) segment_update(ql, qr, v, mid + 1, r, rt << 1 | 1);
pushup(rt);
} int main() {
while(~scanf("%d", &n)) {
cnt = 1;
for(int i = 1; i <= n; i++) scanf("%d%d%d%d", &e[i].x, &e[i].y, &e[i].a, &e[i].b);
sort(e + 1, e + 1 + n, cmp2); e[0].y = 0;
for(int i = 1; i <= n; i++) {
if(e[i].y != e[i - 1].y) e[i].ty = ++cnt;
else e[i].ty = cnt;
}
cnt++;
sort(e + 1, e + 1 + n, cmp1);
build(1, cnt, 1);
for(int i = 1; i <= n; i++) {
update(e[i].ty, query(1, e[i].ty, 1, cnt, 1) + 1LL * e[i].b, 1, cnt, 1);
segment_update(1, e[i].ty - 1, 1LL * e[i].a, 1, cnt, 1);
segment_update(e[i].ty + 1, cnt, 1LL * e[i].b, 1, cnt, 1);
}
printf("%lld\n", zd[1]);
}
return 0;
}
I Points Division
J Fraction Comparision (签到)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; int main() {
ll x, a, y, b;
while(~scanf("%lld%lld%lld%lld", &x, &a, &y, &b)) {
ll t1 = x / a, t2 = y / b;
if(t1 > t2) puts(">");
else if(t1 < t2) puts("<");
else {
x %= a, y %= b;
if(x * b == y * a) puts("=");
else x * b < y * a ? puts("<") : puts(">");
}
}
return 0;
}
J Fraction Comparision