USACO 2022 年 12 月月赛，铜牌
T1-USACO 2022 December Contest, Bronze Problem 1. Cow College
Farmer John 计划为奶牛们新开办一所大学！
有 N（1 ≤ N≤ 10^5）头奶牛可能会入学。每头奶牛最多愿意支付 ci 的学费（1 ≤ ci ≤ 10^6）。 Farmer John 可以设定所有奶牛入学需要支付的学费。如果这笔学费大于一头奶牛愿意支付的最高金额，那么这头奶牛就不会入学。Farmer John 想赚尽可能多的钱，从而可以给他的讲师提供一笔可观的工资。请求出他能赚到的钱的数量，以及此时应当收取多少学费。
输入格式（从终端 / 标准输入读入）：
输入的第一行包含 N。第二行包含 N 个整数 c1,c2,…,cN，其中 ci 是奶牛 i 愿意支付的最高学费金额。
输出格式（输出至终端 / 标准输出）：
输出 Farmer John 可以赚到的大金额以及最优情况下他应该收取的学费。如果有多个解，输出收取学费最小的解。
注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，Java 中的 “long”，C/C++ 中的 “long long”）。
输入样例：
4
1 6 4 6
输出样例：
12 4
如果 Farmer John 收费 4，那么 3 头奶牛将会入学，从而使他赚取 3⋅4=12 的金额。
测试点性质：
测试点 2-4 满足 ci≤1,000。
测试点 5-8 满足 N≤5,000。
测试点 9-12 没有额外限制。
供题：Freddie Tang
创新新互联，凭借十余年的成都网站设计、成都网站建设经验，本着真心·诚心服务的企业理念服务于成都中小企业设计网站有上千家案例。做网站建设，选创新互联公司。
emmm……看到这题的第一眼是想枚举，但一看数据量“1 ≤ N≤ 10^5”瞬间石化，这……有些眼熟（嘿嘿，好奇的同学点进去看看，就明白了），嘿嘿，前缀和嘛！
明白方法实现不难，公式是（money是总学费数组，a是牛愿意付的学费，money[0]=0）：
money[i]=money[i-1]+当前牛的数量*(a[i]-a[i-1])-a[i-1];
而牛的数量可以另开一个变量cow=n，然后每循环一次cow–。但是首先得明白一个问题：如果a[i]=a[i-1]，那么这个cow的数字是错误的，但其实我们不需要去管它，因为如果a[i-1]=a[i]，那么money[i]时间复杂度O(n log n):
#includeusing namespace std;
long long a[100010],n,money[100010],cow,ans=-1,ans1=-1,same;
void readp(){cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
sort(a+1,a+1+n);//先对输入进行排序
cow=n+1;//初始化……欸，我下面代码用n-i+1代替cow了，忽略忽略
}
void work(){for(int i=1;i<=n;++i){money[i]=money[i-1]-a[i-1]+(n-i+1)*(a[i]-a[i-1]);
}
for(int i=1;i<=n;++i){if(money[i]>ans){ ans=money[i];
ans1=a[i];
}//打擂台求大值
}
}
int main(){readp();
work();
cout<
但是有一种更为简单的方法——这里可以直接算出money[i]:是愿意付学费牛的个数✖️当前单个学费
#includeusing namespace std;
long long a[100010],ans,n,pos;
void readp(){scanf("%d",&n);
for(int i=1;i<=n;++i)
cin>>a[i];
sort(a+1,a+n+1);
}
void work(){for(int i=1;i<=n;++i)
if(ans ans=a[i]*(n-i+1);
pos=a[i];
}
printf("%d %d\n",ans,pos);
}
int main(){readp();
work();
return 0;
}
int main(){readp();
work();
return 0;
}
T2-USACO 2022 December Contest, Bronze Problem 2. Feeding the Cows
Farmer John 有 N（1≤N≤105）头奶牛，每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。她们沿水平方向排成一行，奶牛们占据的位置编号为 1…N。
由于奶牛们都饿了，FJ 决定在 1…N 中的某些位置上种植草地。更赛牛和荷斯坦牛喜欢不同类型的草，所以如果 Farmer John 决定在某个位置种草，他必须选择种植更赛牛喜欢的草或荷斯坦牛喜欢的草——他不能在同一个位置同时种两种草。种植的每一片草地都可以喂饱数量不限的相应品种的奶牛。
每头奶牛愿意移动至多 K（0≤K≤N−1）个位置以前往一个草地。求出喂饱所有奶牛所需种植的最小草地数量。此外，输出一种使用最小草地数量喂饱所有奶牛的种植方案。任何满足上述条件的方案均视为正确。
输入格式（从终端 / 标准输入读入）：
每个测试用例包含 T 个子测试用例，为一种奶牛的排列。输入的第一行包含 T（1≤T≤10）。以下是 T 个子测试用例。
每个子测试用例的第一行包含 N 和 K。第二行包含一个长度为 N 的字符串，其中第 i 个字符表示第 i 头奶牛的品种（G 表示更赛牛，H 表示荷斯坦牛）。
输出格式（输出至终端 / 标准输出）：
对于 T 个子测试用例中的每一个，输出两行。第一行输出喂饱所有奶牛所需的最小草地数量。第二行输出一个长度为 N 的字符串，表示一种使用最小草地数量喂饱所有奶牛的种植方案。第 i 个字符表示第 i 个位置，若不种草则为 ‘.’，若种植喂饱更赛牛的草则为 ‘G’，若种植喂饱荷斯坦牛的草则为 ‘H’。任何合法的方案均可通过。
输入样例：
6
5 0
GHHGG
5 1
GHHGG
5 2
GHHGG
5 3
GHHGG
5 4
GHHGG
2 1
GH
输出样例：
5
GHHGG
3
.GH.G
2
…GH.
2
…GH
2
…HG
2
HG
注意对于某些子测试用例，存在多种可通过的方案使用最小数量的草地。例如，在第四个子测试用例中，以下是另一个可以通过的答案：
.GH…
这个方案在第二个位置种植一块喂饱更赛牛的草地以及在第三个位置种植一块喂饱荷斯坦牛的草地。这使用了最小数量的草地并确保了所有奶牛都在她们喜欢的草地的 3 个位置以内。
测试点性质：
测试点 2-4 满足 N≤10。
测试点 5-8 满足 N≤40。
测试点 9-12 满足 N≤105。
供题：Mythreya Dharani
这题……耗了我一个小时。。。
先简要介绍一下，我的思路是：最优解必定是当前位置+k，而如果放置在这儿，那么在当前位置+2k的范围内即无需再放置该种类草。但需要解决一个问题：当当前位置+k>n怎么办？我是这样解决的：while(a[n-pp] == ‘G’||a[n-pp] == ‘H’)++pp;
这样可以统一调配：当然无须担心没位置或位置小于当前位置（出界时必定该种类草已经不需要了）
#includeusing namespace std;
long long k,t,n,fine,way;
char q[100010],ans[100010];
void readp(){cin>>n>>k;
for(long long i=1;i<=n;++i)cin>>q[i];
}
void work(){long long G=0,H=0;
for(long long i=1;i<=n;++i){if(q[i]=='G'&&G long long p=i+k;
if(p>n){ long long pp=0;
while(ans[n-pp]=='G'||ans[n-pp]=='H'){++pp;
}
p=n-pp;
}
ans[p]='G';
G=i+k+k;
++way;
}
else if(q[i]=='H'&&H ++way;
long long p=i+k;
if(p>n){ long long pp=0;
while(ans[n-pp]=='G'||ans[n-pp]=='H'){++pp;//若出界，在界内以保持最优的原则（哎呀，其实没必要，只要你保证不重且位置在当前位置后即可）从后向前分配
}
p=n-pp;
}
ans[p]='H';
H=i+k+k;
}
if(ans[i]!='G'&&ans[i]!='H'){ ans[i]='.';
}
}
}
void out(){cout<cin>>t;
for(long long i=1;i<=t;++i){readp();
work();
out();
}
return 0;
}
从今天起，我要养成好习惯----非空间必要全开long long！！！
T3-USACO 2022 December Contest, Bronze Problem 3. Reverse Engineering
Elsie 有一个程序，接受一个 N（1≤N≤100）个变量的数组 b[0],…,b[N−1] 作为输入，其中每个变量等于 0 或 1，并且返回对输入数组应用一系列 if / else if / else 语句的结果。每个语句检查至多一个输入变量的值，并返回 0 或 1。这类程序的一个例子是：
if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;
例如，如果上方程序的输入是 “10”（即 b[0]=1 及 b[1]=0），那么输出应当为 1。
Elsie 告诉了 Bessie 对于 M（1≤M≤100）个不同输入的正确输出。Bessie 现在正试图对 Elsie 的程序进行逆向工程。不幸的是，Elsie 可能说了谎；可能不存在上述形式的程序行为与 Elsie 所说的均一致。
对于 T（1≤T≤10）个子测试用例中的每一个，判断 Elsie 是否一定在说谎。
输入格式（从终端 / 标准输入读入）：
输入的第一行包含 T，为子测试用例的数量。
每一个子测试用例的第一行包含两个整数 N 和 M，以下 M 行，每行包含一个由 N 个 0 或 1 组成的字符串，表示一个输入（即 b[0]…b[N−1] 的值），以及另一个字符（0 或 1）表示输出。相邻的子测试用例之间用空行分隔。
输出格式（输出至终端 / 标准输出）：
对于每一个子测试用例，输出一行，包含 “OK” 或 “LIE”，分别表示 Elsie 可能没有说谎或是一定在说谎。
输入样例：
4
1 3
0 0
0 0
1 1
2 4
00 0
01 1
10 1
11 1
1 2
0 1
0 0
2 4
00 0
01 1
10 1
11 0
输出样例：
OK
OK
LIE
LIE
以下是第一个子测试用例的一个合法的程序：
if (b[0] == 0) return 0;
else return 1;
以下是第一个子测试用例的另一个合法的程序：
if (b[0] == 1) return 1;
else return 0;
以下是第二个子测试用例的一个合法的程序：
if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;
显然，对于第三个子测试用例不存在对应的合法的程序，因为 Elsie 的程序一定始终对相同的输入产生相同的输出。
可以证明对于最后一个子测试用例不存在对应的合法的程序。
测试点性质：
测试点 2-3 满足 N=2。
测试点 4-5 满足 M=2。
测试点 6-12 没有额外限制。
供题：Benjamin Qi
第3题，欲哭无泪……
分析----拿样例举一波例子：
00 0
01 1
10 1
11 0
看，00和01结果不一样但是第一位一样，说明第一个if语句不可能是判断是否为0
10与11结果不一样但是第一位一样，说明第一个if语句也不可能判断是否为1，所以就错了。
（也可以这么看：00与10结果不一样但是第二位一样，说明对应的if语句不可能是判断是否为0，01与11结果不一样但是第二位一样，说明对应的if语句也不可能是判断是否为1，所以出错）
（更多见注释）
#includeusing namespace std;
int main(){int t,m,n;
string s[110];
bool v[110];
cin>>t;
while(t--){cin>>n>>m;
for(int i=1;i<=m;++i)cin>>s[i]>>v[i];
int ans0=0,ans1=0,vh[2][2];//vh数组用于统计数量，如：vh[1][0]统计的是结果是0有的1的个数
int vh1[110],vh2[110];//vh1，vh2用于标记，如果审核发现没问题（且确定了思路中提到的确定了if的条件），就删掉，接下来就不处理该数据了。vh1标记的是第几位被标记，vh2只标记具体的某一个数
memset(vh1,0,sizeof(vh1));
memset(vh2,0,sizeof(vh2));
for(int i=1;i<=m;++i)
if(v[i]==0)ans0++;
else ans1++;//先统计结果中是0还是1的个数
bool bl=1,bo=0;
while(bl){ bl=0;
for(int i=0;i if(!vh1[i]){memset(vh,0,sizeof(vh));
for(int ii=1;ii<=m;++ii)
if(!vh2[ii])vh[s[ii][i]-'0'][v[ii]]++;
if(vh[0][0]==0&&vh[0][1]!=0){//
bl=1;
ans1-=vh[0][1];
for(int j=1;j<=m;++j)
if(s[j][i]=='0')vh2[j]=1;
}
if(vh[0][1]==0&&vh[0][0]!=0){bl=1;
ans0-=vh[0][0];
for(int j=1;j<=m;++j)
if(s[j][i]=='0')vh2[j]=1;
}
if(vh[1][0]==0&&vh[1][1]!=0){bl=1;
ans1-=vh[1][1];
for(int j=1;j<=m;++j)
if(s[j][i]=='1')vh2[j]=1;
}
if(vh[1][1]==0&&vh[1][0]!=0){bl=1;
ans0-=vh[1][0];
for(int j=1;j<=m;++j)
if(s[j][i]=='1')vh2[j]=1;
}
if(bl){vh1[i]=1;
break;
}
}
}
}
if(ans0==0||ans1==0)cout<<"OK"<
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
文章标题：USACO2022DecemberContest,Bron-创新互联
新闻来源：
http://cdkjz.cn/article/idcgp.html
