AtCoder 传送门

洛谷传送门

一眼。

将 \(a\) 中每个数用前导零补到 \(6\) 位，题目相当于问所有 \(i,j\)，\(a_i\) 的每一位加 \(a_j\) 的这一位都不超过 \(9\) 的 \((i,j)\) 对数。

直接高维前缀和统计即可，时间复杂度 \(O(n + 10^6)\)。

code 
/*

p_b_p_b txdy
AThousandSuns txdy
Wu_Ren txdy
Appleblue17 txdy

*/

#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 1000100;

int n, a[maxn], b[maxn][9], sum[10][10][10][10][10][10];

void solve() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		int x = a[i];
		for (int j = 0; j < 6; ++j) {
			b[i][j] = x % 10;
			x /= 10;
		}
		++sum[b[i][0]][b[i][1]][b[i][2]][b[i][3]][b[i][4]][b[i][5]];
	}
	for (int i = 0; i <= 9; ++i) {
		for (int j = 0; j <= 9; ++j) {
			for (int k = 0; k <= 9; ++k) {
				for (int l = 0; l <= 9; ++l) {
					for (int p = 0; p <= 9; ++p) {
						for (int q = 1; q <= 9; ++q) {
							sum[i][j][k][l][p][q] += sum[i][j][k][l][p][q - 1];
						}
					}
				}
			}
		}
	}
	for (int i = 0; i <= 9; ++i) {
		for (int j = 0; j <= 9; ++j) {
			for (int k = 0; k <= 9; ++k) {
				for (int l = 0; l <= 9; ++l) {
					for (int p = 1; p <= 9; ++p) {
						for (int q = 0; q <= 9; ++q) {
							sum[i][j][k][l][p][q] += sum[i][j][k][l][p - 1][q];
						}
					}
				}
			}
		}
	}
	for (int i = 0; i <= 9; ++i) {
		for (int j = 0; j <= 9; ++j) {
			for (int k = 0; k <= 9; ++k) {
				for (int l = 1; l <= 9; ++l) {
					for (int p = 0; p <= 9; ++p) {
						for (int q = 0; q <= 9; ++q) {
							sum[i][j][k][l][p][q] += sum[i][j][k][l - 1][p][q];
						}
					}
				}
			}
		}
	}
	for (int i = 0; i <= 9; ++i) {
		for (int j = 0; j <= 9; ++j) {
			for (int k = 1; k <= 9; ++k) {
				for (int l = 0; l <= 9; ++l) {
					for (int p = 0; p <= 9; ++p) {
						for (int q = 0; q <= 9; ++q) {
							sum[i][j][k][l][p][q] += sum[i][j][k - 1][l][p][q];
						}
					}
				}
			}
		}
	}
	for (int i = 0; i <= 9; ++i) {
		for (int j = 1; j <= 9; ++j) {
			for (int k = 0; k <= 9; ++k) {
				for (int l = 0; l <= 9; ++l) {
					for (int p = 0; p <= 9; ++p) {
						for (int q = 0; q <= 9; ++q) {
							sum[i][j][k][l][p][q] += sum[i][j - 1][k][l][p][q];
						}
					}
				}
			}
		}
	}
	for (int i = 1; i <= 9; ++i) {
		for (int j = 0; j <= 9; ++j) {
			for (int k = 0; k <= 9; ++k) {
				for (int l = 0; l <= 9; ++l) {
					for (int p = 0; p <= 9; ++p) {
						for (int q = 0; q <= 9; ++q) {
							sum[i][j][k][l][p][q] += sum[i - 1][j][k][l][p][q];
						}
					}
				}
			}
		}
	}
	ll ans = 0;
	for (int i = 1; i <= n; ++i) {
		ans += sum[9 - b[i][0]][9 - b[i][1]][9 - b[i][2]][9 - b[i][3]][9 - b[i][4]][9 - b[i][5]];
		bool flag = 1;
		for (int j = 0; j < 6; ++j) {
			if (b[i][j] > 9 - b[i][j]) {
				flag = 0;
				break;
			}
		}
		if (flag) {
			--ans;
		}
	}
	printf("%lld\n", ans >> 1);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

原文地址：http://www.cnblogs.com/zltzlt-blog/p/16852666.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性