题解

50 条题解

  • 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);
    }
    
  • 0
    @ 2016-11-02 15:27:10

    法1:
    #include<cstdio>
    #include<map>
    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);
    法2:
    #include<cstdio>
    #include<algorithm>
    int v[10010],k[200010];
    int main()
    {
    int n,i,ptr=0,lst=2e9;scanf("%d",&n);
    for(i=1;i<=n;++i)scanf("%d",&k[i]);
    std::sort(k+1,k+n+1);
    for(i=1;i<=n;++i){if(k[i]-lst)ptr++,lst=k[i];v[ptr]++;}
    std::unique(k+1,k+n+1);
    for(i=1;i<=ptr;++i)printf("%d %d\n",k[i],v[i]);
    }

  • 0
    @ 2016-10-26 18:53:39

    评测结果
    编译成功
    测试数据 #0: Accepted, time = 15 ms, mem = 552 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 560 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 636 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 708 KiB, score = 10
    测试数据 #4: Accepted, time = 31 ms, mem = 1096 KiB, score = 10
    测试数据 #5: Accepted, time = 31 ms, mem = 1612 KiB, score = 10
    测试数据 #6: Accepted, time = 31 ms, mem = 1612 KiB, score = 10
    测试数据 #7: Accepted, time = 125 ms, mem = 2640 KiB, score = 10
    测试数据 #8: Accepted, time = 93 ms, mem = 2644 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 556 KiB, score = 10
    Accepted, time = 341 ms, mem = 2644 KiB, score = 100
    代码
    c++
    #include<bits/stdc++.h>
    using namespace std;
    struct cmp {
    bool operator () (int &a, int &b) {
    return a > b ;
    }
    };
    priority_queue<int,vector<int>,cmp>q;
    int main() {
    int n,i;
    scanf("%d",&n);
    for (i=1; i<=n; i++) {
    int number;
    scanf("%d",&number);
    q.push(number);
    }
    int pre=q.top();
    int t=0;
    while (q.size()) {
    int now=q.top();
    if (now==pre) t++;
    else {
    printf("%d %d\n",pre,t);
    t=1;
    }
    q.pop();
    pre=now;
    }
    printf("%d %d\n",pre,t);
    }

  • 0
    @ 2016-10-26 18:50:17

    暴力优先队列

    #include<bits/stdc++.h>
    using namespace std;
    int n,t;
    
    
    priority_queue<int,vector<int>, greater<int> > heap;
    int main() {
        int i,tmp;
        scanf("%d",&n);
        for (i=1; i<=n; i++) {
            scanf("%d",&tmp);
            heap.push(tmp);
        }
        t=0;
        tmp=heap.top();
        while (true) {
            if (heap.empty()) {
                printf("%d %d\n",tmp,t);
                break;
            }
            if (tmp!=heap.top()) {
                printf("%d %d\n",tmp,t);
                tmp=heap.top();
                t=1;
                heap.pop();
            } else {
                t++;
                heap.pop();
            }
        
        }
        return 0;
    }
    
  • 0
    @ 2016-10-11 20:21:59
    #include<cstdlib>
    #include<cstdio>
    #include<vector>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<string>
    #include<queue>
    #include<stack>
    #include<ctime>
    #include<cmath>
    #include<map>
    #include<cctype>
    #define f(x,y) for(register int x=1;x<=y;x++)
    using namespace std;
    inline int read() {
        register int x = 0;
        register char c = getchar() ;
        register int f = 1;
        while (isspace(c)) c = getchar() ;
        if(c == '-') f = -1,c = getchar();
        do x = x * 10 + c - '0', c = getchar();
        while (isdigit(c)) ;
        return x * f;
    }
    map <int,int> m;
    int main(){
    //  freopen("calc.in","r",stdin);
        //freopen("calc.out","w",stdout);
        int n;
        n = read ();
        f(i,n) 
            m[read()]++;
        for (map<int, int>::iterator pos1 = m.begin(); pos1 != m.end(); pos1 ++)
            printf ("%d %d\n",pos1->first,pos1->second);
        return 0;
    }
    
  • 0
    @ 2016-10-11 20:21:04

    #include<cstdlib>
    #include<cstdio>
    #include<vector>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<string>
    #include<queue>
    #include<stack>
    #include<ctime>
    #include<cmath>
    #include<map>
    #include<cctype>
    #define f(x,y) for(register int x=1;x<=y;x++)
    using namespace std;
    inline int read() {
    register int x = 0;
    register char c = getchar() ;
    register int f = 1;
    while (isspace(c)) c = getchar() ;
    if(c == '-') f = -1,c = getchar();
    do x = x * 10 + c - '0', c = getchar();
    while (isdigit(c)) ;
    return x * f;
    }
    map <int,int> m;
    int main(){
    int n;
    n = read ();
    f(i,n)
    m[read()]++;
    for (map<int, int>::iterator pos1 = m.begin(); pos1 != m.end(); pos1 ++)
    printf ("%d %d\n",pos1->first,pos1->second);
    return 0;
    }

  • 0
    @ 2016-09-19 21:49:48

    本来想敲个HashMap的简易模版,结果敲出来发现效率还不如直接用map。。。
    ```c++
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<list>
    using namespace std;

    const int MOD = 10000;

    int n;

    struct HashMap {
    typedef int Key;
    typedef int Val;

    struct Pair {
    Key key;
    Val val;
    Pair (const Key &key, const Val &val) : key(key), val(val) {}
    };

    list<Pair> map[MOD];
    list<Key> vis;
    Val nops;

    int getint (const Key &key) { return key % MOD;}

    bool count (const Key &key) {
    int key_num = getint(key);
    for (auto p = map[key_num].begin(); p != map[key_num].end(); p++)
    if (p->key == key) return true;
    return false;
    }

    bool insert (const Key &key, const Val &val = 0) {
    if (count(key)) return false;
    vis.push_back(key);
    map[getint(key)].push_back(Pair(key, val));
    }

    Val& operator {
    insert(key);
    int key_num = getint(key);
    for (auto p = map[key_num].begin(); p != map[key_num].end(); p++)
    if (p->key == key) return p->val;
    return nops;
    }

    void print_ans () {
    vis.sort();
    for (auto p = vis.begin(); p != vis.end(); p++)
    printf("%d %d\n", *p, (*this)[*p]);
    }
    };

    HashMap tool;

    int main ()
    {
    cin >> n;
    while (n--) {
    int num; scanf("%d", &num);
    tool[num]++;
    }

    tool.print_ans();
    return 0;
    }
    ```

  • 0
    @ 2016-08-28 15:13:11

    为什么大家都用map<int,int>::iterator p呢……可以用auto的
    ```c++
    #include <iostream>
    #include <cstdio>
    #include <map>

    using namespace std;

    map<int,int>m;

    int main()
    {
    m.clear();
    int n;
    cin >> n;
    for (int i=0;i<n;i++)
    {
    int a;
    scanf("%d",&a);
    m[a]++;
    }
    for (auto p=m.begin();p!=m.end();p++)
    cout << p->first << " " << p->second << endl;
    return 0;
    }
    ```

  • 0
    @ 2016-08-28 11:25:14

    复制楼下,内存不用开那么大
    #include <iostream>
    #include <iomanip>
    #include <map>
    using namespace std;
    map<int,int> book;
    int main()
    {
    ios::sync_with_stdio(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    int x;
    cin>>x;
    book[x]++;
    }
    map<int,int>::iterator it;
    for(it=book.begin();it!=book.end();it++)
    cout<<it->first<<" "<<it->second<<endl;
    return 0;
    }

  • 0
    @ 2016-08-28 11:20:40

    归并排序,动态数组 为什么动态数组更费内存
    #include <iostream>
    #include <cstring>
    #include <vector>

    using namespace std;

    vector <int> num;
    vector <int> ans;

    void gsort(int l,int r)
    {
    if(l==r)return;//cout<<"dsfe";
    int mid=(l+r)/2;
    gsort(l,mid);
    gsort(mid+1,r);
    //memset(ans,0,sizeof(ans));
    int k=l;
    int i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
    if(num[i]<num[j])
    {
    ans[k]=num[i];
    ++k;
    ++i;
    }else
    {
    ans[k]=num[j];
    ++k;
    ++j;
    }
    }
    while(i<=mid)
    {
    ans[k]=num[i];
    ++k;
    ++i;
    }
    while(j<=r)
    {
    ans[k]=num[j];
    ++k;
    ++j;
    }
    for(k=l;k<=r;++k)
    num[k]=ans[k];
    return;
    }

    int main()
    {
    int n;
    cin>>n;
    int i;
    int t=1;
    for(i=0;i<n;++i)
    {
    ans.push_back(0);
    num.push_back(0);
    }
    //memset(num,0,sizeof(num));//初始化;
    for(i=0;i<n;++i)
    cin>>num[i];
    gsort(0,n-1);
    for(i=0;i<n;++i)//输出计数
    {
    cout<<num[i]<<' ';
    while(num[i]==num[i+1])
    {
    ++t;
    ++i;
    }
    cout<<t<<endl;
    t=1;
    }
    return 0;
    }
    **普通数组,归并排序**
    #include <iostream>
    #include <cstring>
    #include <vector>

    using namespace std;

    int num[200000];
    int ans[200000];

    //vector <int> num;
    //vector <int> ans;

    void gsort(int l,int r)
    {
    if(l==r)return;//cout<<"dsfe";
    int mid=(l+r)/2;
    gsort(l,mid);
    gsort(mid+1,r);
    //memset(ans,0,sizeof(ans));
    int k=l;
    int i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
    if(num[i]<num[j])
    {
    ans[k]=num[i];
    ++k;
    ++i;
    }else
    {
    ans[k]=num[j];
    ++k;
    ++j;
    }
    }
    while(i<=mid)
    {
    ans[k]=num[i];
    ++k;
    ++i;
    }
    while(j<=r)
    {
    ans[k]=num[j];
    ++k;
    ++j;
    }
    for(k=l;k<=r;++k)
    num[k]=ans[k];
    return;
    }

    int main()
    {
    int n;
    cin>>n;
    int i;
    int t=1;/*
    for(i=0;i<n;++i)
    {
    ans.push_back(0);
    num.push_back(0);
    }*/
    //memset(num,0,sizeof(num));//初始化;
    for(i=0;i<n;++i)
    cin>>num[i];
    gsort(0,n-1);
    for(i=0;i<n;++i)//输出计数
    {
    cout<<num[i]<<' ';
    while(num[i]==num[i+1])
    {
    ++t;
    ++i;
    }
    cout<<t<<endl;
    t=1;
    }
    return 0;
    }

  • 0
    @ 2016-08-28 10:53:34

    动态数组 内存反而更大了,为什么啊???
    #include <iostream>
    #include <cstring>
    #include <vector>

    using namespace std;

    vector <int> num;

    void ksort(int l,int r)//快排
    {
    int mid=num[(l+r)/2];
    int i=l,j=r;
    int temp=0;
    do
    {
    while(num[i]<mid)++i;
    while(num[j]>mid)--j;
    if(i<=j)
    {
    temp=num[i];
    num[i]=num[j];
    num[j]=temp;
    ++i;
    --j;
    }
    }while(i<=j);
    if(l<j)ksort(l,j);
    if(i<r)ksort(i,r);
    return;
    }

    int main()
    {
    int n;
    cin>>n;
    int i;
    int t=1;
    for(i=0;i<n;++i)
    num.push_back(0);
    // memset(num,0,sizeof(num));//初始化;
    for(i=0;i<n;++i)
    cin>>num[i];
    ksort(0,n-1);
    for(i=0;i<n;++i)//输出计数
    {
    cout<<num[i]<<' ';
    while(num[i]==num[i+1])
    {
    ++t;
    ++i;
    }
    cout<<t<<endl;
    t=1;
    }
    return 0;
    }
    **普通数组**
    #include <iostream>
    #include <cstring>

    using namespace std;

    void ksort(int num[],int l,int r)//快排
    {
    int mid=num[(l+r)/2];
    int i=l,j=r;
    int temp=0;
    do
    {
    while(num[i]<mid)++i;
    while(num[j]>mid)--j;
    if(i<=j)
    {
    temp=num[i];
    num[i]=num[j];
    num[j]=temp;
    ++i;
    --j;
    }
    }while(i<=j);
    if(l<j)ksort(num,l,j);
    if(i<r)ksort(num,i,r);
    return;
    }

    int main()
    {
    int n;
    cin>>n;
    int num[200000];
    int i;
    int t=1;
    memset(num,0,sizeof(num));//初始化;
    for(i=0;i<n;++i)
    cin>>num[i];
    ksort(num,0,n-1);
    for(i=0;i<n;++i)//输出计数
    {
    cout<<num[i]<<' ';
    while(num[i]==num[i+1])
    {
    ++t;
    ++i;
    }
    cout<<t<<endl;
    t=1;
    }
    return 0;
    }

  • 0
    @ 2016-08-25 14:51:39

    pascal秒过!!!两个过程轻松搞定!!!
    ```pascal
    type
    arr=array[0..33333,0..2] of longint;
    var
    ans,g,i,k,n,m1,m2,total:longint;
    a:arr;

    procedure factorization(k:longint;var a:arr;var link:longint);
    var
    i:longint;
    begin
    i:=1;
    link:=0;
    repeat
    inc(i);
    if k mod i=0
    then
    begin
    inc(link);
    a[link,1]:=i;
    a[link,2]:=0;
    while k mod i=0 do
    begin
    inc(a[link,2]);
    k:=k div i;
    end;
    end;
    until k=1;
    end;

    procedure main;
    var
    i,z,max:longint;
    begin
    max:=-1;
    read(k);
    for i:=1 to total do
    begin
    if k mod a[i,1]<>0 then exit;
    z:=0;
    while k mod a[i,1]=0 do
    begin
    inc(z);
    k:=k div a[i,1];
    end;
    if (a[i,2]+z-1) div z>max then max:=(a[i,2]+z-1) div z;
    end;
    if max<ans then ans:=max;
    end;

    begin
    ans:=maxlongint;
    readln(n);
    readln(m1,m2);
    if m1=1
    then
    begin
    writeln(0);
    halt;
    end;
    factorization(m1,a,total);
    for i:=1 to total do a[i,2]:=a[i,2]*m2;
    for i:=1 to n do main;
    readln;
    if ans=maxlongint
    then
    writeln(-1)
    else
    writeln(ans);
    end.
    ```

  • 0
    @ 2016-08-15 11:55:46

    STL大法好,退C转C++保平安~
    MAP当桶用,一用一个爽~
    c++
    #include <iostream>
    #include <iomanip>
    #include <map>
    using namespace std;
    map<unsigned long long,int> book;
    int main()
    {
    ios::sync_with_stdio(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    int x;
    cin>>x;
    book[x]++;
    }
    map<unsigned long long,int>::iterator it;
    for(it=book.begin();it!=book.end();it++)
    cout<<it->first<<" "<<it->second<<endl;
    return 0;
    }

  • 0
    @ 2016-08-02 18:11:07

    第一次想用计数试一下,结果RE+超时。。。。。。。看来不得不用快排啊
    pascal
    var
    i,j,n,m,s:longint;
    a:array[1..1000000] of longint;
    procedure qsort(l,r: longint);
    var
    i,j,x,y: longint;
    begin
    i:=l;
    j:=r;
    x:=a[(l+r) div 2];
    repeat
    while a[i]<x do
    inc(i);
    while x<a[j] do
    dec(j);
    if not(i>j) then
    begin
    y:=a[i];
    a[i]:=a[j];
    a[j]:=y;
    inc(i);
    j:=j-1;
    end;
    until i>j;
    if l<j then qsort(l,j);
    if i<r then qsort(i,r);
    end;
    begin
    readln(n);
    for i:=1 to n do
    readln(a[i]);
    qsort(1,n);
    s:=1;
    for i:=1 to n do
    begin
    if a[i+1]=a[i] then inc(s)
    else
    begin
    writeln(a[i],' ',s);
    s:=1;
    end;
    end;
    end.

  • 0
    @ 2016-07-29 20:37:45

    type re=record
    a,b:longint;
    end;
    var
    a:array[1..10100]of re;
    b:array[1..200100]of longint;
    i,j,k,m,n:longint;
    procedure qsort(l,r:longint);
    var
    i,j,mid,p:longint;
    begin
    i:=l;
    j:=r;
    mid:=b[(i+j) div 2];
    repeat
    while b[i]<mid do inc(i);
    while b[j]>mid do dec(j);
    if i<=j then
    begin
    p:=b[i];
    b[i]:=b[j];
    b[j]:=p;
    inc(i);
    dec(j);
    end;
    until i>j;
    if l<j then qsort(l,j);
    if i<r then qsort(i,r);
    end;
    begin
    readln(n);
    k:=1;
    for i:=1 to n do
    readln(b[i]);
    qsort(1,n);
    k:=1;
    a[1].a:=b[1];
    a[1].b:=1;
    for i:=2 to n do
    begin
    if b[i]=b[i-1] then inc(a[k].b)
    else
    begin
    inc(k);
    a[k].a:=b[i];
    a[k].b:=1;
    end;
    end;
    for i:=1 to k do writeln(a[i].a,' ',a[i].b);
    end.

  • 0
    @ 2016-07-14 20:28:09

    排序统计(写了读入优化)

    
    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    using namespace std;
    const int N=200005;
    int n,tot=1,s[N];
    
    int cmp(const void*a,const void*b){
        return *(int*)a-*(int*)b;
    }
    
    void read(int &x){
        int ch=getchar();
        while(ch<'0'||ch>'9')ch=getchar();
        x=0;
        while(ch>='0'&&ch<='9'){
            x=x*10+ch-'0';
            ch=getchar();
        }
    }
    
    int main(){
        read(n);
        for(int i=0;i<n;i++)
            read(s[i]);
        qsort(s,n,sizeof(s[0]),cmp);
        printf("%d ",s[0]);
        for(int i=1;i<n;i++){
            if(s[i]==s[i-1])
                tot++;
            else{
                printf("%d\n%d ",tot,s[i]);
                tot=1;
            }
        }
        printf("%d\n",tot);
        return 0;
    }
    
  • 0
    @ 2015-10-20 13:22:39

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    using std::vector;
    using std::sort;

    const int maxn=5859380;//Each m_hashTable has mostly 256 elements.

    class Hash
    {
    private:

    struct Element;
    vector<Element> m_hashTable[maxn];
    vector<int> m_hasElement;
    int N;

    void add(int x);

    public:

    Hash();

    void output();
    };

    struct Hash::Element
    {
    int m_key;
    int m_cnt;
    Element(int key):m_key(key),m_cnt(1) {}

    bool operator < (const Element& A)
    {
    return this->m_key<A.m_key;
    }
    };

    void Hash::add(int x)
    {
    int h=x>>8;
    int n=m_hashTable[h].size();
    bool inTable=false;

    for(int i=0;i<n;i++) if(m_hashTable[h][i].m_key==x) {
    inTable=true;
    m_hashTable[h][i].m_cnt++;
    }

    if(!inTable) {
    if(n==0) m_hasElement.push_back(h);
    m_hashTable[h].push_back(Element(x));
    }
    }

    Hash::Hash()
    {
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
    int x;scanf("%d",&x);
    add(x);
    }
    }

    void Hash::output()
    {
    sort(m_hasElement.begin(),m_hasElement.end());

    int n=m_hasElement.size();
    for(int i=0;i<n;i++) {
    int h=m_hasElement[i];
    sort(m_hashTable[h].begin(),m_hashTable[h].end());
    int k=m_hashTable[h].size();
    for(int j=0;j<k;j++)
    printf("%d %d\n",m_hashTable[h][j].m_key,m_hashTable[h][j].m_cnt);
    }
    }

    int main()
    {
    Hash* H=new Hash();
    H->output();
    return 0;
    }

    没什么卵用的Hash

  • 0
    @ 2015-10-08 21:56:05

    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>
    using namespace std;

    int n;
    int a[200010] = {};
    int num[10010] = {};

    int main()
    {
    int tmp,sum = 1;
    scanf("%d",&n);
    for(int i = 1;i <= n; i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    tmp = a[1];
    for(int i = 2;i <= n; i++)
    {
    if(tmp != a[i])
    {
    printf("%d %d\n",tmp,sum);
    tmp = a[i];
    sum = 1;
    continue;
    }
    sum++;
    }
    printf("%d %d\n",tmp,sum);
    return 0;
    }

    linhui is my son....

  • 0
    @ 2015-09-11 22:51:30

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int MAXN = 200000 + 10;

    int num[MAXN];

    int main()
    {
    int n, bri = 0, sum = 1;
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    scanf("%d", &num[i]);
    sort(&num[1], &num[1]+n);
    for(int i=2; i<=n; i++){
    if(num[i] != num[i-1]){
    printf("%d %d\n", num[i-1], sum);
    sum = 1;
    }
    else
    sum++;
    }
    printf("%d %d\n", num[n], sum);
    return 0;
    }
    模拟

  • 0
    @ 2015-08-23 11:30:59

    水题水题超级水题,直接借用库函数qsort。顺便问一下,在noip比赛中能这样用么?
    #include <iostream>
    #include <cstdlib>
    //#include <fstream>
    using namespace std;
    int comp(const void*a,const void*b)
    {
    return (int)a-*(int*)b;
    }
    int main()
    {
    //ifstream cin("p1816.in",ios::in);
    //ofstream cout("p1816.out",ios::out);
    int n;
    cin>>n;
    const int N=200000;
    long s[N]={0};
    for(int i=0;i<n;cin>>s[i++]);
    qsort(s,n,sizeof(int),comp);
    cout<<s[0]<<' ';
    int tot=1;
    for(int i=1;i<n;i++)
    {
    if(s[i]==s[i-1])tot++;
    else cout<<tot<<endl<<s[i]<<' ',tot=1;
    }
    cout<<tot<<endl;
    //cin.close();
    //cout.close();
    return 0;
    }

信息

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