程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [ACM] ZOJ 3844 Easy Task (模擬+哈希)

[ACM] ZOJ 3844 Easy Task (模擬+哈希)

編輯:C++入門知識

[ACM] ZOJ 3844 Easy Task (模擬+哈希)


Easy Task

Time Limit: 2 Seconds Memory Limit: 65536 KB

You are given n integers. Your task is very easy. You should find the maximum integer a and the minimum integer b among these n integers. And then you should replace both a and bwith a-b. Your task will not be finished unless all the integers are equal.

Now the problem come, you want to know whether you can finish you task. And if you can finish the task, you want to know the final result.

Input

The first line of the input contain an integer T(T≤ 20) indicates the number of test cases.

Then T cases come. Each case consists of two lines. The first line is an integer n(2≤ n≤ 10) as the problem described. The second line contains n integers, all of them are no less than -100000 and no more than 100000.

Output

For each case you should print one line. If you can finish your task, you should print one of the n integers. Otherwise, you should print "Nooooooo!"(without quotes).

Sample Input

2
3
1 2 3
2
5 5

Sample Output

2
5

Author: CHEN, Zemin
Source: ZOJ Monthly, January 2015

解題思路:

題意為給定n個數(2<=n<=10),每個數的范圍為 -100000到100000,有一種操作:找到這n個數中最大的數max,最小的數min,把這兩個數都替換為 max-min , 重復這樣的操作,直到這n個數完全相同,如果可以達到這樣的目的,就輸出最後那n個數中的其中一個(每個數都一樣),如果不能,則輸出 Nooooooo!。

n的范圍很小,直接按照題意排序模擬即可,一開始覺得任何數據都可以達到目的,沒有輸出Nooooooo!的情況,寫了一發,交上去,果斷WA.後來和二師兄討論,應該記錄狀態才對,一旦出現相同的狀態,那麼就不能達到目的,輸出Nooooooo!。方法為哈希查找,每一個狀態用包含這n個數的結構體來保存,關鍵字是這n個數的和,以n個數的和對一個大素取余作為關鍵字,10個數的最大和不超過100000*10,所以開辟這麼大的結構體類型的vector數組,當出現一個新的狀態時,就去該狀態的和取余後的索引中的那些狀態去比較,這樣可以減少比較次數,因為一個狀態和另一個狀態相同,它們分別的元素之和取余後相等是大前提。

注意:n個元素和可能是負數,建立索引要加上mod變為正數.

代碼:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define ll long long
const int mod=100000*10+1;
const int inf=0x3f3f3f3f;
const int maxn=12;
int num[maxn];
int n;
struct Node
{
    int a[maxn];
};
vectorvc[mod+10];

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        for(int i=0;i<=mod;i++)
            vc[i].clear();
        Node tp;
        cin>>n;
        int sum=0;
        for(int i=0;i>num[i];
            sum+=num[i];
        }
        tp.a[n]=sum;
        sort(num,num+n);
        if(num[0]==num[n-1])
        {
            cout<


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved