2021ICPC济南区域赛VP记录

和破壁人及 wky VP 了去年的济南区域赛。最后排第 8，虽然离前 3 还有不少距离，但至少发挥没有之前两次 ICPC 预选赛那么拉跨。这次签到题很少，并且 E 题连写带调弄了一个多小时，差点都以为要寄了。感觉有几道题目很有意思，故记录一下思路。

（前面有两队是打星参加的）

E

下文约定记号 $G_i=\{j\mid(i,j)\text{ is a magic link}\}$

观察到 M 的大小比较蹊跷，于是猜想有 $O(NM)$ 做法。首先不考虑题目所求，想一下如何在不删点的情况下计算总分数。

考虑如下的一个交叉产生的代价如何计算：

凑了一阵均摊复杂度之后，可以得到以下的搞法：

枚举 a
- 按从小到大的顺序枚举与 a 有边的点 c
  - 枚举所有位于 $(a,c)$ 之间的点 b
    - 快速计算 $(a,c)$ 与 $(b,>c)$ 交叉产生的代价

考虑如何快速计算 $(a,c)$ 与 $(b,>c)$ 交叉产生的代价。注意到 c 是不断增加的，那么对于每个 b，形如 $(b,>c)$ 的边必然是不断减少的。

于是就想到对于每个 b，将 $G_b$ 递增排序，然后维护一个指针 $ind_b$，表示 $G_b$ 中第一个 $>c$ 的值的下标。然后就可以实时维护当前符合要求的 d 之和，就可以算出 $(a,c)$ 与 $(b,d)$ 交叉产生的代价之和。

分析上述算法的复杂度：

前三重循环最多会跑 $O(NM)$ 次
对于同一个 a，每条边最多会删一次，所以维护 $ind_b$ 的复杂度也是 $O(NM)$。

假设我们已经知道了不删边的答案，考虑删两个点 x,y 后答案是啥。发现感觉起来就很容斥，显然有：

\[ans'=ans-ans_\text{包含 x}-ans_\text{包含 y}+ans_\text{包含 x 和 y}\]

中间两项是很好统计的，只需要在上述算法中把答案算到 a 头上就可以了。

最后一项不好直接算，我们分两种情况讨论：

x 和 y 在交叉边对应的 4 个点中，是相邻的

这个也好搞，只需要在上述算法中，把答案算到 a,b 头上即可。

x 和 y 在交叉边对应的 4 个点中，是不相邻的

这就意味着 x,y 在同一条边上，只需要在上述算法中，把答案算到 a,c 头上即可。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MXN = 2e3 + 5;
ll n, m;
vector<ll> g[MXN];
ll sum[MXN], ind[MXN], sz[MXN];
ll redu(ll x) {
    if (x > n) x -= n;
    if (x > n) x -= n;
    if (x > n) x -= n;
    if (x > n) x -= n;
    return x;
}
ll only[MXN], both[MXN][MXN];
ll edge[MXN][MXN];
int main() {
    /* freopen("test.in", "r", stdin); */
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        if (v < u) swap(u, v);
        g[u].push_back(v);
        g[v].push_back(u + n);
        g[u + n].push_back(v + n);
        g[v + n].push_back(u + n + n);
    }
    for (ll i = 1; i <= n * 2; i++) sort(g[i].begin(), g[i].end());

    ll ans = 0;
    for (ll i = 1; i <= n; i++) {
        for (ll j = i; j < i + n; j++) {
            ind[j] = sz[j] = sum[j] = 0;
            while (sz[j] < g[j].size() && g[j][sz[j]] < i + n) sum[j] += redu(g[j][sz[j]++]);
        }
        for (ll j : g[i]) {
            for (ll k = i + 1; k < j; k++) {
                while (ind[k] < sz[k] && g[k][ind[k]] <= j) sum[k] -= redu(g[k][ind[k]++]);
                ll delt = (i + redu(j)) * ((sz[k] - ind[k]) * redu(k) + sum[k]);
                ans += delt;
                only[i] += delt;
                both[i][k] += delt;
                edge[i][j] += delt;
            }
        }
    }
    ll res = -1e18;
    for (ll i = 1; i <= n; i++)
        for (ll j = i + 1; j <= n; j++) {
            res = max(res, ans / 4 - only[i] - only[j] + both[i][j] + both[j][i + n] + edge[i][j]);
            /* cerr<<i<<" "<<j<<" "<<res<<endl; */
        }
    cout << res << endl;
    return 0;
}

C

首先，下标的顺序是可以忽略的，最后只需要把答案乘以 $\prod cnt_i!$ 即可。

首先任意两个合法的过程中，一个人取的数集合必定都是一样的（下标可以不同）。

手玩了几个小时之后，发现一个合法取数数列的规律：

如果最大数出现偶数次，那么在数列中出现必定是成对出现。比如说 A 某一次偷袭，取了一个最大数，则 B 也必须要取一个最大数来应对 A 的偷袭。否则 A 的取数集合就变了。
如果最大数出现奇数次，那么必然在一开始的时候就被取走了一个。随后问题就被转化为出现偶数次的情况。

于是大胆猜想：

将取数序列中最大数去掉之后，次大数也必然满足这一规律。

这个规律感觉就很对，实际也很对，但是懒得证了。然后就能做了，假如目前知道只考虑数值为 $1\sim i$ 的数，能形成的合法取数序列个数。然后只用把 $\lfloor\frac{cnt_{i+1}}{2}\rfloor$ 对 $i+1$ 插进当前的序列即可。

代码：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MXN=2e6+5;
const ll P=998244353;
ll n;
ll cnt[MXN];
ll fac[MXN],ifac[MXN];
ll qpow(ll x,ll y){
    ll r=1;
    while(y){
        if(y&1)r=r*x%P;
        x=x*x%P,y>>=1;
    }
    return r;
}
ll c(ll x,ll y){
    if(y>x || y<0)return 0;
    return fac[x]*ifac[y]%P*ifac[x-y]%P;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    fac[0]=ifac[0]=1;
    for(ll i=1;i<MXN;i++){
        fac[i]=fac[i-1]*i%P;
        ifac[i]=qpow(fac[i],P-2);
    }
    for(ll i=1;i<=n;i++){
        ll x;
        cin>>x;
        cnt[x]++;
    }
    ll tot=0,ans=1;
    for(ll i=1;i<=n;i++){
        ans=ans*fac[cnt[i]]%P*c(tot+cnt[i]/2,cnt[i]/2)%P;
        tot+=cnt[i];
    }
    cout<<ans<<endl;

    return 0;
}

D

假如斜率定了，则截距取到 $i\times k-a_i$ 的中位数时，答案最小。

盲猜一波答案是关于斜率的单谷函数，然后二分谷底就可以过了。注意二分的时候要用 double 而非 int。否则会碰到函数里平坦的地方就寄了。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll MXN = 2e5 + 5;
const ld eps = 0.1;
ll n, arr[MXN];
ld brr[MXN];
ld cal(ld k) {
    for (ll i = 1; i <= n; i++) brr[i] = arr[i] - i * k;
    nth_element(brr + 1, brr + (n + 1) / 2, brr + 1 + n);
    ld mid = brr[(n + 1) / 2], ans = 0;
    for (ll i = 1; i <= n; i++) ans += abs(mid - brr[i]);
    return ans;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie();
    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> arr[i];
    ld mx = 1e18 / n;
    ld l = -mx, r = mx;
    for (ll i = 1; i <= 100; i++) {
        ld mid = (l + r) / 2;
        /* cerr << mid << " " << cal(mid) << " " << cal(mid + eps) << endl; */
        if (cal(mid) <= cal(mid + eps))
            r = mid;
        else
            l = mid;
    }
    ll mn = 1e18;
    for (ll i = l - 2; i <= l + 2; i++) {
        mn = min(mn, (ll)round(cal(i)));
    }
    cout << mn;
    return 0;
}

A（口胡）

由于其他题时间太多了，最后没时间写。队友告诉我只需要把每个点对应坐标存到 dfn 的位置，然后维护区间加向量，区间叉乘，单点求值即可。

M（口胡）

破壁人口胡出来的，感觉很是奇妙。

由于四个状态没法直接 2SAT，可以每个状态拆成两部分：

于是就可以建出一个边数 $O(n^2)$ 的图，然后依次最大化每一个矩形的答案，再 2SAT 判断是否合法，复杂度 $O(n^3)$。

作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接

阅读量:

2021ICPC济南区域赛VP记录

打的还行

E

C

D

A（口胡）

M（口胡）

CATALOG

FEATURED TAGS

FRIENDS