2021-2022-2 ACM集训队每周程序设计竞赛（12） - 问题 D: 衔尾之蚯蚓 - 题解

从不大于 N N N 的正整数中取出两个数 A A A 和 B B B。
当 A A A 和 B B B以 10 10 10 为基数，并且没有前导零时，如果 A A A 的最后一位数字等于 B B B 的第一位数字， A A A 的第一位数字等于 B B B 的最后一位数字。

请计算合法数对的数量。

这道题我看了一些人的代码，可能是有些想复杂了。

题意是所有符合条件的数对，而条件相当于中的两个数，其实只需要关注它们的第一位和最后一位，然后就有些人开始讨论中间应该怎样去填，是否会超 N N N 之类的……
其实大可不易，因为一共只有 N N N 个数，我们只需要将这N个数按照它们的第一位与最后一位进行分类，最后就是一个简单的 9 ∗ 9 9*9 9∗9 运算。

时间复杂度： O （ n ） O（n） O（n）

#include 
using namespace std;
int n;
int d[11][11];

int main() {

	cin >> n;

	for (int i = 1; i <= n; i++)
		d[to_string(i)[0] - '0'][i % 10]++;

	int res = 0;
	for (int i = 1; i <= 9; i++)
		for (int j = 1; j <= 9; j++)
			res += d[i][j] * d[j][i];

	cout << res;

	return 0;
}