蓝
题目链接: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; }