比赛链接：Codeforces Round 937 (Div.4)
A. Stair, Peak, or Neither?
按照题目要求模拟即可。
时间复杂度： $O(1)$。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, a, b, c;
cin >> n;
while (n--)
{
cin >> a >> b >> c;
if (a < b && b < c)
printf("STAIR\n");
else if (a < b && b > c)
printf("PEAK\n");
else
printf("NONE\n");
}
return 0;
}
B. Upscaling
按照题目要求模拟即可。
时间复杂度： $O(n^2)$。
#include <bits/stdc++.h>
using namespace std;
int n, t;
inline int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
x = x * 10 + c - '0', c = getchar();
return x * f;
}
int main()
{
t = read();
while (t--)
{
n = read();
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if ((i + j) % 2 == 0)
printf("##");
else
printf("..");
}
printf("\n");
for (int j = 1; j <= n; j++)
{
if ((i + j) % 2 == 0)
printf("##");
else
printf("..");
}
printf("\n");
}
}
return 0;
}
C. Clock Conversion
按照题目要求将 $24$ 小时制转换为 $12$ 小时制。这种涉及时间的题目，输入输出的时候用，scanf 和 printf 会比较方便一点。
时间复杂度： $O(1)$。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int h, m;
char c;
scanf("%d:%d", &h, &m);
if (h < 12)
{
c = 'A';
if (h == 0)
h = 12;
}
else
{
c = 'P';
if (h != 12)
h -= 12;
}
printf("%02d:%02d %cM\n", h, m, c); // 如果小时或时间为一位数，在前面补零
}
return 0;
}
D. Product of Binary Decimals
由于小于的 binary decimal 数比较少，所以可以直接用 $a$ 数组列举出所有 binary decimal 数。然后再利用 dfs 判断给出数字能否由 binary decimals 数的乘积组成。
时间复杂度： $O(\log n)$。
#include <bits/stdc++.h>
using namespace std;
int t, n, flag;
int a[]={ 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111, 11000, 11001, 11010, 11011, 11100, 11101, 11110, 11111 };
inline int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
x = x * 10 +c - '0', c = getchar();
return x * f;
}
void dfs(int x)
{
if (x == 1 || flag == 1)
{
flag = 1;
return;
}
for (int i = 0; i < 30; i++)
if (x % a[i] == 0)
dfs(x / a[i]);
}
int main()
{
t = read();
while (t--)
{
n = read();
flag = 0;
dfs(n);
if (flag)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
E. Nearly Shortest Repeating Substring
- 从原字符串的头部和尾部分别枚举字符串 $k$，再去判断这个字符串 $k$ 能不能通过重复来组成字符串 $s$，使得最多有一个字符不同。
- 优化：只有当字符串 $k$ 的长度能够整除字符串 $s$ 长度 $n$ 的时候 $k$ 才有可能是组成 $s$ 的最短子串，所以只有当字符串 $k$ 的长度能够整除字符串 $s$ 长度 $n$ 的时候需要验证。
- 可能有人会问：为什么要分别从原字符串的头部和尾部分别枚举？不能只从一头枚举吗？
根据题目意思我们可以得出，如果头部或尾部的字符串 $k_1$，$k_2$ 可以通过重复组成字符串 $s$，那么 $k_1$，$k_2$可能存在一下几种情况：
- $k_1$ 和 $k_2$ 相等。当 $k_1$ 和 $k_2$ 相等的时候，只从一端进行枚举跟从两端进行枚举结果是一样的。
- $k_1$ 和 $k_2$ 相差一个字符。当 $k_1$ 和 $k_2$ 相差一个字符的时候，只从一端进行枚举结果可能会出现错误。例如样例里的字符串
hshahaha，从两端枚举的时候结果是 $2$，从一端枚举的结果是 $4$。这是因为hshahaha这个字符串的 $k$ =ha，而只从头枚举不可能出现这样的 $k$ 字符串。
时间复杂度： $O(n \sqrt n)$。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int t, n, ans;
string s1;
inline int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
x = x * 10 + c - '0', c = getchar();
return x * f;
}
int main()
{
t = read();
while (t--)
{
n = read();
ans = n;
cin >> s1;
for (int i = 1; i <= n / 2; i++)
{
if (n % i != 0)
continue;
string s2 = s1.substr(0, i);
int flag = 0;
for (int j = 0, k = 0; j < n; j++, k = (k + 1) % i)
{
if (s1[j] != s2[k])
flag++;
if (flag > 1)
break;
}
if (flag <= 1)
ans = min(ans, i);
s2 = s1.substr(n - i, i), flag = 0;
for (int j = 0, k = 0; j < n; j++, k = (k + 1) % i)
{
if (s1[j] != s2[k])
flag++;
if (flag > 1)
break;
}
if (flag <= 1)
ans = min(ans, i);
}
printf("%d\n", ans);
}
return 0;
}
F. 0, 1, 2, Tree!
先判断是否存在这样的树。设总结点数为 $n=a+b+c$，树的边数一定是 $n-1$；另一方面，所有结点的子结点数量之和为 $2a+b$，也等于边数。所以必须满足 $2a+b=a+b+c-1$。化简可得 $c=a+1$。
如果不满足这个条件，就不可能构造出这样的树，直接输出 $-1$。
接下来考虑最小高度。为了让树尽量矮，应该尽可能把有 $2$ 个子结点的结点放在靠上的层，因为它们可以更快地扩展出更多位置。
- 如果 $a=0$，说明没有分叉结点。此时根据 $c=a+1$ 可知只有一个叶子结点，剩下的 $b$ 个结点都只能形成一条链，所以最小高度就是 $b$。
- 如果 $b=0$，说明只有二叉分叉结点和叶子结点。最优做法是把 $a$ 个有 $2$ 个子结点的结点按层尽量填满，因此最小高度为 $\lfloor \log_2 a \rfloor+1$。
- 如果 $a>0$ 且 $b>0$，先按层放置有 $2$ 个子结点的结点。代码中的
num表示当前层最多能放多少个结点，依次为 $1,2,4,\dots$。当剩余的 $a$ 个二叉结点可以放进当前层时，说明二叉结点部分已经放完，此时高度为oup。- 当前层有
num个位置，但只用了 $a$ 个位置放二叉结点，所以还剩num - a个位置。这些位置可以放一子结点，并且不会增加当前最小高度，因此先用它们抵消一部分 $b$。 - 如果此时 $b \le 0$，说明所有一子结点都可以在不增加高度的情况下放完，答案就是
oup。 - 否则，剩下的一子结点只能继续往下接链。当前最深层可以继续向下延伸的位置数为
res = a + num，所以每增加一层，最多可以消耗res个一子结点。因此额外需要的高度是 $\left\lceil \frac{b}{res} \right\rceil$，代码中用(b + res - 1) / res实现向上取整。
- 当前层有
时间复杂度： $O(\log a)$。
#include <bits/stdc++.h>
using namespace std;
int t, a, b, c;
inline int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
x = x * 10 + c - '0', c = getchar();
return x * f;
}
int main()
{
t = read();
while (t--)
{
a = read(), b = read(), c = read();
if (c != a + 1)
printf("%d\n", -1);
else if (a == 0)
printf("%d\n", b);
else if (b == 0)
{
int oup = log2(a) + 1;
printf("%d\n", oup);
}
else
{
int num = 1, oup = log2(a) + 1, res;
while (1)
{
if (a <= num)
{
res = a + num;
b -= (num - a);
num *= 2;
break;
}
a -= num;
num *= 2;
}
if (b <= 0)
printf("%d\n", oup);
else
printf("%d\n", oup + (b + res - 1) / res);
}
}
return 0;
}