-7

昨天，我们不得不在 codeforces 比赛中解决问题，因为我是一个初学者，所以我无法解决这个问题。

http://codeforces.com/contest/353/problem/A

我使用了这个算法，但它有问题。我认为它应该打印 s 或 f，但它什么也不打印。它只是自动关闭。即使我添加了一个输入来停止即时关闭

#include <cstdlib>
#include <iostream>

using namespace std;

    int main(){
    int y=0;
    int x=0;
    int f;
    int a;
    cin >> a;
    int s;
    s = 0;
    int number [a][a];
    for(int i = 0;i<a;i++){                
        cin >> number[i][0] >> number[i][1];
        x += number[i][0];
        y += number[i][1];
    }

    for(int i = 0;i<a;i++){
        if(x%2==0 && y%2==0){
            return s;             
        }else if(y%2!=0 && x%2==0){
            f = -1;
            return f;
        }else if(y%2==0 && x%2!=0){
            f = -1;
            return f;
        }else{
            y+= number[i][0];
            x+= number[i][1];
            s++;  
        }  
    }

    int g;
    if(f!=-1){
        cout << s;
    }else{
       cout << f;
    }  
}
4

2 回答 2

1

正如 Angew 所说，return 语句不正确，导致您退出 main。你想用休息来代替它；退出循环但不退出函数。

于 2013-10-11T13:36:06.023 回答
0

我没有花精力试图理解你的算法，但乍一看它看起来比它应该的复杂。

根据我对问题的理解，有3种可能：

  • 上半部分和下半部分的总和已经是偶数（所以什么都不需要做）
  • 上半部分和下半部分的总和不能相等（因此不存在解决方案）
  • 只需旋转一个 Domino 即可使上半部分和下半部分的总数相等（因此所需时间为 1 秒）

我基于这样一个事实，即仅添加偶数总是给出偶数结果，并且添加偶数个奇数也总是给出偶数结果。

基于此，我将维护 2 个不同的数组，而不是像您的代码中那样使用二维数组 - 一个用于上半部分数字，另一个用于下半部分数字。此外，我会编写以下两个辅助函数：

  1. oddNumCount - 将数组作为输入；只返回数组中奇数的个数。
  2. oddAndEvenTileExists - 将 2 个数组作为输入；返回具有奇数+偶数组合的第一个图块的索引，如果不存在这样的图块，则返回-1。

那么我的算法的核心是：

if (((oddNumCount(upper_half_array) % 2) == 0) && ((oddNumCount(lower_half_array) % 2) == 0))
{
    // nothing needs to be done

    result = 0;
}
else if (((oddNumCount(upper_half_array) - oddNumCount(lower_half_array)) % 2) == 0)
{
    // The difference between the number of odd numbers in the two halves is even, which means a solution may exist.
    // A solution really exists only if there exists a tile in which one number is even and the other is odd.

    result = (oddAndEvenTileExists(upper_half_array, lower_half_array) >= 0) ? 1 : -1;
}
else
{
    // no solution exists.

    result = -1;
}

如果您想准确指出需要旋转的图块，则可以保存“oddAndEvenTileExists”函数返回的索引。

您可以自己编写实际代码来测试它是否有效。即使没有，您也会编写一些代码，希望能让您略高于“完全初学者”。

于 2013-10-11T14:48:48.090 回答