Problem 1. Leaders
\(\mathcal{Farmer \ John}\) 共有 \(n\) 头奶牛，品种用字符 \(\mathsf{G}\) 或 \(\mathsf{H}\) 表示。每一头牛有一个管辖区间 \([i , E_i]\)
称一头奶牛为领袖，仅当其能管辖所有与自己同品种的奶牛，或者能管辖另一种奶牛的领袖，或者二者都满足。
在两种奶牛中各选出一只作领袖，问可能的领袖对数。
\(2 \leq n \leq 10^{5}\) ，数据保证有解。
先统计能管辖到所有奶牛的领袖对 \((p,q)\) ，共有两种情况 \((p < q)\)：
-
\(p,q\) 均能管辖到同品种的所有奶牛
显然这样的 \((p,q)\) 最多有一对。
用前缀和预处理出 \(preG_i\) 表示前 \(i\) 只奶牛中品种为 \(\mathsf{G}\) 的数量，\(preH_i\) 表示前 \(i\) 只奶牛中品种为 \(\mathsf{H}\) 的数量。
于是可以 \(O(1)\) 求出 \([i , E_i]\) 中与自己同品种奶牛的数量，判断其是否等于总共的同品种奶牛数量即可。 -
\(q\) 能管辖同品种的所有奶牛，\(p\) 能管辖到 \(q\)
利用情况 \(1\) 中的性质，每种奶牛中 \(q\) 最多有一个。所以可以记录下 \(q\) ，然后枚举 \(p\) ，统计 \(q\) 出现在多少个异种奶牛管辖区间即可。
#include<cstdio>
const int M=1e5+10;
char str[M];
int n,E[M],preG[M],preH[M];
long long ans;
int main(){
scanf("%d",&n);
scanf(" %s",str+1);
for(int i=1;i<=n;i++) scanf("%d",&E[i]);
for(int i=1;i<=n;i++){//前缀和
preG[i]=preG[i-1],preH[i]=preH[i-1];
if(str[i]=='G') preG[i]++;
if(str[i]=='H') preH[i]++;
}
int totG=preG[n],totH=preH[n];//总共的 G,H 数量
int curG=-1,curH=-1;
for(int i=1;i<=n;i++){
if(str[i]=='G' and preG[E[i]]-preG[i-1]==totG) curG=i;
if(str[i]=='H' and preH[E[i]]-preH[i-1]==totH) curH=i;
}
if(curG!=-1 and curH!=-1) ans++;//第一种情况
if(curG!=-1)
for(int i=1;i<curG;i++)
if(curG<=E[i]) ans++;
if(curH!=-1)
for(int i=1;i<curH;i++)
if(curH<=E[i]) ans++;//第二种情况
printf("%lld",ans);
return 0;
}
Problem 2. Air Cownditioning II
\(\mathcal{Farmer \ John}\) 的 \(n\) 只奶牛住在编号 \(1...100\) 的牛棚里。第 \(i\) 头奶牛住在 \([s_i , t_i]\) 牛棚中。每头奶牛的居住范围不相交。
天气炎热，第 \(i\) 头奶牛希望自己居住的牛棚温度全部下降至少 \(c_i\) 度。
有 \(m\) 台空调，第 \(j\) 台空调能用 \(cost_j\) 的代价使 \([a_j , b_j]\) 牛棚下降 \(p_j\) 度。
问满足所有奶牛的最小花费是多少。
\(1 \leq n \leq 20\) , \(1 \leq m \leq 10\) , 数据保证有解。
数据范围十分小，考虑二进制枚举每台空调用或不用。
先处理出第 \(i\) 个牛棚至少需要下降 \(lim_i\) 度。
然后枚举状态 \(S \in [0 , 2^m)\) ，若二进制下 \(S\) 的第 \(j\) 位为 \(1\) 代表使用这台空调，\(0\) 则不用。
维护一个数列，若使用第 \(j\) 台空调则将 \([a_j , b_j]\) 区间都加上 \(p_j\) ，显然可以用 \(差分 + 前缀和\) 维护。
最后判断方案是否合法。合法则将花费与答案取最小值。
其实可以用 \(dfs\) ，但是二进制枚举代码更简洁所以用了后者。
#include<cstdio>
#include<cstring>
const int M=110;
int max(int A,int B){return A>B?A:B;}
int min(int A,int B){return A<B?A:B;}
int n,m;
int s[M],t[M],c[M],lim[M];
//第 i 个位置至少要降低lim[i] 度
int cost[M],p[M],a[M],b[M];
int dif[M],pre[M];
bool check(){
pre[0]=0;
for(int i=1;i<=100;i++) pre[i]=pre[i-1]+dif[i];
for(int i=1;i<=100;i++)
if(pre[i]<lim[i]) return false;
return true;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d%d",&s[i],&t[i],&c[i]);
for(int i=1;i<=m;i++) scanf("%d%d%d%d",&a[i],&b[i],&p[i],&cost[i]);
for(int i=1;i<=n;i++)
for(int j=s[i];j<=t[i];j++) lim[j]=max(lim[j],c[i]);
int ans=0x3f3f3f;
for(int S=0;S<(1<<m);S++){
memset(dif,0,sizeof dif);
int tot=0;
for(int i=1;i<=m;i++)
if(S&(1<<(i-1))){
tot+=cost[i];
dif[a[i]]+=p[i],dif[b[i]+1]-=p[i];
}
if(check()) ans=min(ans,tot);
}
printf("%d",ans);
return 0;
}
Problem 3. Moo Operations
给定 \(q\) 个字符串，每个都包含字符 \(\mathsf{M}\) 和 \(\mathsf{O}\) 。
你可以执行若干次以下两种操作，将字符串变成 \(\mathsf{MOO}\) :
- 将第一个或最后一个字符取反， \(\mathsf{M} \to \mathsf{O}\) 或者 \(\mathsf{O} \to \mathsf{M}\) 。
- 删除第一个或最后一个字符。
对于每个字符串求出最少的操作次数。无解输出
-1。
\(1 \leq q \leq 100\) , 字符串长度不大于 \(100\) 。
设最后保留下来的 \(\mathsf{MOO}\) 的中间那个 \(\mathsf{O}\) 在原数列的下标为 \(i\) 。很显然中间的 \(i\) 不可能被改动，所以可以枚举 \(i\) 。
设字符串长度为 \(len\) ，那么要保留上述 \(MOO\) ，需要经过如下操作：
-
删除位于 \([1,i-2]\) 的字符。
-
删除位于 \([i+2,len]\) 的字符。
-
修改 \(i-1\) 与 \(i+1\) 位的字符。
第 \(1,2\) 步共需要操作 \(len - 3\) 步，第三步若第 \(i-1\) 位不为 \(\mathsf{M}\) ，第 \(i+1\) 位不为 \(\mathsf{O}\) 则各需要一次修改。最后与答案取最小值即可。
注意判断无解。
#include<cstdio>
#include<cstring>
#define min(A,B) ((A)<(B)?(A):(B))
const int M=110;
int q;
int main(){
scanf("%d",&q);
while(q--){
bool flag=false;
char str[M];
scanf(" %s",str+1);
int len=strlen(str+1),ans=0x3f3f3f;
for(int i=2;i<len;i++){
if(str[i]!='O') continue;
int tmp=len-3;
if(str[i-1]=='O') tmp++;
if(str[i+1]=='M') tmp++;
ans=min(ans,tmp),flag=true;
}
if(flag) printf("%d\n",ans);
else printf("-1\n");
}
return 0;
}