题解

131 条题解

  • 4
    @ 2017-07-09 15:24:07

    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    using namespace std;
    int n,m,a[100001];
    main()
    {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)next_permutation(a,a+n+1);
    for(int i=1;i<=n;i++)printf("%d ",a[i]);
    }

  • 2
    @ 2017-08-24 21:28:18

    next_permuration!
    #include<iostream>
    #include<cmath>
    #include<vector>
    #include<set>
    #include<bitset>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<deque>
    #include<ctime>
    #include<queue>
    #define mp make_pair
    using namespace std;
    inline long long stoi(string s){
    long long rt=0;
    for(int i=0;i<s.size();i++) rt=rt*10+s[i]-'0';
    return rt;
    }
    inline string itos(long long x){
    string rt="";
    while(x){
    rt+=(char)(x%10+'0');
    x/=10;
    }
    reverse(rt.begin(),rt.end());
    return rt;
    }
    const int INF=1000000009;
    int a[10005],n,m;
    int main(){
    cin>>n>>m;
    int i,j;
    for(i=0;i<n;i++) cin>>a[i];
    for(i=0;i<m;i++) next_permutation(a,a+n);
    for(i=0;i<n;i++) cout<<a[i]<<' ';
    return 0;
    }

  • 2
    @ 2017-07-04 09:34:10
    //离散书上的经典算法,《离散数学及其应用》P436
    #include <iostream>
    #include <algorithm>
     using namespace std;
    int main()
    {
        std::ios::sync_with_stdio(false);
        int arr[10005];
        int N, M;
        int j, k, r, s;
        cin >> N >> M;
        for(int i = 0; i < N; i++)
            cin >> arr[i];
        while(M--)
        {
            j = N - 2;
            while(arr[j] > arr[j+1])
                j--;
            k = N - 1;
            while(arr[k] < arr[j])
                k--;
            swap(arr[k], arr[j]);
            r = N - 1;
            s = j + 1;
            while(r > s)
            {
                swap(arr[s], arr[r]);
                r--; s++;
            }
        }
        for(int i = 0; i < N; i++)
            cout << arr[i] << " ";
        cout << endl;
        return 0;
    }
    
  • 0
    @ 2018-08-07 08:08:59
    #include <bits/stdc++.h>
    using namespace std;
    #define FOR(i,n) for (int i=1;i<=n;i++)
    #define REP(i,a,b) for (int i=a;i<=b;i++)
    #define pb push_back
    #define mp make_pair
    #define ll long long
    const int N=10000+10;
    const int inf=0x3f3f3f3f;
    const ll mod=7654321;
    const double PI=3.1415926;
    const double eps=1e-8;
    
    int n,m;
    int a[N];
    void next(int a[]) {
        int pos=1;
        REP(i,2,n) if (a[i]>a[i-1]) pos=i;
        if (pos==1) return;
        int pos2=0;
        REP(i,pos,n) {
            if (a[i]>a[pos-1]&&(pos2==0||a[i]<a[pos2])) {
                pos2=i;
            }
        }
        swap(a[pos2],a[pos-1]);
        sort(a+pos,a+1+n);
        /*
        FOR(i,n) cout<<a[i]<<" ";
        cout<<endl;
        */
    }
    int main() {
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
        cin>>n>>m;
        FOR(i,n) cin>>a[i];
        while (m--) next(a);
        FOR(i,n) cout<<a[i]<<" ";
        cout<<endl;
        return 0;
    }
    
  • 0
    @ 2018-02-06 09:47:51
    #include<cstdio>
    #include<algorithm>
    int a[10010];
    int main() {
        int n, m;
        scanf("%d%d", &n, &m);
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        while(m--) std::next_permutation(a+1, a+n+1);
        for(int i=1; i<n; i++) printf("%d ", a[i]);
        printf("%d", a[n]);
        return 0;
    }
    
  • 0
    @ 2017-07-23 13:51:56

    !刷题并不重要,重要的是理解!
    祝大家 RP+++

    #include <iostream>
    #include <algorithm>
    using namespace std;
    int a[10005],
        n,m;
    int main()
    {
        ios::sync_with_stdio(false); //iostream 加速开关
        cin >> n >> m; //INPUT
        for(int i=0; i<n; i++)
            cin >> a[i];
        for(; m--;) // 循环m次
            next_permutation(a,a+n); // C++STL 下一个排列
        for(int i=0; i<n; i++) // OUTPUT
            cout << a[i] << ' ';
        cout << endl;
    }
    
  • 0
    @ 2017-05-08 08:01:39

    直接调用STL就好啦~
    当然要认真地写常规算法也是可以的

    #include <iostream> 
    #include <algorithm>
    using namespace std; 
    int n,m,martian[10001]; 
    
    void print()  
    {
      for(int i=0;i<n-1;i++) 
        cout<<martian[i]<<' '; 
      cout<<martian[n-1]<<"\n";   
    }
    
    int main()   
    {   
      cin>>n>>m;
      for(int i=0;i<n;i++)
        cin>>martian[i];
      for(int i=1;i<=m;i++)
        next_permutation(martian,martian+n);     
      print();
      return 0; 
    }
    
  • 0
    @ 2014-08-16 20:33:59

    var
    n,k,i,ans:longint;
    a:array[1..10000] of longint;

    procedure qsort(l,r:longint);
    var
    i,j,mid,t:longint;
    begin
    i:=l;
    j:=r;
    mid:=a[(l+r) div 2];
    repeat
    while a[i]<mid do inc(i);
    while a[j]>mid do dec(j);
    if i<=j then
    begin
    t:=a[i];
    a[i]:=a[j];
    a[j]:=t;
    inc(i);
    dec(j);
    end;
    until i>j;
    if l<j then qsort(l,j);
    if i<r then qsort(i,r);
    end;

    procedure try(p:longint);
    var
    i,k,l,j,t:longint;
    t1:boolean;
    begin
    if ans=0 then
    begin
    for i:=1 to n-1 do
    write(a[i],' ');
    writeln(a[n]);
    halt;
    end;
    for i:=n-1 downto p+1 do
    begin
    t1:=true;
    while t1 do
    begin
    t1:=false;
    l:=maxlongint;
    k:=0;
    for j:=i+1 to n do
    if (a[j]>a[i]) and (a[j]<l) then
    begin
    l:=a[j];
    k:=j;
    end;
    if k<>0 then
    begin
    t:=a[i];
    a[i]:=a[k];
    a[k]:=t;
    t1:=true;
    qsort(i+1,n);
    dec(ans);
    try(i);
    end;
    end;
    end;
    end;

    begin
    readln(n);
    readln(k);
    for i:=1 to n do
    read(a[i]);
    ans:=k;
    try(0);
    end.//By Fkc

  • 0
    @ 2014-08-15 14:05:54

    #include<algorithm>
    #include<iostream>
    using namespace std;
    main()
    {
    int i,n,m,a[10001];
    cin>>n>>m;
    for(i=1;i<=n;i++)
    cin>>a[i];
    for(i=1;i<=m;i++)
    next_permutation(a+1,a+n+1);
    for(i=1;i<=n;i++)
    cout<<a[i]<<' ';
    }
    跟楼下一个方法。

  • 0
    @ 2014-08-15 14:02:26

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    int n,m,a[10001];
    main()
    {
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    cin>>a[i];
    for (int i=1;i<=m;i++)
    next_permutation(a+1,a+n+1);
    for (int i=1;i<=n;i++)
    cout<<a[i]<<' ';
    }
    algorithm函数库真心强大。连求下一个排列的函数都有。2004T4,15行代码秒杀!next_permutation万岁~

  • 0
    @ 2014-07-11 12:27:34

    var
    a:array[1..10000]of longint;
    n,m,i,j,k,t,l:longint;
    procedure swap(var a,b:longint);
    var t:longint;
    begin
    t:=a;a:=b;b:=t;
    end;
    procedure quicksoft(l,r:longint);
    var
    x,y,mid:longint;
    begin
    mid:=a[(l+r)div 2];x:=l;y:=r;
    repeat
    while a[x]<mid do inc(x);
    while a[y]>mid do dec(y);
    if x<=y then begin swap(a[x],a[y]);inc(x);dec(y);end;
    until x>y;
    if x<r then quicksoft(x,r);
    if l<y then quicksoft(l,y);
    end;
    begin
    read(n,m);
    for i:=1 to n do read(a[i]);
    for i:=1 to m do
    for j:=n downto 2 do
    if a[j-1]<a[j] then
    begin
    t:=maxlongint;
    for k:=j to n do if (a[k]<t)and (a[k]>a[j-1]) then
    begin t:=a[k];l:=k;end;
    swap(a[j-1],a[l]);
    quicksoft(j,n);

    break;
    end;
    for i:=1 to n do write(a[i],' ');
    end.

  • 0
    @ 2014-04-30 21:22:03

    #include <iostream>
    #include <algorithm>
    #include <vector>

    using namespace std;

    int main()
    {
    int n,m,temp;
    cin >> n >> m;
    vector<int> p;
    for(int i=0;i<n;i++){
    cin >> temp;
    p.push_back(temp);
    }
    for(int i=0;i<m;i++) next_permutation(p.begin(),p.end());
    vector<int>::iterator j;
    for(j=p.begin();j!=p.end();j++) cout << *j <<" ";
    //cout << "Hello world!" << endl;
    return 0;
    }

    Orz下面所有的神牛。我什么都不懂,我只知道algorithm里面有个叫作next permutation的东西。。。

  • 0
    @ 2014-01-17 09:41:02

    var
    f,g:array[1..10001] of integer;

    n,m,i,j,k,tt,p,q,c:integer;

    procedure arraya;
    begin
    for p:=1 to n-i-1 do
    for q:=p+1 to n-i do
    if g[p]>g[q] then
    begin
    k:=g[p];
    g[p]:=g[q];
    g[q]:=k;
    end;
    end;

    begin
    readln(n);
    readln(m);
    for i:=1 to n do read(f[i]);
    tt:=m;
    while tt>0 do
    begin
    for i:=n downto 1 do
    if f[i]<f then break;
    c:=20000;
    for j:=i+1 to n do
    if (f[j]<c) and (f[j]>f[i]) then
    begin c:=f[j]; k:=j; end;
    c:=f[i];
    f[i]:=f[k];
    f[k]:=c;
    for j:=i+1 to n do g[j-i]:=f[j];
    arraya;
    for j:=i+1 to n do f[j]:=g[j-i];
    dec(tt);
    end;
    for i:=1 to n-1 do
    write(f[i],' ');
    writeln(f[n]);
    end.

  • 0
    @ 2013-12-28 12:35:51

    编译成功

    测试数据 #0: Accepted, time = 62 ms, mem = 540 KiB, score = 10
    测试数据 #1: Accepted, time = 15 ms, mem = 540 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 544 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 544 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 540 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 544 KiB, score = 10
    Accepted, time = 92 ms, mem = 544 KiB, score = 100

  • 0
    @ 2013-11-06 08:47:17

    #include <iostream>
    #include <algorithm>
    using namespace std;
    #define MAX 10001
    int a[MAX],n,m;

    void fun()
    {
    int i,c=0,d=0,min;
    for(i=n;i>1;i--)
    if(a[i-1]<a[i])
    {

    break;
    }
    c=i-1;
    int v=1;
    if(i!=n)
    {
    for(;i<=n;i++)
    {
    if(a[c]<a[i] )
    {

    if(v)
    {
    min=a[i];
    d=i;
    v=0;
    }
    else if(a[i]<min)
    {
    min=a[i];
    d=i;
    }
    }
    }
    }
    else
    d=n;
    // cout<<"a[c] "<<a[c]<<" a[d]"<<a[d]<<endl;
    int tem=a[c];
    a[c]=a[d];
    a[d]=tem;

    sort(a+c+1,a+n+1);

    }
    int main()
    {
    int i;
    while(cin>>n>>m)
    {
    for(i=1;i<=n;i++)
    cin>>a[i];
    for(i=1;i<=m;i++)
    fun();
    for(i=1;i<n;i++)
    cout<<a[i]<<" ";
    cout<<a[i]<<endl;
    }
    return 0;
    }

  • 0
    @ 2013-10-20 21:26:00

    手动生成1-10000的排列肯定超时,而M才100,我们只要掌握生成任意一个排列的下一个即可;
    通过自己模拟+2、+3等,就可知排列每次肯定都减少一个最靠近右侧的逆序对,如有A[J-1]《A[J],那A[J-1]一定得更新了,因为不可能不变这个A[J-1]却还可以生成下一个排列(慢慢理解其实很简单)。而代替这个A[J-1]的是什么呢,那肯定也是A[J]-A[N]里面大于A[J-1]且最小的一个A[K];然后对A[J]-A[N]排下序即是下一个排列;
    如1 2 3 5 4,j-1为第3个3,则K为第5个4,交换后为1 2 4 5 3,然后再排序为1 2 4 3 5,这就是下一个排列。

  • 0
    @ 2013-09-15 15:08:15

    我记得去年做这题,根本看不懂。。现在一看这么简单

    因为n大,以前是想直接dfs,所以不会做。但是今天又看了看题目,觉得很水。

    虽然n这么大,但是m只有100.纯粹模拟n,有很多时间是浪费。

    可以直接用生成法。//so easy

    生成法的原理:

    1、j从最后往前面搜,找到第一个a[j-1]<a[j].

    2、在从a[j]-a[n]中找到一个大于a[j-1]的最小数a[k]

    3、swap(a[j-1],a[k])

    4、qsort(j,n),使他们从小到大排序。

    这样一个排列就生成,如此做m次后,就是最后的答案!

    经过一年的训练,能力增强。冲刺2013NOIp普及组一等!

    SYF

    想看跟详细的题解和程序。点 题解

    想一起探讨Oi的孩纸门,可加QQ 841249284 峰哥,写明备注,欢迎所有人!

    • @ 2014-07-10 17:39:57

      var
      n,m,i,j,t,k:longint;
      a:array [0..10010] of longint;

      procedure qsort(l,r:longint);
      var
      u,e,mid,p:longint;
      begin
      u:=l; e:=r;
      mid:=a[(u+e)div 2];
      repeat
      while a[u]<mid do u:=u+1;
      while a[e]>mid do e:=e-1;
      if u<=e then
      begin
      p:=a[u]; a[u]:=a[e]; a[e]:=p;
      u:=u+1; e:=e-1;
      end;
      until u>e;
      if l<e then qsort(l,u);
      if u<r then qsort(e,r);
      end;

      begin
      readln(n); readln(m);
      for i:=1 to n do
      read(a[i]);
      for i:=1 to m do
      begin
      for j:=n downto 2 do
      if a[j]>a[j-1] then break;
      k:=j-1; t:=a[k+1];
      for j:=k+1 to n do
      if (a[j]<t) and (a[j]>a[k]) then t:=a[j];
      a[j]:=a[k]; a[k]:=t;
      qsort(k+1,n);
      end;
      for i:=1 to n do
      write(a[i],' ');
      end.
      大神能帮我看看哪出问题了么,,,这个程序只有20分。。。。

  • 0
    @ 2013-08-23 08:30:46

    字典序法编程容易实现,而且求某个排列的下一个排列好使。

    方法就是
    如:2341
    第一步:连续两数,满足左边<右边,并且要最靠右的,这里是34,记左边的下标为u.
    编程的时候从右往左扫描,找到就BREAK.
    第二步:以u位置的数3为准,找最靠右的大于它的数4。
    把3,4互换,得到2431;
    第三步:把u位置后面的数,反序.

    2341->2431->2413

    完毕.[感谢notblack大神提供思路]

    #include<iostream>
    using namespace std;
    int main()
    {
    int n,m,i,j,k,l,t,h,a[20001],x;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    cin>>a[i];
    for(i=1;i<=m;i++)
    {
    for(j=n;j>1;j--)
    if(a[j]>a[j-1])
    break;
    h=j-1;
    for(l=n;l>1;l--)
    if(a[l]>a[h])
    break;
    k=a[l];a[l]=a[h];a[h]=k;
    for(x=1;x<=n;x++)
    a[x+n]=a[x];
    for(t=2*n;h+1<=n;h++,t--)
    a[h+1]=a[t];
    }
    for(i=1;i<n;i++)
    cout<<a[i]<<" ";
    cout<<a[n];
    system("pause");
    return 0;
    }

  • 0
    @ 2013-04-04 09:59:44

    这题一开始我想深搜成全排列,看看10000个手指就傻了。楼下那位大牛的题解让我豁然开朗,其实最多只需100次循环了,跟M有关。加油、加油!!
    var i,j,n,k,m,c,w,t:longint;
    a,b:array[1..10000]of longint;
    procedure swap(var a,b:longint);
    begin
    c:=a;
    a:=b;
    b:=c;
    end;
    begin
    readln(n);
    readln(m);
    for i:=1 to n do read(a[i]);
    for i:=1 to m do begin
    w:=n;while a[w-1]>a[w] do dec(w);
    w:=w-1;
    for j:=n downto w+1 do if a[j]>a[w] then begin
    t:=j;
    break;
    end;
    swap(a[w],a[t]);k:=n;
    for j:=w+1 to n do b[j]:=a[j];
    for j:=w+1 to n do begin
    a[k]:=b[j];
    dec(k);
    end;
    end;
    write(a[1]);
    for i:=2 to n do write(' ',a[i]);writeln;
    end.

  • 0
    @ 2010-07-16 19:35:19

    var

    f,g:array[1..10001] of integer;

    n,m,i,j,k,tt,p,q,c:integer;

    procedure arraya;

    begin

    for p:=1 to n-i-1 do

    for q:=p+1 to n-i do

    if g[p]>g[q] then

    begin

    k:=g[p];

    g[p]:=g[q];

    g[q]:=k;

    end;

    end;

    begin

    readln(n);

    readln(m);

    for i:=1 to n do read(f[i]);

    tt:=m;

    while tt>0 do

    begin

    for i:=n downto 1 do

    if f[i]

信息

ID
1115
难度
3
分类
组合数学 点击显示
标签
递交数
3116
已通过
1593
通过率
51%
被复制
1
上传者