华师一附中OI组

标题: UVA 861 Little Bishops [打印本页]
作者: 吴语林    时间: 2018-7-6 18:29
标题: UVA 861 Little Bishops
https://www.luogu.org/problemnew/show/UVA861

A bishop is a piece used in the game of chess which can onlymove diagonally from its current position. Two bishops attackeach other if one is on the path of the other. In the figurebelow, the dark squares
represent the reachable locations forbishop B1 from its current position. Bishops B1 and B2 arein attacking position,
while B1 and B3 are not. Bishops B2and B3 are also in non-attacking position.Given two numbers n and k,
determine the number ofways one can put k bishops on an n × n chessboard so thatno two of them are in attacking positions

Input
The input file may contain multiple test cases. Each testcase occupies a single line in the input file and contains twointegers n (1 ≤ n ≤ 8)
and k (0 ≤ k ≤ n2).A test case containing two zeros terminates the input.

Output
For each test case, print a line containing the total number of ways
one can put the given number ofbishops on a chessboard of the given size so that no two of them lie in attacking positions. You maysafely assume that this
number will be less than 1015

Sample Input
8 6
4 4
0 0
Sample Output
5599888
260

作者: 吴语林    时间: 2018-7-6 18:30
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <map>
  6. #include <string>
  7. #include <vector>
  8. #include <queue>
  9. #include <stack>
  10. #include <cstdio>
  11. #include <cstdlib>
  12. using namespace std;
  13. long long n,k,whi[100],bla[100],lw,lb,all=0,f[100][100];
  14. void init()
  15. {
  16.     memset(bla,0,sizeof(bla));
  17.     memset(whi,0,sizeof(whi));
  18.     for(int i=1;i<=n;i++)
  19.         if(i<=n/2)
  20.                 {
  21.             whi[i]=2*i-1;
  22.             bla[i]=2*i;
  23.         }
  24.         else
  25.                 {
  26.             if(whi[n+1-i]==0)
  27.                 whi[i]=whi[i-1]+2;
  28.             else
  29.                                 whi[i]=whi[n+1-i];
  30.             bla[i]=bla[n-i];
  31.         }
  32. }
  33. long long suan_bla(int qi)
  34. {
  35.         memset(f,0,sizeof(f));
  36.         if(qi==0)
  37.                 return 1;
  38.         f[1][1]=bla[1];
  39.         for(int i=2;i<=qi;i++)
  40.                 f[1][i]=0;
  41.         for(int i=2;i<=lb;i++)
  42.         {
  43.                 f[i][1]=f[i-1][1]+bla[i];
  44.                 for(int j=2;j<=qi;j++)
  45.                         f[i][j]=f[i-1][j]+max((long long)0,f[i-1][j-1]*(bla[i]-j+1));
  46.         }
  47.         return f[lb][qi];
  48. }
  49. long long suan_whi(int qi)
  50. {
  51.         memset(f,0,sizeof(f));
  52.         if(qi==0)
  53.                 return 1;
  54.         f[1][1]=whi[1];
  55.         for(int i=2;i<=qi;i++)
  56.                 f[1][i]=0;
  57.         for(int i=2;i<=lw;i++)
  58.         {
  59.                 f[i][1]=f[i-1][1]+whi[i];
  60.                 for(int j=2;j<=qi;j++)
  61.                         f[i][j]=f[i-1][j]+max((long long)0,f[i-1][j-1]*(whi[i]-j+1));
  62.         }
  63.         return f[lw][qi];
  64. }
  65. int main()
  66. {
  67.         scanf("%lld%lld",&n,&k);
  68.         while(n!=0||k!=0)
  69.         {
  70.                 if(n==1)
  71.                 {
  72.                         if(k==1||k==0)
  73.                                 printf("1\n");
  74.                         else
  75.                                 printf("0\n");
  76.                         scanf("%lld%lld",&n,&k);       
  77.                         continue;
  78.                 }
  79.                 all=0;
  80.                 init();
  81.             lw=n,lb=n-1;
  82.             sort(whi+1,whi+lw+1);
  83.             sort(bla+1,bla+1+lb);               
  84.             for(int i=0;i<=k;i++)
  85.                     all+=suan_bla(i)*suan_whi(k-i);
  86.             printf("%lld\n",all);
  87.                 scanf("%lld%lld",&n,&k);
  88.         }
  89.     return 0;
  90. }
复制代码
作者: 吴语林    时间: 2018-7-6 18:32
详细说明
作者: admin    时间: 2018-7-6 21:08
楼上WYL好牛呀  做法正确



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2