王清楚

07-11 10:22 牛客运营

发布于北京

关注

【题解】牛客周赛Round50

牛客周赛50题解

A

语法题，直接模拟

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
using ll =long long;
const int N=1e6+50;
const int mod=998244353;
void solve() {
    ll a,b,x;
    cin>>a>>b>>x;
    if(min(a,b)+x>max(a,b)) cout<<"YES\n";
    else cout<<"NO\n";
}
signed main() 
{		
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--)solve();
	return 0;
}

B

只用加法和乘法是最优的，因此可以全排列之后枚举每个位置是用乘号还是加号还是括号，或者直接分类讨论，枚举使用了几次乘号和用不用括号也可以。

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
using ll =long long;
const int N=1e6+50;
const int mod=998244353;

void solve() {
    ll a,b,c;
    cin>>a>>b>>c;
    ll ans=a*b*c;
    ans=max(ans,a+b+c);
    ans=max(ans,a+b*c);
    ans=max(ans,c+b*a);
    ans=max(ans,b+c*a);
    ans=max(ans,(a+b)*c);
    ans=max(ans,(b+c)*a);
    ans=max(ans,(a+c)*b);
    cout<<ans<<"\n";
}
signed main() 
{		
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--)solve();
	return 0;
}

C

做法同上一题，排除 $a$ 和 $c$ 先运算的情况即可

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
using ll =long long;
const int N=1e6+50;
const int mod=998244353;
void solve() {
    ll a,b,c;
    cin>>a>>b>>c;
    ll ans=a*b*c;
    ans=max(ans,a+b+c);
    ans=max(ans,a+b*c);
    ans=max(ans,c+b*a);
    ans=max(ans,(a+b)*c);
    ans=max(ans,(b+c)*a);
    cout<<ans<<"\n";
}
signed main() 
{		
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--)solve();
	return 0;
}

D

题意:要求一组 $a_1,b_1,a_2,b_2$ 使得 $ax^2+bx+c=(a_1x+b1)*(a_2x+b_2)$

等价于 $a=a_1*a_2,b=a_1*b_2+a_2*b_1,c=b_1*b_2$

一种方法是直接根号枚举 $a$ 和 $c$ 的因数作为 $a_1$ 和 $b_1$ ,代入 $a=a_1*a_2,c=b_1*b_2$ 求出 $a_2,b_2$ 然后检查是否满足 $b=a_1*b_2+a_2*b_1$ ，注意负因数的情况。

另一种方法是注意到 $\frac{-b_1}{a_1}$ , $\frac{-b_2}{a_2}$ 即为方程 $ax^2+bx+c=0$ 的两个根，因此直接通过求根公式判断是否有根，有则解出两根后判断是否是有理根，然后回代解出一组 $a_1,b_1,a_2,b_2$ 即可。注意两个根的最简分数的分母的乘积必须是 $a$ 的约数才可行。

代码：

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
using ll =long long;
const int N=1e6+50;
const int mod=998244353;
void solve() {
    ll a,b,c;
    cin>>a>>b>>c;
    ll delta=b*b-4*a*c;
    if(delta<0) return cout<<"NO\n",void();
    ll t=sqrtl(delta);
    if(t*t!=delta) return cout<<"NO\n",void();
    ll x=-b+t,y=-b-t,domx=2*a,domy=2*a;
    ll gcdx=__gcd(x,domx),gcdy=__gcd(y,domy);
    domx/=gcdx,x/=gcdx,domy/=gcdy,y/=gcdy;
    if(a%abs(domx*domy)) return cout<<"NO\n",void();
    ll z=a/domx/domy;
    domx*=z,x*=z;
    cout<<-1*domx<<" "<<x<<" "<<-1*domy<<" "<<y<<"\n";
}
signed main() 
{		
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t=1;
	cin>>t;
	while(t--)solve();
	return 0;
}

E

题意转化为，从根节点出发每次随机跳到下一层的一个节点，如此重复直到在一个叶子节点，求停下时的深度的期望。

要求停下深度的期望即求在每个深度下停下的概率乘上对应深度的和即可。设 $p_i$ 是到达第 $i$ 层节点的概率 $q_i$ 是停留在第 $i$ 层的概率

因此停留层数的数学期望 $E=\sum_{i=1}^n q_i*i$ 而 $p_i=q_i+q_(i+1)+..+q_n$ 因此交换求和顺序便可以推出：

$E=\sum_{i=1}^n q_i*i =\sum_{i=1}^n \sum_{j=i}^n q_i =\sum_{i=1}^n p_i$

然后考虑计算 $p_i$ 点要到达第 $i$ 层的事件要求点要到达第 $i-1$ 层，并且在第i-1层随机的时候没有随机到叶子节点。记 $i-1$ 层有 $a_i$ 个节点其中有 $b_i$ 个叶子那么没有随机到叶子节点的概率是( $a_i-b_i$ )/ $a_i$ 因此

$p_i$ = ${p}_{i-1}$ $*(a_i-b_i)$ / $a_i$

可以通过一次dfs计算 $a_i$ 和 $b_i$ 。

代码：

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
using ll =long long;
const int N=1e6+50;
const int mod=998244353;
#define int long long
ll ifac[N],fac[N],mi[N],dep[N],p[N];
ll a[N],b[N];
ll getmi(ll a,ll x)
{
	ll rt=1;
	while(x)
	{
		if(x&1) rt=rt*a%mod;
		a=a*a%mod,x>>=1;
	}
	return rt;
}

inline ll C(ll n,ll m)
{
	if(n<m||n<0||m<0) return 0;
	return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}


ll invv(ll x)
{
	return getmi(x,mod-2);
}
vector<ll> g[N];
ll maxdep=1;
void dfs(int x,int fa)
{
    dep[x]=dep[fa]+1;
    maxdep=max(maxdep,dep[x]);
    a[dep[x]]++;
    b[dep[x]]+=(x!=1 && g[x].size()==1 );
    for(auto u:g[x])
    {
        if(u==fa) continue;
        dfs(u,x);
    }
    
}
void solve() {
	ll n,x,y;
	cin>>n;
    if(n==1) return cout<<"0\n",void();
    rep(i,1,n-1)
    {
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dep[0]=0;
    dfs(1,0);
    ll ans=0;
    p[1]=1;
    rep(i,2,n)
    {
        p[i]=p[i-1]*(a[i]-b[i])%mod*invv(a[i])%mod;
    }
    rep(i,1,n)
    {
       // cout<<a[i]<<" "<<b[i]<<" "<<p[i]<<" \n";
        ans+=p[i];
        ans%=mod;
    }
    cout<<ans<<"\n";
}
signed main() 
{		
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--)solve();
	return 0;
}

F

如果 $R$ 不为两个完全平方数和，则答案为 $\inf$ 。

否则设 $R=x^2+y^2$ ，对所有满足条件的 $(x,y)$ 求最大公约数，记作 $d$ 。答案为 $d^2$ ，若 $\frac{R}{d^2} \equiv 2 \pmod 4$ ，则答案为 $2d^2$ 。

证明：假定有 $k$ 组 $(x,y)$ 满足 $R=x^2+y^2$ ，则一个点可以延伸出 $4k$ 条边。考虑规约同余类，则可得到 $x,y$ 上的同余类各有 $d$ 个，因此答案为 $d^2$ 。但是当 $\frac{R}{d^2} \equiv 2 \pmod 4$ 时，在一个同余类下，不同奇偶性的点彼此也无法到达(此时的 $(x,y)$ 互质并且同为奇数，因此与其联通的点的横纵坐标的奇偶性都相同)，此时答案为 $2d^2$ 。至于可达性可以根据裴蜀定理和调整法构造出来。

暴力枚举 $R$ 的分解方式可以得到一个 $O(\sqrt{R})$ 的做法，然而结合数论知识可以只在分解质因数的复杂度解决此题。

事实上若R为两个平方数的和，则答案为 $R$ 除去所有其 $4k+1$ 类型的素因子。证明可参考讲解视频和以下三条引理，由于属于数论知识，在此不详细展开。

lemma 1:

$n$能表示成为两个平方数的和当且仅当$n$的所有$4*k+3$型素因子在$n$中出现次数是偶数

lemma 2:

如果$a$和$b$互素，则$a^2+b^2$的所有因子都能表示为两个平方数之和。

lemma 3:

$m能表示成$m$=$a^2+b^2$，且gcd(a,b)= 1，当且仅当以下两个条件之一成立:
1.$m$是奇数，且$m$的每个素因子都模4余1

2.m是偶数，m/2是奇数且m/2的每个素因子都模4余1

代码：

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
using ll =long long;
const int N=1e6+50;
const int mod=998244353;
#define int long long
ll ifac[N],fac[N],mi[N],d[N],f[N],s[N];
ll getmi(ll a,ll x)
{
	ll rt=1;
	while(x)
	{
		if(x&1) rt=rt*a%mod;
		a=a*a%mod,x>>=1;
	}
	return rt;
}

inline ll C(ll n,ll m)
{
	if(n<m||n<0||m<0) return 0;
	return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
void init(int N=1000005)
{
	fac[0] = fac[1] = ifac[0] = ifac[1]= 1;
    for (ll i = 2; i < N; ++i) {
        fac[i] = fac[i - 1] * i % mod;
        //inv[i] = (P - P / i) * inv[P % i] % P;
        //ifac[i] = (ll)ifac[i - 1] * inv[i] % P;
		

    }
	
	ifac[N-1]=getmi(fac[N-1],mod-2);
	    for (ll i = N-2; ~i; --i) {
        ifac[i] = (ll)ifac[i + 1] * (i+1)% mod;
    }


}
ll invv(ll x)
{
	return getmi(x,mod-2);
}
ll gcd(int x,int y)
{
    if(x==0) return y;
    else if(y==0) return x;
    else return __gcd(x,y);
}

void solve() {
	ll n;
	cin>>n;
    ll ans=1;
    for(int i=2;i*i<=n;i++)
    {
        if(n%i!=0) continue;
        int p=0;
        while(n%i==0) n/=i,p++;
        if(i%4!=1)
        {
            if(i%4==3 && (p&1)) return cout<<"inf\n",void();
            while(p--) ans*=i;
        }
    }
        if(n%4!=1)
        {
            if(n%4==3) return cout<<"inf\n",void();
            ans*=n;
        }
        
    cout<<ans<<"\n";
}
signed main() 
{		
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t=1;
	cin>>t;
	while(t--)solve();
	return 0;
}