备孕百度之星-9月14日

补最小生成树的板子，把星球联通做了。又发现了一个求期望的题目，做了一下。

星球联通

#include<bits/stdc++.h> 

using namespace std;
typedef long long ll;


int main( )
{
	//最小生成树
	int n, k;
	cin >> n >> k;
	long c[n-k];
	for(int i = 0; i < n-k; i++) cin >> c[i];
	long p[n][3];
	for(int i = 0; i < n; i++) cin >> p[i][0] >> p[i][1] >> p[i][2];
	vector<int> ans;//最小生成树的边
	long g[n][n], dis[n];
	int flag[n];
	memset(flag, 0, sizeof(flag));
	memset(dis, 0x3f, sizeof(dis)); 
	//prime
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			g[i][j] = pow(p[i][0] - p[j][0], 2) + pow(p[i][1] - p[j][1], 2) + pow(p[i][2] - p[j][2], 2);
		}
	}
	for(int i = 0; i < n; i++){
		int t = -1;
		for(int j = 0; j < n; j++)
			if(!flag[j] && (t == -1 || dis[t] > dis[j])) t = j;
		if(i) ans.push_back(dis[t]);
		flag[t] = 1;
		for(int j = 0; j < n; j++)
			if(!flag[j] && dis[j] > g[t][j]) dis[j] = g[t][j];
	}
	sort(ans.begin(), ans.end());
//	for(int i = 0; i < ans.size(); i++)
//		cout << ans[i] << endl;
	long sum = 0;
	for(int i = 0; i < n-k; i++){//免费建k-1个，还剩下 
		sum += ans[i];
	}
	long res = sum;//不额外买
	for(int i = 1; i < n-k; i++){//枚举额外买的数量 
		sum -= ans[n-k-i];
		res = min(res, sum + c[i-1]); 
	} 
	cout << res << endl;
	
	
	return 0;
}

一开始是java选手，用的prime，被卡常。痛定思痛，去敲了两天c++，stl又看了一遍，补了一些数论知识。用c++写了最小生成树，后面写错了：sum += c【i+1】,这样导致都加一起了，应该加c[i]后减去c[i-1]或者直接和sum + c[i]对比，这种小的细节在没有错误测试用例的提醒下，很难发现，目前想到的就是多写一些注释，尽量保证不要遗漏算法步骤。

萌新

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int T;
    cin >> T;
    while(T-- > 0){
        int a, b;
        cin >> a >> b;
        int mi = -1;
        int ma = -1;
        if(abs(a-b) == 1) {
            cout << -1 << " " << -1 << endl;
            continue;
        }
        if(abs(a-b) == 0 && a <= 2) {
            cout << -1 << " " << -1 << endl;
            continue;
        }
        if(abs(a-b) == 0 && a >= 2){
            cout << 2 << " " << a << endl;
            continue;
        }
        ma = max(a,b) - min(a,b);
        for(int i = 2; i * i <= max(a, b); i++){
            if((a % i) == (b % i)){
                mi = i;
                break;
            }
        }
        if(mi == -1) mi = ma;
        cout << mi << " " << ma << endl;
    }
    return 0;
}

猎人杀


#include<bits/stdc++.h> 

using namespace std;

int main( )
{	
	int T;
	cin >> T;
	while(T-- > 0){
		int t;
		int n;
		cin >> n;
		int bk = 0;//已经寄了的 
		int lang = -1;
		int tag[n];
		memset(tag, 0, sizeof(tag));//1表示寄了
		for(int i = 0; i < n; i++) {
			cin >> t;
			if(t == 1) lang = i;
		}  
		int kill[n][n];
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++){
				cin >> kill[i][j];
				kill[i][j]--; 
			} 
		int cur_l = 0;			
		//狼杀人
		while(tag[kill[lang][cur_l]] == 1) cur_l++;//找个活人 
		tag[kill[lang][cur_l]] = 1;
//		cout << "狼杀" << kill[lang][cur_l] + 1 << endl; 
		
		//死的猎人杀人 
		t = kill[lang][cur_l];
		bk++; 
		while((n-bk) > 2){
			//判断狼是否死
			if(tag[lang] == 1) break;//狼自杀 
			int in = 0; 
			while(tag[kill[t][in]] == 1) in++;//找个活人 
			tag[kill[t][in]] = 1;
			
//			cout << "猎人杀" << kill[t][in] + 1 << endl; 
			t = kill[t][in];
			if(tag[lang] == 1) break;//狼寄 
			bk++;
		}
		if(tag[lang] == 0){
			cout << "langren" << endl;
		}else{
			cout << "lieren" << endl;
		}
	} 
    return 0;
}

就喜欢刷简单题。。。

几何分布期望

题目：小A在玩一个网络游戏，有一个抽装备环节。装备池总共有n+m件装备，分别为n件普通装备和m件ssr装备。每次抽中一件ssr级装备，花费2元，不放回。每次抽中一件普通装备，花费1元，放回。所有装备抽中的概率相等。问：小A若想抽走所有ssr级装备，所有花费的期望是多少元？

先考虑在m+n张卡片中抽出一张ssr的期望次数。抽中的概率为m/(n+m)，故期望次数为1/p = n/m + 1。在n/m + 1的次数之前，即n/m次，全部都是抽中普通卡，故抽中一张的期望金币：2 + n/m。现在考虑抽出来了一个ssr，剩余n+m张的期望金币思路同上。

#include <iostream>
using namespace std;
double ans;
int main()
{
    int n, m; cin >> n >> m;
    for(int i=1; i<=m; i++)
        ans += 2.0 + double(n) / double(i);
    printf("%.2lf\n", ans);
    return 0;
}