题解

24 条题解

  • 1
    @ 2017-11-10 20:19:45
    #include<bits/stdc++.h>
    #include<unordered_map>
    using namespace std;
    int m, k;
    priority_queue<int, vector<int>, greater<int>>heap;
    vector<int>numb;
    int main()
    {
        ios::sync_with_stdio(false);
        cin >> k >> m;
        int now = 1;
        heap.push(now);
        while (numb.size() < k) {//TO DO:找序列前k个
            now = heap.top();
            numb.push_back(now);
            heap.pop();
            heap.push(now * 2 + 1);
            heap.push(now * 4 + 5);
        }
        string n;
        stringstream p;
        for (int i = 0; i < numb.size(); i++)//TO DO:int转string。
        {
            p << numb[i];
            string ans;
            p >> ans;
            n += ans;
            p.clear();
        }
        cout << n << endl;
        auto num = 0;
        while (num<m)//TO DO:每次找第一个降序的数字,没有就删最后一个。
        {
            auto i = n.begin();
            for (i; i != n.end() ; i++)
                if (*i < *(i + 1)||i+1==n.end())
                {
                    n.erase(i);
                    num++;
                    break;
                }
        }   cout << n;
        return 0;
    }
    
    
    

    注释都在上面了,只是把*4+5写成*5+4瞬间爆掉9个点,调了30分钟想跳楼……(只是暴力不优化效率有点低啊,最长的点要了450ms)

  • 0
    @ 2017-10-07 19:15:01

    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<vector>
    #include<queue>
    #include<stack>
    #define maxa 30000+10
    #define FOR(i,x,y) for(i=x;i<=y;++i)
    using namespace std;
    int a[maxa];
    int main()
    {
    int k,m;
    priority_queue<int,vector<int>,greater<int> > q;
    cin>>k>>m;
    int t = 1;
    q.push(1);
    while(!q.empty())
    {
    int u = q.top();
    q.pop();
    a[t++] = u;
    if(t==maxa)
    break;
    q.push(2*u+1);
    q.push(4*u+5);
    }
    string s;
    int i;
    stack<int > st;
    FOR(i,1,k){
    cout<<a[i];
    while(a[i]>0)
    {
    st.push(a[i]%10);
    a[i]/=10;
    }
    while(!st.empty()){
    s+=st.top()+'0';
    st.pop();
    }
    }
    cout<<endl;
    int tot = 0;
    while(tot<m)
    {
    for(i=0;i<s.length();++i)
    if((i+1)<s.length()&&s[i]<s[i+1])
    {
    s.erase(i,1);
    break;
    }
    if(i==s.length())
    s.erase(s.length()-1,1);
    tot++;
    }
    if(s.length())
    cout<<s<<endl;
    else
    cout<<0<<endl;
    return 0;
    }

  • 0
    @ 2009-11-04 21:52:57

    未加优化前..

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 9ms

    ├ 测试数据 05:答案正确... 150ms

    ├ 测试数据 06:运行超时...

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:运行超时...

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:80 有效耗时:159ms

    加了去9优化后...

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 25ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:25ms

    哎交了四次!!!!

  • 0
    @ 2009-10-24 17:44:06

    交表程序283KB,1200多行,交上去似乎服务器爆掉了@_@……

    const st:array[1..30000]of string=('1','3','7','9','15','17','19','31','33','35','39','41','63','65','67','71','73','79','81','83','127','129','131','135','137',………………………………'4232227','4232231','4232233','4232255','4232257','4232259','4232263','4232265','4232271','4232273','4232275','4232319','4232321','4232323','4232327','4232329','4232335','4232337','4232339','4232351','4232353','4232355','4232359','4232361','4232447');

    我晕我晕我晕我晕我晕我晕我晕我晕我晕我晕我晕我晕我晕我晕我晕我晕我晕我晕我晕

  • 0
    @ 2009-09-20 09:27:02

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    0ms的秘密:

    用线段树维护实现贪心。

  • 0
    @ 2009-08-09 14:19:13

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 88ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 244ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:332ms

    傻×了许久。。。结果还是这么慢,

    Orz LX的ipip2005。

    我直接用堆生成数。然后乱写一通。。。

  • 0
    @ 2009-07-29 14:24:09

    出题者用心良苦啊,不让元素里出现 0

    第一问用数据调整法,求出前n个数(n>30000)排序以后输出前K个就可以

    就是让所有数小于某个数maxn,maxn需要自己调整,能求出30000多个就可以,再排序就好

  • 0
    @ 2009-07-27 18:57:00

    var

    k,m,i,j,p1,p2:longint;

    tf:boolean;

    s:array [1..30000] of longint;

    num,temp:ansistring;

    begin

    p1:=1;

    p2:=1;

    tf:=false;

    s[1]:=1;

    num:='1';

    readln(k,m);

    repeat

    while 2*s[p1]+14*s[p2]+5 do

    begin

    s[p1+p2]:=4*s[p2]+5;

    str(s[p1+p2],temp);

    num:=num+temp;

    if p1+p2=k then

    begin

    tf:=true;

    break;

    end;

    p2:=p2+1;

    end;

    until tf;

    writeln(num);

    i:=0;

    j:=1;

    repeat

    i:=i+1;

    if (num[i]='9') and (m>=i-j) then

    begin

    m:=m-i+j;

    delete(num,j,i-j);

    i:=j;

    j:=j+1;

    end;

    until (mlength(num)-j+1 then

    begin

    delete(num,length(num)-m+1,m);

    writeln(num);

    halt;

    end;

    num:=num+':';

    repeat

    m:=m-1;

    i:=j;

    while num[i]>=num do i:=i+1;

    delete(num,i,1);

    until m=0;

    delete(num,length(num),1);

    writeln(num);

    end.

  • 0
    @ 2009-07-21 09:20:54

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    0秒的奥秘:用贪心算法删数的时候遇到9就跳出~~~

    为了这个0秒害我交两遍,AC率降低1%

  • 0
    @ 2009-06-27 11:45:31

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 72ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 197ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:269ms

    虽然理论复杂度很高,但实际跑起来还是很快的

  • 0
    @ 2009-06-13 17:45:37

    我一共交了9遍,九遍啊!!!!不过第一遍的时候就是80分了,然后改了又改,终于AC了。

    方法:开一个30000的长整形数组,然后从第一个开始逐个的加,并且保证是递增的:a[1]:=1;a[2]:=a[1]*2+1=3;a[3]:=a[2]*2+1=7;a[4]:=a[1]*4+5=9;... ...我们要做的是找到什么时候用p*2+1,什么时候用p*4+5,并且找到a[i];所以我们应该用两个指针,初始的时候k1:=1;k2:=1;然后逐个向后检验是a[i]*2+1大,还是a[i]*4+5大

  • 0
    @ 2009-06-12 22:38:54

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 306ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 525ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:831ms

    0ms怎么弄的?求教。

  • 0
    @ 2009-06-02 21:58:03

    为什么错????

    programme rp++;

    var

    a:array[-5..5000000] of boolean;

    s:string;

    s1:string;

    n,m,k,i,j,l,r:longint;

    begin

    readln(m,k);

    fillchar(a,sizeof(a),false);

    a[1]:=true;

    i:=1;n:=1;

    s:='1';

    while i0 do

    begin

    dec(k);

    j:=1;

    while (s[j]>=s[j+1]) and (j1) do delete(s,1,1);

    writeln(s);

    end.

  • 0
    @ 2009-06-02 18:28:03

    第一题用O(K)的解法就可以了.

    用俩指针p1,p2维护 2x+1,4x+5 的情况....

    第二题贪心.

  • 0
    @ 2009-06-01 15:34:36

    看到第一问没什么好想法,就写了平衡树……

    第二问就是一个贪心(最好用栈),注意等于的情况……

    p.s. 平衡树居然能秒闪…… Orz SBT

  • 0
    @ 2009-06-02 16:49:22

    记录-R1257351

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    原始标程。

  • 0
    @ 2009-06-01 13:38:53

    开了[4300000]的布尔数组 方便快捷

    我想也可以用堆来解决

  • 0
    @ 2009-05-31 22:56:26

    楼下好方法

  • 0
    @ 2009-05-31 20:04:03

    不会做

  • 0
    @ 2009-05-31 18:36:35

    第三个做出来的= =!

信息

ID
1545
难度
7
分类
模拟 点击显示
标签
(无)
递交数
665
已通过
126
通过率
19%
被复制
2
上传者