\(A. Average Rank\)
将每个人的排名看作是前面一个人的贡献，然后采用类似懒标记的形式优化复杂度。
int sum[N],point[N],cnt[N],pre[N],laz[N];
void solve(){
int n=read(),w=read();
laz[0]=w;
cnt[0]=n;
for(int i=0;i<w;i++){
int k=read();
for(int j=0;j<k;j++){
int x=read();
int &p=point[x];
sum[x]+=laz[p]-cnt[p+1]*(w-i)-pre[x];
laz[p]+=w-i;
--cnt[p];
++cnt[++p];
pre[x]=laz[p];
}
}
for(int i=1;i<=n;i++){
int p=point[i];
sum[i]+=laz[p]-pre[i];
double ans=sum[i]*1.0/w;
printf("%.10lf\n",ans);
}
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(D. Disposable Switches\)
所有边边权 \(*u\) 。考虑若最短路经过 \(k\) 条边，可用一次函数表达，这时候所有一次函数构成的图的下沿就是可能的一些路径，用 \(floyed\) 完成 \(dp\) 过程。
int n, m,dis[N][N];
vector<PII> vec[N];
bool res[N], vis[N][N];
bool cross(PII a, PII b, PII c) {
long double xa = c.second - a.second, ya = a.first - c.first,
xb = b.second - a.second, yb = a.first - b.first;
return xa * yb < xb * ya;
}
void Floyd() {
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= n; ++j) {
dis[i][j] = INF;
}
}
dis[0][1] = 0;
for (int i = 0; i <= n - 2; ++i) {
for (int j = 1; j <= n; ++j) {
for (auto k : vec[j]) {
dis[i + 1][k.first] = min(dis[i + 1][k.first], dis[i][j] + k.second);
}
}
}
}
void dfs(int now, int to) {
res[to] = vis[now][to] = true;
if (!now) return;
for (auto i : vec[to]) {
if (dis[now - 1][i.first] + i.second == dis[now][to]) {
if (vis[now - 1][i.first]) continue;
dfs(now - 1, i.first);
}
}
}
void solve() {
n=read(),m=read();
for(int i=1;i<=m;i++){
int u=read(),v=read(),c=read();
vec[u].emplace_back(make_pair(v, c));
vec[v].emplace_back(make_pair(u, c));
}
Floyd();
vector<PII> stk;
for (int i = n - 1; i >= 1; --i) {
PII p = make_pair(i, dis[i][n]);
while (stk.size() >= 2) {
if (cross(stk[stk.size() - 2], stk[stk.size() - 1], p)) stk.pop_back();
else break;
}
if (stk.size() == 1 && stk.back().second > p.second) stk.pop_back();
stk.emplace_back(p);
}
for (auto i : stk)
dfs(i.first, n);
vector<int> ans;
for(int i=1;i<=n;i++){
if (res[i]) continue;
ans.emplace_back(i);
}
cout << ans.size() << '\n';
for (auto i : ans) cout << i << ' ';
}
\(H. Height Profile\)
把分数化为\(a_i-g*i \le a_j-g*j\)，然后排序计算答案。
从小到大的排序后，我们只需要找到一个左右能成立的点（在已排除不合法的情况下必然存在答案），同时判断能否向两端延伸。
int h[N];
void solve(){
int n=read(),k=read(),maxx=0;
for(int i=0;i<=n;i++){
h[i]=read();
}
for(int i=1;i<=n;i++){
maxx=max(maxx,h[i]-h[i-1]);
}
for(int i=1;i<=k;i++){
double g;
cin>>g;
int x=round(g*10.0);
if(maxx<x){
cout<<"-1\n";
continue;
}else{
double ans=-1;
vector<PII>vec(n+1),tmp(n+1);
for(int ii=0;ii<=n;ii++){
vec[ii]=make_pair(h[ii]-ii*x,ii);
tmp[ii]=vec[ii];
}
sort(vec.begin(),vec.end());
int l=n,r;
for(auto [x,y]:vec){
r=y;
if(l<r){
double res=0;
if(l>0)res=max(res,(double)(tmp[r].first-tmp[l].first)/fabs(tmp[l].first-tmp[l-1].first));
if(r<n)res=max(res,(double)(tmp[r].first-tmp[l].first)/fabs(tmp[r+1].first-tmp[r].first));
if(res>1.0)res=1.0;
ans=max(ans,r-l+res);
}
l=min(l,r);
}
printf("%.12lf\n",ans);
}
}
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(J. Jackdaws And Crows\)
还没看懂，先贴个 \(jiangly\) 慢慢看。
#include <bits/stdc++.h>
struct Matrix {
int a00, a01, a10, a11;
};
Matrix operator*(const Matrix &lhs, const Matrix &rhs) {
Matrix res;
res.a00 = std::min(lhs.a00 + rhs.a00, lhs.a01 + rhs.a10);
res.a01 = std::min(lhs.a00 + rhs.a01, lhs.a01 + rhs.a11);
res.a10 = std::min(lhs.a10 + rhs.a00, lhs.a11 + rhs.a10);
res.a11 = std::min(lhs.a10 + rhs.a01, lhs.a11 + rhs.a11);
return res;
}
struct SegmentTree {
int n;
std::vector<Matrix> t;
SegmentTree(int n) : n(n), t(4 * n) {
build(1, 0, n);
}
void build(int p, int l, int r) {
t[p].a00 = t[p].a11 = r - l;
t[p].a01 = t[p].a10 = 1e9;
if (r - l == 1)
return;
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
}
void modify(int p, int l, int r, int x, int y) {
if (r - l == 1) {
if (y == 0) {
t[p].a10 = 0;
} else {
t[p].a01 = 0;
}
return;
}
int m = (l + r) / 2;
if (x < m) {
modify(2 * p, l, m, x, y);
} else {
modify(2 * p + 1, m, r, x, y);
}
t[p] = t[2 * p] * t[2 * p + 1];
}
void modify(int x, int y) {
modify(1, 0, n, x, y);
}
int get() {
return std::min({t[1].a00, t[1].a01, t[1].a10, t[1].a11});
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, c, r;
std::cin >> n >> c >> r;
int64_t ans = 1ll * n * r;
SegmentTree t(n);
std::vector<std::tuple<int, int, int>> events;
events.reserve(2 * n);
for (int i = 0; i < n; ++i) {
int x;
std::cin >> x;
events.emplace_back(std::max(0, 1 - x), i, 0);
events.emplace_back(std::max(0, 1 + x), i, 1);
}
std::sort(events.begin(), events.end());
for (auto [a, x, y] : events) {
t.modify(x, y);
ans = std::min(ans, 1ll * a * c + 1ll * t.get() * r);
}
std::cout << ans << "\n";
return 0;
}