题目链接
http://acm.split.hdu.edu.cn/listproblem.php?vol=51
HDU 6033-6044
官方题解
1001 Add More Zero
http://acm.split.hdu.edu.cn/showproblem.php?pid=6033
题意是一台计算机可以表示0 ~ 2m-1的整数,询问这个区间内最大的10k整数是多少。
例如m=32,k=9(0 ~ 4294967295),m=64,k=19(0 ~ 18446744073709551615)。
计算公式⌊log10(2m−1)⌋=⌊log102m⌋=⌊mlog102⌋。
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int main(){ 5 int kase = 1, n; 6 while(~scanf("%d", &n)){ 7 double t = n * log10(2); 8 printf("Case #%d: %d\n", kase++, (int)t); 9 } 10 }
1002 Balala Power!
http://acm.split.hdu.edu.cn/showproblem.php?pid=6034
给出n个仅由小写字母组成的字符串,求一个从小写字母到[0..25]的映射,使得在该映射下,将原来的字符串看作26进制整数,使得这些整数的和最大。
在原字符串可以看作26进制整数的意义下,可以将每个26进制“整数”转换成十进制表示法,也就是Σai*26i,其中,ai为字母,i为位数。
例如样例三,有如下表示:
a = a
ba = b*26 + a
abc = a*262 + b*26 + c
将它们求和,得到 sum = a * (262 + 2*1) + b * (2 * 26) + c * (1)。
将字母看作未知数时,求sum最大的映射自然就是系数越大赋值越大,也就是按照系数升序排序,求和时系数×次序即可。
注意附加条件,不能有前导0的出现,即一个字符串长度大于1时,字符串第一个字母不能映射到0。
出现这种情况时,先从小到大找到第一个可以没有出现在开头的字母,然后把原来第0个字母插到查找到的位置中,然后这中间所有的字母往前移动一个。
例如,排序后的结果是abcd……,其中ab都不能映射为0,cd可以,上述处理之后,次序应该是cabd……。
(证明:对于每种排列,写出sum表达式,利用a<b<c<d的条件可以证明cabd最大。)
代码实现套大数板子,记录每个字母在每一位的出现,处理进位,排序,处理附加条件。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 #define FOR(x, n) for(int x = 0; x < (n); x++) 5 #define FORR(x, n) for(int x = 1; x <= (n); x++) 6 #define FRR(x, a, b) for(int x = (a); x < (b); x++) 7 #define CLR(x) memset(x, 0, sizeof(x)) 8 #define SET(x) memset(x, -1, sizeof(x)) 9 #ifndef _GLIBCXX_ALGORITHM 10 #define max(a, b) ((a) > (b) ? (a) : (b)) 11 #define min(a, b) ((a) < (b) ? (a) : (b)) 12 #endif 13 const int oo = 0x3fffffff; 14 // const int oo = 0x2AAAAAAA; 15 const int mod = 1e9+7; 16 const int MAXSIZE = 100000 + 100; 17 const int m = 26; 18 19 LL pow_mod(LL a, LL b, LL n){ 20 LL r = 1, base = a; 21 while(b){ 22 if(b&1) r *= base; 23 r %= n; 24 base *= base; 25 base %= n; 26 b >>= 1; 27 } 28 return r; 29 } 30 31 struct bign{ 32 static const int base = 26; 33 static const int MAXSIZE = 100100; 34 int num[MAXSIZE + 100]; 35 int len; 36 bool flag; 37 char ch; 38 39 bign(){ 40 clear(); 41 } 42 43 void clear(){ 44 CLR(num); 45 len = 1; 46 flag = false; 47 } 48 49 bool operator < (const bign &b) const{ 50 if(len != b.len) return len < b.len; 51 for(int i = len-1; i >= 0; i--) 52 if(num[i] != b.num[i]) return num[i] < b.num[i]; 53 return true; 54 } 55 56 void carry(){ 57 FOR(i, len-1){ 58 if(num[i] >= base){ 59 num[i+1] += num[i] / base; 60 num[i] %= base; 61 } 62 } 63 if(num[len-1] >= base){ 64 num[len] = num[len-1] / base; 65 num[len-1] %= base; 66 len ++; 67 } 68 } 69 70 LL toLL(){ 71 LL ans = 0; 72 FOR(i, len){ 73 ans += num[i] * pow_mod(base, i, mod); 74 ans %= mod; 75 } 76 return ans; 77 } 78 }; 79 80 bign cnt[m]; 81 char str[1000000 + 10]; 82 83 int main(){ 84 int n, kase = 1; 85 while(~scanf("%d", &n)){ 86 FOR(i, m) cnt[i].clear(); 87 while(n--){ 88 scanf("%s", str); 89 int len = strlen(str); 90 FOR(i, len){ 91 cnt[str[i]-'a'].num[len-i-1]++; 92 cnt[str[i]-'a'].len = max(cnt[str[i]-'a'].len, len-i); 93 } 94 if(len > 1) cnt[str[0]-'a'].flag = true; 95 } 96 FOR(i, m) cnt[i].ch = 'a' + i; 97 FOR(i, m) cnt[i].carry(); 98 stable_sort(cnt, cnt+m); 99 // FOR(i, m) cout << cnt[i].ch << ' ' << cnt[i].flag << ' ' << i << ' ' << cnt[i].toLL() << endl; 100 // FOR(i, m) cout << cnt[i].toLL() << endl; 101 int k = 1; 102 while(cnt[0].flag == true){ 103 swap(cnt[0], cnt[k++]); 104 } 105 // FOR(i, m) cout << cnt[i].ch << ' ' << cnt[i].flag << ' ' << i << ' ' << cnt[i].toLL() << endl; 106 107 LL ans = 0; 108 FOR(i, m){ 109 ans += i * cnt[i].toLL(); 110 ans %= mod; 111 } 112 printf("Case #%d: %I64d\n", kase++, ans); 113 } 114 }
1011 KazaQ's Socks
http://acm.split.hdu.edu.cn/showproblem.php?pid=6043
题意,有柜子和篮子分别放没穿和穿过的袜子,最初有编号1~n的袜子在柜子里,每天找编号最小的那个穿,晚上放到篮子里,当篮子里有n-1双时(柜子里只剩一双的时候),篮子里的洗完后就都重新回到柜子里。
手动模拟计算样例,发现是按照如下规律循环计数的:
1, 2, 3, 1, 2, 1, 3, 1, 2, 1, 3, ...
1, 2, 3, 4, 1, 2, 3, 1, 2, 4, 1, 2, 3, 1, 2, 4, ...
(1, 2, ... , n) , (1, 2, ... , n-2, n-1) , (1, 2, ... , n-2, n) , (1, 2, ... , n-2, n-1) , (1, 2, ... , n-2, n) , ...
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 5 int main(){ 6 int n, kase = 1, ans; 7 LL k; 8 while(~scanf("%d%I64d", &n, &k)){ 9 if(k <= n) ans = k; 10 else{ 11 k -= n; 12 int turn = 2 * (n-1); 13 k %= turn; 14 if(k == 0) k = turn; 15 if(k <= turn /2) ans = k; 16 else{ 17 k -= turn/2; 18 if(k < turn/2) ans = k; 19 else ans = k + 1; 20 } 21 } 22 printf("Case #%d: %d\n", kase++, ans); 23 } 24 }