A.Balanced Substring
题意：给一串只含a和b的字符串，如果它的某个子串a和吧数量相等，则称这个子串是平衡的
求一个平衡子串的开始和结尾的下标
思路：
最简的做法就是遍历字符串，当你发现某个字符禾前面字符不相等的时候，那么这时候就是子串ab或者子串ba，
答案就出来了，如果字符串全是一个字母就是无解，我写的过于复杂的一点。。。。。
代码如下：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
char str[55];
bool okk=false;
scanf("%s",str);
int num[105],f[55];
memset(num,-1,sizeof(num));//num记录i这种状态第一次出现的位置
memset(f,0,sizeof(f));//f用来记录到i之前的字符串a和b的情况
num[0]=0;
for(int i=1;i<=n;i++)
{
if(str[i-1]=='a')
{//是a就+1
f[i]=f[i-1]+1;
if(num[abs(f[i])]>=0)//为什么要取绝对值，其实就是想省空间或者说f[i]是负数再处理麻烦
{//如果说f[i]在前面出现过，那么（num[absf[i]],i]之间a和b的数量相等
printf("%d %d\n",num[abs(f[i])]+1,i);//上面解释的时候是左开右闭，
//为什么是这样子，自己模拟一下就知道了
okk=true;
break;
}
else
num[abs(f[i])]=i;
}
else
{//b就-1
f[i]=f[i-1]-1;//原理同上
if(num[abs(f[i])]>=0)
{
printf("%d %d\n",num[abs(f[i])]+1,i);
okk=true;
break;
}
else
num[abs(f[i])]=i;
}
//cout<<f[i]<<endl;
}
if(!okk)//如果没有，那么就是无解
printf("-1 -1\n");
}
return 0;
}
B.Chess Tournament
题意:每个人对比赛都有一种期望，要么是所有比赛都不能输要么是最少赢一场，给你n个人的期望，1代表所有比赛不输
2代表最少赢一场，求是否存在一种结果满足所有人的要求
思路:其实样例有提升一点点，就全1的时候，比赛全是平局，那么我们遇到两人都是希望不输的时候
那么他们之间的比赛结果是平局即可，对于最少赢一把的人来讲，
如果说只有两人希望赢一把，那么他们之间只有一场比赛，不能满足要求，
但是又三人及以上比赛场次就>=希望赢一把的人数，就可以满足他们的要求了
这样子就基本上确定了，只有赢一把的人数>0&&<3无解，其他均有解
emm，注意任意两个人之间只进行一场比赛，所以两个人之间的结果是关于主对角线相反的
代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,sum[5];
memset(sum,0,sizeof(sum));
char str[55];
scanf("%d",&n);
//cout<<n<<endl;
scanf("%s",str);
for(int i=0;i<n;i++)
{//统计情况2的人数
sum[str[i]-'0']++;
}
//cout<<"--------------\n";
if(sum[2]>0&&sum[2]<3)
{//如果>0&&<3就是无解
printf("NO\n");
continue;
}
//cout<<"-------------------\n";
char mp[55][55];
for(int i=0;i<n;i++)
{//处理掉情况1的人
for(int j=0;j<n;j++)
{
if(i==j)/和自己比赛
mp[i][i]='X';
else if((str[i]-'0')==1&&(str[j]-'0')==1)
{//i和j都希望不输就是平局
mp[i][j]='=';
mp[j][i]='=';
}
else if((str[i]-'0')==1&&(str[j]-'0')==2)
{//i希望不输，但是j只希望赢一把，所有就是i赢j输
mp[i][j]='+';
mp[j][i]='-';
}
else if((str[i]-'0')==2&&(str[j]-'0')==1)
{
mp[i][j]='-';
mp[j][i]='+';
}
}
}
//cout<<"-------------------"<<endl;
int f=-1;
for(int i=0;i<n;i++)
{//剩下的处理i和j都是情况2的人
if((str[i]-'0')==1)
continue;
int j;
if(f==-1)
f=i;//从0开始第一个情况2的人
bool okk=false;//用来记录i是否最少赢一场，毕竟最后一个情况2的人后面没有人可以赢了
for(j=i+1;j<n;j++)
{//i赢了后面全是情况2的人
if((str[j]-'0')==2)
{
mp[i][j]='+';
mp[j][i]='-';
okk=true;
}
}
if(!okk)
{//对于最后一个人，让他赢第一个情况2的人
mp[i][f]='+';
mp[f][i]='-';
}
}
printf("YES\n");
for(int i=0;i<n;i++)
{//输出结果
for(int j=0;j<n;j++)
printf("%c",mp[i][j]);
printf("\n");
}
}
return 0;
}
C.Jury Meeting
题意:
给n个人，每个人有a[i]给建议，从第一个人开始讲自己的建议，每次一个人只讲一个建议
1-n讲完一次后又从1开始循环，如果说第i个人讲完了自己的建议就跳过
当所有人的顺序可以改变的时候，有多少种顺序是满足所有人都不会连续讲自己的建议
思路：
首先确定什么情况才会出现一个人连续讲，或者说确定什么情况才会出现一个人不会连续讲
就是对于这样子一种情况进行解析
11111假设这是最多发言次数的人的每次发言，我们需要把这些隔开，那么我们最少需要多少个空才能把1隔开
很显然4个空格是最少的这种情况空格一定在1后面出现，五个空格就比较随意放了，基于这个结论，分类讨论
1、如果说max(a[i])出现的次数大于1，那么这两个人（几个人）可以轮流讲就不会出现一个人连续讲两次
2、如果说max(a[i])出现次数==1，那么第二多的建议的人的建议！=max(a[i])-1，这样的话
无论如何max(a[i])这个人都要连续讲，因为没有人给他轮换，他在最后最少要连续讲两次
3、如果说max(a[i])==1&&第二多的建议==max(a[i])-1，这样子的话，如果说第二多的人每一轮在max(a[i])后面讲
这样子的话就刚刚好把max(a[i])隔开
代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
int mx=-1,num=0,mn,nun=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int t;
scanf("%d",&t);
if(t>mx)
{
mn=mx;//记录次多建议
nun=num;//次多建议的次数
mx=t;//最多建议
num=1;//最多建议的次数
}
else if(t==mx)
{
num++;
}
else if(t<mx&&t>mn)
{
mn=t;
nun=1;
}
else if(t==mn)
{
nun++;
}
}
if(num>1)
{//最多建议的人多于1，那么任意排就是n!
long long ans=1;
for(int i=2;i<=n;i++)
ans=(ans*(i%998244353))%998244353;
cout<<ans<<endl;
}
else
{
//如果是次多建议刚好等于max-1，那么全排列是n!但是次多建议的人全在最多建议的人前面是不满足条件的
//不满足要求的条件情况有nun!(次多的人任意排)*1(最多建议的人)*(nun+2)*(nun+3)*n!
//次多人排在最多人前面是nun! * 1剩下的人插缝排，此时最少nun+2个缝(左右两边也算)每多一个人就多一个缝
//所以结果是n!-(nun!*1*(nun+2)*(nun+3)*``````*n)
//注意n!==nun!*1*(nun+2)*(nun+3)*``````*n *nun+1
//所以答案是nun!*1*(nun+2)*(nun+3)*``````*n *nun
//就是在求n！的时候在i==nun+1时候i-1即可
long long ans=1;
for(int i=2;i<=n;i++)
{
if(i!=nun+1)
ans=(ans*(i%998244353))%998244353;
else
ans=(ans*((i-1)%998244353))%998244353;
}
if(mn+1<mx)//次多建议小于max-1就无解
ans=0;
cout<<ans<<endl;
}
}
return 0;
}
D.Inconvenient Pairs
题意：
给n个竖着的街道，m个横着的街道(街道无限长)，k个人，人保证在街道上
求有多少对人两人按街道走的距离大于曼哈顿距离，曼哈顿距离就是|x1-x2|+|y1-y2|
思路：
考虑怎么样的两人之间的路程大于曼哈顿距离或者说怎么样的两个人之间的距离是曼哈顿距离
横着的街道无论如何都会和竖着的街道交接(无限长)，那么一个人在横着的街道，一个人在竖着的街道，
这样子就保证他之间的路程是等于曼哈顿距离,这样子如果一个人在横竖街道的交点，那么他和任意一个人都是曼哈顿距离
如果两个人在同一个竖着或者横着的街道，他们之间的距离也是曼哈顿距离
那么剩下的情况就是两个人都在横着（竖着）的街道且两个街道不在同一个街道的情况了
仔细看图就会发现，假设两个人的坐标是(x1,y1)(x2,y2)，且都在竖着的街道
如果（y1,y2）之间没有一个横着的街道(假设(y1<y2))，
那么他们的距离就会大于曼哈顿距离
也就是说横着的街道把竖着的街道分成了(m+1)块，(m+1)是因为左右两边也算
竖着的街道把横着的街道分成了（n+1）块
同一块且不在同一个街道的人之间的距离大于曼哈顿距离
代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
vector<int> x[1000005],y[1000005];//记录这在x[i]块的人的横着的街道的位置
int cnt[1000005];//记录这一块多少人
bool ux[1000005], uy[1000005];//记录出现的街道的x位置，y位置
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m,k;
scanf("%d %d %d",&n,&m,&k);
vector<int> xx, yy;
xx.push_back(1000005);//防止越界，保证upper_bound可以找到值
yy.push_back(1000005);//毕竟如果一个人在竖着的街道，他的y值大于横着的街道最大位置
//为啥没有设置下界呢，因为小于y值最小，upper_bound找到的是最小
memset(ux,false,sizeof(ux));//所有街道位置不曾出现
memset(uy,false,sizeof(uy));
for(int i = 0; i < n; i ++ )
{
int t;
scanf("%d", &t);
xx.push_back(t);
ux[t]=true;//x=t出现一个竖着的街道
}
for(int i = 0; i < m; i ++ )
{
int t;
scanf("%d", &t);
yy.push_back(t);
uy[t]=true;//y=t出现一个横着的街道
}
for(int i=0;i<k;i++)
{
int a,b;
scanf("%d %d",&a,&b);
if(ux[a] && uy[b])
continue;//如果在横竖街道
if(ux[a])//点在竖着的街道上，用平行于y轴的街道划分区域
{//记录在这区域里的所有的x的坐标
y[upper_bound(yy.begin(),yy.end(),b)-yy.begin()].push_back(a);
}
else
{//同上
x[upper_bound(xx.begin(),xx.end(),a)-xx.begin()].push_back(b);
}
}
long long ans=0;
memset(cnt,0,sizeof(cnt));
for(int i=0;i<=n;i++)
{//对于每一块都进行计数
//(x[i-1],x[i])之间的人数是x[i].size()
ans=ans+(long long)x[i].size()*x[i].size();//两个人任意组合
//关于自己选自己，我们在去掉同一个街道的时候会减去
for(int j=0;j<x[i].size();j++)
cnt[x[i][j]]++;//在这一块，但是在横着街道y的人数==cnt[x[i][j]]
for(int j=0;j<x[i].size();j++)//要去掉同一块但是在同一个街道的人数
ans=ans-(long long)(cnt[x[i][j]]*cnt[x[i][j]]),cnt[x[i][j]]=0;
//cnt[x[i][j]]是因为不能确定那些x[i][j]出现过，所以减去过的街道就清0
x[i].clear();//clear是因为多样例，需要清空x[i]给下一个样例用
}
for(int i=0;i<=m;i++)
{
ans=ans+(long long)y[i].size()*y[i].size();
for(int j=0;j<y[i].size();j++)
cnt[y[i][j]]++;
for(int j=0;j<y[i].size();j++)
ans=ans-(long long)(cnt[y[i][j]]*cnt[y[i][j]]),cnt[y[i][j]]=0;
y[i].clear();
}
//注意文明计算的时候是一个人选任意其他人，这样子a选了b，b还会选a,所以/2
cout<<ans/2<<endl;
}
return 0;
}
记录一下思路，嗯，以后拉学弟写这套题的时候，我讲解的时候不需要重新看题了
最近实在是事情多，题写的好少，菜到焦虑
