进制均值
Description：
小明非常喜欢自然数，他发现自然数123用十六进制表示时只有两位，第一位是7 第二位是11，所以自然数123用十六进制表示时的 数码和 是18. 现在他想知道自然数n用2进制、3进制、4进制......n-1进制表示时所有的数码和加起来的平均值。计算数码和时采用的是十进制，最终的结果是不可约的分数。
输入有多组测试数据，每组测试数据占一行，为自然数n(3 <= n <= 1000)，输入到文件结束。输出输出题目要求的结果，格式为 X/Y ，分子在前，分母在后。每个结果占一行。
样例输入
5
3
样例输出
7/3
2/1
这道题比较简单，首先借用一下任意进制转换的代码：
// n ：被转换的数字
// m ：代表m进制
// a[] ：代表储存转换后数字的数组
while(n){
a[k++] = n % m;
n /= m;
}
要求和的话就需要做一些变动了。只需要令一个数字sum保存，然后将第二行代码改为 sum += n%m; 即可。
得到所有的数码位的和后，下一步就是求平均值了。这里要注意约分一下，因为 sum 不一定与分母互质。注意到从 2 到 n-1 共有 n-2 个数，因此只需要用辗转相除法求得 sum 和 n-2 的最大公约数，再输出 (sum/gcd) / ((n-2)/gcd) 即可。代码如下：
#include <cstdio>
#include <iostream>
#include <cstdlib>
using namespace std;
int gcd(int m, int n)
{
if(n==0)
return m;
else return gcd(n, m%n);
}
int main()
{
int n;
while(cin>>n){
int sum = 0;
for(int i=2; i<n; i++){
int m = n;
while(m){
sum += m % i;
m /= i;
}
}
int t = gcd(sum, n-2);
sum /= t;
t = (n-2)/t;
cout<<sum<<"/"<<t<<endl;
}
return 0;
}
第k个幸运数字
Description：数字4和7是幸运数字，而其他的都不是幸运数字。一个整数是幸运数字，当且仅当它的十进制表示只包含幸运数字。
现在让你给出第K大的幸运数字。
Input
第一行一个整数K（1<=K<=10^18）
Output
第K大的幸运数字。
思路：把4看成二进制的0，7看成二进制的1，前面再补一个1，如下表：
| k(dec) | k+1(dec) | bin(k+1) | bin(k+1)抹去第一个1 | num |
|---|---|---|---|---|
| 1 | 2 | 10 | 0 | 4 |
| 2 | 3 | 11 | 1 | 7 |
| 3 | 4 | 100 | 00 | 44 |
| 4 | 5 | 101 | 01 | 47 |
| 5 | 6 | 110 | 10 | 74 |
| 6 | 7 | 111 | 11 | 77 |
| 7 | 8 | 1000 | 000 | 444 |
| 8 | 9 | 1001 | 001 | 447 |
| 9 | 10 | 1010 | 010 | 474 |
这个规律已经很明显了，我们不难写出代码：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <cstdlib>
using namespace std;
int main(){
int T;
long long k;
int a[1000];
scanf("%d", &T);
while(T--){
cin>>k;
memset(a,0,sizeof(a));
long long m = k+1;
int n = 0;
while(m){
n++;
m /= 2;
}
k = k+1;
n--;
cout<<n<<endl;
for(int i=n-1; i>=0; i--){
if(k%2 == 0)
a[i] = 4;
else
a[i] = 7;
k /= 2;
}
for(int i=0; i<n; i++){
printf("%d", a[i]);
}
putchar('\n');
}
return 0;
}
爬山
题目描述：
小B曾经酷爱网络游戏，整日通宵达旦的玩游戏，导致身体素质急剧下降，因此下决心痛改前非，远离一切电子产品，并通过远足爬山的方式改变生活方式并提高身体素质。由于担心对身体造成太大的负荷，他总是选择最平坦的路径，并记录每天的行程情况及达到的最高海拔，使得连续两天之间的海拔之差最多为一个单位。不幸的是，在行程结束时，他不小心掉进河里，造成部分记录信息遗失。他想知道自己行程中可能达到的最高海拔，你是否能够帮忙？
输入
输入有若干组，每组的第一行为空格分隔的两个整数n和m，1<=n<=10^8, 1<=m<=10^5，分别表示行程天数以及未遗失的记录数。随后紧跟m行，每行为空格分隔的两个整数d和h，1<=d<=n, 0<=h<=10^8，表示行程的第几天及当天达到的最高海拔。
输出
对每组输入，如果记录是可能的，则在单独的行中输出可能达到的最高海拔，否则输出字符串“IMPOSSIBLE”（不含引号）。
样例输入
8 2
2 0
7 0
8 3
2 0
7 0
8 3
样例输出
2
IMPOSSIBLE
Hint
第一天和最后一天的海拔可以是任何值。
这道题逻辑比较难懂，但是耐心分析一番后，还是可以做出来的。已知天数 d1 和 d2 ，以及这两天到达的海拔高度 h1 和 h2，则这段时间上的最高高度为 (d2-d1)/2 + (h2+h1) 。若 h2-h1 > d2-d1 ，则不符题意，直接输出“IMPOSSIBLE”就好了。
经过以上推断，不难写出代码：
#include <map>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
map<int, int> mp;
vector<int> vec;
int m, n;
int solve()
{
int max_h = mp[vec[0]] + vec[0] - 1;
for(int i=1; i<m; i++){
if(mp[vec[i]] - mp[vec[i-1]] > vec[i] - vec[i-1]){
cout<<"IMPOSSIBLE"<<endl;
return 0;
}
int t = (vec[i]-vec[i-1])/2 + (mp[vec[i]]+mp[vec[i-1]])/2;
max_h = max_h > t ? max_h : t;
}
int end = mp[vec[m-1]] + n - vec[m-1];
max_h = max_h > end ? max_h : end;
cout<<max_h<<endl;
return 1;
}
int main()
{
while(cin>>n>>m){
int d, h;
for(int i=0; i<m; i++){
cin>>d>>h;
mp[d] = h;
vec.push_back(d);
}
sort(vec.begin(), vec.end());
solve();
mp.clear();
vec.clear();
}
return 0;
}
代码可以随意取用，欢迎前来探讨或者给出错误样例～
陈政/arc001 原创作品转载请注明出处
