牛客周赛 Round 29

发布时间:2024年01月21日

小红的中位数

思路:记录每个数的下标,如何按照数值排序;

1、n为奇数,删去一个数后,还剩下偶数个数,那么中位值一定是最中间的两个的平均值。

2、n为偶数,删去一个数后,还剩下奇数个数,那么中位值一定是最中间的哪个数。

代码:

void solve() {
 
    cin >> n;
 
    a = vector<pii> (n + 1);
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i].first;
        a[i].second = i;
    }
 
    sort(a.begin() + 1, a.end());
 
    vector<double> ans(n + 1);
    for (int i = 1; i <= n; ++ i) {
        if (n % 2 == 0) {
            if (i <= n / 2) {
                ans[a[i].second] = a[n / 2 + 1].first;
            } else {
                ans[a[i].second] = a[n / 2].first;
            }
        } else {
            if (i <= n / 2) {
                ans[a[i].second] = (a[n / 2 + 1].first + a[n / 2 + 2].first) / 2.0;
            } else if (i == n / 2 + 1) {
                ans[a[i].second] = (a[n / 2].first + a[n / 2 + 2].first) / 2.0;
            } else {
                ans[a[i].second] = (a[n / 2].first + a[n / 2 + 1].first) / 2.0;
            }
        }
    }
 
    for (int i = 1; i <= n; ++ i) {
        cout << fixed << setprecision(1) << ans[i] << '\n';
    }
 
}

小红构造数组

思路:本质上就是分解质因数,分解完质因数后,这些数都是质数,乘积为x。分解完质因数后,开始按照次数用堆排序,每次取出两个堆顶,插入答案数组中,然后判断相邻是否有相等的。

代码:

#define int ll
void solve() {
    ll n;
    cin >> n;
    if (n == 1) {
        cout << "-1" << endl;
        return;
    }
    vector<ll> f;
    for (int i = 2; 1LL * i * i <= n; i++) {
        while (n % i == 0) {
            f.push_back(i);
            n /= i;
        }
    }
    if (n > 1) f.push_back(n);
    map<ll, int> cnt;
    for (int v : f) cnt[v]++;
    priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> q;
    for (auto [k, v] : cnt) q.push({v, k});
    vector<int> f2;
    while (!q.empty()) {
        auto [c, u] = q.top(); q.pop();
        f2.push_back(u);
        c--;
        if (!q.empty()) {
            auto [c2, u2] = q.top(); q.pop();
            c2--;
            f2.push_back(u2);
            if (c2) q.push({c2, u2});
        }
        if (c) q.push({c, u});
    }
    for (int i = 1; i < f2.size(); i++) {
        if (f2[i - 1] == f2[i]) {
            cout << -1 << endl;
            return;
        }
    }
    cout << f2.size() << endl;
    for (int v: f2) cout << v << ' ';
}

小红又战小紫

思路:

如果存在某一堆石头为2,必然使用技能1;
如果不存在某一堆石头为2,必然使用技能2;

胜率为100%dp[i][j]代表还有i堆石头为1,j堆石头为2,先手方获胜概率;

i+j堆 ?i/(i+j)的概率转移到dp[i-1][j] ? j/(i+j)的概率转移到dp[i+1][j-1]

代码:

int qmi(int a,int p){
	int res=1;
	while(p){
		if(p&1)res=res*a%mod;
		a=a*a%mod;
		p>>=1;
	}
	return res;
}

map<int,int>mp;
int dp[1010][1010];

void solve(){
	int n,x;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>x,mp[x]++;

	//初始化逆元数组
	vector<int>inv(n+1);
	for(int i=1;i<=n;i++)
		inv[i]=qmi(i,mod-2);

	for(int i=0;i<=n;i++){//dp[i][j]代表 总共i堆石头,其中有j堆为2,i-j堆为1
		dp[i][0]=1;
		for(int j=1;j<=i;j++){
			dp[i][j]=(i-j)*inv[i]%mod*((1-dp[i-1][j]+mod)%mod)%mod;
			dp[i][j]+=j*inv[i]%mod*(1-dp[i][j-1]+mod)%mod;
			dp[i][j]%=mod;
		}
	}
	cout<<dp[n][mp[2]]<<endl;
}

文章来源:https://blog.csdn.net/weixin_73550568/article/details/135734988
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。