倒立数对 题解

1.题目

题目链接

2.分析

数对形式是这样的：(A,,B) A=ab||A=acb B=ba||B=bca 影响两数是否能配对的只关乎到其最高位和最低位，而中位几乎可以忽略不记。联想到之前的统计区间，依旧是可以让之前枚举过的数字记录备用，且只用记录两位，之后倒过来调用。这样的话，我们只用枚举一个数，另一个数通过正在枚举的数的两位颠倒过来就可以查找到了。

3.代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int TOP=2e5+5;
int n;
int t[15][15];
int a[10]={1,10,100,1000,10000,100000,1000000};
int wei=1;
int ans;
signed main()
{
//	freopen("number.in","r",stdin);
//	freopen("number.out","w",stdout);
	int f;
	cin>>n;
	for(f=1;f<=n;f++)
	{
		if(f>=a[wei])
			wei++;
		if(f/a[wei-1]==f%10)
			ans++;
    //如果两位数相等，则有一位数可匹配
		ans+=t[f%10][f/a[wei-1]]*2;
		t[f/a[wei-1]][f%10]++;
	}
	cout<<ans;
	return 0;
}

总体实现就是通过一个表(a)，记录进位的最小数，且往后统计最高位是也能用上（打表真好用)。用一个二位数组t[f][k]，统计高位是f，低位是k的数的数量，就能求出当前数能配成多少对了。

-诚信做人，请勿抄袭-