P10172 「OICon-02」Pick Stone题目描述小 S 有一个n×mn\times mn×m的棋盘。初始每个位置都有一个棋子。每次小 S 可以取走一个周围四连通被取走棋子数不超过111的棋子。求小 S 最多能取走多少棋子并构造一种合法的取棋子方案。输入格式一行两个正整数n,mn,mn,m表示棋盘大小。输出格式第一行一个正整数表示最多能取走的棋子数ansansans。接下来nnn行每行mmm个−1∼ans-1\sim ans−1∼ans之间的整数。每个位置的数表示这个位置的棋子是第几个取走的。如果该位置的棋子没被取走请输出−1-1−1。输入输出样例 #1输入 #12 2输出 #13 1 2 3 -1输入输出样例 #2输入 #23 5输出 #212 2 3 4 5 6 1 -1 12 -1 7 8 9 -1 11 10说明/提示样例解释对于样例111取出(1,1)(1,1)(1,1)时周围有000个已取出位置取出(1,2),(2,1)(1,2),(2,1)(1,2),(2,1)时周围有111个已取出位置故原构造符合要求。容易证明没有更优答案。数据范围本题采用捆绑测试。Subtask\text{Subtask}Subtask特殊性质Score\text{Score}Score111n1n1n1202020222n2n2n2303030333n3n3n3505050对于100%100\%100%的数据1≤n≤3\bm{1\leq n\leq3}1≤n≤31≤m≤1051\leq m\leq10^51≤m≤105。如果你答对了第一问最多能取走的棋子数而没有正确地构造你将获得70%70\%70%的分值。一个子任务你的得分是所有测试点得分的最小值。注意你仍需要按格式输出n×mn\times mn×m个数表示构造方案我们推荐你全部输出−1-1−1。保证checker.cpp在符合格式要求的输出下用时不超过0.50.50.5秒。C实现#includebits/stdc.husingnamespacestd;intn,m;inta[100005];//第三行中对应石子是第几个取的不取为0intmain(){cinnm;if(n1){coutmendl;for(inti1;im;i)couti ;//顺序取走}if(n2){coutm(m1)/2endl;for(inti1;im;i)couti ;coutendl;intcntm1;for(inti1;im;i)cout(i1?cnt:-1) ;//隔一个取一个}if(n3){intcnt0;//第三行中取到了多少个棋子for(inti1;im1;i){//构造枚举中间石子枚举到m1是为了确保中间取不到而左边取得到的情况不被漏掉if((i1)(i/2)%20){//第三行每组中间的石子必定与第二行中第奇数个取到的石子对齐if(i1im)a[i]cnt;//中间if(i1)a[i-1]cnt;//左边if(im)a[i1]cnt;//右边}}cout2*m(m3)/4endl;for(inti1;im;i)couti ;coutendl;for(inti1;im;i)cout(i1?m(i1)/2:-1) ;coutendl;for(inti1;im;i){if(a[i])coutm(m1)/2a[i] ;//前面取了m(m1)/2个elsecout-1 ;}}}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
