校赛F,H题题解

F题题目：火柴棒拼数

时间限制：1s 内存限制：32MB

喵星人喵喵在地球上发现了一种叫做火柴棒的东西，但他并不会用，于是请教了他在地球上的朋友汪汪，汪汪告诉他火柴棒是用来进行拼数字的游戏的，于是喵喵无可救药地爱上了这个游戏并乐此不疲……
每个数的拼法如下图：


喵喵是个爱思考的好孩子，现在他想拼出数字x，但他想提前知道他需要多少根火柴棒，于是他很快就算出来了，你可以吗？
输入:
有多组输入样例，最后以文件结尾EOF结束。
第一行是一个整数T，表示有T组测试样例，0 ≤ T ≤ 1000。
之后的T行中，每一行有一个数字x。（x的位数小于1000）
（注意输入的x可能会有前导零，但是要求拼出的数字不能有多余的前导零，即：输入0011 输出应该为4，即拼出11即可， 但末尾的零不能省略）

输出：
针对每一个测试样例，输出一行结果。
结果的格式为:
”Case #$No: $A”，其中，$No表示第No组样例，$A表示拼出x需要的火柴棍数。
输入样例 输出样例
2
73
409 Case #1: 8
Case #2: 16

防爆零的水题之一~~~~~

1000位，得拿字符串读进来，然后一位一位的累加需要的火柴就可以啦，含有前导零的要将其去掉，注意一个特殊情况：000000，由于是0，最后一个零要保留

没有啦……水题一道，大家AC愉快吧！

可是可是~~~~校赛的时候卡死了一堆人，通过率只有36%~~~~(>_<)~~~~ ……不幸福，送分都没送出去~~~~~~

#include <iostream>
#include <string.h>
#include <string>
#include <stdio.h>
using namespace std;
const int a[] ={6,2,5,5,4,5,6,3,7,6};
int t;
char s[1020];
int deal()
{
    int l = 0;
    while ((l < strlen(s)) && (s[l] == '0') )
    {
        l++;
    }
    //printf("%d\n", l);
    if (l == strlen(s)) return a[0];
    int re = 0;
    while (l < strlen(s))
    {
        re += a[s[l] - '0'];
        l++;
    }
    return re;

}
int main()
{
    scanf("%d", &t);
    for (long i= 1; i <= t; i++)
    {

		scanf("%s", s);
		printf("Case #%d: ", i);
        printf("%d\n", deal());
    }
    return 0;
}

H题题目:

喵星人吃土豆

时间限制：1s                                           内存限制：32MB 

描述：

喵星人喵喵在到了地球以后爱上了吃土豆，并将土豆的种子带回了喵星球进行播种，但是他等啊等土豆都没有成熟……

……

　　终于有一天，喵喵种的土豆奇迹般的收获了，于是他得到了很多很多的土豆（实在太多，数不过来，你可以认为是无穷个）。他将这很多很多个土豆按照重量进行了排序，每个土豆的编号依次为1、2、3……N，然后他就惊奇地发现：由于喵星球的土壤很奇特，第i个土豆的重量正好是3^(i-1) 。

　　现在喵喵要吃掉其中的若干个土豆。他每次拿的土豆的数目是任意的，选得土豆也是任意的。选中的土豆的“总重量”为每个土豆重量之和。例如：喵喵这一次拿了第一个土豆和第三个土豆，那么总重量为1+9=10。

　　喵喵想知道，在所有的选土豆方案里，他可以获得的第k大的“总重量”是多少。

输入:

有多组输入样例，最后以文件结尾EOF结束。

第一行是一个整数T，表示有T组测试样例，0 ≤ T ≤ 70。

之后的T行中，每一行有一个数字k。（k<=2^31-1）

输出

针对每一个测试样例，输出一行结果。

结果的格式为:

”Case#$No: $A”，其中，$No表示第No组样例，$A表示他可以获得的第k大的总重量。

具体的请参见输出样例。

样例说明：

土豆的重量依次为：1,3,9,27,81……

喵喵能够拿到的重量从小到大为：

1、3、4（=1+3）、9、10=（1+9）、12=（9+3）、13（=1+9+3）……

所以第7大的美观程度是13,第四大是9

先说明：本题不是本弱原创，据说是一个叫做oibh的上古论坛上的题，在初高中竞赛的一些测评网站上（如RQNOJ等）有原题，所以我就把题目描述改了……（原题名叫：猫猫的小鱼）

思路：

我们假设用01来表示每一个编号的土豆取还是不取，于是：对于每一个取土豆的方式，都有唯一的二进制串与之对应，如取1,3,4,7号土豆，对应串为1001101（从右向左编号），而这个串对应的美观值是1 * 3^0 + 0 * 3^1 + 1 * 3^2 + 1 * 3^3 +0 * 3^4 + 0 * 3^5 + 1 * 3^6 ，事实上就是这个串的当成三进制展开的值。而由于这些01串当成二进制和当成三进制的大小关系是相同的，所以，重量第k大的方案对应的的01串就是k的二进制表示，而对于一个了01串，它所对应的重量就是这个串按照三进制展开的值，于是本题解法为：将k所对应的二进制串当成三进制串转为十进制……

（如果还没想通，再看看下面的表）

 有同学直接手推通项公式，膜拜！

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
using namespace std;
int t, n;
void deal(int x)
{
	long long re = 0;
	long long k = 1LL;
	while (x > 0)
	{

		re += k * (x & 1);
		x = x >> 1;
		k *= 3LL;
	}
	cout << re << endl;
}
int main()
{
	scanf("%d", &t);
	for (int i = 1; i <= t; i++)
	{
		printf("Case #%d: ", i);
		scanf("%d", &n);
		deal(n);
	}
	return 0;
}