A
题意分析
把给定的坐标的那一行和那一列的其他所有坐标都输出来
C++代码
#include<iostream>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
string s;
cin>>s;
for(int i=1;i<=8;i++){
if(i+'0'!=s[1])cout<<s[0]<<i<<endl;
}
for(int i=0;i<8;i++){
if(i+'a'!=s[0])cout<<(char)(i+'a')<<s[1]<<endl;
}
}
return 0;
} B
题意分析
正着做不是很方便，可以倒着做，具体看代码
C++代码
#include<iostream>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
string s,t;
cin>>s;
int cnt1=0,cnt2=0;//cnt1和cnt2记录应该删除的小写字母的数量和大写字母的数量
//倒着从后往前做，遇到b就cnt1++，遇到B就cnt2++
//然后每次遇到小写字母，就判断cnt1是否为0，若为0，则不加上该字符，否则加上，大写字母同理
for(int i=s.size()-1;i>=0;i--){
if(s[i]=='b')cnt1++;
else if(s[i]=='B')cnt2++;
else{
if(s[i]>='a'&&s[i]<='z')
if(cnt1)cnt1--;
else t+=s[i];
else
if(cnt2)cnt2--;
else t+=s[i];
}
}
for(int i=t.size()-1;i>=0;i--)cout<<t[i];//逆序输出结束后的字符串
cout<<endl;
}
return 0;
}C
题意分析
直接找出现次数最多的字母出现的次数maxx，然后进行判断
1、maxx>n-maxx，就要删除(n-maxx)次，剩余maxx-(n-maxx)个数
2、maxx<=n-maxx，看n是奇数还是偶数，奇数剩1个，偶数剩0个
总结：输出max(n%2,maxx-(n-maxx))
如果看不习惯可以分开写
C++代码
#include<iostream>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n,cnt[26]={0},maxx=0;
cin>>n;
string s;
cin>>s;
for(int i=0;i<s.size();i++){
cnt[s[i]-'a']++;
maxx=max(maxx,cnt[s[i]-'a']);
}
cout<<max(n%2,maxx-(n-maxx))<<endl;
}
return 0;
}D
题意分析
二分
二分每个k，然后判断k是否可行
初始L=0,R=0
从前往后遍历每个区间，假设当前枚举到了区间i
当前可走到的区间范围为[L-k,R+k]
然后判断区间 [l[i],r[i]] 和 区间 [L-k,R+k] 是否有交集，
1、如果没有，直接返回false
2、如果有，更新L=max(l[i],L-k)，R=min(r[i],R+k)，必须要落在区间i内
然后接着枚举，如果到了最后一个区间都可行的话，就返回true
C++代码
#include<iostream>
using namespace std;
const int N=200010;
int l[N],r[N];
int n;
bool check(int k){
int L=0,R=0;
for(int i=1;i<=n;i++){
int a=L-k,b=R+k;//a,b表示可以跳到的最左边和最右边
if(a>r[i]||b<l[i])return false;//如果[a,b]与当前区间[l[i],r[i]]没有交集，表示不合法
L=max(a,l[i]),R=min(b,r[i]);//更新当前步骤可以到达的合法区间
}
return true;
}
int main(){
int t;
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++)cin>>l[i]>>r[i];
int l=0,r=1e9,ans=-1;
while(l<r){
int mid=l+r>>1;
if(check(mid))ans=mid,r=mid;
else l=mid+1;
}
cout<<l<<endl;
}
return 0;
}E
题意分析
加法不能有进位，直接枚举每一位就行，每一位的三个数的和不能超过9
加起来后的数位和＝原本的数位和。
如果不产生进位，那么数位和不变；如果产生一次进位，数位和会增加9，所以不能产生进位
举个例子：8+18+0=26
但是17=8+1+8!=2+6=8，原因就是8+18的过程中有个进位，数位和就比原来的数位和多9
C++代码
#include<iostream>
using namespace std;
typedef long long LL;
int cnt[10];
int n;
void solve(){
cin>>n;
LL ans=1;
while(n){
ans*=cnt[n%10];
n/=10;
}
cout<<ans<<endl;
}
int main(){
int t;
cin>>t;
for(int i=0;i<=9;i++)
for(int j=0;i+j<=9;j++)
for(int k=0;i+j+k<=9;k++)
cnt[i+j+k]++;
while(t--){
solve();
}
return 0;
}F
题意分析
如果某个位置开始连续n个数字都是递增的，那么这个数字可以作为最终结果第一个位置上的数，把这个数移动到第一个位置有两种方案：
一种是直接移位，一种是先翻转再移位再翻转回来
如果某个位置开始连续n个数字都是递减的，那么这个数字可以是最终结果最后位置的数，
同样有两种方案：
一种是先移位再翻转，一种是先翻转再移位
C++代码
#include<iostream>
using namespace std;
const int N=200010,INF=1e9;
int a[N*2];
int n;
void solve(){
cin>>n;
for(int i=0;i<n;i++)cin>>a[i],a[i+n]=a[i];
int ans=INF;
for(int i=0;i<n;i++){
int j=i;
while(j+1<2*n&&a[j+1]>=a[j])j++;//a[i]~a[j]是非递减序列
for(int k=i;k<=j&&k<n;k++){
int len=j-k+1;
if(len>=n){
ans=min(ans,(n-k)%n);//直接移位
int rev=n-1-k;//翻转的次数
ans=min(ans,n-1-rev+2);//先翻转再移位
}
}
i=j;
}
for(int i=0;i<n;i++){
int j=i;
while(j+1<2*n&&a[j+1]<=a[j])j++;//a[i]~a[j]非递增序列
for (int k=i;k<=j&&k<n;k++){
int len=j-k+1;
if(len>=n){
ans=min(ans,(n-k)%n+1);
int rev=n-1-k;
ans=min(ans,n-1-rev+1);
}
}
i=j;
}
if(ans>INF/2)ans=-1;
cout<<ans<<endl;
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
}G
题意分析
显然，这题的图是基环树，若干个基环树
对所有有关联的灯泡建一条有向边，显然，建完之后可能有环，对于环外的点，直接用拓扑序列做，遇到1就将该节点进入答案序列，然后给他变成0（注意关联节点的状态也要变），遇到0就不进入答案序列
做完拓扑序列后，对于环内的点，必定每个点的入度都为1，因为每个点的出度最多为1，而又要形成环，所以不可能有节点的入度大于1
所以直接用bfs依次找出每个环，存储环内的节点，记录环上的节点状态为1的个数，如果有奇数个1，则不可能关闭所有的灯，否则一定可以关闭所有的灯
对于怎样记录环内的点怎样记入答案序列？
用t表示当前状况，初值为0，遇到1取反，状态为1的是一种答案，状态为0的为另一种答案。
判断两种答案哪个操作次数少就用哪个
直接看代码，看的时候一定要画个图模拟一下，不然有点难看懂
C++代码
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N=200010;
int st[N],g[N],d[N];
int n;
string s;
void solve(){
cin>>n>>s;
for(int i=0;i<=n;i++)d[i]=0,st[i+1]=s[i]-'0';//st存储每个灯的状态
for(int i=1;i<=n;i++){
cin>>g[i];//g[i]存储与灯i相关联的灯
d[g[i]]++;//建一条虚拟边i->g[i],g[i]的入度加一
}
queue<int> q;
vector<int> ans;
//先对环以外的所有点跑一遍拓扑序列
for(int i=1;i<=n;i++)
if(!d[i])
q.push(i);//入度为0的点入队
while(q.size()){
int u=q.front();
q.pop();
int v=g[u];
d[v]--;
if(st[u])st[v]^=1,ans.push_back(u);//如果该灯是亮的,则要关,与它关联的灯的状态也要改变
if(!d[v])q.push(v);//如果v的入度为0，则入队
}
//剩下入度不为0的点都是环内的点
int flag=0;
for(int i=1;i<=n;i++){//枚举所有环的起点
if(d[i]){//入度不为0则为某个环上的点，暂定为起点
q.push(i);
vector<int> tmp;//记录环内的所有点
int t=0,cnt=0;//t表示：按照当前遍历顺序，某个点是否要操作 cnt记录一共需要操作的次数
while(q.size()){
int u=q.front();
q.pop();
tmp.push_back(u);
d[u]=0;//环内的点一定只有一条边指向它，因为所有点的出度都为1
int v=g[u];
if(st[u])t^=1;//当前灯是开着的，则改变t的状态
//cout<<"t="<<t<<endl;
cnt+=t;//t=1表示在该点要进行操作，t=0表示在该点不用进行任何操作
if(d[v])q.push(v);
}
//1、如果只有奇数个状态为1的灯泡，则不可能关掉所有的灯
if(t){
flag=1;
break;
}
//2、有偶数个开着的灯，且至少需要操作cnt次
t=0;
if(cnt*2<=tmp.size()){//操作次数<=环内总数的一半，则直接按遍历顺序，每次t=1操作
for(auto x:tmp){
if(st[x])t^=1;
if(t)ans.push_back(x);
}
}else{
for(auto x:tmp){//否则反着来，t=0进行操作
if(st[x])t^=1;
if(t==0)ans.push_back(x);
}
}
}
}
if(flag==0){
cout<<ans.size()<<endl;
for(auto x:ans)cout<<x<<" ";
cout<<endl;
}else cout<<-1<<endl;//某个环内有奇数个灯泡亮着
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}