今天考试我第三题想出来了然后斜挂了 因为想太麻烦了 就很难受 没时间去写其他题目了 只打了暴力
这道题真的很巧妙啊 数据范围明示要$n√n$啊
首先可以发现最劣的答案就是$40000$ 也就是每个分成一段 所以每段里面的颜色种类$k$不会超过$sqrt(n)$种
所以我们考虑对于每一个位置枚举$k$的大小 寻找出最长的包含$k$种颜色的区间$[j, i]$ 这时候$dp[i] = min(dp[j - 1] + k * k)$
现在的问题转化为如何求出最长的包含$k$种颜色的区间 我们记$pos[j]$为上述区间的左端点 $cnt[j]$为上述区间当前的颜色种数
记录$nex[i], pre[i]$两个数组分别表示与$i$号位置颜色相同的元素上一次出现‘下一次出现的位置 我么用他们来维护$pos$
每新进入一个未知判断$pre[i]$与$pos[j]$的关系 若$pre[i] < pos[j]$就说明当前区间该颜色第一次出现 那么$cnt[j] ++$
若$cnt[j] > j$就需要将$pos$后移 若$nex[pos[j]] < i$说明即使向后移了当前颜色在该区间中仍然存在 继续后移知道$cnt$真正减少即可
代码
#include <bits/stdc++.h> #define oo 1e9 using namespace std; const int N = 40000 + 5; int m, pos[N], cnt[N], nex[N], n, a[N], pre[N], las[N], f[N]; int main( ) { freopen("cleanup.in", "r", stdin); freopen("cleanup.out", "w", stdout); scanf("%d%d", & n, & m); for(int i = 1;i <= n;i ++) scanf("%d", & a[i]); int t = sqrt(n); for(int i = 1;i <= n;i ++) { pre[i] = las[a[i]]; nex[las[a[i]]] = i; las[a[i]] = i; f[i] = oo; nex[i] = n + 1; } for(int i = 1;i <= t;i ++) pos[i] = 1; for(int i = 1;i <= n;i ++) for(int j = 1;j <= t;j ++) { if(pre[i] < pos[j]) cnt[j] ++; if(cnt[j] > j) { cnt[j] --; while(nex[pos[j]] < i) pos[j] ++; pos[j] ++; } f[i] = min(f[i], f[pos[j] - 1] + j * j); } printf("%d ", f[n]); }
这道题看似很难其实是最简单的..首先这个而分形很明显所以考虑枚举$L$
因为需要覆盖所有的点 所以考虑上下左右四个方向的最远点
又考虑到我们只有三个正方形 所以一个正方形需要贴着两个极限边
所以枚举每个正方形到底是贴着哪个个极限边即可
代码
#include <bits/stdc++.h> #define oo 1e9 using namespace std; const int N = 2 * 1e4 + 5; int n, x[N], y[N], tail[5], q[5][N], len; bool in[N]; bool dfs(int dep) { if(dep == 3) { for(int i = 1;i <= n;i ++) if(! in[i]) return false; return true; } int xx1 = oo, xx2 = -oo, yy1 = oo, yy2 = -oo; for(int i = 1;i <= n;i ++) if(! in[i]) xx1 = min(xx1, x[i]), xx2 = max(xx2, x[i]), yy1 = min(yy1, y[i]), yy2 = max(yy2, y[i]); tail[dep] = 0; for(int i = 1;i <= n;i ++) if(x[i] - xx1 <= len && y[i] - yy1 <= len && ! in[i]) in[i] = true, q[dep][++ tail[dep]] = i; if(dfs(dep + 1)) return true; for(int i = 1;i <= tail[dep];i ++) in[q[dep][i]] = false; tail[dep] = 0; for(int i = 1;i <= n;i ++) if(xx2 - x[i] <= len && y[i] - yy1 <= len && ! in[i]) in[i] = true, q[dep][++ tail[dep]] = i; if(dfs(dep + 1)) return true; for(int i = 1;i <= tail[dep];i ++) in[q[dep][i]] = false; tail[dep] = 0; for(int i = 1;i <= n;i ++) if(xx2 - x[i] <= len && yy2 - y[i] <= len && ! in[i]) in[i] = true, q[dep][++ tail[dep]] = i; if(dfs(dep + 1)) return true; for(int i = 1;i <= tail[dep];i ++) in[q[dep][i]] = false; tail[dep] = 0; for(int i = 1;i <= n;i ++) if(x[i] - xx1 <= len && yy2 - y[i] <= len && ! in[i]) in[i] = true, q[dep][++ tail[dep]] = i; if(dfs(dep + 1)) return true; for(int i = 1;i <= tail[dep];i ++) in[q[dep][i]] = false; return false; } int main( ) { freopen("cover.in", "r", stdin); freopen("cover.out", "w", stdout); scanf("%d", & n); for(int i = 1;i <= n;i ++) scanf("%d%d", & x[i], & y[i]); int l = 0, r = oo, ans = oo; while(l <= r) { len = l + r >> 1; for(int i = 1;i <= n;i ++) in[i] = false; if(dfs(0)) ans = len, r = len - 1; else l = len + 1; } printf("%d ", ans); }
这道题我明显想麻烦了！！！！！现在想想真是蠢啊 离正解只有一步之遥了
首先对于每个询问的区间我们将它看作一段一段的边单独考虑贡献 题目给的是点 所以这个时候我们需要每次询问将$R--$
那么对于右端点在$i$的边 他的贡献即为$v[i] * (i - l + 1) * (r - i + 1)$ 总贡献即为$∑v[i] * (i - l + 1) * (r - i + 1)$将式子化简得到
$-∑v[i] * i ^ {2} + (l + r) ∑v[i] * i + ∑v[i] * (-l * r - l + r + 1)$
所以只需要维护$v[i] * i^{2},v[i] * i,v[i]$的区间和即可
代码
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 5; int n, m; ll sum1[N], sum2[N], tag[4 * N]; struct node { ll f, g, h; node(ll f = 0, ll g = 0, ll h = 0): f(f), g(g), h(h) {} }tr[4 * N]; ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } node update(node a, node b) { node c; c.f = a.f + b.f; c.g = a.g + b.g; c.h = a.h + b.h; return c; } void push_down(int o, ll l, ll r) { ll mid = l + r >> 1; if(tag[o]) { tag[o << 1] += tag[o], tag[o << 1 | 1] += tag[o]; tr[o << 1].f += (sum2[mid] - sum2[l - 1]) * tag[o]; tr[o << 1].g += (sum1[mid] - sum1[l - 1]) * tag[o]; tr[o << 1].h += 1ll * (mid - l + 1) * tag[o]; tr[o << 1 | 1].f += (sum2[r] - sum2[mid]) * tag[o]; tr[o << 1 | 1].g += (sum1[r] - sum1[mid]) * tag[o]; tr[o << 1 | 1].h += 1ll * (r - mid) * tag[o]; tag[o] = 0; } } void modify(int o, ll l, ll r, ll L, ll R, ll del) { if(l >= L && r <= R) { tr[o].f += (sum2[r] - sum2[l - 1]) * 1ll * del; tr[o].g += (sum1[r] - sum1[l - 1]) * 1ll * del; tr[o].h += 1ll * (r - l + 1) * del; tag[o] += 1ll * del; return ; } push_down(o, l, r); ll mid = l + r >> 1; if(L <= mid) modify(o << 1, l, mid, L, R, del); if(mid < R) modify(o << 1 | 1, mid + 1, r, L, R, del); tr[o] = update(tr[o << 1], tr[o << 1 | 1]); } void Init( ) { scanf("%d%d",& n,& m); for(int i = 1;i <= n;i ++) sum2[i] = sum2[i - 1] + 1ll * i * i, sum1[i] = sum1[i - 1] + 1ll * i; } node query(int o, ll l, ll r, ll L, ll R) { if(l >= L && r <= R) return tr[o]; push_down(o, l, r); ll mid = l + r >> 1; node ans = node(0, 0, 0); if(L <= mid) ans = update(ans, query(o << 1, l, mid, L, R)); if(mid < R) ans = update(ans, query(o << 1 | 1, mid + 1, r, L, R)); return ans; } int main( ) { freopen("roadxw.in", "r", stdin); freopen("roadxw.out", "w", stdout); Init( ); while(m --) { char opt[10]; ll L, R; ll x; scanf("%s", opt); R --; if(opt[0] == 'C') { scanf("%lld%lld%lld", & L, & R, & x); modify(1, 1, n - 1, L, R - 1, x); } else { scanf("%lld%lld", & L, & R); ll dwn = (R - L + 1) * (R - L) / 2; R --; node ans = query(1, 1, n - 1, L, R); ll a = ans.h * (-L + R + 1 - L * R); a -= ans.f; a += ans.g * (L + R); ll g = gcd(a, dwn); printf("%lld/%lld ", a / g, dwn / g); } } }