2016 Hdu 多校赛第四场

发表于   |   分类于

Hdu 5763 Another Meaning

链接

Another Meaning

题意

给定句子A和单词B，单词B可表示两种意思，问句子A可表示多少种意思

分析

令dp[i]表示到i结尾的字符串可以表示的不同含义数，那么考虑两种转移:
末尾不替换含义：dp[i-1]
末尾替换含义：dp[i-|B|] (A.substr(i-|B|+1,|B|) = B，即可匹配)
那么对于末尾替换含义的转移，需要快速判断B能不能和当前位置的后缀匹配，
kmp或者hash判断即可。直接strstr也可过。

参考代码

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
#include<stdio.h>
#include<string.h>
const int N=100010;
const int mod=1e9+7;
char s[N],t[N];
int dp[N];
bool flag[N];
int main()
{
    int T;
    scanf("%d",&T);
    for(int k=1;k<=T;k++){
        scanf("%s%s",s,t);
        int n=strlen(s);
        int m=strlen(t);
        memset(flag,false,sizeof(flag));
        for(int i=0;i<n;i++){
            if((strstr(s+i,t))==(s+i))
                flag[i+m-1]=true;
        }
        dp[0]=1;
        for(int i=0;i<n;i++){
            if(i>0)
                dp[i]=dp[i-1];
            if(flag[i]){
                if(i-m>=0)
                    dp[i]=(dp[i]+dp[i-m])%mod;
                else
                    dp[i]=2;
            }
        }
        printf("Case #%d: %d\n",k,dp[n-1]);
    }
    return 0;
}

Hdu 5768 Lucky7

链接

Lucky7

题意

求[l,r]范围内是7的倍数，同时不满足任意一个给定的同余式的数的个数。
如范围为[1,100]，不满足模3余2或模5余3的7的倍数有7,21,42,49,70,84,91 ，故答案为7.

分析

因为满足任意一组pi和ai，即可使一个“幸运数”被“污染”，我们可以想到通过容斥来处理这个问题。当我们选定了一系列pi和ai后，题意转化为求[x，y]中被7整除余0，且被这一系列pi除余ai的数的个数，可以看成若干个同余方程联立成的一次同余方程组。然后我们就可以很自然而然的想到了中国剩余定理。需要注意的是，在处理中国剩余定理的过程中，可能会发生超出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
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
#include<stdio.h>
#include<string.h>
typedef long long LL;
const int N=20;
LL m[N],a[N];
bool flag[N];
LL mulMod(LL x,LL y,LL mod)
{
    LL ans=0;
    while(y){
        if(y&1)
            ans=(ans+x)%mod;
        x=(x+x)%mod;
        y>>=1;
    }
    return ans;
}
LL exgcd(LL a,LL b,LL& x,LL& y)
{
    LL d;
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    d=exgcd(b,a%b,x,y);
    LL temp=x;
    x=y;
    y=temp-a/b*y;
    return d;
}
LL china(int n,LL l,LL r)
{
    LL M=1,x=0;
    for(int i=0;i<=n;i++)
        if(flag[i])
            M*=m[i];
    for(int i=0;i<=n;i++){
        if(!flag[i])
            continue;
        LL w=M/m[i];
        LL d,y;
        d=exgcd(m[i],w,d,y);
        y=(y%M+M)%M;
        //x=(x+y*w*a[i])%M;
        x=(x+mulMod(mulMod(y,w,M),a[i],M))%M;
    }
    x=(x+M)%M;
    LL sum=(r+M-x)/M-(l-1+M-x)/M;
    return sum;
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int k=1;k<=T;k++){
        int n;
        LL x,y;
        scanf("%d%lld%lld",&n,&x,&y);
        for(int i=0;i<n;i++){
            scanf("%lld%lld",&m[i],&a[i]);
        }
        m[n]=7;
        a[n]=0;
        flag[n]=1;
        LL tol=1<<n,ans=0;
        for(int i=0;i<tol;i++){
            int cnt=0;
            for(int j=0;j<n;j++){
                if(i&(1<<j)){
                    flag[j]=true;
                    cnt++;
                }
                else
                    flag[j]=false;
            }
            int t=(cnt&1)?-1:1;
            ans=ans+t*china(n,x,y);
        }
        printf("Case #%d: %lld\n",k,ans);
    }
    return 0;
}

Hdu 5773 The All-purpose Zero

链接

The All-purpose Zero

题意

已知一个整数序列（不小于0），其中0可以被替换成任意整数，求能得到的最长子序列的长度

分析

0可以转化成任意整数，包括负数，显然求LIS时尽量把0都放进去必定是正确的。因此我们可以把0拿出来，对剩下的数将每个权值S[i]减去i前面0的个数，再做LIS，就能保证结果是严格递增的。最后再算上0的数量。时间复杂度O(nlogn)

参考代码

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
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=100010;
int a[N];
int main()
{
    int T;
    scanf("%d",&T);
    for(int k=1;k<=T;k++){
        int n;
        scanf("%d",&n);
        int zero=0;
        a[0]=-1;
        int len=0;
        for(int i=1;i<=n;i++){
            int x;
            scanf("%d",&x);
            if(x==0)
                zero++;
            else{
                int pos=lower_bound(a,a+len+1,x-zero)-a;
                a[pos]=x-zero;
                if(pos>len)
                    len=pos;
            }
        }
        printf("Case #%d: %d\n",k,len+zero);
    }
    return 0;
}

Hdu 5774 Where Amazing Happens

链接

Where Amazing Happens

题意

已知一份获奖名单，每次询问给定一个队伍名，问其获得过几次奖

分析

先对获奖名单预处理，每次查询直接输出即可

参考代码

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
#include<stdio.h>
#include<map>
#include<string>
#include<string.h>
using namespace std;
string s[100]={
"Cleveland Cavaliers",
"Golden State Warriors",
"San Antonio Spurs",
"Miami Heat",
"Miami Heat",
"Dallas Mavericks",
"L.A. Lakers",
"L.A. Lakers",
"Boston Celtics",
"San Antonio Spurs",
"Miami Heat",
"San Antonio Spurs",
"Detroit Pistons",
"San Antonio Spurs",
"L.A. Lakers",
"L.A. Lakers",
"L.A. Lakers",
"San Antonio Spurs",
"Chicago Bulls",
"Chicago Bulls",
"Chicago Bulls",
"Houston Rockets",
"Houston Rockets",
"Chicago Bulls",
"Chicago Bulls",
"Chicago Bulls",
"Detroit Pistons",
"Detroit Pistons",
"L.A. Lakers",
"L.A. Lakers",
"Boston Celtics",
"L.A. Lakers",
"Boston Celtics",
"Philadelphia 76ers",
"L.A. Lakers",
"Boston Celtics",
"L.A. Lakers",
"Seattle Sonics",
"Washington Bullets",
"Portland Trail Blazers",
"Boston Celtics",
"Golden State Warriors",
"Boston Celtics",
"New York Knicks",
"L.A. Lakers",
"Milwaukee Bucks",
"New York Knicks",
"Boston Celtics",
"Boston Celtics",
"Philadelphia 76ers",
"Boston Celtics",
"Boston Celtics",
"Boston Celtics",
"Boston Celtics",
"Boston Celtics",
"Boston Celtics",
"Boston Celtics",
"Boston Celtics",
"St. Louis Hawks",
"Boston Celtics",
"Philadelphia Warriors",
"Syracuse Nats",
"Minneapolis Lakers",
"Minneapolis Lakers",
"Minneapolis Lakers",
"Rochester Royals",
"Minneapolis Lakers",
"Minneapolis Lakers",
"Baltimore Bullets",
"Philadelphia Warriors"
};
map<string,int> mp;
void init()
{
    for(int i=0;i<70;i++){
        mp[s[i]]++;
    }
}
int main()
{
    int T;
    init();
    scanf("%d",&T);
    getchar();
    for(int k=1;k<=T;k++){
        char t[50];
        fgets(t,50,stdin);
        int n=strlen(t);
        t[n-1]=0;
        string tmp=t;
        printf("Case #%d: %d\n",k,mp[t]);
    }
    return 0;
}

Hdu 5775 Bubble Sort

链接

Bubble Sort

题意

已知n的一个排列，问按照冒泡排序，每个数能到达的最右位置与最左位置的差

分析

考虑一个位置上的数字c在冒泡排序过程的变化情况。c会被其后面比c小的数字各交换一次，
之后c就会只向前移动。数组从右向左扫，用线段树维护一下得到每个值右边有多少个比其小的值，
加上原位置得到最右位置，最左位置为初始位置和最终位置的最小值。

参考代码

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
#include<stdio.h>
#include<string.h>
const int N=100010;
int tree[N<<2],a[N];
int _min[N],_max[N];
void pushUp(int node)
{
    tree[node]=tree[node<<1]+tree[node<<1|1];
}
void update(int l,int r,int node,int pos)
{
    if(l==r){
        tree[node]++;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid)
        update(l,mid,node<<1,pos);
    else
        update(mid+1,r,node<<1|1,pos);
    pushUp(node);
}
int query(int l,int r,int node,int ql,int qr)
{
    if(ql<=l&&r<=qr){
        return tree[node];
    }
    int mid=(l+r)>>1;
    int sum=0;
    if(ql<=mid)
        sum+=query(l,mid,node<<1,ql,qr);
    if(mid<qr)
        sum+=query(mid+1,r,node<<1|1,ql,qr);
    return sum;
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int k=1;k<=T;k++){
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            _max[a[i]]=a[i]>i?a[i]:i;
            _min[a[i]]=a[i]<i?a[i]:i;
        }
        memset(tree,0,sizeof(tree));
        for(int i=n;i>=1;i--){
            update(1,n,1,a[i]);
            if(a[i]==1) continue;
            int temp=query(1,n,1,1,a[i]-1);
            if(temp+i>_max[a[i]])
                _max[a[i]]=temp+i;
        }
        printf("Case #%d:",k);
        for(int i=1;i<=n;i++){
            printf(" %d",_max[i]-_min[i]);
        }
        printf("\n");
    }
    return 0;
}