AtCoder Beginner Contest 194 A~E题解

ABC194 A~E

• [A - I Scream](https://atcoder.jp/contests/abc194/tasks/abc194_a)
• • 题目大意
  • 输入格式
  • 输出格式
  • 样例
  • 分析
  • 代码
• [B - Job Assignment](https://atcoder.jp/contests/abc194/tasks/abc194_b)
• • 题目大意
  • 输入格式
  • 输出格式
  • 样例
  • 分析
  • 代码
• [C - Squared Error](https://atcoder.jp/contests/abc194/tasks/abc194_c)
• • 题目大意
  • 输入格式
  • 输出格式
  • 样例
  • • 样例输入1
    • 样例输出1
    • 样例输入2
    • 样例输出2
  • 分析
  • 代码
• [D - Journey](https://atcoder.jp/contests/abc194/tasks/abc194_d)
• • 题目大意
  • 输入格式
  • 输出格式
  • 样例
  • 分析
  • 代码
• [E - Mex Min](https://atcoder.jp/contests/abc194/tasks/abc194_e)
• • 题目大意
  • 样例
  • 分析
  • 代码

A - I Scream

题目大意

在日本，有如下四种冰淇淋产品：

• 至少有$15\%$的milk solids和$8\%$的milk fat的产品称为“冰淇淋”；
• 至少有$10\%$的milk solids和$3\%$的milk fat且不是冰淇淋的产品称为“冰奶”；
• 至少有$3\%$的milk solids且不是冰淇淋或冰奶**的产品称为“乳冰”；
• 不是以上三种的产品称为“调味冰”。

在这里，milk solids由milk fat和milk solids-not-fat组成。
有一种冰淇淋产品，它由$A\%$的milk solids-not-fat和$B\%$的milk fat组成。
这种产品是上述的哪一类？

$0\le A,B\le 100$
$0\le A+B\le 100$

输入格式

$AB$

输出格式

请按如下格式输出类别：

• 如果这是冰淇淋，输出$1$；
• 如果这是冰奶，输出$2$；
• 如果这是乳冰，输出$3$；
• 如果这是调味冰，输出$4$。

样例

分析

只需将$A$加上$B$（变为milk solids的占比），再按题目所说的判断即可。

代码

#include 
using namespace std;int main()
{int a, b;scanf("%d%d", &a, &b);a += b;if(a >= 15 && b >= 8) puts("1");else if(a >= 10 && b >= 3) puts("2");else if(a >= 3) puts("3");else puts("4");return 0;
}

B - Job Assignment

题目大意

你的公司有$N$位员工，他们叫员工$1$，员工$2$，……，员工$N$。
你有两份重要工作要完成——工作A和工作B。
员工$i$可以在 A i A_i Ai​分钟内完成工作A并在 B i B_i Bi​分钟内完成工作B。
你要将两个工作分别分给某一位员工。
假设工作A分给了员工$i$，工作B分给了员工$j$，将要花的分钟数设为$t$，则：
t = { A i + B i ( i = j ) max ⁡ { A i , B j } ( i ≠ j ) t= \begin{cases} A_i+B_i & (i=j) \\ \max\{A_i,B_j\} & (i\ne j) \\ \end{cases} t={Ai​+Bi​max{Ai​,Bj​}​(i=j)(i=j)​
求最小的$t$。

$2\le N\le 1000$
1 ≤ A i , B i ≤ 1 0 5 1\le A_i,B_i\le 10^5 1≤Ai​,Bi​≤105

输入格式

$N$
A 1 B 1 A_1~B_1 A1​ B1​
A 2 B 2 A_2~B_2 A2​ B2​
$⋮$
A N B N A_N~B_N AN​ BN​

输出格式

输出答案。

样例

略，请自行前往AtCoder查看

分析

这题由于$N$最大只有 1 0 3 10^3 103，所以枚举是完全可行的，只要枚举所有的$(i,j)$，再根据题目里的公式求出答案取最小值即可，这样做总时间复杂度为 O ( n 2 ) \mathcal O(n^2) O(n2)。
另外，本题也有贪心的$\mathcal{O}(n)$的算法，但是情况太多，代码太麻烦，所以这里不写。

代码

#include 
#define maxn 1005
#define INF 2147483647
using namespace std;int a[maxn], b[maxn];inline void setmin(int& x, int y) { if(y < x) x = y; }
inline int max(int x, int y) { return x > y ? x : y; }int main()
{int n;scanf("%d", &n);for(int i=0; i<n; i++)scanf("%d%d", a + i, b + i);int ans = INF;for(int i=0; i<n; i++){setmin(ans, a[i] + b[i]); // i == jfor(int j=i+1; j<n; j++){setmin(ans, max(a[i], b[j]));setmin(ans, max(a[j], b[i]));}}printf("%d\n", ans);return 0;
}

C - Squared Error

题目大意

给你一个长度为$N$的序列$A$。
输出 ∑ i = 2 N ∑ j = 1 i − 1 ( A i − A j ) 2 \displaystyle \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2 i=2∑N​j=1∑i−1​(Ai​−Aj​)2。

2 ≤ N ≤ 3 × 1 0 5 2 \le N \le 3 \times 10^5 2≤N≤3×105
∣ A i ∣ ≤ 200 |A_i| \le 200 ∣Ai​∣≤200

输入格式

$N$
A 1 A 2 A 3 … A N A_1~A_2~A_3~\dots~A_N A1​ A2​ A3​ … AN​

输出格式

输出一行，即 ∑ i = 2 N ∑ j = 1 i − 1 ( A i − A j ) 2 \displaystyle \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2 i=2∑N​j=1∑i−1​(Ai​−Aj​)2。

样例

样例输入1

3
2 8 4

样例输出1

56

通过计算，我们得到 ∑ i = 2 N ∑ j = 1 i − 1 ( A i − A j ) 2 = ( 8 − 2 ) 2 + ( 4 − 2 ) 2 + ( 4 − 8 ) 2 = 56 \displaystyle \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2 = (8 - 2)^2 + (4 - 2) ^ 2 + (4 - 8) ^ 2 = 56 i=2∑N​j=1∑i−1​(Ai​−Aj​)2=(8−2)2+(4−2)2+(4−8)2=56。

样例输入2

5
-5 8 9 -4 -3

样例输出2

950

分析

根据公式 ( a − b ) 2 = a 2 + b 2 − 2 a b (a-b)^2=a^2+b^2-2ab (a−b)2=a2+b2−2ab，我们可以使用如下推理：
∑ i = 2 N ∑ j = 1 i − 1 ( A i − A j ) 2 \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2 i=2∑N​j=1∑i−1​(Ai​−Aj​)2
∑ i = 2 N ∑ j = 1 i − 1 A i 2 + A j 2 − 2 A i A j \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} {A_i}^2+{A_j}^2-2A_iA_j i=2∑N​j=1∑i−1​Ai​2+Aj​2−2Ai​Aj​
( ∑ i = 2 N ∑ j = 1 i − 1 A i 2 ) + ( ∑ i = 2 N ∑ j = 1 i − 1 A j 2 ) − ( ∑ i = 2 N ∑ j = 1 i − 1 2 A i A j ) (\sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} {A_i}^2)+(\sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} {A_j}^2)-(\sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} 2A_iA_j) (i=2∑N​j=1∑i−1​Ai​2)+(i=2∑N​j=1∑i−1​Aj​2)−(i=2∑N​j=1∑i−1​2Ai​Aj​)
这时，我们设 S i = ∑ j = 1 i − 1 A i S_i=\sum\limits_{j=1}^{i-1} A_i Si​=j=1∑i−1​Ai​，则：
( n − 1 ) ( ∑ i = 1 N A i 2 ) − 2 ( ∑ i = 1 N S i A i ) (n-1)(\sum_{i = 1}^{N} {A_i}^2)-2(\sum_{i = 1}^{N} S_iA_i) (n−1)(i=1∑N​Ai​2)−2(i=1∑N​Si​Ai​)
这时，计算所有 S i S_i Si​的时间复杂度为$\mathcal{O}(n)$，求最终结果的时间复杂度也是$\mathcal{O}(n)$，所以总时间复杂度为$\mathcal{O}(n)$。

代码

#include 
#define maxn 300005
using namespace std;using LL = long long;int main()
{int n, s1 = 0;scanf("%d", &n);LL s2 = 0, m = 0LL;for(int i=0; i<n; i++){LL x;scanf("%lld", &x);m += x * s1;s1 += x, s2 += x * x;}m <<= 1LL, s2 *= n - 1LL;printf("%lld\n", s2 - m);return 0;
}

D - Journey

题目大意

我们有一个$N$个顶点（称为顶点$1$、顶点$2$、……、顶点$N$）。
目前，这个图没有任何边。
Takahashi会重复执行以下操作，直到这个图变为连通图：

• 从这$N$个顶点中随机选一个顶点。每个顶点被抽中的概率相等，即 1 N \frac 1 N N1​。
• 在现在站着的点和选中的顶点之间添加一条边，并走到这个点上。

求Takahashi执行操作次数的期望值。

输入格式

$N$

输出格式

输出答案，最大允许浮点数误差 1 0 − 6 10^{-6} 10−6。

样例

分析

通过dp分析，我们可以得到 ∑ i = 1 n − 1 N i \sum\limits_{i=1}^{n-1}\frac Ni i=1∑n−1​iN​这个公式。这时，就可以写代码了。

代码

#include 
using namespace std;int main()
{int n;scanf("%d", &n);double res = 0;for(int i=1; i<n; i++)res += double(n) / i;printf("%.8lf\n", res);return 0;
}

E - Mex Min

题目大意

我们定义 m e x ( x 1 , x 2 , x 3 , … , x k ) \mathrm{mex}(x_1, x_2, x_3, \dots, x_k) mex(x1​,x2​,x3​,…,xk​)为最小的不出现在 x 1 , x 2 , x 3 , … , x k x_1, x_2, x_3, \dots, x_k x1​,x2​,x3​,…,xk​中的自然数。
给你一个长度为$N$的序列$A$： ( A 1 , A 2 , A 3 , … , A N ) (A_1, A_2, A_3, \dots, A_N) (A1​,A2​,A3​,…,AN​)。
对于每个$0\le i\le N-M$的整数$i$，我们计算 m e x ( A i + 1 , A i + 2 , A i + 3 , … , A i + M ) \mathrm{mex}(A_{i + 1}, A_{i + 2}, A_{i + 3}, \dots, A_{i + M}) mex(Ai+1​,Ai+2​,Ai+3​,…,Ai+M​)。输出这些$N-M+1$个结果中的最小值。

样例

略，请自行前往AtCoder查看

分析

先用最基本的方法想一下这道题，要求 m e x ( x 1 , x 2 , x 3 , … , x k ) \mathrm{mex}(x_1, x_2, x_3, \dots, x_k) mex(x1​,x2​,x3​,…,xk​)，只需记录每个 x i x_i xi​的出现次数，放进数组$\text{cnt}$里（ cnt i = i \text{cnt}_i=i cnti​=i在$x$中出现的次数）。这时，只要找到$\text{cnt}$中第一个$0$即可，这样计算$\mathrm{mex}$的时间复杂度为$\mathcal{O}(k)$。我们还可以想到一种优化方法，就是每一次计算 m e x ( A i + 1 , A i + 2 , A i + 3 , … , A i + M ) \mathrm{mex}(A_{i + 1}, A_{i + 2}, A_{i + 3}, \dots, A_{i + M}) mex(Ai+1​,Ai+2​,Ai+3​,…,Ai+M​)（$1\le i\le N-M$）时，将 cnt A i \text{cnt}_{A_i} cntAi​​减少$1$，并且将 cnt A i + M \text{cnt}_{A_{i+M}} cntAi+M​​增加$1$，这样就达到了$\mathcal{O}(1)$计算$\text{cnt}$的效果。但是，即使这样还会TLE。所以，我们可以用一个set维护$\text{cnt}$中所有$0$的位置，这样总时间复杂度就能降至$\mathcal{O}(N\log M)$。

代码

这里注意，set中一定要添加$N$！

#include 
#include 
#define maxn 1500005
using namespace std;int cnt[maxn], a[maxn];set<int> s;inline void setmin(int& x, int y)
{if(y < x) x = y;
}int main()
{int n, m;scanf("%d%d", &n, &m);for(int i=0; i<n; i++)scanf("%d", a + i);for(int i=0; i<m; i++)cnt[a[i]] ++;for(int i=0; i<n; i++)if(cnt[i] == 0)s.insert(i);s.insert(n);int ans = *s.begin();n -= m;for(int i=0; i<n; i++){if(cnt[a[i + m]]++ == 0) s.erase(a[i + m]);if(--cnt[a[i]] == 0) s.insert(a[i]);setmin(ans, *s.begin());}printf("%d\n", ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！