Блог пользователя wao.uchiha

Автор wao.uchiha, 11 лет назад, По-английски

Hi all, I am currently solving a problem that must find the number of different sub seqence of a array that elements can appear more than one example 3 3 5 6. I think the answer is ((number of 1)+1)*((number of 2)+2)*... like 3 3 5 has (2+1)*(5+1)=6 different sub sequences. But it's wrong: 3 5 3 has 7 different sub sequences. Any one help me,please?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится
#include <vector>
#include <algorithm>
#include <math.h>
#include <stdio.h>
using namespace std;
int main()
{
vector<int>V;
V.push_back(3);
V.push_back(3);
V.push_back(5);
V.push_back(6);
sort(V.begin(),V.end());
int b=1;
while(next_permutation(V.begin(),V.end()))++b;
printf("%d\n",b);
}

B is 1 at first because next_permutation doesn't count sorted order. Hope this help. ;-)

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I mean that sub sequence 1 2 has 4 sub seqence {1},{1,2},{2},{}. Although that, thank you for your comment.

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

314C - Sereja and Subsequences from Codeforces Round 187 (Div. 1) needs you to do almost the same, except for subsequences must be non-decreasing and you are to output sum of product of all such subsequences. Try reading the editorial (though it did not help me) or accepted codes.
Hope it helps.

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

oh yeah! I found it. @NiVeR: N<=10^5, and element is not important.

here is brute code:

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>

#define rep(i,n) for(int i=0,_n=(n);i<_n;++i)
using namespace std;

typedef vector<int> VI;
set<VI> f;
VI a;
int n,s[100],dp[100];

int main(){
    cin>>n;
    rep(i,n) cin>>s[i];
    rep(i,1<<n){
        a.clear();
        rep(j,n) if (i&(1<<j)) a.push_back(s[j]);
        f.insert(a);
    }
    cout<<f.size()<<'\n';
    return 0;
}

But i has a O(N) solution: We have a1a2...,an the sub sequence that have a[i] is f[i] if a[i] appear before f[i]=sum(f[j],j=1..i-1) if a[i] is first appear f[i]=sum(f[j],j=1..i-1)+1 The result is sum(f[j],j=1..n)+1. P/s: sorry, it's wrong.