AtCoder ABC402 A~D 题解

A - CBC

题目大意

给点字符串 $S$，输出其中所有大写字母。

思路

根据题意模拟即可。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;int main()
{string s;cin >> s;for (int i = 0; i < s.size(); i++)if ('A' <= s[i] && s[i] <= 'Z')cout << s[i];return 0;
}

B - Restaurant Queue

题目大意

一些人排队，初始队列为空，$Q$ 次操作，每一次新增一个人或者输出队列第一个人的数字并移除。

思路

显然可以使用 std::queue，根据题意模拟即可。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;queue<int> q;
int Q;int main()
{cin >> Q;while (Q--){int op;cin >> op;if (op == 1){int x;cin >> x;q.push(x);}else{cout << q.front() << endl;q.pop();}}return 0;
}

C - Dislike Foods

题目大意

有 $N$ 种原料和 $M$ 种 食物，第 $i$ 种食物由 $K_i$ 种原料组成，分别是 $A_{i,1},A_{i,2},\dots ,A_{i,K_i}$。刚开始，Snuke 不喜欢任何原料。第 $i$ 天，他接受了第 $B_i$ 种原料，且只能吃仅由 $B_1,B_2,\dots ,B_i$ 组成的食物。问每一天他能吃多少个食物。

思路

发现数据范围很大，而且第 $i-1$ 天 Snuke 能吃的食物在第 $i$ 天的时候也可以吃。这个单调性起到了至关重要的作用，我们不必重复枚举，每一次只需要考虑包含 $B_i$ 的食物能否使用即可。可以使用数组维护每一种食物的原料有多少个可以吃，当原料个数与数组值相等的时候，这个食物可以食用。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;int n, m, ans;
vector<int> a[300010];
vector<int> v[300010];
int b[300010];
int k[300010];
int c[300010];int main()
{cin >> n >> m;for (int i = 1; i <= m; i++){cin >> k[i];a[i].push_back(0);for (int j = 1; j <= k[i]; j++){int aa; cin >> aa;a[i].push_back(aa);v[aa].push_back(i);}sort(a[i].begin(), a[i].end());}for (int i = 1; i <= n; i++)cin >> b[i];for (int i = 1; i <= n; i++){for (int j = 0; j < v[b[i]].size(); j++){c[v[b[i]][j]]++;if (c[v[b[i]][j]] == k[v[b[i]][j]])ans++;}cout << ans << endl;}return 0;
}

D - Line Crossing

题目大意

有 $N$ 个点均匀分布在圆周上，它们之间连了 $M$ 条线，求这 $M$ 条线中有多少对是交叉的。

思路

直接求交叉不容易，我们不妨先求出来平行的有多少对，再用总对数减去求出答案。观察题中的图片可以发现，部分平行线 $AB$ 和 $CD$ 满足 $A+B=C+D$，而另外一种情况是由循环问题导致的。在 $8$ 个点的时候，两端分别是 $1$、$2$ 的直线与两端分别是 $4,7$ 的直线平行。所以，我们将等式完善一下：$A+B$ 对 $N$ 取模的结果等于 $C+D$ 对 $N$ 取模的结果。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;int n, m;
int cnt[2000010];struct node
{int a, b;
} ;node p[300010];int main()
{cin >> n >> m;for (int i = 1; i <= m; i++){cin >> p[i].a >> p[i].b;cnt[(p[i].a + p[i].b) % n]++;}long long ans = 1LL * m * (m - 1);for (int i = 0; i < n; i++)ans -= 1LL * cnt[i] * (cnt[i] - 1);ans /= 2;cout << ans << endl;return 0;
}