程序员进阶之算法练习（八十）
题目1
题目链接
题目大意：
有一个数组a，仅有整数1和-1组成，我们定义数组a的乘积为：
对于 1≤𝑖<𝑗≤𝑛, 𝑎[𝑖]⋅𝑎[𝑗]=1的数量。
现在给出数组长度n和乘积k，问是否可以构造一个满足要求的数组a；
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤20000)
每个样例1行， n和𝑘，表示数组长度和乘积k （2≤𝑛≤100 ; 0≤𝑘≤(𝑛−1)*𝑛/2）
输出：
如果有解，则输出YES，然后第二行输出n个整数；
如果无解，则输出NO；
Examples
input
7
2 0
2 1
3 1
3 2
3 3
5 4
5 5
output
YES
1 -1
YES
1 1
YES
1 -1 1
NO
YES
1 1 1
YES
-1 1 -1 1 1
NO
题目解析：
题目给出的数据范围比较小，可以直接枚举；
遍历数组存在0个、1个、2个、、、到n个1的情况，剩下用-1填充；
然后再遍历整个数组，两两计算a[i]*a[j] = 1的数量；
如果满足要求则输出；
class Solution {
static const int N = 201010;
char s[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
int ans = 0;
for (int i = 0; i <= n; ++i) //第i个开始都是1，前面都是-1
{
int sum = 0;
for (int x = 0; x < n; ++x) {
for (int y = x + 1; y < n; ++y) {
if ((x < i && y < i) || (x >= i && y >= i)) {
++sum;
}
}
}
if (sum == k) {
ans = 1;
int tmp = 0;
cout << "YES" << endl;
while (tmp < i) {
cout << "-1" << " ";
++tmp;
}
while (tmp < n) {
cout << "1" << " ";
++tmp;
}
cout << endl;
break;
}
}
if (!ans) cout << "NO" << endl;
}
}
}
题目2
题目链接
题目大意：
给出1到n的整数排列所形成的数组p以及整数k，现在可以对数组进行下列操作形成从小到大的数组：
选择任意两个相差为k的位置，交换他们的位置上的元素；
比如说数组[3,2,1] 和 k=2，那么可以选择位置1和位置3进行交换，得到数组[1,2,3]，满足题目要求；
但是有些数组的无法满足要求，比如说[2,4,3,1]和k=2，此时无法通过交换得到数组[1,2,3,4]；
这种情况下，此时允许在最初的时候（进行交换操作之前），对选择任意数组两个位置，进行交换（该交换只允许一次），比如说：
数组[2,4,3,1]选择整数1和2交换得到[1,4,3,2]，然后再进行交换操作，可以得到从小到大的数组[1,2,3,4]；
现在的任务是给出数组p和整数k，问是否能得到从小到大的数组。
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例2行
第一行 n和𝑘，表示数组长度和整数k (2≤𝑛≤2⋅1e5; 1≤𝑘≤𝑛−1)
第二行 n个整数 𝑝1,𝑝2,…,𝑝𝑛 （1≤𝑝𝑖≤n）
输出：
每个样例一行，输出0/1/-1，分别表示：
0，有解，并且不需要提前交换；
1，有解，但是必须要提交交换；
-1，无解；
Examples
input
6
4 1
3 1 2 4
4 2
3 4 1 2
4 2
3 1 4 2
10 3
4 5 9 1 8 6 10 2 3 7
10 3
4 6 9 1 8 5 10 2 3 7
10 3
4 6 9 1 8 5 10 3 2 7
output
0
0
1
0
1
-1
题目解析：
当k=1的时候，肯定有解，因为可以随意交换；
当k>1的时候，每个位置能和相距为k的位置交换，那么将距离为k的元素全部提取出来，这部分元素就能任意交换，比如说数组[1,2,3,4,5,6,7]
k=2时，数组可以拆分为[1,3,5,7]和[2,4,6]，这两个数组的元素就能任意交换；
k=3时，整数可以拆分为[1,4,7], [2,5], [3,6] 这样三个数组；
我们将数组p，拆分成k个数组，每个数组如果都按照上述的规律展示，那么不需要做提前交换，就可以有解；
通过不匹配当前数组的元素数量，如果为2，那么通过提前交换就有解；如果为其他值则无解；
举个例子，假设数组4 1 3 5 2 6 7，我们拆分得到
457
12
36
那么可以得到4应该在第二组，而不是第一组；
1不应该在第二组，而是应该在第一组；
此时提前交换1和4，有解；
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> a[i];
if (k == 1) cout << 0 << endl;
else {
int cnt = 0;
for (int i = 1; i <= k; ++i) {
int idx = i;
while (idx <= n) {
if ((a[idx] - i) % k) ++cnt;
idx += k;
}
}
if (cnt == 2) cnt = 1;
cout << (cnt < 2 ? cnt : -1) << endl;
}
}
}
}
题目3
题目链接
题目大意：
有n个整数的数组a，数组元素由1和-1组成；
现在可以对数组中的元素进行操作（最后一个元素无法操作），将这个元素与右边元素进行符号反转；
比如说数组[1, -1, -1]，如果我们选择[1, -1]进行符号反转，则得到[-1, 1, -1]；如果我们选择[-1, -1]进行符号反转，则可以得到[1, 1, 1]；
这个操作必须执行一次，问操作完数组最大的和是多少。（a1+a2+a3...+an)
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤500)
每个样例2行，第一行整数𝑛 (2≤𝑛≤10e5）
第二行n个整数 𝑎1,𝑎2,…,𝑎𝑛 (𝑎𝑖=1 or 𝑎𝑖=−1)
输出：
每个样例一行，输出可能的最大数组和；
Examples
input
4
5
-1 1 1 -1 -1
5
1 1 -1 -1 -1
2
1 1
4
1 -1 -1 1
output
3
3
-2
4
题目解析：
直接累加数组的整数，得到整数和sum；
接着遍历数组：
如果能找到两个-1相邻，则直接反转着两个整数，sum=sum+4；
如果能有一个-1，则sum=sum;
如果都是1，则sum=sum - 4;
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int sum = 0, done = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i];
sum += a[i];
}
for (int i = 1; i < n && !done; ++i) {
if (a[i] + a[i - 1] == -2) {
sum += 4;
done = 1;
}
}
for (int i = 0; i < n && !done; ++i) {
if (a[i] == -1) {
done = 1;
}
}
if (!done) {
sum -= 4;
}
cout << sum << endl;
}
}
}
题目4
题目链接
题目大意：
给出一个由 _ 和 ^ 两种字符组成的字符串，现在小明可以往字符串任意位置插入这两种字符，要求：
1、任何位置的字符，都可以和相邻连续字符组成^_^ 或者 ^^ 这样的字符串；
2、尽可能少的插入字符；
比如说字符串^^__^_^^__^，在第3,4,9,10,11个字符，就无法和相邻连续字符组成满足要求的字符串。
问最少需要插入多少个字符。
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤100)
每个样例1行，字符串𝑠 (1≤|𝑠|≤100)
输出：
每个样例一行，输出最少插入数量；
Examples
input
7
^______^
___^_^^^_^___^
^_
^
^_^^^^^_^_^^
___^^
_
output
5
5
1
1
0
3
2
题目解析：
字符串只包含两种字符，由于可以插入 ^ 字符，^字符可以和_组成^_^ ，也可以和^组成^_^，那么必然题目有解；
对于题目来说，单个^，以及_左右不是^都是不合法的，需要插入^；
那么就可以有简单的解决方案：
从左到右遍历字符串，对于第i个字符串s[i]，假如：
1、s[i]是^字符，只要i>0，^必然合法，因为s[i-1]是'^'，已经合法；如果s[i-1]是'_'，那么在处理s[i-1]的时候已经做了合法处理；
2、s[i]是_字符，如果i==0，需要在前面插入^，否则只需要考虑后面是_的情况，需要插入一个^；
class Solution {
static const int N = 201010;
char s[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> s;
int n = strlen(s);
int ans = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '_') {
if (i == 0) {
++ans;
}
if (i + 1 == n || s[i + 1] == '_') {
++ans;
}
}
else {
if (n == 1) {
++ans;
}
}
}
cout << ans << endl;
}
}
}
题目5
题目链接
题目大意：
给出一个0/1字符组成的字符串，现在按照以下规则进行排序：
1、将字符串str作为矩阵第一行；
2、将字符串str所有字符右移1位（最后一位字符会移动到最左边的位置），将这个字符当做下一行；
重复以上规则，直到得到一个正方形矩阵。
以“101”字符串为例：
第一行是101；
第二行是110；
第三行是011；
问得到的正方形矩阵中，由1组成的连续字符矩阵最大面积是多少。
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤2⋅1e4 )
每个样例1行，字符串𝑠 (1≤|𝑠|≤2⋅1e5),
输出：
每个样例一行，输出最大的面积，如果不存在则输出0；
Examples
input
5
0
1
101
011110
101010
output
0
1
2
6
1
题目解析：
由于字符串长度很大，暴力枚举计算的空间复杂度太高；
分析题目给出的构造规则，我们发现0会形成一条斜线，将矩形分割开来；
参考题目样例4，我们可以知道最终矩阵：
0 0 1 1 1 1 0
1 0 0 1 1 1 1
1 1 0 0 1 1 1
1 1 1 0 0 1 1
1 1 1 1 0 0 1
0 1 1 1 1 0 0
存在一个长为4，等边三角形；
同理，这样的字符串，一样在矩阵中存在长为4的等边三角形。
1 1 1 1 0 0 0
0 1 1 1 1 0 0
0 0 1 1 1 1 0
0 0 0 1 1 1 1
1 0 0 0 1 1 1
1 1 0 0 0 1 1
极端的情况，连续的1拆分在两边
1 1 0 0 0 1 1
1 1 1 0 0 0 1
1 1 1 1 0 0 0
0 1 1 1 1 0 0
0 0 1 1 1 1 0
0 0 0 1 1 1 1
1 0 0 0 1 1 1
1 1 1 0 0 0 1
1 1 1 1 0 0 0
0 1 1 1 1 0 0
0 0 1 1 1 1 0
0 0 0 1 1 1 1
1 0 0 0 1 1 1
1 1 0 0 0 1 1
可以得到一个规律，我们根据字符串中“连续”1的数量，就可以得到等边三角形的数量。
这个连续1的计算方式，可以用下面的规则：
将字符串1100011，复制一遍粘到末尾 1100011+1100011 = 11000111100011
这样去计算一遍连续的最长字符串即可。
注意：
1、如果全为1，答案为n * n；
2、如果全为0，答案为0；
3、结果有可能超int32，需要用long long。
class Solution {
static const int N = 401010;
char s[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> s;
int n = strlen(s);
for (int i = 1; i < n; ++i) {
s[n + i - 1] = s[i - 1]; // 拼接
}
s[n * 2 - 1] = '0';
int cur = 0, zero = 0, len = 0;
for (int i = 0; i < 2 * n; ++i) {
if (s[i] == '0') {
len = max(len, cur);
cur = 0;
}
else {
++cur;
}
}
for (int i = 0; i < n; ++i) zero |= (s[i] == '0');
if (!zero) cout << n * 1LL * n << endl;
else {
if (len <= 2) cout << len << endl;
else if (len % 2) cout << (len + 1) / 2LL * (len + 1) / 2 << endl;
else cout << len / 2LL * (len + 2) / 2 << endl;
}
}
}
}
