数鸭子

问题描述

湖边有一群鸭子，每一只鸭子都不⼀样，或羽毛不同，或性格不同。TT在脑子里开了一个 map<鸭子，整数>
tong，把鸭⼦变成了一些数字。现在他好奇，有多少只鸭子映射成的数的数位中不同的数字个数小于 k 。

Input

输⼊第一行包含两个数 n, k，表示鸭子的个数和题目要求的 k。
接下来一行有 n 个数 ai，每个数表示鸭子被TT映射之后的值。
n ≤ 1e6，k ≤ 1e6，ai ≤ 1e15。

Output

输出一行，一个数，表示满足题目描述的鸭子的个数。
无行末空格

Sample

Input: 
6 5
123456789 9876543210 233 666 1 114514

Output: 
4

Limitation

Time limit      1000 ms
Memory limit    262144 kb

解题思路

就是求一堆数串中有多少个数串的不同数字个数小于 k，比如12345，其值为5；11111，其值为 1。

然而题目数据 k 可以大于 10，一共就 0..9 九个数字，出个 k > 10 的意义在哪，k > 10 的话不是都不用求直接输出 n 吗……搞得我开始想多了，还好最后几分钟没改，真的是想多了。

把输入的数当成字符串处理，数据范围用 long long。

源代码

#include <iostream>
#include <string>
using namespace std;

bool solve(string a, long long k) {
	bool reach[10] = { false };
	int count = 0;
	for (unsigned long long i = 0; i != a.length(); i++) {
		if (!reach[a[i] - '0']) {
			reach[a[i] - '0'] = true;
			count++;
		}
		if (count >= k)
			return false;
	}
	return true;
}

int main() {
	long long n, k;
	cin >> n >> k;
	long long count = 0;
	for (long long i = 0; i < n; i++) {
		string a;
		cin >> a;
		if (solve(a, k))
			count++;
	}
	cout << count << endl;

	return 0;
}