Codeforces Round 906 (Div. 2)

Doremy's Connecting Plan

算法本质

思维

题目大意

给出n个点（暂时没有边），每个点有点值，若某2个点满足以下条件则可以连接一条边：

• 对于第i个点和第j个点，若i点和j点的连通块的所有点值 >= i * j * c（c是给定的常数）

输出是否可以使得图为连通块。

思路推演

首先想到是同点1连接，但是似乎不一定，于是来展开证明：

证明：
若有两个非1点u v，若其可以连接成功，则一定存在某个点可以与1连接成功。

使用反证法。
若两点可以连接成功，可以写出式子：
a[u] + a[v] >= u*v*c
若两点不可同1连接成功，可以写出式子：
a[u] + a[1] < u*c
a[v] + a[1] < v*c
由于u>1 v>1，则可以得出：
所以显然 a[u] + a[v] >= u*v*c >= u*c+v*c > a[u] + a[v] + 2*a[1]
可以看出存在问题，所以得证。

这说明了，我们可以优先处理同1连接的情况，而且由于其仅需要连通，所以我们仅处理同1连接的情况。
每个点同1连接的难度是固定的，所以可以用一个优先队列来处理即可。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
    cin>>n>>k;
    vector<int> a(n+5);
    read(a, 1, n);
    int sum=a[1];
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
    for (int i=2; i<=n; i++)
        q.push({i*k-a[i], i});
    flag = 1;
    while (q.size())
    {
        auto [cha, id] = q.top();
        q.pop();
        if (cha>sum)        // 如果钱不够
        {
            flag=0;
            break;
        }
        sum += a[id];
    }
    cout<<(flag ? "Yes" : "No")<<endl;
    return;
}

Doremy's Drying Plan (Easy Version)

算法本质

思维

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。