EXAM-2018-7-29

未完成

[ ] H
[ ] A

D

莫名TLE 不在循环里写strlen()就行了

F

相减特判水题

J

模拟一下就可以发现规律，o(n)

K

每个数加一减一不变，用map，再从-1枚举，那个数出现最多就是答案

I

通过观察我们可以发现，我们只用维护每个间断点就可以。查询的时候就从最近那个间断点出发，乘以相差的时间再判断合法性就可以了。现在的问题是如何维护间断点。因为每次查询时它的初始值是不一样的，如果每次都从原点开始肯定会T，所以我们可以维护一个合法区间，一个从0开始，一个从X开始。

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e5+7;

int s[maxn];

int main(){

    int X;

    scanf("%d",&X);

    int n;

    scanf("%d",&n);

    for(int i=1;i<=n;i++){

        scanf("%d",&s[i]);

    }

    int k,time,x;

    int t=0,j=0,l=X,r=0,stage=-1,ans,aa=0;

    scanf("%d",&k);

    for(int i=1;i<=k;i++){

        scanf("%d%d",&time,&x);

        while(j<n&&s[j+1]<=time){

            ans=stage*(s[j+1]-t);

            l=max(0,min(X,l+ans));

            r=max(0,min(X,r+ans));

            t=s[j+1];

            stage=-stage;

            j++;

            aa+=ans;

            //cout<<ans<<endl;

        }

        int num=time-t;

        x=max(r,min(l,x+aa));

        x=max(0,min(X,x+stage*(num)));

        printf("%d\n",x);

    }

    return 0;

}

B

听学长讲的这道题，感觉思路很清晰。首先游戏有三种人：正常人，僵尸，感染者；游戏结束的条件是没有正常人。然后boss每轮会让一个人变成僵尸，僵尸会让是自己倍数的玩家感染。

当初审题的时候就感觉特别乱，其实理清楚这道题就是一道普通的组合数学。如何让游戏结束，就是当RMB玩家(无法被他人感染)变成僵尸，其他的非RMB玩家可以说什么时候被感染不用去管，因为只有RMB玩家被全部变成僵尸游戏才结束。

可以得出公式，我们枚举轮数，轮数跟RMB玩家最后被感染的位置有关。我们先在该位置上放一个RMB玩家，然后前面的C(座位数,RMB玩家-1),RMB跟非RMB与顺序有关，再乘以轮数，结果就出来了

#include<bits/stdc++.h>

#define ll long long

#define met(a) memset(a, 0, sizeof(a))

using namespace std;

const int maxn=1e7+5,mod=1e9+7;

ll l,r,n,cnt,fac[maxn],inv[maxn];

bool isprime[maxn];

ll qpow(ll x,ll k){

    ll ret=1;

    while(k){

        if(k&1) ret = (ret*x)%mod;

        x = x*x%mod;

        k>>=1;

    }

    return ret;

}

void init(){

    fac[0]=1;

    for(ll i=1;i<=n+1;i++) fac[i]=(fac[i-1]*i)%mod;

    inv[n+1]=qpow(fac[n+1],mod-2);

    for(ll i=n;i>=0;i--) inv[i]=(inv[i+1]*(i+1))%mod;

    for(int i=l;i<=r;i++){

        if(!isprime[i]) cnt++;

        for(int j=i+i;j<=r;j+=i)

          isprime[j]=1;

    }

    return ;

}

ll C(ll x,ll y){

    if(!x&&!y) return 1;

    if(x<y) return 0;

    return fac[x]*inv[y]%mod*inv[x-y]%mod;

}

int main(){

    scanf("%lld%lld",&l,&r);

    n=r-l+1;

    init();

    ll ans=0;

    for(ll i=l+cnt-1;i<=r;++i){

        ans = (ans+(i-l+1)*C(i-l,cnt-1)%mod*fac[cnt]%mod*fac[n-cnt]%mod)%mod;

        //cout<<C(i-l,cnt-1)%mod*fac[cnt]%mod*fac[n-cnt]%mod<<endl;

    }

    printf("%lld\n",ans%mod);

    return 0;

}

然后这里面有一个基本的求组合数的模板：

ll qpow(ll x,ll k){

    ll ret=1;

    while(k){

        if(k&1) ret = (ret*x)%mod;

        x = x*x%mod;

        k>>=1;

    }

    return ret;

}

void init(){

    fac[0]=1;

    for(ll i=1;i<=n+1;i++) fac[i]=(fac[i-1]*i)%mod;

    inv[n+1]=qpow(fac[n+1],mod-2);

    for(ll i=n;i>=0;i--) inv[i]=(inv[i+1]*(i+1))%mod;

    //for(int i=l;i<=r;i++){

    //    if(!isprime[i]) cnt++;

    //    for(int j=i+i;j<=r;j+=i)

    //      isprime[j]=1;

    //}

    return ;

}

ll C(ll x,ll y){

    if(!x&&!y) return 1;

    if(x<y) return 0;

    return fac[x]*inv[y]%mod*inv[x-y]%mod;

}

H

现在中文题也看不懂了

题目意思是可以交换单词里的字母，从而让所给的这几个单词构建的字典树节点最少。我们先假设：

若一个单词构成字典树，则节点数为总字符数+1
若两个单词构成字典树，则节点数为两个单词总字符数-相同字符数+1
若三个或多个单词构成字典树，则节点数为多个单词总字符数-相同字符数+1？

然鹅并不是

假设三个单词：apple phy ppt 这么算的话节点数应该是11，但是正确答案是9.当apple跟ppt先组合，再与phy组合就是最优解，由此可见不能直接采用三种结合的方法。我们可以两两组合，然后再递推。从而想到状态压缩DP

准备状态压缩从零开始

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=1e6+7;

char str[maxn];

int cnt[20][200],ans[205];

int main(){

    int n,len;

    scanf("%d",&n);

    for(int i=1;i<=n;i++){

        scanf("%s",str);

        len=strlen(str);

        for(int j=0;j<len;j++){

            cnt[i][str[j]]++;

        }

    }

    int k=(1<<n)-1;

    int f[k+5];

    memset(f,0,sizeof(f));

    for(int i=1;i<=k;i++){//枚举所有状态

        memset(ans,0x3f,sizeof(ans));

        for(int j=1;j<=n;j++){

            if(i&(1<<(j-1))){

                for(int aa='a';aa<='z';aa++){

                    ans[aa]=min(cnt[j][aa],ans[aa]);//每个字母在这个状态出现最少次数

                    f[i]+=cnt[j][aa];

                }

            }

        }

        int sum=0;

        for(int aa='a';aa<='z';aa++) sum+=ans[aa];

        for(int z=i&(i-1);z;z=i&(z-1)){//状态转移 递推

            f[i]=min(f[i],f[i^z]+f[z]-sum);

        }

    }

    printf("%d\n",f[k]+1);

    return 0;

}

这里有两种枚举：

二进制枚举：

int k=(1<<n)-1;

    for(int i=1;i<=k;i++){//枚举所有状态

        for(int j=1;j<=n;j++) if(i&(1<<(j-1))){

枚举子集：

for(int z=i&(i-1);z;z=i&(z-1)){

地址EXAM-2018-7-29

巴特西

EXAM-2018-7-29

EXAM-2018-7-29

未完成

D

F

J

K

I

B

H

最新文章

热门文章