xtu oj 1522 格子

这篇具有很好参考价值的文章主要介绍了xtu oj 1522 格子。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

一个n×m的网格,格子里最多能放一枚棋子,将k枚棋子随机放入不同的网格中,使得同行同列最多只有一枚棋子,请问概率是多少?

输入格式

第一行是一个整数T (1≤T≤512),表示样例的个数。

以后每行一个样例,为三个整数n,m,k, (1≤n,m,k≤8)

输出格式

每行输出一个样例的结果,如果概率为0,输出0;如果概率为1,输出1;否则输出一个分数x/y,保证x与y互质。

样例输入

2
3 3 2
3 3 3

样例输出

1/2
1/14

AC代码

#include<stdio.h>
#define ll long long
ll gcd(ll a,ll b){
	ll t;
	while(a%b!=0){
		t=a%b;
		a=b;
		b=t;
	}
	return b;
}
//找最小值 
ll Min(ll a,ll b){
	if(a>b)return b;
	else return a;
}
//第一个棋子n*m种放法,第二个棋子n*m-1放法,以此类推 
ll Solve(ll m,ll n){
	ll i,res=1;
	for(i=m;i>=m-n+1;i--){
		res*=i;
	}
	return res;
}
int main(){
    int T;
	scanf("%d",&T);
	while(T--){
		 int i;
		 ll n,m,k;
		 scanf("%I64d%I64d%I64d",&n,&m,&k);
		 ll min=Min(n,m);
		 if(k>min)printf("0\n");
		 else if(k==1)printf("1\n");
		 else{
		 	ll fm=Solve(n*m,k);
		    ll fz=1;
		    ll t=1;
		    for(i=0;i<k;i++){
		    	t=(n-i)*(m-i);
		    	fz*=t;
			} 
		    ll g=gcd(fz,fm);
		    fz/=g;
		    fm/=g;
		    printf("%I64d/%I64d\n",fz,fm);
		 }
	}	
}

解题思路:第一个棋子情况n*m,消去所在行和列,第二个棋子情况(n-1)*(m-1),以此类推。

总数:第一个棋子n*m种放法,第二个棋子n*m-1放法,以此类推 

AC代码

#include<stdio.h>
#define ll long long
ll gcd(ll a,ll b){
	ll t;
	while(a%b!=0){
		t=a%b;
		a=b;
		b=t;
	}
	return b;
}
//找最小值 
ll Min(ll a,ll b){
	if(a>b)return b;
	else return a;
}
//第一个棋子n*m种放法,第二个棋子n*m-1放法,以此类推 
ll Solve(ll m,ll n){
	ll i,res=1;
	for(i=m;i>=m-n+1;i--){
		res*=i;
	}
	return res;
}
int main(){
    int T;
	scanf("%d",&T);
	while(T--){
		int i;
		 ll n,m,k;
		 scanf("%I64d%I64d%I64d",&n,&m,&k);
		 ll min=Min(n,m);
		 if(k>min)printf("0\n");
		 else if(k==1)printf("1\n");
		 else{
		 	ll fm=Solve(n*m,k);
		    //放入棋子剩余的格子数 
		    ll grid=n*m;
		    ll fz=1;
		    for(i=1;i<=k;i++){
		      fz*=grid;
		      //有重复减去的,所以要加上重复减去的 
		 	  grid=grid-n-m+1+2*(i-1);
		    }
		    ll g=gcd(fz,fm);
		    fz/=g;
		    fm/=g;
		    printf("%I64d/%I64d\n",fz,fm);
		 }
	}	
}

解题思路:先考虑特殊情况,k=1时,概率为1;k大于min(n,m),概率为0。利用剩余格子计算即可,放一个棋子消去棋子所在的行和列,下一个棋子在剩余棋子中填就行。注意考虑重复的情况。文章来源地址https://www.toymoban.com/news/detail-811790.html

到了这里,关于xtu oj 1522 格子的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • xtu oj 1340 wave

    一个n列的网格,从(0,0)网格点出发,波形存在平波(从(x,y)到(x+1,y)),上升波(从(x,y)到(x+1,y+1)),下降波(从(x,y)到(x+1,y−1))三种波形,请问从(0,0)出发,最终到达(n,0)的不同波形有多少种?如图,3列网格有7种不同的波形。 第一行是样例数T(1≤T≤42)。 以后每行一个整数n(1≤n≤42

    2024年02月01日
    浏览(90)
  • XTU-OJ 1343-青蛙

    有n个位置按顺时钟排列成一个圆,分别编号从1∼n。一只青蛙最开始在1号位置上,它每次可以跳往与之相隔k个位置的位置上。比如,n=5,k=2时, 青蛙从位置1可以按逆时钟方向跳到位置3,也可以按顺时钟方向跳到位置4。请问这只青蛙能跳到所有的位置上吗? 第一行输入一个

    2024年02月07日
    浏览(36)
  • XTU-OJ 1258-矩阵

    编写一个程序,将1~n2按行依次填入n×n的矩阵,执行若干条行或者列的循环移动的指令,再将数字按行依次取出。 指令如下: 指令 含义 L x y x行循环左移y次 R x y x行循环右移y次 U x y x列循环上移y次 D x y x列循环下移y次 第一行是一个整数K,表示样例的个数。 每个样例的第一

    2024年01月20日
    浏览(35)
  • XTU-OJ 1170-ICPC

    题目描述 ACM/ICPC比赛涉及的知识点非常多,一个队伍三个人需要能够互补。一个队伍某个知识点的高度是三个人中水平最高的那个人决定。现在给你三个人的每个知识点的水平情况,请计算一下这个队伍的水平。 输入 存在多个样例。每个样例的第一行是一个整数N(3≤N≤100

    2024年02月08日
    浏览(37)
  • XTU-OJ 1172-因子和

    题目描述 给一个正整数n,请求n所有因子的累加和。 输入 每行一个整数n,1≤n≤100,000,000。如果n为0表示输入结束,不需要处理。 输出 每行输出一个结果。 样例输入 样例输出 解题思路: 一眼看见数据 n 最大能到 1e8,用暴力不知道是否会超时,这里就继续沿用 质因数分解

    2024年02月08日
    浏览(35)
  • XTU-OJ 1221-Binary

    题目描述 给你一个非负整数n(0≤n≤232-1),求其二进制里面最长连续1数码的长度。 比如,7的二进制为111,所以最长连续1数码的长度为3;13的二进制为1101,所以最长连续1数码的长度为2. 输入 第一行是一个整数K(K≤20000),表示样例的个数; 以后每行一个整数n。 输出 每行输出一

    2024年02月08日
    浏览(35)
  • xtu oj 1334 Least Common Multiple

    一个集合,任取3个不同的元素,求其最小公倍数中最小的值是多少? 第一行是样例数T(1≤T≤100)。 每个样例的第一行是一个整数n(3≤n≤50),表示集合元素的个数。 每个样例的第二行是n个整数a1,a2,…,an,1≤ai≤106。 每个样例输出一行。 AC代码 遇到比较多个数值时,可以采用

    2024年01月17日
    浏览(27)
  • 湘大 XTU OJ 1256 湘潭大学 题解(非常详细):枚举

    1256 湘潭大学 湘潭大学简称 “XTU” ,作为即将成为湘大的一份子,怎么不能为湘大添砖加瓦了?现在给你一个 字符串 ,请你计算一下,从中选取字符, 最多能组成多少个“XTU”? 第一行是一个整数K,表示样例的个数。 以后每行一个字符串, 字符串只包含英文大写字母,

    2024年02月13日
    浏览(43)
  • 湘潭大学 湘大 XTU OJ 1271 Color 题解(非常详细)

    链接 1271 题面 Alice在玩一个游戏,她在一个m×n的格子里,随机涂黑k个格子。然后她每次可以把一行或者一列的格子染成红色,但是这一行中不能有黑色的格子。 请问她最多能把多少个格子涂成红色? 第一行是一个整数T(T≤100),表示样例的个数。 每个样例的第一行是m(1≤

    2024年02月11日
    浏览(39)
  • 湘潭大学 湘大 XTU OJ 1055 整数分类 题解(非常详细)

    整数分类 Description 按照下面方法对整数x进行分类:如果x是一个个位数,则x属于x类;否则将x的各位上的数码累加,得到一个新的x,依次迭代,可以得到x的所属类。比如说24,2+4=6,则24的类别数是6;39,3+9=12,1+2=3,则39的类别数是3。 输入        每行输入一个非负整数

    2024年02月12日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包