U$16$B$01$F. Milk Pails

这道题因为数据范围很小，所以可以直接枚举$m/x$~$m/y$，看相乘起来哪个是$<m$的最大值即可。

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("pails.in","r",stdin);
	freopen("pails.out","w",stdout); 
	int x,y,m;
	cin>>x>>y>>m;
	int ans=0;
	for(int i=0;i<=m/x;i++) for(int j=0;j<=m/y;j++) if(x*i+y*j<=m) ans=max(x*i+y*j,ans);
	cout<<ans;
	return 0;
}

U$16$B$01$OC. Diamond Collector

这题我们可以直接枚举，考虑如果将第$i$颗钻石放到展示柜上，有多少颗钻石可以和第$i$个钻石一起放到展示柜上，取最大值即可。

#include<bits/stdc++.h>
using namespace std;
int a[1010]; 
int main(){
	freopen("diamond.in","r",stdin);
	freopen("diamond.out","w",stdout); 
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	int ans=0;
	sort(a+1,a+1+n);
	for(int i=1;i<=n-1;i++){
		int cnt=1;
		for(int j=i+1;j<=n;j++) if(abs(a[j]-a[i]<=k)) cnt++;
		ans=max(cnt,ans);
	}
	cout<<ans;
	return 0;
}

U$16$B$03$F. Load Balancing

我们可以发现，若是直接枚举$1$~B的分割点话是肯定会超时的，时间复杂度是$O(B^3)$。

我们发现，其实有很多的枚举都是无效的，因为每一个区域里奶牛的数量都不会有很大的变动。

所以我们可以这么办：

• 考虑将$x$设在每个$a_i$的左边，$y$设置在每个$a_i$的上面，在取所有划分方案里面的最优解即可。

那这么做的话，可以将所有的情况都包含在内吗？答案是可以的！因为我们是根据$a_i$来设$x$与$y$的，所以一定可以将所有的情况都包含在内！

#include<bits/stdc++.h>
using namespace std;
struct P{
	int x,y;
};
P a[110];
int main(){
	freopen("balancing.in","r",stdin);
	freopen("balancing.out","w",stdout); 
	int n,b;
	cin>>n>>b;
	for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
	int ans=1e9;
	for(int t=1;t<=n;t++){
		int i=a[t].x+1;
		for(int u=1;u<=n;u++){
			int j=a[u].y+1,cnt_1=0,cnt_2=0,cnt_3=0,cnt_4=0;
			for(int k=1;k<=n;k++){
				if(a[k].x<i&&a[k].y<j) cnt_1++;
				else if(a[k].x<i&&a[k].y>j) cnt_2++;
			    else if(a[k].x>i&&a[k].y<j) cnt_3++;
				else cnt_4++; 
			}
		    ans=min(ans,max({cnt_1,cnt_2,cnt_3,cnt_4}));
		}
	}
	cout<<ans;
	return 0;
}

U$16$S$02$F. Load Balancing Ⅱ

这道题其实是和U$16$B$03$F. Load Balancing是一样的，只不过数据范围变大了。

我们可以发现：

• 每次遍历，都只会让某一个区域$+1$，让某一个区域$-1$，所以我们只要先预处理一下值，在做改变即可。

#include<bits/stdc++.h>
using namespace std;
struct P{
	int x,y;
};
P a[1010];
bool cmp(P a,P b){
	return a.y<b.y;
}
int main(){
	freopen("balancing.in","r",stdin);
	freopen("balancing.out","w",stdout); 
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
	sort(a+1,a+1+n,cmp);
	int ans=1e9;
	for(int i=1;i<=n;i++){
		int cnt_1=0,cnt_2=0,cnt_3=0,cnt_4=0,x1=a[i].x+1;
		for(int j=1;j<=n;j++){
			if(a[j].x<x1) cnt_4++;
			else cnt_2++;
		}
		ans=min(ans,max({cnt_1,cnt_2,cnt_3,cnt_4}));
		for(int j=1;j<=n;j++){
			if(a[j].x<x1) cnt_3++,cnt_4--;
			else cnt_2--,cnt_1++;
			if(a[j].y!=a[j+1].y) ans=min(ans,max({cnt_1,cnt_2,cnt_3,cnt_4}));
		}
	}
	cout<<ans;
	return 0;
}

U$17$B$02$OC. Bovine Genomics

对于这道题目我们可以枚举位置，

若两组都出现了相同字符，则排除当前位置，否则计数器$++$。

最后输出计数器的值即可。

#include<bits/stdc++.h>
using namespace std;
int a[110][30],b[110][30];
int main(){
	freopen("cownomics.in","r",stdin);
    freopen("cownomics.out","w",stdout);
	int n,m;
	cin>>n>>m;
	for(int j=1;j<=n;j++){
		string s;
		cin>>s;
		for(int i=0;i<s.size();i++) a[i][s[i]-'A']++; 
	}
	for(int j=1;j<=n;j++){
		string s;
		cin>>s;
		for(int i=0;i<s.size();i++) b[i][s[i]-'A']++; 
	} 
	int ans=0;
	for(int i=0;i<m;i++){
		bool flag=1;
		for(int j=0;j<26;j++) if(a[i][j]&&b[i][j]) flag=0;
		if(flag) ans++;
	}
	cout<<ans;
	return 0;
}

U$17$S$02$OC. Bovine Genomics Ⅱ

对于这道题目，我们可以考虑一组位置 $i$，$j$，$k$（也就是三层循环），

遍历检查有没有发现某头无斑点牛与当前有斑点牛在这三个位置上有相同的组合。

如果找到有斑点的牛在这些位置上与无斑点的牛共享相同的组合，那么这三个位置就不能解释斑点性。

如果没有发现这样的重叠，那么这组三个位置可以成功解释斑点性，计数器$++$。

最后输出计数器即可。

还有一个小技巧：

我们在输入的时候可以用以下方式进行：

• 'A' 转换为$1$
• 'C' 转换为$2$
• 'G' 转换为$3$
• 'T' 转换为 $4$

#include<bits/stdc++.h>
using namespace std;
int a[510][60],b[510][60],c[5][5][5];
int cl(char x){
	if(x=='A') return 1;
	if(x=='C') return 2;
	if(x=='G') return 3;
	if(x=='T') return 4;
}
int main(){
	freopen("cownomics.in","r",stdin);
    freopen("cownomics.out","w",stdout);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		for(int j=0;j<s.size();j++) a[i][j+1]=cl(s[j]);
	}
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		for(int j=0;j<s.size();j++) b[i][j+1]=cl(s[j]);
	}
	int ans=0;
	for(int i=1;i<=m-2;i++){
	 	for(int j=i+1;j<=m-1;j++){
	 		for(int k=j+1;k<=m;k++){
	 			memset(c,0,sizeof(c));
	 			bool flag=1;
                for(int t=1;t<=n;t++){
                	c[a[t][i]][a[t][j]][a[t][k]]=1;
				}
                for(int t=1;t<=n;t++){
                	if(c[b[t][i]][b[t][j]][b[t][k]]){
						flag=0;
						break;
					} 
			    }
			    if(flag) ans++;
			}
		}
	}
    cout<<ans;
	return 0;
}

U$20$B$01$F. Triangles

这题因为数据很小，所以我们可以直接枚举。

然后找最大值。

最后输出最大值即可。

#include<bits/stdc++.h>
using namespace std;
int x[110],y[110],ans;
int main(){
	freopen("triangles.in","r",stdin);
	freopen("triangles.out","w",stdout);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                if(x[i]==x[k]&&y[i]==y[j]) ans=max(ans,abs(x[i]-x[j])*abs(y[i]-y[k]));      
                else if(x[i]==x[j]&&y[i]==y[k]) ans=max(ans,abs(x[i]-x[k])*abs(y[i]-y[j]));
				else continue;                      
            }
        }
    }
    cout<<ans;
    return 0;
}

U$22$B$01$F. Sleeping in Class

正向求最小操作次数很难，但我们反向可以穷举合并过后的数列长度。

我们知道，无论怎么操作数列总和都不变。

所以我们可以知道，要想使合并后的每个数都相等，数列总和一定是一个整数，

我们只要枚举数列总和的所有质因子即可。

我们可以遍历整个数列，看数列的每一个元素是否是数列总和之枚举数字。

#include <bits/stdc++.h>
using namespace std;
int a[100010];
int main(){
	freopen("sleep.in","r",stdin);
	freopen("sleep.out","w",stdout);
	int t;
    cin>>t;
    while(t--){
    	int n,sum=0;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
			sum+=a[i];
        }
        for(int i=n;i>=1;i--){
            if(sum%i==0){
                int ans=sum/i,lj=0;
				bool flag=1;
    			for(int j=1;j<=n;j++){
                    lj+=a[j];
                    if(lj>ans){
						flag=0;
						break;
					}
                    else if(lj==ans) lj=0;
                }
                if(flag==1){
					cout<<n-i<<endl;
					break;
				}
            }
        }
    }
    return 0;
}