网络赛水题

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4272

一开始看确实很简单的，但是晕死的题意距离坑了很多人。。

View Code

 1 typedef long long ll;
 2 const int N = 1010;
 3 int a[N];
 4 int main()
 5 {
 6     int n,i,j;
 7     //freopen("data.txt","r",stdin);
 8     while(scanf("%d",&n) != EOF)
 9     {
10         for(i = 0; i < n; i++)
11         scanf("%d",&a[i]);
12         if(n % 2)
13         {
14             printf("0\n");continue;
15         }
16         int flag;
17         for(i = 0; i < n; i++)
18         {
19             int sum = 0;
20             flag = 0;
21             for(j = i + 1; j < n && sum < 8; j++)
22             {
23                 if(a[j] == a[i])
24                 {
25                     flag = 1;
26                     for(int k = j; k > i + 1; k--)
27                     a[k] = a[k - 1];
28                     i++;
29                     break;
30                 }
31                 sum ++;
32             }
33             if(!flag) break;
34         }
35         if(!flag) printf("0\n");
36         else printf("1\n");
37     }
38     return 0;
39 }

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4273

一个计算几何的题目。poj上有个类似题目，都是用这个模板。不会做，赛后搜的一个代码，改改交上去是对的，算是个模板题吧

搜的代码链接：http://hi.baidu.com/lccycc_acm/item/1fed873d08776b607c034bd2

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4278

题意：计程器坏了，凡是遇到3 和 8 就会向前跳一个数，给出计程器显示的数，求出真实的数

题目是HG写的，昨天晚上看网上人都是写的从 8 进制转换为 10 进制，我就 2 的在那推规律，找了好长时间，不过还好真的有规律（0 到 100 内跳过的数，0 到 1000 跳过的数～～～～）打出表，然后再计算，麻烦有点

View Code

 1 typedef long long ll;
 2 const int N = 1010;
 3 int a[9] = {0,2,36,488,5904,67232,737856,7902848,83222784};
 4 int pows(int n)
 5 {
 6     int i;
 7     int tem = 1;
 8     for(i = 0; i < n; i++)
 9     tem *= 10;
10     return tem;
11 }
12 int main()
13 {
14     int n;
15     int len;
16     //freopen("data.txt","r",stdin);
17     while(scanf("%d",&n), n)
18     {
19         int tem = n;
20         int ttem = n;
21         len = 0;
22         while(tem)
23         {
24             tem /= 10;
25             len ++;
26         }
27         //cout<<"len = "<<len<<endl;
28         int tsum = 0;
29         while(len)
30         {
31             int kem = n / pows(len - 1);
32             //cout<<"kem = "<<kem<<endl;
33             n %= pows(len - 1);
34             //cout<<"n = "<<n<<endl;
35             if(kem == 0) {len --; continue;}
36             if(len == 1)
37             {
38                 if(kem > 8) tsum += 2;
39                 else if(kem > 3) tsum += 1;
40             }
41             else
42             {
43                 if(kem > 8) {tsum += (kem - 2) * a[len - 1] + 2 * pows(len) / 10;}
44                 else if(kem > 3) {tsum += (kem - 1) * a[len - 1] + pows(len) / 10;}
45                 else {tsum += (kem) * a[len - 1];}
46             }
47             //cout<<"stsum = "<<tsum<<endl;
48             len --;
49         }
50 
51         //cout<<"tsum = "<<tsum<<endl;
52         printf("%d: %d\n",ttem,ttem - tsum);
53     }
54     return 0;
55 }

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4282

如果能想到当 z = 2 时，那个表达式是个完全平方式，那么 z 就可以从 3 开始枚举到 31，因为 y > x 所以，而且是幂运算，暴力枚举 x 最多到 1400，所以完全可以过

View Code

 1 typedef long long ll;
 2 ll pows(int x,int n)
 3 {
 4     int i;
 5     ll tem = 1;
 6     for(i = 0; i < n; i++)
 7     tem *= x;
 8     return tem;
 9 }
10 int main()
11 {
12     int z;
13     ll x,y;
14     int n;
15     //freopen("data.txt","r",stdin);
16     while(scanf("%d",&n), n)
17     {
18         int sum = 0;
19         int tem = sqrt(n * 1.0);
20         if(tem * tem == n) // 如果是完全平方，先计算
21         sum += (tem - 1) / 2;
22         for(z = 3; z < 31; z ++)
23         {
24             x = 1;
25             while(1)
26             {
27                 ll temp = pows(x,z);
28                 if(temp / 2 >= n) break;  // 加判断
29                 y = x + 1;
30                 while(1)
31                 {
32                     ll kemp = pows(y,z);
33                     if(temp + kemp + x * y * z > n) break;  // 判断
34                     else if(temp + kemp + x * y * z == n) sum++;  // 其实这里也可以加个判断，因为一旦找到了，肯定不用往后面枚举 y 了
35                     y++;
36                 }
37                 x++;
38             }
39         }
40         printf("%d\n",sum);
41     }
42     return 0;
43 }

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4287

题意：给出手机键上的字母，按下一串数字，然后给出一些单词，问没一个数字串命中的单词个数有几个

简单的计算，把每个手机键上的字母当成权值一样，然后计算每个字符串的权值，与上面给的数字串去匹配

View Code

 1 typedef long long ll;
 2 const int N = 5010;
 3 int num[N];
 4 int sum[1000000];
 5 int a[26] = {2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9};
 6 int main()
 7 {
 8     int n,m;
 9     int t,i,j;
10     char str[10];
11     //freopen("data.txt","r",stdin);
12     scanf("%d",&t);
13     while(t--)
14     {
15         scanf("%d%d",&n,&m);
16         for(i = 0; i < n;i++)
17         scanf("%d",&num[i]);
18         _clr(sum,0);
19         for(i = 0; i < m; i++)
20         {
21             int tsum = 0;
22             cin>>str;
23             int len = strlen(str);
24             for(j = 0; j < len; j++)
25             //for(i = 0; i < len; i++)
26             {
27                 tsum = tsum * 10 + (a[str[j] - 'a']);
28             }
29             sum[tsum] ++;
30         }
31         for(i = 0; i < n; i++)
32         printf("%d\n",sum[num[i]]);
33     }
34     return 0;
35 }