USACO 2023 January Contest, Bronze

[USACO23JAN] Leaders B

题目描述

农夫约翰有 $N$ 头牛 $(2\le N\le {10}^5)$。每头牛的品种要么是 Guernsey，要么是 Holstein。通常情况下，牛站成一排，按顺序编号为 $1\cdots N$。

在一天的过程中，每头牛都会写下一个牛的列表。具体来说，第 $i$ 头牛的列表包含从她自己（第 $i$ 头牛）开始到包括第 $E_i(i\le E_i\le N)$ 头牛的范围。

FJ 最近发现，每种牛的品种都有一个独特的领导者。FJ 不知道领导者是谁，但他知道每个领导者的列表必须包括其品种的所有牛，或者其他品种的领导者（或两者）。

帮助 FJ 计算可能成为领导者的牛对数。保证至少有一对可能的领导者。

输入格式

第一行包含 $N$。

第二行包含一个长度为 $N$ 的字符串，其中第 $i$ 个字符表示第 $i$ 头牛的品种（G 表示 Guernsey，H 表示 Holstein）。保证至少有一个 Guernsey 和一个 Holstein。

第三行包含 $E_1\cdots E_N$。

输出格式

输出可能的领导者对数。

输入输出样例 #1

输入 #1

4
GHHG
2 4 3 4

输出 #1

1

输入输出样例 #2

输入 #2

3
GGH
2 3 3

输出 #2

2

说明/提示

样例 1 的解释

唯一有效的领导者对是 $(1,2)$。第 1 头牛的列表包含其他品种的领导者（第 2 头牛）。第 2 头牛的列表包含她品种的所有牛（Holstein）。

没有其他对是有效的。例如，$(2,4)$ 是无效的，因为第 4 头牛的列表不包含其他品种的领导者，也不包含她品种的所有牛。

样例 2 的解释

有两个有效的领导者对，$(1,3)$ 和 $(2,3)$。

评分

• 输入 $3-5$：$N\le 100$
• 输入 $6-10$：$N\le 3000$
• 输入 $11-17$：没有额外的限制。

解题思路

代码示例

#include<iostream>
using namespace std;
const int maxn=2e5+5;
char s[maxn];
int n,l,r,e[maxn],ans;
int main(){
	cin>>n>>(s+1);
	for(int i=1;i<=n;i++) cin>>e[i];
	for(int i=n;i>=1;i++){
		if(s[i]==s[1]) {r=i;break;}
	}
	for(int i=2;i<=n;i++){
		if(s[i]!=s[1]) {l=i;break;}
	}
	for(int i=1;i<l;i++){
		if((i==1 s++;
	}
	cout<<ans;
}

[USACO23JAN] Air Cownditioning II B

题目描述

农夫约翰的 $N$ 头奶牛 $(1\le N\le 20)$ 住在一个谷仓里，谷仓里有连续的牛栏，编号为 $1-100$ 。 奶牛 $i$ 占据了编号 $[s_i,t_i]$ 的牛栏。 不同奶牛占据的牛栏范围是互不相交的。 奶牛有不同的冷却要求，奶牛 $i$ 占用的每个牛栏的温度必须至少降低 $c_i$ 单位。

谷仓包含 $M$ 台空调，标记为 $1-M$ $(1\le M\le 10)$。第 $i$ 台空调需要花费 $m_i$ 单位的金钱来运行 $(1\le m_i\le 1000)$ ，如果运行，第 $i$ 台空调将牛栏 $[a_i,b_i]$ 所有牛栏的温度降低 $p_i$（$1\le p_i\le {10}^6）$。 空调覆盖的牛栏范围可能会重叠。

请帮助农夫约翰求出满足所有奶牛需求要花费的最少金钱。

输入格式

第一行两个整数，分别为 $N$ 和 $M$。

第 $2$ 至 $(N+1)$ 行，每行三个整数，分别为 $s_i$、$t_i$ 和 $c_i$ 。

第 $(N+2)$ 至 $(M+N+1)$ 行，每行四个整数， 分别为 $a_i$、$b_i$、$p_i$ 和 $m_i$。

输出格式

一个整数，表示最少花费的金钱。

输入输出样例 #1

输入 #1

2 4
1 5 2
7 9 3
2 9 2 3
1 6 2 8
1 2 4 2
6 9 1 5

输出 #1

10

说明/提示

样例解释 1

一种花费最少的可能解决方案是选择那些冷却区间为 $[2,9]$ 、$[1,2]$ 和 $[6,9]$ 的空调，成本为 $ 3+2+5=10$ .

对于 $100\mathrm{\%}$ 的数据，$1\le N\le 20$， $1\le M\le 10$, $ 1 \le a_i, b_i, s_i, t_i \le 100$, $1\le c_i,p_i\le {10}^6$， $1\le m_i\le 1000$。

解题思路

• 由于只有最多10台空调，则我们可以暴力遍历每台空调的状态：开或关。
• 然后将这10台空调的每组状态带入检查，如果每个牛栏的下降温度都符合就记录。
• 在暴力遍历的时候，如果发现成本已经大于之前符合条件的记录时，则结束该种遍历，实现剪枝。

代码示例

#include<iostream>
using namespace std;

bool f[15]={false};//空调的状态，true为开，false为关
int n,m,ans=0x3f3f3f;
struct T1{//牛
    int s;
    int t;
    int c;
}a[25];
struct T2{//空调
    int a;
    int b;
    int p;
    int m;
}b[15];
bool check(){//检查所有的温度都符合
    int a2[110]={0};
    for(int i=0;i<m;i++){
        if(f[i]){
            for(int j=b[i].a;j<=b[i].b;j++){
                a2[j]+=b[i].p;//记录每个牛栏的下降温度
            }
        }
    }
    for(int i=0;i<n;i++){
    	for(int j=a[i].s;j<=a[i].t;j++)
       	 	if(a2[j]<a[i].c){//如果某个牛栏的温度没有达到牛的温度要求，则返回false
            	return false;
        	}
    }
    
    return true;
}
void dfs(int i,int k){//第i台空调，当前这种组合花费了k
//	cout<<i<<" "<<k<<endl;
	
    if(k>ans || i>m){//剪枝
    	return;
    }
    
    if(i==m && check()){
        ans = k;
        return;
    }
    
    f[i] = false;
    dfs(i+1,k);//空调关
    f[i] = true;
    dfs(i+1,k+b[i].m);//空调开
    
}
int main(){
    int i,j,k;
    cin >> n >> m;
    for(i=0;i<n;i++){
        cin >> a[i].s >> a[i].t >> a[i].c;
    }
    for(i=0;i<m;i++){
		cin >> b[i].a >> b[i].b >> b[i].p >> b[i].m;
    }
    dfs(0,0);
    cout<< ans <<endl;
	return 0;	
}

[USACO23JAN] Moo Operations B

题目描述

农夫约翰给了奶牛贝西 $Q$ 个新字符串 $(1\le Q\le 100)$ ，其中只有字符 M 和 O ，她想将 $Q$ 个字符串都变成 MOO。

贝西可以用如下的方式改变字符串：

• 用相反的字符替换第一个或最后一个字符（将 M 变成 O ，将 O 变成 M ）。
• 删除第一个或最后一个字符。

贝西只想用最少的次数完成改变。请你帮她找到需要的最小改变次数。如果不可能在有限的步数中完成这个任务，请输出 -1 。

输入格式

输入数据的第一行是一个正整数 $Q$ 。

接下来的 $Q$ 行中，每行一个只包含大写字母 M 或 O 的字符串 $S$ ，保证 $ 1\le |S| \le 100$ 。

输出格式

输出 $Q$ 行，每行为该测试点最小操作次数，如果不可能在有限的步数中完成这个任务，请输出 -1 。

输入输出样例 #1

输入 #1

3
MOMMOM
MMO
MOO

输出 #1

4
-1
0

说明/提示

样例解释 1

将第一个字符串转换为 MOO的 $4$ 个操作序列如下：

• 用O替换最后一个字符（操作1）
• 删除第一个字符（操作2）
• 删除第一个字符（操作2）
• 删除第一个字符（操作2）

可以证明，第二个字符串无法转换为 MOO。

第三个字符串已经是 MOO，因此无需执行任何操作。

对于 $100\mathrm{\%}$ 的测试点，保证 $1\le Q\le 100$, $ 1\le |S| \le 100$ 。

解题思路

• 只要有字符串大于3个字符，且有字符 O，都可以变成 MOO

代码示例

#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';
	}
}