T1
题目描述
当一个字符串A是由1个或多个字符串B拼接而成，我们称为“B组成了A”。例如，“ab”组成了“abab”。现有两个长度小度1000字符串S1和S2，请找出最长的字符串X，使得“X组成了S1”且“X组成了S2”，如果找不到X，返回空字符串。区分大小写。
输入描述
第1行是字符串S1
第2行是字符串S2
输出描述
最长的字符串X，使得“X组成了S1”且“X组成了S2”，如果找不到X，返回空字符串
示例1
样例输入
abcabc
abc
样例输出
abc
算法
(暴力求解) $O(len1 + len2)$
枚举短字符串的所有循环节去暴力匹配长字符串
C++ 代码
#include <bits/stdc++.h>
using namespace std;
string s1, s2;
bool check(string &s, string &p) {
if (s.size() % p.size()) return false;
for (int i = 0; i < s.size(); i += p.size())
for (int j = 0; j < p.size(); j ++ )
if (s[i + j] != p[j])
return false;
return true;
}
int main() {
cin >> s1 >> s2;
if (s1.size() > s2.size()) swap(s1, s2);
int len1 = s1.size(), len2 = s2.size();
vector<string> t;
for (int i = len1; i >= 1; i -- )
if (len1 % i == 0) {
bool is_valid = true;
for (int j = 0; j < len1; j ++ )
if (s1[j % i] != s1[j]) {
is_valid = false;
break;
}
if (is_valid) t.push_back(s1.substr(0, i));
}
for (auto c: t)
if (check(s2, c)) {
cout << c;
break;
}
return 0;
}
T2
题目描述
已知矩形的行和列，请按如下规律输出斜对角矩形。
输入描述
矩阵的行和列大小
输出描述
按规律输出的矩阵
示例1
样例输入
2 2
样例输出
[[1,3],[2,4]]
示例2
样例输入
1 2
样例输出
[[1,2]]
示例3
样例输入
4 3
样例输出
[[1,3,6],[2,5,9],[4,8,11],[7,10,12]]
算法
(找规律模拟) $O(m * n)$
注意输出细节即可
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int n, m;
int main() {
cin >> n >> m;
vector<vector<int>> a(n + 1, vector<int>(m + 1, 0));
int k = 1;
for (int t = 2; t <= m + n; t ++ )
for (int i = min(t - 1, n); i >= 1 && t - i <= m; i -- )
a[i][t - i] = k ++ ;
cout << '[';
for (int i = 1; i <= n; i ++ ) {
cout << '[';
for (int j = 1; j <= m; j ++ ) {
cout << a[i][j];
if (j < m) cout << ',';
}
cout << "]";
if (i < n) cout << ',';
}
cout << ']';
return 0;
}
T3
题目描述
在机票业务中，我们常常用到各种字母数字组合的信息，如机场代码“SHA”，航班代码“CA522”等。为了节省存储空间，减少字符串操作，我们把英文大小写字母和数字进行编码，每个字符编码为一个6位的二进制编码。这样一个含5个字符的字符串，用一个32位的整数就可以表示，其中编码占用30位，空置两位（2 + 5 * 6），一个含10个字符的字符串，用两个32位的整数就可以表示（2+ 5 * 6，2 + 5 * 6）
字符二进制编码规则：
“a”编码为000001，“b”编码为000010，…，“z”编码为011010
“A”编码为011011，…，“Z”编码为110100
“0”编码为110101，…，“9”编码为111110
字符串编码示例：
“Aa0Z9”编码为整数453467454（00011011 00000111 01011101 00111110）
“a”编码为整数1（00000000 00000000 00000000 00000001）
“Aa0Z9a”编码为整数453467454 1（输出模式是第一个数字+空格+第二个数字）
现要求将输入的字符串转为整数数组，不符合编码规范的字符编码为000000进行占位
输入描述
输入一个字符串，如：
Aa0Z9
更多例子：
Aa0Z9a
a*
输出描述
转换后的整数，不同数字之间用一个空格隔开，最后一个数字之后不要跟空格
453467454
更多例子：
453467454 1
64
示例1
样例输入
Aa0Z9
样例输出
453467454
算法
(枚举) $O(n)$
题目太长了
C++ 代码
#include <bits/stdc++.h>
using namespace std;
string s;
int main()
{
cin >> s;
int n = s.size();
for (int i = 0; i < n; i += 5) {
int ret = 0;
for (int j = i; j < min(n, i + 5); j ++ ) {
ret <<= 6;
if (s[j] >= 'a' && s[j] <= 'z') ret += s[j] - 'a' + 1;
else if (s[j] >= 'A' && s[j] <= 'Z') ret += s[j] - 'A' + 27;
else if (s[j] >= '0' && s[j] <= '9') ret += s[j] - '0' + 53;
}
if (i) cout << ' ' << ret;
else cout << ret;
}
return 0;
}
