Codeforces Round #213(Div. 2) 不完全不正确题解

比赛地址：戳我

A. Good Number

关键：

Let's call a number k-good if it contains all digits not exceeding k (0, ..., k).

即，给出的数必须包括[0...k]所有数字。超出范围的数字忽略不计。

一个小坑。注意读题。

B. The Fibonacci Segment

找出给出数列的最长子列，使这个子列满足: a[i] + a[i + 1] == a[i + 2]。

同时，长度为1 或 2的子列均认为满足条件。

此题需要一个小小的证明，我不知道怎么表达。看代码就好，很简单的思路。

C. Matrix

一道中等题。

对于一个子矩阵来说，其和必须为: sum(a[i...j]) * sum(a[x...y])

所以我们用O(n^2)的时间复杂度枚举出s的所有子串和，以及所有子串和出现的次数。

如果 M = sum(a[i...j])， 同时cnt[M] = u;
则推出 N = a / M; //注：M为0的情况再讨论
得到cnt[N] = v;
则 ans += u * v;

当上述伪代码中的M为0时，如果a == 0，则N必须为所有子串和的种数。

如果a != 0，则N必为0。（因为0 * M == 0 != a)

被得0情况小坑了几次，之后把这题切掉了。

D. Free Market

其实这题算一道简单题。

因为题目中给出公式s(x) + d < s(y)。根据此式我们可以推出，无论我们拥有什么宝贝。下一轮交换的结果一定满足如下两个条件。

A[i + 1] > A[i];
A[i + 1] <= A[i] + d;

A[i]表示的是第i轮我们拥有的宝贝的总价值。

对于A[i]，我们可以用背包DP来求得其可能的值。

于是此题就转化为：背包DP + 一个while循环。可以归为简单题。但是有一点思路上的小弯。

E. Beautiful Set

TODO：此题不会，我需要一个证明。。。坐等题解。

A. Good Number

import sys

sys.stdin = open("input.txt")

(n, k) = map(int, raw_input().split())

res = 0

for i in xrange(n):
    s = map(int, raw_input())
    st = set()
    for item in s:
        if item > k:
            pass
        else:
            st.add(item)
    else:
        if len(st) == k + 1:
            res += 1
            #print s, 'yes'

print res

B. The Fibonacci Segment

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define print(x) cout << x << endl
#define input(x) cin >> x

const int SIZE = 100100;

int n;
int A[SIZE];

int judge(int &t)
{
    int st = t - 1 >= 0? t - 1: t;
    int res = 0;
    for (int i = 0; st + i < n; i++) {
        if (i >= 2 && 
                A[st + i - 1] + A[st + i - 2] == A[st + i]) {
            res = i + 1;
        } else if (i < 2) {
            res++;
            continue;
        } else {
            break;
        }
    }
    t = st + res;
    return res;
}

int main()
{
    freopen("input.txt", "r", stdin);
    while(input(n)) {
        for (int i = 0; i < n; i++) {
            input(A[i]);
        }
        int ans = 0;
        int t = 0;
        while (t < n) {
            int res = judge(t);
            //print(t);
            ans = max(ans, res);
        }

        print(ans);
    }
    return 0;
}

C. Matrix

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

#define print(x) cout << x << endl
#define input(x) cin >> x

typedef long long llint;

const int SIZE = 4444;

llint a;
int len;
char val[SIZE];
map<llint, int> mp;

int main()
{
    freopen("input.txt", "r", stdin);
    while (input(a)) {
        llint ans = 0;
        input(val);
        len = strlen(val);
        mp.clear();
        int sumall = 0;
        for (int i = 0; i < len; i++) {
            val[i] -= '0';
        }

        for (int i = 1; i <= len; i++) {
            llint t = 0;
            for (int j = 0; j < i; j++) {
                t += val[j];
            }
            mp[t]++;
            sumall++;
            for (int j = i; j < len; j++) {
                t -= val[j - i];
                t += val[j];
                mp[t]++;
                sumall++;
            }
        }
        for (map<llint, int>::iterator iter = mp.begin();
                iter != mp.end();
                ++iter) {
            llint x = iter -> first;
            int y = iter -> second;
            //print(x << ' ' << y);
            if (!x) {
                if (!a) {
                    ans += (llint)sumall * y;
                }
                continue;
            }
            if (a % x == 0) {
                int z = mp[a / x];
                ans += (llint)y * z;
            }
        }
        print(ans);
    }

    return 0;
}

D. Free Market

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define print(x) cout << x << endl
#define input(x) cin >> x

const int N = 55;
const int D = 10100;

char dp[N * D];
int n, d;
int A[N];

void do_package()
{
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = N * D - 1; j >= 0; j--) {
            if (dp[j] && j + A[i] < N * D) {
                dp[j + A[i]] = 1;
            }
        }
    }
}

void solve(int &val, int &day)
{
    val = day = 0;
    while (1) {
        bool flag = false;
        for (int i = val + d; i > val; i--) {
            if (dp[i]) {
                val = i;
                day++;
                flag = true;
                break;
            }
        }
        if (!flag) break;
    }
}


int main()
{
    freopen("input.txt", "r", stdin);
    while (input(n >> d)) {
        for (int i = 0; i < n; i++) {
            input(A[i]);
        }
        do_package();

        int a, b;
        solve(a, b);
        print(a << ' ' << b);
    }
    return 0;
}

E. Beautiful Set

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define print(x) cout << x << endl
#define input(x) cin >> x

const int prime[15] = {2, 3, 5, 7, 11,
                     13, 17, 19, 23, 29,
                     31, 37, 41, 43, 47};


int main()
{
    int n;
    input(n);
    vector<int> res;
    int limit = 2 * n * n;

    for (int i = 0; i < 15; i++) {
        res.clear();
        res.push_back(1);
        for (int j = 0; j <= i; j++) {
            int p = prime[j];
            int sz = res.size();
            for (int k = 0; k < sz; k++) {
                int x = res[k];
                while (x * p <= limit) {
                    x *= p;
                    res.push_back(x);
                }
            }
        }
        if (res.size() >= n) {
            break;
        }
    }
    sort(res.begin(), res.end(), greater<int>());
    for (int i = 0; i < n; i++) {
        if (i) printf(" ");
        printf("%d", res[i]);
    }
    puts("");
    return 0;
}