C - Get an Even String
题意
给出一个字符串s，删掉字符串里面的某些字符，使得字符串满足：对于任意奇数 i i i 都存在 s i = = s i + 1 s_i == s_{i + 1} si?==si+1?。求删掉的最小字符数。
思路
顺着题意想很容易就想到dp，但是！！！
可以换个想法：最小化删除数量，可以等价为最大化满足条件的数量，即最大化
s
i
=
=
s
i
+
1
s_i == s_{i + 1}
si?==si+1?的数量。
由于对于删掉任意奇数位置 j j j 上的字符，影响的只是 j j j 后面的元素，所以可以直接贪心，从头到尾，找到最多的 s i = = s i + 1 s_i == s_{i + 1} si?==si+1?。
因为题意是相邻字符两两匹配，那就可以每匹配到 s i = = s i + 1 s_i == s_{i + 1} si?==si+1?，那就删除 s [ i ] , s [ i + 1 ] s[i], s[i + 1] s[i],s[i+1]，且在 i i i 位置之前没有被删掉的字符都是不符合条件的字符。
而后面要是再遇到 j > i ? & & ? s [ i ] = = s [ j ] j > i\ \&\&\ s[i] == s[j] j>i?&&?s[i]==s[j] 的话，因为前面可以和 s [ j ] s[j] s[j] 匹配的字符已经被匹配完了，所以 s [ j ] s[j] s[j] 需要和后面的字符匹配，就用mp记录就好了。
最后用字符串的长度减去刚刚删去的符合条件的字符对数： l e n ? c n t × 2 len - cnt \times 2 len?cnt×2，就可以了
代码
string s; cin >> s;
map<char, int> mp;
int ans = 0;
for (int i = 0; i < s.length(); i++) {
mp[s[i]]++;
if (mp[s[i]] == 2)
mp.clear(), ans++;
}
cout << s.length() - ans * 2 << "\n";
D - Maximum Product Strikes Back
题意
给出一个数组 a a a，对于任意 0 ≤ ∣ a [ i ] ∣ ≤ 2 0 \le |a[i]| \le 2 0≤∣a[i]∣≤2。对于任意 l ， r l， r l，r， 0 ≤ l ≤ r ≤ n 0 \le l \le r \le n 0≤l≤r≤n，删掉数组 a a a的前 l l l 个元素和后 r r r 个元素，求 l , r l, r l,r使得 a [ l + 1 ] × a [ l + 2 ] × . . . × a [ r ? 2 ] × a [ r ? 1 ] a[l + 1] \times a[l + 2] \times ... \times a[r - 2] \times a[r - 1] a[l+1]×a[l+2]×...×a[r?2]×a[r?1] 最大。
思路
影响区间内乘积的元素主要为负数和0。只要处理好这种元素的关系，就很方便算了。
首先考虑元素0，因为对于任意区间来说，一旦存在元素0，就会使得整个乘积全部变为0，即使前后扩张区间也无法挽回状况。
当我们把数组中所有的0全部提取出来之后，相当于是把数组给分成了若干个区间，对于每个区间，里面存在的元素就只有正数和负数。
那么对于分成的若干个区间，其实就可以单独考虑每一个区间，因为，假设对于第 i i i 个区间(假设下标为 x , x + 1 , . . . , y x,x+1,..., y x,x+1,...,y)来说，按照题意求这个区间的最大值 m a x i max_i maxi?，就要删去区间前 l x lx lx 个元素和区间后 r x rx rx 个元素（ x ≤ l x ≤ r x ≤ y x \le lx \le rx \le y x≤lx≤rx≤y），结合前两段的内容，我们之所以取出区间 i i i 是因为，区间 i i i前后都存在元素0，区间即使向外扩张，区间内的最大值也不会改变，因为我们向外扩张的话扩张的第一个元素必然是0。所以我们只需要求出我们划分出的所有区间的最大值 m a x i max_i maxi?，然后找到这些最大值里面的最大值 M A X ( m a x i ) MAX(max_i) MAX(maxi?)，就是整个数组符合题意的最大值了。
然后我们考虑怎么求出每个区间的最大值 m a x i max_i maxi?。
对于区间
i
i
i 来说(假设下标为
x
,
x
+
1
,
.
.
.
,
y
x,x+1,..., y
x,x+1,...,y)，如果区间内全是正数或者有偶数个负数，那
m
a
x
i
=
∏
(
a
j
)
(
x
≤
j
≤
y
)
max_i = \prod(a_j) (x\le j\le y)
maxi?=∏(aj?)(x≤j≤y)。如果区间内有奇数个负数，那么势必会影响结果，由于题目规则很特殊，是直接删去数组两头的元素，所以，我们只需要找到离区间两端各自最近的负数
a
[
l
x
]
和
a
[
r
x
]
?
且
(
x
≤
l
x
≤
r
x
≤
y
a[lx]和 a[rx] \ 且(x \le lx \le rx \le y
a[lx]和a[rx]?且(x≤lx≤rx≤y）$：
.若
∣
∏
k
≤
l
x
k
=
x
a
[
k
]
∣
<
∣
∏
k
≤
y
k
=
r
x
a
[
k
]
∣
|\prod\limits^{k = x}_{k \le lx}a[k]| < |\prod\limits^{k = rx}_{k \le y}a[k]|
∣k≤lx∏k=x?a[k]∣<∣k≤y∏k=rx?a[k]∣，那么
m
a
x
i
=
∏
k
≤
r
k
=
l
x
+
1
a
[
k
]
max_i = \prod\limits^{k = lx + 1}_{k \le r}a[k]
maxi?=k≤r∏k=lx+1?a[k]；否则
m
a
x
i
=
∏
k
≤
r
x
?
1
k
=
x
a
[
k
]
max_i = \prod\limits^{k = x}_{k \le rx - 1}a[k]
maxi?=k≤rx?1∏k=x?a[k]。
这样整个题的思路就齐全了，时间复杂度也大概只有 O ( n l o g n ) O(nlogn) O(nlogn)。但是，我RE了。。。。整形溢出！用了__int64还是不行，就突然发现，其实不用求出乘积的。。。因为数组里面所有的数字乘起来，相当于是 2 l e n 2^{len} 2len，所以直接把区间内乘积大小的比较，转变为符合条件的区间内2的绝对值的个数的多少就行了。。。（哎，又是弱智的一天= =）
代码
int n, mul[maxn], a[maxn], pre[maxn], b[maxn];
void solve() {
int t; cin >> t;
while (t--) {
cin >> n;
for (int i = 0; i <= n + 8; i++) a[i] = 1, pre[i] = 0, b[i] = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
b[i] = b[i - 1];
pre[i] = pre[i - 1];
if (abs(a[i]) == 2) b[i]++, a[i] /= 2;
if (a[i] < 0) pre[i]++; //标记负数
}
int tmp = 0, lft = 0, rgh = n;
for (int i = 1; i <= n; i++) {
while ((i <= n) && (!a[i])) i++; //跳过0
if (i > n) break;
int l = i, r = l;
while (r < n && a[r + 1]) r++; //找到0 0之间的区间
i = r + 1;
if ((pre[r] - pre[l - 1]) & 1) { //区间内奇数个负数
int lx = l, rx = r;
while (lx <= r && a[lx] > 0) lx++;
while (rx >= l && a[rx] > 0) rx--;
int tmp1 = b[r] - b[lx];
int tmp2 = b[rx - 1] - b[l - 1];
if (tmp < tmp1) tmp = tmp1, lft = lx, rgh = n - r;
if (tmp < tmp2) tmp = tmp2, lft = l - 1, rgh = n - rx + 1;
} else {
int tmp1 = b[r] - b[l - 1];
if (tmp < tmp1) tmp = tmp1, lft = l - 1, rgh = n - r;
}
}
cout << lft << " " << rgh << "\n";
}
}
E- Matrix and Shifts
题意
给出一个 n × n n \times n n×n的01矩阵，矩阵的第 i i i行或第 i i i列可以和第 i + 1 i + 1 i+1行或 i + 1 i + 1 i+1列交换，首行或尾列可以和尾行或首列交换。矩阵的元素可以修改成0或1，没修改一次需要花费1，现在需要使得矩阵的对角线全是1，其余位置为0，结合矩阵行或列的交换，求最少的花费。
思路
哎 做的题太少了，不知道这个结论。
对于行、列可以相邻交换的矩阵，将矩阵复制成
2
n
×
2
n
2n\times 2n
2n×2n的矩阵，那么交换行列后的矩阵一定存在在这个复制后的矩阵里面。
所以直接遍历就好了。考虑到时间复杂度，所以预处理一个矩阵前缀和、对角线前缀和就可以了。
（！记得注释#define int long long，呜呜呜不然会MLE呜呜呜呜呜）
const int maxn = 4005;
int n, pre[maxn][maxn], x[maxn][maxn];
bool a[maxn][maxn];
void solve() {
int t;
cin >> t;
while (t--) {
cin >> n;
char c;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> c;
a[i][j] = a[i + n][j] = a[i][j + n] = a[i + n][j + n] = c - '0';
}
}
int ans = n * n;
for (int i = 1; i <= 2 * n; i++) {
for (int j = 1; j <= 2 * n; j++) {
pre[i][j] =
pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + a[i][j];
x[i][j] = x[i - 1][j - 1] + a[i][j];
}
}
for (int i = n; i <= 2 * n; i++) {
for (int j = n; j <= 2 * n; j++) {
int tmp = pre[i][j] - pre[i - n][j] - pre[i][j - n] +
pre[i - n][j - n];
ans = min(tmp - 2 * (x[i][j] - x[i - n][j - n]) + n, ans);
}
}
cout << ans << "\n";
}
}
