题解《子数整数》、《欢乐地跳》、《开灯》

子数整数

题目描述

对于一个五位数$a_1{a}_2{a}_3{a}_4{a}_5$，可将其拆分为三个子数：

$su{b}_1=a_1{a}_2{a}_3$

$su{b}_2=a_2{a}_3{a}_4$

$su{b}_3=a_3{a}_4{a}_5$

例如，五位数$20207$可以拆分成

$su{b}_1=202$

$su{b}_2=020(=20)$

$su{b}_3=207$

现在给定一个正整数$K$，要求你编程求出$10000$到$30000$之间所有满足下述条件的五位数，条件是这些五位数的三个子数$su{b}_1,su{b}_2,su{b}_3$都可被$K$整除。

输入格式

一个正整数K

输出格式

每一行为一个满足条件的五位数，要求从小到大输出。不得重复输出或遗漏。如果无解，则输出“No”。

样例 #1

样例输入 #1

15

样例输出 #1

22555
25555
28555
30000

提示

$0<K<1000$

题解

// Author:PanDaoxi
#include <iostream>
using namespace std;
bool f(char s[],int k){
    
	// 写个函数判断一下切开后是否能被整除
	int sub[4]={
    };
	sub[0]=(s[0]-'0')*100+(s[1]-'0')*10+(s[2]-'0'),
	sub[1]=(s[1]-'0')*100+(s[2]-'0')*10+(s[3]-'0'),
	sub[2]=(s[2]-'0')*100+(s[3]-'0')*10+(s[4]-'0');
	// cout<<sub[0]<<" "<<sub[1]<<" "<<sub[2]<<endl;
	// 返回结果
	return (sub[0]%k==0&&sub[1]%k==0&&sub[2]%k==0)?true:false;
}
int main(){
    
	int k,a[30001],n=0;
	cin>>k;
	for(int i=10000;i<=30000;i++){
    
		// 当初写得不对，但是懒得改了，直接转字符串套函数
		char s[7]={
    };
		s[0]=i/10000+'0',
		s[1]=(i%10000)/1000+'0';
		s[2]=(i%1000)/100+'0';
		s[3]=(i%100)/10+'0';
		s[4]=i%10+'0';
  		if(f(s,k)) a[n++]=i; // 储存到数组里面
	}
	if(n==0){
     // 无解
		cout<<"No";
		return 0;
	}
	for(int i=0;i<n;i++){
    
		cout<<a[i]<<endl;
	}
	return 0;
}

欢乐的跳

题目描述

一个$n$个元素的整数数组，如果数组两个连续元素之间差的绝对值包括了$[1,n-1]$之间的所有整数，则称之符合“欢乐的跳”，如数组$1423$符合“欢乐的跳”，因为差的绝对值分别为：$3,2,1$。

给定一个数组，你的任务是判断该数组是否符合“欢乐的跳”。

输入格式

每组测试数据第一行以一个整数$n(1\le n\le 1000)$开始，接下来$n$个空格隔开的在[$-10^8$,$10^8$]之间的整数。

输出格式

对于每组测试数据，输出一行若该数组符合“欢乐的跳”则输出"Jolly"，否则输出"Not jolly"。

样例 #1

样例输入 #1

4 1 4 2 3

样例输出 #1

Jolly

样例 #2

样例输入 #2

5 1 4 2 -1 6

样例输出 #2

Not jolly

提示

$1\le n\le 1000$

题解

// Author:PanDaoxi
#include <iostream>
#include <cmath>
using namespace std;
int main(){
    
	int n,a[1001];
	bool flag=false;
	cin>>n;
	// 读入数据
	for(int i=0;i<n;i++){
    
		cin>>a[i];
	}
	for(int i=0;i<n-1;i++){
    
	    // 依据题意，写出式子
		int t=abs(a[i]-a[i+1]);
		if(1<=t&&t<=n) flag=true;
		else flag=false; // 不符合
	}
	
	if(flag==true) cout<<"Jolly";
    else cout<<"not Jolly";
	return 0;
}

开灯

题目描述

在一条无限长的路上，有一排无限长的路灯，编号为$1,2,3,4,\dots$。

每一盏灯只有两种可能的状态，开或者关。如果按一下某一盏灯的开关，那么这盏灯的状态将发生改变。如果原来是开，将变成关。如果原来是关，将变成开。

在刚开始的时候，所有的灯都是关的。小明每次可以进行如下的操作：

指定两个数，$a,t$（$a$为实数，$t$为正整数）。将编号为$[a],[2\times a],[3\times a],\dots ,[t\times a]$的灯的开关各按一次。其中$[k]$表示实数$k$的整数部分。

在小明进行了$n$次操作后，小明突然发现，这个时候只有一盏灯是开的，小明很想知道这盏灯的编号，可是这盏灯离小明太远了，小明看不清编号是多少。

幸好，小明还记得之前的$n$次操作。于是小明找到了你，你能帮他计算出这盏开着的灯的编号吗？

输入格式

第一行一个正整数$n$，表示$n$次操作。

接下来有$n$行，每行两个数，$a_i,t_i$。其中$a_i$是实数，小数点后一定有$6$位，$t_i$是正整数。

输出格式

仅一个正整数，那盏开着的灯的编号。

样例 #1

样例输入 #1

3
1.618034 13
2.618034 7
1.000000 21

样例输出 #1

20

提示

记$T=t_1+t_2+t_3+\dots +t_n$。

对于$30\%$的数据，满足$T\le 1000$

对于$80\%$的数据，满足$T\le 200000$

对于$100\%$的数据，满足$T\le 2000000$

对于$100\%$的数据，满足$n\le 5000,1\le a_i<1000,1\le t_i\le T$

数据保证，在经过$n$次操作后，有且只有一盏灯是开的，不必判错。而且对于所有的 $i$ 来说，$t_i\times a_i$ 的最大值不超过 2000000。

题解

// Author:PanDaoxi
#include <iostream>
using namespace std;
int main(){
    
	int n;
	// 写个布尔数组储存数据，而且空间用得少
	bool flag[20000001]={
    };
	cin>>n;
	for(int i=1;i<=n;i++){
    
		// 输入实数a 和 整数t
		double a;
		int t;
		cin>>a>>t;
		// 核心处理，把路灯关的打开，开的关掉
		for(int j=1;j<=t;j++){
    
			// 一个数学原理
			flag[int(j*a)]-=1;
			flag[int(j*a)]*=-1;
		}
	}
	// 输出结果
	for(int i=1;i<20000001;i++){
    
		if(flag[i]){
    
			cout<<i;
			return 0;
		}
	}
	return 0;
}

上面提到的数学原理，是说把1变成0，把0再变成1这件事。如果直接写if的话会超时。
我最开始想到的是利用绝对值嘛，你看这里有个0，它减1就变-1了，-1的绝对值是1；1减去1变成0，0的绝对值还是0。这样就变化了。
再进一步简化，因为减去1以后非正数了，所以，负数的绝对值是它的相反数，我们就可以表示为-1的相反数为1，而且规定了0的相反数是0。所以，我们有：

x-=1;
// x=-x;
x*=-1;