3月11日"考试"总结

你都没考你总结啥

---

T1

正解

对于01串 \(a\) , 我们在它后面加'0'

并定义其异或序列 : \(b\) , 有 \(b_{i}=a_{i} \oplus a_{i-1}\)

那么 , 每个\(a\)都有唯一的\(b\)与之对应

现在\(a\)的匹配变为\(b\)的匹配 , \(a\)的区间翻转变为\(b\)的两个位置的翻转

考虑怎么匹配 , 发现范围内的\(T\)的长度只有根号种

然后对于一个长度的\(T\) , 我们可以把\(S\)"折起来"计算

复杂度大概是\(n \sqrt n\)级别的 \(O(\)可过\()\)

上代码 :

#include
    
     #define MAXN(a) ((max##a)+10)using namespace std;const int maxn=200000,maxm=20000000;struct str{    int *p,tag; str *next;    str(){tag=0,p=NULL,next=NULL;}    ~str(){}};int n,m,tail,sed;int s[MAXN(n)];int t[MAXN(m)];int p[MAXN(m)];int cnt[2][MAXN(n)];int ans[MAXN(m)];str *beg[MAXN(m)];inline void init(){    {        char k=getchar();int las=0;        while(k!='a'&&k!='b')k=getchar();        while(k=='a'||k=='b'){            s[++n]=((k=='b')^las);            las=(k=='b'),k=getchar();        }s[++n]=sed=las;    }    scanf("%d",&m);    for(int i=1;i<=m;i=-~i){        char k=getchar();        while(k!='a'&&k!='b')k=getchar();        int len=0;str *now=new str();        now->p=t+tail;now->tag=i;        while(k=='a'||k=='b')            now->p[++len]=(k=='b'),k=getchar();        tail+=len;now->next=beg[len],beg[len]=now;    }    return;}inline void pre_work(int len){    memset(cnt,0,sizeof(cnt));    int ed=(n-1)/len*len+1;    for(int i=len+1;i< ed;i++)        cnt[s[i]][(i-1)%len+1]++;}inline void calc(str *st,int len){    int &Ans=ans[st->tag];    if(len+1
     
      p[1];        for(int i=2;i<=len;i=-~i)            p[i]=st->p[i]^st->p[i-1];        for(int u=1;u<=len;u=-~u)            Ans+=(s[u]!=p[u]);        p[1]=st->p[1]^st->p[len];        for(int k=1;k<=len;k=-~k)            Ans+=cnt[p[k]^1][k];        for(int u=ed;u<=n-1;u=-~u)            Ans+=(s[u]!=p[u-ed+1]);        Ans+=(st->p[(n-2)%len+1]!=sed);    }    else {        p[1]=st->p[1];        for(int i=2;i<=n-1;i=-~i)            p[i]=st->p[i]^st->p[i-1];        p[n]=st->p[n-1];        for(int u=1;u<=n;u=-~u)            Ans+=(s[u]!=p[u]);    }    return;}int main(){#ifndef ONLINE_JUDGE    freopen("string.in","r",stdin);    freopen("string.out","w",stdout);#endif    init();    int cnt=0;    for(int i=1;i<=tail;i=-~i){        if(beg[i]==NULL)continue;        //printf("%d %d %d\n",n,i+1,n%(i+1));        pre_work(i);str *u=beg[i];        while(u!=NULL)            calc(u,i),u=u->next;    }    for(int i=1;i<=m;i=-~i)        printf("%d\n",(ans[i])>>1);    return 0;}
     
    

---

T2

得分情况 :

预计分数 : 15pts

实际得分 : 15pts

暴力搜就完事了

正解 :

先考虑"已知"从\(1\)到\(n\)花费的时间的期望 , 设为\(l\)

那么有DP式 :

\[ f[u][j]=\frac{(\sum min( f[v][j-d[v]],H-(j-d[v])+l) )}{ot[u]}+1 \]

\(min\)里头那坨的意义是 , 你从\(u\)出发到\(v\) , 要么继续从\(v\)走 , 要么从\(v\)返回至起点

而返回至起点后 , 你需要在起点呆 \(H-(j-d[v])\) 的时间回血 , 然后用\(l\)的时间到\(n\)

知道了这个好像没啥用 , 题目要求的就是 \(l\) 的值

但我们发现有了这个后 , \(l\)就可以二分了

因为对于一个二分出的\(l\) , 如果它比\(l_{ans}\)大的话 , 一定有\(f[1][H]< l\)

完事 , 复杂度\(O(n^3*log_2n)\) , 可过

Code :

inline bool check(ldb limt){    for(int i=1;i< n;i=-~i)        for(int j=1;j<=H;j=-~j)            f[i][j]=inf;    for(int u=n-1;u>=1;u--){        for(int j=mx[u]+1;j<=H;j=-~j){            ldb res=0;if(!ot[u])continue;            for(int i=head[u];i;i=e[i].next){                int v=e[i].v;                res+=min(f[v][j-d[v]],H-(j-d[v])+limt);            }f[u][j]=(res/(ldb)ot[u])+1;        }    }return f[1][H]< limt;}int main(){    r(n),r(m),r(H);    for(int i=1;i<=m;i=-~i){        int r(u),r(v);add(u,v);    }    for(int i=1;i<=n;i=-~i)r(d[i]);    for(int u=1;u<=n;u=-~u)        for(int i=head[u];i;i=e[i].next)            mx[u]=max(mx[u],d[e[i].v]);    ldb l=0,r=2000000,ans=0;    while(l+eps<=r){        ldb mid=(l+r)/2;        if(check(mid))            r=mid-eps,ans=mid;        else l=mid+eps;     }    if(ans>=1000000)puts("-1");    else printf("%.6Lf",ans);    return 0;}

---

T3

正解

天上第一的找规律大师发现了规律

我太菜了 , 只能抄他的代码维持生活

所以具体题解看

代码(抄的他的) :

#include
    
     #define r(a) (a)=read
     
      ()#define rl(a) (a)=read
      
       ()#define MAXN(a) ((max##a)+10)using namespace std;typedef long long ll;const int maxk=5000;const int mod=1e9+7;namespace Math{    int C[MAXN(k)][MAXN(k)];    inline ll quick_pow(ll a,ll b){        ll ans=1;a%=mod,b%=(mod-1);        while(b){            if(b&1)ans=ans*a%mod;            a=a*a%mod,b>>=1;        }return ans;    }    inline ll inv(ll a){return quick_pow(a,mod-2);}    inline void init(){        for(int i=0;i<=maxk;i=-~i)            for(int j=0;j<=i;j=-~j)                if(j==0||i==j)C[i][j]=1;                else C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;    }}using Math::C;using Math::inv;using Math::quick_pow;int K,R_,inv_;ll n,R;int n_[MAXN(k)];int s[MAXN(k)];int S(int k){    if(s[k])return s[k];    int res=1ll*n_[k]*R_%mod,det=0;    for(int i=1;i<=k;i=-~i){        det=1ll*C[k][i]*S(k-i)%mod;        res=(res+((i&1)?-1ll:1ll)*det%mod)%mod;    }return s[k]=1ll*(res%mod+mod)%mod*inv_%mod;}template
       
        inline T read();signed main(){#ifndef ONLINE_JUDGE    freopen("sword.in","r",stdin);    freopen("sword.out","w",stdout);#endif    Math::init();n_[0]=1;    int T=read
        
         ();    while(T--){        r(K),rl(n),rl(R);R_=quick_pow(R,n+1);inv_=inv(R-1);        for(int i=1;i<=K;i=-~i)n_[i]=1ll*n_[i-1]*((n)%mod)%mod;        memset(s,0,sizeof(s));        s[0]=1ll*(R_-(R%mod)+mod)%mod*inv_%mod;        printf("%d\n",S(K));    }    return 0;}template
         
          inline T read(){ T sum=0,f=1;char k=getchar(); for(;k< '0'||'9'< k;k=getchar()) if(k=='-')f=-1; for(;'0'<=k&&k<='9';k=getchar()) sum=(sum<<1)+(sum<<3)+(k^48); return sum*f;}
         
        
       
      
     
    

---