A. 小水獭游河南
a的长度小于 26，所以直接暴力枚举暴力判断。
#include <bits/stdc++.h>
using namespace std;
void solve() {
string s;
cin >> s;
if (s.size() == 1) {
cout << "NaN\n";
return;
}
map<char, int> cnt;
for (int i = 0; i < s.size(); i++) {
cnt[s[i]]++;
if (cnt[s[i]] == 2) break;
int f = 1;
for (int j = i + 1, l = s.size() - 1; j < s.size() && j <= l; j++, l--) {
if (s[j] != s[l]) f = 0;
}
if (f) {
cout << "HE\n";
return;
}
}
cout << "NaN\n";
return;
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t;
cin >> t;
for (; t; t--)
solve();
return 0;
}
B. Art for Rest
枚举\(k\)，然后暴力判断就好了，判断的条件是对于每一个区间的右端点应该满足前缀最大值小于等于后缀最小值。
#include <bits/stdc++.h>
using namespace std;
int32_t main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector<int> a(n + 1), b(n + 1), c(n + 2);
for (int i = 1; i <= n; i++) cin >> a[i];
b[0] = INT_MIN;
for (int i = 1; i <= n; i++) b[i] = max(b[i - 1], a[i]);
c[n + 1] = INT_MAX;
for (int i = n; i >= 1; i--)
c[i] = min(c[i + 1], a[i]);
auto check = [b, c, n](int k) {
for (int i = k; i <= n; i += k)
if (b[i] > c[i + 1]) return false;
return true;
};
int res = 0;
for (int i = 1; i <= n; i++)
if (check(i)) res++;
cout << res;
return 0;
}
C. Toxel 与随机数生成器
如果是采用算法二生成的二进制序列，那么至少会有一个长度为\(10^3\)的序列反复出现至少两次。所以把前\(10^3\)作为模式串跑一个 kmp就好了。
#include <bits/stdc++.h>
using namespace std;
vector<int> prefix_function(string s) {
int n = s.size();
vector<int> pi(n);
for (int i = 1, j; i < n; i++) {
j = pi[i - 1];
while (j > 0 && s[i] != s[j]) j = pi[j - 1];
if (s[i] == s[j]) j++;
pi[i] = j;
}
return pi;
}
vector<int> kmp(string text, string pattern) { // pattern 在 text 中出现的位置
string cur = pattern + '#' + text;
int n = text.size(), m = pattern.size();
vector<int> v;
vector<int> lps = prefix_function(cur);
for (int i = m + 1, last = -1; i <= n + m; i++)
if (lps[i] == m) v.push_back(i - 2 * m);
return v;
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
string s, t;
cin >> s;
t = s.substr( 0 , 1000 );
if( kmp(s,t).size() <= 1 ) cout << "Yes";
else cout << "No";
return 0;
}
实际上，这道题的数据比较特殊，如果出现重复的情况length最长只有\(1e4\)，所以一样用前\(10^3\)做模式串，然后枚举第二个串的起点就好了。
#include <bits/stdc++.h>
using namespace std;
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
string s, t;
cin >> s;
int m = 1000;
t = s.substr( 0 , m );
for( int i = m ; i <= 1e4 ; i ++ )
if( s.substr(i,m) == t ){
cout << "No\n";
return 0;
}
cout << "Yes\n";
return 0;
}
E. 矩阵游戏
f[i][j][k]表示从\((1,1)\)走到\((i,j)\)并至多转换\(k\)个问号的最大收益。然后枚举一下转移就好了。需要用到滚动数组优化。
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, m, k;
cin >> n >> m >> k;
string s;
vector<vector<int>> f(m + 1, vector<int>(k + 1, 0)), g(m + 1, vector<int>(k + 1, 0));
for (int i = 1; i <= n; i++) {
cin >> s;
for (int j = 1; j <= m; j++) {
for (int x = 0; x <= k; x++) {
f[j][x] = max(f[j - 1][x], g[j][x]);
if (x > 0) f[j][x] = max(f[j][x], f[j][x - 1]);
if (s[j - 1] == '?') {
if (x > 0) f[j][x] = max(f[j][x], max(f[j - 1][x - 1], g[j][x - 1]) + 1);
f[j][x] = max(f[j][x], max(f[j - 1][x], g[j][x]));
} else if (s[j - 1] == '1') {
f[j][x] = max(f[j][x], max(f[j - 1][x], g[j][x]) + 1);
} else {
f[j][x] = max(f[j][x], max(f[j - 1][x], g[j][x]));
}
}
}
g = f;
}
cout << g[m][k] << "\n";
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--) solve();
return 0;
}
F. Art for Last
因为这里最终选出的子序列在原序列中的顺序是无关的。所以我们可以把原序列排序，选取长度为\(k\)的子区间。
这样的话，最大差值就是子区间的端点，最小差值可以暴力的求解。再加上枚举区间，最终的复杂度是\(O(nk)\)
比较简单的做法是，提前预处理排序后的差分数组，然后双指针的形式，配合堆求解，复杂度\(O(n\log k)\)
堆的实现可以用multiset。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a.begin() + 1, a.end());
vector<int> b(n + 1);
for (int i = 2; i <= n; i++)
b[i] = a[i] - a[i - 1];
int res = LLONG_MAX;
multiset<int> cnt;
for (int i = 2; i < k; i++)
cnt.insert(b[i]);
for (int l = 1, r = k; r <= n; r++, l++) {
cnt.insert(b[r]);
res = min(res, (a[r] - a[l]) * (*cnt.begin()));
cnt.erase(cnt.lower_bound(b[l + 1]));
}
cout << res;
return 0;
}
G. Toxel 与字符画
写一个很丑的模拟就行了。求\(x^y\)可以用快速幂，但是这里快速幂的过程中很容易会超精度。
首先超精度的地方是乘法，所以实际上相当于要判断\(a\times b\le 10^{18}\)。
对不等式两侧同时取对数\(\log_{10}(a\times b) = \log_{10}a+\log_{10}b \le 18\)。
注意的是log10为了保证精度，应该在传入整形的时候强转为long double
#include <bits/stdc++.h>
using namespace std;
#define double long double
#define int long long
const int INF = 1e18;
const double l = 18.0;
int power( int x , int y ){
int ans = 1;
while( y ){
if( y & 1 ) {
if( log10((double)ans) + log10((double)x) <= l ) ans = ans * x;
else return INF + 1;
}
y >>= 1;
if(y) {
if( log10((double)x) + log10((double)x) <= l ) x = x * x;
else return INF + 1;
}
}
return ans;
}
int read(){
int x = 0 , ch = getchar();
while( ch < '0' || ch > '9' ) ch = getchar();
while( ch >= '0' && ch <= '9' ) x = (x<<3)+(x<<1) + ch - '0' , ch = getchar();
return x;
}
int32_t main(){
map<string,vector<string>> st;
st["="] = {
".......",
".......",
".......",
".......",
"=======",
".......",
"=======",
".......",
".......",
"......."
};
st["0"] = {
".......",
".......",
"0000000",
"0.....0",
"0.....0",
"0.....0",
"0.....0",
"0.....0",
"0000000",
"......."
};
st["1"] = {
".......",
".......",
"......1",
"......1",
"......1",
"......1",
"......1",
"......1",
"......1",
"......."
};
st["2"] = {
".......",
".......",
"2222222",
"......2",
"......2",
"2222222",
"2......",
"2......",
"2222222",
"......."
};
st["3"] = {
".......",
".......",
"3333333",
"......3",
"......3",
"3333333",
"......3",
"......3",
"3333333",
"......."
};
st["4"] = {
".......",
".......",
"4.....4",
"4.....4",
"4.....4",
"4444444",
"......4",
"......4",
"......4",
"......."
};
st["5"] = {
".......",
".......",
"5555555",
"5......",
"5......",
"5555555",
"......5",
"......5",
"5555555",
"......."
};
st["6"] = {
".......",
".......",
"6666666",
"6......",
"6......",
"6666666",
"6.....6",
"6.....6",
"6666666",
"......."
};
st["7"] = {
".......",
".......",
"7777777",
"......7",
"......7",
"......7",
"......7",
"......7",
"......7",
"......."
};
st["8"] = {
".......",
".......",
"8888888",
"8.....8",
"8.....8",
"8888888",
"8.....8",
"8.....8",
"8888888",
"......."
};
st["9"] = {
".......",
".......",
"9999999",
"9.....9",
"9.....9",
"9999999",
"......9",
"......9",
"9999999",
"......."
};
st["00"] = {
".....",
"00000",
"0...0",
"0...0",
"0...0",
"00000",
".....",
".....",
".....",
"....."
};
st["11"] = {
".....",
"....1",
"....1",
"....1",
"....1",
"....1",
".....",
".....",
".....",
".....",
};
st["22"] = {
".....",
"22222",
"....2",
"22222",
"2....",
"22222",
".....",
".....",
".....",
".....",
};
st["33"] = {
".....",
"33333",
"....3",
"33333",
"....3",
"33333",
".....",
".....",
".....",
".....",
};
st["44"] = {
".....",
"4...4",
"4...4",
"44444",
"....4",
"....4",
".....",
".....",
".....",
"....."
};
st["55"] = {
".....",
"55555",
"5....",
"55555",
"....5",
"55555",
".....",
".....",
".....",
"....."
};
st["66"] = {
".....",
"66666",
"6....",
"66666",
"6...6",
"66666",
".....",
".....",
".....",
"....."
};
st["77"] = {
".....",
"77777",
"....7",
"....7",
"....7",
"....7",
".....",
".....",
".....",
"....."
};
st["88"] = {
".....",
"88888",
"8...8",
"88888",
"8...8",
"88888",
".....",
".....",
".....",
"....."
};
st["99"] = {
".....",
"99999",
"9...9",
"99999",
"....9",
"99999",
".....",
".....",
".....",
"....."
};
st["INF"] = {
".......................",
".......................",
"IIIIIII.N.....N.FFFFFFF",
"...I....NN....N.F......",
"...I....N.N...N.F......",
"...I....N..N..N.FFFFFFF",
"...I....N...N.N.F......",
"...I....N....NN.F......",
"IIIIIII.N.....N.F......",
".......................",
};
st[" "] = {
".",
".",
".",
".",
".",
".",
".",
".",
".",
"."
};
vector<string> xx(10);
xx[0] = "0";
xx[1] = "1";
xx[2] = "2";
xx[3] = "3";
xx[4] = "4";
xx[5] = "5";
xx[6] = "6";
xx[7] = "7";
xx[8] = "8";
xx[9] = "9";
vector<string> yy(10);
yy[0] = "00";
yy[1] = "11";
yy[2] = "22";
yy[3] = "33";
yy[4] = "44";
yy[5] = "55";
yy[6] = "66";
yy[7] = "77";
yy[8] = "88";
yy[9] = "99";
for( int t = read() , x , y , z; t ; t -- ){
x = read() , y = read() , z = power( x , y );
vector<string> res , ans;
res.push_back(" ");
ans.clear();
while( x ){
ans.emplace_back( xx[x%10]);
x /= 10;
}
reverse(ans.begin() , ans.end() );
for( auto i : ans )
res.emplace_back(i) , res.push_back(" ");
ans.clear();
while( y ){
ans.emplace_back( yy[y%10]);
y /= 10;
}
reverse(ans.begin() , ans.end() );
for( auto i : ans )
res.emplace_back(i),res.push_back(" ");
res.push_back("="),res.push_back(" ");
if( z > INF ) res.push_back("INF"),res.push_back(" ");
else {
ans.clear();
while( z ){
ans.emplace_back( xx[z%10]);
z /= 10;
}
reverse(ans.begin() , ans.end() );
for( auto i : ans )
res.emplace_back(i),res.push_back(" ");
}
for( int i = 0 ; i < 10 ; i ++ ){
for( auto j : res )
cout << st[j][i];
cout << "\n";
}
cout << "\n";
}
return 0;
}
H. Travel Begins
多弄几个样例找找规律
#include <bits/stdc++.h>
using namespace std;
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while( t -- ){
int n , k;
cin >> n >> k;
if( n*2 >= k )
cout << n-(k+1)/2+1 << " " << n-(k+1)/2+k << "\n";
else
cout << "0 " << n*2 << "\n";
}
return 0;
}
K. 排列与质数
看到答案推出来的结果是分奇偶的。我们的做法是不用讨论这个问题的。
\(4,1,3,5,2,\cdots,n-7,n-5,n-3,n,n-2,n-4,n-1,n-6,n-8\cdots\)
先这样构造，一直构造到\(6\)，然后\(4,1,3,5,2\)放在开头就好了。
这种构造方式只能满足大于等于 12 的情况，其他情况直接打表即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n;
cin >> n;
if (n < 12) {
if (n == 2 || n == 3 || n == 4)
cout << -1;
else if (n == 5)
cout << "4 1 3 5 2";
else if (n == 6)
cout << "1 3 5 2 4 6";
else if (n == 7)
cout << "1 3 5 7 2 4 6";
else if (n == 8)
cout << "1 3 5 7 2 4 6 8";
else if (n == 9)
cout << "1 3 5 7 9 2 4 6 8";
else if (n == 10)
cout << "1 3 5 7 10 8 6 9 2 4";
else if (n == 11)
cout << "11 9 7 10 8 6 1 3 5 2 4";
return 0;
}
deque<int> a;
a.push_back(n);
for (int i = n - 2; i >= 6; i--) {
if (i & 1) a.push_front(i);
else a.push_back(i);
if (i == n - 4) {
if (i & 1) a.push_front(n - 1);
else a.push_back(n - 1);
}
}
cout << "4 1 3 5 2";
while (!a.empty()) {
cout << " " << a.front();
a.pop_front();
}
return 0;
}