【题解】Gregor and the Pawn Game
题目描述
There is a chessboard of size n by n . The square in the i -th row from top and j -th column from the left is labelled (i,j) .
Currently, Gregor has some pawns in the n -th row. There are also enemy pawns in the 1 -st row. On one turn, Gregor moves one of his pawns. A pawn can move one square up (from (i,j) to (i-1,j) ) if there is no pawn in the destination square. Additionally, a pawn can move one square diagonally up (from (i,j) to either (i-1,j-1) or (i-1,j+1) if and only if there is an enemy pawn in that square. The enemy pawn is also removed.
Gregor wants to know what is the maximum number of his pawns that can reach row 1 ?
Note that only Gregor takes turns in this game, and the enemy pawns never move. Also, when Gregor's pawn reaches row 1 , it is stuck and cannot make any further moves.
输入格式
The first line of the input contains one integer t ( 1\le t\le 2\cdot 10^4 ) — the number of test cases. Then t test cases follow.
Each test case consists of three lines. The first line contains a single integer n ( 2\le n\le 2\cdot{10}^{5} ) — the size of the chessboard.
The second line consists of a string of binary digits of length n , where a 1 in the i -th position corresponds to an enemy pawn in the i -th cell from the left, and 0 corresponds to an empty cell.
The third line consists of a string of binary digits of length n , where a 1 in the i -th position corresponds to a Gregor's pawn in the i -th cell from the left, and 0 corresponds to an empty cell.
It is guaranteed that the sum of n across all test cases is less than 2\cdot{10}^{5} .
输出格式
For each test case, print one integer: the maximum number of Gregor's pawns which can reach the 1 -st row.
输入输出样例
输入 #1
4
3
000
111
4
1111
1111
3
010
010
5
11001
00000
输出 #1
3
4
0
0
分析
首先,显然对于 n\ge 3 的情况,第 2 行到第 n-1 行可以忽略,故我们只需要考虑一个 2\times n 的棋盘。
对于位于 (i,j) 的白棋(己方),我们有 3 种移动的方案:
- 当左上方即 (i-1,j-1) 有黑棋时,可以向左上方即 (i-1,j-1) 移动。
- 当正上方即 (i-1,j) 没有黑棋时,可以向正上方即 (i-1,j) 移动。
- 当右上方即 (i-1,j+1) 有黑棋时,可以向右上方即 (i-1,j+1) 移动。
观察三种方案可以发现,向左上方或正上方移动显然不会影响位于 (i,j+1) 至位于 (i,n) 的所有白棋的移动,而向右上方移动会影响位于 (i,j+1) 的白棋向左上方移动。至此我们得到了一个贪心方案:尽量向左上方或正上方移动。
多测记得清空数组,时间复杂度 O(n)。
代码
#include<bits/stdc++.h>
using namespace std;
int t;
int n;
int a[200001],b[200001];
signed main(){
scanf("%d",&t);
while(t--){
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%1d",&a[i]);
for(int i=1;i<=n;i++)scanf("%1d",&b[i]);
int ans=0;
for(int i=1;i<=n;i++){
if(!b[i])continue;
if(a[i]==0){
ans++;continue;
}
if(a[i-1]==1){
a[i-1]=2;
ans++;
continue;
}if(a[i+1]==1){
a[i+1]=2;
ans++;
continue;
}
}
printf("%d\n",ans);
}
}
最后修改:2021 年 08 月 17 日 01 : 06 PM
© 允许规范转载
相关文章
- 无法获取指向控制台的文件描述符 (couldn't get a file descriptor referring to the console)
- error: Your local changes to the following files would be overwritten by merge 解决方案
- ORA-01378: The logical block size (string) of file string is not compatible with the disk sector size (media sector size is string and host sector size is string) ORACLE 报错 故障修复 远程处理
- ORA-32014: error processing parameter “string” from the SPFILE restore image ORACLE 报错 故障修复 远程处理
- ORA-04000: the sum of PCTUSED and PCTFREE cannot exceed 100 ORACLE 报错 故障修复 远程处理
- ORA-08119: The new initrans will make the index too big ORACLE 报错 故障修复 远程处理
- ORA-13607: The specified task or object string already exists ORACLE 报错 故障修复 远程处理
- ORA-13629: The task or object string is being used by another operation. ORACLE 报错 故障修复 远程处理
- 关于The function equals must be used with a prefix when a de详解编程语言
- Linux Trunk: Unlocking the Power of Open Source Systems(linuxtrunk)
- What’s the difference between SHGetMalloc, SHAlloc, CoGetMalloc, and CoTaskMemAlloc详解编程语言
- CD and Explore the Amazing World of Linux(cd.linux)
- 「Linux 录屏软件下载」功能强大,操作简单!(Note: The translation of the title can be read as Linux Screen Recording Software Download: Powerful Functionality Simple Operation! (linux录屏软件下载)
- Exploring the Features of MySQL 5.7: A Comprehensive Guide from the Official Documentation(mysql5.7官方文档)
- Exploring the Mysterious MySQL Error 1370: Tips and Fixes(mysql1370)
- Exploring the Benefits and Advantages of Linux LDT for Modern Businesses(linuxldt)
- Exploring the Benefits and Challenges of Implementing a MySQL Multidatabase Architecture with Multiple Data Centers.(mysql多数据中心)
- Exploring the Benefits of Storing Data with MongoDB and XML(mongodbxml)
- Exploring the Latest Innovations and Updates in MySQL for the Year 2013(mysql2013)
- Exploring the Power and Flexibility of Linux UIO: A Comprehensive Guide.(linuxuio)
- Exploring the Versatile Applications of Linux Operating Systems(linux操作系统的应用)