牛客周赛 Round 29

小红的中位数

思路：记录每个数的下标，如何按照数值排序；

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;
}