首页 > 试题广场 > 看花
[编程题]看花

小明有一个花园,花园里面一共有m朵花,对于每一朵花,都是不一样的,小明用1m中的一个整数表示每一朵花。

他很喜欢去看这些花,有一天他看了n次,并将n次他看花的种类是什么按照时间顺序记录下来。

记录用a[i]表示,表示第i次他看了a[i]这朵花。

小红很好奇,她有Q个问题,[l,r]的时间内,小明一共看了多少朵不同的花儿,小明因为在忙着欣赏他的花儿,所以想请你帮他回答这些问题。


输入描述:
输入两个数n,m;(1<=n<=2000,1<=m<=100);分别表示n次看花,m表示一共有m朵花儿。

接下来输入n个数a[1]~a[n],a[i]表示第i次,小明看的花的种类;

输入一个数Q(1<=Q<=1000000);表示小红的问题数量。

输入Q行 每行两个数l,r(1<=l<=r<=n);表示小红想知道在第l次到第r次,小明一共看了多少不同的花儿。


输出描述:
一共Q行

每一行输出一个数 表示小明在[l,r]的时间内看了多少种花。
示例1

输入

5 3
1 2 3 2 2
3
1 4
2 4
1 5

输出

3
2
3
用cin通不过的代码,用scanf通过了
#include <iostream> #include <set> #include <vector> #include <unordered_set> using namespace std; int main(){     int m,n;     while(cin >> n >> m){         vector<int> a(n);         for(int i = 0; i < n; ++i){             scanf("%d" , &a[i]);         }         vector<vector<int>> ans(n, vector<int>(n, 1)); // ans[i][j] 表示从时间[i + 1, j + 1]看了几种花,其中i <= j;         for(int i = 0; i < n; ++i){             unordered_set<int> set_a;             set_a.insert(a[i]);             for(int j = i; j < n; ++j){                 set_a.insert(a[j]);                 ans[i][j] = set_a.size();             }         }         int Q;         cin >> Q;         while(Q--){             int l, r;             scanf("%d %d" , &l, &r);             //printf("%d\n",ans[l - 1][r - 1]);             //cin >> l >> r;             cout << ans[l - 1][r - 1] << endl;         }     }     return 0; }

编辑于 2019-07-31 15:41:03 回复(3)

本题经典问题是查询区间不同数量,简单做法是树状数组求法 (还有主席树做法

先对询问进行离线。 然后按照右端点从小到大排序。

  1. 树状数组统计答案,对于第一次出现直接加1
  2. 第二次出现,先减去上一次的影响,在加1
然后枚举右端点,有询问的话,拿出左端点放到树状数组进行查询
整体复杂度 O(n*logn)

显然数据范围可以开到 n, k 可以开到 1e6,不然暴力预处理就过了

#include
using namespace std;
const int N = 1e6 + 5;
int a[N];
struct Bit {
    int c[N];
    int n;
    void init() { memset(c, 0, sizeof(c)); }
    int lowbits(int x) { return x & -x;}
    void add(int i, int v) {
        for(; i <= n; i += lowbits(i)) c[i] += v;
    }
    int get(int i) {
        int ans = 0;
        if(i <= 0) return 0;
        for(; i > 0; i -= lowbits(i)) ans += c[i];
        return ans;
    }
}B;
struct node {
    int l, r, id;
    bool friend operator < (node a, node b) {
        return a.r < b.r;
    }
}b[N];
int id[N], ans[N];
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("a.txt", "r", stdin);
    #endif // ONLINE_JUDGE
    int n, m, k;
    scanf("%d %d", &n, &k);
    B.init();
    B.n = n;
    memset(id, -1, sizeof(id));
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    scanf("%d", &m);
    for(int i = 1; i <= m; i++) {
        int l, r;
        scanf("%d %d", &l, &r);
        b[i] = {l, r, i};
    }
    sort(b + 1, b + m + 1);
    int j = 1, sum = 0;
    for(int i = 1; i <= n; i++) {
        if(id[a[i]] != -1) B.add(id[a[i]], -1), sum--;
        id[a[i]] = i; sum++;
        B.add(i, 1);
        while(j <= m && b[j].r == i) {
            int tmp = sum - B.get(b[j].l-1);
            ans[b[j].id] = tmp;
            j++;
        }
    }
    for(int i = 1; i <= m; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}
编辑于 2019-08-12 23:43:47 回复(2)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int []A = new int [n];
        int []B = new int [m];
        for(int i=0;i<n;i++){
            A[i] = sc.nextInt();
        }
        int Q = sc.nextInt();
        int [][]a = new int [Q][2];
        for(int i=0;i<Q;i++){
            a[i][0] = sc.nextInt();
            a[i][1] = sc.nextInt();
        }
        
        
        for(int i=0;i<Q;i++){
        	int t=0;
        	for(int j=a[i][0]-1;j<=a[i][1]-1;j++){
        		int dd = A[j];
                if(B[dd-1]!=i+1){
                    B[dd-1]=i+1;
                    t++;
                }
        		
        	}
        	System.out.println(t);
        	
        	}
  
        }
    }

发表于 2019-08-16 16:02:59 回复(1)
#include<iostream>
#include<vector>
usingnamespacestd;
  
intmain()
{
    intn,m;
    scanf("%d%d",&n,&m);
//    cin>>n>>m;  //看花次数,花的种类
      
    vector<int> a(n+1); //看花序列
    a[0]=0;
    for(intk=1;k<=n;k++)
    {
        intkind;
        scanf("%d",&kind);
        a[k]=kind;  //放入花的种类
    }
      
    intq;
    scanf("%d",&q);
  
    vector<int> flower;
    for(inti=0;i<=m;i++)
        flower.push_back(0);
      
    for(intc=0;c<q;c++)    //q次问询
    {
        intl,r;
        scanf("%d%d",&l,&r);
        intnum =0;
          
        for(intf=l;f<=r;f++)
        {
            if( flower[a[f]] == 0)
            {
               num++;
               flower[a[f]]=1;
            }
        }
         
        //将flower还原
        for(inte=1;e<=m;e++)
        {
            flower[e]=0;
        }
        cout<<num<<endl;
    }
    return0;
}
哈希表的思想,只通过了百分之86,剩下的超时了
发表于 2019-08-09 16:53:53 回复(2)
n,m=map(int,input().strip().split())
lt=list(map(int,input().strip().split()))
Q=int(input())
for i in range(Q):
    l,r=map(int,input().strip().split())
    print(len(set(lt[l-1:r])))
显示超时……只完成了86.67%的用例,求大佬来帮忙优化一下……我怀疑是set()函数复杂度超了但我并没有证据🤣
发表于 2019-08-05 22:06:34 回复(3)
//用深度优先搜索的简单解法,虽然超时了,但可以看看方法,代码如下。 
#include <stdio.h>						
int n,m,q,l,r;			//题目数据 
int t,total=0;		 
int a[2019];
int v[2019]={0};				//用来标记是否被访问过的数组 
void dfs(int l,int r){
	if(l==r){				//递归出口,当左等于右时跳出 ,此时在处理最后一个数 
		if(v[l]==0)						 
			printf("%d\n",total+1);	//最后一个数若未访问总数加一 
		else
			printf("%d\n",total);	//最后一个数若已访问总数不变 
			
		total=0;			//数据清零 ,准备处理下一组问题 
		for(int i=1;i<=n;i++)
		v[i]=0;
		return;
	}
	for(int k=l;k<=r;k++){			
		if(a[k]==a[l]&&v[k]==0){	//标记与第一个数字相等且未被访问过的数字 
			v[k]=1;						
			t=2;			//如果找到新的未被访问的数字的话让t=2
		}
	}
	if(t==2){				//如果t=2,说明找到新的数字,总数++,再把t初始化 
		total++;
		t=0;
	}
	dfs(l+1,r);				//向右寻找下一个 
}
int main(void){
	scanf("%d%d",&n,&m);			//输入m,n,a[i] 
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}								
	scanf("%d",&q);				//输入Q 
	for(int i=1;i<=q;i++){
		scanf("%d%d",&l,&r);		//输入l,r 
		dfs(l,r);			//搜索开始 
	}
	return 0;
}

发表于 2019-08-05 19:15:35 回复(0)
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] a = new int[n];
//		         读取看的次数的种类
		for(int i=0;i<n;i++) {
			a[i]= sc.nextInt(); 
		}
		int q = sc.nextInt();
		for(int i=0;i<q;i++) {
			int l = sc.nextInt();
			int r =sc.nextInt();
			System.out.println(test(l,r,a));

		}
	}
	public static int test(int l,int r,int[]a) {
		Set<Integer> temp = new HashSet<>();
		for(int i=l-1;i<r;i++) {
			temp.add(a[i]);
		}
		return temp.size();
	}
}
 
怎么才能100%啊?

编辑于 今天 11:39:03 回复(0)
import java.util.Scanner;

public class Flower {

	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		int n=0,m=0;
		n=scanner.nextInt();
		m=scanner.nextInt();
		int[] a=new int[n+1];
		int[] b=new int[m+1];
		
		for(int i=1;i<=n;i++) {
			a[i]=scanner.nextInt();	
		}
		int q=scanner.nextInt();
		int[] c=new int[q];
		for(int i=0;i<q;i++) {
			for(int k=0;k<m+1;k++) {
				b[k]=0;
			}
			int t=0;
			int l=scanner.nextInt();
			int r=scanner.nextInt();
			for(int j=l;j<=r;j++) {
				if(b[a[j]]!=1) {
				t++;
				b[a[j]]=1;
				}
			}
			c[i]=t;
		}
		for(int i=0;i<q;i++)
		{
			System.out.println(c[i]);
		}
	}

}

通过率86.67%

编辑于 2019-08-23 21:43:59 回复(0)
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    int a[n+1];
    a[0]=0;
    int b[105];
    int c[n+1][n+1];

    memset(c,0,sizeof(c));
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d",&a[i]);
    }
    for(int i = 1; i<= n; ++i)
    {
        memset(b,0,sizeof(b));
        for(int j = i; j <= n; ++j)
	{
	    b[a[j]]++;
            int num=0;
            int count=0;
            for(int k = 1; k <= 100; ++k)
	    {
		if(b[k]) 
		{
 		count+=b[k];
                num++;
                if(count==j-i+1) break;
		}
	    }
            c[i][j]=num;
	}
        
        //printf("%d ",num);
    }
    int Q;
    scanf("%d",&Q);
    while(Q--)
    {
        int x,y;
	scanf("%d %d",&x,&y);
        printf("%d\n",c[x][y]);
    }
    return 0;
}


发表于 2019-08-15 13:04:30 回复(0)
线段树有点大才小用了。
发表于 2019-08-12 20:24:23 回复(0)
case通过率为86.67% ,超时了,求大佬指点
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        boolean []check = new boolean[m];
        int[] arr = new int[n];
        for (int i = 0; i <n; i++) {
            arr[i] = scan.nextInt();
        }
        int q = scan.nextInt();
        for (int i = 0; i <q; i++) {
            initCheck(check);
            int l = scan.nextInt();
            int r = scan.nextInt();
            int count = 0;
            for(int j=l-1;j<r;j++){
                if(!check[arr[j]-1]){
                    check[arr[j]-1]=true;
                    count++;
                }
            }
            System.out.println(count);
        }
    }
    public static void initCheck(boolean []check){
        for(int i=0;i<check.length;i++)
            check[i]=false;
    }
}


编辑于 2019-08-12 10:32:26 回复(0)
通过率:86.66% ,超时
求指点
public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] a = new int[n+1];
        int count = 0;
        Set<Integer> set = new HashSet<>();
        while (++count <= n) {
            a[count] = sc.nextInt();
        }
        int Q = sc.nextInt();
        while (Q-- > 0) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            for (int i = l; i <= r; i++) {
                set.add(a[i]);
            }
            System.out.println(set.size());
            set.clear();
        }
    }


发表于 2019-08-09 22:23:46 回复(0)
数组越界,通过53.55%求解答
import java.util.Arrays;
import java.util.Scanner;

/**
 * created by LMR on 2019/8/7
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int a[] = new int[n];

        int mem[][][] = new int[n][n][m];
        for (int i = 0; i < n; i++)
        {
            a[i] = sc.nextInt();
            mem[0][n - 1][a[i] - 1]++;
        }
        for (int i = n - 1; i >= 0; i--)
            for (int j = 0; j < i; j++){
                if (j != 0){
                    mem[j][i] = Arrays.copyOf(mem[j - 1][i], m);
                    mem[j][i][a[j - 1] - 1]--;
                }else {
                    if (i != n - 1){
                        mem[j][i] = Arrays.copyOf(mem[j][i + 1], m);
                        mem[j][i][a[i + 1] - 1]--;
                    }
                }
            }

        int q = sc.nextInt();
        int i = 0;
        while (i < q){
            int l =sc.nextInt();
            int r = sc.nextInt();
            if (l == r)
                System.out.println(1);
            else {
                int temp[] = mem[l-1][r-1];
                int result = 0;
                for (int k : temp)
                    if (k != 0)
                        result++;
                System.out.println(result);
            }

            i++;
        }
    }
}


发表于 2019-08-09 00:20:38 回复(0)
# 通过87%  最后超内存了  之前的思路是遍历一遍,用dict 保存当前为止出现过得花以及对应的次数
# 超时; 现在是2维遍历,维护一个二维矩阵,表示i到j的种类数,也只通过了87%
import sys
lines = sys.stdin.readlines()
n,m = [int(n) for n in lines[0].strip().split()]
c = [int(n) for n in lines[1].strip().split()]
qNum = int(lines[2].strip())
q = []
for i in range(3,len(lines)):
    q.append([int(m) for m in lines[i].strip().split()])

res = [[0 for i in range(n)] for j in range(n)]
for i in range(len(c)):
    s = set()
    for j in range(i,n):
        s.add(c[j])
        res[i][j] = len(s)

for quary in q:
    l,r = quary[0],quary[1]
    print(res[l-1][r-1])

编辑于 2019-08-05 17:02:09 回复(0)