Talent Show G 蓝

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