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