Celery's Blog

0%

挑战程序设计竞赛-day7

发表于 Valine：

字符串Hash

字符串Hash用于判断两个字符串是否相同.

字符串Hash函数的构造：

设长度为mm的字符串ss为H(s)H(s)，则H(s)=(s1∗basem−1+s2∗basem−2+...+sm∗base0)%modH(s) = (s_1 * base^{m - 1} + s_2 * base^{m -2} + ... + s_m * base^{0}) \% mod

其中ss一般取1-26或1-52， base取自己喜欢的质数，比如131，mod取2147483647或者可以使用unsigned long long。unsigned lng long可以支持自然溢出。

字符串Hash的性质：

  • H(c,k)=H(c,k−1)∗base+ckH(c, k) = H(c, k -1) * base + c_k

    有了这个性质，我们就可以通过地推求解字符串的字符串Hash值

  • H(k+1,n+k)=H(c,k+n)−H(c,k)∗basenH(k + 1, n + k) = H(c, k + n) - H(c, k) * base^{n}

    推导：

    H(k+1,n+k)=sk+1∗baselen1−1+sk+2∗baselen1−2+...+sn+k∗base0,len1=nH(k +1, n+k) = s_{k + 1} * base^{len_1 - 1} + s_{k+2}*base^{len_1 - 2} + ... + s_{n + k} * base^0, len1 = n

    H(c,n+k)=sc∗baselen2−1+sc+1∗baselen2−2+...+sn+k∗base0,len2=n+k−c+1H(c, n + k) = s_c * base^{len_2 - 1} + s_{c + 1} * base^{len_2 - 2} + ... + s_{n+k} * base^0, len2 = n + k - c + 1

    H(c,k)=sc∗baselen3−1+sc+1∗baselen3−2+...+sk∗base0,len3=k−c+1H(c, k) = s_c * base^{len_3 - 1} + s_{c + 1} *base^{len_3 - 2} + ... + s_k*base^{0}, len3 = k - c + 1

    所以，综上$H(k+1, n+k) =H(c, k + n) - H(c, k) * base^{n} $

RK-Hash

  • 自然溢出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int bs = 131;
uLL base[N], h[N];
void RKHash(char *s) {
    int n = strlen(s + 1);
    h[0] = 0;
    base[0] = 1;
    for(int i = 1; i <= n; i++) {
        h[i] = h[i - 1] * bs + s[i];
        base[i] = base[i - 1] * bs;
    }
}

uLL getHash(int l, int r) {
    return (h[r] - h[l - 1] * base[r - l + 1]);
}

  • 取modmod

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    struct HASH {
        int bs, mod;
        int base[N], h[N];
        HASH(int bs, int mod):bs(bs), mod(mod) {}
        void init(int n) {
            base[0] = 1;
            for(int i = 1; i <= n; i++) {
                base[i] = base[i - 1] * bs % mod;
            }
        }
        void RKHash(char *s) {
            int n = strlen(s + 1);
            h[0] = 0;
            for(int i = 0; i <= n; i++) {
                h[i] = ((LL)h[i - 1] * bs + s[i]) % mod;
            }
        }
        int getHash(int l, int r) {
            return (h[r] - (LL)h[l - 1] * base[r - l + 1] % mod + mod) % mod;
        }
    }H(233, 1000173169), H2(131, 9999991);

POJ 1065 Wooden Sticks

大意：这个题目定义了一种偏序关系≤

(L1, W1)≤(L2, W2)当且仅当L1<=L2且W1<=W2

给的输入就是一个偏序集，目标就是把这个偏序集划分为一系列chain，并要求chain的个数尽可能少

思路：首先按照L对输入的偏序集进行排序，然后观察W，看最少能分离出多少单调递增（非严格）的子序列。

这里还采用了一种非常巧妙的做法，就是利用栈。

假设排序后，W序列为：4 1 5 9 2

那么我们当前的输入值比栈顶的值大，就入栈，如果比栈顶的值小，就找栈中最大的但是比当前值小的值进行更改，改为当前值。

具体在实现的时候采用了lower_bound，这个是STL中的函数，使用二分查找实现的。

lower_bound( begin,end,num,greater<type>() ) : 从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标.

所以，经过这一波操作之后，dp数组就会变成:

1
2
3
4
5
4
4 1
5 1
9 1
9 2

因此，最终找到比-1大的最小的元素就是2，其位置也是2，故最少分成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
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
const int N = 5010;
int n;
struct node {
    int w;
    int l;
};

bool cmp(const node &a, const node &b) {
    if(a.l == b.l) {
        return a.w < b.w;
    }
    return a.l < b.l;
}

node wood[N];
int dp[N];

void solve() {
    memset(dp, -1, sizeof(dp));
    for(int i = 1; i <= n; i++) {
        *lower_bound(dp, dp + n, wood[i].w, greater<int>()) = wood[i].w;
    }
    printf("%d\n", lower_bound(dp, dp + n, -1, greater<int>()) - dp);
}

int main() {
    int num;
    scanf("%d", &num);
    for(int i = 0;i < num; i++) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d%d", &wood[i].l, &wood[i].w);
        }
        sort(wood + 1, wood + n + 1, cmp);
        solve();
    }
}

POJ 3336 Making the grade

大意：给定一个序列，以最小代价将其变成单调不增或单调不减序列

dp[i][j]表示将前i个数字变成最大值为j的单调序列所需要用的最小代价

显然：dp[i][j] = min(dp[i - 1][k] + abs(j - w[i])), k <= j

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 2010;
// const int MAXA = 1000000010;
// const long long inf = (1 << 60);
int n;
int a[MAXN], b[MAXN];
ll dp[MAXN][MAXN];

void solve() {
    for(int i = 1; i <= n; i++) {
        long long mn = dp[i - 1][1];
        for(int j = 1; j <= n; j++) {
            mn = min(mn, dp[i - 1][j]);
            dp[i][j] = mn + abs(a[i] - b[j]);
        }
    }
    long long ans = dp[n][1];
    for(int i = 1; i <= n; i++) {
        ans = min(ans, dp[n][i]);
    }
    printf("%lld\n", ans);
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    solve();
    return 0;
}

POJ 2184 Cows Exhibition

大意：每行给出si和fi，代表牛的两个属性，然后要求选出几头牛，是的则求出总S与总F的和，注意S与F都不能为负数

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<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=110;
int dp[200010];
int value[MAXN];
int weight[MAXN];
int nKind;
int main()
{
    int k=100000;
    while(scanf("%d",&nKind)!=EOF)
    {
        for(int i=0;i<nKind;i++)
        {
            scanf("%d%d",&value[i],&weight[i]);
        }
        for(int i=0;i<=200000;i++)dp[i]=-INF;
        dp[k]=0;
        for(int i=0;i<nKind;i++)
        {
            if(value[i]>0)//正的是逆序
            {
                for(int j=200000;j>=value[i];j--)//注意范围
                  if(dp[j-value[i]]>-INF)
                    dp[j]=max(dp[j],dp[j-value[i]]+weight[i]);
            }
            else//负的是顺序
            {
                for(int j=0;j<=200000+value[i];j++)//注意范围
                  if(dp[j-value[i]]>-INF)
                    dp[j]=max(dp[j],dp[j-value[i]]+weight[i]);
            }
        }
        int ans=0;
        for(int i=100000;i<=200000;i++)
            if(dp[i]>=0&&dp[i]+i-100000>ans)
                ans=dp[i]+i-100000;
        printf("%d\n",ans);
    }
    return 0;
}