A - Last Two Digits
题目大意
给定正整数\(N\)，求\(N\)的后两位。
\(100\le N\le 999\)
输入格式
\(N\)
输出格式
输出\(N\)的后两位，注意输出可能有前导0。
样例
| \(N\) | 输出 |
|---|---|
| \(254\) | 54 |
| \(101\) | 01 |
分析
题目已经规定\(N\)是三位数，因此无需使用整数输入，直接将输入看成字符串，输出后两位即可。
代码
#include <cstdio>
using namespace std;
int main()
{
getchar();
putchar(getchar());
putchar(getchar());
return 0;
}
B - Practical Computing
题目大意
输出\(N\)个整数序列\(A_0,\dots,A_{N-1}\)。它们按如下定义：
- \(A_i\)的长为\(i+1\)。
- \(A_i\)的第\(j+1\)个元素记为\(a_{i,j}\)（\(0\le j\le i<N\)），即：
- 当\(j=0\)或\(j=i\)时，\(a_{i,j}=1\)；
- 否则，\(a_{i,j}=a_{i-1,j-1}+a_{i-1,j}\)。
\(1\le N\le 30\)
输入格式
\(N\)
输出格式
输出\(N\)行。第\(i\)行上有\(A_{i-1}\)中的\(i\)个数，用空格分隔。
样例
样例输入1
3
样例输出1
1
1 1
1 2 1
样例输入2
10
样例输出2
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
分析
其实不用读题，看一眼样例，是不是很眼熟？没错，就是著名的杨辉三角。
不知道也没关系（不过应该也没人不知道），直接按题目要求（\(i,j\)正序）依次计算即可。时间复杂度\(\mathcal O(n^2)\)，空间复杂度\(\mathcal O(n)\)或\(\mathcal O(n^2)\)。详见代码\(1,2\)。
继续考虑，杨辉三角中\(a_{i,j}=C_j^i\)，所以可以用\(\mathcal O(1)\)的空间计算，时间不变，代码待会补。
代码
- 代码\(1\)（普通方法+无优化+
cin/cout，\(7\text{ms}~3604\text{KB}\)）
时间：\(\mathcal O(n^2)\)
空间：\(\mathcal O(n^2)\)
难度：低#include <iostream> using namespace std; int arr[35][35]; int main() { int n; cin >> n; for (int i = 0; i < n; i++) { arr[i][0] = 1; arr[i][i] = 1; } for (int i = 2; i < n; i++) { for (int j = 1; j < i; j++) { arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j]; } } for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { cout << arr[i][j] << " "; } cout << endl; } return 0; } - 代码\(2\)（普通方法+滚动表+
scanf/printf，\(6\text{ms}~1656\text{KB}\)）
时间：\(\mathcal O(n^2)\)
空间：\(\mathcal O(n)\)
难度：中低#include <cstdio> using namespace std; int a[35]; int main() { int n; scanf("%d", &n); a[0] = 1, puts("1"); for(int i=1; i<n; i++) { putchar('1'); for(int j=i-1; j>0; j--) a[j] += a[j - 1]; for(int j=1; j<i; j++) printf(" %d", a[j]); a[i] = 1, puts(" 1"); } return 0; }
C - K Swap
题目大意
给定长度为\(N\)的序列\(A=(a_1,a_2,\dots,a_N)\)和整数\(K\)，你可以重复下列操作任意次：
- 选择整数\(1\le i\le N-K\)，交换\(a_i\)和\(a_{i+K}\)。
问：是否能通过上述操作将\(A\)按升序排列？
\(2\le N\le 2\times 10^5\)
\(1\le K\le N-1\)
\(1\le a_i\le 10^9\)
输入格式
\(N~K\)
\(a_1~\dots~a_N\)
输出格式
如果可以达到目标，输出Yes；否则，输出No。
样例
样例输入1
5 2
3 4 1 3 4
样例输出1
Yes
该样例中，\(A=(3,4,1,3,4),K=2\)。一种完成任务的操作如下：
- 交换\(a_1\)和\(a_3\)，此时\(A=(1,4,3,3,4)\)；
- 交换\(a_2\)和\(a_4\)，此时\(A=(1,3,3,4,4)\)，排序完成。
样例输入2
5 3
3 4 1 3 4
样例输出2
No
\(K=3\)，无法将\(A\)排序。
样例输入3
7 5
1 2 3 4 5 5 10
样例输出3
Yes
可以不进行操作。
分析
题目可以看成：在\(a_i,a_{K+i},a_{2K+i},\dots\)（\(1\le i<K\)）中的元素是可以两两相邻交换的。那么，根据冒泡排序的原理，这些元素是可以直接排序并放入原位置上的。此时，只需依次对于\(i=1,2,\dots,K-1\)的上述序列并排序、放回原位，最终检查是否已被排成升序即可。
代码
#include <cstdio>
#include <set>
#include <algorithm>
#define maxn 200005
using namespace std;
int a[maxn], b[maxn];
int main()
{
int n, k;
scanf("%d%d", &n, &k);
for(int i=0; i<n; i++)
{
scanf("%d", a + i);
b[i] = a[i];
}
sort(b, b + n);
for(int i=0; i<k; i++)
{
multiset<int> s1, s2;
for(int j=i; j<n; j+=k)
{
s1.insert(a[j]);
s2.insert(b[j]);
}
if(s1 != s2)
{
puts("No");
return 0;
}
}
puts("Yes");
return 0;
}
特别: 本题涉及到很多数组操作，使用Python代码量非常小（使用数组切片和sorted()），所以也是一道很好的Python数组练习题。因此，这里破例提供Python示例代码：
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k):
a[i::k] = sorted(a[i::k])
print('Yes' if a == sorted(a) else 'No')
D - Together Square
题目大意
给定整数\(N\)。求正整数对\((i,j)\)的个数，满足：
- \(1\le i,j\le N\)
- \(i\times j\)是一个完全平方数（即\(1^2,2^2,3^2,\dots\)）
\(1\le N\le 2\times 10^5\)
输入格式
\(N\)
输出格式
输出答案。
样例
| \(N\) | 输出 |
|---|---|
| \(4\) | \(6\) |
| \(254\) | \(896\) |
分析
注意\(N\)较大，所以最容易想到的\(\mathcal O(n^2)\)暴力枚举肯定是不行的，然后仔细思考后发现可以枚举整数对\((x,y)\)（\(1\le x,y\le\lfloor\sqrt N\rfloor\)），当\(x,y\)互质时将答案加上\(\frac N {\max\{x^2,y^2\}}\)，这样答案正确，建议读者自行思考原因。
时间复杂度计算：
- 循环（次数\(\sqrt N\)，枚举\(x\)）
- 循环（次数\(\sqrt N\)，枚举\(y\)）
gcd最大公约数算法（辗转相除法\(\log\max\{x,y\}\approx\log\sqrt N\)，判断互质）
- 循环（次数\(\sqrt N\)，枚举\(y\)）
综上，总时间复杂度为\(\mathcal O(\sqrt N\times\sqrt N\times\log\sqrt N)=\mathcal O(N\log\sqrt N)\)。
代码
#include <cstdio>
using namespace std;
inline int gcd(int a, int b)
{
while(b ^= a ^= b ^= a %= b);
return a;
}
int main()
{
int n = 0; char c;
while((c = getchar()) != '\n')
n = (n << 3) + (n << 1) + (c ^ 48);
int t = __builtin_sqrt(n);
long long ans = 0LL, x;
for(int i=1; i<=t; i++)
for(int j=i; j<=t; j++)
if(gcd(i, j) == 1)
{
ans += (x = n / (i > j? i * i: j * j));
if(i != j) ans += x;
}
printf("%lld\n", ans);
return 0;
}
E - Small d and k
题目大意
给定一个由\(N\)个点和\(M\)条边组成的简单无向图。
对于每个\(i=1,2,\dots,M\)，第\(i\)条边连接顶点\(a_i\)和\(b_i\)。
已知 每个顶点的度数不超过3，回答下列\(Q\)个查询，第\(i\)个查询为：
- 求与顶点\(x_i\)距离不超过\(k_i\)的点的下标之和。
\(1\le N,Q\le 1.5\times 10^5\)
\(0\le M\le \min\{\frac{N(N-1)}2,\frac32N\}\)
\(1\le a_i<b_i\le N\)，\((a_i,b_i)\)互不相同。
\(1\le x_i\le N\)，\(0\le k_i\le 3\)
输入格式
\(N~M\)
\(a_1~b_1\)
\(\vdots\)
\(a_M~b_M\)
\(Q\)
\(x_1~k_1\)
\(\vdots\)
\(x_Q~k_Q\)
输出格式
输出\(Q\)行。第\(i\)行应包含第\(i\)个查询的答案。
样例
样例输入
6 5
2 3
3 4
3 5
5 6
2 6
7
1 1
2 2
2 0
2 3
4 1
6 0
4 3
样例输出
1
20
2
20
7
6
20
样例解释：AtCoder 254E - Small d and k #sample
分析
注意这题数据范围，这是解体的关键：
- 减少算法耗时：
- \(0\le k\le 3\)
- 顶点度数\(~\le3\)
- 根据乘法原理，一次查询最大符合条件的顶点数为\(3^3+1=28\)个
- 防止常数问题：
- \(1\le N\le \textbf{1.5}\times 10^5\)
- 时间限制\(3.5\text{s}\)
因此，使用简单的暴力\(\text{BFS}\)正好符合题目数据范围。详见代码。
代码
注意dis数组的清零操作，无需全部清零，只需把刚刚改过的清零即可。
#include <cstdio>
#include <queue>
#define maxn 150005
using namespace std;
vector<int> G[maxn];
int dis[maxn];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
while(m--)
{
int a, b;
scanf("%d%d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
int Q; scanf("%d", &Q);
for(int i=1; i<=n; i++) dis[i] = -1;
while(Q--)
{
int x, k;
scanf("%d%d", &x, &k);
vector<int> ans;
queue<int> q;
q.push(x);
dis[x] = 0;
while(!q.empty())
{
int v = q.front(); q.pop();
int d = dis[v];
if(d <= k) ans.push_back(v);
if(++d > k) continue;
for(int u: G[v])
if(dis[u] == -1)
{
dis[u] = d;
q.push(u);
}
}
int res = 0;
for(int v: ans)
res += v, dis[v] = -1;
printf("%d\n", res);
}
return 0;
}