AtCoder Beginner Contest 342 （ABCDEFG题）视频讲解

A - Yay!

Problem Statement

You are given a string S S S consisting of lowercase English letters. The length of S S S is between 3 3 3 and 100 100 100, inclusive.

All characters but one of S S S are the same.

Find x x x such that the x x x-th character of S S S differs from all other characters.

Constraints

S S S is a string of length between 3 3 3 and 100 100 100, inclusive, consisting of two different lowercase English letters.

All characters but one of S S S are the same.

Input

The input is given from Standard Input in the following format:

S S S

Output

Print the answer.

Sample Input 1

yay

Sample Output 1

2

The second character of yay differs from the first and third characters.

Sample Input 2

egg

Sample Output 2

1

Sample Input 3

zzzzzwz

Sample Output 3

6

Solution

具体见文末视频。

---

Code

#include #define int long longusing namespace std;typedef pair PII;typedef long long LL;signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);string S;cin >> S;S = ' ' + S;unordered_map Cnt;for (int i = 1; i  X, P[X] = i;cin >> Q;while (Q --){int l, r;cin >> l >> r;if (P[l] > P[r]) cout if (P[x] != x) P[x] = Find(P[x]);return P[x];}signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cin  N  S;S = ' ' + S;for (int i = 0; i > Q;while (Q --){char a, b;cin >> a >> b;for (int i = 0; i  A[i], Cnt[A[i]] ++, mx = max(mx, A[i]);int Result = 0;for (int i = 1; i id = 0, id2 = 0;for (int j = 1; j fact[ ++ id] = j;if (i / j != j) fact[ ++ id] = i / j;}for (int j = 1; j fact[j] * fact[k], i * i / fact[j] / fact[k]};int T1 = 0, T2 = 0;for (int j = 1; j auto v = f2[j];if (v.first  mx || v.second  mx) continue;if (v.first == v.second && !Vis[v.first])T1 += Cnt[v.first] * max(0ll, Cnt[v.first] - 1) / 2, Vis[v.first] = Vis[v.second] = 1;else if (!Vis[v.first])T2 += Cnt[v.first] * Cnt[v.second], Vis[v.first] = Vis[v.second] = 1;}for (int j = 1; j auto v = f2[j];if (v.first  mx || v.second  mx) continue;Vis[v.first] = Vis[v.second] = 0;}Result += T1 + T2;}int Zero = 0;for (int i = 1; i if (A[i]) continue;Result += N - Zero - 1;Zero ++;}cout     for (int i = 2; i         if (!st[i]) primes[cnt ++ ] = i;        for (int j = 0; primes[j]             st[primes[j] * i] = true;            if (i % primes[j] == 0) break;        }    }}signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cin  N;get_primes(SIZE - 10);int Result = 0;for (int i = 1; i cin  A[i];if (!A[i]) continue;for (int j = 0; j > k >> c >> a >> b, add(b, a, {l, d, l + (k - 1) * d, c});Dijkstra(N);for (int i = 1; i  D;Build(1, 0, max(L + D - 1, N));f[0] = 1.0;Modify(1, 0, 1.0);for (int i = 1; i if (i = L) f[i] = Query(1, i - min(D, i), L - 1) / D;else f[i] = Query(1, i - min(i, D), i - 1) / D;Modify(1, i, f[i]);}for (int i = 0; i > L >> D;f[0] = 1.0, S[0] = 1.0;for (int i = 1; i if (i = L) f[i] = (S[L - 1] - (min(i, D) == i ? 0 : S[i - min(i, D) - 1])) / D;else f[i] = (S[i - 1] - (min(i, D) == i ? 0 : S[i - min(i, D) - 1])) / D;S[i] = S[i - 1] + f[i];}for (int i = 0; i  1, v = -1e18;if (Tree[u].Cnt.size()) v = Tree[u].Cnt.rbegin() -> first;if (mid >= x) return max(v, Query(u cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cin  N;for (int i = 1; i > A[i];Build(1, 1, N);cin >> Q;std::vector qry;qry.resize(Q + 1);int idx = 0;while (Q --){int op, l, r, x;cin >> op >> l;idx ++;if (op == 1)cin >> r >> x, Modify(1, l, r, x, 1), qry[idx] = {l, r, x};else if (op == 2)Modify(1, qry[l][0], qry[l][1], qry[l][2], 2);elsecout