本文共 3858 字，大约阅读时间需要 12 分钟。

A. And Then There Were K

题目

Given an integer n, find the maximum value of integer k such that the following condition holds:

n & (n−1) & (n−2) & (n−3) & … (k) = 0

where & denotes the bitwise AND operation.

Input

The first line contains a single integer t (1≤t≤3⋅10⁴).

Then t test cases follow.

The first line of each test case contains a single integer n (1≤n≤10⁹).

Output

For each test case, output a single integer — the required integer k.

分析题意

给出一个数n，要求得出最大的k满足：

n & (n−1) & (n−2) & (n−3) & … (k) = 0 这题考察的是对位与操作&的理解。

将[m,n]所有数字按位与，就是保留[m,n]的最长公共前缀，然后把后面的位全部置0，就得到所有数字按位与的结果。而[m,n]的最长公共前缀就是m和n的公共前缀。

本题就相当于求n和k的公共前缀为0时的最大k值，那只要把n的二进制首位变成0后面的全变成1就得到了k。即找到n>=2^x=k+1，符合题意的最大k值。

上代码

#include
   
    using namespace std;int solve(int n,int k){
   	if(n>=k) return solve(n,k*2);	return k/2-1;}int main(){
   	int t;	cin>>t;	while(t--)	{
   		int n;		cin>>n;		cout<
    
     <
    
   

反思

注意边界条件。

B1. Palindrome Game (easy version)

题目

The only difference between the easy and hard versions is that the given string s in the easy version is initially a palindrome, this condition is not always true for the hard version.

A palindrome is a string that reads the same left to right and right to left. For example, “101101” is a palindrome, while “0101” is not.

Alice and Bob are playing a game on a string s (which is initially a palindrome in this version) of length n consisting of the characters ‘0’ and ‘1’. Both players take alternate turns with Alice going first.

In each turn, the player can perform one of the following operations:

· Choose any i (1≤i≤n), where s[i]= ‘0’ and change s[i] to ‘1’.

Pay 1 dollar.

· Reverse the whole string, pay 0 dollars. This operation is only allowed if the string is currently not a palindrome, and the last operation was not reverse. That is, if Alice reverses the string, then Bob can’t reverse in the next move, and vice versa.

Reversing a string means reordering its letters from the last to the first. For example, “01001” becomes “10010” after reversing.

The game ends when every character of string becomes ‘1’. The player who spends minimum dollars till this point wins the game and it is a draw if both spend equal dollars. If both players play optimally, output whether Alice wins, Bob wins, or if it is a draw.

Input

The first line contains a single integer t (1≤t≤10³). Then t test cases follow.

The first line of each test case contains a single integer n (1≤n≤10³).

The second line of each test case contains the string s of length n, consisting of the characters ‘0’ and ‘1’. It is guaranteed that the string s is a palindrome and contains at least one ‘0’.

Note that there is no limit on the sum of n over test cases.

Output

For each test case print a single word in a new line:

“ALICE”, if Alice will win the game,

“BOB”, if Bob will win the game, “DRAW”, if the game ends in a draw.

分析题意

如果回文串中的0是偶数个，那么当A第一步执行操作1以后（A只能这么做），B也执行操作1使串变回回文串，在这一过程中A和B的花费都一样。当回文串中的0个数为2时，A执行操作1，B执行操作2，A只能再执行操作1，游戏结束。此时B获胜。

如果回文串中0是奇数个，那么中间那个数一定是0。A的第一步执行操作1将中间的0变为1，如果游戏结束，B获胜。如果游戏继续，那么后续情况和上一段一样，无论如何获胜的都是A。

上代码

#include
   
    using namespace std;string solve(int n,string str){
   	int cnt=0;	for(int i=0;i
    
     >t;	while(t--)	{
   		int n;		string str;		cin>>n;		cin>>str;		cout<
     
      <
     
    
   

反思

一开始没考虑只有1个0的情况。

B2. Palindrome Game (hard version)

题目

The only difference between the easy and hard versions is that the given string s in the easy version is initially a palindrome, this condition is not always true for the hard version.

分析题意

如果是回文串，同B1；

如果不是回文串，A可以通过不断翻转保证B不赢，且平局只有一种情况： 一共只有2个0且n为奇数中间是0。

上代码

#include
   
    using namespace std;string solve(int n,string str){
   	int cnt=0;	int cnt1=0;	for(int i=0;i
    
     >t;	while(t--)	{
   		int n;		string str;		cin>>n;		cin>>str;		cout<
     
      <
     
    
   

反思

这种问题就是分类讨论。

一般来说都会存在先手或后手必赢的局面， 然后还要找出特殊情况。

转载地址：http://cyprz.baihongyu.com/