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\)
输入格式
\(A~B\)
输出格式
请按如下格式输出类别：
- 如果这是冰淇淋，输出\(1\)；
- 如果这是冰奶，输出\(2\)；
- 如果这是乳冰，输出\(3\)；
- 如果这是调味冰，输出\(4\)。
样例
| \(A\) | \(B\) | 输出 |
|---|---|---|
| \(10\) | \(8\) | \(1\) |
| \(1\) | \(2\) | \(3\) |
| \(0\) | \(0\) | \(4\) |
分析
只需将\(A\)加上\(B\)（变为milk solids的占比），再按题目所说的判断即可。
代码
#include <cstdio>
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并在\(B_i\)分钟内完成工作B。
你要将两个工作分别分给某一位员工。
假设工作A分给了员工\(i\)，工作B分给了员工\(j\)，将要花的分钟数设为\(t\)，则：
求最小的\(t\)。
\(2\le N\le 1000\)
\(1\le A_i,B_i\le 10^5\)
输入格式
\(N\)
\(A_1~B_1\)
\(A_2~B_2\)
\(\vdots\)
\(A_N~B_N\)
输出格式
输出答案。
样例
略，请自行前往AtCoder查看
分析
这题由于\(N\)最大只有\(10^3\)，所以枚举是完全可行的，只要枚举所有的\((i,j)\)，再根据题目里的公式求出答案取最小值即可，这样做总时间复杂度为\(\mathcal O(n^2)\)。
另外，本题也有贪心的\(\mathcal O(n)\)的算法，但是情况太多，代码太麻烦，所以这里不写。
代码
#include <cstdio>
#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 == j
for(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\)。
输出\(\displaystyle \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2\)。
\(2 \le N \le 3 \times 10^5\)
\(|A_i| \le 200\)
输入格式
\(N\)
\(A_1~A_2~A_3~\dots~A_N\)
输出格式
输出一行，即\(\displaystyle \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2\)。
样例
样例输入1
3
2 8 4
样例输出1
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\)。
样例输入2
5
-5 8 9 -4 -3
样例输出2
950
分析
根据公式\((a-b)^2=a^2+b^2-2ab\)，我们可以使用如下推理：
\[\sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2 \]\[\sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} {A_i}^2+{A_j}^2-2A_iA_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) \]这时，我们设\(S_i=\sum\limits_{j=1}^{i-1} A_i\)，则：
\[(n-1)(\sum_{i = 1}^{N} {A_i}^2)-2(\sum_{i = 1}^{N} S_iA_i) \]这时，计算所有\(S_i\)的时间复杂度为\(\mathcal O(n)\)，求最终结果的时间复杂度也是\(\mathcal O(n)\)，所以总时间复杂度为\(\mathcal O(n)\)。
代码
#include <cstdio>
#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\)个顶点中随机选一个顶点。每个顶点被抽中的概率相等，即\(\frac 1 N\)。
- 在现在站着的点和选中的顶点之间添加一条边，并走到这个点上。
求Takahashi执行操作次数的期望值。
输入格式
\(N\)
输出格式
输出答案，最大允许浮点数误差\(10^{-6}\)。
样例
| \(N\) | 输出 |
|---|---|
| \(2\) | \(2\) |
| \(3\) | \(4.5\) |
分析
通过dp分析，我们可以得到\(\sum\limits_{i=1}^{n-1}\frac Ni\)这个公式。这时，就可以写代码了。
代码
#include <cstdio>
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
题目大意
我们定义\(\mathrm{mex}(x_1, x_2, x_3, \dots, x_k)\)为最小的不出现在\(x_1, x_2, x_3, \dots, x_k\)中的自然数。
给你一个长度为\(N\)的序列\(A\)：\((A_1, A_2, A_3, \dots, A_N)\)。
对于每个\(0\le i\le N-M\)的整数\(i\)，我们计算\(\mathrm{mex}(A_{i + 1}, A_{i + 2}, A_{i + 3}, \dots, A_{i + M})\)。输出这些\(N-M+1\)个结果中的最小值。
样例
略，请自行前往AtCoder查看
分析
先用最基本的方法想一下这道题，要求\(\mathrm{mex}(x_1, x_2, x_3, \dots, x_k)\)，只需记录每个\(x_i\)的出现次数，放进数组\(\text{cnt}\)里（\(\text{cnt}_i=i\)在\(x\)中出现的次数）。这时，只要找到\(\text{cnt}\)中第一个\(0\)即可，这样计算\(\mathrm{mex}\)的时间复杂度为\(\mathcal O(k)\)。我们还可以想到一种优化方法，就是每一次计算\(\mathrm{mex}(A_{i + 1}, A_{i + 2}, A_{i + 3}, \dots, A_{i + M})\)（\(1\le i\le N-M\)）时，将\(\text{cnt}_{A_i}\)减少\(1\)，并且将\(\text{cnt}_{A_{i+M}}\)增加\(1\)，这样就达到了\(\mathcal O(1)\)计算\(\text{cnt}\)的效果。但是，即使这样还会TLE。所以，我们可以用一个set维护\(\text{cnt}\)中所有\(0\)的位置，这样总时间复杂度就能降至\(\mathcal O(N\log M)\)。
代码
这里注意，set中一定要添加\(N\)！
#include <cstdio>
#include <set>
#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;
}