牛客练习赛7
A.骰⼦的游戏
水题，直接暴力枚举六个面再比较大小，完结散花。
时间复杂度O(6*6)
#include<bits/stdc++.h>
using namespace std;
int T,x,y,a[7],b[7];
int main()
{
scanf("%d",&T);
while(T--)
{
x=0;y=0;
for(int i=1;i<=6;i++)scanf("%d",&a[i]);
for(int i=1;i<=6;i++)scanf("%d",&b[i]);
for(int i=1;i<=6;i++)
for(int j=1;j<=6;j++)
if(a[i]>b[j])x++;
else if(a[i]<b[j])y++;
if(x>y)puts("Alice");
if(x<y)puts("Bob");
if(x==y)puts("Tie");
}
return 0;
} B.购物
dp题，中等偏下难度（我不知道为什么我的记忆化搜索萎了）
表示前i天，买j个糖果的最小代价。
时间复杂度O(n^3)
#include<bits/stdc++.h>
using namespace std;
const int N=305;
int n,m,sum[N][N],f[N][N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
scanf("%d",&sum[i][j]);
sort(sum[i]+1,sum[i]+m+1);
for(int j=2;j<=m;j++)
sum[i][j]+=sum[i][j-1];
}
memset(f,0x3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
for(int k=i-1;k<=j;k++)
if(j-k<=m)
f[i][j]=min(f[i][j],f[i-1][k]+sum[i][j-k]+(j-k)*(j-k));
cout<<f[n][n];
return 0;
} C.随机树
这题较难，思维上要用唯一分解定理，代码实现上要用树链剖分（或dfs序）。
唯一分解定理：任何一个数都能被分解成若干质数的若干次数的乘积,也就是分解质因数（）
因数个数为每一个质数加1的乘积,比如12，因数个数为（2+1）*（1+1））
时间复杂度O(nlog(n))
#include<bits/stdc++.h>
using namespace std;
#define mid (l+r)/2
#define int long long
const int mod=1e9+7;
const int xu[6]={2,3,5,7,11,13};
const int N=100005;
int n,m,x,y,top,a[N],ans[10],head[N],seg[N],rev[N],size[N];
char s[N];
struct node{
int too,next;
}edge[N*2];
struct node2{
int jia[10];
}tree[N*4];
int kuai(int a,int b)
{
if(b==0)return 1;
if(b==1)return a;
int x=kuai(a,b/2);
if(b%2==0)return x*x%mod;
return x*x%mod*a%mod;
}
void add(int a,int b)
{
edge[++top].too=b;edge[top].next=head[a];head[a]=top;
}
void dfs(int u,int fa)
{
seg[u]=++seg[0];
rev[seg[0]]=u;
size[u]=1;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(v==fa)continue;
dfs(v,u);
size[u]+=size[v];
}
}
void pushup(int nod)
{
for(int i=0;i<6;i++)
tree[nod].jia[i]=(tree[nod*2].jia[i]+tree[nod*2+1].jia[i])%mod;
}
void build(int nod,int l,int r)
{
if(l==r)
{
for(int i=0;i<6;i++)
{
while(a[rev[l]]%xu[i]==0)
{
tree[nod].jia[i]++;
tree[nod].jia[i]%=mod;
a[rev[l]]/=xu[i];
}
}
return;
}
build(nod*2,l,mid);build(nod*2+1,mid+1,r);
pushup(nod);
}
void change(int nod,int l,int r,int x,int val)
{
if(l==r)
{
for(int i=0;i<6;i++)
{
while(val%xu[i]==0)
{
tree[nod].jia[i]++;
tree[nod].jia[i]%=mod;
val/=xu[i];
}
}
return;
}
if(x<=mid)change(nod*2,l,mid,x,val);
else change(nod*2+1,mid+1,r,x,val);
pushup(nod);
}
void find(int nod,int l,int r,int L,int R)
{
if(l==L&&r==R)
{
for(int i=0;i<6;i++)ans[i]=(ans[i]+tree[nod].jia[i])%mod;
return;
}
if(R<=mid)find(nod*2,l,mid,L,R);
else if(L>mid)find(nod*2+1,mid+1,r,L,R);
else{
find(nod*2,l,mid,L,mid);
find(nod*2+1,mid+1,r,mid+1,R);
}
}
signed main()
{
scanf("%lld",&n);
for(int i=1;i<n;i++)
{
scanf("%lld%lld",&x,&y);
x++;y++;
add(x,y);
add(y,x);
}
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
dfs(1,0);
build(1,1,n);
scanf("%lld",&m);
while(m--)
{
scanf("%s",s);
if(s[0]=='R')
{
int res=1,sum=1;
scanf("%d",&x);
x++;
for(int i=0;i<6;i++)ans[i]=0;
find(1,1,n,seg[x],seg[x]+size[x]-1);
for(int i=0;i<6;i++)
{
res=(long long)res*kuai(xu[i],ans[i])%mod;
sum=(long long)sum*(ans[i]+1)%mod;
}
printf("%lld %lld\n",res,sum);
}
else{
scanf("%lld%lld",&x,&y);
x++;
change(1,1,n,seg[x],y);
}
}
return 0;
} D.珂朵莉的无向图
简单题，直接宽搜。
把一开始的t个点都加入队列，宽搜求出每个点的最短路径。最后记录答案，输出。
时间复杂度O(qn)
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,Q,x,y,t,s,top,ans,head[N],dis[N];
queueq;
bool vis[N];
struct node{
int too,next;
}edge[N];
void add(int a,int b)
{
edge[++top].too=b;edge[top].next=head[a];head[a]=top;
}
int main()
{
scanf("%d%d%d",&n,&m,&Q);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
while(Q--)
{
while(!q.empty())q.pop();
scanf("%d%d",&t,&s);
ans=0;
for(int i=1;i<=n;i++)
{
vis[i]=false;
dis[i]=1e9;
}
for(int i=1;i<=t;i++)
{
scanf("%d",&x);
q.push(x);
dis[x]=0;
vis[x]=true;
//ans++;
}
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(!vis[v])
{
dis[v]=dis[u]+1;
vis[v]=true;
q.push(v);
//if(dis[v]<=s)ans++;
}
}
}
for(int i=1;i<=n;i++)
if(dis[i]<=s)ans++;
printf("%d\n",ans);
}
return 0;
} E.珂朵莉的数列
难度中等偏高，思维难度较高，代码实现中等。
我们考虑每个数对答案的贡献，比如总共有8个数，考虑第5个数，如果第3个数和第5个数符合条件，对答案的贡献就是(3-1+1) * (8-5+1)
查找符合条件的数可以用树状数组实现，代码和求逆序对差不多，就是原来是加一，现在是加自己的位置。
注意：要高精度，可以使用两个int，分开来存。
时间复杂度O(nlog(n))
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2000005;
int n,ans1,ans2,a[N],b[N],c[N];
int lowbit(int x)
{
return x&-x;
}
void add(int x,int y)
{
while(x<=n)
{
c[x]+=y;
x+=lowbit(x);
}
}
int query(int x)
{
int res=0;
while(x)
{
res+=c[x];
x-=lowbit(x);
}
return res;
}
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
b[i]=a[i];
}
sort(b+1,b+n+1);
for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+n+1,a[i])-b;
for(int i=1;i<=n;i++)
{
int t=(query(n)-query(a[i]))*(n-i+1);
add(a[i],i);
ans2+=t;
ans1+=ans2/10000000000000000ll;
ans2%=10000000000000000ll;
}
if(ans1)printf("%lld%016lld",ans1,ans2);
else printf("%lld\n",ans2);
return 0;
} 
美的集团公司福利 878人发布