2024.10.24 The 2021 ICPC Northwestern Russia Regional Contest

比赛链接

Solved：8/14

Penalty：909

Rank：23

前五道签到题 ABCHL。

K. Kaleidoscopic Route

题意

给一张带边权的图，求一条1到n的路径，使经过的边数最少的同时边的极差最大。

题解

求出最短路图，然后DAG上dp：f和g分别表示从1到这个点能经过的最大边权和最小边权。然后每转移一条边(x,y,z)就用g[x]-z和z-f[x]分别更新答案。输出方案就分别记一下f和g转移的前一个点就行。

经典说起来容易写起来难。。

D. Day Streak

题意

给一个数组 ${a_i}$，求 $t$ 使得 ${\lfloor\frac {a_i+t}m\rfloor}$的最长连续段最长。

题解

首先本质不同的 $t$ 只有 $m-a_i\bmod m$。

当 $t$ 增大的时候，有某些数从 $\lfloor\frac {a_i}m\rfloor$ 变为 $\lfloor\frac {a_i}m\rfloor+1$。

因此我们需要支持单点修改和维护最长连续段。

连续段可以用【珂朵莉树】来维护。即维护一个 set<pair<int,int>>，存储所有连续段。每次单点修改等于插入一个点和删除一个点，插入即合并左右两个连续段（如果有），删除即把它所在的连续段拆成两短。额外再维护一个set存所有连续段的长度。

int n,m,a[N];
map<int,vector<int>> mp;
map<int,int> val;
set<pii> s;
multiset<int> len;
void insert(int x){
    auto it=s.lower_bound(pii(x,x));
    int L=x,R=x;
    vector<pii> tmp;
    if(it!=s.end()&&it->first==x+1)R=it->second,tmp.push_back(*it);
    if(it!=s.begin()){
        --it;
        if(it->second==x-1)L=it->first,tmp.push_back(*it);
    }
    for(auto p:tmp)s.erase(p),len.erase(len.find(p.second-p.first+1));
    s.insert(pii(L,R)),len.insert(R-L+1);
}
void erase(int x){
    auto it=s.lower_bound(pii(x+1,-1));
    --it;
    int L=it->first,R=it->second;
    s.erase(it),len.erase(len.find(R-L+1));
    if(L<x)s.insert(pii(L,x-1)),len.insert(x-L);
    if(R>x)s.insert(pii(x+1,R)),len.insert(R-x);
}
void solve(){
    cin>>n>>m;
    mp.clear();
    val.clear();
    s.clear();
    len.clear();
    for(int i=1;i<=n;++i){
        cin>>a[i];
        if(a[i]%m)mp[m-a[i]%m].push_back(i);
        a[i]/=m;
        if(!val[a[i]])insert(a[i]);
        ++val[a[i]];
    }
    int ans=*len.rbegin(),anst=0;
    for(auto [x,e]:mp){
        for(int i:e){
            --val[a[i]];
            if(!val[a[i]])erase(a[i]);
            if(!val[a[i]+1])insert(a[i]+1);
            ++val[a[i]+1];
        }
        if(ans<*len.rbegin())ans=*len.rbegin(),anst=x;
    }
    cout<<ans<<' '<<anst<<'\n';
}

E. Extreme Problem

题意

给定函数在 $([-10,10]\cap \mathbb{Z})^2$ 上的性质：有/无极小值、有/无极大值，有/无平台，构造这个函数。

题解

玩数（值）分（析）玩的！

只有八种数据，直接手玩构造：

无重复极值，无平台：x+y

无重复极值，有平台：0

有重复极小值，无平台：令重复极小值为 (-1,0) 和 (1,0)，为了让两个都是极小再加一个极值点 (0,0)。对x的偏导数是 $x^{3-x$。凑整数，$x}4-2x^2+y2$。

有重复极大值，无平台：上面的取负号。

有重复极小值，有平台：令重复极小值为 (-2,0) 和 (2,0)，平台是 (0,0) 周围五个数。那么 x 方向需要有三个零点 -1，0，1，因此有因子 $x^3-x$。设函数表达式为 $(x^3-x)(x2+a)$，代入 $x=2$ 解得 $a=\frac {40}7$。注意两位数不能直接写到表达式里（逆天题意）。y 方向和 x 方向一样的表达式，加起来就行。

有重复极大值，有平台：上面的取负号。

有重复极大极小值，无平台：令重复极值为 (-2,0),(-1,0),(1,0),(2,0)，同上。结果是 $3x^5-25x3+60x+y^2$。

有重复极大极小值，有平台：令重复极值为 (-3,0),(-2,0),(2,0),(3,0)，同上。结果是 $(x^3-x)(239x4-4211x^2+18360)+(y3-y)(239y^4-4211y2+18360)$。注意这里 $239\times 10^7>2$ 会爆，所以直接近似一下，用 $x^4-18x2+75$，这样极值点偏了 0.1 左右，不过题意要求是离散的，所以差不多就行。

7 发罚时有一半都是被前缀表达式格式偷袭的。。。偷懒不写表达式转换器是这样的。