JS's Blog
0%

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2089

题目大意：
找出区间[n,m][n,m]内不含子串62以及4的数字个数

分析：
找不含4的数字直接在向下层dp时遇到i==4i==4的情况跳过即可，对于不含62的情况，加一个参数prepre，记录之前一个数位的情况，若之前为6，且当前要放2，则跳过，按模板dp即可

这题的数据量很小，所以直接暴力也可以，当然一般当做数位dp练手，上手可以先先试试不看模板，敲一发没有额外限制条件的dp，也就是求0−n0-n之间数字的个数，然后试着通过增加、修改条件，达成题目的要求

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <cstring>

typedef long long ll;

int dp[30][2];

int a[50],pos;

ll dfs(int pos,int pre,bool sta,bool limit)
{
    if (pos==-1)
        return 1;
    if (!limit&&dp[pos][sta]!=-1)   return dp[pos][sta];
    int up = limit?a[pos]:9;
    ll ans = 0;
    for (int i = 0 ; i <= up ; i ++)
    {
        if (pre==6&&i==2)
            continue;
        if (i==4)
            continue;
        ans += dfs(pos-1,i,i==6,limit&&i==pos[a]);
    }
    if (!limit) dp[pos][sta] = ans;
    return ans;
}


ll solve(ll n)
{
    pos = 0;
    while (n)
    {
        a[pos++] = n%10;
        n /= 10;
    }
    return dfs(pos-1,0,false,true);
}

int main()
{
    int n,m;
    memset(dp,-1,sizeof(dp));
    while (~scanf("%d%d",&n,&m)&&(n||m))
    {
        if (n>m)
        {
            n = n^m;
            m = n^m;
            n = n^m;
        }
        printf("%lld\n",solve(m)-solve(n-1));
    }
}

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1695

题目大意：
给定区间[a,b][a,b]与区间[c,d][c,d]，求两区间内各取一数gcd为k的种数，a,b{a,b}与b,a{b,a}视为同一种

分析：
由于题目给定了一个特殊条件，a=c=1，所以其实转化为了求[1,b/k][1,b/k]与[1,d/k][1,d/k]内互质数对的个数
首先一个区间内与x互质的数的个数我们可以用容斥快速的求得，而区间又不是很大，所以可以直接暴力整个区间，求所有的互质数对

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;

const ll mod = 1e9+7;

ll a,b,c,d,k;
const int maxn = 100000+10;
vector<int> ft[120005];
bool isprime[120000];

void init()
{
    for (int i = 2 ; i <= maxn ; i ++)
    {
        if (!isprime[i])
        {
            for (int j = i ; j <= maxn ; j += i)
            {
                isprime[j] = true;
                ft[j].push_back(i);
            }
        }
    }

}

ll solve(int x,int sta,ll n)
{
    int pos = 0;
    ll temp = 1;
    while (sta)
    {
        if (sta&1)
            temp *= ft[x][pos];
        pos ++;
        sta >>= 1;
    }

    return n/temp;
}



int main(){
    init();
    int T,t=1;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k);
        printf("Case %d: ",t++);
        if (k==0)
        {
            printf("0\n");
            continue;
        }
        b/=k;d/=k;

        if (b*d==0)
            printf("0\n");
        else
        {
            if (b>d)
                swap(b,d);
            ll ans = 0;
            for (int i = 1 ; i <= d ; i ++)
            {
                ans += min(i*1LL,b);
                for (int j = 1 ; j < (1<<ft[i].size()); j ++)
                {
                    ll temp = solve(i,j,min(i*1LL,b));int cp = j,cnt = 0;
                    //printf("cp = %d\t",cp);
                    while (cp)
                    {
                        cp -= cp&(-cp);
                        cnt++;
                    }
                    //printf("cnt = %d\n",cnt);
                    if (cnt&1)  ans -= temp;
                    else    ans += temp;
                }
            }
            printf("%lld\n",ans);

        }

    }



    return 0;
}

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=6053

题目大意：
给定数组A，AiA_i为BiB_i的最大取值范围，求问有多少种不同的序列B满足任意[l,r][l,r]区间内，gcd值不为1

分析：
gcd值不为1，即所有数都不互质，均拥有某个质因子，但是可以发现直接容斥的复杂度是O(105)∗O(105)=O(1010)O(10^5)*O(10^5)=O(10^{10})，显然复杂度超标，需要优化，经过学长指导，通过对Ai/pA_i/p的结果进行，分组，可以用每次一次O(log2n)O(log_2n)复杂的二分和一次O(log2n)O(log_2n)的快速幂求得一个分组的答案，每个因子均摊大约log2nlog_2n个分组，一共至多n个因子，所以总计复杂度为O(n(log2n)2)O(n(log_2n)^2)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>


using namespace std;

typedef long long ll;

const int maxn = 2e5+200;
const int mod = 1e9+7;
int n;
ll ans;

bool isprime[maxn];
ll pf[maxn];
int pn[maxn];
ll arr[maxn];


void init()
{
    memset(isprime,true,sizeof(isprime));
    for (int i = 2; i <= maxn ; i ++)
    {
        if (isprime[i])
        {
            for (int j = i ; j <= maxn ; j+= i)
            {
                if(!pf[j]) pf[j] = i;
                else    pf[j] *= i;
                pn[j]++;
                if (j!=i)   isprime[j] = false;
            }
        }
    }


}

ll qp(ll a ,int n)
{
    ll res = 1;
    while (n)
    {
        if (n&1) res= res*a%mod;
        a  = a*a %mod;
        n >>= 1;
    }
    return res;
}


ll solve(int p)
{
    int i = 1;
    ll res = 1;
    while (i<=n)
    {
        int l = i,r = n+1 ,mid;
        int x = arr[i]/p;
        while (1)
        {
            if (l==r-1)
                break;

            mid = (l+r)>>1;
            if (x==arr[mid]/p)
                l = mid;
            else
                r = mid;
        }

        res = res*qp(x,l-i+1)%mod;
        i = l +1;
    }
    return res%mod;
}


int main() {
    int T,t=1;
    init();
    scanf("%d",&T);

    while (T--)
    {
        ans = 0;
        scanf("%d",&n);
        for (int i = 1 ; i <= n ; i ++)
            scanf("%lld",&arr[i]);

        sort(arr+1,arr+n+1);
        int up = arr[1];
        for (int i = 2 ; i <= up ; i ++)
        {
            if (i!=pf[i])   continue;
            ll tmp = solve(i);
            if (pn[i]&1) ans += tmp%mod;
            else    ans -= tmp%mod;
            ans %=mod;
            ans = (ans+mod)%mod;
        }
        printf("Case #%d: %lld\n",t++,ans%mod);
    }

    return 0;
}

Posted on Edited on In ,

题目链接：
http://poj.org/problem?id=1091

题目大意：
给定N,M，有N+1个数字，最后一个必定为M，前面的数字小于等于M，跳蚤可以选择一个数字向左跳该长度，也可以向右，多次选择之后求跳蚤可以跳至左边一单位距离的位置的所有数字组合种数

分析：
顺序考虑很难想，不妨逆向思考，什么情况下跳蚤问题无解，这种问题一般很多地方都有涉及，比如换零钱，凑整之类，总之是在gcd(a1,a2,…,an)≠1gcd(a_1,a_2,\dots,a_n)\not= 1时，问题无解，所以枚举所有可以使N+1个数字不互质的可能情况种数，最后答案用mn−ansm^n-ans即可

实际上数据太水了，不然肯定是要开高精度的，光mnm^n就爆long longlong\space long了

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;

const ll mod = 1e9+7;

int n,m;
int factor[10000],cnt;
int pr[10000];


ll quickpow(ll a,ll n)
{
    ll res = 1;
    while (n)
    {
        if (n&1)    res = res*a;
        a = a *a;
        n >>= 1;
    }
    return res;
}


void factorfind(int x)
{
    cnt = 0;
    for (int i = 2 ; i * i <= x ; i ++)
    {
        if (x%i==0)
        {
            factor[++cnt] = i;
            while (x%i==0)
                x /= i;
        }
    }
    if (x!=1)
        factor[++cnt] = x;
    return;
}

ll dfs(int now,int all,int pos)
{
    if (now==all)
    {
        int x = m;
        for (int i = 1; i <= all ; i ++)
            x /= pr[i];
        return quickpow(x,n);
    }
    ll res = 0;
    for (int i = pos ; i <= cnt; i ++)
    {
        pr[now+1] = factor[i];
        res += dfs(now+1,all,i+1);

    }
    return res;
}



ll solve(int t)
{
    return dfs(0,t,1);
}





int main(){



    while (~scanf("%d%d",&n,&m))
    {
        factorfind(m);
        ll ans = 0;
        for (int i = 1 ; i <= cnt ; i ++)
        {
            ll temp = solve(i);

            if (i&1)    ans += temp;
            else    ans -= temp;
        }
        ans = quickpow(m,n)-ans;
        printf("%lld\n",ans);

    }
    return 0;
}

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=6063

题目大意：
求式子∑i=1nkμ2(i)×⌊nki⌋\sum_{i=1}^{n^k}\mu^2(i)\times\lfloor \sqrt{\frac{n^k}{i}}\rfloor的值

分析：
根据多校第三场的1008题解，任意一个数xx，可以被唯一的表示成a2×ba^2\times b的形式，其中μ2(b)=1\mu^2(b) = 1，对于小于nkn^k的每一个μ2(i)=1\mu^2(i)=1的ii来说，⌊xi⌋\lfloor \sqrt{\frac{x}{i}} \rfloor表示a2×i≤xa^2\times i \leq x的所有a的个数，由于对于每个ii，能表示出的数均不同，所以小于nkn^k的所有的ii恰好能表示出nkn^k内的所有数，所以答案就是nkn^k，快速幂即可

注意：由于n,kn,k均为101810^{18}级别，所以如果快速幂前不对n取模，过程中会爆long long

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

 
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;

typedef long long ll;
const int mod = 1e9+7;

ll quickpow(ll a,ll n)
{
    ll res= 1;
    while (n)
    {
        if (n&1)
            res = res*a%mod;
        a = a*a%mod;
        n >>= 1;
    }
    return res;
}

int main()
{
    ll n,k;
    int t = 1;
    while (~scanf("%lld%lld",&n,&k))
    {
        ll ans =quickpow(n%mod,k);
        printf("Case #%d: %lld\n",t++,ans%mod);

    }
    return 0;
}

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2204

题目大意：
给定一个数N，求1-N内有多少个数可以表示成MKM^K的形式，其中K>1

分析：
可以枚举指数进行容斥，指数最多63次，263>10182^{63}>10^{18}，然后对于含有奇数个质因子的指数加入，含有偶数个的减去，对于含有重复质因子的指数会被其他更小的指数覆盖，不用考虑

当前寻找的指数为k,也就是要找最大的满足$a^k\leq n $的数，由于上界为101810^{18}，所以在求aka^k的过程中很容易就会爆long long ，所以最好再加个限制，由于没想到什么好的办法，我打了一个表来加上限制

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
//#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;

const ll mod = 1e9+7;

int up[100];

ll n;

int divide(int x)
{
    int cnt =0;
    for (int i = 2 ; i *i <= x ; i ++)
    {
        if (x%i==0)
        {
            cnt++;
            x /= i;
            if (x%i==0)
                return -1;
        }
    }
    if (x!=1)
        cnt++;
    return cnt;
}

void init()
{
    up[2] = 1000000000;
    up[3] = 1000000;
    up[5] = 3981;
    up[6] = 1000;
    up[7] = 372;
    up[10] = 63;
    up[11] = 43;
    up[13] = 24;
    up[14] = 19;
    up[15] = 15;// 437893890380859375
    up[17] = 11;// 505447028499293771
    up[19] = 8;// 144115188075855872
    up[21] = 7;// -1261475310744950487
    up[22] = 6;// 131621703842267136
    up[23] = 6 ;//789730223053602816
    up[26] = 4;// 4503599627370496
    up[29] = 4;// 288230376151711744
    up[30] = 3 ;//205891132094649
    up[31] = 3 ;//617673396283947
    up[33] = 3 ;//-2080022246165795451
    up[34] = 3 ;//0
    up[35] = 3 ;//0
    up[37] = 3 ;//-8741818693953543755
    up[38] = 2 ;//274877906944
    up[39] = 2 ;//549755813888
    up[41] = 2;// 0
    up[42] = 2 ;//0
    up[43] = 2 ;//0
    up[46] = 2 ;//70368744177664
    up[47] = 2 ;//140737488355328
    up[51] = 2;// 0
    up[53] = 2 ;//0
    up[55] = 2 ;//0
    up[57] = 2;// 144115188075855872
    up[58] = 2 ;//288230376151711744
    up[59] = 2 ;//0
}


ll quickpow(ll a, ll n)
{
    ll res= 1;
    while (n)
    {
        if (n&1)    res= res*a;
        a = a*a;
        n >>=1;
    }
    return res;
}


ll solve(ll x)
{
    ll rt = (ll)pow(n*1.0,1.0/x);
    if (quickpow(rt,x)<=n)
    {
        while (quickpow(rt+1,x)<=n&&rt+1<=up[x])
            rt ++;
    }
    else
    {
        while (quickpow(rt,x)>n)
            rt--;
    }
    return rt-1;
}

int main(){
    init();
    int T,t=1;
    while (~scanf("%lld",&n))
    {
        ll ans = 0;
        for (int i = 2 ; i <= 63 ; i ++)
        {
            if (quickpow(2,i)>n)
                break;
            int cnt = divide(i);
            if (cnt==-1) continue;
            if (cnt&1)  ans += solve(i);
            else ans -= solve(i);
        }
        printf("%lld\n",ans+1);

    }



    return 0;
}

Posted on Edited on In ,

指针

指针的定义

指针即地址

0x3d4f | 0x3d50 | 0x3d51 | 0x3d52
—|—|—|—|—
56 | 73 | 48 | 95

上表是一个关于地址和存储空间的举例，每个地址均对应一个存储空间，或者说，计算机中每一个存储空间都有编号，用以表明位置，称为指针。

通常我们所声明的变量，都是储存在一个或多个地址拼合在一起的一块存储空间中。

指针，存放的是一个地址值，不同类型的变量有不同类型的地址值。

声明整型指针变量

野指针

1
int *p ;

这样一句代码 ， 就声明了一个int型的指针变量p，由于没有初始化，p此时称为一个野指针，对野指针的操作是非常危险的。

空指针

1
int *p = NULL;

通过这一语句，可以声明一个指向NULL的指针变量p，由于它指向的是NULL，可以认为它不指向任何地址，称为空指针（实际上一般认为指向内存地址0位，由于此地址需要极高权限操作，所以空指针一般是安全的。

取地址符

1
2
int a = 3;
int *p = &a;

通过这样一部分代码，我们定义了一个有初值的int型指针变量p，它的初值是int型变量a的地址，& 符号就是取地址符，可以获得一个变量的地址。

在p指向变量a的地址后，便可以通过(*p)取得变量p所指向的变量的值，也就是变量a的值，同时对(*p)的任何操作也会直接影响变量a。

联系C语言中的整型基本读入语句，scanf("%d",&a);这即是把从控制台窗口读入的值，写入了变量a的地址中，再加上上方的语句，此时变量p的值就是变量a的地址，所以这句语句也可以这样表达scanf("%d",p);

指针的作用

指针最常见的作用就是在参数中传递变量的地址，举例如下

传值与传地址

传值

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void Swap(int a, int b){
    int temp = a;
    a = b;
    b = temp;
    return;
}


int main(){
    int x = 5 , y = 7;
    Swap(x,y);
    cout<<x<<'\t'<<y<<endl;
}

函数的功能显然是想要交换形参a与b的值，但这是无法做到的，因为函数的形参变量是传值的，即当前的Swap函数相当于只是获得了来自调用处函数的两个整型值(5和7)，并在Swap函数内新声明了变量a和b保存这两个整型值，而不是获得了两个变量(x和y)。

传地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void Swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
    return;
}


int main(){
    int x = 5 , y = 7;
    Swap(&x,&y);
    cout<<x<<'\t'<<y<<endl;
}

以上的程序片段是可以完成交换功能的，函数的参数并不是两个整型变量，而是两个整型指针变量，传入的是两个变量x,y的地址，(*a)与(*b)是直接对变量x,y的地址所存储内容的修改

举个可能不太恰当的例子，现在有两个瓶子，一个装的是橙汁，一个装的是可乐，需要人来交换他们的内容，上面传值的函数是找来的人又弄来了两个瓶子，里面有一瓶完全一样的橙汁和一瓶完全一样的可乐，并且用第三个瓶子(temp)把他们交换了，而需要交换的两个瓶子并没有发生任何变化。

但下面传地址的函数找来的人直接找到了这两个瓶子的位置，又拿了一个瓶子(temp)过来，交换了他们的内容，这次，这两个瓶子里的内容成功交换了。

尝试

根据Swap函数，构造一个函数，能够求出传入的两个参数的和，并保存在第一个参数中带回主调函数中

更多的指针

其他类型变量的指针

之前介绍的都是int *型的指针，而C/C++有众多的类型，显然我们知道指针不止此一种，一般某种类型的变量，我们只使用此类型的指针保存它的地址，反例如下

1
2
float a = 3.1415926535;
int *p = a;

此程序段编译时就会报错，如果通过强制类型转换，把代码改为

1
2
float a = 3.1415926535;
int *p = (int *)&a;

编译便不会报错，但是由于这只是简单的把变量a的地址强制转换成了(int *)类型，地址所存储的二进制码并没有变，所以*p此时的值并不是3，而是1078530011，这其中有一些不可告人的处理转换，详情可以学习整型编码与浮点数编码

数组的指针

当我们在C/C++内声明一个数组，也就是内存中占用了一段连续的地址，长度为每个单元的长度*数组长度，继续举例

1
2
int arry[100];
int *p = arry;

由上面的程序可以发现，声明的数组名也就是这一段内存的首地址，*p即可访问arry[0]，由于上面说明数组的地址是连续的，所以可想而知
*(p+1)即可访问arry[1]，(这里的括号不可缺少，由于*的优先级高于加法运算符+，所以需要加上括号，否则相当于(*a)+1这样的一个表达式

注意 对于不同的指针类型，+1操作所跳过的地址值不同，如对于(int *)型指针 int * ptr; ptr+1将指向ptr所对应的地址后第四个位置，即增加了一个int的长度，指向了数组中或内存中下一个int型变量的地址，（由于此操作不管下面四个字节是否保存的是int，都会当做int取出，所以尽量减少对内存位置区域的改变

指针的数组

与普通数组几乎同理，只是存放的内容是地址

1
2
3
4
5
int a , b;
int * p[10];
p[0] = &a;
p[1] = &b;

指针的指针

既然指针变量本身也是一个变量，那么便可以用一个指针指向它，

1
2
3
4
5
6
7
int a;
int *x = &a;
int **y = &x;

int * p[10];
int ** q = p;

如上例，x是一个指向变量a的指针，y是一个指向int型指针的指针

而下面的两个语句，由于在上面数组的指针中提到，数组名本身就是一个指向内存中数组所在位置的首地址，所以数组名本身就是一个指针，那么指针数组的数组名也就是一个指针的指针，所以不需要取地址符便可以直接赋值给一个 指针的指针变量 q

另外，关于取地址符的反向操作，对一个地址取内容的操作符 *，是根据所给地址值，返回地址处的数据，由于指针的指针是层层指向的，所以对于这样的情况，取出地址中的值也要层层取出，对于上面的程序片段

1
2
3
int * p[10];
int ** q = p;

使用 *q可以取出q所指向变量地址处的内容，而q指向一个(int *)的指针，所以得到的还是一个指针(p[0])，再做一个运算才能得到一个int型变量，即**q

尝试

一维数组

声明一个一维数组，使用刚刚的方法，用一个指针保存数组的首地址，并用此指针存取数组中的元素

多维数组

声明一个多维数组，试着使用指针来存取多维数组的元素

多维指针数组

太复杂了，写出这种的都该判刑！

申请内存空间

调用malloc或new会返回一段在内存中申请的空间的地址，所以需要用一个指针接收

free对应 malloc申请的空间 ，delete对应 new申请的空间 ， 不可以混用

free 或 delete 后 ， 要记得把接收地址的指针变量值置为NULL

C语言 :malloc() ，free()

C++：new , delete

扩展应用

链表

用基本的struct构建一个C语言风格的链表，实现链表的创建，删除，插入节点，搜索，[倒置]，（排序）

1
2
3
4
5
struct Node{
    int data;
    Node* next;
};

树(二叉树)

根据二叉树的基本节点，创建一颗具备最基本的二叉树，附加递归等知识，实现二叉树的构建，删除，查找，三序遍历，叶节点计数

1
2
3
4
5
6
struct Node{
    int data;
    Node* leftson;
    Node* rightson;
};

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5904

题目大意：
给定两个串a,b，长度分别为n与m，求两个串的最长公共上升子序列，且子序列的值连续

n,m≤100000  a[i],b[i]≤1000000n,m\leq100000 \space \space a[i],b[i]\leq1000000

分析：
直接做显然不好做，选择dp[i]表示以i结尾的连续递增子序列的长度，dp[a[i]] = dp[a[i]-1]+1，i从1遍历到n，即可得到一个串的所有子序列，得到两个串的子序列后，遍历每个子序列，两个串的相同结尾的子序列长度取最小值，然后找最大值即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;


int a[120000],b[120000],dpa[2100000],dpb[2100000];


int main()
{
    int T,n,m;
    scanf("%d",&T);
    while (T--)
    {
        int maxn = 0 ;
        scanf("%d%d",&n,&m);
        for (int i = 1 ; i <= n ; i ++)
        {
            scanf("%d",&a[i]);
            maxn = max(maxn,a[i]);
        }
        for (int i = 1 ; i <= m ; i ++)
        {
            scanf("%d",&b[i]);
            maxn = max(maxn,b[i]);
        }
        for (int i = 0 ; i <=maxn ; i ++)
        {
            dpa[i] = 0;
            dpb[i] = 0;
        }
        int ans=0;
        for (int i = 1 ; i <= n ; i ++)
            dpa[a[i]] = dpa[ a[i] - 1 ] + 1 ;
        for (int i = 1 ; i <= m ; i ++)
            dpb[b[i]] = dpb[ b[i] - 1 ] + 1 ;
        for (int i = 0 ; i <= maxn ; i ++)
            ans = max(ans,min(dpa[i],dpb[i]));
        printf("%d\n",ans);
    }
}

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2067、
题目大意：
一个大小为n∗nn*n的棋盘，从左下角走到右下角，每次只能向上或者向右走，不能穿越对角线，一共有多少种走法
分析：
先考虑右下三角的情况，最后总数乘2即可
http://blog.sina.com.cn/s/blog_6aefe4250101asv5.html
http://www.cnblogs.com/wuyuegb2312/p/3016878.html#suggestion
http://blog.sina.com.cn/s/blog_4298002e0100eko0.html
几篇关于卡特兰数详细解释的博客
我的理解，卡特兰数主要用于解决，一个变量被另一个变量限制的问题，比如：
括号匹配，有一个右括号必然之前要有一个左括号，即在放下一个右括号之前，序列中的左括号数必须大于右括号数
再或者公园找零问题
2n个人排队买票，其中n个人持50元，n个人持100元。每张票50元，且一人只买一张票。初始时售票处没有零钱找零。请问这2n个人一共有多少种排队顺序，不至于使售票处找不开钱？
若想找的开钱，那在收100元之前，已收50元的数目必须大于100元的数目
再比如当前的问题
若要不穿越对角线，则向上走的步数必须时刻小于等于向右走的步数
第一步一定向右走，假设第k步向上走，一共要走2n2n步，同时2 k−12~k-1且k+1 2nk+1~2n也满足这个性质
卡特兰数主要有几个式子可求

h(n)=C2nnn+1h(n) = \frac{C_{2n}^n}{n+1}

h(n)=C2nn−C2nn−1h(n) = C_{2n}^n - C_{2n}^{n-1}

h(n)=h(0)∗h(n−1)+h(1)∗h(n−2)+⋯+h(n−1)∗h(0)h(n) = h(0)*h(n-1) + h(1)*h(n-2)+\cdots+h(n-1)*h(0)

这题不能使用第一二个公式，因为n≤35n\leq35过于大，C7035C_{70}^{35}的值会爆longlong 所以使用第三个公式打表即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<map>
#include <algorithm>
#define mod 1000000007
using namespace std;
typedef long long ll;
ll ctl[109]={1,1};
void init()
{
    for (int i = 1 ; i <= 36 ; i ++)
    {
        ctl[i]=0;
        for (int j = 0 ; j < i ; j ++)
            ctl[i]+=ctl[j]*ctl[i-j-1];
    }

}

int main()
{
    init();
    int n,ca=1;
    while (~scanf("%d",&n))
    {
        if (n==-1)
            break;
        printf("%d %d %I64d\n",ca++,n,2*ctl[n]);
    }
}

Posted on Edited on In ,

转自：随心所欲

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4061

题目大意：
总共有m堆牌，每堆有aia_i张数字为ii的牌，现在随机分配牌所在的堆，使每堆牌数保持不变，然后从第一堆取一张牌，数字为jj，则到第j堆取一张牌，然后循环如此做，直到下一堆要取的牌堆为空，则结束游戏，求游戏结束时所有牌堆为空的概率

思路：

分析：假设取的牌顺序是一个序列，那么这种序列在末尾为11时是和取牌序列一一对应的，且是符合“游戏结束时牌恰好被取完”的一种情况。

简证：1、在序列中，任一数$ i 的后一个数的后一个数 j$ 是必然要放在第 i 堆里的。而值为$ i 的数有的数有 a[i]$个，所以在 $i 后面的数也恰好后面的数也恰好a[i]个，所以个，所以a[i]个数被放到第个数被放到第 i $堆，符合题目约束条件。

2、在序列中，由于游戏是从第一堆开始的，所以第一个数虽然没有前驱，但是他是放在第 11 堆的。所以如果 11 不为最后一个数，那么第一堆中必然有a[1]+1a[1]+1个数了，不行。

3、序列中的最后一个数 记 i ，如果不为 11 ，那么值 ii 就只有a[i]−1a[i]-1个后继了。

4、结合2、3，易知只有最后一个数为$ 1$ ，堆容量a[i]才会都符合。才能根据此序列构造一种符合的分堆及取牌（题目原意是随机取的）情况，即一一对应。

所以至此，题目转变为NN个数的全排列，其中最后一个数为1的概率是多少。先从a[1]a[1]个11里取一个11，有a[1]a[1]种，然后剩下的N−1N-1个数全排列有(N−1)!(N-1)!种，所以总共符合有a[1]∗(N−1)!a[1]*(N-1)!种。而NN个数全排列有N!N!种。所以概率为a[1]/Na[1]/N。而N=∑a[i]N = \sum a[i]。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>
#include<cstring>
#include<algorithm>
#define I(x) scanf("%d",&x)
using namespace std;
int main(){
    int n,a,sum,t,b,ca=0;
    I(t);
    while(t--){
        I(n);
        sum=0;
        for(int i=0;i<n;i++){
            I(a);
            sum+=a;
            if(i==0) b=a;
        }
        printf("Case %d: %.6lf\n",++ca,1.0*b/sum);
    }
    return 0;
}