Atcoder ABC434游记

题目

A.Triangular Number

题目描述

你得到一个正整数 $N$ 。

输出从 $1$ 到 $N$ 的所有整数的和，即 $1+2+\cdots+N$ 。

思路

语法题

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    int n;
    cin >> n;
    cout << n * (n + 1) / 2;
    return 0;
}

B.No-Divisible Range

题目描述

给定一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\ldots,A_N)$ 。

求满足 $1\leq l\leq r\leq N$ 的整数 $(l,r)$ 对满足下列条件的个数：

对于每一个满足 $l\leq i\leq r$ 的整数 $i$ ， $A_i$ 是而不是是 $A_l+A_{l+1}+\cdots+A_r$ 的因数。

思路

语法题

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<int> s(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + a[i];
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int tp = s[j] - s[i - 1];
            bool flag = 1;
            for (int k = i; k <= j; k++) {
                if (tp % a[k] == 0) {
                    flag = 0;
                    break;
                }
            }
            ans += flag;
        }
    }
    cout << ans;
    return 0;
}

C.Domino

题目描述

在数轴上有一排多米诺骨牌。第一个多米诺骨牌位于坐标 $i$ 处，高度 $A_i$ 。

当第 $i$ 张多米诺骨牌向右倒下时，坐标 $i$ 到 $i+A_i-1$ （含）范围内的所有多米诺骨牌都向右倒下。

当第一张多米诺骨牌向右倒下时，总共会有多少张多米诺骨牌倒下？

思路

从前到后遍历一遍，每次更新最远能到达的位置即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int pos = 1; 
    for (int i = 1; i <= pos && i <= n; i++) {
        pos = max(pos, i + a[i] - 1);
    }
    cout << min(pos, n);
    return 0;
}

D.Reachability Query 2

题目描述

给定一个有向图，有 $N$ 个顶点和 $M$ 条边。

顶点编号从 $1$ 到 $N$ ，第 $i$ 条边是从顶点 $X_i$ 到顶点 $Y_i$ 的有向边。

最初，所有的顶点都是白色的。

按顺序处理 $Q$ 查询。每个查询都是以下两种类型之一：

• ‘1 v’：把颜色顶点 $v$ 改为黑色。

• ‘2 v’：确定是否可以沿着顶点 $v$ 的边到达黑色顶点。

思路

有向边，所以没有想怎么DSU。

在读边的时候把反向边读了，每次修改节点颜色直接沿着反向边BFS标记一下哪些结点可达黑色节点就过了。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int> edges[333333];              
vector<int> redges[333333];           
bool ans[333333], vis[333333];   
void bfs(int x)
{
    queue<int> q;
    q.push(x);
    vis[x] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int nex : redges[u]) {
            if (!vis[nex]) {
                vis[nex] = 1;
                q.push(nex);
            }
        }
    }
}
signed main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        redges[v].push_back(u);
    }
    int T;
    cin >> T;
    while (T--) {
        int ch, x;
        cin >> ch >> x;
        if (ch == 1) {
            if (!ans[x]) {
                ans[x] = 1;
                bfs(x);
            }
        } else {
            cout << (vis[x] ? "Yes" : "No") << '\n';
        }
    }
    return 0;
}

E.Cover query

题目描述

$N$ 格子从左到右排成一行。

从左边 $(1\leq i\leq N)$ 开始的 $i$ \第一个格子称为 $i$ 格子。

最初，所有的格子被涂成白色。

按顺序处理 $Q$ 查询。

$i$ \查询 $(1\leq i\leq Q)$ 如下所示：

给出两个整数 $(L_i,R_i)$ $(1\leq L_i\leq R_i\leq N)$ 。

将所有格子 $L_i, L_i+1, \ldots, R_i$ 涂成黑色。

在这里，被涂成白色的格子现在被涂成黑色，而被涂成黑色的格子保持原样。

之后，找出（在 $N$ 格子中）被涂成白色的格子数。

思路

感谢这道题：http://oj.daimayuan.top/contest/397/problem/3335

每次都把得到的整数看作线段，用set维护这些线段。对于重合的线段直接在set里面upperbound找到第一个重合的，一个一个删了就好了。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    int n, T;
    cin >> n >> T;
    set<pair<int, int>> st;
    int cnt = 0;
    while (T--) {
        int l, r;
        cin >> l >> r;
        auto it = st.upper_bound({l, LLONG_MAX});
        if (it != st.begin()) {
            it--;
            if (it -> second < l) {
                it++;
            }
        }
        int p1 = l, p2 = r;
        vector<pair<int, int>> v;  
        while (it != st.end() && it -> first <= r) {
            cnt -= (it -> second - it -> first + 1);
            p1 = min(p1, it -> first);
            p2 = max(p2, it -> second);
            v.push_back(*it);
            it++;
        }
        for (int i = 0; i < v.size(); i++) {
            st.erase(v[i]);
        }
        st.insert({p1, p2});
        cnt += (p2 - p1 + 1);
        cout << n - cnt << '\n';
    }
    return 0;
}

F.Cat exercise

题目描述

$N$ 个塔从左到右排成一排，从左边 $(1\leq i\leq N)$ 开始的第 $i$ 塔的高度为 $P_i$ 。

这里， $(P_1,P_2,\ldots,P_N)$ 是 $(1,2,\ldots,N)$ 的一个排列。

第 $i$ 和左边第 $j$ 之间的距离定义为 $\lvert i-j\rvert$ 。

有一只猫，最初在高度为 $N$ 的猫塔的顶端。

Takahashi想通过反复选择和移除塔来锻炼这只猫。

当Takahashi移走一座塔时，猫的移动方式如下：

• 如果猫不在被移除的塔的顶部，猫不会移动。

• 如果猫在被移除的塔的顶部，并且在塔的左边或右边至少有一个塔存在，猫会移动到塔中最高的塔（不包括被移除的塔），通过从被移除的塔开始反复移动到相邻的塔。此时，猫移动的是移动前塔和移动后塔之间的距离（移动前、移动后和移动过程中塔的高度无关紧要）。

• 如果猫在被移除的塔的顶部，并且塔的左边或右边没有相邻的塔，猫就会跳到高桥的怀里，练习到这里结束。在这种情况下，不会发生任何移动。

在这里，被拆除的塔之间的空间没有被填满。也就是说，最初与从左边开始的第 $i$ 座塔相邻的塔只是从左边开始的第 $(i-1)$ 和第 $(i+1)$ 座塔（如果它们存在的话），并且它们将永远不会与其他塔相邻，因为之后会移除其他塔。

找出猫在练习结束前可能移动的最大总距离。

思路

一眼笛卡尔树，闭着眼树形dp做完了

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int lc[222222], rc[222222], dp[222222], n;
void dfs(int x)
{
    if (x == 0) {
        return;
    }
    if (lc[x]) {
        dfs(lc[x]);
    }
    if (rc[x]) {
        dfs(rc[x]);
    }
    int maxx = 0;
    if (lc[x]) {
        int u = lc[x];
        while (u) {
            maxx = max(maxx, abs(x - u) + dp[u]);
            u = rc[u];
        }
    }
    if (rc[x]) {
        int u = rc[x];
        while (u) {
            maxx = max(maxx, abs(x - u) + dp[u]);
            u = lc[u];
        }
    }
    dp[x] = maxx;
}
signed main()
{
    cin >> n;
    vector<int> a(n + 1);
    stack<int> st;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        lc[i] = 0;
        rc[i] = 0;
        int ls = 0;
        while (!st.empty() && a[st.top()] < a[i]) {
            ls = st.top();
            st.pop();
        }
        rc[i] = ls;
        if (!st.empty()) {
            lc[st.top()] = i;
        }
        st.push(i);
    }
    int rt = -1;
    while (!st.empty()) {
        rt = st.top();
        st.pop();
    }
    dfs(rt);
    cout << dp[rt];
    return 0;
}

复盘

F出原题何意味 但是这题是我不会的树剖