最近的一些题改完之后一直想写一些题解，但是由于我改题太慢了一直没赶上写，正好今天老师今天晚上给我们留出了一个晚上改题，于是就把一些近期的题目写一下。
联赛模拟测试17 简单的区间
其实这道题在之前是有一道类似的题的，联考day1的幂次序列，但是因为那次写学长将的hash表加启发式合并的解法给我调自闭了，就没有改完，这次就算是还账了吧。
观察题目的式子我们可以发现，我们要的答案为所有序列除去其中最大值之后其余数字之和，于是我们可以考虑计算出每一个数字作为最大值的时候它所在的序列对答案的贡献一共有多少，可以把这个区间分为三部分，最大值左边，最大值右面以及最大值，我们需要做的就是从左面或者右面出发，从另一面去查找和这一面的和可以组成k的倍数(即模k意义下和为0)就行了,为了保证时间复杂度不为玄学(经过亲身实践会跑的比暴力还慢),我们需要保存大的一边的前缀和,从小的一边出发进行查找,于是我们可以使用hash表和启发式合并来进行求解,但是我还是没能调出来。于是我们可以对该做法进行魔改，因为我们似乎只需要区间之内的权值之和模k为一个数的区间个数，于是想到使用主席树来进行求解，但是又经过亲测发现，毒瘤出题人卡了主席树的常数，如果写的丑的话和暴力一个分(有可能还没暴力分高),于是我们又想到可以对区间模k的值开数个vector，每次在里面二分查找，就可以得出答案了（同是(O(nlogn)),主席树什么时候才能站起来(QAQ)），注意从右面找左面的区间个数的时候要求区间右对齐，直接找是不行了，需要我们简单推一下式子。
主席树写法(30分到60分不等,取决于你的常数)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
const int N = 1e6 + 10;
typedef long long ll;
struct node {
ll mx;
int id;
bool operator < (const node &a)const {
return a.mx > mx;
}
} st[N][25];
int n, k;
ll a[N], sum[N], ans;
int st_query(int l, int r) {
node res = (node){0, 0};
int d = log2(r - l + 1);
if(res < st[l][d])
res = st[l][d];
if(res < st[r - (1 << d) + 1][d])
res = st[r - (1 << d) + 1][d];
return res.id;
}
struct Tree {
int ls, rs, siz;
} tree[N];
int top, rt[N];
void build(int &t, int l, int r) {
t = ++top;
if(l == r) return;
int mid = (l + r) >> 1;
build(tree[t].ls, l, mid);
build(tree[t].rs, mid + 1, r);
}
int clone(int t) {
tree[++top] = tree[t];
return top;
}
void change(int &t, int l, int r, int pos) {
t = clone(t);
tree[t].siz++;
if(l == r) return;
int mid = (l + r) >> 1;
if(pos <= mid) change(tree[t].ls, l, mid, pos);
else change(tree[t].rs, mid + 1, r, pos);
}
int query(int t, int l, int r, int pos) {
if(l == r) return tree[t].siz;
int mid = (l + r) >> 1;
if(pos <= mid) return query(tree[t].ls, l, mid, pos);
else return query(tree[t].rs, mid + 1, r, pos);
}
void Solve(int l, int r) {
if(l > r) return;
if(l == r) {
return;
}
int mid = st_query(l, r);
int lenl = mid - l, lenr = r - mid;
if(lenl > lenr) {
Solve(mid + 1, r);
Solve(l, mid - 1);
for(int i = mid; i <= r; ++i) {
int now = (sum[i] - sum[mid] + k) % k;
now = (sum[mid - 1] + now + k) % k + 1;
int pos = query(rt[mid - 1], 1, k, now);
if(l >= 2)
pos -= query(rt[l - 2], 1, k, now);
ans += pos;
if(i == mid && sum[mid - 1] % k == now - 1)
ans--;
}
}
else {
Solve(l, mid - 1);
Solve(mid + 1, r);
for(int i = l; i <= mid; ++i) {
int now = (sum[mid - 1] - sum[i - 1] + k) % k;
if((mid - 1 - i + 1) > 0 && now == 0) ans++;
now = (sum[mid] - now + k) % k + 1;
int pos = query(rt[r], 1, k, now);
pos -= query(rt[mid], 1, k, now);
ans += pos;
}
}
}
int main() {
freopen("interval.in", "r", stdin);
freopen("interval.out", "w", stdout);
scanf("%d%d", &n, &k);
build(rt[0], 1, k);
change(rt[0], 1, k, 1);
for(int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
sum[i] = sum[i - 1] + a[i];
rt[i] = rt[i - 1];
change(rt[i], 1, k, sum[i] % k + 1);
st[i][0] = (node){a[i], i};
}
for(int j = 1; j <= 18; ++j)
for(int i = 1; i <= n; ++i) {
if(st[i][j] < st[i][j - 1])
st[i][j] = st[i][j - 1];
if(st[i][j] < st[i + (1 << (j - 1))][j - 1])
st[i][j] = st[i + (1 << (j - 1))][j - 1];
}
Solve(1, n);
printf("%lld
", ans);
return 0;
}
vector二分写法(时间上可以碾压主席树(当然内存也是))
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iostream>
const int N = 1e6 + 10;
#define rint register int
const int L = 1 << 20;
char buffer[L],*S,*T;
#define gc (S == T && (T = (S = buffer) + fread(buffer,1,L,stdin),S == T) ? EOF : *S++)
#define read() ({int s = 0,f = 1;char ch = gc;for(;!isdigit(ch);ch = gc)if(ch == '-')f = -1;for(;isdigit(ch);ch = gc)s = s * 10 + ch - '0';s * f;})
struct node {
int mx;
int id;
bool operator < (const node &a)const {
return a.mx > mx;
}
} st[N][25];
std::vector<int> ve[N];
int n, k;
int a[N], sum[N], ans, lg[N];
int st_query(rint l, rint r) {
node res = (node){0, 0};
rint d = lg[r - l + 1];
if(res < st[l][d])
res = st[l][d];
if(res < st[r - (1 << d) + 1][d])
res = st[r - (1 << d) + 1][d];
return res.id;
}
int query(rint l, rint r, rint val) {
int pos = std::upper_bound(ve[val].begin(), ve[val].end(), r) - ve[val].begin() - 1;
pos = pos - (std::lower_bound(ve[val].begin(), ve[val].end(), l) - ve[val].begin());
return pos + 1;
}
void Solve(rint l, rint r) {
if(l > r) return;
if(l == r) {
return;
}
rint mid = st_query(l, r);
rint lenl = mid - l, lenr = r - mid;
if(lenl > lenr) {
Solve(mid + 1, r);
Solve(l, mid - 1);
for(rint i = mid; i <= r; ++i) {
rint now = (sum[i] - sum[mid] + k) % k;
now = (sum[mid - 1] + now + k) % k + 1;
rint pos = query(l - 1, mid - 1, now);
ans += pos;
if(i == mid && sum[mid - 1] % k == now - 1)
ans--;
}
}
else {
Solve(l, mid - 1);
Solve(mid + 1, r);
for(rint i = l; i <= mid; ++i) {
rint now = (sum[mid - 1] - sum[i - 1] + k) % k;
if((mid - 1 - i + 1) > 0 && now == 0) ans++;
now = (sum[mid] - now + k) % k + 1;
rint pos = query(mid + 1, r, now);
ans += pos;
}
}
}
int main() {
freopen("interval.in", "r", stdin);
freopen("interval.out", "w", stdout);
for(int i = 2; i <= 1e6; ++i) {
lg[i] = lg[i / 2] + 1;
}
ve[1].push_back(0);
n = read(); k = read();
for(rint i = 1; i <= n; ++i) {
a[i] = read();
st[i][0] = (node){a[i], i};
if(a[i] >= k) a[i] %= k;
sum[i] = sum[i - 1] + a[i];
if(sum[i] >= k) sum[i] -= k;
ve[sum[i] + 1].push_back(i);
}
for(rint j = 1; j <= 18; ++j)
for(rint i = 1; i <= n; ++i) {
if(st[i][j] < st[i][j - 1])
st[i][j] = st[i][j - 1];
if(st[i][j] < st[i + (1 << (j - 1))][j - 1])
st[i][j] = st[i + (1 << (j - 1))][j - 1];
}
Solve(1, n);
printf("%d
", ans);
return 0;
}
晚间测试8 physics
读完题面就感觉法拉第和伏特的棺材板压不住了
感觉这道题的思路妙就妙在时光倒流，也算是以后做题的一个积累，如果我们把加号变成减号的操作变为减号变回加号的操作，容易发现此时的答案是单调不增的，而且如果加上一个新的电荷之后如果答案得到更新此时的答案一定是包含刚刚变化的点的。所以我们可以维护一下矩阵里面每一个加号在它的左面和右面距离它最近的减号距离它的距离，那么如果这个点在新的答案矩阵里面，它对答案贡献的长度最多只有(l[i]+r[i]-1)，我们就可以在修改完一个点之后扫一下点所在的列，依此取一下最长的连续的一段的左右边界，同时检查当左右边界距离不小于新答案的最大长度，和答案比较就可以做到(O(n))更新，如果二分答案的话可以做到(O(nqlogn))但是前面已经说过了,答案是单调不降的,于是我们在现在的答案的基础上累加检验就可以了,检验不过就直接break掉。(其实下面我的代码复杂度是假的,我没有用单调队列进行优化,而是如果检验不行直接跳回去,但是因为数据水可以过)
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
const int N = 1e6 + 10;
char ch[1100][1100];
int dp[1100][1100];
#define min(a, b) (a > b ? b : a)
#define Min(a, b, c) (min(a, min(b, c)))
#define max(a, b) (a > b ? a : b)
struct Que {
int x, y;
} a[N];
int ans[N], now, up[1100][1100], down[1100][1100];
int q[N], head, tail;
int main() {
freopen("physics.in", "r", stdin);
freopen("physics.out", "w", stdout);
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
scanf(" %c", &ch[i][j]);
}
}
for(int i = 1; i <= k; ++i) {
scanf("%d%d", &a[i].x, &a[i].y);
ch[a[i].x][a[i].y] = '-';
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(ch[i][j] == '+')
dp[i][j] = Min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
if(now < dp[i][j]) now = dp[i][j];
}
}
ans[k] = now;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(ch[i][j] == '-') {
down[i][j] = 0;
}
else down[i][j] = down[i][j - 1] + 1;
}
for(int j = m; j >= 1; --j) {
if(ch[i][j] == '-') {
up[i][j] = 0;
}
else up[i][j] = up[i][j + 1] + 1;
}
}
for(int t = k; t > 1; --t) {
ch[a[t].x][a[t].y] = '+';
for(int j = 1; j <= m; ++j) {
if(ch[a[t].x][j] == '-') {
down[a[t].x][j] = 0;
}
else down[a[t].x][j] = down[a[t].x][j - 1] + 1;
}
for(int j = m; j >= 1; --j) {
if(ch[a[t].x][j] == '-') {
up[a[t].x][j] = 0;
}
else up[a[t].x][j] = up[a[t].x][j + 1] + 1;
}
tail = 0;
int pre = now;
while(true) {
tail = 0;
int mn = 0x3f3f3f3f, mx = 0;
pre = now;
for(int j = 1; j <= n; ++j) {
if(up[j][a[t].y] + down[j][a[t].y] - 1 < now + 1) {
tail = 0;
mn = 0x3f3f3f3f;
mx = 0;
}
else {
mn = min(mn, a[t].y + up[j][a[t].y] - 1);
mx = max(mx, a[t].y - down[j][a[t].y] + 1);
if(mn - mx + 1 < now + 1) {
j -= tail;
tail = 0;
mn = 0x3f3f3f3f;
mx = 0;
}
else tail++;
}
if(tail >= now + 1) {
now++;
break;
}
}
if(now == pre) break;
pre = now;
}
ans[t - 1] = now;
}
for(int i = 1; i <= k; ++i) {
printf("%d
", ans[i]);
}
return 0;
}
开几个坑过几天慢慢填
联考day6 选数 模板
晚间测试10 大佬(kat)
联考day5 客星璀璨之夜 割海成路之日
晚间测试9 主仆见证了 Hobo 的离别
晚间测试8 chinese