bjfuoj小A回文数和拆除土墙

69 阅读 0 评论 46 点赞

我是靠谱客的博主自觉烤鸡，最近开发中收集的这篇文章主要介绍bjfuoj小A回文数和拆除土墙，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

描述
最近小A在研究一个数学问题。
如果一个数n，它的二进制数和十进制数是回文数（例如1001，66，64446都是回文数），那么小A就把它命名为小A回文数。但是小A想知道，如果给定两个数n和m，它们之间有哪些数是小A回文数呢？（1<=n<=m<=10^6）

输入
输入包含多组，每组测试数据包含两个整数n,m，其中1<=n<=m<=1000000

输出
对于每一组测试数据，输出的结果之间用换行隔开。

样例输入1

1 5

样例输出1

1
3
5

样例输入2

5 10

样例输出2

5
7
9

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
bool ispal(int num, int jinzhi)
{
int t = num;
int pal = 0;
while (num)
{
pal = pal * jinzhi;//乘进制
pal = pal + (num % jinzhi);///倒序n进制下的数字
num = num / jinzhi;//但计算采用十进制
}
return t == pal;//即正序和倒序下的n进制数相等
}
bool judge(int n)
{
if (ispal(n, 2) && ispal(n, 10))return true;
return false;
}
int main()
{
int n, m;
while (cin >> n >> m) {
for (int i = n; i <= m; i++)
{
if (judge(i))cout << i << endl;
}
}
return 0;
}

描述
小A家的大门外有一堵土墙，这堵土墙是由n个高度可能不相同的长方体从左至右砌成的。例如，当n为7，h=[1,2,6,1,1,7,1]时，这堵墙的图形如下：

某日，小A从外面买了一台宽度为k的电视，他想要将这个电视搬进家里，所以，他必须要从这堵土墙中拆除k个连续的长方体，以至于能将宽度为k的电视搬进家里。但是，小A又想这k个连续的长方体高度之和最小，以至于拆除的土墙最不费力。
小A想问问你，从哪块长方体开始拆，以至于这连续的k块长方体高度之和最小。

输入
有多组输入数据，每组第一行包含两个正整数n，k（1<=n<=1.5*10^5，1<=k<=n），n代表这堵土墙由n个高度可能不相同的长方体组成的，k代表电视机的宽度。第二行有n个整数，h1,h2,..,hn(1<=hi<=100)，代表从左至右这n个长方体的高度。

输出
输出一个整数j，表示从j块长方体开始拆，j,j+1,...,j+k-1这k块长方体的高度和最小。如果j有多个位置，输出最左边的位置。

样例输入1

7 3
1 2 6 1 1 7 1

样例输出1

#include <string>
#include <vector>
#include <iostream>
using namespace std;
int main()
{
int a, b, t;
vector <int>c;
while (cin >> a >> b)
{
c.resize(0);//将上次的数据清除（易错）
c.push_back(0);
for (int i = 1; i <= a; i++)
{
cin >> t;
c.push_back(c[i-1]+t);//c数组存下前缀和，在后续降低时间复杂度很有用
}
int minn = 1e9, pos = 0;//pos存位置，minn存最小的高度和,初值为1e9
for (int i = b; i <= a; i++)
if (c[i] - c[i - b]<minn)
{
minn = c[i] - c[i - b];
pos = i - b + 1;
}
cout << pos <<endl;
}
return 0;
}