2017 Multi-University Training Contest - Team 1

时间:2022-03-26 04:28:43

题目链接

http://acm.split.hdu.edu.cn/listproblem.php?vol=51

HDU 6033-6044

官方题解

http://bestcoder.hdu.edu.cn/blog/2017-multi-university-training-contest-8-solutions-by-%E5%8C%97%E4%BA%AC%E8%88%AA%E7%A9%BA%E8%88%AA%E5%A4%A9%E5%A4%A7%E5%AD%A6/


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)=log10​​2m​​=mlog10​​2⌋。

 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 }