(23-24赛季)稠州常规赛02题解
T1 循环节的判定
思路
本题就是水题，模拟一边即可，解法有很多种，自己尝试！
T2 逛画展
思路1
本题类似与数列分组，那么可以考虑二分，因为这种众多解中求解最优解的题目，多数和二分有关，我们二分一下长度，然后写一个check函数对这个长度是否能看完所有画家的画进行验证，时间复杂度为O(NlogN).
思路2
当然本题可以用双指针来做，因为框定所有的画是题目要求的。
在这种情况下我们可以利用L,R前后指针进行区间纳入数值！ 时间复杂度是O(N)!
//k记录当前区间中有多少画家的图画
while(l<=r && r<=n)
{
if(k==m)//判断是否符合要求
{
if(ans>r-l+1)
{
ans=r-l+1;//ans记录最小区间长度
ll=l; rr=r;
//ll记录最小区间的左端点,rr记录最小区间的右端点
}
b[a[l]]--;
if(b[a[l]]==0) k--;
l++;
}
else{
r++;
b[a[r]]++;
if(b[a[r]]==1) k++;
}
}T3 小美的字符串变换
思路
本题是一个稍微变化一下的求解联通块的问题！
1利用循环枚举出矩形的形态！
for(int i = 1; i <= n; i ++){
if(n % i == 0){
int sum = 0;
for(int j = 1; j <= n; j ++){
if(vis[j] == 0){
dfs(j , n / i , a[j]);
sum ++;
}
}
memset(vis , 0 , sizeof(vis));
ans = min(ans , sum);
}
}2利用dfs或者bfs对矩形进行联通块数量求解，直接染色即可！
void dfs(int x , int y , char z){
if(z != a[x] || vis[x] == 1)
return ;
vis[x] = 1;
if(x + y <= n)
dfs(x + y , y , z);
if(x % y != 0)
dfs(x + 1 , y , z);
if(x % y != 1)
dfs(x - 1 , y , z);
if(x + y >= 1)
dfs(x - y , y , z);
return ;
} 本题是美团的算法岗位招人题目，还是考验大家对基础算法的理解和掌握！
T4 一道简答题
本题考察大家对上周线段树的掌握情况，当然这种区间修改，单点查询的题目，用树状数组也是很合适的！
考虑本题只会修改1和0，那么也就是我只需要打一个标记表示该区间的值是1或者0即可！
所以建树就不用了，只需要一个updata和push_down,query即可！
void push_down(int k)
{
if(tag[k])
{
tag[k<<1]^=1;
tag[k<<1|1]^=1;
tag[k]=0;
}
}
void updata(int k,int l,int r,int x,int y)
{
if(x<=l&&r<=y)//如果当前区间完全被修改区间包含，整体xor
{
tag[k]^=1;
return;
}
push_down(k);//下传标记
int mid=(l+r)>>1;
if(x<=mid)updata(k<<1,l,mid,x,y);
if(mid<y)updata(k<<1|1,mid+1,r,x,y);
}
int query(int k,int l,int r,int x)
{
if(l==r)return tag[k];
push_down(k);//下传标记
int mid=(l+r)>>1;
if(x<=mid)return query(k<<1,l,mid,x);
else return query(k<<1|1,mid+1,r,x);
}思路2
树状数组其实和它思路是一样的，也是区间修改，然后下传即可！
下周大家可以跟随梓杰同学学习下树状数组，然后对比下两种结构的差别！
T5车站分级
思路
本题考察拓扑排序，主要是大家要学会思维转换！
难点
本题其实难点是建图，建图完成以后，就是正常的拓扑排序即可！
把每个车站看成图的一个点，如果从 a[1]到 a[s]中，停靠的站点为 a[1],a[2],…,a[s]，则意味着
从 a[1]到 a[s]中没有停靠的车站的等级都小于 a[1],a[2],…,a[s]的等级，所以我们把这些站点分别 引一条有向边到 a[1],a[2],…,a[s]对应的点，比如样例 1 建立的图如下：
for(int i=1;i<=m;i++) {
memset(is,0,sizeof(is));//is表示是否是停靠站
scanf("%d",&s);
for(int j=1;j<=s;j++)
scanf("%d",&st[j]),is[st[j]]=true;
for(int j=st[1];j<=st[s];j++)
if(!is[j]) //枚举站点，若不是已停靠的就小于所有停靠站的等级
for(int k=1;k<=s;k++) //枚举已停靠站点
if(!tuopu[j][st[k]]) tuopu[j][st[k]]=1,de[st[k]]++;//tuopu[i][j]表示j>i的级别，如上
}建图成功后，就是普通的拓扑排序了！
具体看代码注释
for(int i=1;i<=m;i++) {
memset(is,0,sizeof(is));//is表示是否是停靠站
scanf("%d",&s);
for(int j=1;j<=s;j++)
scanf("%d",&st[j]),is[st[j]]=true;
for(int j=st[1];j<=st[s];j++)
if(!is[j]) //枚举站点，若不是已停靠的就小于所有停靠站的等级
for(int k=1;k<=s;k++) //枚举已停靠站点
if(!tuopu[j][st[k]]) tuopu[j][st[k]]=1,de[st[k]]++;//tuopu[i][j]表示j>i的级别，如上
}
do{
top=0;
for(int i=1;i<=n;i++)
if(de[i]==0&&!bo[i]) {
tt[++top]=i,bo[i]=true;//开始将出度为0的点删掉
}
for(int i=1;i<=top;i++)
for(int j=1;j<=n;j++)
if(tuopu[tt[i]][j]) tuopu[tt[i]][j]=0,de[j]--;//去边去点
ans++;
} while(top);T6 公平分割
思路
其实就是一个背包问题，我们考虑最大容量下的最大价值，但是考虑天平是对半分的，那么我们通过循环，找到第一个过半的即可！
for(int i=1;i<=n;i++)
for(int j=sum;j>=a[i];j--)
dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
for(int i=1;i<=sum;i++)
if(dp[i]>=(sumb+1)/2){
cout<<sum-i;
break;
}
```