牛客周赛-Round-84
目录
牛客周赛 Round 84
这场比赛确实比以前的水了很多，不过不影响，有学习意义即可
思路：直接判断三个数是否相同，想通就输出Yes，否则就是No
#include<bits/stdc++.h>
using namespace std;
int a,b,c;
signed main()
{
cin>>a>>b>>c;
if(a==b&&b==c)
{
cout<<"Yes";
}
else
{
cout<<"No";
}
}
思路：这题明显不是考验排列组合的，因为要使得a[i]不同，也就说明最多只有两种，从大到小一次，从小到大一次，然后直接去统计两个数之间的差值累加和即可
#include<bits/stdc++.h>
using namespace std;
int n;
int a[105];
int cnt[105];
signed main()
{
cin>>n;
set<int> s;
for(int i=1;i<=n;i++)
{
cin>>a[i];
s.insert(a[i]);
cnt[a[i]]++;
}
sort(a+1,a+1+n);
int ans=0;
int cha=a[1];
int sum=0;
for(int c:s)
{
sum+=c-cha;
cha=c;
}
if(s.size()==1)
ans=1;
else
ans=2;
cout<<ans<<" "<<sum;
return 0;
}
思路：可以用前缀和，先把每两两之间的差值算出来，然后用前缀和数组pre去统计从第1个差值到第i个差值的总和，然后就可以跑一遍从k+1到n,去统计pre[i]-pre[i-k]的累加和
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
string s;
int cha[1000006];
int pre[1000006];
signed main()
{
cin>>n>>k;
cin>>s;
s=' '+s;
for(int i=2;i<=n;i++)
{
cha[i]=abs(s[i]-s[i-1]);
}
if(k==2)
{
int sum=0;
for(int i=2;i<=n;i++)
{
sum+=cha[i];
}
cout<<sum<<"\n";
return 0;
}
int sum=0;
for(int i=2;i<=n;i++)
{
pre[i]=pre[i-1]+cha[i];
}
k-=1;
for(int i=k+1;i<=n;i++)
{
sum+=pre[i]-pre[i-k];
}
cout<<sum;
return 0;
}
思路：这题一看题就是属于
带权树重心
类问题了，题目中说是将一整颗树变成两棵树，也就是说，我们只需要去先去求到一整棵树的权值，然后
abs(用整棵树的权值-当前结点的权值-abs(当前结点的父节点-当前节点)
，数学公式可以这么去表示，那么我们应该先去跑dfs，先去把整棵树每个点的权值求出来，叶子结点的权值是0，然后我们在dfs遍历中找到每个点权值最大的子节点的编号，然后最后dfs跑完遍历一遍，去寻找绝对值后的最小值，我们在遍历过程中要去跳过叶子结点
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int u,v;
vector<int> e[200005];
int ans[200005];
int mx[200005];
void dfs(int v,int fa)
{
int maxn=0;
for(int u:e[v])
{
if(u!=fa)
{
dfs(u,v);
ans[v]+=ans[u]+abs(v-u);
if(ans[u]>maxn)
{
maxn=ans[u];
mx[v]=u;
}
else if(ans[u]==maxn)
{
mx[v]=min(mx[v],u);
}
}
}
}
signed main()
{
cin>>n;
if(n==1)
{
cout<<0;
return 0;
}
for(int i=1;i<=n-1;i++)
{
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1,0);
int sum=ans[1];
int minn=1e12;
for(int i=1;i<=n;i++)
{
if(ans[i]!=0)
{
minn=min(minn,abs(ans[mx[i]]-(sum-ans[mx[i]]-abs(i-mx[i]))));
}
}
cout<<minn;
return 0;
}
思路：我们可以现将这个题转换为两个数相邻的概率，如果先从数组中除去两个数，那么还剩下n-2个数，然后出现的概率为(n-2)!,如果将捆绑的两个数插入有2*(n-1)种可能，除以总的情况n!，那么说明每两个数相邻的概率为2/n;
那么根据题目来说，我们应该去求2/n*(a[j]-a[i]){1<=i<j<=n};但是这样的时间复杂度为O（n^2），还是太高了，如何降低时间复杂度呢？
直接用排序+前缀和去求任意两个数之间的绝对值之差即可，时间复杂度降为O（n）刚好满足题意
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M = 1e9+7;
int a[200005];
long long pow(long long a, int k) {
if (k == 0) return 1;
return pow(a*a%M, k/2)*(k%2?a:1)%M;
}
int main() {
int n;
cin>>n;
for (int i=1; i<=n; i++)
cin>>a[i];
sort(a+1, a+1+n);
long long ans = 0, sum = 0;
for (int i=1; i<=n; i++)
ans += (long long)a[i]*(i-1) - sum, ans %= M, sum += a[i];
cout<<ans*2%M*pow(n, M-2)%M<<'\n';
return 0;
}