Atcoder ABC403游记

Atcoder ABC399游记（A~D）

66 这回D和上回不同，不是余数性质了

A. Odd Position Sum

题目描述

给你一个整数序列，对于所有$i$满足$1 \leq 2*i+1 \leq N$，计算$A_i$的和。

思路

水

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            ans += a[i];
        }
    }
    cout << ans;
    return 0;
}

B.Four Hidden

题目描述

给你一个字符串$T$，由小写英文字母和?组成，以及由小写英文字母组成的字符串$U$。

字符串$T$是通过取一个仅小写的字符串$S$，并用?恰好替换其中的四个字符来获得的。

告诉我$S$是否可能包含$U$作为连续子字符串。

思路

水 等等怎么挂了两发

杂乱的代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s, t;
    cin >> s >> t;
    for (int i = 0; i + t.length() - 1 < s.length(); i++) {
        bool check = 1;
        for (int j = 0; j < t.length(); j++) {
            if (s[i + j] != t[j] && s[i + j] != '?') {
                check = 0;
                break;
            }
        }
        if (check == 1) {
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
    return 0;
}

C.403 Forbidden

问题陈述

某软件上上有 $N$ 个用户，编号从 $1$ 到 $N$ ，还有 $M$ 个页面，编号从 $1$ 到 $M$ 。最初，没有用户有查看任何竞赛页面的权限。

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

• 1 X Y：授予用户 $X$ 查看页面 $Y$ 的权限。

• 2 X：授予用户 $X$ 查看所有页面的权限。

• 3 X Y：回答用户 $X$ 是否可以查看页面 $Y$ 。

一个用户可能多次被授予同一页面的权限。

思路

map实现即可，最多多个是否是超级用户数组，水啊

有用bit做的？？？？？？？？？？？？？？？？？？？？

代码

#include<bits/stdc++.h>
using namespace std;
map<pair<int, int>, bool> mp;
bool vis[222222];
int main()
{
    int n, m;
    cin >> n >> m;
    int T;
    cin >> T;
    while (T--) {
        int ch;
        cin >> ch;
        if (ch == 1) {
            int x, y;
            cin >> x >> y;
            mp[{x, y}] = 1;
        } else if (ch == 2) {
            int x;
            cin >> x;
            vis[x] = 1;
        } else {
            int x, y;
            cin >> x >> y;
            cout << (vis[x] || mp[{x, y}] ? "Yes" : "No") << '\n';
        }
    }
    return 0;
}

D.Forbidden Difference

题目描述

给你一个长度为$N$的数组$A$和一个$D$，问你最少删除多少个元素，可以满足：

• 对于任意$1 \leq i,j \leq N$，满足$|A_i - A_j| \not= D$

思路

这个$D$最大到1e6。。。。

赛时想到其实可以取模$D$的完全剩余系，对于每个数都可以构成一条链，然后对这条链动态规划就行了！！！

具体怎么动态规划呢，我们首先设$M$为$A$中有多少种数模$D$的余数为当前的$r$。

然后$dp_i$就表示我们对于前$i$种可以最多不删的数的个数，所以要么选$i-2$加上当前数字个数，要么选$i-1$，因为根据题目的定义，留下来的不能相邻。

所以就简单了，但是还要特判D为0的情况！

不知道atc出多少次D题DP了

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n, d;
    cin >> n >> d;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int maxx = -1;
    for (int i = 0; i < n; i++) {
        maxx = max(maxx, a[i]);
    }
    vector<int> cnt(maxx + 1, 0);
    for (int i = 0; i < n; i++) {
        cnt[a[i]]++;
    }
    if(d == 0) {
        int ans = 0;
        for (int i = 0; i < cnt.size(); i++) {
            if(cnt[i] > 0) {
                ans++;
            }
        }
        cout << (n - ans);
        return 0;
    }
    int ans = 0;
    for(int r = 0; r < d; r++) {
        vector<int> lian;
        for (int x = r; x <= maxx; x += d) {
            lian.push_back(cnt[x]);
        }
        int m = lian.size();
        if(m == 0) {
            continue;
        }
        vector<int> dp(m, 0);
        dp[0] = lian[0];
        if(m > 1) {
            dp[1] = max(lian[0], lian[1]);
        }
        for(int i = 2; i < m; i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + lian[i]);
        }
        ans += dp[m - 1];
    }
    cout << (n - ans);
    return 0;
}