A. Sakurako's Exam
分类讨论即可，当a为奇数，无法消去1，或者a==0且b为奇数时，无法消去2
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
void solve()
{
int a,b;
int flag=1;
cin>>a>>b;
if(a&1 ) flag=0;
else if(a==0 and b&1) flag=0;
if(flag) cout<<"Yes";
else cout<<"No";
cout<<endl;
}
signed main()
{
int t=1;
cin>>t;
while(t--) solve();
}
B. Square or Not
这题被hack了，假如是64，每行16个，虽然是美丽矩阵，但不是正方形，所以要保证第一个0的下标-1的平方为n，这样才可以确保是个正方形。
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
void solve()
{
int flag=1;
int n; cin>>n;
if(sqrt(n)!=(int)sqrt(n)) flag=0;
string s;
cin>>s;
int p=s.find('0');
if((p-1)*(p-1)!=n&&n!=4) flag=0;
if(flag) cout<<"Yes";
else cout<<"No";
cout<<endl;
}
signed main()
{
int t=1;
cin>>t;
while(t--) solve();
}
C. Longest Good Array
可以暴力枚举，也可以二分答案
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
void solve()
{
int a,b;
cin>>a>>b;
int l=2,r=1e9;
b-=a;
int mid;
while(l<=r)
{
mid=(l+r)>>1;
if(mid*(mid-1)/2<=b) l=mid+1;
else r=mid-1;
}
cout<<l-1<<endl;
}
signed main()
{
int t=1;
cin>>t;
while(t--) solve();
}
D. Sakurako's Hobby
题目问的是从i出发可以获得的黑块次数，一个排列可以分成有限个循环，比如1 2 4 5 3，可以分成1 和2和4 5 3 4，在第三个循环当中，从i=3或i=4或i=5出发经历的元素是一样的，所以得到的黑块次数也是一样的。
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
void solve()
{
int n;
cin>>n;
int p[n+1]={0},ans[n+1]={0};
int us[n+1]={0};
for(int i=1;i<=n;i++) cin>>p[i];
string s;
cin>>s;
for(int i=1;i<=n;i++)
{
if(us[i]) continue;
int sz=0;
//计算这个循环每个元素应该有多少个黑块次数
while(!us[i])
{
us[i]=1;
sz+=s[i-1]=='0';
i=p[i];
}
//循环遍历去赋值
while(us[i]!=2)
{
us[i]=2;
ans[i]=sz;
i=p[i];//会把一个循环中的数都遍历到
}
}
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
cin>>t;
while(t--) solve();
}
E. Alternating String
分为奇偶来讨论
如果是偶数，我们只需要统计奇数位上出现次数最多的字母和偶数位上出现次数最多的字母，然后用n减掉这两个数就是最小操作次数了
如果是奇数，肯定要选择一个位置删掉，然后再按偶数来进行操作，枚举位置来删除时，这个位置后面的每个字母的奇偶就会变化，比如abcab，奇数位上a（1）偶数位上a（4），删掉c以后呢，a（3），所以对应字母的奇数位数量要加到偶数位的数量上，偶数位上的同理，然后比较再取最大值即可
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin>>n;
string s;
cin>>s;
int ans=0;
if(n&1)
{
vector pre(2,vector<int>(30));//第0行为偶数数组 第1行为奇数数组
auto suf=pre;
//pre为当前位置前面奇偶位数上字符的数量
//suf为后面
for(int i=0;i<n;i++) suf[i&1][s[i]-'a']++;//统计奇数和偶数位上各字母的数量
for(int i=0;i<n;i++)
{
suf[i&1][s[i]-'a']--;//枚举删除的位置，删除完这个位置前
int res=0;
for(int k=0;k<2;k++){
//每个字母在奇数位和偶数位上都会有计数
//所以两次循环删除这位数以后，奇偶会互换
//所以把对应的字母的pre[奇][字母]+suf[偶][字母] 反之同理
int mx=0;
for(int j=0;j<26;j++)
{
int t=pre[k][j]+suf[k^1][j];
if(t>mx) mx=t;
}
res+=mx;
}
//从左往右遍历，所以pre是慢慢增加的
pre[i&1][s[i]-'a']++;
ans=max(ans,res);
}
ans=n-ans;
}else{
//偶数 直接找奇偶位置上的最大数量的字母
vector res(2,vector<int>(30) );
for(int i=0;i<n;i++) res[i&1][s[i]-'a']++;
for(int i=0;i<2;i++)
{
auto mx=*max_element(res[i].begin(),res[i].end());
ans+=mx;
}
ans=n-ans;
}
cout<<ans<<endl;
}
int main()
{
int t=1;
cin>>t;
while(t--) solve();
}