牛客小白月赛47
A. 牛牛的装球游戏
标签
暴力
思路
- 显然，答案为 \(\pi r^2l-[\frac{l}{2r}]*\frac{4\pi r^3}{3}\)。
- 时间复杂度为 \(\mathcal O(1)\)。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int T;
double ans,pi=3.141592653589;
int t,h,r;
int main()
{
cin>>t;
while(t--)
{
cin>>r>>h;
int n=h/(2*r);
ans=pi*r*r*h-n*4.0*pi*r*r*r/3;
printf("%.3lf\n",ans);
}
return 0;
}
B. 牛牛的数字集合
标签
数学
思路
- 因为均值不等式 \([(a_{1}\dots a_{l_1})^{m}(a_{l_1+1}\dots a_{l_2})^m\dots (a_{l_i}\dots a_n)^m]^{\frac{1}{m}}=\prod a_i\le \frac{(a_{1}\dots a_{l_1})^{m}+(a_{l_1+1}\dots a_{l_2})^m+\dots +(a_{l_i}\dots a_n)^m}{m},m\ge1\)，故 \(\prod a_i\) 即为最小价值和。
- 时间复杂度为 \(\mathcal O(n)\)。
代码
点击查看代码
n=eval(input())
a=[int(e) for e in input().split()]
ans=1
for e in a:
ans=(ans*e)%(int(1e9+7))
print(ans)
C. 小猫排队
标签
双指针
思路
- 对撞指针，也可以用双端队列模拟。
- 时间复杂度为 \(\mathcal O(n)\)。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int n,a[maxn],ans;
deque<int> q;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n+1;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
q.push_back(a[i]);
while(true)
{
int del=0;
while(!q.empty()&&q.back()<=a[n+1])
del++,q.pop_back();
if(q.empty())
{
ans+=(del+1);
break;
}
q.pop_back();ans++;
if(q.empty()) break;
q.pop_front();
}
cout<<ans;
return 0;
}
D. 造桥
标签
线性 DP
思路
- 因为状态的转移与结尾字符与开头字符有关，故设状态 \(dp_i\) 表示在前 \(i\) 个字符串中进行拼接且最后以第 \(i\) 个字符串作为结尾能得到的最大长度。则 \(dp_i=len_i+\max\limits_{j\le i-1,tail_j=head_i}{dp_j}\)。由于与第 \(i\) 个拼接只与前面的串的最后一个字符有关，故设 \(maxl_{i,j}\) 表示前 \(i-1\) 个字符中以 ascii 码为 \(j\) 结尾的拼接串的最大长度，同时可将 \(maxl_{i,j}\) 滚动数组为 \(maxl_j\)。则 \(dp_i=len_i+maxl_{tail_i}\)。
- 时间复杂度为 \(\mathcal O(n)\)。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+100;
int t,n,maxl[200],ans;
char a[maxn];
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(maxl,0,sizeof(maxl));
ans=0;
for(int i=1;i<=n;i++)
{
cin>>a+1;
int len=strlen(a+1);
ans=max(ans,maxl[a[1]]+len);
maxl[a[len]]=max(maxl[a[1]]+len,maxl[a[len]]);
}
printf("%d\n",ans);
}
}
E. 牛牛的方格图
标签
二维差分
思路
- 首先证明若某一种颜色有 \(n,n>1\) 个不同的点，则其覆盖面为矩形，采用数学归纳法。当 \(n=2\) 时，结论显然成立。当 \(n=k,k>2\) 时，假设结论成立。则当 \(n=k+1\) 时，分离出一点，则可知其他 \(n-1\) 个点可形成 \(1\) 个矩形，进而这 \(n-1\) 个点可等效为矩形的左上顶点与右下顶点 \(2\) 个点，由假设，这两个点连同分离出的一点的覆盖面一定为矩形，因为 \(k\ge3\)。故只需统计每种颜色的行最大值 \(x_2\)、行最小值 \(x_1\)、列最大值 \(y_2\)、列最小值 \(y_1\)，则关于该颜色的覆盖面即为左上顶点为 \((x_1,y_1)\)、右下顶点为 \((x_2,y_2)\) 的矩形。
- 考虑如何得知某一点是否被覆盖，只需判断在其上的颜色种类数是否大于 \(0\) 即可。因为覆盖面为矩形，故需要区间修改，单点查询，采用二维差分。
- 时间复杂度为 \(\mathcal O(nm+10^6)\)。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxt=1e6+5;
const int maxn=1e3+5;
int col[maxt][4],n,m,c,ci[maxn][maxn];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=int(1e6);i++)
col[i][1]=int(1e3+100),col[i][3]=int(1e3+100);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&c);
col[c][0]=max(col[c][0],i);
col[c][1]=min(col[c][1],i);
col[c][2]=max(col[c][2],j);
col[c][3]=min(col[c][3],j);
}
for(int i=1;i<=int(1e6);i++)
{
if(col[i][0]==0) continue;
if(col[i][0]==col[i][1]&&col[i][2]==col[i][3]) continue;
int l,r,x,y;
l=col[i][0],r=col[i][2],x=col[i][1],y=col[i][3];
ci[l+1][r+1]++,ci[l+1][y]--,ci[x][r+1]--,ci[x][y]++;
}
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
ci[i][j]+=ci[i-1][j]+ci[i][j-1]-ci[i-1][j-1];
if(ci[i][j]==0) ans++;
}
}
cout<<ans;
return 0;
}
F. 缆车
标签
最近公共祖先
思路
- 若 \(m\) 个点 \(k\) 全都可以通达，则新修的铁路可以建在 \(k\) 与其子树中除其以外的任意节点之间，暴力枚举子树中的节点更新最小代价即可，具体方式为 \(ans=sumi-\max\limits_{j\in tree_k,j\ne k}{sum_j*(depth_j-depth_k-1)},sum_j=|\{e|e \in M,e \in tree_j\}|\)。
- 若 \(m\) 个点 \(k\) 不可全都通达，则新修的铁路不可随意安置，必须使 \(k\) 与其他景点可通达，显然建在不可通达点的最近公共祖先处可使代价最小。
- 时间复杂度为 \(\mathcal O(n\log n)\)。
代码
点击查看代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxlg=20;
const int maxn=2e5+100;
int depth[maxn],anc[maxn][maxlg+5],sum[maxn];
bool vis[maxn],flag[maxn];
int head[maxn],cnt;
struct edge
{
int to,next;
} e[maxn];
void add(int u,int v)
{
e[++cnt]=(edge){v,head[u]};
head[u]=cnt;
}
int n,k,m;
void dfs(int u,int fa,int d,int tp)
{
if(u==k) tp=1;
flag[u]=tp;
anc[u][0]=fa,depth[u]=d;
if(vis[u]) sum[u]=1;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
dfs(v,u,d+1,tp);
sum[u]+=sum[v];
}
}
void Init()
{
for(int j=1;j<=maxlg;j++)
for(int i=1;i<=n;i++)
anc[i][j]=anc[anc[i][j-1]][j-1];
}
void swim(int &x,int h)
{
for(int i=0;h;i++)
{
if(h&1) x=anc[x][i];
h>>=1;
}
}
int lca(int x,int y)
{
if(depth[x]<depth[y]) swap(x,y);
swim(x,depth[x]-depth[y]);
if(x==y) return x;
for(int i=maxlg;anc[x][0]!=anc[y][0];i--)
if(anc[x][i]!=anc[y][i])
x=anc[x][i],y=anc[y][i];
return anc[x][0];
}
void dfsi(int u,ll &ans,ll sumi)
{
if(u!=k)
ans=min(ans,sumi-1ll*sum[u]*(depth[u]-depth[k]-1));
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
dfsi(v,ans,sumi);
}
}
int main()
{
scanf("%d",&n);
int u,v;
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v);
}
scanf("%d%d",&m,&k);
int x;
for(int i=1;i<=m;i++)
{
scanf("%d",&x);
vis[x]=true;
}
dfs(1,0,1,0);
Init();
int all_father=-1;
for(int i=1;i<=n;i++)
{
if(flag[i]||!vis[i]) continue;
if(all_father==-1) all_father=i;
else all_father=lca(all_father,i);
}
if(all_father!=-1)
{
ll ans=0,del;
for(int i=1;i<=n;i++)
{
if(!vis[i]) continue;
if(flag[i])
del=depth[i]-depth[k];
else del=1+depth[i]-depth[all_father];
ans+=del;
}
printf("%lld",ans);
}
else
{
ll sumi=0,ans=0;
for(int i=1;i<=n;i++)
if(vis[i]) sumi+=depth[i]-depth[k];
ans=sumi;
dfsi(k,ans,sumi);
printf("%lld",ans);
}
return 0;
}