CF2063 无意之间的补题记录

 

TD Game With Triangles 2000

题目大意

平面上有 个互不相同的点 。初始时你的得分为 。你可以通过以下操作增加得分：

• 选择三个不共线的不同点；
• 将得分增加这三个点形成三角形的面积；
• 从平面中删除这三个点。

游戏示例，其中执行了两次操作。设 表示可执行操作的最大次数。例如若无法执行任何操作，则 。另外定义 为恰好执行 次操作时可能达到的最大得分。此处 对所有满足 的整数 均有定义。

请找出 的值，并分别计算所有 对应的 值。

解答

这道题赛时想到了思路，但是因为时间不够没有调出来。然后掉到了 1800 多名去了（Codeforces Round 1000）。Yee tour fen.

容易发现，选线段肯定是选最两边的，选点肯定是选最中间的。这样是最优的。那么我们首先给点排序（题目里没说序列有序！！），然后就可以开始贪心选：每次选线段就比较一下 侧的两端的距离和 侧两端的距离。然后选最长的那一端，假设为 端。然后把两端的两个点和 端的中间的那一个点给删掉。然后把这个三角形记录到 栈里面（栈的作用后面再说）。如果在 端同理。

但是这个时候，你会遇到在 端选完了，但是 端还剩一堆点的情况。这个时候因为还没有达到 ，所以肯定是要强制选对面的一些点的。那么我们就从 栈里面弹出来一个三角形（就是删除一个三角形。根据从大到小选的原则，这个三角形是面积最小的）。这样就给对面的点创造出来了 个 点。然后对面的 个 点再和这 个 点相组合，就是 个新的三角形。再减去弹出来的那个三角形，就相当于这就是多了一个三角形的最优答案。

那么边界 如何算？这个其实是好算的。设最终选的最多次在 端选了 条线段，在 端选了 条线段。

那么就可以列出不等式：

联立可得 。

又因为两侧选点的极限是 ，所以 。

于是这道题就做完了。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
typedef long long ll;
struct Stack{
    ll val[N];
    int len=0;
    void push(ll x){
        val[++len] = x;
    }
    void pop(){len--;}
    ll top(){return val[len];}
    int size(){return len;}
    void clear(){len = 0;}
}sta, stb;
ll a[N], b[N];
int cnta, cntb;
int n, m, kmax;
ll ans = 0;
int apos, bpos;
void ProcessA(){
    ans += (a[n-apos+1] - a[apos]);
    sta.push(a[n-apos+1] - a[apos]);
    apos ++;
    cnta -= 2, cntb -= 1;
}
void ProcessB(){
    ans += (b[m-bpos+1] - b[bpos]);
    stb.push(b[m-bpos+1] - b[bpos]);
    bpos ++;
    cntb -= 2, cnta -= 1;
}
void DelA(){
    ans -= sta.top(), sta.pop();
    cnta += 2, cntb += 1;
}
void DelB(){
    ans -= stb.top(), stb.pop();
    cntb += 2, cnta += 1;
}
ll f[N];
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    sort(a+1, a+1+n), sort(b+1, b+1+m);
    kmax = min({n, m, (n+m)/3});
    ans = 0;
    cnta = n, cntb = m;
    apos = 1, bpos = 1;
    for(int i=1;i<=kmax;i++){
        if((cnta >= 2 && cntb >= 2 && 
            (a[n-apos+1] - a[apos]) >= (b[m-bpos+1] - b[bpos]))
         || (cnta >= 2 && cntb == 1)){
            ProcessA();
        }else if((cntb >= 2 && cnta >= 2 && 
            (a[n-apos+1] - a[apos]) < (b[m-bpos+1] - b[bpos]))
         || (cnta == 1 && cntb >= 2)){
            ProcessB();
        }else if(cnta == 0){
            DelA();
            ProcessB();
            ProcessB();
        }else if(cntb == 0){
            DelB();
            ProcessA();
            ProcessA();
        }
        f[i] = ans;
    }
    cout<<kmax<<'\n';
    for(int i=1;i<=kmax;i++){
        cout<<f[i]<<' ';
    }
    cout<<'\n';
}
void duoceclear(){
    sta.clear(), stb.clear();
    cnta = 0, cntb = 0;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        solve();
        duoceclear();
    }
}

TE Triangle Tree 2300

题目大意

给定一棵以节点 为根、包含 个节点的有根树 。节点对 被称为好对，当且仅当 不是 的祖先 且 不是 的祖先。对于任意两个节点， 定义为从 到 的唯一简单路径的边数， 定义为它们的最近公共祖先。

定义函数 如下：

• 若 是好对，则 为满足以下条件的整数 的数量：存在一个由边长 、 和 构成的非退化三角形 。
• 否则，。

你需要计算以下值：

$$\sum_{i = 1}^{n-1} \sum_{j = i+1}^n f(i,j).$$

树是无环连通图。有根树是指定一个特殊节点为根的树。

节点 的祖先是从 到根的简单路径上的所有节点（包含根但不含 自身）。根节点没有祖先。

当边长 、、 满足 、、 时，三角形为非退化的。

解答

以 为边长， 已知，是三角形的条件很明显就是 。所以可以对于每一个点对列式子来算出合法三角形个数。

我们可以列出来两种情况：

1. 当 和 互不为祖先时：

$$f(u,v) = dep_u + dep_v - 2dep_{lca} - |dep_u - dep_v| - 1$$

1. 否则， 和 一个是另一个的祖先，

$$f(u,v) = dep_u + dep_v - 2dep_{lca} - |dep_u - dep_v|$$

那么就可以把式子分成 4 个部分：

1. 计算所有的 。对于每一个 ，它的贡献次数很明显是 次。因为以其为端点最多也就只有 种情况。

2. 计算所有的 。这个可以后面 DFS 出 的值之后，先将其排一个序，然后再从小到大，利用前缀和来计算。

3. 计算所有的 。注意到 的情况是只会发生在 和 互不为祖先的情况。所以可以先算出所有 和 一个是另一个的祖先的情况，然后再用所有的情况减去这个数。这种情况可以当 DFS 完某一个点 的时候，就把答案加上 。因为它的后代都和这个点造出来了一个是另一个的祖先的情况。

4. 计算所有的 。我们可以在 DFS 某个点 的时候，钦定现在算的 就是 。那么 为 的情况就只有两种：

   • 两个节点都是它的后代，并且这两个节点分别在两个不同儿子的子树里。也就是存在 ，，。这种情况的答案就是列举所有两个不同的儿子 ，。那么算这个并且复杂度要正确，就可以使用前缀和，既能时间复杂度正确，也可以消掉前面不必要的 。
   • 一个节点是 ，另一个节点 。这种情况只有 种。

   所以情况数 就为这两个答案加起来。它对总答案的贡献就是 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+5;
vector<int> edge[N];
#define add(u,v) edge[u].push_back(v), edge[v].push_back(u)
// int fa[N];
// if v is not u's anc, ans_{u, v} = dep[u] + dep[v] - 2dep[lca] - |dep[u]-dep[v]| - 1
// or else ans = dep[u] + dep[v] - 2dep[lca] - |dep[u] - dep[v]|

int n;
typedef long long ll;
ll anspre2, ansmid1, ansabs, anslst;
// anspre2 = sum dep[u] + dep[v], ansmid1 = sum 2dep[lca], ansabs = sum |dep[u]-dep[v]|, anslst = sum 1
int dep[N], siz[N];
void dfs(int x, int fa){
    dep[x] = dep[fa] + 1;
    ll presum = 0; // presum -> siz
    ll xcnt = 0;
    siz[x] = 1;
    for(int v: edge[x]){
        if(v == fa) continue;
        dfs(v, x);
        xcnt += presum * siz[v];
        siz[x] += siz[v], presum += siz[v];
    }
    ansmid1 += 2 * dep[x] * (xcnt + siz[x] - 1);
    anslst += (siz[x] - 1);
}
void GetAnsPre2(){
    for(int i=1;i<=n;i++) anspre2 += 1ll * dep[i] * (n-1);
}
int b[N];
void GetAnsAbs(){
    for(int i=1;i<=n;i++) b[i] = dep[i];
    sort(b+1, b+1+n);
    ll presum = 0;
    for(int i=1;i<=n;i++){
        ansabs += (1ll*b[i]*(i-1))-presum;
        presum += b[i];
    }
}
void solve(){
    cin>>n;
    int u, v;
    for(int i=1;i<n;i++){
        cin>>u>>v; add(u, v);
    }
    dfs(1, 0);
    GetAnsPre2();
    GetAnsAbs();
    anslst = 1ll*(n)*(n-1)/2 - anslst;
    // cout<<anspre2<<' '<<ansmid1<<' '<<ansabs<<' '<<anslst<<'\n';
    cout<<anspre2 - ansmid1 - ansabs - anslst<<'\n';
}
void duoceclear(){
    for(int i=1;i<=n;i++) edge[i].clear(), edge[i].shrink_to_fit();
    anspre2 = ansmid1 = ansabs = anslst = 0;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        solve();
        duoceclear();
    }
}

TF1 Counting Is Not Fun (EZ) 2400

题目大意

这是该问题的简单版本。与困难版本的区别在于，此版本对 和 的限制更小。

一个括号序列被称为平衡的，当且仅当其可以通过以下形式文法构造：

1. 空序列 是平衡的。
2. 若括号序列 是平衡的，则 也是平衡的。
3. 若括号序列 和 是平衡的，则拼接序列 也是平衡的。

例如，序列 “(())()”、”()”、”(()(()))” 和空序列是平衡的，而 “(()” 和 “(()))(“ 则不是。

给定一个平衡括号序列 ，当满足以下条件时，索引对 （）被称为好对： 是 ‘(‘， 是 ‘)’，且这两个括号是在构造序列 时通过规则 2 同时添加的。例如，序列 “(())()” 有三个不同的好对：、 和 。可以证明，任何包含 个括号的平衡括号序列恰好有 个不同的好对，且无论用何种规则顺序构造同一括号序列，得到的好对集合都相同。

Emily 将与 John 进行括号猜谜游戏。游戏规则如下：

初始时，John 有一个包含 个不同好对的平衡括号序列 ，但 Emily 不知道其内容。John 告诉 Emily 的值，并要求 Emily 猜测该序列。

在 轮中，John 每轮给出如下形式的线索：

• ：序列 包含好对 。

John 给出的线索互不相同且互不矛盾。

在某个时刻，Emily 可以确定满足当前所有线索的平衡括号序列是唯一的。例如，假设 Emily 知道 有 个好对，并包含好对 。在 个有 个好对的平衡括号序列中，只有序列 “((()))” 包含好对 。因此，可以看出 Emily 并不总是需要 轮才能猜出 。

为了尽早确定 的内容，Emily 希望知道每轮线索后符合条件的平衡括号序列数量。显然这对 Emily 来说并非易事，尤其当存在大量好对时。现在轮到你来帮助 Emily。给定所有线索，你需要在每轮前后输出答案。由于答案可能很大，请对 取模。

解答

这道题因为 ，所以可以使用 模拟。

因为每一个合法的括号对，可以把整个序列分为内外两部分。

然后整个序列就被分成了一个类似树形的结构。

然后就会发现，对于每一个树上的节点以及其代表的区间 ，那么就可以算出没有被点 、 和儿子占用的空余区间长度为 。要求出总长为 的合法的括号序列对数，很容易想到答案就是 。所有的答案就是所有区间的 乘起来就可以了。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 10004;
typedef long long ll;
const ll mod = 998244353;
ll catalan[N];
int n;
ll ksm(ll bas, ll x){
    ll ans = 1;
    while(x){
        if(x&1) ans = ans * bas % mod;
        bas = bas * bas % mod; x>>=1;
    }
    return ans;
}
void init(){
    catalan[0] = 1;
    for(int i=1;i<N;i++){
        catalan[i] = catalan[i-1]*ksm(i+1, mod-2) % mod * (4*i-2) % mod;
    }
}
struct Status{
    int exist, st;
    // st = 0: 入，1: 出
}p[N];

void check_and_insert(int l, int r){
    p[l].exist = 1, p[l].st = 0;
    p[r].exist = 1, p[r].st = 1;
}
int depans[N], nowdep;
int len = 0;
void simulation(){
    nowdep = 0;
    ll ans = 1;
    // cout<<"SIMULATING...\n";
    for(int i=0;i<=len+1;i++){
        if(p[i].exist){
            if(p[i].st == 0) nowdep ++;
            else{
                ans = (ans * catalan[depans[nowdep]/2]) % mod;
                depans[nowdep] = 0; nowdep --;
            }
        }else depans[nowdep] ++;
        // cout<<nowdep<<' ';
    }
    // cout<<'\n';
    cout<<' '<<ans;
    // cout<<'\n';
}

void solve(){
    cin>>n;
    len = n*2;
    cout<<catalan[n];
    p[0] = {1, 0}, p[len+1] = {1, 1};
    for(int i=1;i<=n;i++){
        int l, r;
        cin>>l>>r;
        check_and_insert(l, r);
        simulation();
    }
    cout<<'\n';
}

void duoceclear(){
    for(int i=0;i<=len+1;i++) p[i].exist = p[i].st = 0;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    cin>>t;
    init();
    while(t--){
        solve();
        duoceclear();
    }
    return 0;
}

TF2 Counting Is Not Fun (HD) 2700

题目大意

与 TF1 的题意完全一致，但是加强数据范围，。

解答

书接上回，上一道题造成时间复杂度过大的原因就是使用了模拟的做法。我们需要优化这个做法使得复杂度为 。

这个时候，我们就需要维护一个树形结构。这个树上的每一个点都维护了这个点对应区间的 。如果是要快速插入区间，这个是不好维护的。那么正难则反，可以用时光倒流法。

首先我们把一棵完整的树建出来。那么就可以开始删点了。我们维护一个答案 ，表示现在的答案。每删一个区间，设其代表的节点为 ，就可以将其所有的儿子 都连到它的父亲 ，并且更新它父亲的 。即 。暴力连边会被卡，那么就使用并查集。然后更新答案。在 更新之前 。然后再 更新之后 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 600004;
typedef long long ll;
const ll mod = 998244353;
ll catalan[N], invcata[N];
int n;
ll ksm(ll bas, ll x){
    ll ans = 1;
    while(x){
        if(x&1) ans = ans * bas % mod;
        bas = bas * bas % mod; x>>=1;
    }
    return ans;
}

void init(){
    catalan[0] = 1;
    for(int i=1;i<N;i++){
        catalan[i] = catalan[i-1]*ksm(i+1, mod-2) % mod * (4*i-2) % mod;
    }
    for(int i=0;i<N;i++) invcata[i] = ksm(catalan[i], mod-2);
}

int have[N];
int len = 0;
int val[N], st[N], top;
int father[N];
void simulation(){
    for(int i=1;i<=len;i++){
        if(have[i] == 0){
            val[st[top]] ++;
        }else{
            if(have[i] ^ st[top]){ // Start
                st[++top] = have[i];
            }else{
                top --;
                father[have[i]] = st[top];
            }
        }
    }
}
ll ans[N];
struct DSU{
    int fa[N];
    void init(int x){
        for(int i=1;i<=x;i++) fa[i] = i;
    }
    int getfa(int x){
        return (fa[x] == x)? x: (fa[x] = getfa(fa[x]));
    }
}dsu;
void solve(){
    cin>>n;
    len = n*2;
    for(int i=1;i<=n;i++){
        int l, r;
        cin>>l>>r;
        have[l] = have[r] = i;
    }
    simulation();
    dsu.init(len);
    ans[n+1] = 1;
    for(int i=0;i<=n;i++) ans[n+1] = ans[n+1] * catalan[val[i]/2] % mod;
    for(int i=n;i>=1;i--){
        ans[i] = ans[i+1] * invcata[val[i]/2] % mod;
        int x = dsu.getfa(father[i]);
        dsu.fa[i] = x;
        ans[i] = ans[i] * invcata[val[x]/2] % mod;
        val[x] += val[i] + 2;
        ans[i] = ans[i] * catalan[val[x]/2] % mod;
    }
    for(int i=1;i<=n+1;i++){
        cout<<ans[i]<<' ';
    }
    cout<<'\n';
}

void duoceclear(){
    for(int i=0;i<=n;i++) ans[i] = val[i] = 0;
    ans[n+1] = 0;
    for(int i=0;i<=len;i++) have[i] = 0;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    cin>>t;
    init();
    while(t--){
        solve();
        duoceclear();
    }
    return 0;
}