Mex

题目大意:给出一个序列\(a\),定义\(f(l,r)\)为集合{\(a_l, a_{l+1}, …, a_r\)}的sg值,求\(\sum_i \sum_{j(i\leq j)} f(i,j)\)的值。

问题的关键(突破口):假设对于一个固定的\(p\),我们求出了对于所有\(j\)的\(f(p,j)\),现在考虑\(p\)增加一,思考对于所有\(j\)的\(f(p+1,j)\)的值与\(f(p,j)\)有什么变化。

兔子与寿司

据说这题是原创题?以至于我找不到提交的地方。

这题很容易想到枚举第一只兔子的吃的最大的美味值x,然后显然把a小于等于x的篮子分给第一只兔子,现在考虑剩下的篮子。

我们可以用线段树维护,线段树的下标y是篮子的b值,存的值表示第二只兔子吃的最大美味小于等于y时,后面两只兔子最大的美味值的和最小是多少。

modseq

这题当时我记得旁边的人都刷刷地秒了,我这个逗比不会做。。。。

其实这个关系到鸽巢原理,当序列的长度大于\(p\)时,显然答案就是0嘛!我记得我以前看过!

忍不住贴个代码(事实上并没有多大意义)。

#include <cstdio>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std; const int MAXN = (int) 2e5 + 3; int n;
int a[MAXN]; struct s_node {
long long sum;
int mini, maxi;
int mark;
}; s_node t[1 << 19]; void update(int idx) {
int idxl = idx << 1;
int idxr = idxl | 1;
t[idx].sum = t[idxl].sum + t[idxr].sum;
t[idx].mini = min(t[idxl].mini, t[idxr].mini);
t[idx].maxi = max(t[idxl].maxi, t[idxr].maxi);
} void build(int idx, int L, int R, int sg[]) {
t[idx].mark = -1;
if (L == R) {
t[idx].mini = t[idx].maxi = sg[L];
t[idx].sum = sg[L];
return;
} int M = (L + R) >> 1; build(idx << 1, L, M, sg);
build(idx << 1 | 1, M + 1, R, sg); update(idx);
} int posi[MAXN]; void analyse() {
static int next[MAXN];
fill(next, next + 1 + n, -1);
for (int i = n - 1; i >= 0; i--) {
if (next[a[i]] == -1) posi[i] = -1;
else posi[i] = next[a[i]];
next[a[i]] = i;
}
static int sg[MAXN], cnt[MAXN];
fill(cnt, cnt + n + 1, 0); int num = 0;
for (int i = 0; i < n; i++) {
cnt[a[i]]++;
while (cnt[num]) num++;
sg[i] = num;
} build(1, 0, n - 1, sg);
} void setLazy(int idx, int L, int R, int x) {
t[idx].mini = t[idx].maxi = x;
t[idx].sum = (long long) x * (R - L + 1);
t[idx].mark = x;
} void modify(int idx, int L, int R, int l, int r, int x) {
if (t[idx].maxi <= x) return;
if (t[idx].mini >= x && l <= L && r >= R) {
setLazy(idx, L, R, x);
return;
}
int M = (L + R) >> 1; if (-1 != t[idx].mark) {
setLazy(idx << 1, L, M, t[idx].mark);
setLazy(idx << 1 | 1, M + 1, R, t[idx].mark);
t[idx].mark = -1;
} if (l <= M) modify(idx << 1, L, M, l, r, x);
if (r > M) modify(idx << 1 | 1, M + 1, R, l, r, x);
update(idx);
} int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif while (scanf("%d", &n) == 1) {
if (n == 0) break;
for (int i = 0; i < n; i++) {
scanf("%d", a + i);
a[i] = min(a[i], n);
}
analyse();
long long ans = t[1].sum;
for (int i = 0; i + 1 < n; i++) {
int p = a[i];
modify(1, 0, n - 1, i, i, 0);
if (posi[i] == -1) {
modify(1, 0, n - 1, i + 1, n - 1, p);
}
else {
if (i + 1 <= posi[i] - 1)
modify(1, 0, n - 1, i + 1, posi[i] - 1, p);
}
ans += t[1].sum;
} cout << ans << endl;
} return 0;
}
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int MAXN = (int) 1e5 + 3; struct s_blanket {
int a, b, c;
}; int n;
s_blanket x[MAXN]; int idx_value[MAXN]; bool cmp(const s_blanket &p, const s_blanket &q) {
return p.a < q.a;
} struct s_node {
int maxi, lazy;
int value;
}; s_node t[1 << 18]; void setLazy(int idx, int v, int L) {
t[idx].maxi = v;
t[idx].lazy = v;
t[idx].value = v + idx_value[L];
} void build(int idx, int L, int R) {
if (L == R) {
t[idx].value = idx_value[L];
return;
}
int M = (L + R) >> 1;
build(idx << 1, L, M);
build(idx << 1 | 1, M + 1, R);
t[idx].value = min(
t[idx << 1].value,
t[idx << 1 | 1].value);
} void dfs(int idx, int L, int R, int y, int v, bool ok) {
if (L > y) return;
if (t[idx].maxi >= v) return;
if (L == R) {
if (v > t[idx].maxi) {
t[idx].maxi = v;
t[idx].value = idx_value[L] + v;
}
return;
}
int M = (L + R) >> 1;
int idxl = idx << 1;
int idxr = idxl | 1;
if (t[idx].lazy) {
setLazy(idxl, t[idx].lazy, L);
setLazy(idxr, t[idx].lazy, M + 1);
t[idx].lazy = 0;
} if (ok && R <= y) {
setLazy(idx, v, L);
return;
} if (ok) {
dfs(idxl, L, M, y, v, ok);
dfs(idxr, M + 1, R, y, v, ok);
}
else {
if (t[idxl].maxi < v) {
dfs(idxl, L, M, y, v, false);
dfs(idxr, M + 1, R, y, v, true);
}
else {
dfs(idxr, M + 1, R, y, v, false);
}
} t[idx].maxi = min(t[idxl].maxi, t[idxr].maxi);
t[idx].value = min(t[idxl].value, t[idxr].value);
} void insert(s_blanket item) {
int posi = lower_bound(idx_value, idx_value + n, item.b) - idx_value;
dfs(1, 0, n - 1, posi - 1, item.c, false);
} int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif scanf("%d", &n);
for (int i = 0; i <= n; i++) {
if (i < n)
scanf("%d%d%d", &x[i].a, &x[i].b, &x[i].c);
idx_value[i] = x[i].b;
}
n++; sort(idx_value, idx_value + n);
sort(x, x + n, cmp); int ans = 0x3f3f3f3f;
build(1, 0, n - 1);
for (int i = n - 1; i >= 0; i--) {
ans = min(ans, x[i].a + t[1].value);
insert(x[i]);
}
printf("%d\n", ans); return 0;
}
#include <cstdio>

int main() {
int n, m;
static int a[100001];
while (scanf("%d%d", &n, &m) == 2) {
for (int i = 1; i <= n; i++) scanf("%d", a + i);
for (int i = 0; i < m; i++) {
int l, r, p;
scanf("%d%d%d", &l, &r, &p);
if (r - l + 1 > p) {
printf("0\n");
continue;
}
int ans = 0x3f3f3f3f;
for (int x = l; x <= r; x++) {
int sum = 0;
for (int y = x; y <= r; y++) {
sum = (sum + a[y]) % p;
if (sum < ans) ans = sum;
}
}
printf("%d\n", ans);
}
}
return 0;
}
05-02 12:27