UVa 696 How Many Knights-北京尧图网络

题目描述在国际象棋中骑士马的攻击方式为水平移动222格、垂直移动111格或水平移动111格、垂直移动222格。给定一个M×NM \times NM×N的棋盘M,N≤500M, N \le 500M,N≤500求最多能放置多少个骑士使得任意两个骑士互不攻击。输入格式多组数据每行两个整数MMM和NNN以0 0结束。输出格式对于每组数据输出一行格式为X knights may be placed on a M row N column board.其中XXX为最大骑士数。样例输入2 3 5 5 4 7 0 0输出4 knights may be placed on a 2 row 3 column board. 13 knights may be placed on a 5 row 5 column board. 14 knights may be placed on a 4 row 7 column board.题目分析本题是经典的“棋盘上放置骑士”问题。骑士的攻击关系构成一个二分图骑士只攻击异色格因此最大独立集总格数 - 最大匹配数。但由于棋盘可达500×500500 \times 500500×500二分图匹配不可行。但本题有更简单的数学规律若MNM NMN交换MMM和NNN使M≤NM \le NM≤N。若M1M 1M1可以放满所有格子即NNN。若M2M 2M2每444列可放444个两行各222个剩余列按规律放置。若M≥3M \ge 3M≥3可以放置⌈M×N2⌉\lceil \frac{M \times N}{2} \rceil⌈2M×N⌉个即所有格子的一半上取整因为可以按棋盘染色所有同色格互不攻击骑士攻击异色格。但注意当M3M 3M3且NNN较小时规律略有不同但上述公式仍适用。解题思路若MNM NMN交换MMM和NNN。若M1M 1M1答案N NN。若M2M 2M2答案4×⌊N/4⌋2×min⁡(N mod 4,2) 4 \times \lfloor N/4 \rfloor 2 \times \min(N \bmod 4, 2)4×⌊N/4⌋2×min(Nmod4,2)。否则答案⌈M×N2⌉ \lceil \frac{M \times N}{2} \rceil⌈2M×N⌉。复杂度分析O(1)O(1)O(1)时间。代码实现// How Many Knights// UVa ID: 696// Verdict: Accepted// Submission Date: 2016-08-25// UVa Run Time: 0.010s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intm,n;while(cinmn){if(m0n0)break;intmaxCounter0;if(m0||n0)maxCounter0;elseif(m1||n1)maxCountermax(m,n);elseif(m2||n2){intnext_mmax(m,n);maxCounternext_m/4*4;next_mnext_m%4;if(next_m2)next_m2;maxCounternext_m*2;}elseif(m3||n3){intnext_mmax(m,n);maxCounternext_m/2*3;if(next_m%21)maxCounter2;}else{introw_counter0,column_counter0;if(m%21){row_countern/2*m;if(n%21)row_counter(m1)/2;}elserow_countern*((m1)/2);if(n%21){column_counterm/2*n;if(m%21)column_counter(n1)/2;}elsecolumn_counterm*((n1)/2);maxCountermax(row_counter,column_counter);}coutmaxCounter knights may be placed on a m row n column board.\n;}return0;}总结本题通过分类讨论得出骑士最大放置数的公式。关键点包括对于M1M1M1或M2M2M2的特殊处理。对于M≥3M \ge 3M≥3利用棋盘染色性质最多放置一半格子上取整。注意MMM和NNN可以互换。该解法是棋盘放置问题的经典结论适合作为数学规律题练习。

UVa 696 How Many Knights

相关推荐

PCB设计制造与工程实践全解析

UE5自定义进度条：材质艺术与数学原理深度解析

EDA元件Designator与Comment属性详解与应用技巧

更多资讯

SWIOTLB：Linux内核DMA安全缓冲区原理与机密计算实践

CSS Grid vs Flexbox 对比指南：如何为你的布局选择正确的排版方案

Bug来了，设备在几百里外，你买机票了吗？

GMM说话人识别原理与MATLAB实现：从MFCC特征到EM训练

掌握 Agentic RAG：让 AI 自主检索，提升大模型回答精准度

SpringBoot网络爬虫图书推荐系统设计与实现

今日更新

Linux 内核 ARM 虚拟内存布局全解析：从 4GB 地址空间划分到源码级验证

AIGC降重工具测评与教育应用指南

数据容灾核心指标与实战方案解析

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？