Atcoder ABC428游记

F手写300行主席树 然后样例没过 还剩5min这一块

---

题目

题目评级

A.Grandma’s Footsteps

题目描述

高桥在学校里玩得很开心。下课铃一响，游戏就开始了。

铃声响起后，他立即重复以下动作：

• 以每秒 $S$ 米的速度跑 $A$ 秒。然后，保持静止 $B$ 秒。

到下课铃响后 $X$ 秒时，他总共跑了多少米？

思路

小学奥数周期问题 所以就做完了

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int s, a, b, x;
    cin >> s >> a >> b >> x;
    int ans = 0;
    for (int i = 1; i <= x; i++) {
        int tp = i % (a + b);
        if (1 <= tp && tp <= a) {
            ans += s;
        }
    }
    cout << ans;
    return 0;
}

---

B.Most Frequent Substrings

题目描述

给你一个长度为 $N$ 的字符串 $S$ ，由小写英文字母组成。

将长度为 $K$ 的字符串 $t$ 的出现次数定义为满足以下条件的整数 $i$ 的个数：

• $1 \leq i \leq N-K+1$
• 从 $i$ /th字符到 $(i+K-1)$ /th字符的 $S$ 子串符合 $t$ 。

求长度为 $K$ 的字符串出现次数的最大值 $x$ 。同时，按升序词性顺序输出所有长度为 $K$ 且出现次数为 $x$ 的字符串。

思路

你发现$N,K \leq 1000$之后就变成语法题，所以就做完了

但是没读题，挂$1$发的我算什么（？

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    map<string, int> mp;
    for (int i = 0; i <= n - k; i++) {
        string t = s.substr(i, k);
        mp[t]++;
    }
    vector<string> ans;
    int maxx = -1;
    auto it = mp.begin();
    while (it != mp.end()) {
        if (it->second > maxx) {
            maxx = it->second;
            ans.clear();
            ans.push_back(it->first);
        } else if (it->second == maxx) {
            ans.push_back(it->first);
        }
        it++;
    }
    sort(ans.begin(), ans.end());
    cout << maxx << '\n';
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << ' ';
    }
    return 0;
}

---

C.Brackets Stack Query

题目描述

当且仅当一个字符串 $T$ 满足以下条件时，它被称为一个好的括号序列：

• $T$ 可以通过重复以下操作 0 次或更多次变成空字符串：

  • 选择包含在 $T$ 中的 () 作为（连续的）子串并将其删除。

例如，()、(()()) 和空字符串是良好的括号序列，但 )()( 和 ))) 不是良好的括号序列。

有一个字符串 $S$ 。最初， $S$ 是空字符串。
按照给出的顺序处理 $Q$ 查询。每次查询后，判断 $S$ 是否是一个好的括号序列。
查询有两种类型：

• 1 c:给出一个字符 $c$ 。 $c$ 是 ( 或 )。将 $c$ 追加到 $S$ 的末尾。
• 2:删除 $S$ 的最后一个字符。保证此时 $S$ 不是空字符串。

思路

每次就操作最后一个点，所以考虑仿照判断判括号序列时候的方法，搞一个栈。我们知道一个序列是合法括号序列应该就满足：

• 对于每一个位置，左括号前缀个数$\geq$右括号前缀个数
• 左端点总个数$=$右端点总个数

所以我们的栈就维护两个值：当前位置前缀的左括号前缀个数-右括号前缀个数和前面这个东西的前缀最小值，最后判断的时候只需要判断栈顶的第一个元素是不是$0$，第二个元素是不是$\geq 0$即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int T;
    cin >> T;
    vector<pair<int, int>> st;
    st.push_back({0, 0});
    while (T--) {
        int ch;
        cin >> ch;
        if (ch == 1) {
            char c;
            cin >> c;
            int x = st.back().first, y = st.back().second;
            st.push_back({x + (c == '(' ? 1 : -1), min(y, x + (c == '(' ? 1 : -1))});
        } else {
            st.pop_back();
        }
        if (!st.back().first && st.back().second >= 0) {
            cout << "Yes" << '\n';
        } else {
            cout << "No" << '\n';
        }
    }
    return 0;
}

---

D.183184

题目描述

对于正整数 $x$ 和 $y$ ，定义 $f(x,y)$ 如下：

• 设 $z$ 是将十进制符号 $x,y$ 解释为字符串并按此顺序连接得到的字符串。设 $f(x,y)$ 是将 $z$ 解释为十进制整数时的值。

例如， $f(3,14)=314,\ f(100,3)=1003$ 。

给你正整数 $C$ 和 $D$ 。求满足以下条件的整数 $x$ 的个数：

• $1 \leq x \leq D$
• $f(C, C+x)$ 是一个完全平方。

给你 $T$ 个测试用例，求每个测试用例的答案。

思路

今日已完成卡精度但是居然没被卡到大学习(1/1)

加的数在$[1,D]$的区间里，我们直接疯狂枚举它可能有的长度，然后按照sqrt分块把这一块的和累加到ans里就做完了

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int pre[12];
void init()
{
    pre[0] = 1;
    for (int i = 1; i < 12; i++) {
        pre[i] = pre[i - 1] * 10;
    }
}
int sqrt1(int x)
{
    if (x <= 1) {
        return x;
    }
    int tp = sqrtl((long double)x);
    tp = max(0LL, tp);
    while (tp * tp > x) {
        tp--;
    }
    while ((tp + 1) * (tp + 1) <= x) {
        tp++;
    }
    return tp;
}
int sqrt2(int x)
{
    int tp = sqrt1(x);
    return (tp * tp == x) ? tp : tp + 1;
}
signed main()
{
    init();
    int T;
    cin >> T;
    while (T--) {
        int c, d;
        cin >> c >> d;
        int st = log10(c + 1) + 1;
        int ed = log10(c + d) + 1;
        int ans = 0;
        for (int i = st; i <= ed; i++) {
            if (max(c + 1, pre[i - 1]) > min(c + d, pre[i] - 1)) {
                continue;
            }
            int tp = c * pre[i];
            if (tp + max(c + 1, pre[i - 1]) > tp + min(c + d, pre[i] - 1)) {
                continue;
            }
            if (sqrt2(tp + max(c + 1, pre[i - 1])) <= sqrt1(tp + min(c + d, pre[i] - 1))) {
                ans += sqrt1(tp + min(c + d, pre[i] - 1)) - sqrt2(tp + max(c + 1, pre[i - 1])) + 1;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

---

E.Farthest Vertex

题目描述

有一棵树，树上有 $N$ 个顶点，编号为 $1$ 至 $N$ 。 $i$ -th 边连接顶点 $A_i$ 和 $B_i$ 。
将顶点 $u$ 和 $v$ 之间的距离定义为路径中端点位于顶点 $u$ 和 $v$ 的边的数量。(这条路径是唯一确定的）。

求解下面有关 $v = 1, 2, \dots, N$ 的问题。

• 在顶点 $1, 2, \dots, N$ 中，输出与顶点 $v$ 距离最大的顶点的编号。如果有多个顶点满足条件，则输出个顶点中数字最大的顶点。

思路

猜结论题！但是我们因为BFS要返回距离最远编号最大的点，但是我脑抽的返回了最后搜到的点，导致我们吃4发没发现 快来踩我啦啦啦

结论：

证明：观察样例 因为我不会证明（？

所以我们直接从$1$BFS找到满足距离最远编号最大的点$A$，维护一个$A$的dist1数组，再从$A$开始BFS，找到另一个距离最远编号最大的点$B$，最后一次BFS再维护一个dist2记录$B$到每个点的距离。

对于每个点，答案就是$A$或$B$中的一个，我们按着题面判断答案是$A$还是$B$就做完了。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int> edges[555555];
int n;
int bfs(int st, vector<int> &dist)
{
    for (int i = 1; i <= n; ++i) dist[i] = -1;
    queue<int> q;
    q.push(st);
    dist[st] = 0;
    int res = st;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (dist[u] > dist[res] || (dist[u] == dist[res] && u > res)) {
            res = u;
        }
        for (auto nex : edges[u]) {
            if (dist[nex] == -1) {
                dist[nex] = dist[u] + 1;
                q.push(nex);
            }
        }
    }
    return res;
}
signed main()
{
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    vector<int> dist1(n + 1), dist2(n + 1);
    int a = bfs(1, dist1);
    int b = bfs(a, dist1);
    bfs(b, dist2);
    for (int v = 1; v <= n; v++) {
        if (dist1[v] > dist2[v]) {
            cout << a << '\n';
        } else if (dist2[v] > dist1[v]) {
            cout << b << '\n';
        } else {
            cout << max(a, b) << '\n';
        }
    }
    return 0;
}

---

复盘

aaaaaa 昨天伊蕾娜生日，都5年了你们日本人不出第二季出这么恶心的题想干嘛啊