347

A - Divisible

给你正整数 $N$ 和 $K$ ，以及长度为 $N$ , $A$ 序列。

提取 $A$ 中所有是 $K$ 倍数的元素，除以 $K$ ，并打印商。

void solve() {
    int n, k;cin >> n >> k;
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;if (x % k == 0)cout << x/k << " ";
    }
}

B - Substring

给你一个由小写英文字母组成的字符串 $S$ 。 $S$ 有多少个不同的非空子串？

子串是连续的子序列。

后缀数组扳题(还没学)

void solve() {
    string s;cin >> s;
    set<string> st;
    for (int i = 0;i < s.size();i++) {
        for (int j = i;j < s.size();j++) {
            st.insert(s.substr(i, j - i + 1));
        }
    }
    cout << st.size() << '\n';
}

C - Ideal Holidays

在 AtCoder 王国，一周由 $A + B$ 天组成，其中第一天至 $A$ 天为节假日，而 $(A + 1)$ 至 $(A + B)$ 天为工作日。

高桥有 $N$ 个计划， $i$ 个计划安排在 $D_{i}$ 天之后。

他忘记了今天是星期几。请判断他的 $N$ 个计划是否都安排在节假日。

if (*(max_element(ar.begin(), ar.end())) - *(min_element(ar.begin(), ar.end())) + 1 <= a)cout << "Yes\n";
else cout << "No\n";

上面的代码有一个特殊情况没考虑到：
hack 数据：

2 3 10
1 12

可以发现按照上面的代码答案是 No 实际上是可以的，只是需要将区间向右平移两个位置变为 3 1 即可。

void solve() {
    int n, a, b;cin >> n >> a >> b;vector <int> ar(n);
    for (int i = 0;i < n;i++) {
		cin >> ar[i]; ar[i] %= a + b;
    }
    sort(ar.begin(), ar.end());
    int ans = ar[n - 1] - ar[0] + 1;
    for (int i = 1;i <= n - 1;i++) {
        ans = min(ans, a + b - (ar[i] - ar[i - 1]) + 1);
    }
    if (ans <= a)cout << "Yes\n";
    else cout << "No\n";
}

D - Popcount and XOR

给你非负整数 $a$ ， $b$ 和 $C$ 。请判断是否有一对非负整数 $(X, Y)$ 满足以下五个条件。如果存在，请输出 $X, Y$ 。否则输出 -1

$0 \leq X, Y \leq 2^{60}$
$popcount (X) = a$
$popcount (Y) = b$
$X \oplus Y = C$

Solution

位运算/构造

#define int long long
void solve() {
    int a, b, c;cin >> a >> b >> c;
    bitset<60> A, B, C(c);
    int x = a + b - C.count();
    if (x & 1 || a < x / 2 || b < x / 2) {
        cout << "-1\n";return;
    }
    x /= 2;
    a -= x;b -= x;
    for (int i = 0;i <= 59;i++) {
        if (C[i]) { // if ((c & (1ll << i))) {
            if (a) {
                A[i] = 1;a--;
            } else if (b) {
                B[i] = 1;b--;
            }
        } else {
            if (x) {
                A[i] = 1;B[i] = 1;x--;
            }
        }
    }
    if (x || a || b) {
        cout << "-1\n";return;
    }
    if ((A.to_ullong() ^ B.to_ullong()) != c) {
        cout << "-1\n";return;
    }
    cout << A.to_ullong() << " " << B.to_ullong() << "\n";
}

E - Set Add Query

有一个长度为 $N$ 的整数序列 $A = (A_{1} \sim A_{N})$ ，其中所有元素的初始值都设为 $0$ 。此外，还有一个初始为空的集合 $S$ 。

依次执行以下 $Q$ 查询。在处理完所有 $Q$ 查询后，找出序列 $A$ 中每个元素的值。 $i$ -th 查询的格式如下：

给出一个整数 $x_{i}$ 。如果 $S$ 中包含整数 $x_{i}$ ，则从 $S$ 中删除 $x_{i}$ 。否则，在 $S$ 中插入 $x_{i}$ 。然后，如果 $j \in S$ 包含 $j = 1, 2, \dots, N$ ，则将 $| S |$ 添加到 $A_{j}$ 中。

求最终的 $A$ 数组

Solution

前缀和

const int N = 2e5 + 10;
vector<ll> g[N], a(N), sum(N), ans(N);
set<int> s;
void solve() {
    int n, q;cin >> n >> q;
    for (int i = 1;i <= q;i++) {
        cin >> a[i];
        g[a[i]].push_back(i);
    }
    set<int> s;
    for (int i = 1;i <= q;i++) {
        if (s.find(a[i]) == s.end()) {
            s.insert(a[i]);
        } else {
            s.erase(a[i]);
        }
        a[i] = s.size();
        sum[i] = sum[i - 1] + a[i];
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j < g[i].size();j += 2) {
            int r = g[i][j], l = g[i][j - 1];
            ans[i] += sum[r - 1] - sum[l - 1];
        }
        if (g[i].size() & 1) {
            ans[i] += sum[q] - sum[*g[i].rbegin() - 1];
        }
    }
    for (int i = 1;i <= n;i++)cout << ans[i] << " \n"[i == n];
}