A 划分序列
题目大意 ： 把n个数分成k段，使得和最大的那一段和最小
-
如果这个些数都是非负数或都是非正数，二分答案然后贪心的扫一遍即可
-
可是这些数有正有负，贪心是不对的
-
所以对于枚举的答案，找到满足最大的和小于ans的分法中能分的最多段数和最小段数，如果k在范围内说明合法
-
找最大最小的段数就用Dp，树状数组优化一下就好了
Code
Show Code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e4 + 5;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar())
x = x * 10 + c - '0';
return x * f;
}
int n, k, a[N], m, t1[N], t2[N], s[N], b[N], l, r;
void Add1(int x, int w) {
for (; x; x -= x & -x) t1[x] = min(t1[x], w);
}
int Ask1(int x, int ans = 1e9) {
for (; x <= m; x += x & -x) ans = min(ans, t1[x]);
return ans;
}
void Add2(int x, int w) {
for (; x; x -= x & -x) t2[x] = max(t2[x], w);
}
int Ask2(int x, int ans = -1e9) {
for (; x <= m; x += x & -x) ans = max(ans, t2[x]);
return ans;
}
bool Judge(int mid) {
memset(t1 + 1, 0x3f, m * 4);
memset(t2 + 1, 0xbf, m * 4);
int f = 0, g = 0;
for (int i = 1; i <= n; ++i) {
int x = lower_bound(b + 1, b + m + 1, b[s[i]] - mid) - b;
Add1(s[i-1], f); Add2(s[i-1], g);
f = Ask1(x) + 1; g = Ask2(x) + 1;
}
return f <= k && k <= g;
}
int main() {
n = read(); k = read();
for (int i = 1; i <= n; ++i) {
a[i] = read(), b[i] = s[i] = s[i-1] + a[i];
a[i] < 0 ? l += a[i] : r += a[i];
}
sort(b + 1, b + n + 2);
m = unique(b + 1, b + n + 2) - b - 1;
for (int i = 0; i <= n; ++i)
s[i] = lower_bound(b + 1, b + m + 1, s[i]) - b;
while (l < r) {
int mid = 1ll * l + r >> 1;
if (Judge(mid)) r = mid;
else l = mid + 1;
}
printf("%d
", l);
return 0;
}
B Ring
题目大意 ： 问一段区间内的边能否组成环
- 双指针扫一遍，用LCT动态维护联通性，挺简单的
Code
Show Code
#include <cstdio>
#include <algorithm>
#define Get(x) (c[f[x]][1] == x)
#define Nroot(x) (c[f[x]][Get(x)] == x)
using namespace std;
const int N = 3e5 + 5;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar())
x = x * 10 + c - '0';
return x * f;
}
int n, m, q, x[N], y[N], R[N], f[N], c[N][2], t[N], stk[N], tp;
void Rotate(int x) {
int y = f[x], z = f[y], k = Get(x);
if (Nroot(y)) c[z][Get(y)] = x; f[x] = z;
c[y][k] = c[x][k^1]; f[c[x][k^1]] = y;
c[x][k^1] = y; f[y] = x;
}
void Pushdown(int x) {
if (!t[x]) return;
swap(c[x][0], c[x][1]); t[x] = 0;
t[c[x][0]] ^= 1; t[c[x][1]] ^= 1;
}
void Splay(int x) {
for (int y = x; y; y = Nroot(y) ? f[y] : 0) stk[++tp] = y;
while (tp) Pushdown(stk[tp--]);
while (Nroot(x)) {
int y = f[x];
if (Nroot(y)) Get(x) == Get(y) ? Rotate(y) : Rotate(x);
Rotate(x);
}
}
void Access(int x) {
for (int y = 0; x; y = x, x = f[x])
Splay(x), c[x][1] = y;
}
void Mroot(int x) {
Access(x); Splay(x); t[x] ^= 1;
}
int Froot(int x) {
Access(x); Splay(x);
while (c[x][0]) x = c[x][0];
return x;
}
void Link(int x, int y) {
Mroot(x); f[x] = y;
}
void Cut(int x, int y) {
Mroot(x); Access(y); Splay(y);
//if (c[y][0] == x && !c[x][1])
f[x] = c[y][0] = 0;
}
int main() {
n = read(); m = read(); q = read();
for (int i = 1; i <= m; ++i)
x[i] = read(), y[i] = read();
for (int l = 1, r = 1; l <= m; ++l) {
for (; r <= m && Froot(x[r]) != Froot(y[r]); ++r)
Link(x[r], y[r]);
Cut(x[l], y[l]); R[l] = r;
}
while (q--) {
int l = read(), r = read();
puts(R[l] <= r ? ">_<" : "QAQ");
}
return 0;
}
C Match
- 经过题解的化简就成了代码里的式子，但没看懂咋化的
Code
Show Code
#include <cstdio>
using namespace std;
const int M = 1e9 + 7;
int Pow(int a, int k, int ans = 1) {
for (; k; k >>= 1, a = 1ll * a * a % M)
if (k & 1) ans = 1ll * ans * a % M;
return ans;
}
int main() {
int n; scanf("%d", &n);
printf("%lld", (222222224ll * n % M * n % M + 311111113ll * n + 177777779 + 288888891ll * Pow(n, M - 2)) % M);
}```
</details>