蓝
题目链接：https://www.luogu.com.cn/problem/P4377
类型：二分法与01分数规划
大意是根据n头奶牛的体重和才艺值选择出战的一组奶牛，才艺和体重比值最大的获胜，有体重下限限制（需要凑够这些重量）。
solution：这个问题很像01背包，选择或者不选。只不过价值变成了比值。我们可以二分这个比值，然后每次计算一次01背包，用才艺减去这个比值后的重量，如果得到的fw小了，说明比值大了，否则说明比值小了。根据背包后的fw确定单调范围。
code：
bool check(double x){
for(int i=1;i<=n;i++){
a[i].y = (double)a[i].t - a[i].w*x;
}
for(int i=1;i<=w;i++) f[i] = -INF;
f[0] = 0;
for(int i=1;i<=n;i++){
for(int j=w;j>=0;j--){
if(j+a[i].w>=w) f[w] = max(f[w],f[j]+a[i].y);
else f[j+a[i].w] = max(f[j+a[i].w],f[j]+a[i].y);
}
}
return f[w]<0;
}
int main()
{
//cin.ignore(numeric_limits<streamsize>::max(),'\n');
ios_base::sync_with_stdio(0); cin.tie(0); //cout.tie(0);
cin>>n>>w;
double l=0,r=0;
for(int i=1;i<=n;i++){
cin>>a[i].w>>a[i].t;
r+=a[i].t;
}
for(int i=0;i<=50;i++){
double mid = (r+l)/2;
if(check(mid)){
r = mid;
}else{
l = mid;
}
}
ll ans = l * 1000;
cout<<ans<<endl;
}
球形空间产生器 蓝
题目链接：https://www.luogu.com.cn/problem/P4035
类型：高斯消元，数学
大意是给出一个n维的球的n+1个球面上的点，确定球心坐标。
solution：首先可以确定的是每个点到球心的距离是一样的。我们总是可以得到 (a1 - x1)^2 + (a2 - x2)^2 +... = r
其中r为球的半径。我们需要求出这个球的各个x。通过n+1个方程，我们可以消减掉r。这样就形成了n个方程式解决n个变量。相减后直接移项然后跑一遍高斯消元即可。
code：
int main()
{
//cin.ignore(numeric_limits<streamsize>::max(),'\n');
//ios_base::sync_with_stdio(0); cin.tie(0); //cout.tie(0);
cin>>n;
for(int i=0;i<=n;i++){
for(int j=0;j<n;j++){
cin>>c[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
a[i][j] = 2*(c[i][j]-c[i+1][j]);
a[i][n]+=(c[i][j]*c[i][j]) - (c[i+1][j]*c[i+1][j]);
}
}
int ff = gauss();
for(int i=0;i<n-1;i++){
printf("%.3lf ",a[i][n]);
}
printf("%.3lf\n",a[n-1][n]);
// for(int i=0;i<n;i++){
// for(int j=0;j<=n;j++){
// printf("%.3lf ",a[i][j]);
// }
// printf("\n");
// }
}
蓝
题目链接：https://www.luogu.com.cn/problem/P2455
类型：高斯消元
算是高斯消元的板子题，大意是给出n元一次方程组，求各个x解。
solution：这个题就相当好做了，直接存矩阵后跑一遍高斯消元。然后从每个方程组中去找x1，x2等，因为存在x在随机方程组中出现，先vector存起来x和它的值，然后根据x进行排序即可。
code：
int main()
{
//cin.ignore(numeric_limits<streamsize>::max(),'\n');
//ios_base::sync_with_stdio(0); cin.tie(0); //cout.tie(0);
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<=n;j++){
cin>>a[i][j];
}
}
int t = gauss();
vector<tdata> ve;
if(t==0){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j]!=0){
ve.push_back({j+1,a[i][n]});
break;
}
}
}
sort(ve.begin(),ve.end(),cmp);
for(auto i:ve){
printf("x%d=%.2lf\n",i.num,i.sum);
}
}else if(t==1){
cout<<0<<endl;
}else{
cout<<-1<<endl;
}
}
可乐 绿
题目链接：https://www.luogu.com.cn/problem/P3758
类型：矩阵快速幂，矩阵加速
大意是给出城市的个数和城市道路的条数，存在一个机器人在1号城市。每一秒，它可能的操作，自爆，停留，到下一个城市。求t秒后的各种方案。
在老罗新书中，给出过定理，求路径数量可以矩阵加速。
solution：矩阵双向存储路径，然后自身存在路径，我们可以令0的位置是自爆状态，每个i点都可以到达0。
然后跑一遍矩阵加速。
对于任意从1 到 i，将不同的方案数量累加起来。
code：
int main()
{
//cin.ignore(numeric_limits<streamsize>::max(),'\n');
ios_base::sync_with_stdio(0); cin.tie(0); //cout.tie(0);
matrix a;
mem(a.m);
cin>>n>>m;
int x,y;
for(int i=1;i<=m;i++){
cin>>x>>y;
a.m[x][y] = 1;
a.m[y][x] = 1;
}
for(int i=0;i<=n;i++) a.m[i][i] = 1;
for(int i=1;i<=n;i++) a.m[i][0] = 1;
cin>>k;
matrix ans = pow_matrix(a);
int sum = 0;
for(int i=0;i<=n;i++){
sum+=ans.m[1][i];
sum%=mod;
}
cout<<sum<<endl;
}