\(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;
}
- 2019 Northwestern Programming European Regional2019 northwestern programming european 2021 northwestern programming european programming acm-icpc american regional programming shenyang regional contest programming regional contest 2023 programming hangzhou regional contest programming regional yinchuan contest programming regional contest aefhkl programming stormwind shenyang regional intercollegiate programming regional contest