BZOJ 4806 - 4809 象棋四题

2023-07-24 10:45:16

4806: 炮

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 103 Solved: 72
[Submit][Status][Discuss]

Description

众所周知，双炮叠叠将是中国象棋中很厉害的一招必杀技。炮吃子时必须隔一个棋子跳吃，即俗称"炮打隔子"。

炮跟炮显然不能在一起打起来，于是rly一天借来了许多许多的炮在棋盘上摆了起来……他想知道，在N×M的矩形

方格中摆若干炮（可以不摆）使其互不吃到的情况下方案数有几种。

棋子都是相同的。

Input

一行，两个正整数N和M。

N<=100,M<=100

Output

一行，输出方案数mod 999983。

Sample Input

1 3

Sample Output

HINT

Source

By FancyCoder

[Submit][Status][Discuss]

 #include<cstdio>

 #define N 105

 #define P 999983

 int n,m;long long f[N][N][N],ans;

 inline long long C(int a,int b){

     return b==?a:(1LL*a*(a-)/)%P;

 }

 main(){

     scanf("%d%d",&n,&m),f[][m][]=;

     for(int i=;i<n;++i)

         for(int j=;j<=m;++j)

             for(int k=;k<=m;++k)

                 if(f[i][j][k]){

                     (f[i+][j][k]+=f[i][j][k])%=P;

                     if(j>)(f[i+][j-][k+]+=f[i][j][k]*C(j,))%=P;

                     if(j>)(f[i+][j-][k+]+=f[i][j][k]*C(j,))%=P;

                     if(j>)(f[i+][j-][k]+=f[i][j][k]*C(j,)%P*C(k,))%=P;

                     if(k>)(f[i+][j][k-]+=f[i][j][k]*C(k,))%=P;

                     if(k>)(f[i+][j][k-]+=f[i][j][k]*C(k,))%=P;

                 }

     for(int i=;i<=m;++i)

         for(int j=;j<=m;++j)

             ans=(ans+f[n][i][j])%P;

     printf("%lld\n",ans);

 }

4807: 車

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 126 Solved: 45
[Submit][Status][Discuss]

Description

众所周知，車是中国象棋中最厉害的一子之一，它能吃到同一行或同一列中的其他棋子。車跟車显然不能在一起打

起来，于是rly一天又借来了许多许多的車在棋盘上摆了起来……他想知道，在N×M的矩形方格中摆最多个数的車

使其互不吃到的情况下方案数有几种。但是，由于上次摆炮摆得实在太累，他为了偷懒，打算增加一个条件：对于

任何一个車A，如果有其他一个車B在它的上面（車B行号小于車A），那么車A必须在車B的右边（車A列号大于車B）

。

棋子都是相同的。

Input

一行，两个正整数N和M。

N<=1000000，M<=1000000

Output

一行，输出方案数的末尾50位（不足则直接输出）。

Sample Input

2 2

Sample Output

HINT

Source

By FancyCoder

[Submit][Status][Discuss]

 #include<cstdio>

 #define N 1000005

 int n,m,t,pri[N],que[N],cnt[N],ans[],tot=,mor;

 void calc(int lim,int flg){

     for(int i=;i<=lim;++i)

         for(int num=i;num!=;)

             cnt[pri[num]]+=flg,num/=pri[num];

 }

 main(){

     scanf("%d%d",&n,&m);

     if(n<m)n^=m^=n^=m;

     for(int i=;i<=n;++i){

         if(!pri[i])que[++t]=pri[i]=i;

         for(int j=;j<=t&&i*que[j]<=n;++j){

             pri[que[j]*i]=que[j];

             if(!(i%que[j]))break;

         }

     }

     ans[]=;

     calc(n,+);

     calc(m,-);

     calc(n-m,-);

     for(int i=;i<=t;++i)

         for(int j=;j<=cnt[que[i]];++j){tot+=;

             for(int k=;k<=tot;++k)ans[k]*=que[i];

             for(int k=;k<=tot;++k)ans[k+]+=ans[k]/,ans[k]%=;

             while(tot&&!ans[tot])--tot;if(tot>)tot=;

         }

     while(tot&&!ans[tot])--tot;

     for(int i=tot;i;--i)putchar(''+ans[i]);

 }

4808: 马

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 106 Solved: 43
[Submit][Status][Discuss]

Description

众所周知，马后炮是中国象棋中很厉害的一招必杀技。"马走日字"。本来，如果在要去的方向有别的棋子挡住（俗

称"蹩马腿"），则不允许走过去。为了简化问题，我们不考虑这一点。马跟马显然不能在一起打起来，于是rly在

一天再次借来了许多许多的马在棋盘上摆了起来……但这次，他实在没兴趣算方案数了，所以他只想知道在N×M的

矩形方格中摆马使其互不吃到的情况下的最多个数。但是，有一个很不幸的消息，rly由于玩得太Happy，质量本来

就不好的棋盘被rly弄坏了，不过幸好只是破了其中的一些格子（即不能再放子了），问题还是可以继续解决的。

Input

一行，两个正整数N和M。

接下来N行，每行M个数，要么为0，表示没坏，要么为1，表示坏了。

N<=200,M<=200

Output

一行，输出最多的个数。

Sample Input

2 3
0 1 0
0 1 0

Sample Output

HINT

Source

By FancyCoder

[Submit][Status][Discuss]

 #include <cstdio>

 template <class T>

 inline T min(const T &a, const T &b)

 {

     return a < b ? a : b;

 }

 inline int nextInt(void)

 {

     int r = ;

     int f = ;

     int c = getchar();

     for (; c < ; c = getchar())

         if (c == '-')f = ;

     for (; c > ; c = getchar())

         r = r *  + c - ;

     return f ? -r : r;

 }

 const int mxn = ;

 const int mxm = ;

 const int inf = ;

 int s;

 int t;

 int tt;

 int hd[mxn];

 int nt[mxm];

 int to[mxm];

 int fl[mxm];

 inline void add(int x, int y)

 {

     nt[tt] = hd[x], to[tt] = y, fl[tt] = , hd[x] = tt++;

     nt[tt] = hd[y], to[tt] = x, fl[tt] = , hd[y] = tt++;

 }

 int dep[mxn];

 int que[mxn];

 int cur[mxn];

 inline bool bfs(void)

 {

     for (int i = s; i <= t; ++i)

         dep[i] = ;

     int l = , r = ;

     dep[s] = ;

     que[] = s;

     while (l != r)

     {

         int u = que[l++], v;

         for (int i = hd[u]; ~i; i = nt[i])

             if (v = to[i], !dep[v] && fl[i])

                 dep[que[r++] = v] = dep[u] + ;

     }

     return dep[t];

 }

 int dfs(int u, int f)

 {

     if (!f || u == t)

         return f;

     int used = , flow, v;

     for (int &i = cur[u]; ~i; i = nt[i])

         if (v = to[i], fl[i] && dep[v] == dep[u] + )

         {

             flow = dfs(v, min(f - used, fl[i]));

             used += flow;

             fl[i] -= flow;

             fl[i^] += flow;

             if (used == f)

                 return used;

         }

     if (!used)

         dep[u] = ;

     return used;

 }

 inline int flow(void)

 {

     int ret = , tmp;

     while (bfs())

     {

         for (int i = s; i <= t; ++i)

             cur[i] = hd[i];

         while (tmp = dfs(s, inf))

             ret += tmp;

     }

     return ret;

 }

 int n, m, id[][];

 const int mov[][] =

 {

     {+, +},

     {+, -},

     {-, +},

     {-, -},

     {+, +},

     {+, -},

     {-, +},

     {-, -}

 };

 signed main(void)

 {

     n = nextInt();

     m = nextInt();

     for (int i = ; i <= n; ++i)

         for (int j = ; j <= m; ++j)

             if (!nextInt())id[i][j] = ++t;

     ++t;

     for (int i = s; i <= t; ++i)

         hd[i] = -;

     for (int i = ; i <= n; ++i)

         for (int j = ; j <= m; ++j)

             if (id[i][j])

             {

                 if ((i ^ j) & )

                     add(s, id[i][j]);

                 else

                     add(id[i][j], t);

             }

     for (int i = ; i <= n; ++i)

         for (int j = ; j <= m; ++j)

             if (((i ^ j) & ) && id[i][j])

                 for (int k = ; k < ; ++k)

                 {

                     int x = i + mov[k][];

                     int y = j + mov[k][];

                     if (x <  || x > n)continue;

                     if (y <  || y > m)continue;

                     if (!id[x][y])continue;

                     add(id[i][j], id[x][y]);

                 }

     printf("%d\n", t -  - flow());

 }

4809: 皇后

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 123 Solved: 62
[Submit][Status][Discuss]

Description

众所不知，rly现在不会玩国际象棋。但是，作为一个OIer，rly当然做过八皇后问题。这里再啰嗦几句，皇后可以攻击到同行同列同对角线，在n*n的方格中摆n个皇后使其互不攻击到，求不同的解的数量，这就是经典的n皇后问题。现在问题推广到n皇后问题，这个问题对于你而言实在是小菜一叠。但因为上一次rly把棋盘弄破了，又拿不出新的，所以rly打算难一点点，问题就是破棋盘上的n皇后问题。他想知道……（你们懂的）。

棋子都是相同的。

Input

一行，一个正整数N。

接下来N行，每行N个数，要么为0，表示没坏，要么1，表示坏了。

N<=16

Output

一行，输出不同的解的数量。

Sample Input

4
1 0 1 1
1 1 1 0
0 1 1 1
1 1 0 1

Sample Output

HINT

Source

By FancyCoder

[Submit][Status][Discuss]

 #include <cstdio>

 inline int nextInt(void)

 {

     int r = ;

     int c = getchar();

     for (; c < ; c = getchar());

     for (; c > ; c = getchar())

         r = r *  + c - ;

     return r;

 }

 const int mxn = ;

 typedef unsigned long long lnt;

 int n, ans, map[mxn][mxn];

 void search(int x, lnt a, lnt b, lnt c)

 {

     if (x == n)++ans;

     else

     {

         lnt d = a | b | c;

         for (register int y = ; y < n; ++y)

             if (!map[x][y] && !((d >> y) & ))

                 search(x + ,

                     (a | (1ULL << y)),

                     (b | (1ULL << y)) >> ,

                     (c | (1ULL << y)) << );

     }

 }

 signed main(void)

 {

     n = nextInt();

     for (int i = ; i < n; ++i)

         for (int j = ; j < n; ++j)

             map[i][j] = nextInt();

     search(, , , );

     printf("%d\n", ans);

 }

@Author: YouSiki

码农公寓

4806: 炮

Description

Input

Output

Sample Input

Sample Output

HINT

Source

4807: 車

Description

Input

Output

Sample Input

Sample Output

HINT

Source

4808: 马

Description

Input

Output

Sample Input

Sample Output

HINT

Source

4809: 皇后

Description

Input

Output

Sample Input

Sample Output

HINT

Source

相关文章