indeed 第二次笔试题

1. Maximal Values

很简单，从前往后扫，找满足的，O（n）,很容易就过掉了。 maxn = 100. 没啥难点。

2. Bi-gram

用map统计个数，从前往后扫，每2个字符作为一个字符串，然后遍历map，存到vector里面，根据个数，字典序进行排序，也很简单。maxn = 100，不用考虑什么复杂的东西，没难度。

/*
ID: y1197771
PROG: test
LANG: C++
*/
#include<bits/stdc++.h>
#define pb push_back
#define FOR(i, n) for (int i = 0; i < (int)n; ++i)
#define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
typedef long long ll;
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e3 + 10;
struct node {
    string v;
    int s;
    bool operator<(const node & x) const {
        if(s == x.s) return v < x.v;
        return s > x.s;
    }
};
void solve() {
    string s;
    cin >> s;
    map<string, int> ma;
    for (int i = 0; i < s.size() - 1; i ++) {
        string cur = s.substr(i, 2);
        ma[cur]++;
    }
    vector<node> v;
    for (auto it : ma) {
        v.pb({it.first, it.second});
    }
    sort(v.begin(), v.end());
    for (auto i : v)
        cout << i.v << endl;

}
int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    solve();
    return 0;
}

3. Sequence Filpping

理解题意很重要，给出许多区间，可以对这些区间内的数字进行翻转，这些区间可以任意选取。考虑数据范围很小，maxn = 8, maxm = 8, 考虑子集加全排列，复杂度是 2^8 * 8! * 8 = 82 575 360,在2s的时限内可以跑完，更上次的题目套路差不多。

这道题我做的时候，还以为只是子集，没考虑区间翻转顺序，以及后续debug的时候，忘记还原a数组，浪费了一些时间，这些小点都需要仔细注意。

/*
ID: y1197771
PROG: test
LANG: C++
*/
#include<bits/stdc++.h>
#define pb push_back
#define FOR(i, n) for (int i = 0; i < (int)n; ++i)
#define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
typedef long long ll;
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e3 + 10;
int n, m;
int a[20];
int b[20];
vector<pii> range;
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int x, y;
    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        range.pb({x, y});
    }
    int res = 0;
    for (int i = 1; i <= n; i++)
        res += i * a[i];
    for (int i = 0; i < (1 << m); i++) {

        vector<int> p;
        for (int j = 0; j < m; j++) {
            if((1 << j) & i) {
                p.pb(j);
                //reverse(b + range[j].first, b + range[j].second + 1);
                //cout << range[j].first << " " << range[j].second << endl;
            }
        }
        sort(p.begin(), p.end());
        do {
            for (int j = 1; j <= n; j++) b[j] = a[j];
            for (int x = 0; x < p.size(); x++) {
                reverse(b + range[p[x]].first, b + range[p[x]].second + 1);
            }
            int s = 0;
            for (int j = 1; j <= n; j++) {
                s += j * b[j];
            //cout << b[j] << " ";
            }
            //cout <<endl;
            res = max(res, s);

        } while( next_permutation(p.begin(), p.end()));

    }
    cout << res << endl;
}
int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    solve();
    return 0;
}

4. Making a Number

题目描述很简单，一下就理解题意，然后我连例子都没仔细看，以为这不是状态dp么，记住过去的9个字母是什么，一步一步进行转移是什么不就完了，也没仔细考虑复杂度，然后结果肯定是失败的。应该先在纸上写清楚。大概算一下复杂度，还是太慌张，上来就想瞎码代码，这是错误的。

分析：分析例子，找规律，如果是状态转移dp，考虑一共的状态数是10！ = 3 628 800，这个数字很大，1e5 * 10!,在2s的时间限制内是不行的，仔细想想，当长度超过10的时候，每个字符转移就是固定的，也就是后面所有的数字都确定了，为了满足每10个字符都不一致，因为最多10个字符，这个条件限制的非常好，比如现在是0123456789，下次的数字一定是01234567890，以至于后面的长度都确定了，01234567890123456789，这样没10个10个都是一样的，这样一想，那么结果就很简单了。

1. 当单词长度小于等于10个的时候，先判断合法性，有重复的数字，直接返回10， 然后统计出现的字符个数为a，单词长度为L，问号的个数为b, 然后结果就是 (10 - a)! / ((10 - a) - b)!. 也就是 A(10 - a, b);

2. 当单词长度大于10的，就是给的样例二，1???????9?????????4?，每10个字符进行一次划分。就像下面这样：

1???????9?

????????4?

10个长度为一组，因为前10个确定以后，后面的就直接重复就可以了，这里例子为0的原因是，上下第9个位置不能同时为9和4，然后，你应该知道怎么怎么做了。

就是每10个字符都归到前10个字符里面，如果是'？'直接跳过，如果是数字，判断前10个的相应位置上的字符，如果是数字，判断是否相等，不行等，直接返回0，相等则判断下一个字符，如果是问号，则把该位置字符置为同一字符。

最后根据前10的字符的情况，按照情况1的方式计算出结果。

我当时是这样想的，但是只过了12个例子，结束后又调试代码，才发现有一个下标写错了，感觉可以过得。

贴上我的代码，写的有点丑。

/*
ID: y1197771
PROG: test
LANG: C++
*/
#include<bits/stdc++.h>
#define pb push_back
#define FOR(i, n) for (int i = 0; i < (int)n; ++i)
#define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
typedef long long ll;
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
string s;
ll ans = 0;
bool check(string s) {
    if(s.size() <= 10) return 1;
    string t = s.substr(0, 10);
    for (int i = 10; i < s.size(); i+=10) {
        if(i + 9 >= s.size()) {
            for (int j = 0; i + j < s.size() && j < 10; j++) {
                if(t[j] != '?' && s[i + j] != '?') {
                    if(t[j] != s[i + j]) return 0;
                } else if((t[j] == '?' && s[i + j] != '?')) {
                    t[j] = s[i + j];
                }
            }
        } else {
            for (int j = 0; j < 10; j++ ) {
                if(t[j] != '?' && s[i + j] != '?') {
                    if(t[j] != s[i + j]) return 0;
                } else if((t[j] == '?' && s[i + j] != '?')) {
                    t[j] = s[i + j];
                }
            }
        }
    }
    set<char> se;
    for (char it : t) {
        if(it == '?') continue;
        se.insert(it);
    }
    ans = 1;
    int d = 10 - se.size();
    //cout << d << " " << endl;
    while(d) {
        ans *= d; d--;
    }
    return 1;
}
void solve() {
    while(cin >> s) {
    if(s.size() <= 10) {
        set<char> se;
        for (auto t : s) {
            if(t == '?') continue;
            if(se.count(t)) {
                cout << 0 << endl;
                continue;
            }
            se.insert(t);
        }
        int n = s.size() - se.size();
        ll res = 1;
        int d = 10 - se.size();
        while(n) {
            res *= d; n--; d--;
        }
        cout << res << endl;
        continue;
    } else {
        if(check(s)) {
            cout << ans << endl;
        } else {
            cout << 0 << endl;
        }
    }
    }

}
int main() {
    freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    solve();
    return 0;
}

下面贴一下大神的代码：其实思路差不多

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <bits/stdc++.h>
using namespace std;

int main()
{
    freopen("test.in", "r", stdin);
    string str;

    while(cin >> str) {
        map<int, int> umap;
        int ans = 1, len = str.size();
        bool flag = false;
        for(int i = 0; i < len; ++ i) {
            if(str[i] != '?') {
                if(umap.find(i % 10) != umap.end()) {
                    if(umap[i % 10] != str[i] - '0') {
                        flag = true;
                        break;
                    }
                }
                else {
                    str[i % 10] = str[i];
                    umap[i % 10] = str[i] - '0';
                }
            }
        }
        if(flag) cout << 0 << endl;
        else {
            int n = umap.size();
            int cnt = 0;
            for(int i = 0; i < min(len, 10); ++ i)
                if(str[i] == '?')
                    cnt ++;
            for(int i = 10 - n, j = 1; j <= cnt; -- i, ++ j)
                ans *= i;
            cout << ans << endl;
        }
    }


    return 0;
}

总结：

其实还是挺简单，头脑冷静下来仔细分析，还是可以很快做出来的。前3道是水题，最后一道稍微思考一下，就可以了。