M-Maimai DX 2077_"蔚来杯"2022牛客暑期多校训练营(加赛) (nowcoder.com)
阅读理解和膜你题。
double pts[5][5]={
{1,1,0.8,0.5,0},
{2,2,1.6,1.0,0},
{3,3,2.4,1.5,0},
{5,5,2.5,2,0},
{1,0.5,0.4,0.3,0}
};
int num[4][5];
int sum[4];
double A,B,A0,B0;
int main(){
for(int i=0;i<4;i++){
for(int j=0;j<5;j++){
scanf("%d",&num[i][j]);
sum[i]+=num[i][j];
}
}
for(int i=0;i<4;i++)A+=sum[i]*pts[i][0];
B=sum[3]*pts[4][0];
for(int i=0;i<4;i++){
for(int j=0;j<5;j++){
A0+=num[i][j]*pts[i][j];
}
}
for(int j=0;j<5;j++){
B0+=num[3][j]*pts[4][j];
}
printf("%lf",A0/A*100.0+B0/B);
return 0;
}
H-Here is an Easy Problem of Zero-chan_"蔚来杯"2022牛客暑期多校训练营(加赛) (nowcoder.com)
dfs回溯,lca的一些小性质,质因子。
怪,并没有第一时间想到树形dp,而是想到了搜索回溯。
如何计算后缀零?
一个数如果乘以10,它就会出现一个后缀0,而10的质因子只有2和5。因此我们不必真的把所有lca乘起来,只需要计算它们乘起来之后质因子2和5的次数,两者取最小值即可。
如何处理lca?
-
首先,分析一个点和其他所有点之间lca的关系。很容易可以发现,一个点的lca只会在dfs当前的搜索路径上。如下图,3的lca只能是3、1、0这三个点。
-
其次,分析每个lca会出现的次数。因为如果知道它们出现的次数,很容易就可以算出它们的乘积中质因子2和5的次数。同样以点3为例,lca=3的情况恰好对应结点3的子树规模,lca=1的情况恰好等于结点1的子树规模减去结点3的子树规模,lca=0的情况恰好等于结点0的子树规模减去结点1(即结点3所在的分支)的子树规模。
-
最后,考虑如何更快地求出每个点的情况。因为dfs的过程中可以借助回溯很方便处理当前dfs的路径,所以一遍dfs就能把每个点的情况都求出来。
细节见代码:
#define x first
#define y second
const int N=1e5+5,M=2*N;
typedef long long ll;
typedef pair<ll,ll>PII;
int n,q;
PII ten[N];
int e[M],ne[M];
int h[N],idx;
int sz[N];
PII ans[N],res;
void adde(int x,int y){
e[idx]=y; ne[idx]=h[x]; h[x]=idx++;
}
void dfs_sz(int u,int fa){
sz[u]=1;
for(int i=h[u];~i;i=ne[i]){
int v=e[i];
if(v==fa)continue;
dfs_sz(v,u);
sz[u]+=sz[v];
}
}
void dfs_ten(int u,int fa){
//先加上一整棵子树的质因子次数
res={ res.x+ten[u].x*sz[u] , res.y+ten[u].y*sz[u] };
for(int i=h[u];~i;i=ne[i]){
int v=e[i];
if(v==fa)continue;
//往下搜索或者求答案,都需要先减去该分支的大小的以u为根的质因子次数
res={res.x-ten[u].x*sz[v] , res.y-ten[u].y*sz[v]};
ans[v]={res.x+ten[v].x*sz[v], res.y+ten[v].y*sz[v]};
dfs_ten(v,u);
//回溯
res={res.x+ten[u].x*sz[v] , res.y+ten[u].y*sz[v]};
}
//回溯
res={ res.x-ten[u].x*sz[u] , res.y-ten[u].y*sz[u] };
}
int main(){
scanf("%d%d",&n,&q);
int x,y;
memset(h,-1,sizeof(h));
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
adde(x,y), adde(y,x);
}
for(int i=2;i<=n;i++){//求出每个数中质因子2和5的个数
x=i;
for(int j=2;x>1 && j<=5;j++){
int cnt=0;
while(x%j==0){
cnt++;
x/=j;
}
if(j==2)ten[i].x=cnt;
if(j==5)ten[i].y=cnt;
}
}
dfs_sz(1,0);
ans[1]=res={0,0};//ans记录每个点的答案,res是dfs过程中的临时结果
dfs_ten(1,0);
for(int i=1;i<=q;i++){
scanf("%d",&x);
printf("%lld\n",min(ans[x].x,ans[x].y));
}
return (0-0);
}
E-Everyone is bot_"蔚来杯"2022牛客暑期多校训练营(加赛) (nowcoder.com)
很怪的博弈论题。
此题的关键在于:每个人都想最大化自己的冰红茶数量。
如果已经有n-p个人复读了,那么接下来那个人一定不会选择复读,因为如果他复读了,剩下的所有人也会一起复读,最后被惩罚的就是他了。、
对于n-2p,n-3p,n-4p....也是同理。最后可以得出,到(n mod p) + 1
这个人的时候,复读就停止了。
前n mod p
个人一定一上来就会复读,因为如果他们不复读,后面的人就会抢占他们的机会。
const int N=1e3+5;
int n,p;
int a[N][N];
int main(){
scanf("%d%d",&n,&p);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=n;i++){
if(i<=n%p)printf("%d ",a[i][i]);
else printf("%d ",0);
}
printf("\n");
return 0;
}
标签:sz,ten,int,第五场,lca,dfs,牛客,res,加塞
From: https://www.cnblogs.com/tshaaa/p/16623042.html