问题求解

题目描述

给定一个正整数N，求最小的M满足比N大且M与N的二进制表示中有相同数目的1。

举个例子，假如给定N为78，二进制表示为1001110，包含4个1，那么最小的比N大的并且二进制表示中只包含4个1的数是83，其二进制是1010011，因此83就是答案。

输入格式

输入若干行，每行一个数N(1 ≤ N ≤ 1000000)，如果这行为0表示输入结束。

输出格式

对于每个N,输出对应的M。

样例

样例输入
1

2

3

4

78

0

样例输出
2

4

5

8

83

#include <bits/stdc++.h>
using namespace std;

void shizhuaner(int);
int nn;
int la;
int aa[100000010];

int main()
{
	
	int n;
	cin>>n;
	while(n!=0)
	{
		nn = 0;
		la = 0;
		shizhuaner(n);
		for(int i = la;i>=1;i--)
		{
			nn = nn*10+aa[i];
		}
		int cnt = 0;
		int nnn = nn;
		while(nnn!=0)
		{
			if(nnn%10==1) cnt++;
			nnn = nnn/10;
		}
		
		for(int i = n+1;true;i++)
		{
			la = 0;
			nn = 0;
			shizhuaner(i);
			for(int j = la;j>=1;j--)
			{
				nn = nn*10+aa[j];
			}
			nnn = nn;
			int cntt = 0;
			while(nnn!=0)
			{
				if(nnn%10==1) cntt++;
				nnn = nnn/10;
			}
			if(cnt==cntt)
			{
				cout<<i<<endl;
				break;
			}
		}
		cin>>n;
	}
	
	return 0;
}
void shizhuaner(int a)
{
	if(a==1)
	{
		aa[++la] = a;
		return;
	}
	int c = a%2;
	aa[++la] = c;
	a = a/2;
	shizhuaner(a);
	return;
	
}

泳池

题目描述

小C在一个排水系统不太好的学校上学。又是一个下雨天，学校里高低不平积了很多水。小C突发奇想：如果大雨一直下，多久以后我可以在学校里游泳呢？

学校是 N x N 的坐标方格 grid 中，每一个方格的值 grid(i,j)表示在位置 (i,j) 的高度。现在开始下雨了。当时间为 t 时，此时雨水导致方格中任意位置的水位为 t 。你可以从一个方格游向四周相邻的任意一个方格，但是前提是此时水位必须同时淹没这两个方格。假定小C的游动是不耗时的。

现在小C从坐标方格的左上(0,0)出发。最少耗时多久他才能到达坐标方格的右下平台 (N-1, N-1)？

输入格式

第一行有一个整数N，以下是一个N*N的方阵，代表各处的高度。 输入范围： 2 ≤ N ≤ 300 0 ≤ Height ≤ 10000000

输出格式

输出一个整数，代表最少等待时间T

样例

样例输入 1
2

0 2

1 3

样例输出 1
3

样例解释 1

时间为3时，才可以游向平台(1,1)，此时水位为3。

样例输入 2

5
0 1 2 3 4
24 23 22 21 5
12 13 14 15 16
11 17 18 19 20
10 9 8 7 6

样例输出 2
16

#include <iostream>
#include <iomanip>
using namespace std;
int n,m;
int a[310][310];
int cnt = 0;
int di[] = {0,1,0,-1};
int dj[] = {1,0,-1,0};
bool f = false;
void aaa(int,int);
int main()
{
	cin>>n;
	for(int i = 0;i<n;i++)
	{
		for(int j = 0;j<n;j++)
		{
			cin>>a[i][j];
		}
	}
	cnt = a[n-1][n-1];
	for(int i = 0;i<n;i++)
	{
		for(int j = 0;j<n;j++)
		{
			if(a[i][j]-a[n-1][n-1]>=0)
			{
				a[i][j] = a[i][j]-a[n-1][n-1];
			}
			else
			{
				a[i][j] = 0;
			}
		}
	}
	
	while(true)
	{
		
		aaa(0,0);
		if(f==true)
		{
			break;
		}
		cnt++;
		for(int i = 0;i<n;i++)
		{
			for(int j = 0;j<n;j++)
			{
				if(a[i][j]>0)
				{
					a[i][j]--;
				}
			}
		}
	}
	cout<<cnt;
	
	return 0;
}
void aaa(int i,int j)
{
	if(i==n-1&&j==n-1)
	{
		f = true;
		return;
	}
	for(int qqq = 0;qqq<4;qqq++)
	{
		int ti = i+di[qqq];
		int tj = j+dj[qqq];
		if(ti>=0&&ti<n&&tj>=0&&tj<n&&a[ti][tj]==0)
		{
			a[ti][tj] = -1;
			aaa(ti,tj);
			a[ti][tj] = 0;
		}
	}
	return;
}