首页 > 试题广场 >

射击训练

[编程题]射击训练

热度指数：1544 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小Q 是一个专业的射击运动员，有一天他像往常一样进行 n 次射击训练，每次射击他都会取最高的四次得分作为最终得分来衡量他的射击状态，但是今天他制定了一个奇怪的规则：在 n 次射击得分中取出四次得分 a,b,c,d ，并且满足 a*b*c=d 作为最终得分来衡量他的射击状态。

但是小Q 发现满足这个条件的 (a,b,c,d) 可能不止一个，小Q 需要你来帮助他计算一共有多少个这种 (a,b,c,d)

数据范围： $4 \le n \le 500 \$ ，输入的所有得分满足 $1 \le w_i \le 1000 \$

输入描述:

输入包括两行，第一行包括一个正整数n，表示射击的次数。

第二行n个正整数，表示每次射击的得分。

输出描述:

输出可以作为最终得分的种数。

示例1

输入

6
10 2 2 7 40 160

输出

说明

有两种满足条件的(a,b,c,d)分别是(10,2,2,40)和(2,2,40,160)。

算法知识视频讲解

小新少郎

//我个人认为此代码不正确，第一点，比如说我测试1 1 1 2这四位数正确输出应该为0,但是输出却为4
//第二点，help这个记录的仅仅是出现过的的数，这个出现的数有可能在a,b,c已经出现过啦，d就不能出现
//我的代码在下面

#include<iostream>
(720)#include<algorithm>
using namespace std;
const int N=505;
const int WJ=1e6+5;
int main()
{
    int n;
    int arr[N];
    int help[WJ]={0};
    int i,j,k,m;
    cin>>n;
    for(i=0;i<n;i++) cin>>arr[i];
    sort(arr,arr+n);
    for(i=0;i<n;i++) help[arr[i]]=1; 
    int ans=0;
    for(i=0;i<n-2;i++)
    {
        for(j=i+1;j<n-1;j++)
        {
            for(k=j+1;k<n;k++)
            {
                    
                    if(arr[i]*arr[j]*arr[k]>arr[n-1]) break;
                    if(help[arr[i]*arr[j]*arr[k]]==1) ans++;
            }
        }
    }
    cout<<ans;
    return 0;
}

/*下面是我自己的代码，时间复杂度可能有点高，毕竟嵌套了四层循环

#include<iostream>
(720)#include<algorithm>
using namespace std;
const int N=505;
int main()
{
    int n;
    int arr[N];
    int i,j,k,m;
    int a,b,c,d;
    cin>>n;
    for(i=0;i<n;i++) cin>>arr[i];
    sort(arr,arr+n);
    int ans=0;
    for(i=0;i<n-3;i++)
    {
        a=arr[i];
        for(j=i+1;j<n-2;j++)
        {
            b=arr[j];
            for(k=j+1;k<n-1;k++)
            {
                c=arr[k];
                for(m=k+1;m<n;m++)
                {
                    d=arr[m];
                    if(a*b*c==d) ans++;
                    if(a*b*c>d) break;
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

发表于 2020-04-12 18:12:05 回复(0)

炊烟晚霞

（a,b,c,d）可重复吗，这都没说清楚

发表于 2020-07-30 02:15:58 回复(0)

无心2019

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,w[501],res=0,vim[1000005];
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>w[i];
        vim[w[i]]=1;
    }
    sort(w,w+n);
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            for(int k=j+1;k<n;k++)
            {
                int m=w[i]*w[j]*w[k];
                if(m>w[n-1])
                    break;
                else if(vim[m]==1)
                    res++;
            }
        }
    }
    cout<<res<<endl;
    return 0;
}

发表于 2019-06-26 20:43:37 回复(0)

嘟嘟6668

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        while(scan.hasNext()){
            int n=Integer.valueOf(scan.nextLine());
            int[]data=new int[n];
            String s=scan.nextLine();
            String[]strs=s.split(" ");
            for(int i=0;i<n;i++){
                data[i]=Integer.valueOf(strs[i]);
            }
            System.out.println(get(n,data));
        }
    }
    public static int get(int n,int[]data){
        int count=0;
        long tem=0;
        Arrays.sort(data);
        int[]help=new int[1000005];
        for(int i=0;i<n;i++){
            help[data[i]]=1;
        }
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                for(int k=j+1;k<n;k++){
                    tem=data[i]*data[j]*data[k];
                    if(tem>1000005){
                        break;
                    }
                    else {
                        int temh=(int)tem;
                        if(help[temh]==1){
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }
}

发表于 2019-06-13 16:38:56 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    int a[n], m=0, cnt=0;
    bool mp[100001] = {false};
    for(int i=0;i<n;i++){
        scanf("%d", &a[i]);
        mp[a[i]] = true;
    }
    sort(a, a+n);
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            for(int k=j+1;k<n;k++){
                m = a[i]*a[j]*a[k];
                if(m>a[n-1])
                    break;
                else if(mp[m])
                    cnt++;
            }
        }
    }
    printf("%d\n", cnt);
    return 0;
}

发表于 2020-09-22 19:48:20 回复(0)

Python 3

牛客645538045号

Test cases are incorrect, no zero elements are allowed.

I have tested some datas and are proved to be "correct".

import sys
number = eval(input())
num_list = []
lst = input()
for i in lst.split():
    num_list.append(eval(i))
    
num_list.sort()
def fullfill(a, b, c, d) :
    if (a==b):
        return fullfill(a, b+1, c, d)
    if (b==c):
        return fullfill(a, b, c+1, d)
    if (c==d):
        return fullfill(a, b, c, d+1)
    if d>=number:
        return 0
    product = num_list[a]*num_list[b]*num_list[c]
    if product < num_list[d]:
        return fullfill(a, b, c, d+1)
    else:
        return (product == num_list[d]) + max(fullfill(a, b+1, c, d), fullfill(a, b, c+1, d), fullfill(a+1, b, c, d))

print(fullfill(0, 1, 2, 3))

This code used a sorting function, which costs O(nlogn) time, simply moving the window should give O(n) amount of time. Therefore, the overall runtime should be O(nlogn)

发表于 2022-03-23 03:01:14 回复(0)

huixuphys

感觉这题有很大的问题。题目中说得分是正整数，而测试用例中却可以是0。而且题目中也没有说明(a, b, c, d)数值上相同的不同射击结果可不可以重复计算。我写的代码中重复计算了不同轮次的a, b, c而d只计算一次，并且判定d的时候还可以从a, b, c中取值，这样最后竟然可以通过，这意味着正确的代码反而通不过。

发表于 2020-08-29 10:51:01 回复(0)

喵汪喵汪喵喵喵

谁能告诉我错在何处？

import java.io.BufferedReader;

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
      String str = bf.readLine();
      String s= bf.readLine();
      int n=Integer.parseInt(str),res=0;
      String[] t=s.split(" ");
      int[] a=new int[n];
      for(int i=0;i<n;i++)
      {
          a[i]=Integer.parseInt(t[i]);
      }
      Arrays.sort(a);
      for(int i=0;i<n-3;i++)
      {
          for(int j=i+1;j<n-2;j++)
          {
              for(int k=j+1;k<n-1;k++)
              {
                  for(int l=k+1;l<n;l++)
                  {
                      if(a[l]==a[i]*a[j]*a[k])
                      {
                          res++;
                      }
                  }
              }
          }
      }
      System.out.println(res);
    }
}

发表于 2020-06-11 23:15:34 回复(1)