Blog - Floating Ocean
0%

AtCoder - ABC 291

发表于 更新于
本文字数： 5.4k 阅读时长 ≈ 10 分钟
阅读次数： Valine：

Contestant. Rank 1877. Rating +196.

A. camel Case

题意

给定一个由一个大写字母和若干个小写字母组成的字符串，输出大写字母的位置。

思路

如题，很签到。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f;

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    string s;
    cin >> s;
    for(int i=0;i<s.size();i++){
        if(s[0] >= 'A' && s[i] <= 'Z'){
            cout << i + 1 << '\n';
            break;
        }
    }
}

无聊的签到题

B. Trimmed Mean

题意

给定 个评委的分数，去掉最大 个和最小 个评委的分数，输出剩余分数的平均数。

思路

如题，排个序即可。

时间复杂度：O(nlogn)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f;

int a[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin >> n;
    for(int i=0;i<5 * n;i++) cin >> a[i];
    sort(a, a + 5 * n);
    double ans = 0;
    for(int i=n;i<5*n-n;i++) ans += (double) a[i];
    cout << (ans / ((double) 3 * n)) << '\n';
}

差点看成只各去掉一个（（

C. LRUD Instructions 2

题意

给定一个由 组成的字符串，模拟点的移动， 表示横坐标减一， 表示横坐标加一， 表示纵坐标减一， 表示纵坐标加一。输出有多少点被经过了至少两遍。

思路

如题，模拟即可。

可以用 存有没有经过，或者开一个布尔数组。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f;

int a[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    map<pii, bool> mp;
    int n;
    cin >> n;
    string s;
    cin >> s;
    pii p = {0, 0};
    mp[p] = true;
    bool f = false;
    for(int i=0;i<n;i++){
        char now = s[i];
        if(now == 'L'){
            p.first --;
        }else if(now == 'R'){
            p.first ++;
        }else if(now == 'U'){
            p.second ++;
        }else p.second --;
        if(mp[p]){
            f = true;
            break;
        }
        mp[p] = true;
    }
    cout << (f ? "Yes\n" : "No\n");
}

捏马的，忘了在走过以后设标记了（（

D. Flip Cards

题意

给定 张牌，牌的正反两面各印有一个数字，输出整个牌组满足条件的正反情况，满足相邻牌值不相等。

思路

考虑到只需满足相邻牌值不相等，所以我们不妨采用 的方式，定义一个 表示第 位及以前的牌满足第 张牌的正反情况满足 的情况总数， 表示向上，否则向下。

那么，对于一个位置，它有两种递推的方式——从上一个为正面的牌的情况数和从上一个为反面的牌的情况数。两个递推的方式的和即为当前位置的值。

如，如果不考虑相邻牌不相等，那么

。

考虑条件的话，我们用 判断即可。

当然，初始情况下 。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f, mod = 998244353;

int dp[N][2];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin >> n;
    int lastA, lastB;
    cin >> lastA >> lastB;
    dp[1][0] = 1, dp[1][1] = 1;
    for(int i=2;i<=n;i++){
        int nowA, nowB;
        cin >> nowA >> nowB;
        if(nowA != lastA) dp[i][0] = (dp[i][0] + dp[i - 1][0]) % mod;
        if(nowA != lastB) dp[i][0] = (dp[i][0] + dp[i - 1][1]) % mod;
        if(nowB != lastA) dp[i][1] = (dp[i][1] + dp[i - 1][0]) % mod;
        if(nowB != lastB) dp[i][1] = (dp[i][1] + dp[i - 1][1]) % mod;
        lastA = nowA, lastB = nowB;
    }
    cout << (dp[n][0] + dp[n][1]) % mod << '\n';
}

其实只有两个的话完全可以用两个变量来存，使空间复杂度降低很多

E. Find Permutation

题意

给定 个点以及 组可重复的大小关系 $Ai, B_i，构建一个排列p，对于所有条件，均满足p{Ai} < p{B_i}$。输出是否能唯一确定这个排列，若能唯一确定，输出这个排列。

思路

首先，我们可以一眼看出这是求拓扑序。那么，这道题唯一的障碍就是怎么排除无法唯一确定的点，因为如果成环了，拓扑排序会自动找出。

那么，我们来考虑每次读取队列的时候的情况：

考虑到拓扑排序的算法，我们会将每次遍历的时候，将入度为 的点全都放入队列，那么只要出现多个入度为 的点，那么就一定会出现如 的情况，此时直接判 即可。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f, mod = 998244353;

int n, m;
vector<int> G[N];
int in[N];  // 存储每个结点的入度

void topSort() {
    vector<int> L;
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (in[i] == 0) q.push(i);
    if(q.size() > 1){
        cout << "No\n";
        return;
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        L.push_back(u);
        for (auto v : G[u]) {
            if (--in[v] == 0) {
                q.push(v);
            }
        }
        if(q.size() > 1) {
            cout << "No\n";
            return;
        }
    }
    if (L.size() == n) {
        cout << "Yes\n";
        vector<int> ans(n);
        for(int i=0;i<n;i++){
            ans[L[i] - 1] = i + 1;
        }
        for (auto i : ans) cout << i << ' ';
    } else {
        cout << "No\n";
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m;
    map<pii, bool> mp;
    for(int i=0;i<m;i++){
        int x, y;
        cin >> x >> y;
        if(mp[{x, y}]) continue;
        G[x].emplace_back(y);
        in[y] ++;
        mp[{x, y}] = true;
    }
    topSort();
}

有一说一，为什么入读和出度的配对不可以用来判呢？

F. Teleporter and Closed off

题意

给定 个长度为 的字符串 ，若 ，那么可以使用这个传送点，从第 个城市传送到第 个城市。输出对于第 个城市，从第一个城市到最后一个城市，满足跳过这个城市的路径使用的传送点的最少数量。

思路

首先，对于第 个城市，它的状态是从前一个传送点推过来的，存在递推性，所以我们可以用 来实现。

对于第 个城市，若要跳过它，那么我们一定得从 个城市传送到 个城市，所以我们可以枚举 ，找出对于所有城市 前面用了多少传送点，城市 后面用了多少传送点，最后的答案即为传送点数量之和 。

那么，我们可以从前往后 ，再从后往前 ，最后的值即为 。

而对于 ，从前向后的时候，对于第 个城市，我们可以枚举所有 ，那么我们可以传送到所有满足条件的 个城市。因而，这些城市的传送点数量即可用当前城市来更新。

从后往前是类似的。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 4e5 + 10, inf = 0x3f3f3f3f, mod = 998244353;

int dp[N][2];
string a[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for(int i=0;i<n;i++)cin >> a[i];
    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = dp[n - 1][1] = 0;
    for(int i=0;i<n;i++){
        for(int j=1;j<=min(m, n - i);j++){
            if(a[i][j - 1] == '1') dp[i + j][0] = min(dp[i + j][0], dp[i][0] + 1);
        }
    }
    for(int i=n-1;i>=0;i--){
        for(int j=1;j<=min(m, i - 1);j++){
            if(a[i - j][j - 1] == '1') dp[i - j][1] = min(dp[i - j][1], dp[i][1] + 1);
        }
    }
    for(int k=1;k<n-1;k++){
        int ans = inf;
        for(int i=max(k - m + 1, 0ll);i<k;i++){
            for(int j=k+1;j<min(n, i+m+1);j++){
                if(a[i][j - i - 1] == '1') ans = min(ans, dp[i][0] + dp[j][1] + 1);
            }
        }
        cout << (ans >= inf ? -1 : ans) << ' ';
    }
}

dp老写错状态，淦