雅礼学习10.4

上午考试

各题状况

T1

莫名其妙20分了。

考场上一眼秒掉了这个题目：这不就是个并查集捆绑+快速幂么

然后开开心心这个点如果有这个质因子的话\(fa\)就指向这个质因子，而每个数字有多个质因子。。。

多个质因子在相互指\(fa\)的时候指乱套了。。。。

对拍的时候看出来的，然后用\(1\)个多小时来调这份代码，最后自己都不知道这东西在干嘛了，就凉了。

T2

写了个暴力枚举，期望\(20\)实际\(20\)

T3

看到成绩之后：这题怎么会爆\(long long\)的？？？

然后讲题的时候。。。出题人说第二个部分分里面\(a_i\)的取值范围给错了，少了三个零。。。

凉凉，\(30\)挂没了

题目及考场代码

T1

图片.png

#include 
    
     #include 
     
      inline int read(){    int n=0,w=1;register char c=getchar();    while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}    while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();    return n*w;}const int N=1e5+1,mod=1e9+7;int n,tot,a[N],prime[N],head[N*10];bool notprime[N],vis[N];struct Edge{    int v,nxt;}edge[N<<1];inline void add(int u,int v){edge[++tot]=(Edge){v,head[u]};head[u]=tot;}inline void Get_prime(){    for(int i=2;i
      
       >=1,x=x*x%mod)        if(b&1)            res=res*x%mod;    return res;}int main(){    freopen("x.in","r",stdin);    freopen("x.out","w",stdout);    int t=read();    Get_prime();    tot=0;    while(t--)    {        memset(vis,false,sizeof vis);        memset(head,0,sizeof head);        tot=0;        n=read();        for(int i=1;i<=n;++i)        {            a[i]=read();            work(i);        }        tot=0;        for(int i=1;i<=n;++i)            if(!vis[i])            {                ++tot;                dfs(i);            }        printf("%d\n",(ksm(2,tot)-2+mod)%mod);    }    fclose(stdin),fclose(stdout);    return 0;}

T2

图片.png

/* * 这啥题啊。。。 * ao原来d是长度啊。。。。 * * 那不是。。。暴力就很好写了 * string+map水一发 */#include 
    
     #include 
     
      #include 
      inline int read(){    int n=0,w=1;register char c=getchar();    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}    while(c>='0'&&c<='9')n=n*10+c-'0',c=getchar();    return n*w;}const int N=91;int n,m,d,tot,ans,head[N];std::string s;std::map
       
         mp;struct Edge{    int v,w,nxt;}edge[N*(N-1)*2];inline void add(int u,int v,int w){edge[++tot]=(Edge){v,w,head[u]};head[u]=tot;}void dfs(int now,int step){    if(step==d)    {        if(!mp[s])            mp[s]=++ans;        return ;    }    for(int i=head[now];i;i=edge[i].nxt)    {        s.push_back(edge[i].w+'0');        dfs(edge[i].v,step+1);        s.erase(s.end()-1);    }}int main(){    freopen("y.in","r",stdin);    freopen("y.out","w",stdout);    n=read(),m=read(),d=read();    for(int u,v,w,i=1;i<=m;++i)    {        u=read(),v=read(),w=read();        add(u,v,w),add(v,u,w);    }    dfs(1,0);    printf("%d",ans);    fclose(stdin);fclose(stdout);    return 0;}

T3

图片.png

/* * 我旁边的dalao用一小时切了这个题，然后到处说：哇T3好水我贪心能100啊 * 然后有人问他：你复杂度多少的 * 他：100啊 * 那人：？？？100是个什么复杂度啊，我问的是复杂度 * 他：aoao。。。我看看啊。。。 O(n*q)的 * 那人：。。。你再去看看数据范围 * 他：？？？ * * 笑死我了hhhhh * 写了个模拟 */#include 
    
     inline int read(){    int n=0,w=1;register char c=getchar();    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}    while(c>='0'&&c<='9')n=n*10+c-'0',c=getchar();    return n*w;}const int N=1e5+1;int n,q,x[N];int main(){    freopen("z.in","r",stdin);    freopen("z.out","w",stdout);    n=read(),q=read();    for(int i=1;i<=n;++i)        x[i]=read();    int len,l,r,ans;    while(q--)    {        len=read();        ans=l=0,r=len;        for(int i=1;i<=n;++i)        {            if(x[i]>r)            {                ans+=x[i]-r;                l+=x[i]-r;                r=x[i];            }            else                if(x[i]

正解及代码

T1

对所有\(gcd\ne 1\)的两个数字连边，最后统计联通块数量（假设为\(cnt\)），那么答案为\(2^{cnt}-2\)

#include
    
     using namespace std;const int maxn=1e5+10,maxa=1e6+10,mod=1e9+7;int t,n,last[maxa],ans;bool vis[maxn];vector
     
       g[maxn];int pcnt,prime[maxa],minp[maxa];bool prm[maxa];inline void init(){    for(int i=2;i
      
       1){                int fac=minp[x];                while(x%fac==0)                    x/=fac;                if(last[fac]){                    g[i].push_back(last[fac]);                    g[last[fac]].push_back(i);                }                last[fac]=i;            }        }        ans=1;        for(int i=1;i<=n;++i)            if(!vis[i])                ans=ans*2%mod,dfs(i);        printf("%d\n",(ans+mod-2)%mod);    }    return 0;}

T2

\(f[i][j][mask]\)表示从\(i\)出发，到\(j\)结束，是否存在一条表示为\(mask\)的路径

但是显然这个复杂度不够优

考虑meet in the middle ，对于每种可能的路径，枚举中间的位置进行判断

\(O(2^{\frac{d}{2}}\times n\times (n+m))+2^d\times n\)

可以用\(bitset\)进行优化，能让整体除以\(64\)，由此可以解决\(N\)更大的问题

#include
    
     using namespace std;const int maxn=90+10,maxmask=1<<20/2+1;int n,m,d,d1,d2,ans;bitset
     
       g0[maxn],g1[maxn],dp[maxmask],f[maxmask];int main(){    freopen("y.in","r",stdin);    freopen("y.out","w",stdout);    scanf("%d%d%d",&n,&m,&d);    for(int i=1,u,v,c;i<=m;++i){        scanf("%d%d%d",&u,&v,&c);        if(c)            g1[u][v]=g1[v][u]=true;        else            g0[u][v]=g0[v][u]=true;    }    d2=d/2;d1=d-d2;    for(int u=n;u;--u){        for(int i=0;i

T3

如果存在一个\(x_i\)使得\(x_{i-1}=x_i\)或者\(x_{i-1}\lt x_i\lt x_{i+1}\)，那么可以删掉它（当完成上一个\(x\)的时候同时完成了这个任务）

#include
    
     using namespace std;typedef long long ll;const int maxn=1e5+10;int n,m;ll tot,ans[maxn];vector
     
       x;vector
      
       
         > a;map
        
          mp;inline ll calc(ll k){    if(!mp.empty()&&mp.begin()->second<0)        return tot-(mp.size()-1)*k;    else        return tot-mp.size()*k;}inline void solve(){    priority_queue
         
          
           ,vector
           
            
              >,greater
             
              
                > > q; int t=0; for(int i=0;i
               
                ::iterator p=mp.lower_bound(id); if(p==mp.end()||p->first!=id||abs(p->second)!=tmp) continue; while(t
                
                 second)>a[t].first) ans[a[t].second]=calc(a[t].first),++t; if(p!=mp.begin()) if(p!=prev(mp.end())){ tmp=p->second,tot-=abs(p->second); tmp+=prev(p)->second,tot-=abs(prev(p)->second); tmp+=next(p)->second,tot-=abs(next(p)->second); mp.erase(prev(p)); mp.erase(next(p)); p->second=tmp,tot+=abs(tmp); q.push(make_pair(abs(tmp),id)); } else{ tot-=abs(p->second); mp.erase(p); } else if(p->second>0) if(p!=prev(mp.end())){ tmp=p->second,tot-=abs(p->second); tmp+=next(p)->second,tot-=abs(next(p)->second); mp.erase(next(p)); if(tmp){ p->second=tmp,tot+=abs(tmp); q.push(make_pair(abs(tmp),id)); } else mp.erase(p); } else{ tot-=abs(p->second); mp.erase(p); } } while(t
                 
                  0&&p>last)) x.back()+=p-last; else x.push_back(p-last); last=p; } for(int i=0,l;i