天天摸鱼身体棒
A. Yet Another String Game
给定一串字符串，两个人轮流进行游戏，每个人轮流选一个之前没选过的字母，将其变成任意一个其他的字母，A的目标是让结果最小，B目标是让结果最大，问理想最终结果是啥
从头开始，奇数位不是a的改成a，a改成b；偶数位不是z的改成z，z改成y即可
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <set>
#include<vector>
#include<cmath>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
ll t;
ll n,m;
string s;
char dat[10005][10005];
int main() {
ios::sync_with_stdio(0);
cin >> t;
while (t--)
{
cin >> s;
for (int i = 0; i < s.length(); i++) {
if (i % 2) {
if (s[i] == 'z')s[i] = 'y';
else s[i] = 'z';
}
else {
if (s[i] == 'a')s[i] = 'b';
else s[i] = 'a';
}
}
cout << s << '
';
}
}
B. The Great Hero
有个great hero和一系列怪物，great hero每次讨伐怪物可以给怪物造成固定伤害，同时讨伐的怪物也会对英雄造成伤害，给定每个怪物的血量和伤害，英雄的血量和伤害，问能不能全部讨伐怪物（讨伐成功时英雄死了也没关系
可以知道英雄最多可以一换一换掉一个怪物（受到一次致死伤害，而其他的怪物伤害都是要全部硬吃的，那么我们考虑换掉攻击力最高的怪物即可
剩下的部分模拟即可
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <set>
#include<vector>
#include<cmath>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
ll t;
ll n, m;
ll A, B;
string s;
P a[100000 + 5];
int main() {
ios::sync_with_stdio(0);
cin >> t;
while (t--)
{
cin >> A >> B >> n;
ll maxx = 0;
ll tol = 0;
for (int i = 0; i < n; i++) {
cin >> a[i].first;
}
for (int i = 0; i < n; i++) {
cin >> a[i].second;
}
sort(a, a + n);
int flag = 1;
for (int i = 0; i < n; i++) {
ll tmp = a[i].first * ceil(a[i].second * 1.0 / A);
if (i == n - 1) {
if (B + a[i].first < tmp)flag = 0;
}
else {
if (B < tmp) {
flag = 0;
break;
}
B -= tmp;
}
}
if (!flag)cout << "NO
";
else cout << "YES
";
}
}
C. Searching Local Minimum
交互题：给定1到n的一个重排，令a[0]和a[n+1]是无穷大，要在100次询问中找到任意一个i令a[i]<min（a[i-1],a[i+1])
二分搜索，每次查询mid以及左右的点，如果mid比右边的大那mid右边肯定存在i，mid比右边小那mid左边存在i
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <set>
#include<vector>
#include<cmath>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
ll t;
ll n, m;
ll A, B;
string s;
ll dat[100000 + 5] = {};
int main() {
// ios::sync_with_stdio(0);
cin >> n;
ll l = 1, r = n ;
dat[0] = 100000 + 5;
dat[n + 1] = 100000 + 5;
while (l<r)
{
ll m = (l + r) >> 1;
if (dat[m] == 0) {
cout << "? " << m << endl;
cin >> dat[m];
}
if (m + 1 <= n && dat[m + 1] == 0) {
cout << "? " << m+1 << endl;
cin >> dat[m+1];
}
if (m - 1 > 0 && dat[m - 1] == 0) {
cout << "? " << m-1 << endl;
cin >> dat[m-1];
}
if (dat[m + 1] > dat[m])r = m;
else l = m + 1;
}
cout << "! " << l << endl;
}
D. Painting the Array I&&II
给定一串数列，把它分为0和1两个子串，然后分别把两个子串中相邻的相同数字合并，求两个子串的最短/最长长度
最长：先记下两个子串中最后一个数字，a0和a1，然后判断当前的数字要放到哪个子串中
如果a0 == a1 == dat[i] ，dat[i]放哪都一样没用
如果a0 == dat[i]&&a1 != dat[i] 放入1子串
如果a0 != dat[i] && a1 != dat[i]，不能乱放，要比较a0和a1的数字的下一位的位置，放更近的，因为下一位相同数字越近，越容易被合并，更新后就不易合并
最短：如果a0 != dat[i] && a1 != dat[i]，要比较a0和a1的数字的下一位的位置，放更远的，
其他情况都可以直接合并，不用更新
I
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <set>
#include<vector>
#include<cmath>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
ll t;
ll n, m;
ll A, B;
string s;
ll dat[100000 + 5] = {};
vector<ll> pos[100000 + 5];
int main() {
ios::sync_with_stdio(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> dat[i];
pos[dat[i]].push_back(i);
}
ll a0 = 0, a1 = 0;
ll l0 = 0, l1 = 0;
for (int i = 0; i < n; i++)
{
pos[dat[i]].erase(pos[dat[i]].begin(), pos[dat[i]].begin() + 1);
ll nxt0 = pos[a0].empty() ? 1000000 : pos[a0][0];
ll nxt1 = pos[a1].empty() ? 1000000 : pos[a1][0];
if (dat[i] != a0 && dat[i] != a1) {
if (nxt0 < nxt1) {
l0++;
a0 = dat[i];
}
else {
l1++;
a1 = dat[i];
}
}
else if (dat[i] == a0&&dat[i]!=a1) {
l1++;
a1 = dat[i];
}
else if(dat[i] != a0 && dat[i] == a1){
l0++;
a0 = dat[i];
}
}
cout << l0 + l1;
}
II
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <set>
#include<vector>
#include<cmath>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
ll t;
ll n, m;
ll A, B;
string s;
ll dat[100000 + 5] = {};
vector<ll> pos[100000 + 5];
int main() {
ios::sync_with_stdio(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> dat[i];
pos[dat[i]].push_back(i);
}
ll a0 = 0, a1 = 0;
ll l0 = 0, l1 = 0;
for (int i = 0; i < n; i++)
{
pos[dat[i]].erase(pos[dat[i]].begin(), pos[dat[i]].begin() + 1);
ll nxt0 = pos[a0].empty() ? 1000000 : pos[a0][0];
ll nxt1 = pos[a1].empty() ? 1000000 : pos[a1][0];
if (dat[i] != a0 && dat[i] != a1) {
if (nxt0 > nxt1) {
l0++;
a0 = dat[i];
}
else {
l1++;
a1 = dat[i];
}
}
}
cout << l0 + l1;
}