专栏首页wym牛客练习赛19-C-托米航空公司

牛客练习赛19-C-托米航空公司

链接:https://www.nowcoder.com/acm/contest/111/C 来源:牛客网

时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 262144K,其他语言524288K 64bit IO Format: %lld

题目描述

托米老师靠才华与颜值发家致富后,开了一家航空公司,公司的口号是“您想飞,我们便做您的翅膀~让您每次飞行都有独特的体验!”

但是现在有一个小小的问题需要解决,托米家的飞机每排有M个座位,有N排座位。因此座椅形成了M × N的网格(忽略过道),公司为每次航班都出售K张票。 为了满足口号中的“翅膀”部分,座位必须遵守以下规则:座位被占用时,座位正前方和座位后方的座位以及当前座位左边和右边必须是空的(大概是因为这个飞机会很大吧,boss就是这么任性哼)。 然后为了满足口号中的“独特体验”部分。公司则是对每一趟航班飞机的座位采取不同的安排,如果这一趟的某个座位是占用的,而另一趟的座位是空的,则这两趟飞机座位安排是不同的。 给你三个数字M,N和K。 现在需要从这些座位中选出k个合法的座位。由于这个数字可能非常大,我们只求它对420047取模的结果。

输入描述:

输入的第一行包含一个整数T,表示指定测试用例的数量。
每个测试用例前面都有一个空白行。
每个测试用例由包含三个整数M,N和K的一行组成。

输出描述:

对于每个测试用例输出一行,表示答案对420047取模的结果。

#include <bits/stdc++.h>

#define ll long long using namespace std; int a[85][85]; int dir[5][2]={-1,0, 1,0, 0,-1, 0,1, 0,0};//表示前后左右四个方向,多一个0,0是为了标记自身 int n,m; int mod=420047; int dfs(int k,int x)//k表示还要选多少个座位,x是已经遍历过多少座位  { if(k==0) return 1; int res=0; for(int i=1;i<=n;i++)    for(int j=1;j<=m;j++)       {  if(i*m+j<x)//i*m+j是当前座位序号,排数乘m加上第几列,最大序号是n*m  continue;//由于后面的遍历序号一定变大,小就跳过  if(a[i][j]==0)  { for(int k=0;k<5;k++)  a[i+dir[k][0]][j+dir[k][1]]++;//标记附近点和自身    res+=dfs(k-1,i*m+j);    res%=mod;    for(int k=0;k<5;k++)  a[i+dir[k][0]][j+dir[k][1]]--;//解除标记  }   } return res; } int main() { int t; memset(a,0,sizeof(a)); scanf("%d",&t); while(t--) { int k; scanf("%d %d %d",&n,&m,&k); int ans=dfs(k,0); printf("%d\n",ans); } return 0; } 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU 6611 K Subsequence (最小费用最大流)

    用户2965768
  • POJ - 2195 Going Home 最小费用最大流

    题意:多组输入,n行m列矩阵包含相等个数的 ‘m’ 和 ‘ H ’ 每个men要到达Home,每移动一个格子耗费 1,求最小花费。

    用户2965768
  • Educational Codeforces Round 67 (Rated for Div. 2) A~E 贪心,构造,线段树,树的子树

    Educational Codeforces Round 67 (Rated for Div. 2)

    用户2965768
  • 挑战程序竞赛系列(66):4.7字符串匹配(1)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 洛谷P1481 魔族密码(LIS)

    attack
  • hdu1040

    @坤的
  • 这绝对是C语言的一个经典例题了!

    意图很明显,要用swap函数中交换main函数中的a和b的值,但是很明显上述代码是达不到要求的,a和b的值没有发生改变。其实本题就是C中比较有名传址和传值的典型...

    7089bAt@PowerLi
  • 程序员面试金典 - 面试题 10.10. 数字流的秩(map/树状数组)

    假设你正在读取一串整数。每隔一段时间,你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。

    Michael阿明
  • POJ 刷题系列:1753. Flip Game

    POJ 刷题系列:1753. Flip Game 传送门:POJ 1753. Filp Game 题意: 一个4*4的矩阵,每一格要么是白色,要么是黑色。现在...

    用户1147447
  • 挑战程序竞赛系列(95):3.6数值积分(1)

    挑战程序竞赛系列(95):3.6数值积分(1) 传送门:AOJ 1313: Intersection of Two Prisms 题意: 有一个侧棱与Z轴平行...

    用户1147447

扫码关注云+社区

领取腾讯云代金券