编程之美2013全国挑战赛------资格赛-----题解？？

该用户从未签到

30 主题	127 好友	2万积分

技术宅认证程序员

重度中二患者

积分: 28325

发表于 2013-4-9 01:26:54 | 显示全部楼层 |阅读模式

╱人◕‿‿◕人╲定下契约

您需要登录才可以下载或查看，没有账号？╱人◕‿‿◕人╲订下契约（注册新用户）

本帖最后由 foodszhu 于 2013-4-9 01:36 编辑

好吧。。。重开一贴有水贴的嫌疑。。。不过作为赛后的发布一下题解还是很有必要的。。。。
但是个人来说。。。虽然小数据都水过了。。。。但无情的大数据只过了第一题orz。。。。。

排名排到400+ 。@Whisper1166 （ W君看了一下跟我一样。。。第一题过了。。第二题WA第三题RE，排名靠的相当近。。。。）
所以在这里也不敢说发什么解题报告。。。毕竟自己还没有做出来。。。但是为了照顾一下刚接触编程的同学。。。。咱们就把问题简单化吧。。。。

这里也非常欢迎大家把自己的AC代码贴出来，尤其是过了大数据的代码。。。如果有空还可以讲解一下最好。。。W君不要吝啬糖哦。。。

题目链接：https://www.gn00.com/t-268811-1-1.html 我也就不再打题目了。。。

---------------------------------------------------------------------------------------------------------------------------------------------
第一题：传话游戏

[mw_shl_code=c,true]#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
int T;
scanf("%d", &T);
int A = T;
while(T > 0){
      T--;
      int N,M;
      scanf("%d%d", &N, &M);
      char change[100][2][100] = {{{0}}};
      for(int i = 0; i < M; i++){
         scanf("%s%s", change[0], change[1]);
      }
      char think[100] = {0}, pass[100][100] = {{0}};
      scanf("\n%[^\n]", think);
      int l1 = 0, l2 = 0;
      for(int i = 0; i < strlen(think); i++){
         if(think != ' '){
            pass[l1][l2++] = think;
         } else {
            l1++;
            l2 = 0;
         }
      }
      l1++;
      for(int i = 0; i < N - 1; i++){
         for(int k = 0; k < l1; k++){
            int t = 0;
            for(int j = 0; j < M; j++){
                  if(t == 0 && strcmp(pass[k], change[j][0]) == 0){
                     strcpy(pass[k], change[j][1]);
                     t = 1;
                  }
            }
         }
      }
      printf("Case #%d:", A - T);
      for(int i = 0; i < l1; i++){
         printf(" %s", pass);
      }
      printf("\n");
}
}[/mw_shl_code]
代码虽然是C风格。。。但是只能交C++，因为大赛编译器不支持c99.。。orz。。。。
三道之中最水一题。。。考究会不会读取字串并分割。。。然后就是替换字串的问题。。。
读取一行含空格的字符串时得用gets或者scanf("\n%[^\n]")，gets前必须加getchar否则不会读入也会导致错误。。。
剩下似乎没什么了。。。注意下一个单词不能在一个人那里来回变(就是要break出来。。。），还有n个游戏者，但是只变n-1次就好了。。。数组稍微开大点。。。就可以过大数据了。。。。

-------------------------------------------------------------------------------------------------------------------------------------------------------
第二题：长方形
[mw_shl_code=applescript,true]#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main(){
int T;
scanf("%d", &T);
for(int t = 0; t < T; t++){
      int N,M,K;
      scanf("%d%d%d", &N, &M, &K);
      if(N > M){
         int tmp = N;
         N = M;
         M = tmp;
      }
      int maxN = 0;
      for(int min = 1, max = 0; min <= N; min++){
         max = K / min;
         if(max > M){
            max = M;
         }
         int remain = K - min * max,  num = min * max * (min - 1) * (max - 1) / 4;
         remain -= remain / min * min;
         if(remain > 1){
            if(max < M){
                  num += max * (remain - 1) * remain / 2;
            } else if(min < N){
                  num += min * (remain - 1) * remain / 2;
            }
         }
         if(num > maxN){
            maxN = num;
         }
      }
      printf("Case #%d: %d\n", t + 1, maxN);
}
}[/mw_shl_code]
好吧。。。。这题我是暴力穷举过得。。。。有种淡淡的无奈啊。。。结果看起来穷举都是错的。。。最后大数据WA了。。。不清楚为什么。。。
用了一个简单的公式。。。一个N*Ｍ的网格中最多有Ｎ*Ｍ*(N-1)(M-1) / 4个长方形(证明也很简单，就是乘法原理，横着的边数 * 纵列的边数 = （1 + 2 + 3+.....N) * (1 + 2 + 3......M))
剩下的石子数目肯定少于min（Ｎ，Ｍ），然后在一个个的铺到较长的那个边上。。。再计算。。。把可能的大矩阵遍历一遍。。。就可以得到最大值了。。。

至于大数据哪里错了还真不知道。。。可能这样子做出来并不一定是最优的也有可能。。。。希望有过大数据的出来讲一下。。。

--------------------------------------------------------------------------------------------------------------------------------------------------------

第三题：树上的三角形
[mw_shl_code=c,true]#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int map[200][200] = {{0}}, path[200][200] = {{0}}, dist[200][200] = {{0}}, N = 0;

int floyd(){
for(int i = 0; i < N; i++){
      for(int j = 0; j < N; j++){
         dist[j] = map[j];
         if(map[j] > 10000){
            path[j] = -1;
         } else {
            path[j] = i;
         }
      }
}
for(int k = 0; k < N; k++){
      for(int i = 0; i < N; i++){
         for(int j = 0; j < N; j++){
            if(dist[k] + dist[k][j] < dist[j]){
                  dist[j] = dist[k] + dist[k][j];
                  path[j] = path[k][j];
            }
         }
      }
}
}
int main(){
int T;
scanf("%d", &T);
for(int t = 0; t < T; t++){
      scanf("%d", &N);
      for(int i = 0; i < 200; i++){
         for(int j = 0; j < 200; j++){
            map[j] = 20000001;
         }
      }
      memset(dist, 0, sizeof(dist));
      memset(path, 0, sizeof(path));
      for(int i = 0; i < N - 1; i++){
         int a, b, len = 0;
         scanf("%d%d%d", &a, &b, &len);
         map[a - 1][b - 1] = len;
         map[b - 1][a - 1] = len;
      }
      floyd();
      printf("Case #%d:\n", t + 1);
      int M = 0;
      scanf("%d", &M);
      for(int i = 0; i < M; i++){
         int S, F, len[1000] = {0}, l = 0;
         scanf("%d%d", &S, &F);
         S--, F-- ;
         if(S == F || path[S][F] == -1){
            printf("No\n");
            continue;
         }
         while(S != F){
            int end = F;
            F = path[S][F];
            len[l++] = map[F][end];
         }
         for(int x = 0; x < l; x++){
            for(int y = x + 1; y < l; y++){
                  if(len[x] > len[y]){
                     int asd = len[x];
                     len[x] = len[y];
                     len[y] = asd;
                  }
            }
         }
         int result = 0;
         for(int k = 1; k < l - 1; k++){
            if(len[k - 1] + len[k] > len[k + 1]){
                  result = 1;
                  break;
            }
         }
         if(result == 0){
            printf("No\n");
         } else {
            printf("Yes\n");
         }
      }
}
}[/mw_shl_code]

也是某些意义上的暴力过。。。用floyd先求出最短路径，再将最短路径上的树枝长度排序，再判断是否构成三角形。。。。
大数据错的也很明显。。。我数组就开了那么大。。。。肯定ＲＥ。。。。

-------------------------------------------------------------------------------------------------------------------------------------
经过这次资格赛发现微软还是很细腻的做了很多工作。。。作为资格赛，题目难度相当于学过Ｃ语言课就差不多能过第一题，
一个认真听过算法课的计算机学生就可以答完所有小数据，搞过ＡＣＭ的应该就可以水过大数据的的样子。。。。
作为一名正在学算法课的学生表示压力山大。。。估计到初赛就一道题都答不上了。。。或许向班里大神要要代码不错。。。。

@Whisper1166 不过初赛可能看样子在版里搞不起来了吧。。。毕竟有时间限制两个小时还是很紧张。。。讨论做不起来的话难道初赛完直接在网上找找题解？。。。。

评分

参与人数 1	宅币 +40	贡献 +3	收起理由
_Nozomi	+ 40	+ 3	o(￣▽￣)ブ发糖

查看全部评分

等死星人

合作站点账号登陆

编程之美2013全国挑战赛------资格赛-----题解？？

╱人◕‿‿◕人╲定下契约

评分