对弈【牛客tracker 每日一题】-北京尧图网络

对弈时间限制1秒空间限制256M知识点枚举网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述善弈者谋势不善弈者谋子。 ——《弈林新编》蒟蒻H t B e s t HtBestHtBest与神犇W H Z WHZWHZ下棋五子棋H t B e s t HtBestHtBest执黑棋W H Z WHZWHZ执白棋。由于H t B e s t HtBestHtBest天资愚笨不会判断输赢所以需要你帮他开发一个判断五子棋输赢的程序。输入描述第一行有2 22个正整数n m nmnm分别表示棋盘大小 n nn和对弈步数。接下来m mm行每行两个正整数x i , y i x_i,y_ixi,yi表示对弈者下棋的坐标第2 、 4 、 6 … 2、4、6…2、4、6…行是HtBest下的棋子第3 、 5 、 7 … 3、5、7…3、5、7…行是W H Z WHZWHZ下的棋子。输出描述第一行一个字符串s ss和一个正整数n u m numnum用空格隔开分别表示对弈的胜负结果和该结果出现时的步数如果H t B e s t HtBestHtBest胜则s “ H t B e s t ” s“HtBest”s“HtBest”n u m numnum为H t B e s t HtBestHtBest胜利时的步数为偶数如果W H Z WHZWHZ胜则s “ W H Z ” s“WHZ”s“WHZ”n u m numnum为W H Z WHZWHZ胜利时的步数为奇数如果对弈m mm步后胜负仍未定则s “ U N K ” s“UNK”s“UNK”n u m m nummnumm。提示当棋盘上第一次有五个子连续排列横竖斜都可时胜负已定。在这之后两人有可能仍继续落子。示例1输入10 20 1 1 1 2 2 1 2 2 3 1 3 2 4 1 4 2 5 1 5 2 6 1 6 2 7 1 7 2 8 1 8 2 9 1 9 2 10 1 10 2输出HtBest 9说明在第9 99步时H t B e s t HtBestHtBest获胜当前局面示例2输入10 27 8 6 9 4 2 1 7 5 4 7 8 4 4 3 5 4 10 3 5 5 9 7 9 5 3 4 6 3 5 10 1 5 9 2 6 5 5 7 1 4 2 5 8 5 1 3 3 2 8 3 2 6输出WHZ 22说明在第2 22步时W H Z WHZWHZ获胜当前局面示例3输入10 1 1 1输出UNK 1说明下一手后胜负未分。备注对于100 % 100\%100%的测试数据1 ≤ n ≤ 1000 1 ≤ n ≤ 10001≤n≤10001 ≤ m ≤ 100000 1 ≤ m ≤ 1000001≤m≤100000解题思路本题是模拟落子定向胜负检测的经典五子棋判赢问题利用「仅新落子可能形成五连」的性质将每次胜负判定的复杂度从全盘扫描的O ( n 2 ) O(n^2)O(n2)优化为常数级完美适配十万步的大规模数据。1. 核心优化仅检查当前落子点五子棋中只有刚刚落下的棋子才可能促成新的五连此前的棋盘状态已经验证过无五连。因此每次落子后只需以该棋子为中心向四个方向延伸检查连续同色棋子数即可无需全盘扫描单次检查为O ( 1 ) O(1)O(1)常数开销。2. 四个检测方向五连共有四种形态横向、纵向、主对角线左上-右下、副对角线右上-左下。对应四个方向向量纵向行变化列不变(1, 0)横向列变化行不变(0, 1)主对角线行列同步增减(1, 1)副对角线行增列减(-1, 1)对每个方向以落子点为中心向两端各延伸最多4格统计连续同色棋子的最大长度若任意方向长度≥5则当前玩家获胜。3. 边界简化处理由于最多仅需向四周延伸4格因此给棋盘坐标整体加上偏移量代码中为3让所有合法落子点周围都留有足够的缓冲区域无需额外判断数组越界大幅简化代码逻辑。4. 整体流程初始化棋盘所有位置标记为空。按顺序模拟每一步落子奇数步第1、3、5…步为HtBest的黑棋偶数步为WHZ的白棋。每落一子立即执行胜负检测若形成五连直接输出胜者与当前步数终止程序。若所有m步走完仍未分出胜负输出UNK与总步数m。算法总时间复杂度为O ( m ) O(m)O(m)可轻松处理十万步的输入规模。总结核心逻辑利用五连必然包含最新落子的性质将胜负检测限定在当前点的四个方向上线性模拟每一步落子首次检测到五连立即输出结果。关键操作定向四方向连续计数、坐标偏移简化边界处理、落子即检查提前终止。效率保障每次检查为常数级操作总复杂度线性十万步数据可毫秒级完成。代码简要说明棋盘存储使用vectorstring存储棋盘大小设为n8初始值填充为-1代表空位通过坐标整体3的偏移避免边界越界判断。check检测函数遍历四个方向向量每个方向以落子点为中心从-4到4依次检查位置。统计连续同色棋子数若计数达到5则立即返回true表示获胜。落子主循环按步循环读取坐标通过i1判断当前玩家0对应HtBest1对应WHZ。写入棋子后调用check函数若获胜则按规则输出玩家名称与第i1步的步数直接返回结束程序。未分胜负处理所有步数走完仍未触发胜利输出UNK与总步数m。输入优化关闭流同步并解绑tie大幅提升十万级数据的读取速度。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n,m;vectorstringg;boolcheck(ll x,ll y,chart){for(constauto[dx,dy]:{make_pair(1,0),make_pair(0,1),make_pair(1,1),make_pair(-1,1)}){ll c0;for(ll i-4;i5;i){if(g[xi*dx][yi*dy]t){c;if(c5)returntrue;continue;}c0;}}returnfalse;}voidsolve(){cinnm;g.assign(n8,string(n8,(char)-1));for(ll i0;im;i){ll x,y;cinxy;charti1;x3;y3;g[x][y]t;if(check(x,y,t)){if(t)coutWHZ i1endl;elsecoutHtBest i1endl;return;}}coutUNK mendl;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);solve();return0;}

对弈【牛客tracker 每日一题】

相关推荐

SecLists 与 Weakpass：3 大场景下的高效密码字典选择策略

华为交换机 Access/Trunk 模式实战：3种典型组网场景配置与验证

XDreamer可视化编程：美术师零代码Unity游戏开发实战指南

更多资讯

3步做出面试加分简历：Magic Resume AI简历编辑器上手指南

Velero Schedule 跳过立即触发备份：skipImmediately 配置设计与源码解析

西电光电院复试备考全攻略：精准对标考纲与综合能力展示

Java Web投票系统实战：Servlet+JSP+JDBC完整部署与代码级调试

Java Swing课设实战：JTable数据绑定与CRUD实现

3步搞定3D打印振纹：Klipper 输入整形的完整调参指南

今日更新

基于MATLAB的CRI显色指数计算：从SPD光谱到Ra的完整流程

JSP+Servlet+MySQL博客系统源码部署与优化全攻略

蜂窝调度算法 MATLAB 实现：比例公平、轮询与最大 C/I 对比

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

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

分布式服务的决策记录

创业产品的首版范围

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