3.7

[蓝桥杯2016初赛]煤球数目

题目描述
有一堆煤球，堆成三角棱锥形。具体：
第一层放1个，
第二层3个（排列成三角形），
第三层6个（排列成三角形），
第四层10个（排列成三角形），
….
如果一共有100层，共有多少个煤球？

输出
请填表示煤球总数目的数字。

样例输出

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=1e5+5;
int main (){
    cout<<171700<<endl;
    return 0;
}

[蓝桥杯2016初赛]冰雹数

题目描述
任意给定一个正整数N，如果是偶数，执行： N / 2；如果是奇数，执行： N * 3 + 1
生成的新的数字再执行同样的动作，循环往复。
通过观察发现，这个数字会一会儿上升到很高，一会儿又降落下来。
就这样起起落落的，但最终必会落到“1”
这有点像小冰雹粒子在冰雹云中翻滚增长的样子。
比如N=9：9,28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
可以看到，N=9的时候，这个“小冰雹”最高冲到了52这个高度。
输入
输入存在多组测试数据，对于每组测试数据输入一行包含一个正整数N(N<1000000)
输出
对于每组测试数据，输出一行包含一个正整数表示答案
(答案是指从1到N，小冰雹能冲到的最高高度)

样例输入
10
100

样例输出
52
9232

思路:直接暴力会超时，从1到n会发现偶数会重复操作，去掉重复操作，直接算奇数的即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=1e6+5;

int n;

int main (){
	while(scanf("%d",&n)!=EOF){
		ll ans=n;
		for(int i=3;i<=n;i+=2){
			ll j=i;
			while(j>=i){
				if(j&1==1) j=j*3+1;
				else j/=2;
				ans=max(ans,j);
			}
		}
		printf("%lld\n",ans);
		
	}
	return 0;
}

[蓝桥杯2016初赛]平方怪圈

题目描述
如果把一个正整数的每一位都平方后再求和，得到一个新的正整数。对新产生的正整数再做同样的处理。
如此一来，你会发现，不管开始取的是什么数字，最终如果不是落入1，就是落入同一个循环圈。
请写出这个循环圈中最大的那个数字。
输出
输出答案即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=1e4+5;
int n;
int fun(int a){
	int res=0;
	while(a){
		int temp=a%10;
		res+=temp*temp;
		a/=10;
	}
	return res;
}
int main (){
	/*scanf("%d",&n);
	int ans=0;
	int new_n; 
	for(int i=1;i<=100;i++){
		new_n=fun(n);
		n=new_n;
		ans=max(ans,n);
		cout<<n<<endl;
	}
	printf("%d\n",ans);*/
	printf("145");
	return 0;
}

[蓝桥杯2016初赛]报纸页数

题目描述
X星球日报和我们地球的城市早报是一样的，都是一些单独的纸张叠在一起而已。每张纸印有4版。
比如，某张报纸包含的4页是：5,6,11,12，可以确定它应该是最上边的第2张报纸。
我们在太空中捡到了一张X星球的报纸，4个页码分别是：1125,1126,1727,1728
请你计算这份报纸一共多少页（也就是最大页码,并不是用了几张纸哦）？
输出
输出答案即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=1e4+5;
int main (){
	cout<<1124+1728<<endl;
	
	return 0;
}

[蓝桥杯2016初赛]交换瓶子

题目描述
有N个瓶子，编号 1 ~ N，放在架子上。
比如有5个瓶子：2 1 3 5 4，要求每次拿起2个瓶子，交换它们的位置。
经过若干次后，使得瓶子的序号为：1 2 3 4 5
对于这么简单的情况，显然，至少需要交换2次就可以复位。
如果瓶子更多呢？你可以通过编程来解决。
输入
输入存在多组测试数据，对于每组测试数据：
第一行: 一个正整数N（N<10000）, 表示瓶子的数目
第二行：N个正整数，用空格分开，表示瓶子目前的排列情况。

输出
对于每组测试数据输出一行，包含一个正整数表示答案

样例输入
5
3 1 2 5 4
5
5 4 3 2 1

样例输出
3
2

思路：扫一遍数组，将a[i]上的值和本应该在i位置上的数对调即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=1e4+5;

int N;
int pos[MAX_N];
int a[MAX_N]; 
int ans;

int main (){
	while(scanf("%d",&N)!=EOF){
		ans=0;
		for(int i=1;i<=N;i++){
			scanf("%d",&a[i]);
			pos[a[i]]=i;
		}
		for(int i=1;i<=N;i++){
			if(a[i]==i) continue;
			int id1=a[i];  
			int pos1=pos[id1];	 
			int pos2=pos[i];
			int id2=a[pos2];
			ans++;
			swap(a[i],a[pos2]);
			swap(pos[id1],pos[i]);
		}
		printf("%d\n",ans);
		
	}
	 
	return 0;
}

[蓝桥杯2016初赛]凑算式

题目描述
凑算式：
A+ B/C + DEF/GHI =10
这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。
比如：
6+8/3+952/714 就是一种解法，5+3/1+972/486 是另一种解法。
这个算式一共有多少种解法？
输出
输出答案即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=1e5+5;
          //a,b,c,d,e,f,g,h,i
int a[9]={1,2,3,4,5,6,7,8,9};
 
int ans=0;
int main (){
    /*do{
    //  A C GHI +B GHI+C DEF=10*C GHI;
        int A=a[0]*a[2]*(a[6]*100+a[7]*10+a[8]);
        int B=a[1]*(a[6]*100+a[7]*10+a[8]);
        int C=a[2]*(a[3]*100+a[4]*10+a[5]);
        int D=10*(a[6]*100+a[7]*10+a[8])*a[2];
        if(A+B+C==D){
            ans++;
        }
    }while(next_permutation(a,a+9));*/
    cout<<29<<endl;
      
    return 0;
}