Atcoder Beginner Contest248

A.Lacked Number

思路：
  求出给出的字符串中缺少/(0/sim 9/)中的哪一个字符

	std::string s;
	std::cin >> s;
	std::vector<int> a(10);
	for (int i = 0; i < int(s.size()); i ++ ) a[s[i] - '0'] ++;
	int ans = 0;
	for (int i = 0; i < 10; i ++ ) if (!a[i]) ans = i;
	std::cout << ans << "/n";	

B.Slimes

思路：
  只要/(a < b/)就一直乘以/(k/)。

i64 a, b, k;
std::cin >> a >> b >> k;
int ans = 0;
while (a < b) {
	a *= k;
	ans ++;
}

std::cout << ans << "/n";

C.Dice Sum

思路：
  因为我们从第一个数开始选数的时候，只需要知道到最后的时候我们得到的和是多少就可以了，每一次都是从上一个状态递推到下一个状态的，所以可以选择用/(DP/)来求解。我们用/(dp[i][j]/)来表示枚举到第/(i/)个数的时候，所得到的和为/(j/)。状态转移方程为/(dp[i + 1][j + t] = dp[i + 1][j + t] + dp[i][j]/)， /(t/)表示的是此时这个数是/(1 /sim m/)之间的某个数。

	int n, m, k;
	std::cin >> n >> m >> k;

	std::vector<std::vector<Z>> dp(n + 1, std::vector<Z> (k + m + 1));
	dp[0][0] = 1;
	for (int i = 0; i < n; i ++ ) {
		for (int j = 0; j <= k; j ++ ) {
			for (int t = 1; t <= m; t ++ )
				dp[i + 1][j + t] = dp[i + 1][j + t] + dp[i][j]; 
		}
	}

	Z ans = 0;
	for (int i = 0; i <= k; i ++ ) ans += dp[n][i];
	std::cout << ans.val() << "/n";

D. Range Count Query

思路：
  只需要把给的序列中所有的数和它们的下标都记录下来，在/(Q/)次查询的时候，每一次都二分出在/([l,r]/)之间/(x/)出现的/([ll, rr]/)然后直接相减就好了

    int n; std::cin >> n;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i ++ ) std::cin >> a[i];
    int mx = *max_element(a.begin(), a.end());
    std::vector<int> v[mx + 1];
    for (int i = 1; i <= n; i ++ ) v[a[i]].push_back(i);
    int m; std::cin >> m;
    while (m -- ) {
        int l, r, x;
        std::cin >> l >> r >> x;
        int ans = 0;
        if (v[x].size() == 0 || x > mx) std::cout << "0/n";
        else {
            int ll = lower_bound(v[x].begin(), v[x].end(), l) - v[x].begin();
            int rr = upper_bound(v[x].begin(), v[x].end(), r) - v[x].begin();
            std::cout << rr - ll << "/n";
        }
    }