USACO 2023 Jan Cu 题解
LegendaryGrandmaster
2023-02-01 10:24:13
第一次AK铜组进银啊qwq
耗时 $3h \ 30min$
## [Leaders](https://www.luogu.com.cn/blog/686297/solution-p9010)
2023.2.18 修复代码 bug。
hack 数据：
```
4
GHHG
4 3 3 4
```
贪心。能想到的话其实代码很短。
我们可以把选择的两个领导分为两种情况：
1. 有一个领导可以管理自己所有种类的牛，且另外一个领导可以管理这个领导。
2. 两个领导都可以管理各自种类的牛。
把这个想出来代码也就自然好写了。
我们可以先把两种种类**第一次**和**最后一次**出现的牛出现的位置找出来。
之后我们可以看到，如果这头牛能管控的牛可以当领导（那么这个被管控的领导管控的牛必须包括所有和自己种类一样的牛），如果满足，那么就形成一对。
如果两头牛都可以管控所有和自己种类一样的牛，那么也是一对。
**注**：另外需要注意，如果之前两头牛已经成为一组，则不算。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N];
signed main()
{
int n;
cin>>n;
string st;
cin>>st;
st=' '+st;
int g=0,h=0,G=0,H=0;
for(int i=1;i<st.size();i++){
if(st[i]=='G'&&!g)g=i;
else if(st[i]=='H'&&!h)h=i;
}
for(int i=st.size()-1;i>=1;i--){
if(st[i]=='G'&&!G)G=i;
else if(st[i]=='H'&&!H)H=i;
}
for(int i=1;i<=n;i++)cin>>a[i];
char ch;
int ans=0;
bool gg=0,hh=0;
for(int i=1;i<=n;i++){
if(st[i]=='G'){
if(a[i]>=h&&i<=h&&a[h]>=H){
ans++;
if(i==g)gg=1;
}
}
if(st[i]=='H'){
if(a[i]>=g&&i<=g&&a[g]>=G){
ans++;
if(i==h)hh=1;
}
}
}
/*
为了防止抄题解，代码里可能会有废话/ww
管控另外一个领导的定义如下：这个牛所管理的范围可以包含另外一种牛第一次出现的位置。
管理包括所有和自己种类一样的牛的定义如下：这个牛所管理的范围可以包含和自己种类一样的牛最后一次出现的位置。
*/
if(a[g]>=G&&a[h]>=H&&!gg&&!hh)ans++;
cout<<ans;
}
```
## [Cownditioning II](https://www.luogu.com.cn/blog/686297/solution-p9011)
前置芝士：[枚举子集](https://www.luogu.com.cn/problem/B3622)
是的，我们分为**取**和**不取**的情况考虑然后取最小值就行了。
这里用二进制模拟，其实很多方法都可以实现。
可以先把每个单位的牛棚所要的温度加上，如果最后减的话每个单位都比 0 小，那么我们就取最小值。
由于 $m$ 的范围非常小，所以 是可以过去的。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],f[N],x[N],n,m;
struct node{
int l,r,x,t;
}s[N];
string bin(int n,int m)
{
int x[101],t=0,s=m;
while(n!=0){
x[t]=n%2;
t++;
n=n/2;
}
string st="";
while(t<s){
s--;
st+='0';
}
for(int i=t-1;i>=0;i--)st+=char(x[i]+48);
return st;
}
int main()
{
cin>>n>>m;
int L=INT_MAX,R=0;
for(int i=1;i<=n;i++){
int l,r,c;
cin>>l>>r>>c;
a[l]+=c;
a[r+1]-=c;
L=min(L,l);//左边界
R=max(R,r);//有边界
}
//多余的区域是不需要管的。
for(int i=L;i<=R;i++)f[i]=f[i-1]+a[i];//差分求每一的单位所需减少的温度。
//for(int i=L;i<=R;i++)cout<<f[i]<<' ';
for(int i=1;i<=m;i++)cin>>s[i].l>>s[i].r>>s[i].x>>s[i].t;
int mi=INT_MAX;
for(int i=0;i<=pow(2,m)-1;i++){
for(int j=L;j<=R;j++)x[j]=f[j];
string st=bin(i,m);
int ans=0;
for(int j=0;j<st.size();j++){
if(st[j]=='1'){
for(int k=s[j+1].l;k<=s[j+1].r;k++)x[k]-=s[j+1].x;
ans+=s[j+1].t;
}
}
bool ok=1;
//for(int j=L;j<=R;j++)cout<<x[j]<<' ';
//puts("");
for(int j=L;j<=R;j++)
if(x[j]>0){
ok=0;
break;
}
if(ok)mi=min(mi,ans);
}
cout<<mi;
}
```
## [Moo Operations](https://www.luogu.com.cn/blog/686297/solution-p9012)
首先字符串至少要有 3 位，没有直接输出 -1。
我们三位三位模拟取最小值，只要中间是 `O` ，都可以变成 `MOO`。
操作次数如下：
1. `MOO`：0次。
2. `MOM`：1次。
3. `OOO`：1次。
4. `OOM`：2次。
最终取最小值加上总长度 -3 即可。因为最终只能保留 3 位。如果 $mi$ 仍是初始值，那么输出 -1。
```cpp
#include<bits/stdc++.h>
using namespace std;
signed main()
{
int t;
cin>>t;
while(t--){
int mi=0x3f3f3f3f;
string st;
cin>>st;
if(st.size()<3){
puts("-1");
continue;
}
for(int i=0;i<st.size()-2;i++){
string str=st.substr(i,3);
if(str=="MOO")mi=min(mi,0);
else if(str=="MOM")mi=min(mi,1);
else if(str=="OOO")mi=min(mi,1);
else if(str=="OOM")mi=min(mi,2);
}
if(mi==0x3f3f3f3f)puts("-1");
else cout<<mi+st.size()-3<<'\n';
}
}
```