Codeforces Round 796 (Div. 2)

The Enchanted Forest

算法本质

思维

题目大意

一维坐标上1~n上有n个金币产生器，0秒时每个金币产生器旁的金币是a[]表示，其每秒可以产生1金币。

玩家0秒时可以移动至任意一点，一秒内会顺序进行以下操作：

• 玩家移动至相邻格子或者不变
• 玩家收集在这个格子上的所有金币
• 金币产生器都产出1金币

在第k秒时，输出最大化的金币收集数。（相当于进行以上k次操作）

思路推演

朴素的想可以发现，当k<n时，玩家总是不喜欢走回头路的。
然后开始证明。

玩家的收益可以大体分成两个部分：初始金币 + 增长金币
如果玩家回头，则两部分收益都会下降，得证。
不回头，则增长金币收益不变，所以只要找长度k的最大子段和。

但是k>=n的情况可能有所不同。
初始金币一定是会完全收集的，那如何才能得到最多的增长金币呢。

也许可以反过来想一想，既然时间固定，增长金币的总数是一定的，我们只需要让增长金币最后剩余在地图上最少即可——k操作的最后n次操作完整走一遍地图即可。（之前的时间可以在原地发呆）

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
    cin>>n>>k;
    vector<int> a(n+5);
    read(a, 1, n);
    int res, ans;
    if (k<n)
    {
        res = accumulate(a.begin()+1, a.begin()+1+k, 0ll);
        ans = res;
        for (int i=k+1; i<=n; i++)
        {
            res += -a[i-k] + a[i];
            ans = max(ans, res);
        }
        ans += (k-1)*k/2;        // 增长金币部分
    }
    else
    {
        ans = accumulate(a.begin()+1, a.begin()+1+n, 0ll);
        int more = (n-1)*n/2;
        more += (k-n)*n;
        ans += more;
    }
    cout<<ans<<endl;
    return;
}

Sanae and Giant Robot

算法本质

思维 !

题目大意

给定两个长度n数组a[] b[]和m个区间，玩家希望让a[]变得同b[]一致，可以进行任意次一下操作：

• 选择某个区间l r，保证$\sum_{i=l}^{r}a_i = \sum_{i=l}^{r}b_i$，然后使得a[l~r] := b[l~r]

思路推演

朴素地去想暂时没结果，缺少进入的思路。

然后就想不出来了

显然，如果a[] b[]的元素之和不相等，则肯定不可行。
当我们使用操作时，似乎将一个数组分割成了两份，我们是否需要维护两份数组的也遵从上面的规律呢。

我们回溯操作观察，这个规律会更明显。

至此我们修改操作的规则：

• 选择某个区间l r，保证$pa[l-1]=pb[l-1] \quad and \quad pa[r]=pb[r] $，然后使得a[l~r] := b[l~r]

新的操作规则，才能称之为有效操作，其他的操作可以视作无效甚至于破坏相等

抽象题意：

可以视作这里有下标0开始长度n+1的01数组c[]和m个区间。
若区间l r满足c[l] = c[r] = 1则可以使得c[l~r] := 1。
最后希望使得c[0 ~ n]=1

分析一下，我们希望能做一个类似触发器的东西，当c[l] = c[r] = 1时可以触发至某个区间。
当然使用二维信息作key值显然复杂度不允许，所以就以下标做key值，触发时判断一下另外一个条件即可。

另外当我们进行c[l~r] := 1操作时，那些从0值变成1值，会进行一次触发。
这可以使用并查集里的find来优化——因为所有下标只触发一次。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
// 借用并查集find的优化结构
int go[maxn];
int find(int x)        // 找到右边（含自己）第一个未被遍历的
{
    if (go[x]==0)    return x;
    return go[x] = find(go[x]);
}
inline void solve()
{
    cin>>n>>m;
    vector<int> a(n+5), b(n+5), c(n+5);
    read(a, 1, n);
    read(b, 1, n);
    vector<int> tol(m+5), tor(m+5);        // 第i个区间的信息：id --> 下标
    vector<vector<int>> booml(n+5), boomr(n+5);     // 下标 --> id
    for (int i=1; i<=m; i++)
    {
        int l, r;
        cin>>l>>r;
        l--;
        tol[i] = l;
        tor[i] = r;
        booml[l].push_back(i);
        boomr[r].push_back(i);
    }
    queue<int> q;
    auto f = [&](int p) {        // 触发器
        c[p] = 1;
        go[p] = p+1;
        for (int id:booml[p])
            if (c[ tor[id] ])        // 成功触发
                q.push(id);
        for (int id:boomr[p])
            if (c[ tol[id] ])
                q.push(id);
    };
    int pa=0, pb=0;
    for (int i=0; i<=n+1; i++)    go[i]=0;    // 这里注意细节使得go[n+1]=0
    for (int i=0; i<=n; i++)
    {
        pa += a[i];
        pb += b[i];
        if (pa==pb)    f(i);        // 触发
    }
    while (q.size())
    {
        int id=q.front();
        q.pop();
        int l=tol[id], r=tor[id];
        for (int p=find(l); p<=r; p=find(p))        // 触发
            f(p);
    }
    flag = 1;
    for (int i=0; i<=n; i++)
        flag &= c[i];
    cout<<(flag ? "YES" : "NO")<<endl;
    return;
}

title

算法本质

题目大意

思路推演

ac核心代码

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

title

算法本质

题目大意

思路推演

ac核心代码

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

title

算法本质

题目大意

思路推演

ac核心代码

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

title

算法本质

题目大意

思路推演

ac核心代码

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

title

算法本质

题目大意

思路推演

ac核心代码

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