备孕百度之星-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;
}
这次准备百度之星真的是用心了，好几个数学建模的队友想和我一起参见华为杯我都拒绝了，真的不能三心二用，这次百度之星要好好冲个成绩出来