首页 > 代码库 > BZOJ 4806 - 4809 象棋四题
BZOJ 4806 - 4809 象棋四题
4806: 炮
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 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
7
HINT
Source
By FancyCoder
1 #include<cstdio> 2 #define N 105 3 #define P 999983 4 int n,m;long long f[N][N][N],ans; 5 inline long long C(int a,int b){ 6 return b==1?a:(1LL*a*(a-1)/2)%P; 7 } 8 main(){ 9 scanf("%d%d",&n,&m),f[0][m][0]=1;10 for(int i=0;i<n;++i)11 for(int j=0;j<=m;++j)12 for(int k=0;k<=m;++k)13 if(f[i][j][k]){14 (f[i+1][j][k]+=f[i][j][k])%=P;15 if(j>0)(f[i+1][j-1][k+1]+=f[i][j][k]*C(j,1))%=P;16 if(j>1)(f[i+1][j-2][k+2]+=f[i][j][k]*C(j,2))%=P;17 if(j>0)(f[i+1][j-1][k]+=f[i][j][k]*C(j,1)%P*C(k,1))%=P;18 if(k>0)(f[i+1][j][k-1]+=f[i][j][k]*C(k,1))%=P;19 if(k>1)(f[i+1][j][k-2]+=f[i][j][k]*C(k,2))%=P;20 }21 for(int i=0;i<=m;++i)22 for(int j=0;j<=m;++j)23 ans=(ans+f[n][i][j])%P;24 printf("%lld\n",ans);25 }
4807: 車
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 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
1
HINT
Source
By FancyCoder
1 #include<cstdio> 2 #define N 1000005 3 int n,m,t,pri[N],que[N],cnt[N],ans[64],tot=1,mor; 4 void calc(int lim,int flg){ 5 for(int i=2;i<=lim;++i) 6 for(int num=i;num!=1;) 7 cnt[pri[num]]+=flg,num/=pri[num]; 8 } 9 main(){10 scanf("%d%d",&n,&m);11 if(n<m)n^=m^=n^=m;12 for(int i=2;i<=n;++i){13 if(!pri[i])que[++t]=pri[i]=i;14 for(int j=1;j<=t&&i*que[j]<=n;++j){15 pri[que[j]*i]=que[j];16 if(!(i%que[j]))break;17 }18 }19 ans[1]=1;20 calc(n,+1);21 calc(m,-1);22 calc(n-m,-1);23 for(int i=1;i<=t;++i)24 for(int j=1;j<=cnt[que[i]];++j){tot+=7;25 for(int k=1;k<=tot;++k)ans[k]*=que[i];26 for(int k=1;k<=tot;++k)ans[k+1]+=ans[k]/10,ans[k]%=10;27 while(tot&&!ans[tot])--tot;if(tot>50)tot=50;28 }29 while(tot&&!ans[tot])--tot;30 for(int i=tot;i;--i)putchar(‘0‘+ans[i]);31 }
4808: 马
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 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
0 1 0
0 1 0
Sample Output
2
HINT
Source
By FancyCoder
1 #include <cstdio> 2 3 template <class T> 4 inline T min(const T &a, const T &b) 5 { 6 return a < b ? a : b; 7 } 8 9 inline int nextInt(void) 10 { 11 int r = 0; 12 int f = 0; 13 int c = getchar(); 14 15 for (; c < 48; c = getchar()) 16 if (c == ‘-‘)f = 1; 17 18 for (; c > 47; c = getchar()) 19 r = r * 10 + c - 48; 20 21 return f ? -r : r; 22 } 23 24 const int mxn = 40005; 25 const int mxm = 2000005; 26 const int inf = 1000000007; 27 28 int s; 29 int t; 30 int tt; 31 int hd[mxn]; 32 int nt[mxm]; 33 int to[mxm]; 34 int fl[mxm]; 35 36 inline void add(int x, int y) 37 { 38 nt[tt] = hd[x], to[tt] = y, fl[tt] = 1, hd[x] = tt++; 39 nt[tt] = hd[y], to[tt] = x, fl[tt] = 0, hd[y] = tt++; 40 } 41 42 int dep[mxn]; 43 int que[mxn]; 44 int cur[mxn]; 45 46 inline bool bfs(void) 47 { 48 for (int i = s; i <= t; ++i) 49 dep[i] = 0; 50 51 int l = 0, r = 1; 52 dep[s] = 1; 53 que[0] = s; 54 55 while (l != r) 56 { 57 int u = que[l++], v; 58 59 for (int i = hd[u]; ~i; i = nt[i]) 60 if (v = to[i], !dep[v] && fl[i]) 61 dep[que[r++] = v] = dep[u] + 1; 62 } 63 64 return dep[t]; 65 } 66 67 int dfs(int u, int f) 68 { 69 if (!f || u == t) 70 return f; 71 72 int used = 0, flow, v; 73 74 for (int &i = cur[u]; ~i; i = nt[i]) 75 if (v = to[i], fl[i] && dep[v] == dep[u] + 1) 76 { 77 flow = dfs(v, min(f - used, fl[i])); 78 79 used += flow; 80 fl[i] -= flow; 81 fl[i^1] += flow; 82 83 if (used == f) 84 return used; 85 } 86 87 if (!used) 88 dep[u] = 0; 89 90 return used; 91 } 92 93 inline int flow(void) 94 { 95 int ret = 0, tmp; 96 97 while (bfs()) 98 { 99 for (int i = s; i <= t; ++i)100 cur[i] = hd[i];101 102 while (tmp = dfs(s, inf))103 ret += tmp;104 }105 106 return ret;107 }108 109 int n, m, id[205][205];110 111 const int mov[8][2] =112 {113 {+2, +1},114 {+2, -1},115 {-2, +1},116 {-2, -1},117 {+1, +2},118 {+1, -2},119 {-1, +2},120 {-1, -2}121 };122 123 signed main(void)124 {125 n = nextInt();126 m = nextInt();127 128 for (int i = 1; i <= n; ++i)129 for (int j = 1; j <= m; ++j)130 if (!nextInt())id[i][j] = ++t;131 132 ++t;133 134 for (int i = s; i <= t; ++i)135 hd[i] = -1;136 137 for (int i = 1; i <= n; ++i)138 for (int j = 1; j <= m; ++j)139 if (id[i][j])140 {141 if ((i ^ j) & 1)142 add(s, id[i][j]);143 else144 add(id[i][j], t);145 }146 147 for (int i = 1; i <= n; ++i)148 for (int j = 1; j <= m; ++j)149 if (((i ^ j) & 1) && id[i][j])150 for (int k = 0; k < 8; ++k)151 {152 int x = i + mov[k][0];153 int y = j + mov[k][1];154 155 if (x < 1 || x > n)continue;156 if (y < 1 || y > m)continue;157 158 if (!id[x][y])continue;159 160 add(id[i][j], id[x][y]);161 }162 163 printf("%d\n", t - 1 - flow());164 }
4809: 皇后
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 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
1 0 1 1
1 1 1 0
0 1 1 1
1 1 0 1
Sample Output
1
HINT
Source
By FancyCoder
1 #include <cstdio> 2 3 inline int nextInt(void) 4 { 5 int r = 0; 6 int c = getchar(); 7 8 for (; c < 48; c = getchar()); 9 for (; c > 47; c = getchar())10 r = r * 10 + c - 48;11 12 return r;13 }14 15 const int mxn = 20;16 17 typedef unsigned long long lnt;18 19 int n, ans, map[mxn][mxn];20 21 void search(int x, lnt a, lnt b, lnt c)22 {23 if (x == n)++ans;24 else25 {26 lnt d = a | b | c;27 28 for (register int y = 0; y < n; ++y)29 if (!map[x][y] && !((d >> y) & 1))30 search(x + 1,31 (a | (1ULL << y)),32 (b | (1ULL << y)) >> 1,33 (c | (1ULL << y)) << 1);34 }35 }36 37 signed main(void)38 {39 n = nextInt();40 41 for (int i = 0; i < n; ++i)42 for (int j = 0; j < n; ++j)43 map[i][j] = nextInt();44 45 search(0, 0, 0, 0);46 47 printf("%d\n", ans);48 }
@Author: YouSiki
BZOJ 4806 - 4809 象棋四题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。