题目7:错误票据
某涉密单位下发了某种票据，并要在年终全部收回。
每张票据有唯一的ID号。全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。
因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。
你的任务是通过编程，找出断号的ID和重号的ID。
假设断号不可能发生在最大和最小号。
要求程序首先输入一个整数N(N<100)表示后面数据行数。
接着读入N行数据。
每行数据长度不等，是用空格分开的若干个（不大于100个）正整数（不大于100000）
每个整数代表一个ID号。
要求程序输出1行，含两个整数m n，用空格分隔。
其中，m表示断号ID，n表示重号ID
例如：
用户输入：
2
5 6 8 11 9
10 12 9
则程序输出：
7 9
/*
istringstream-用于执行C++风格的串流的输入操作
ostringstream-用于执行C风格的串流的输出操作
*/
#include <bits/stdc++.h>
using namespace std;
//输入N行数据，每行的数据数和数据总数是不确定的，要找出断号数据和重号数据。
//先输出断号数据，再输出重号数据
//关键在于字符串的处理和转化
void s2i(string &str,int &num)
{
stringstream ss;//stringstream可以支持C风格的输入输出操作
ss<<str;//流插入运算符 <<
ss>>num;//流提取运算符 >>
}
int line;
const int MaxN=10000;//最大的数据总数为100*100
int data[MaxN];
int main(){
scanf("%d",&line);
getchar();//把换行符吃掉
int index=0;//读出的数据数，最终的到的是数据总数
for(int i=0;i<line;i++)
{
string s;
getline(cin,s);//字符串s为输入的一行数据
istringstream iss(s);//把s封装到istringstream
string tmp;
while(getline(iss,tmp,' ')){//将iss中的数据按照空格进行切分，切分后的每一个数据都放在tmp中
s2i(tmp,data[index++]);//先取内容，再+1
}
}
//数据输入是乱序的，要进行排序
sort(data,data+index);//index表示数据长度
int a,b;
for(int i=1;i<index;i++ )
{
if(data[i]==data[i-1]+2)
a=data[i]-1;//断号
if(data[i]==data[i-1])
b=data[i];//重号
}
printf("%d %d",a,b);
return 0;
}
题目8：翻硬币
小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。
比如，可能情形是：**oo***oooo
如果同时翻转左边的两个硬币，则变为：oooo***oooo
现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？
我们约定：把翻动相邻的两个硬币叫做一步操作，那么要求：
程序输入：
两行等长的字符串，分别表示初始状态和要达到的目标状态。每行的长度<1000
程序输出：
一个整数，表示最小操作步数
例如：
用户输入：
**********
o****o****
程序应该输出：
5
再例如：
用户输入：
*o**o***o***
*o***o**o***
程序应该输出：
1
//最简单的方法是找规律--分成段，每一段有两个不同，每一段最后一个不同所在的位置-第一个不同所在的位置的总和
//题目没有说明，就不要考虑无解的情况--有奇数个不同
#include <bits/stdc++.h>
using namespace std;
int main()
{
string src;
string target;
getline(cin,src);
getline(cin,target);
int n=src.length();
int ans=0;
int start=-1;
for(int i=0;i<n;i++)
{
if(src[i]!=target[i])
{
if(start==-1)//还没标记第一个位置
{
start=i;
}else{//第一个位置已经标记，现在已经找到了第二个不同的位置
ans=(i-start);
start=-1;//便于接下来找第二段不同
}
}
}
cout<<ans<<endl;
return 0;
}
题目9：带分数
100 可以表示为带分数的形式：100 = 3 + 69258 / 714
还可以表示为：100 = 82 + 3546 / 197
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法。
题目要求：
从标准输入读入一个正整数N (N<1000*1000)
程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！
例如：
用户输入：
100
程序输出：
11
再例如：
用户输入：
105
程序输出：
6
资源约定：
峰值内存消耗 < 64M
CPU消耗 < 3000ms
#include<bits/stdc++.h>
using namespace std;
//生成1-9的全排列，先尝试在可能的位置插入+，再尝试在可能的位置插入/，验算等式，计数
//注意后边的两个串是可以整除的，涉及到整数的除法问题的思考
int parse(const char *arr,int pos,int len){
int ans=0;
int t=1;//基数从1开始
for(int i=pos+len-1;i>=pos;i--)
{
ans+=(arr[i]-'0')*t;//单个字符转换为数字：-‘0’
t*=10;
}
return ans;
}
int main()
{
int ans=0;
int n;
scanf("%d",&n);
string s="123456789";
do{
const char *str=s.c_str();
for(int i=1;i<=7;i++)//i代表加号前的串的长度
{
/*string a=s.substr(0,i);//substr不能够反复使用，耗时比较厉害，会造成运行超时
int inta=atoi(a.c_str());//字符串转整数
*/
int inta=parse(str,0,i);
if(inta>=n) break;
for(int j=1;j<=9-i-1;j++)//代表加号和除号之间的串的长度
{
/*string b=s.substr(i,j);
string c=s.substr(i+j);//除号后面的串
int intb=atoi(b.c_str());//atoi()函数将数字格式的字符串转换为整数类型。例如，将字符串“12345”转换成数字12345。
int intc=atoi(c.c_str());//int atoi(const char* str)
*/
int intb=parse(str,i,j);
int intc=parse(str,i+j,9-i-j);
if(intb % intc==0&&(inta+intb/intc)==n){
ans++;
}
}
}
}while(next_permutation(s.begin(),s.end()));
cout<<ans<<endl;
return 0;
}
题目10：连号区间数
小明这些天一直在思考这样一个奇怪而有趣的问题：
在1~N的某个全排列中有多少个连号区间呢？这里所说的连号区间的定义是：
如果区间[L, R] 里的所有元素（即此排列的第L个到第R个元素）递增排序后能得到一个长度为R-L+1的“连续”数列，则称这个区间连号区间。
当N很小的时候，小明可以很快地算出答案，但是当N变大的时候，问题就不是那么简单了，现在小明需要你的帮助。
输入格式：
第一行是一个正整数N (1 <= N <= 50000), 表示全排列的规模。
第二行是N个不同的数字Pi(1 <= Pi <= N)， 表示这N个数字的某一全排列。
输出格式：
输出一个整数，表示不同连号区间的数目。
示例：
用户输入：
4
3 2 4 1
程序应输出：
7
用户输入：
5
3 4 2 5 1
程序应输出：
9
解释：
第一个用例中，有7个连号区间分别是：[1,1], [1,2], [1,3], [1,4], [2,2], [3,3], [4,4]
第二个用例中，有9个连号区间分别是：[1,1], [1,2], [1,3], [1,4], [1,5], [2,2], [3,3], [4,4], [5,5]
资源约定：
峰值内存消耗 < 64M
CPU消耗 < 5000ms
//连号区间内有序且连续例：连号区间123,-最大值-最小值等于R-L；非连号区间：124，-最大值-最小值不等于R-L
#include<bits/stdc++.h>
using namespace std;
int n;
int arr[50000];
int ans=0;
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
for(int j=0;j<n;j++)
{
int max=arr[j];
int min=arr[j];
for(int i=j;i<n;i++)
{
if(arr[i]>max) max=arr[i];
if(arr[i]<min) min=arr[i];
if(i==j) ans++;
else{
if(max-min==i-j) ans++;//形成连号区间
}
}
}
cout<<ans<<endl;
return 0;
}
网友评论