P11450 [USACO24DEC] Farmer John's Cheese Block B
//Farmer John's Cheese Block B
#include<stdio.h>
#include<iostream>
using namespace std;
int cnt_xy[1005][1005], cnt_yz[1005][1005], cnt_xz[1005][1005];
int main(){
int n, q;
int x, y, z;
int ans = 0;
cin >> n >> q;
for(int i = 1; i <= q; i++){
cin >> x >> y >> z;
if(++cnt_xy[x][y] == n) ans ++;
if(++cnt_yz[y][z] == n) ans ++;
if(++cnt_xz[x][z] == n) ans ++;
cout << ans << endl;
}
return 0;
}
P11451 [USACO24DEC] It's Mooin' Time B
解题思路
-
字符串模拟题，如果不考虑错误的话，那么只需要从头到尾扫一遍长度为3的字符串，利用map存储字符串出现的次数，判断是否大于\(f\)即可。
-
但是本题中可能存在误差。因此如果出现的次数\(cnt >= f-1\)都有可能作为答案。
在判断的时候需要分情况考虑
1）当\(f>1\)时，能够作为答案的字符串\(s1\)一定原本已经在\(s\)中出现过。
如果\(cnt>=f\)那么直接作为答案；
如果\(cnt==f-1\)那么需要判断是否考虑误差之后，能够让出现的次数加一，处理方法如下
-
记录原字符串中所有出现过\(s1\)的所有位置pos1
-
记录若产生误差，能够出现\(s1\)的所有位置pos2
对所有pos2，如果出现一个pos2不会和原字符串中的所有pos1发生冲突，即cnt可以加一，满足要求，可以作为答案。
关于存储：建立两个map<int, vector
>，\(mp1\)存储符合要求的字符串及所有出现的位置，\(mp2\)存储改过之后符合要求的字符串及所有出现的位置 2）当\(f==1\)时，能够作为答案的字符串\(s1\)不一定在\(s\)中出现过。
因此要遍历\(mp1\)以及\(mp2\),所有符合题目条件要求的都可以作为答案（要注意去重）
-
参考代码
//It's Mooin' Time B
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
map<string, vector<int> > mp, mp1;
string ans_str[1000005];
int main(){
int n, f;
string s, st, temp_s;
cin >> n >> f;
cin >> s;
for(int i = 0; i < n - 2; i++){
st = s.substr(i, 3);
if(s[i] != s[i+1] && s[i+1] == s[i+2]) mp[st].push_back(i);
for(int j = 0; j < 3; j++){
string temp = st;
for(int k = 0; k < 26; k++){
temp[j] = 'a' + k;
if(st[j] != temp[j] && temp[0] != temp[1] && temp[1] == temp[2]) mp1[temp].push_back(i);
}
}
}
int ans = 0;
if(f > 1){
for(auto it = mp.begin(); it!= mp.end(); it++){
if(it->second.size() >= f) ans_str[++ans] = it->first;
else if(it->second.size() == f-1){
//遍历一遍改过的map，如果有一个不会冲突的字符串位置，就可以
for(int i = 0; i < mp1[it->first].size(); i++){
bool flag = 1;
for(int j = 0; j < it->second.size(); j++){
if(it->second[j] - 2 <= mp1[it->first][i] && mp1[it->first][i] <= it->second[j] + 2)
flag = 0;
}
if(flag){
ans_str[++ans] = it->first;
break;
}
}
}
}
}
else{
for(auto it = mp.begin(); it != mp.end(); it++){
if(mp1[it->first].size() == 0) ans_str[++ans] = it->first;
}
for(auto it = mp1.begin(); it != mp1.end(); it++) ans_str[++ans] = it->first;
}
cout << ans << endl;
sort(ans_str, ans_str + ans + 1);
for(int i = 1; i <= ans; i++) cout << ans_str[i] << endl;
return 0;
}
P11452 [USACO24DEC] Cake Game S
解题思路
-
Bessie 和 Elsie的吃蛋糕最优策略：
1）对于Bessie来说，一定不能将合并起来的蛋糕位置放在最左边或者最右边，不然会被Elsie吃掉。又因为Bessie只能合并相邻的连续的两个蛋糕，所以实际上Bessie能够吃掉的蛋糕最大值是被动的，取决于Elsie吃左边还是右边的蛋糕。
一开始Bessie只能合并正中间的两个蛋糕（合并其他蛋糕后，都有可能被Elsie吃）
当Elsie吃左边蛋糕，Bessie只能向右边合并，反之亦然。
2）实际上，对于Elsie的最优决策为：求前缀和以及后缀和，枚举\(len(前缀和)+len(后缀和)=2/n-1\)的所有方案，求Elsie能够吃到的最大值，那么总和减去该最大值就是Bessie能够吃到的最大值
参考代码
```
//Cake Game S
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
typedef long long ll;
ll cake[500005];
ll sum_l[500005], sum_r[500005];
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
memset(sum_l, 0, sizeof(sum_l));
memset(sum_r, 0, sizeof(sum_r));
for(int i = 1; i <= n; i++){
cin >> cake[i];
sum_l[i] = sum_l[i-1] + cake[i];
}
if(n == 2){
cout << sum_l[n] << " " << 0 << endl;
continue;
}
for(int i = n; i >= n/2+1; i--) sum_r[i] = sum_r[i+1] + cake[i];
int len = n / 2 - 1;
ll e_ans = 0;
for(int i = 0; i <= len; i++){
e_ans = max(e_ans, sum_l[i] + sum_r[n/2+i+2]);
}
cout << sum_l[n] - e_ans << " " << e_ans << endl;
}
return 0;
}
```
## P11453 [USACO24DEC] Deforestation S
### 解题思路
树状数组+贪心
- 因为想要农场可以尽可能大，所以可以贪心地从前往后判断每一棵树，如果当前的树砍掉依然可以满足数量限制要求的话，那么就将当前树砍掉。
- 发现这道题的坐标值域为$[-10^9,10^9]$。如果用前缀和来维护树的数量状态，会发现值域太大无法处理。因此可以做离散化。并将所有的限制要求的值同样映射。因为树的坐标数组以及要求区间的坐标数组已经都排好序了，所以可以用双指针来实现区间数组的映射，其时间复杂度为$O(2n)$
- 在进行判断的时候，会发现如果当前树砍掉，会对所有包含该树的区间的值都发生改变。动态的修改以及查询可以使用树状数组实现，因此先建立一个树状数组维护区间内树的数量。判断时查询区间内树状数组的值。当前树可以砍掉的时候，修改树状数组。