A.给abc的某个排列，问能否最多交换一次让排列变成abc
直接看有几个不在原位就行
查看代码
#include<iostream>
using namespace std;
void solve()
{
char a,b,c;
cin>>a>>b>>c;
int ans=0;
if(a!='a')ans++;
if(b!='b')ans++;
if(c!='c')ans++;
if(ans<=2)
cout<<"YES\n";
else cout<<"NO\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)solve();
return 0;
}B.给n个数，让你选择一个数+1，让这n个数的乘积最大
排序，给最小的+1然后乘积即可
查看代码
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,a[10];
ll ans=1;
void solve()
{
ans=1;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+1+n);
a[1]++;
for(int i=1;i<=n;i++)ans*=a[i];
cout<<ans<<'\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)solve();
return 0;
}C.给一个靶子，不同区域是不同分数，给定中靶情况问得分，模拟即可
#include<iostream>
using namespace std;
char c;
void solve()
{
int ans=0;
for(int i=1;i<=10;i++)
{
for(int j=1;j<=10;j++)
{
cin>>c;
if(c=='X')
{
if(i==1||j==1||i==10||j==10)
ans+=1;
else if(i==2||j==2||i==9||j==9)
ans+=2;
else if(i==3||j==3||i==8||j==8)
ans+=3;
else if(i==4||j==4||i==7||j==7)
ans+=4;
else ans+=5;
}
}
}
cout<<ans<<'\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)solve();
return 0;
}D.给一段黑白相间的序列，每次可以选择k个连续的格子变成白的，问最少多少次全白，贪心即可，找到黑的，看看在不在前面使用的范围内，不在就用一次
查看代码
#include<iostream>
using namespace std;
void solve()
{
int n,k,ans=0,now=-1;
cin>>n>>k;
string s;
cin>>s;
for(int i=0;i<s.length();i++)
{
if(s[i]=='B'&&now<i)
{
now=i+k-1;
ans++;
}
}
cout<<ans<<'\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)solve();
return 0;
}E.有n格水槽，每格有珊瑚，问里面的水最小多高能填满不少于x个格子，二分答案，然后判断能不能即可
查看代码
#include<iostream>
using namespace std;
typedef long long ll;
int n,x,a[200005];
int check(int m)
{
ll sum=0;
for(int i=1;i<=n;i++)
if(m>=a[i])sum+=m-a[i];
if(sum>x)return 0;
return 1;
}
void solve()
{
cin>>n>>x;
for(int i=1;i<=n;i++)cin>>a[i];
ll l=1,r=5e9;
while(l<r)
{
int mid=(l+r+1)>>1;
if(check(mid))l=mid;
else r=mid-1;
}
cout<<l<<'\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)solve();
return 0;
}F.有n棵树，每棵树有高度和价值，当一棵树能被前一棵树整除时可以连续取这棵树的价值，问在总价值不超过k的情况下最多能取多少棵树
双指针即可，l来存树的左区间，官方是二分
查看代码
#include<iostream>
using namespace std;
int n,k;
int a[200005],b[200005];
void solve()
{
cin>>n>>k;
int ans=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]<=k)ans=1;
}
for(int j=1;j<=n;j++)
cin>>b[j];
int l=1,tmp=a[1];
for(int i=2;i<=n;i++)
{
if(b[i-1]%b[i]==0)
{
if(a[i]+tmp<=k)
{
tmp+=a[i];
ans=max(ans,i-l+1);
}
else
{
tmp+=a[i];
while(tmp>k&&l<=i)tmp-=a[l++];
}
}
else
{
tmp=a[i];
l=i;
if(tmp>k)l++,tmp=0;
}
}
cout<<ans<<'\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)solve();
return 0;
}G.给一个由A,B组成的串,AB可以替换成BC，BA可以替换成CB，问最多替换多少次。
不难看出，替换AB，相当于B左移AAAA<-B，替换BA相当于B右移B->AAAAA，最多可能的替换次数是A的个数(没B就为0)
而可能对答案有影响的是一个B选择左移或者右移。不难想到，当B位于开头或者结尾的时候，B都只有一个方向移动，答案就是A的个数，
如果连续两个B，那么它们就可以一个左移，一个右移，答案也是A的个数
其它情况的时候，B的移动无法覆盖整个串，我们只要舍弃最短的连续A串即可
查看代码
#pragma GCC optimize(2)
#include<iostream>
using namespace std;
typedef long long ll;
void solve()
{
string s;
int ans=0,tt=0;
cin>>s;
int cntt=0,mina=2e5;
for(int i=0;i<s.length();i++)
{
if(s[i]=='A')ans++,cntt++;
else
{
tt++;
mina=min(mina,cntt);
cntt=0;
if(i>0&&s[i-1]=='B')mina=0;
}
}
mina=min(mina,cntt);//B是不是尾
if(tt==0)//没B
{
cout<<"0\n";
return;
}
cout<<ans-mina<<"\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)solve();
return 0;
}H.a,b两人位于一个n点n条边的联通无向图上，a,b每次可以往旁边一个节点走或者不走，a在追b，b知道a下一步往哪里走，同时行动，问b能否不被a抓住。
n点n边，必然有环，b想逃脱必须到环上而且不能被a截住。问题就变成了 判环+b到环的距离及交点+a到交点的距离
如果b在环上，那么可以逃脱，ba在一个点，跑不了，如果a能在b到环上之前先到了b上环的点，跑不了其余情况都能跑。
本蒟蒻太菜了，当时没想到bfs没调出来，看的jiangly大佬的
查看代码
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
void solve()
{
int n,a,b;
cin>>n>>a>>b;
a--,b--;
vector<vector<int> >v(n);
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
x--,y--;
v[x].push_back(y);
v[y].push_back(x);
}
auto bfs=[&](int s)//用来求s到其它点的距离
{
vector<int>dis(n,-1);
queue<int>q;
q.push(s);
dis[s]=0;
while(!q.empty())
{
int x=q.front();
q.pop();
for(auto y:v[x])
{
if(dis[y]==-1)
{
dis[y]=dis[x]+1;
q.push(y);
}
}
}
return dis;
};
auto dis=bfs(b);
int u=-1;//存环上的一点
vector<int>fa(n),dep(n);//存这个点从哪个点来的，以及它的dfs深度
vector<bool>vis(n);//是否被访问过了
auto dfs=[&](auto self,int x)->void
{
vis[x]=1;
for(auto y:v[x])
{
if(!vis[y])
{
fa[y]=x;
dep[y]=dep[x]+1;
self(self,y);
}
else if(dep[y]<dep[x]-1)//意思是y访问过了而且不是x的fa，换言之是环
{
for(int i=x;;i=fa[i])
{
if(u==-1||dis[i]<dis[u])//求出环上距离b最近的点
u=i;
if(i==y)break;
}
}
}
};
dfs(dfs,0);
if(bfs(u)[a]>dis[u])
cout<<"YES\n";
else cout<<"NO\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)solve();
return 0;
}