進制均值
Description：
小明非常喜歡自然數(shù)，他發(fā)現(xiàn)自然數(shù)123用十六進制表示時只有兩位臣嚣，第一位是7 第二位是11涨颜，所以自然數(shù)123用十六進制表示時的 數(shù)碼和 是18. 現(xiàn)在他想知道自然數(shù)n用2進制、3進制茧球、4進制......n-1進制表示時所有的數(shù)碼和加起來的平均值庭瑰。計算數(shù)碼和時采用的是十進制，最終的結(jié)果是不可約的分數(shù)抢埋。
輸入有多組測試數(shù)據(jù)弹灭，每組測試數(shù)據(jù)占一行，為自然數(shù)n(3 <= n <= 1000)揪垄，輸入到文件結(jié)束穷吮。輸出輸出題目要求的結(jié)果，格式為 X/Y 饥努，分子在前捡鱼，分母在后。每個結(jié)果占一行酷愧。
樣例輸入
5
3
樣例輸出
7/3
2/1
這道題比較簡單驾诈，首先借用一下任意進制轉(zhuǎn)換的代碼：
// n ：被轉(zhuǎn)換的數(shù)字
// m ：代表m進制
// a[] ：代表儲存轉(zhuǎn)換后數(shù)字的數(shù)組
while(n){
a[k++] = n % m;
n /= m;
}
要求和的話就需要做一些變動了。只需要令一個數(shù)字sum保存溶浴，然后將第二行代碼改為 sum += n%m; 即可乍迄。
得到所有的數(shù)碼位的和后，下一步就是求平均值了士败。這里要注意約分一下闯两，因為 sum 不一定與分母互質(zhì)。注意到從 2 到 n-1 共有 n-2 個數(shù)，因此只需要用輾轉(zhuǎn)相除法求得 sum 和 n-2 的最大公約數(shù)漾狼，再輸出 (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個幸運數(shù)字
Description：數(shù)字4和7是幸運數(shù)字，而其他的都不是幸運數(shù)字逊躁。一個整數(shù)是幸運數(shù)字伤锚，當(dāng)且僅當(dāng)它的十進制表示只包含幸運數(shù)字。
現(xiàn)在讓你給出第K大的幸運數(shù)字志衣。
Input
第一行一個整數(shù)K（1<=K<=10^18）
Output
第K大的幸運數(shù)字屯援。
思路：把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 |
這個規(guī)律已經(jīng)很明顯了，我們不難寫出代碼：
#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曾經(jīng)酷愛網(wǎng)絡(luò)游戲绿店，整日通宵達旦的玩游戲吉懊，導(dǎo)致身體素質(zhì)急劇下降，因此下決心痛改前非假勿，遠離一切電子產(chǎn)品借嗽，并通過遠足爬山的方式改變生活方式并提高身體素質(zhì)。由于擔(dān)心對身體造成太大的負荷转培，他總是選擇最平坦的路徑恶导，并記錄每天的行程情況及達到的最高海拔，使得連續(xù)兩天之間的海拔之差最多為一個單位浸须。不幸的是惨寿，在行程結(jié)束時，他不小心掉進河里删窒，造成部分記錄信息遺失裂垦。他想知道自己行程中可能達到的最高海拔，你是否能夠幫忙肌索？
輸入
輸入有若干組蕉拢，每組的第一行為空格分隔的兩個整數(shù)n和m，1<=n<=10^8, 1<=m<=10^5诚亚，分別表示行程天數(shù)以及未遺失的記錄數(shù)晕换。隨后緊跟m行，每行為空格分隔的兩個整數(shù)d和h亡电，1<=d<=n, 0<=h<=10^8届巩，表示行程的第幾天及當(dāng)天達到的最高海拔硅瞧。
輸出
對每組輸入份乒，如果記錄是可能的，則在單獨的行中輸出可能達到的最高海拔，否則輸出字符串“IMPOSSIBLE”（不含引號）或辖。
樣例輸入
8 2
2 0
7 0
8 3
2 0
7 0
8 3
樣例輸出
2
IMPOSSIBLE
Hint
第一天和最后一天的海拔可以是任何值瘾英。
這道題邏輯比較難懂，但是耐心分析一番后颂暇，還是可以做出來的缺谴。已知天數(shù) d1 和 d2 ，以及這兩天到達的海拔高度 h1 和 h2耳鸯，則這段時間上的最高高度為 (d2-d1)/2 + (h2+h1) 湿蛔。若 h2-h1 > d2-d1 ，則不符題意县爬，直接輸出“IMPOSSIBLE”就好了阳啥。
經(jīng)過以上推斷，不難寫出代碼：
#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 原創(chuàng)作品轉(zhuǎn)載請注明出處
