题解

49 条题解

  • 3
    @ 2018-05-20 17:15:37

    这个题目想到的最少有5种解法,有些可行有些不可行
    1.使用**桶排序**的思想,开一个和数字大小一致的数组;但是数字的范围是10^9,因此这里是**不可行**的。
    2.使用**hash**,将数字进行hash,遇到冲突决定是将频率增加还是在链表后面挂一个新值。
    3.使用**sort**排序,然后从前往后扫描一遍并记录重复次数。或者使用二分查找找到上界和下界进行相减。
    4.使用**map**,key对应着数字,value表示出现频率,最后用迭代器遍历一遍即可。
    5.书写**二叉排序树**,节点记录值得同时记录下出现的频率;最后进行一遍中序遍历

  • 1
    @ 2018-12-13 22:50:23

    标准离散化算法

    #include<iostream>
    #include<algorithm>
    using namespace std;
    //呵呵
    //大神万岁
    
    //结构定义区
    struct lsv{
        long long value;
        int time;
        lsv(){
            value=0;time=0;
        }
    };
    //全局变量区
    long long num[200001],n;
    lsv ls[10001];
    //函数声明区
    
    //主函数开始!
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>num[i];
        }
        sort(num+1,num+n+1);
        int under=1;
        num[0]=0;
        for(int i=1;i<=n;i++)
        {
            if(num[i]==num[i-1]) ls[under].time++;
            else if(num[i]!=num[i-1])
            {
                under++;
                ls[under].value=num[i];
                ls[under].time=1;
            }
        }
        for(int i=1;i<=under;i++)
        {
            if(ls[i].time!=0)
            {
                cout<<ls[i].value<<' '<<ls[i].time;
                cout<<endl;
            }
        }
        return 0;
    }
    //函数实现区
    
  • 1
    @ 2018-06-13 16:34:54

    简单的map

    #include<iostream>
    #include<map>
    using namespace std;
    int main(){
        map<int,int> A;
        int n,a;
        cin>>n;
        for (int i=0;i!=n;++i) {cin>>a;A[a]++;}
        for (auto &i:A) cout<<i.first<<' '<<i.second<<endl;
    }
    
  • 1
    @ 2018-05-26 15:34:02

    简单的C++代码

    #include<bits/stdc++.h> 
    using namespace std;
    const int maxn=2e5;
    int n,t=1;
    int a[maxn];
    int main()
    {
        ios::sync_with_stdio(false);
        cin>>n;
        for(int i=0;i<n;i++) cin>>a[i];
        sort(a,a+n);
        for(int i=0;i<n;i++)
        {
            if(a[i]==a[i+1]) t++;
            if(a[i]!=a[i+1]&&a[i-1]==a[i])
            {
                cout<<a[i-1]<<" "<<t<<endl;
                t=1;
            }
            if(a[i]!=a[i+1]&&a[i-1]!=a[i]) cout<<a[i]<<" "<<t<<endl;
        }
        
    }
    
  • 0
    @ 2020-04-05 23:44:28
    /*
    平衡二叉树,自己找轮子
    */
    #include <iostream> //[2007提高组-A]统计数字
    #include <algorithm>
    using namespace std;
    
    typedef struct TNode{
        int Data;
        TNode *Left, *Right;
        int t;  //计数
        int Height;
    } * AVLTree;
    
    int GetHeight(AVLTree AVL)
    {
        if(AVL)
            return AVL->Height;
        else
            return 0;
    }
    
    AVLTree SingleLeftRotation(AVLTree A)   //LL旋
    {
        AVLTree B = A->Left;
        A->Left = B->Right;
        B->Right = A;
        A->Height = max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
        B->Height = max(GetHeight(B->Left), GetHeight(A)) + 1;
        return B;
    }
    AVLTree SingleRightRotation(AVLTree A)  //RR旋
    {
        AVLTree B = A->Right;
        A->Right = B->Left;
        B->Left = A;
        A->Height = max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
        B->Height = max(GetHeight(B->Right), GetHeight(A)) + 1;
        return B;
    }
    AVLTree DoubleLeftRightRotation(AVLTree A)  //LR旋
    {
        A->Left = SingleRightRotation(A->Left);
        return SingleLeftRotation(A);
    }
    AVLTree DoubleRightLeftRotation(AVLTree A)  //RR旋
    {
        A->Right = SingleLeftRotation(A->Right);
        return SingleRightRotation(A);
    }
    
    AVLTree Insret(AVLTree T, int x)
    {
        if(!T)
        {
            T = new TNode();
            T->Data = x;
            T->Height = 1;
            T->t = 1;
        }
        else if(x < T->Data)
        {
            T->Left = Insret(T->Left, x);
            if (GetHeight(T->Left) - GetHeight(T->Right) == 2)
                if(x < T->Left->Data)
                    T = SingleLeftRotation(T);
                else
                    T = DoubleLeftRightRotation(T);
        }
        else if(x > T->Data)
        {
            T->Right = Insret(T->Right, x);
            if(GetHeight(T->Left) - GetHeight(T->Right) == -2)
                if(x > T->Right->Data)
                    T = SingleRightRotation(T);
                else
                    T = DoubleRightLeftRotation(T);
        }
        else
            T->t++;
        T->Height = max(GetHeight(T->Left), GetHeight(T->Right)) + 1;
        return T;
    }
    
    void Print(AVLTree T)
    {
        if(T)
        {
            Print(T->Left);
            cout << T->Data << " " << T->t << endl;
            Print(T->Right);
        }
    }
    
    int main()
    {
        int n, x;
        AVLTree AVL = NULL;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> x;
            AVL = Insret(AVL, x);
        }
        Print(AVL);
    
        return 0;
    }
    
    
  • 0
    @ 2019-12-08 16:01:11

    #include<cstdio>
    #include<iostream>
    using namespace std;
    void quicksort(int,int);
    int a[200005];
    int main(){
    int n,i,flag,total;
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d",&a[i]);
    quicksort(0,n-1);
    flag=a[0];
    total=1;
    for(i=1;i<n;i++) {
    if(a[i]!=flag){
    printf("%d %d\n",flag,total);
    total=0;
    }
    flag=a[i];
    total++;
    }
    printf("%d %d\n",flag,total);
    return 0;
    }
    inline void quicksort(int left,int right){
    int i=left,j=right,mid=a[(left+right)/2];
    while(i<=j){
    while(a[i]<mid) i++;
    while(a[j]>mid) j--;
    if(i<=j){
    swap(a[i],a[j]);
    i++;
    j--;
    }
    }
    if(left<j) quicksort(left,j);
    if(i<right) quicksort(i,right);
    }

  • 0
    @ 2019-07-23 16:30:14

    #include <iostream>
    using namespace std;
    int main()
    {
    int n,i,j,b,a[10000][2],k,l=0;
    cin>>n;
    for(i=0;i<10000;i++) {a[i][0]=0;a[i][1]=0;}
    a[0][0]=1500000001;
    for(i=0;i<n;i++)
    {
    cin>>k;
    for(j=0;j<=l;j++)
    if(a[j][0]==k) {a[j][1]++;break;}else
    if(a[j][0]>k)
    {
    l++;
    for(b=l;b>j;b--) {a[b][0]=a[b-1][0];a[b][1]=a[b-1][1];}
    a[j][0]=k;
    a[j][1]=1;
    break;
    }
    }
    for(i=0;i<10000;i++) if(a[i][1]!=0) cout<<a[i][0]<<' '<<a[i][1]<<endl;
    return 0;
    }

  • 0
    @ 2018-05-09 11:07:13

    map大法好

    #include <iostream>
    #include <map>
    
    using namespace std;
    
    int main()
    {
        ios::sync_with_stdio(false);
    
        map<long long, int> mp;
        int n, m;
    
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> m;
            mp[m]++;
        }
    
        for (auto i = mp.begin(); i != mp.end(); i++)
            cout << i->first << " " << i->second << endl;
    
        return 0;
    }
    
  • 0
    @ 2018-02-06 10:14:24
    #include<bits/stdc++.h>
    int n;
    int num[200010];
    int main() {
        scanf("%d", &n);
        for(int i=0; i<n; i++) scanf("%lld", &num[i]);
        std::sort(num, num+n);
        int count=1;
        for(int i=0; i<n-1; i++)
            if(num[i]==num[i+1]) count++;
            else {
                printf("%d %d\n", num[i], count);
                count=1;
            }
        printf("%d %d", num[n-1], count);
        return 0;
    }
    
  • 0
    @ 2017-11-21 17:56:42

    一个垃圾的代码,容菜鸟向神犇学习。。。
    ```cpp
    #include<iostream>
    #include<cstring>
    #define MAXN 200001
    using namespace std;
    long long a[MAXN];
    void qsort(int l,int r)
    {

    int i,j,mid,p;
    i=l;
    j=r;
    mid=a[(l+r)/2];

    do
    {
    while (a[i]<mid) i++;
    while (a[j]>mid) j--;

    if (i<=j)
    {

    p=a[i];
    a[i]=a[j];
    a[j]=p;
    i++;
    j--;

    }
    }
    while (i<=j);

    if (l<j) qsort(l,j);

    if (i<r) qsort(i,r);
    }

    int main()
    {
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    int n,count=1;
    memset(a,0,sizeof(a));
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    qsort(1,n);
    for(int i=2;i<=n+1;i++)
    {
    if(a[i]!=a[i-1])
    {
    cout<<a[i-1]<<" "<<count<<endl;
    count=1;
    }
    if(a[i]==a[i-1])
    count++;
    }
    return 0;
    fclose(stdin);
    fclose(stdout);
    }
    ```

  • 0
    @ 2017-10-20 15:20:19
    #include<bits/stdc++.h>
    #define max_n 200005
    using namespace std;
    int a[max_n],n,last,cnt;
    int main()
    {
        scanf("%d",&n);
        for(register int i=1;i<=n;i++) scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        last=a[1];
        for(register int i=1;i<=n;i++)
        {
            if(a[i]!=last) 
            {
                printf("%d %d\n",last,cnt);
                last=a[i];
                cnt=0;
            }
            cnt++;
        }
        printf("%d %d",last,cnt);
        return 0;
    }
    
  • 0
    @ 2017-10-03 15:24:42
    #include<iostream>
    #include<algorithm>
    using namespace std;
    long long a[200010];
    struct node{
        long long num;
        int ci;
    }q[200100];
    int main()
    {
        int n,i,now=0;
        cin>>n;
        for(i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        sort(a+1,a+n+1);
        for(i=1;i<=n;i++)
        {
            if(a[i]!=a[i-1])
            {
                now++;
                q[now].num=a[i];
                q[now].ci=1;
            }
            else
            q[now].ci++;
        }
        for(i=1;i<=now;i++)
         cout<<q[i].num<<" "<<q[i].ci<<endl;
        return 0;
    }
    
  • 0
    @ 2017-09-08 08:50:26

    这。
    当年的noip为什么这么水。
    简单的两种解法:
    1. STL的sort,当年是不是要自己敲不清楚。
    2. STL的map。

    #include <cstdio>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int MO=19870816;
    int N;
    int A[200005];
    int main () {
        
        scanf("%d", &N);
        for(int i=1; i<=N; i++) scanf("%d", &A[i]);
        sort(A+1, A+N+1);   
        int a=MO, b=0;
        for(int i=1; i<=N+1; i++)   
            if (A[i]!=a) {
                if (i!=1) printf("%d %d\n", a, b);
                a=A[i], b=1;
            }   
            else b++;   
        return 0;
        
    }
    
  • 0
    @ 2017-05-05 08:47:17
    #include<bits/stdc++.h>
    #define For(i,j,k) for(int i=j;i<=k;i++)
    using namespace std;
    int a[200001],n;
    map<int,int>mp;
    int main()
    {
        scanf("%d",&n);
        For(i,1,n)  scanf("%d",&a[i]),mp[a[i]]++;
        sort(a+1,a+n+1);
        int len=unique(a+1,a+n+1)-a-1;
        For(i,1,len)    printf("%d %d\n",a[i],mp[a[i]]);
    }
    
  • 0
    @ 2016-12-29 12:24:48

    C++ STL 大法好。
    map万岁

    #include<iostream>
    #include<cstdio>
    #include<map>
    #include<algorithm>
    using namespace std;
    #define reg register
    int main()
    {
    map<long long,int>t;
    reg int n,i;
    scanf("%d",&n);
    long long a[n];
    for(i=0;i<n;i++)
    {
    scanf("%lld",&a[i]);
    t[a[i]]++;
    }
    sort(a,a+n);
    printf("%lld %d\n",a[0],t[a[0]]);
    for(i=1;i<n;i++)
    if(a[i]!=a[i-1]) printf("%lld %d\n",a[i],t[a[i]]);
    return 0;
    }

  • 0
    @ 2016-12-10 23:51:07

    #这年头使java的人真不多啊。。。奉上本题第一份java题解。。
    ##不说了,好水啊,水的我想吐。。。
    ```java
    import java.util.Arrays;
    import java.util.Scanner;

    public class Main {
    public static void main(String[] args){
    Scanner cin = new Scanner(System.in);

    int n = cin.nextInt();

    int[] a = new int[200001];

    for(int i = 0 ; i < n ; i ++){
    a[i] = cin.nextInt();
    }

    Arrays.sort(a,0,n);

    int tmp = 0;

    for(int i = 0 ; i < n ; i ++){
    tmp ++;
    if(a[i] != a[i+1]){
    System.out.println(a[i] + " " + tmp);
    tmp = 0;
    }
    }

    cin.close();
    }
    }
    ```
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 93 ms, mem = 43012 KiB, score = 10
    测试数据 #1: Accepted, time = 109 ms, mem = 43008 KiB, score = 10
    测试数据 #2: Accepted, time = 140 ms, mem = 43008 KiB, score = 10
    测试数据 #3: Accepted, time = 234 ms, mem = 43004 KiB, score = 10
    测试数据 #4: Accepted, time = 328 ms, mem = 43008 KiB, score = 10
    测试数据 #5: Accepted, time = 328 ms, mem = 43000 KiB, score = 10
    测试数据 #6: Accepted, time = 453 ms, mem = 43008 KiB, score = 10
    测试数据 #7: Accepted, time = 734 ms, mem = 43008 KiB, score = 10
    测试数据 #8: Accepted, time = 750 ms, mem = 43016 KiB, score = 10
    测试数据 #9: Accepted, time = 93 ms, mem = 43008 KiB, score = 10
    Accepted, time = 3262 ms, mem = 43016 KiB, score = 100

  • 0
    @ 2016-11-16 19:25:13
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    int a[200005];
    
    int main()
    {
        int i,j,k,n;
        cin>>n;
        for(i=1;i<=n;i++)
        cin>>a[i];
        sort(a+1,a+n+1);
        int sum=0;  int last=a[1];
        for(i=1;i<=n+1;i++)
        {
            if(a[i]==last)  sum++;
            else{cout<<a[i-1]<<" "<<sum<<endl;sum=1;last=a[i];}
        }
        return 0;
    }
    
  • 0
    @ 2016-11-11 16:09:49

    显然,离散化带个log轻松过
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int MAXN=200005;
    int n,q[MAXN],a[MAXN],Hash[MAXN],val[MAXN];
    int query(int L,int R,int x)
    {
    int l=L,r=R;
    while(l<r){
    int mid=(l+r)>>1;
    if(x<=a[mid])r=mid;
    else l=mid+1;
    }
    return l;
    }
    int main()
    {
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
    scanf("%d",&q[i]);
    a[i]=q[i];
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
    int s=query(1,n,q[i]);
    ++Hash[s];val[s]=q[i];
    }
    for(int i=1;i<=200000;i++){
    if(val[i]>0)printf("%d %d\n",val[i],Hash[i]);
    }
    return 0;
    }

  • 0
    @ 2016-11-06 23:15:50

    从逻辑上来讲是错误的,但是卡了一个错位差——tot的加减问题
    #include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <cmath>
    #include <map>
    #include <vector>
    #include <stack>
    #include <queue>

    using namespace std;

    int n,a[300000];

    int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    sort(a,a+n);
    for(int i=0;i<n;){
    printf("%d ",a[i]);
    int t=a[i],tot=0;
    while(a[i]==t)i++,tot++;
    printf("%d\n",tot);
    }
    }

  • 0
    @ 2016-11-02 15:36:00
    #include<bits/stdc++.h>
    
    std::map<int,int>v;
    int main() {
        int t,i,n;
        scanf("%d",&n);
        for(i=1; i<=n; ++i)scanf("%d",&t),v[t]++;
        for(std::map<int,int>::iterator it=v.begin(); it!=v.end(); it++)
            printf("%d %d\n",(*it),(*it).second);
    }
    

信息

ID
1816
难度
4
分类
(无)
标签
递交数
2878
已通过
1132
通过率
39%
被复制
5
上传者