/*———————————————————————————————————————————————————————————
【结果填空题】T1 (分值：3)
题目：煤球数目
有一堆煤球，堆成三角棱锥形。具体：
第一层放1个，
第二层3个（排列成三角形）,
第三层6个（排列成三角形）,
第四层10个（排列成三角形）,
....
如果一共有100层，共有多少个煤球？
请填表示煤球总数目的数字。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
1 * (1)
2 *** (3)
3 ****** (6)
4 ********** (10)
5 ..............(15)
————————————————————————————————————————————————————————————*/
//
/**
* pre 定义上一层
* plus 定义增量差值 */
#include<iostream>
using namespace std ;
int main(int argc, char const *argv[])
{
int pre = 1 ; //
int plus = 2 ; //
long sum = 1 ;
for (int k = 2; k <= 100; ++k)
{
sum += (pre+plus) ;
pre = pre + plus ;//sum+=pre
plus++ ;
}
cout << sum << endl ;
return 0;
}
//结果：171700
/*———————————————————————————————————————————————————————————
【结果填空题】T2 (分值：5)
题目：生日蜡烛
某君从某年开始每年都举办一次生日party，
并且每次都要吹熄与年龄相同根数的蜡烛。
现在算起来，他一共吹熄了236根蜡烛。
请问，他从多少岁开始过生日party的？
请填写他开始过生日party的年龄数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
————————————————————————————————————————————————————————————*/
//
/*
思路：236 i ~ j
for(i:100)
for(j:100)
等差数列求和：(i+j)/2*(j-i-1)
(a0+a0*(n-1)*d/2)*n*/
#include<iostream>
using namespace std ;
int main()
{
//枚举两个年龄
for (int i = 1; i < 100; ++i)
{
for (int j = i; j < 100; ++j)
{
if((i*j)*(j-i-1)/2==236)
cout << i << " "<< j << endl ;
}
}
//枚举生日举办次数
for (int i = 1; i < 100; ++i)
{
int t = i*(i-1)/2 ;
if((236-t)%i==2)
{
//输出首项
cout << (236-t)/i << " " << i << endl ;
}
}
return 0 ;
}
/*———————————————————————————————————————————————————————————
【结果填空题】T3 (分值：11)
题目：凑算式
B DEF
A + --- + ------- = 10
C GHI
（如果显示有问题，可以参见【图1.jpg】）
这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。
比如：
6+8/3+952/714 就是一种解法，
5+3/1+972/486 是另一种解法。
这个算式一共有多少种解法？
注意：你提交应该是个整数，不要填写任何多余的内容或说明性文字。
————————————————————————————————————————————————————————————*/
//
//全排列
#include<iostream>
#include<math.h>
using namespace std ;
int a[] = {1,2,3,4,5,6,7,8,9} ;
int ans ;
bool check()
{
int x = a[3] * 100 + a[4] * 10 + a[5] ;
int y = a[6] * 100 + a[7] * 10 + a[8] ;
if((a[1]*y + a[2]*x) % (y*a[2])==0 && a[0]
+ (a[1]*y + a[2]*x)/(y*a[2]==10)) return true ;
return false ;
}
//递归回溯生成全排列 适用于无重复元素的情况
//考虑前k位，前面已经排定
void f(int k)
{
if(k==9)
{
//其中一种排列已经生成
if(check()) ans++ ;
}
//从k往后的每个数字都可以放在k位
for (int i = k; i < 9; ++i)
{
{int t=a[i]; a[i]=a[k]; a[k]=t;}
f(k+1) ; //递归
{int t=a[i]; a[i]=a[k]; a[k]=t;} //回溯
}
}
int main()
{
f(0) ;
cout << ans << endl ;
return 0 ;
}
//思路二 next_permutation()
#include<iostream>
#include<math.h>
using namespace std ;
int a[] = {1,2,3,4,5,6,7,8,9} ;
int ans ;
bool check()
{
int x = a[3] * 100 + a[4] * 10 + a[5] ;
int y = a[6] * 100 + a[7] * 10 + a[8] ;
if((a[1]*y + a[2]*x) % (y*a[2])==0 && a[0]
+ (a[1]*y + a[2]*x)/(y*a[2]==10)) return true ;
return false ;
}
int main()
{
do{
if(check()) ans++ ;
}while(next_permutation(a,a+9)) ;
cout << ans << endl ;
return 0 ;
}
/*———————————————————————————————————————————————————————————
【代码填空题】T4 (分值：9)
题目：快速排序
排序在各种场合经常被用到。
快速排序是十分常用的高效率的算法。
其思想是：先选一个“标尺”，
用它把整个队列过一遍筛子，
以保证：其左边的元素都不大于它，其右边的元素都不小于它。
这样，排序问题就被分割为两个子区间。
再分别对子区间排序就可以了。
下面的代码是一种实现，请分析并填写划线部分缺少的代码。
————————————————————————————————————————————————————————————*/
//
#include <stdio.h>
void swap(int a[], int i, int j)//交换
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
int partition(int a[], int p, int r)
{
int i = p; //i指向大于x ——>找大
int j = r + 1; //j指向小于等于x ——>找小
int x = a[p];
while(1){
while(i<r && a[++i]<x);
while(a[--j]>x);
if(i>=j) break;
swap(a,i,j);
}
/*代码填空处
swap(a,p,j) ; //
______________________; */
return j;
}
void quicksort(int a[], int p, int r)
{
if(p<r){
int q = partition(a,p,r); //q为标尺
quicksort(a,p,q-1);
quicksort(a,q+1,r);
}
}
int main()
{
int i;
int a[] = {5,13,6,24,2,8,19,27,6,12,1,17};
int N = 12;
quicksort(a, 0, N-1); //排序
for(i=0; i<N; i++)
printf("%d ", a[i]);
printf("\n");
return 0;
}
/*———————————————————————————————————————————————————————————
【代码填空题】T5 (分值：13)
题目：抽签
X星球要派出一个5人组成的观察团前往W星。
其中：
A国最多可以派出4人。
B国最多可以派出2人。
C国最多可以派出2人。
....
那么最终派往W星的观察团会有多少种国别的不同组合呢？
下面的程序解决了这个问题。
数组a[] 中既是每个国家可以派出的最多的名额。
程序执行结果为：
DEFFF
CEFFF
CDFFF
CDEFF
CCFFF
CCEFF
CCDFF
CCDEF
BEFFF
BDFFF
BDEFF
BCFFF
BCEFF
BCDFF
BCDEF
....
(以下省略，总共101行)
————————————————————————————————————————————————————————————*/
//递归填空
#include <stdio.h>
#define N 6
#define M 5
#define BUF 1024
/**
* k = 数组的下标
* m代表人数，初始为5
* b缓冲字符串
*/
void f(int a[], int k, int m, char b[])
{
int i,j;
if(k==N){
b[M] = 0; //字符串结尾的标志
if(m==0) {printf("%s\n",b); ans++ ;}
return;
}
//递归
for(i=0; i<=a[k]; i++){ //试着将k国家，排除i人
for(j=0; j<i; j++) b[M-m+j] = k+'A'; ////填充buf，有i人就填i个国家符号(k+'A')
/*代码填空处
f(a,k+1,m-i,b) ;
______________________; */
f(a,k+1,m-i,b) ;
}
}
int main()
{
int a[N] = {4,2,2,1,1,3};
char b[BUF];
f(a,0,M,b);
printf("%d\n",ans) ;
return 0;
}
/*———————————————————————————————————————————————————————————
【结果填空题】T6 (分值：19)
题目：方格填数
如下的10个格子
+--+--+--+
| | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | |
+--+--+--+
（如果显示有问题，也可以参看【图1.jpg】）
填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）
一共有多少种可能的填数方案？
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
————————————————————————————————————————————————————————————*/
// 全排列 + 检查
#include<iostream>
using namespace std ;
int a[10] = {0,1,2,3,4,5,6,7,8,9} ;
int ans ;
void check()//检查
{
if(abs(a[0] - a[1])==1 ||
abs(a[0] - a[3])==1 ||
abs(a[0] - a[4])==1 ||
abs(a[0] - a[5])==1 ||
abs(a[1] - a[2])==1 ||
abs(a[1] - a[4])==1 ||
abs(a[1] - a[5])==1 ||
abs(a[1] - a[6])==1 ||
abs(a[2] - a[5])==1 ||
abs(a[2] - a[6])==1 ||
abs(a[3] - a[4])==1 ||
abs(a[3] - a[7])==1 ||
abs(a[3] - a[8])==1 ||
abs(a[4] - a[5])==1 ||
abs(a[4] - a[7])==1 ||
abs(a[4] - a[8])==1 ||
abs(a[4] - a[9])==1 ||
abs(a[5] - a[6])==1 ||
abs(a[5] - a[8])==1 ||
abs(a[5] - a[9])==1 ||
abs(a[6] - a[9])==1 ||
abs(a[7] - a[8])==1 ||
abs(a[8] - a[9])==1 ||)
return false ;
return true ;
}
/*考虑第k个位置，一般从0开始*/
void f(int k)//递归函数
{
//出口
if(k==0)
{
bool b = check() ; //检查
if(b)
ans++ ;
return ;
}
for (int i = k; i < 10; ++i)
//尝试将位置i与位置k交换，以此确定k位的值
{
int t = a[i] ;
a[i] = a[k] ;
a[k] = t ;
}
f(k+1) ;
//回溯
{
int t = a[i] ;
a[i] = a[k] ;
a[k] = t ;
}
}
int main()
{
f(0) ; //初始化
cout << ans << endl ;
return 0 ；
}
//思路2 使用二维数组
/* 3*4 ——> 5*6
-10-10-10-10-10
+--+--+--+
| | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | |
+--+--+--+
-10-10-10-10-10
*/
#include<iostream>
using namespace std ;
int a[5][6] ;
int vis[10] ;
int ans ;
bool check(int i ,int y) //检查
{
for (int x = x-1; x<= i+1; ++x)
{
for (int y = j-1; y <= j+1; ++y)
{
if(abs(a[x][y]-a[i][j])==1)
return false ;
}
}
return true ;
}
//全排列
void f(int k,int y)
{
if(x==3 & y == 4)
{
ans++ ;
return ;
}
//从0-9中抓一个
for (int i = 0; i < 10; ++i)
{
if(vis[i]==0) //i没有没用过
{
a[x][y] = i ; //填数
if(!check(x,y)) //不合法，恢复并continue
{
a[x][y] = -10 ;
continue ;
}
vis[i] = 1 ;
if(y ==4)
f(x+1,1) ; //换行
else
f(x,y+1) ; //继续填右侧的格子
{
vis[i] = 0 ;
a[x][y] = -10 ;
}
}
}
}
//初始化
void init()
{
for (int i = 0; i < 5; ++i)
{
for (int j = 0; j < 6; ++j)
{
a[i][j] = -10 ; //初始化格式
}
}
}
int main(int argc, char const *argv[])
{
init() ; //初始化
f(1,2) ; //递归调用
cout << ans <<endl ; //打印输出
return 0;
}
/*本思路可以防止下标越界的问题*/
/*———————————————————————————————————————————————————————————
【结果填空题】T7 (分值：19)
题目：剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
————————————————————————————————————————————————————————————*/
//
/*
1 2 3 4
5 6 7 8
9 10 11 12
思路1：每个格子作为起点,dfs连五张，去重->结果
思路2：暴力枚举，所有的五张组合，检查它们是不是一个连通块。 */
// 12/13 寒假作业 12/5 dfs
/*思路1： 生成的方法有太多的重复，效率低下
//此题和13年剪格子有相似之处，但是那个题的限制条件是格子数值之和为总和的一半，此题则限制只能是5个格子
//单纯的dfs无法解决T字型连通方案
//本题的解决办法是，找出任意5个格子，判断是否连通*/
#include <algorithm>
#include <iostream>
using namespace std;
int ans;
bool check(int arr[12]);
void dfs(int g[3][4], int i, int j);
int main(int argc, const char *argv[]) {
int per[] = {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1};
do {
if (check(per))
ans++;
} while (next_permutation(per, per + 12));
cout << ans << endl;
return 0;
}
bool check(int arr[12]) {
int g[3][4];
memset(g, 0, sizeof(g));
//将相应位置标注为1
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 4; ++j) {
if (arr[i * 4 + j] == 1)g[i][j] = 1;
}
}
// 经典连通块计算
int cnt = 0;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 4; ++j) {
if (g[i][j] == 1) {
dfs(g, i, j);
cnt++;
}
}
}
return cnt == 1;
}
void dfs(int g[3][4], int i, int j) {
g[i][j] = 0;
if (i + 1 <= 2 && g[i + 1][j] == 1) dfs(g, i + 1, j);
if (i - 1 >= 0 && g[i - 1][j] == 1) dfs(g, i - 1, j);
if (j + 1 <= 3 && g[i][j + 1] == 1) dfs(g, i, j + 1);
if (j - 1 >= 0 && g[i][j - 1] == 1) dfs(g, i, j - 1);
}
//思路2：
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
int a[]={0,0,0,0,0,0,0,1,1,1,1,1};//它的每个排列代表着12选5的一个方案
int ans;
void dfs(int g[3][4],int i , int j){
g[i][j]=0;
if(i-1>=0&&g[i-1][j]==1)dfs(g,i-1,j);
if(i+1<=2&&g[i+1][j]==1)dfs(g,i+1,j);
if(j-1>=0&&g[i][j-1]==1)dfs(g,i,j-1);
if(j+1<=3&&g[i][j+1]==1)dfs(g,i,j+1);
}
bool check(){
int g[3][4];
// 将某个排列映射到二维矩阵上
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 4; ++j) {
if(a[i*4+j]==1) g[i][j]=1;
else g[i][j]=0;
}
}
int cnt=0;//连通块的数目
// g上面就有5个格子被标记为1，现在才用dfs做连通性检查，要求只有一个连通块
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 4; ++j) {
if(g[i][j]==1){
dfs(g,i,j);
cnt++;
}
}
}
return cnt==1;
}
set<string> s1;
void a2s(string &s){
for (int i = 0; i < 12; ++i) {
s.insert(s.end(),a[i]+'0');
}
}
bool isExist(){
string a_str;
a2s(a_str);
if(s1.find(a_str)==s1.end()){
s1.insert(a_str);
return false;
} else
return true;
}
void f(int k){
if(k==12){
if(!isExist()&&check()){
ans++;
}
}
for (int i = k; i < 12; ++i) {
{int t=a[i];a[i]=a[k];a[k]=t;}
f(k+1);
{int t=a[i];a[i]=a[k];a[k]=t;}
}
}
int main(int argc, const char *argv[]) {
f(0);
printf("%d",ans);
//string _s;
//a2s(_s);
//cout<<_s<<endl;
return 0;
}
//思路3：
#include <algorithm>
#include <iostream>
using namespace std;
//它的每个排列代表着12选5的一个方案
int a[] = {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1};
int ans;
void dfs(int g[3][4], int i, int j)
{
g[i][j] = 0;
if (i - 1 >= 0 && g[i - 1][j] == 1)dfs(g, i - 1, j);
if (i + 1 <= 2 && g[i + 1][j] == 1)dfs(g, i + 1, j);
if (j - 1 >= 0 && g[i][j - 1] == 1)dfs(g, i, j - 1);
if (j + 1 <= 3 && g[i][j + 1] == 1)dfs(g, i, j + 1);
}
bool check(int path[12])
{
int g[3][4];
// 将某个排列映射到二维矩阵上
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 4; ++j)
{
if (path[i * 4 + j] == 1) g[i][j] = 1;
else g[i][j] = 0;
}
}
int cnt = 0;//连通块的数目
// g上面就有5个格子被标记为1，现在才用dfs做连通性检查，要求只有一个连通块
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 4; ++j)
{
if (g[i][j] == 1)
{
dfs(g, i, j);
cnt++;
}
}
}
return cnt == 1;
}
bool vis[12];
void f(int k, int path[12])
{
if (k == 12) {
if (check(path))
{
ans++;
}
}
for (int i = 0; i < 12; ++i)
{
if (i>0&&a[i]==a[i-1]&&!vis[i-1])continue;//现在准备选取的元素和上一个元素相同，但是上一个元素还没被使用
if(!vis[i]){//没有被用过的元素可以抓入到path
vis[i]=true;//标记为已访问
path[k]=a[i];//将a[i]填入到path[k]中
f(k + 1, path);//递归
vis[i]=false;//回溯
}
}
}
int main(int argc, const char *argv[])
{
int path[12];
f(0, path);
printf("%d", ans);
return 0;
}
/*———————————————————————————————————————————————————————————
【代码编程题】T8 (分值：21)
题目：四平方和
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多4个正整数的平方和。
如果把0包括进去，就正好可以表示为4个数的平方和。
比如：
5 = 0^2 + 0^2 + 1^2 + 2^2
7 = 1^2 + 1^2 + 1^2 + 2^2
（^符号表示乘方的意思）
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对4个数排序：
0 <= a <= b <= c <= d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，
最后输出第一个表示法
程序输入为一个正整数N (N<5000000)
要求输出4个非负整数，按从小到大排序，中间用空格分开
例如，输入：
5
则程序应该输出：
0 0 1 2
再例如，输入：
12
则程序应该输出：
0 2 2 2
再例如，输入：
773535
则程序应该输出：
1 1 267 838
资源约定：
峰值内存消耗 < 256M
CPU消耗 < 3000ms
请严格按要求输出，不要画蛇添足地打印类似：
“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，
不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>，
不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
————————————————————————————————————————————————————————————*/
//枚举+优化
//优化：采用缓存来空间换时间
/*思路1：
枚举abcd
for(a) 0~a^2
for(b) 0~b^2
for(c) 0~c^2
for(d) 0~d^2
*/
#include<iostream>
#include<cstdio>
#include<map>
int N ;
using namespace std ;
int main()
{
scanf("%d",&N) ;
//
for (int c = 0; c*c <= N/2; ++c)
{
for (int d = c; c*c+d*d <= N ; ++d)
{
if(cache.find(c*c+d*d)==cache.end())
cache[c*c+d*d] = c ;
}
//
for (int a = 0; a*a<= N/4; ++a)
{
for (int b = a; a*a+c*c <= N/2; ++b)
{
if(cache.find(N-a*a+b*b)!=cache.end()) ;
int c = cache[N-(a*a+b*b+c*c)] ;
int d = int(sqrt(N-(a*a+b*b+c*c)) ;
printf("%d %d %d %d\n",a,b,c,d) ;
return 0 ;
}
}
}
return 0 ;
}
/*———————————————————————————————————————————————————————————
【代码编程题】T9 (分值：23)
题目：交换瓶子
有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
程序应该输出：3
再例如，输入：
5
5 4 3 2 1
程序应该输出：2
资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，
不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>，
不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
————————————————————————————————————————————————————————————*/
/*
3 2 1 5 4
[1] [2] [3] [4] [5] */
// 贪心
#include <iostream>
using namespace std;
int n;
int a[10001];
int ans;
int pos(int x)
{
for (int i = 1; i <= n; ++i)
{
if (a[i] == x)return i;
}
return -1;
}
void swap(int i, int j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
void printArr() {
for (int i = 1; i <= n; ++i)
{
printf("%d ", a[i]);
}
printf("\n");
}
int main(int argc, const char *argv[])
{
// 处理输入
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
}
//遍历i:1-N
for (int i = 1; i <= n; ++i)
{
//如果a[i]=i,已经到位
if (a[i] == i)continue;
//否则先找到i在a中的位置pos(i)和i位交换——swap(a,pos(i),i)
else
{
swap(pos(i), i);
ans++;
}
}
//printArr();
printf("%d\n", ans);
return 0;
}
/*———————————————————————————————————————————————————————————
【代码编程题】T10 (分值：31)
题目：最大比例
X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。
并且，相邻的两个级别间的比例是个固定值。
也就是说：所有级别的奖金数构成了一个等比数列。比如：
16,24,36,54
其等比值为：3/2
现在，我们随机调查了一些获奖者的奖金数。
请你据此推算可能的最大的等比值。
输入格式：
第一行为数字 N (0<N<100)，表示接下的一行包含N个正整数
第二行N个正整数Xi(Xi<1 000 000 000 000)，用空格分开。
每个整数表示调查到的某人的奖金数额
要求输出：
一个形如A/B的分数，要求A、B互质。表示可能的最大比例系数
测试数据保证了输入格式正确，并且最大比例是存在的。
例如，输入：
3
1250 200 32
程序应该输出：25/4
再例如，输入：
4
3125 32 32 200
程序应该输出：5/2
再例如，输入：
3
549755813888 524288 2
程序应该输出：4/1
资源约定：
峰值内存消耗 < 256M
CPU消耗 < 3000ms
请严格按要求输出，不要画蛇添足地打印类似：
“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，
不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>，
不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
————————————————————————————————————————————————————————————*/
//
/*
等比数列：a0、a1、a2、a3、a4
等比数列的性质：
a3 p
—— ——> (———)^2
a0 q
*/
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std ;
typedef long long LL ;
int N ;
LL data[100] ;
struct Ratio{
LL x,y ;
Ratio(LL _x,LL _y):x(_x),(_y)
{
LL _gcd = gcd(x,y) ;
x /= _gcd ;
y /= _gcd ;
}
LL gcd(LL a,LL b)
{
if(b==0) return a ;
return gcd(b,a%b) ;
}
} ;
//存储比值
vector<Ratio> ratios ;
int main()
{
//处理输入
scanf("%d",&n) ;
for (int i = 0; i < N; ++i) //扫描输入数据
{
scanf("%lld",&data[i]) ;
}
//排序
sort(data,data+N) ;
//两两比值，以分数形式存储，vector
for (int i = 0; i < N-1; ++i)
{
if(data[i+1]!=data[i])//去重
ratios.push_back(Ratio(data[i+1],data[]i)) ;
}
/*对第一个比值开1-..pow(极限为40)次方作为基数，
如果这个基数的分子、分母的k1
k2次方恰好是其他比值的分子分母的话，基数就是答案*/
for (int pow = 0; pow <= 40; ++pow)
{
Ratio ra0 = ratios[0] ;
LL x = ra0.x ;
LL y = ra0.y ;
LL fx = extract(x,pow) ; //对
LL fy = extract(y,pow) ; //
if(fx==-1 |\ fy ==-1) continue ; //开不出，continue
//能开，就要确认所有比值的分子是fx的整数次方，所有比值的分母是fy的整数次方
//计px=getPow(xx,fx),py=getPow(yy,fy),要求必须是整数且px==py
bool all_match = true ;
//
for (int i = 1; i < ratios.size(); ++i)
{
LL xx = ratios[i].x ;
LL yy = ratios[i].y ;
LL px = getPow(xx,fx) ;
LL py = getPow(yy,fy) ;
if(px == -1 || py == -1 || px != py)
{
all_match = false ;
break ;
}
}
if(all_match)
{
Ratio ans = Ratio(fx,fy) ;
cout << ans.x << "/" << ans.y << endl ;
}
return 0 ;
}
return 0 ;
}
//优化 + 完善
#include <stdio.h>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
typedef long long LL;
int N;
LL data[100];
//结构体
struct Ratio
{
LL x, y;
Ratio(LL _x, LL _y) : x(_x), y(_y)
{
LL _gcd = gcd(x, y);
x /= _gcd;
y /= _gcd;
}
LL gcd(LL a, LL b)
{
if (b == 0)return a;
return gcd(b, a % b);
}
};
vector<Ratio> ratios;
map<LL, map<LL,LL> > all_ex;//all_ex[x][pow]==x开pow次方
map<LL, map<LL,LL> > all_log;//all_log[x][y]==log_y_x，y的多少次方是x？
void init() //预处理
{
for (int i = 2; i < 1e6; ++i)
{//底数
LL cur=(LL)i*i;
int pow=2;
while(cur<1e12)
{
all_ex[cur][pow]=i;
all_log[cur][i]=pow;
pow++;
cur*=i;
}
}
}
/**
* 对x开pow次方
* @param x
* @param pow
* @return
*/
LL extract(LL x,LL pow)
{
if(pow==1)return x;
if(x==1)return 1;
if(all_ex[x].find(pow)!=all_ex[x].end())//意味着x可以开pow整数次方
return all_ex[x][pow];
else
return -1;
}
/**
* 求log_base_x
* @param base
* @param x
* @return
*/
LL log(LL base,LL x)
{
if(base==x)return 1;
if(all_log[x].find(base)!=all_log[x].end())//意味着可以得打一个k，base的k次方是x
return all_log[x][base];
return -1;
}
int main(int argc, const char *argv[])
{
init();
freopen("/Users/zhengwei/CLionProjects/lanqiaobei2019/2016_C_A/data10/in8.txt","r",stdin);
//处理输入
scanf("%d", &N);
for (int i = 0; i < N; ++i)
{
scanf("%lld", &data[i]);
}
//排序
sort(data, data + N);
//处理只有两项的特殊情况
if(N==2)
{
Ratio ans = Ratio(data[1], data[0]);
cout << ans.x << "/" << ans.y << endl;
return 0;
}
//求两两比值，以分数形式存储，vector
for (int i = 0; i < N - 1; ++i)
{
if (data[i + 1] != data[i])//去重
ratios.push_back(Ratio(data[i + 1], data[i]));
}
//对第一个比值开1~..pow(极限为40).次方，作为基数，如果这个基数也是其他比值的基数的话，该基数就是答案
for (int pow = 1; pow <= 40; ++pow)
{
Ratio ra0 = ratios[0];
LL x = ra0.x;
LL y = ra0.y;
LL base_x = extract(x, pow);//对x开pow次方，作为基数，去尝试
LL base_y = extract(y, pow);//对y开pow次方，作为基数，去尝试
if (base_x == -1 || base_y == -1)continue;//开不出，continue
//能开：就要去确认所有比值的分子是fx的整数次方，所有比值的分母是fy的整数次方
//计px=getPow(xx,base_x),py=getPow(yy,base_y)，要求必须是整数且px==py
bool all_match = true;
for (int i = 1; i < ratios.size(); ++i)
{
LL xx = ratios[i].x;
LL yy = ratios[i].y;
LL log_x = log(base_x,xx);
LL log_y = log(base_y,yy);
if(base_y==1&&yy==1)log_y=log_x;
if (log_x == -1 || log_y == -1 || log_x != log_y) {
all_match = false;
break;
}
}
if (all_match)
{
Ratio ans = Ratio(base_x, base_y);
cout << ans.x << "/" << ans.y << endl;
return 0;
}
}
return 0;
}
//【2016年B组C++小结】
/**********************************************************
* 01【结果填空】煤球数目 ：枚举+简单计算
* 02【结果填空】生日蜡烛 ：等差数列求和
* 03【结果填空】凑算式 ：全排列
* 04【代码填空】快速排序 ：裸题
* 05【代码填空】抽签 ：递归，明确参数的含义及参数的变化方向
* 06【填空填空】方格填数 ：全排列 + check
* 07【结果填空】剪邮票(**) ：dfs解决不了T型组合，全排列+dfs求矩阵中的连通块
* 08【编程题】四平方和 ：枚举+优化
* 09【编程题】交换瓶子(**) ：贪心
* 10【编程题】最大比例(***) ：数论、等比数列、预处理
**********************************************************/
