codeforces 451C. Predict Outcome of the Game 解题报告

题目链接：http://codeforces.com/problemset/problem/451/C

题目意思：有3支球队（假设编号为1、2、3），总共要打 n 场比赛，已知已经错过这n场比赛中的 k 场，但从 k 场比赛中可以获取一些信息：设w1表示 k 场比赛中编号为1的球队赢了w1场比赛（w2、w3 类似），绝对值 |w1-w2| = d1， |w2-w3| = d2，问能否通过设置n-k 的赛果来使得n场比赛都打完后，编号为1的球队的胜利次数 == 编号为2的球队的胜利次数 == 编号为3的球队的胜利次数。注意：每场比赛的赛果只有胜和输之分，没有平局。

初时看到这道题目，完全没有思路，当看了Tutorial 之后（不过没仔细看他的solution），就大概知道怎么做了，贡献了两个wa......

首先对于n，如果不能被 3 整除，那就肯定怎么分配剩下的 n-k 场赛果都于事无补的了，因为最终编号为1的球队的胜利次数 == 编号为2的球队的胜利次数 == 编号为3的球队的胜利次数 == n / 3 嘛

　　其次，要得出一条隐含的方程（关键所在）： w1 + w2 + w3 = k！ (1)

然后结合 |w1-w2| = d1 (2)， |w2-w3| = d2 (3) 来得出w1、 w2、 w3的值。（绝对值可以通过w1，w2，w3的大小关系来去掉，有四种情况）

（1）w1 >= w2，w2 >= w3 （2）w1 >= w2，w2 < w3

——> w1 = (2d1 + d2 + k) / 3　　　　　　　　　　　　　　——> w1 = (2d1 - d2 + k) / 3

w2 = (-d1 + d2 + k) / 3　　　　　　　　　　　　　　　　　 w2 = (-d1 - d2 + k) / 3

w3 = (-d1 - 2d2 + k) / 3　　　　　　　　　　　　　　　　　 w3 = (-d1 + 2d2 + k) / 3

（3）w1 < w2，w2 >= w3 （4）w1 < w2，w2 < w3

——> w1 = (-2d1 + d2 + k) / 3　　　　　　　　　　　　 ——> w1 = (-2d1 - d2 + k) / 3

　　　 w2 = ( d1 + d2 + k ) / 3　　　　　　　　　　　　　　　　 w2 = ( d1 - d2 + k ) / 3

　　　 w3 = ( d1 - 2d2 + k) / 3　　　　　　　　　　　　　　　　 w3 = ( d1 + 2d2 + k) / 3

可以知道，x1与x2的大小关系只会影响 d1 的符号，x2与x3的大小关系只会影响 d2 的符号。

那么可以枚举d1与d2的符号（当然不可能是0啦），算出相应的x1, x2, x3 的大小，看看每个xi (1 <= i <= 3 ) 是否满足 0 <= xi <= n/3 (前提是n%3 == 0！下界0一定要加上，因为算出来有可能是负数啊)，还有一点就是，由于涉及除法，4 / 3 == 1 这些情况要考虑到，一个可以避免的方法是，计算的时候，分子要判断是否能被3整除，不能就continue 咯。

总的来说，这题是纯数学题！

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;

 __int64 n, k, d1, d2;

 int main()

 {

     int t;

     while (scanf("%d", &t) != EOF)

     {

         while (t--)

         {

             scanf("%I64d%I64d%I64d%I64d", &n, &k, &d1, &d2);

             if (n % )

                 printf("no\n");

             else

             {

                 int flag = ;

                 for (int s1 = -; s1 <=  && !flag; s1++)  // 控制d1的正负号

                 {

                     for (int s2 = -; s2 <=  && !flag; s2++)  // 控制d2的正负号

                     {

                         if (s1 ==  || s2 == )

                             continue;

                         __int64 w1, w2, w3;

                         __int64 f1, f2, f3;  // w1, w2, w3的分子

                         f1 = (*(s1)*d1 + (s2)*d2 + k);

                         if (f1 % )

                             continue;

                         w1 = f1 / ;

                         f2 = ((-)*(s1)*d1 + (s2)*d2 + k);

                         if (f2 % )

                             continue;

                         w2 = f2 / ;

                         f3 = ((-)*(s1)*d1 + *(-)*(s2)*d2 + k);

                         if (f3 % )

                             continue;

                         w3 = f3 / ;

                         if (w1 + w2 + w3 == k && w1 >=  && w1 <= n/ && w2 >=  && w2 <= n/ && w3 >=  && w3 <= n/)

                         {

                             flag = ;

                             break;

                         }

                     }

                 }

                 printf("%s\n", flag ? "yes" : "no");

             }

         }

     }

     return ;

 }

巴特西

codeforces 451C. Predict Outcome of the Game 解题报告

最新文章

热门文章