一场比一场der了。
A. Yet Another String Game
题意
两个人轮流操作一个字符串，操作后的字母不能和之前相同，一个人想让字典序尽可能大，另一个想让字典序尽可能小，求操作后的字符串
题解
签到题，每次选择最优解。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
cin>>_;
while(_--){
string s;
cin>>s;
for(int i=0;i<s.size();i++){
if(i%2==0){
if(s[i]=='a') s[i]='b';
else s[i]='a';
}
else{
if(s[i]=='z') s[i]='y';
else s[i]='z';
}
}
cout<<s<<endl;
}
return 0;
}
B. The Great Hero
题意
一个英雄要打n个怪物，英雄和每个怪物有攻击力和生命值。可以任意选择一个怪物打一回合，之后二者生命值分别扣减对方攻击力，问能否打完全部怪物（打完所有怪物英雄牺牲也算yes）。
题解
主要在于“打完所有怪物英雄牺牲也算yes”，所以我们必须把攻击力最高的放在最后一个打。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
cin>>_;
while(_--){
ll A,B,n;
cin>>A>>B>>n;
pair<ll,ll> a[n];
int f=0;
for(int i=0;i<n;i++) cin>>a[i].first;
for(int i=0;i<n;i++) cin>>a[i].second;
for(int i=0;i<n;i++){
if(a[i].second%A){
B-=a[i].first*((a[i].second/A)+1);
}
else{
B-=a[i].first*((a[i].second/A));
}
if(B<=0&&i==n-1&&B+a[i].first>0) break;
else if(B<=0)f=1;
}
if(f==1) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}
C. Searching Local Minimum
题意
一道交互题，给一个1-n的数组变换后的数组，在100次查询内确定区域最小值的位置。
题解
结合数据范围，很容易想到二分查找。因为a[i-1]>a[i]&&a[i+1]>a[i]，那么，如果a[mid+1]>a[mid]，就在左区间，反则在右区间。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
cin>>_;
int a[_+2];
memset(a,0,sizeof(a));
a[0]=imax;
a[_+1]=imax;
int l=1;
int r=_;
while (l < r)
{
int mid = (l + r) >> 1;
if (a[mid]==0) cout << "? " << mid << endl, cin >> a[mid];
if (a[mid + 1]==0) cout << "? " << mid + 1 << endl, cin >> a[mid + 1];
if (a[mid] < a[mid + 1]) r = mid;
else l = mid + 1;
}
cout << "! " << l;
return 0;
}
D1. Painting the Array I
题意
找一个数组的两个子序列，子序列中不能出现相邻的数，使得两个子序列长度和最大。
题解
施工中。
