精华内容
下载资源
问答
  • 给定含有n个整数的序列,要求这个序列进行去重操作。所谓去重,是指这个序列中每个重复出现的数,只保留该数第一次出现的位置,删除其余位置。 【输入】 输入包含两行: 第一行包含一个正整数n(1 \le n \le ...

    1117:整数去重

    【题目描述】

    给定含有n个整数的序列,要求对这个序列进行去重操作。所谓去重,是指对这个序列中每个重复出现的数,只保留该数第一次出现的位置,删除其余位置。

    【输入】

    输入包含两行:

    第一行包含一个正整数n(1 \le n \le 20000)$,表示第二行序列中数字的个数;

    第二行包含nn个整数,整数之间以一个空格分开。每个整数大于等于1010、小于等于50005000

    【输出】

    输出只有一行,按照输入的顺序输出其中不重复的数字,整数之间用一个空格分开。

    【输入样例】

    5
    10 12 93 12 75

    【输出样例】

    10 12 93 75

    代码

    /***************************************************
    
    date:4.1
    
    I 数的个数 几个用于判断的数字 
    
    O 操作好无重复的数字 
    
    P 用数组存数字,如果这个数字下标已经为1 就跳过 
    
    ***************************************************/
    
    #include<bits/stdc++.h>
    using namespace std;
    int n;
    int a[20000];
    int main(){
    	scanf("%d",&n);
    	int x;
    	for(int i=1;i<=n;++i){
    		scanf("%d",&x);
    		if(a[x]==1){
    			continue;
    		}else{
    			a[x]=1;
    			printf("%d ",x); 
    		}
    	}
    	return 0;
    }
    
    

    后记

    谢谢大家的关注
    若有任何问题请发邮件至learning.dlq@gmail.com

    展开全文
  • 含有 n个整数的序列a1,a2......an中, 三个数被称作"thair"当且仅当iai 求一个序列中"thair"的个数。 Input 开始一个正整数n, 以后n个数a1~an。 30%的数据n 60%的数据n 100%的数据n 0 Output ...

    Description

    daming最近对一种叫"thair"的东西巨感兴趣。。。

    在含有 n个整数的序列a1,a2......an中,

    三个数被称作"thair"当且仅当i<j<k且ai<aj<ak

    求一个序列中"thair"的个数。

    Input

    开始一个正整数n,

    以后n个数a1~an

    30%的数据n<=100

    60%的数据n<=2000

    100%的数据n<=30000

    0<=a[i]<=maxlongint

    Output

    "thair"的个数

    Sample Input

    Input I
    4
    2 1 3 4
    Input II
    5
    1 2 2 3 4

    Sample Output

    Output I
    2
    Output II
    7

    HINT

    对样例2的说明:

    7个"thair"分别是

    1 2 3

    1 2 4

    1 2 3

    1 2 4

    1 3 4

    2 3 4

    2 3 4

    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    long long map[30001],f[30001],n,mi[30001],ma[30001],ans=0,i;
    struct point
    {
        int position,value;
    }a[30001];
    void build(long long x)
    {
        while(x<=n)
        {
            f[x]++;
            x+=x&-x;
        }
    }
    long long query(long long x)
    {
        long long sum=0;
        while(x)
        {
            sum+=f[x];
            x-=x&-x;
        }
        return sum;
    }
    bool cmp(const point &a,const point &b)
    {
        return a.value<b.value;
    }
    bool cmp2(const point &a,const point &b)
    {
        return a.value>b.value;
    }
    int main()
    {
        scanf("%lld",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%lld",&a[i].value);
    		a[i].position=i;
        }
        sort(a+1,a+n+1,cmp); 
        for(i=1;i<=n;i++)
        {
            if(a[i].value==a[i-1].value) 
    			map[a[i].position]=map[a[i-1].position];
            else 
    			map[a[i].position]=i;
        }
        for(i=1;i<=n;i++)
        {
            mi[i]=query(map[i]-1);
            build(map[i]);
        }
        sort(a+1,a+n+1,cmp2);
        memset(f,0,sizeof(f));
        for(i=1;i<=n;i++)
        {
            if(a[i].value==a[i-1].value)
    			map[a[i].position]=map[a[i-1].position];
            else 
    			map[a[i].position]=i;
        }
        for(i=n;i>0;i--)
        {
            ma[i]=query(map[i]-1);
            build(map[i]);
        }
        for(i=1;i<=n;i++)
    		ans+=mi[i]*ma[i];
        printf("%lld",ans);
    }


    展开全文
  • P1637 三元上升子序列 48通过 225提交 题目提供者该用户不存在 标签云端 ...a的数据比较大啊,真的能用… ...Erwin最近一种叫"thair"的东西巨感兴趣。...在含有n个整数的序列a1,a2......an中,...

    P1637 三元上升子序列

    •  
    • 48通过
    • 225提交
    • 题目提供者该用户不存在
    • 标签云端
    • 难度提高+/省选-
    • 时空限制1s / 128MB

     提交  讨论  题解  

    最新讨论更多讨论

    • 为什么超时啊
    • a的数据比较大啊,真的能用…

    题目描述

    Erwin最近对一种叫"thair"的东西巨感兴趣。。。

    在含有n个整数的序列a1,a2......an中,

    三个数被称作"thair"当且仅当i<j<k且ai<aj<ak

    求一个序列中"thair"的个数。

    输入输出格式

    输入格式:

    开始一个正整数n,

    以后n个数a1~an。

    输出格式:

    "thair"的个数

    输入输出样例

    输入样例#1
     

    Input

    4

    2 1 3 4

    Output

    2

    Input

    5

    1 2 2 3 4

    Output

    7

    对样例2的说明:

    7个"thair"分别是

    1 2 3

    1 2 4

    1 2 3

    1 2 4

    1 3 4

    2 3 4

    2 3 4

    输出样例#1

    说明

    约定 30%的数据n<=100

    60%的数据n<=2000

    100%的数据n<=30000

    大数据随机生成

    0<=a[i]<=maxlongint

    分析:这道题可以借鉴之前求逆序对那样求,我们只需要求对于每一个数i,在i之前比i小的数的个数和在i之后比i大的数的个数,相乘起来,最后将所有结果加起来就是答案,关键就是如何求出这些数的个数。可以利用树状数组。先将数据离散化,先找小于i的,因为要严格小于,所以我们要先-1再查找,然后添加进去,然后找大于i的,从后往前枚举,相当于我们找到i之后不大于i的个数,然后用n-i(i之后的数的个数)减去结果就是严格大于i的数的个数,最后统计一下答案即可。

         如果将这道题推广到要找k个数的情况,我们需要用到dp,则dp[i][j] = dp[k][j-1] + dp[k][j],其中k为小于i中最靠后的一个数.

    #include <iostream>  
    #include <cstdlib>  
    #include <cstdio>  
    #include <cstring>  
    #include <string>  
    #include <algorithm>
    #include <queue>
    #include <stack>
    #include <cmath>
    
    using namespace std;
    
    long long d1[30010], d2[30010],ans1[30010],ans2[30010],dis[30010],ans;
    
    struct node
    {
        long long v;
        int id;
    }a[30010];
    
    int n;
    
    void update(long long x, int v)
    {
        while (x <= n)
        {
            d1[x] += v;
            x += x &(-x);
        }
    }
    
    int sum(long long x)
    {
        int cnt = 0;
        while (x)
        {
            cnt += d1[x];
            x -= x & (-x);
        }
        return cnt;
    }
    
    void update2(long long x, int v)
    {
        while (x <= n)
        {
            d2[x] += v;
            x += x &(-x);
        }
    }
    
    int sum2(long long x)
    {
        int cnt = 0;
        while (x)
        {
            cnt += d2[x];
            x -= x & (-x);
        }
        return cnt;
    }
    
    bool cmp(node a, node b)
    {
        return a.v < b.v;
    }
    
    int main()
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld", &a[i].v);
            a[i].id = i;
        }
        sort(a + 1, a + 1 + n, cmp);
        dis[a[1].id] = 1;
        int tot = 1;
        for (int i = 2; i <= n; i++)
        {
            if (a[i].v != a[i - 1].v)
                tot++;
            dis[a[i].id] = tot;
        }
        for (int i = 1; i <= n; i++)
        {
            ans1[i] = sum(dis[i] - 1); //是找严格小于的而不是小于等于的
            update(dis[i], 1);
        }
        for (int i = n; i >= 1; i--)
        {
            ans2[i] = n - i - sum2(dis[i]);
            update2(dis[i], 1);
        }
        for (int i = 1; i <= n; i++)
            ans += ans1[i] * ans2[i];
        printf("%lld\n", ans);
    
        return 0;
    }

     

    转载于:https://www.cnblogs.com/zbtrs/p/7078292.html

    展开全文
  • * 给定一个N长度(接近10^5)的整数数列,其连续子数列可以含有1~N个元素。 * Lenth值就是子数列元素个数。 * Weight值就是子数列Lenth × 最小元素。 我起初解法是: * 用int N[100001]存储数列值,...
  • idx称为下标,可以由一个整数、两个整数或多个整数构成,下标含有d(d≥1)个整数称为维数是d。数组按维数分为一维、二维和多维数组。一维数组A是n(n>1)个相同类型元素a0,a1,…,an-1构成有限序列,其逻辑表示...

    数组的基本概念

    数组是一个二元组(idx,value)的集合,对每个idx,都有一个value值与之对应。idx称为下标,可以由一个整数、两个整数或多个整数构成,下标含有d(d≥1)个整数称为维数是d。

    数组按维数分为一维、二维和多维数组。

    一维数组A是n(n>1)个相同类型元素a0,a1,…,an-1构成的有限序列,其逻辑表示为A=(a0,a1,…,an-1),其中,A是数组名,ai(0≤i≤n-1)是数组A中序号为i的元素。

    一个二维数组可以看作是每个数据元素都是相同类型的一维数组的一维数组。

    以此类推

    ee29db2b0e93a99cbf5f24a9571a4ad2.png

    数组具有以下特点

    (1)数组中各元素都具有统一的数据类型。

    (2)d(d≥1)维数组中的非边界元素具有d个前驱元素和d个后继元素。

    (3)数组维数确定后,数据元素个数和元素之间的关系不再发生改变,特别适合于顺序存储。

    (4)每个有意义的下标都存在一个与其相对应的数组元素值。

    d维数组抽象数据类型

    b0f460aa582d843d3ad64ddec4c1f58a.png

    数组的主要操作是存取元素值,没有插入和删除操作,所以数组通常采用顺序存储方式来实现。

    一维数组

    一维数组的所有元素依逻辑次序存放在一片连续的内存存储单元中。

    其起始地址为第一个元素a0的地址即LOC(a0)。

    假设每个数据元素占用k个存储单元。

    则任一数据元素ai的存储地址LOC(ai)就可由以下公式求出

    ef7feeec054e36eaf64d09a5a0cf061b.png

    d维数组

    mn列的二维数组Am×n=(aij)为例讨论(二维数组也称为矩阵)。

    704a46fb07733385f69c07a74b938fe4.png

    按行优先存储

    假设每个元素占k个存储单元,LOC(a0,0)表示a0,0元素的存储地址。对于元素aij

    ai,j前面有0~i-1共i行,每行n个元素,共有i×n个元素。

    在第i行中前面有a[i,0..j-1],共j个元素。

    合起来,ai,j前面有i×n+j个元素。

    f4ec34cd720e1d962560b9747fbd33b3.png

    按列优先存储

    假设每个元素占k个存储单元,LOC(a0,0)表示a0,0元素的存储地址。对于元素aij

    ai,j前面有0~j-1共j列,每列m个元素,共有j×m个元素。

    在第j列中前面有a[0..i-1,j],共i个元素。

    合起来,ai,j前面有j×m+i个元素。则:

    a66feeaa2c7e45d4a87c40c5c5270346.png
    ca81230fe3063c2ee89da88f8ab27055.png

    例子:设有二维数组a[1..50,1..80],其a[1][1]元素的地址为2000,每个元素占2个存储单元,若按行优先存储,则元素a[45][68]的存储地址为多少?若按列优先存储,则元素a[45][68]的存储地址为多少?

    按行优先存储

    元素a[45][68]前面有1~44行,每行80个元素,计44×80个元素。

    在第45行中,元素a[45][68]前面有a[45][1..67]计67个元素,这样元素a[45][68]前面存储的元素个数=44×80+67。

    LOC(a[45][68])=2000+(44×80+67)×2=9174。

    例子:设有二维数组a[1..50,1..80],其a[1][1]元素的地址为2000,每个元素占2个存储单元,若按行优先存储,则元素a[45][68]的存储地址为多少?若按列优先存储,则元素a[45][68]的存储地址为多少?

    按列优先存储

    元素a[45][68]前面有1~67列,每列50个元素,计67×50个元素。

    在第68列中,元素a[45][68]前面有a[1..44][68]计44个元素,这样元素a[45][68]前面存储的元素个数=67×50+44。

    LOC(a[45][68])=2000+(67×50+44)×2=8788。

    特殊矩阵的压缩存储

    cbea2e268fddc620744ef291a69dcdb2.png

    对称矩阵的压缩存储

    9ae91c64fbdce53ba4278a2bc26196ad.png
    d4e7984b252fd4968c1019a76be8335e.png
    a6a937c208ee3f5b3c06fe9ee7a35928.png

    三角矩阵的压缩存储

    2008f38591683d116a776b8869eb66f5.png
    e30f9fc92defc47acb6f6528d5ec282e.png
    d7031216c57d644dd9b3b15b9baf5479.png
    51bf85655aa68833aee49cda153a6ac4.png

    对角矩阵的压缩存储

    58798010866f1851c1156c95c049fb05.png
    4db6ba2f086f8890417c81debc37137c.png

    稀疏矩阵

    一个阶数较大的矩阵中的非零元素个数s相对于矩阵元素的总个数t十分小时,即s<

    例如一个100×100的矩阵,若其中只有100个非零元素,就可称其为稀疏矩阵。

    稀疏矩阵和特殊矩阵的不同点:

    特殊矩阵的特殊元素(相同元素、常量元素)分布有规律。

    稀疏矩阵的特殊元素(非0元素)分布没有规律。

    稀疏矩阵的三元组表示

    fb59bd09ac16eb76ae8861b0cbf2a92e.png

    三元组表示中每个元素的类定义如下:

    f3ff2ddec4f55a77818b26398c87aee9.png

    设计稀疏矩阵三元组存储结构类TupClass如下:

    4d5455ef54f19491271aa61333625fa7.png

    TupClass类中包含如下基本运算方法:

    其中,data列表用于存放稀疏矩阵中所有非零元素,通常按行优先顺序排列。这种有序结构可简化大多数稀疏矩阵运算算法。

    e3d3215d0572c8eedc1b8948aa021ff5.png

    稀疏矩阵的十字链表表示

    每个非零元素对应一个结点

    8b6c31a28392d4da57b662d410b02701.png

    每行的所有结点链起来构成一个带行头结点的循环单链表。以h[i](0≤i≤m-1)作为第i行的头结点。

    eeae814dfb34a87caead21bb2b5f29f7.png

    每列的所有结点链起来构成一个带列头结点的循环单链表。 以h[i](0≤i≤m-1)作为第i列的头结点。

    af0951fed89590b6a406b553c29d6de1.png

    行、列头结点可以共享

    93cfcc1d128cc8fc78111abd826aad53.png

    增加一个总头结点,并把所有行、列头结点链起来构成一个循环单链表

    b14fdea4c31207e131e204d517fa6cda.png

    为了统一,设计结点类型如下:

    d022e2c410cb6300e174a0772f762954.png
    0cfde0c4e98a89d60d0569731ea30a02.png
    展开全文
  • 按字典序列排序(将字符串排序)

    千次阅读 2016-10-11 16:24:02
    输入描述: 输入第一行为一个正整数n(1≤n≤1000),下面n行为n个字符串(字符串长度≤100),字符串中只含有大小写字母。 输出描述: 数据输出n行,输出结果为按照字典序排列字符串。 输入例子: 9 cap to cat card two...
  • C#数据结构

    2013-12-10 11:49:54
    便选择一适合于某个特定问题的数据结构。这些问题就是数据结构这门课程所 要研究的主要问题。本章首先说明学习数据结构的必要性和本书的目的,然后解 释数据结构及其有关概念,接着讨论算法的相关知识,最后简单...
  • idx称为下标,可以由一个整数、两个整数或多个整数构成,下标含有d(d≥1)个整数称为维数是d。数组按维数分为一维、二维和多维数组。一维数组A是n(n>1)个相同类型元素a0,a1,…,an-1构成有限序列,其逻辑表示...
  • 你必须知道495C语言问题

    千次下载 热门讨论 2015-05-08 11:09:25
    例如定义一个包含N个指向返回指向字符指针函数指针数组? 1.22 如何声明返回指向同类型函数指针函数?我在设计一个状态机,用函数表示每种状态,每个函数都会返回一个指向下一个状态函数指针。可我...
  • 数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    2. 对于给定 n个元素,可以构造出逻辑结构有 (1)集合 , (2)线性结构 , (3)树型结构 ,_图状结构_(4)_四种。 【中科院计算所 1999 二、1(4分)】 3.数据的逻辑结构是指(数据的组织形式,即数据元素...
  • 数据结构实验

    2012-04-13 09:55:47
    如何构造一种排序方法,使五个整数至多用七次比较就可以完成排序任务? 实验8:集成实验 一、 实验目的 目的:扩大编程量,完成模块化程序设计全过程。 二 、实验要求 1.认真阅读和掌握和本实验相关教材内容。 ...
  • 《你必须知道495C语言问题》

    热门讨论 2010-03-20 16:41:18
    例如定义一个包含N个指向返回指向字符指针函数指针数组? 11  1.22 如何声明返回指向同类型函数指针函数?我在设计一个状态机,用函数表示每种状态,每个函数都会返回一个指向下一个状态函数指针...
  • 例如定义一个包含N个指向返回指向字符指针函数指针数组? 11  1.22 如何声明返回指向同类型函数指针函数?我在设计一个状态机,用函数表示每种状态,每个函数都会返回一个指向下一个状态函数指针...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    n个整数的平均值; 9、 已知f为单链表的表头指针,链表中存储的都是整型数据,试写出实现下列运算的递归算法: a. 求链表中的最大整数; b. 求链表的结点个数; c. 求所有整数的平均数; 告要求:...
  • 你必须知道495C语言问题(PDF)

    热门讨论 2009-09-15 10:25:47
    例如定义一包含N 指向返 回指向字符指针函数指针数组? . . . . . . . . . . . . . . 3 1.8 函数只定义了一次, 调用了一次, 但编译器提示非法重定义了。. . 4 1.9 main() 正确定义是什么? void main...
  • 归并排序

    2021-03-29 19:39:38
    原理:假设初始序列含有 n 个记录,则可以看成时n个有序序列,每个子序列的长度为1,然后两两归并,得到 [n/2] ([x]表示不小于x最小整数) 个长度为2或1有序子序列;再两两归并,一直重复,直至得到一个长度...
  • 2020-10-28

    2020-10-28 19:55:53
    第2行为n个空格间隔的整数,为该链表n个元素的数据域值。第3行为1个正整数m,表示该链表施加的操作数量;接下来m行,每行表示一个操作,为2个或3个整数,格式为0 k d或1 k。0 k d表示在链表第k个结点后插入一个...
  • 涉及的内容是基本的数据结构。在日本,晚上没事安排@…@,时间还是充足的...,于是自己整理下本系列知识点的上章内容。 <p><img alt="moiunt-Fuji" src=...
  • A,B两个整数集合,设计一个算法求交集,尽可能高效。 一个大的含有50M和URL文件记录,一个小的含有500个URL文件记录,找出两个记录里相同URL,要求最小空间和时间。 实现一个函数,一个正整数n,算得到1...
  • 或者求两个整数m和n需要改变m二进制中多少位才能得到n,可以先做 m^n 异或运算,然后求这个数中有多少个1。 面试题11:数值整数次方:如果采用常规解法,需要注意地方:当指数为负数时候;当底数为零且指数...
  • LINGO软件学习

    2009-08-08 22:36:50
    为此,LINGO为用户提供了两可选部分:输入集成员和数据的数据部分(Data Section)和为决策变量设置初始值的初始部分(Init Section)。 3.1 模型的数据部分 3.1.1 数据部分入门 数据部分提供了模型相对静止部分...
  • 1.3.2 给定一个链表,删除链表倒数第N个节点,并且返回链表头结点 1.3.3 如果让你设计一个通用、支持各种数据库秒级备份和恢复系统,你会如何设计 1.3.4 如果让你来设计一个支持数据库、NOSQL 和大数据...
  • 1.9.1 使用软链接来保存文件映像 12 1.9.2 符号链接举例 12 1.10 小结 13 第2章 使用find和xargs 14 2.1 find命令选项 14 2.1.1 使用name选项 15 2.1.2 使用perm选项 16 2.1.3 忽略某个目录 16 2.1.4 使用user...

空空如也

空空如也

1 2 3 4 5
收藏数 91
精华内容 36
关键字:

对含有n个整数的数据序列