# **Intro**
地址：<a href="https://vjudge.net/contest/384255" target="_blank">https://vjudge.net/contest/384255</a>
标签：`模拟` `字符串` `前缀和` `贪心` `动态规划` `连通块`
# **A Polycarp's Pockets**
题意是说一个口袋里不能放进两个或以上同样面值的硬币，然后给出所有硬币的面值，求需要的口袋数的最小值。可以推出：所需求的口袋数的最小值就是重复出现最多次的那个面值的硬币的数量。这样，用计数数组或者`map`容器对各种面值的硬币进行计数，并不断更新出现最大重复数，就可以得到答案。
```cpp
#include<bits/stdc++.h>
using namespace std;
int t[105];
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
cin>>n;
int maxn=0;
for (int i=1;i<=n;i++)
{
int z;
cin>>z;
t[z]++; //计数
maxn=max(maxn,t[z]);
}
cout<<maxn<<'\n';
return 0;
}
```
# **B Binary String Constructing**
看起来简单，但是写起来很麻烦的一道题。本题求的是满足一定交替次数的01序列。题目给出了$0,1$的个数和交替次数。我们先考虑把交替次数做完：
- 样例：$[2,2,1]$（三个分别是$0,1$的个数和交替次数）
- 先用完交替次数：01
- 发现后面怎么弄都不对
这样显然行不通，因为用完交替次数后还剩下$0,1$没用，那必定是要多出一个交替次数。那我们可以退一步考虑，选择留一个交替次数，把其他的交替次数先用完，最后把剩下的$0,1$数字收集起来一起输出。这样一来$0,1$数字和交替次数刚好就用完了。
但是还需要考虑一个问题：最后剩下的只有$0$或者$1$咋办？这其实也很好解决，只需要保证其他的交替次数做完后序列尾位的数字跟剩下的数字不一样就行。
```cpp
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int a,b,x;
cin>>a>>b>>x;
int ch;
if (a>b) //0的个数大于1的个数
{
if (x%2) //x-1为偶数时，开头为1
ch=1;
else ch=0;
for (int i=1;i<=x;i++)
{
cout<<ch;
if (ch) b--;
else a--;
ch=!ch;
}
for (int i=1;i<=b;i++)
cout<<1;
for (int i=1;i<=a;i++)
cout<<0;
}
else
{
if (x%2)
ch=0;
else ch=1;
for (int i=1;i<=x;i++)
{
cout<<ch;
if (ch) b--;
else a--;
ch=!ch;
}
for (int i=1;i<=a;i++)
cout<<0;
for (int i=1;i<=b;i++)
cout<<1;
}
cout<<'\n';
return 0;
}
```
# **C Intense Heat**
这道题求的是长度大于等于k的子段的平均值的最大值。首先要注意是子段而不是子序列，这是不同的概念。既然是子段，那么就非常简单了，数据范围也不大，前缀和直接伺候上！然后再来个暴力求平均值就可以了，时间复杂度为$O(n^2)$。
```cpp
#include<bits/stdc++.h>
using namespace std;
int a[5005];
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i]+=a[i-1];
}
double maxn=0;
for(int i=1;i<=n;i++)
{
for(int j=i+k-1;j<=n;j++)
maxn=max(maxn,((double)(a[j]-a[i-1])/(j-i+1)));
}
cout<<setiosflags(ios::fixed)<<setprecision(15)<<maxn<<endl;
return 0;
}
```
# **D Coins and Queries**
这是一道**贪心题**。做法就是，从大到小循环硬币面值，每次尽可能的去取可以取的当前的硬币面值。如果能凑成，则输出取的数的数目，不能则输出$-1$。来证明一下这个方法：
- **正确性**：因为每个硬币面值都是$2$的次幂，所以从大到小去取，不会使得本来可以凑成的数值凑不成（**想一想啦**）。
- **最优性**：因为是从大到小循环取面值，所以一定能保证数量最优。
当然本题还需要一点处理的技巧。
```cpp
#include<bits/stdc++.h>
using namespace std;
map<int,int> b;
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n,q;
cin>>n>>q;
for (int i=1;i<=n;i++)
{
int bi;
cin>>bi;
b[bi]++;
}
while (q--)
{
int d;
cin>>d;
int cnt=0;
for (int i=31;~i;i--)
{
if ((1<<i)>d) continue;
cnt+=min(d/(1<<i),b[1<<i]);
d-=min(d/(1<<i),b[1<<i])*(1<<i);
if (d==0) break;
}
if (!d)
cout<<cnt<<'\n';
else cout<<"-1\n";
}
return 0;
}
```
# **E How Many Tables**
这一题的出题点是分组并查集。如何计算分组的数量？在经过处理之后，在同一组的人都有相同的"祖先"，所以只需要计所有人的"祖先"的种数就可以了，记录种数用`set`容器会方便很多。
```cpp
#include<bits/stdc++.h>
using namespace std;
int fa[100005];
int check_anc(int x) //寻找祖先
{
if (fa[x]) return fa[x]=check_anc(fa[x]); //路径压缩
return x;
}
void union_anc(int x,int y) //合并
{
x=check_anc(x); y=check_anc(y);
if (x!=y)
fa[x]=y;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t;
cin>>t;
while (t--)
{
memset(fa,0,sizeof(fa));
set<int> num;
int n,m;
cin>>n>>m;
for (int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
union_anc(u,v);
}
for (int i=1;i<=n;i++)
num.insert(check_anc(i));
cout<<num.size()<<'\n';
num.clear();
}
return 0;
}
```
# **F Oil Deposits**
求连通块数原题。
```cpp
#include<bits/stdc++.h>
using namespace std;
char pic[105][105];
int n,m,idx[105][105];
void dfs(int r,int c,int id)
{
if (r<0||r>=m||c<0||c>=n) return;
if (idx[r][c]>0||pic[r][c]!='@') return;
idx[r][c]=id;
for (int dr=-1;dr<=1;dr++)
for (int dc=-1;dc<=1;dc++)
if (dr!=0||dc!=0) dfs(r+dr,c+dc,id);
}
int main()
{
while (scanf("%d%d",&m,&n)==2&&m&&n)
{
for (int i=0;i<m;i++)
scanf("%s",pic[i]);
memset(idx,0,sizeof(idx));
int cnt=0;
for (int i=0;i<m;i++)
for (int j=0;j<n;j++)
if (idx[i][j]==0&&pic[i][j]=='@') dfs(i,j,++cnt);
printf("%d\n",cnt);
}
return 0;
}
```
# **G Bone Collector**
$01$背包原题，使用空间优化，注意循环顺序。
```cpp
#include<bits/stdc++.h>
using namespace std;
int w[3505],v[3505];
int dp[20005];
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t;
cin>>t;
while (t--)
{
memset(dp,0,sizeof(dp));
int n,m; //n为物品数量，m为容量
cin>>n>>m;
for (int i=1;i<=n;i++)
cin>>w[i]; //输入物品的价值和体积
for (int i=1;i<=n;i++)
cin>>v[i]; //输入物品的价值和体积
for (int i=1;i<=n;i++)
for (int j=m;j>=0;j--)
if (j-v[i]>=0)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
cout<<dp[m]<<'\n';
}
return 0;
}
```
# **H Max Sum**
本来是一道普普通通的动态规划题，可是加了求首尾的要求后就变的稍微复杂一些了，需要回忆一下这道题动态规划的原型。
- 设数组为$a$，求解数组为$f$
- **状态**：以当前下标为结尾的子段和最大有多大
- **转移方程**：$f[i]=max\{a[i],f[i-1]+a[i]\}$
尾边界可以很容易得出:找到满足$f[i]$最大的那个下标。首边界怎么求呢，观察转移方程，当$f[i]+a[i]>=a[i]$，即$f[i]>=0$时，就会刷新首边界，所以我们从尾边界开始往前遍历，直到不满足这个条件，那么此时的位置就是首边界的前一个位置。
**大坑**：最后一个测试数据的末尾不要用两个换行。
```cpp
#include<bits/stdc++.h>
using namespace std;
int a[200005],f[200005];
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t;
cin>>t;
for (int j=1;j<=t;j++)
{
int n;
cin>>n;
for (int i=1;i<=n;i++)
cin>>a[i];
for (int i=1;i<=n;i++)
f[i]=max(a[i],f[i-1]+a[i]);
int maxn=INT_MIN,s,e;
for(int i=1;i<=n;i++)
{
if (maxn<f[i])
{
maxn=f[i];
e=i;
}
}
s=e;
for(int i=s-1;i;i--)
{
if (f[i]>=0) s=i;
else break;
}
cout<<"Case "<<j<<":\n"<<maxn<<' '<<s
<<' '<<e<<"\n";
if (j!=t)
cout<<"\n";
}
return 0;
}
```
---
感谢浏览😝！
此文章可能会在后续更新，欢迎纠错。
P1-广州大学ACM暑假集训DAY1-7-20题解
