树状数组,dp + 矩阵乘法
# A. 空
暴力就不多说了。
分两种情况讨论。
- 线段 不包含,且 在 右边,线段异或值为 ,开括号得 ,这里 是定值,如果我们想让整体最大,那么 最小,树状数组维护即可。
- 线段 包含线段 ,那么异或值为 ,要使异或值最大,那么 最大,同样使用树状数组维护即可。
时间复杂度
我这里为了方便,第一种情况维护的 的最大值,这样写一个结构体就行了。
#include <bits/stdc++.h> | |
#define pb push_back | |
using namespace std; | |
namespace IO{ | |
inline int read(){ | |
int x = 0, f = 1; | |
char ch = getchar(); | |
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();} | |
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); | |
return x * f; | |
} | |
template <typename T> inline void write(T x){ | |
if(x < 0) putchar('-'), x = -x; | |
if(x > 9) write(x / 10); | |
putchar(x % 10 + '0'); | |
} | |
} | |
using namespace IO; | |
const int N = 4e5 + 10; | |
int n, ans; | |
struct node{ | |
int l, r; | |
inline bool operator < (const node &b) const{ | |
return l != b.l ? l < b.l : r < b.r; | |
} | |
}p[N]; | |
int b[N], tot; | |
inline void init(){ | |
for(int i = 1; i <= n; ++i){ | |
p[i] = (node){read(), read()}; | |
b[++tot] = p[i].l, b[++tot] = p[i].r; | |
} | |
sort(b + 1, b + 1 + tot); | |
tot = unique(b + 1, b + 1 + tot) - b - 1; | |
sort(p + 1, p + 1 + n); | |
for(int i = 1; i <= n; ++i){ | |
p[i].l = lower_bound(b + 1, b + 1 + tot, p[i].l) - b; | |
p[i].r = lower_bound(b + 1, b + 1 + tot, p[i].r) - b; | |
} | |
} | |
struct BIT{ | |
int c[N]; | |
BIT() {memset(c, -0x3f, sizeof(c));} | |
inline void add(int x, int y){ | |
for(; x; x -= x & (-x)) c[x] = max(c[x], y); | |
} | |
inline int qry(int x){ | |
int res = -1e9; | |
for(; x <= tot; x += x & (-x)) res = max(res, c[x]); | |
return res; | |
} | |
}c1, c2; | |
signed main(){ | |
#ifndef ONLINE_JUDGE | |
freopen("test.in", "r", stdin); | |
freopen("test.out", "w", stdout); | |
#endif | |
n = read(), init(); | |
for(int i = 1; i <= n; ++i){ | |
ans = max(ans, b[p[i].l] + b[p[i].r] + c1.qry(p[i].l)); | |
ans = max(ans, c2.qry(p[i].l) - (b[p[i].r] - b[p[i].l])); | |
c1.add(p[i].r, -b[p[i].l] - b[p[i].r]); | |
c2.add(p[i].r, b[p[i].r] - b[p[i].l]); | |
} | |
write(ans), puts(""); | |
return 0; | |
} |
# B. 早苗
套路的设 表示到了第 天,连续 天刮不同的风的方案数。
转移方程:
这个比较好理解吧。
然后就能拿到 的好成绩了。
其实 到这里使用矩阵乘法优化也很显然了,随便构造个矩阵快速幂一下即可。
#include <bits/stdc++.h> | |
#define pb push_back | |
#define int long long | |
using namespace std; | |
namespace IO{ | |
inline int read(){ | |
int x = 0, f = 1; | |
char ch = getchar(); | |
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();} | |
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); | |
return x * f; | |
} | |
template <typename T> inline void write(T x){ | |
if(x < 0) putchar('-'), x = -x; | |
if(x > 9) write(x / 10); | |
putchar(x % 10 + '0'); | |
} | |
} | |
using namespace IO; | |
const int N = 1e5 + 10; | |
const int M = 110; | |
const int mod = 1e9 + 7; | |
int n, m; | |
inline int add(int x) {return x >= mod ? x - mod : x;} | |
struct Matrix{ | |
int num[M][M]; | |
Matrix() {memset(num, 0, sizeof(num));} | |
Matrix operator * (const Matrix &b) const{ | |
Matrix r; | |
for(int i = 1; i < m; ++i) | |
for(int j = 1; j < m; ++j) | |
for(int k = 1; k < m; ++k) | |
r.num[i][j] = add(r.num[i][j] + num[i][k] * b.num[k][j] % mod); | |
return r; | |
} | |
Matrix operator ^ (int p) const{ | |
Matrix r, a; | |
memcpy(a.num, num, sizeof(num)); | |
for(int i = 0; i <= m + 2; ++i) r.num[i][i] = 1ll; | |
for(; p; a = a * a, p >>= 1ll) | |
if(p & 1) r = r * a; | |
return r; | |
} | |
}f, A; | |
signed main(){ | |
#ifndef ONLINE_JUDGE | |
freopen("test.in", "r", stdin); | |
freopen("test.out", "w", stdout); | |
#endif | |
n = read(), m = read(); | |
for(int i = 1; i < m; ++i) A.num[i][i + 1] = m - i; | |
for(int i = 1; i < m; ++i) | |
for(int j = 1; j <= i; ++j) A.num[i][j]++; | |
f.num[1][1] = m; | |
f = f * (A ^ (n - 1)); | |
int ans = 0; | |
for(int i = 1; i < m; ++i) ans = add(ans + f.num[1][i]); | |
write(ans), puts(""); | |
return 0; | |
} |
# C. 棋盘
完全不会,咕咕。