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 + ;
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 = ; i < s.size() - ; i ++) {
string cur = s.substr(i, );
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 ;
}
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 + ;
int n, m;
int a[];
int b[];
vector<pii> range;
void solve() {
cin >> n >> m;
for (int i = ; i <= n; i++) cin >> a[i];
int x, y;
for (int i = ; i < m; i++) {
cin >> x >> y;
range.pb({x, y});
}
int res = ;
for (int i = ; i <= n; i++)
res += i * a[i];
for (int i = ; i < ( << m); i++) { vector<int> p;
for (int j = ; j < m; j++) {
if(( << 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 = ; j <= n; j++) b[j] = a[j];
for (int x = ; x < p.size(); x++) {
reverse(b + range[p[x]].first, b + range[p[x]].second + );
}
int s = ;
for (int j = ; 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 ;
}
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 + ;
string s;
ll ans = ;
bool check(string s) {
if(s.size() <= ) return ;
string t = s.substr(, );
for (int i = ; i < s.size(); i+=) {
if(i + >= s.size()) {
for (int j = ; i + j < s.size() && j < ; j++) {
if(t[j] != '?' && s[i + j] != '?') {
if(t[j] != s[i + j]) return ;
} else if((t[j] == '?' && s[i + j] != '?')) {
t[j] = s[i + j];
}
}
} else {
for (int j = ; j < ; j++ ) {
if(t[j] != '?' && s[i + j] != '?') {
if(t[j] != s[i + j]) return ;
} 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 = ;
int d = - se.size();
//cout << d << " " << endl;
while(d) {
ans *= d; d--;
}
return ;
}
void solve() {
while(cin >> s) {
if(s.size() <= ) {
set<char> se;
for (auto t : s) {
if(t == '?') continue;
if(se.count(t)) {
cout << << endl;
continue;
}
se.insert(t);
}
int n = s.size() - se.size();
ll res = ;
int d = - se.size();
while(n) {
res *= d; n--; d--;
}
cout << res << endl;
continue;
} else {
if(check(s)) {
cout << ans << endl;
} else {
cout << << endl;
}
}
} }
int main() {
freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
solve();
return ;
}
下面贴一下大神的代码：其实思路差不多
#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 = , len = str.size();
bool flag = false;
for(int i = ; i < len; ++ i) {
if(str[i] != '?') {
if(umap.find(i % ) != umap.end()) {
if(umap[i % ] != str[i] - '') {
flag = true;
break;
}
}
else {
str[i % ] = str[i];
umap[i % ] = str[i] - '';
}
}
}
if(flag) cout << << endl;
else {
int n = umap.size();
int cnt = ;
for(int i = ; i < min(len, ); ++ i)
if(str[i] == '?')
cnt ++;
for(int i = - n, j = ; j <= cnt; -- i, ++ j)
ans *= i;
cout << ans << endl;
}
} return ;
}
总结：
其实还是挺简单，头脑冷静下来仔细分析，还是可以很快做出来的。前3道是水题，最后一道稍微思考一下，就可以了。