首页 > 其他分享 >我们刚刚知道那些题的解法-1

我们刚刚知道那些题的解法-1

时间：2023-07-13 21:44:37浏览次数：48  
标签：return int rep 那些 刚刚 ans define 解法 mod

P7735

考虑将一条边的贡献记在深度较大的电上，一次修改要改的点太多。

想到如果维护每个点的时间，那么一条边是实边当且仅当两个点的时间相同。

轻重链剖分，对于一次操作，维护每个节点的时间，维护重链上的所有点的点权。

对于一次询问，重边直接把贡献加起来，轻边考虑询问两边的时间，因为轻边个数只有 \(\log n\) 个，所以复杂度是对的。

复杂度 \(O(n\log ^2n)\)

#define SegmentTree ST
namespace SegmentTree{
    #define ls(k) k<<1
    #define rs(k) k<<1|1
    struct Node{
        int col,val,sum,tcv,tcc,len;
    }p[N<<2];
    inline void Cc(int k,int co){
        p[k].col=co;p[k].tcc=co;
    }
    inline void Cv(int k,int va){
        p[k].val=va;p[k].tcv=va;
        p[k].sum=va*p[k].len;
    }
    inline void PushDown(int k){
        if(p[k].tcc){Cc(ls(k),p[k].tcc);Cc(rs(k),p[k].tcc);p[k].tcc=0;}
        if(p[k].tcv!=-1){Cv(ls(k),p[k].tcv);Cv(rs(k),p[k].tcv);p[k].tcv=-1;}
    }
    inline void PushUp(int k){p[k].sum=p[ls(k)].sum+p[rs(k)].sum;}
    inline void ChangeV(int k,int l,int r,int z,int y,int x){
        if(z<=l&&r<=y){Cv(k,x);return;}PushDown(k);int mid=(l+r)>>1;
        if(z<=mid) ChangeV(ls(k),l,mid,z,y,x);
        if(mid<y) ChangeV(rs(k),mid+1,r,z,y,x);PushUp(k);
    }
    inline void ChangeC(int k,int l,int r,int z,int y,int x){
        if(z<=l&&r<=y){Cc(k,x);return;}PushDown(k);int mid=(l+r)>>1;
        if(z<=mid) ChangeC(ls(k),l,mid,z,y,x);
        if(mid<y) ChangeC(rs(k),mid+1,r,z,y,x);PushUp(k);
    }
    inline void Build(int k,int l,int r){
        p[k].tcv=-1;
        int mid=(l+r)>>1;p[k].len=r-l+1;if(l==r) return;
        Build(ls(k),l,mid);Build(rs(k),mid+1,r);
    }
    inline int Ask(int k,int l,int r,int z,int y){
        if(z<=l&&r<=y) return p[k].sum;PushDown(k);int mid=(l+r)>>1,ans=0;
        if(z<=mid) ans+=Ask(ls(k),l,mid,z,y);
        if(mid<y) ans+=Ask(rs(k),mid+1,r,z,y);PushUp(k);return ans;
    }
    inline int Gc(int k,int l,int r,int w){
        if(l==r) return p[k].col;PushDown(k);int mid=(l+r)>>1;
        if(w<=mid) return Gc(ls(k),l,mid,w);else return Gc(rs(k),mid+1,r,w);PushUp(k);
    }
    inline void Clear(){mset(p,0);}
}

int t,n,m,id[N],rk[N],tot,fa[N],son[N],siz[N],dep[N],top[N];
vi e[N];

inline void dfs(int k,int fat){
    dep[k]=dep[fat]+1;fa[k]=fat;siz[k]=1;
    for(int to:e[k]) if(to!=fat){dfs(to,k);siz[k]+=siz[to];if(siz[son[k]]<siz[to]) son[k]=to;}
}
inline void Dfs(int k,int t){
    id[k]=++tot;rk[tot]=k;top[k]=t;if(son[k]) Dfs(son[k],t);
    for(int to:e[k]) if(to!=son[k]&&to!=fa[k]) Dfs(to,to);
}
inline void Clear(){
    ST::Clear();rep(i,1,n) e[i].clear(),id[i]=rk[i]=fa[i]=son[i]=siz[i]=dep[i]=top[i]=0;tot=0;
}
inline void Change(int a,int b,int v){
    int A=a,B=b,l=-1;
    while(top[a]!=top[b]){
        if(dep[top[a]]<dep[top[b]]) swap(a,b);
        ST::ChangeC(1,1,n,id[top[a]],id[a],v);
        if(top[a]!=a) ST::ChangeV(1,1,n,id[son[top[a]]],id[a],1);
        a=fa[top[a]];
        if(son[a]) ST::ChangeV(1,1,n,id[son[a]],id[son[a]],0);
    }
    if(dep[a]<dep[b]) swap(a,b);l=b;
    if(l==B){if(son[A]) ST::ChangeV(1,1,n,id[son[A]],id[son[A]],0);}
    else if(l==A){if(son[B]) ST::ChangeV(1,1,n,id[son[B]],id[son[B]],0);}
    else {if(son[A]) ST::ChangeV(1,1,n,id[son[A]],id[son[A]],0);if(son[B]) ST::ChangeV(1,1,n,id[son[B]],id[son[B]],0);}
    // printf("son[A]=%d\n",son[A]);
    // printf("son[B]=%d\n",son[B]);
    // printf("Ask(5)=%d\n",ST::Ask(1,1,n,id[5],id[5]));
    // printf("id[%d]=%d id[%d]=%d\n",b,id[b],a,id[a]);
    ST::ChangeC(1,1,n,id[b],id[a],v);
    if(a!=b) ST::ChangeV(1,1,n,id[son[b]],id[a],1);
    ST::ChangeV(1,1,n,id[b],id[b],0);
    // printf("Ask(5)=%d\n",ST::Ask(1,1,n,id[5],id[5]));
}
inline int Ask(int a,int b){
    int Ans=0;
    // printf("Ask(2)=%d Ask(7)=%d\n",ST::Ask(1,1,n,id[2],id[2]),ST::Ask(1,1,n,id[7],id[7]));
    // printf("Ask(5)=%d\n",ST::Ask(1,1,n,id[5],id[5]));
    while(top[a]!=top[b]){
        if(dep[top[a]]<dep[top[b]]) swap(a,b);
        if(a!=top[a]) Ans+=ST::Ask(1,1,n,id[son[top[a]]],id[a]);
        int t=top[a];a=fa[top[a]];
        int c1=ST::Gc(1,1,n,id[t]),c2=ST::Gc(1,1,n,id[a]);
        if(c1==c2&&c1!=0){
            // puts("here");
            Ans++;
        }
    }
    // printf("Ans=%d\n",Ans);
    if(dep[a]<dep[b]) swap(a,b);
    if(a!=b) Ans+=ST::Ask(1,1,n,id[son[b]],id[a]);
    return Ans;
}

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(t);
    while(t--){
        // printf("t=%d\n",t);
        read(n);read(m);
        rep(i,1,n-1){
            int u,v;read(u);read(v);e[u].pb(v);e[v].pb(u);
        }
        ST::Build(1,1,n);
        dfs(1,0);Dfs(1,0);
        // rep(i,1,n) printf("son[%d]=%d\n",i,son[i]);
        rep(i,1,m){
            int op,a,b;read(op);read(a);read(b);
            if(op==1){
                Change(a,b,i);
            }
            else{
                printf("%d\n",Ask(a,b));
            }
        }
        Clear();
    }
    return 0;
}

犯的错误：

  • 多测不清空。
  • 跳重链的时候忘记修改儿子。
  • 下传标记覆盖没有注意到 \(0\)。
  • 讨论初始点儿子的修改出错。

改进：

  • 调试之前先沉住气把代码整体阅读一遍，可以省下很多时间。

P7736

考虑 \(k=2\) 不难发现答案就是邻接矩阵的行列式。

这是因为对于路径 \((i,p_i)\)，\(p\) 是一个排列，而交点个数的奇偶性等同于排列的奇偶性。这提示我们往行列式的方向去想。

考虑 \(k>2\)，但是 \(n_i=n_1\)。设 \(n_i,n_{i+1}\) 组成的邻接矩阵为 \(M_i\)，考虑 \(\prod |M_i|\) 的结果，不难发现就是问题的答案。这是因为考虑合并两个邻接矩阵 \(|M_i||M_{i+1}|\)，相当于 \((\sum(-1)^{\mathbb{sgn(p)}})(\sum(-1)^{\mathbb{sgn(q)}})\)，正好相当于奇偶性的一个合并。

考虑一般情况，注意到上面的那种情况同样也可以写成 \(|\prod M_i|=|M|\)，而邻接矩阵的乘法是有意义的，\(M_{i,j}\) 就表示第一层图的 \(i\) 到第 \(k\) 层图的 \(j\) 的方案数是多少。考虑一般情况下的 \(|M|\)，合并两个邻接矩阵，方案的奇偶性不变，所以 \(|M|\) 奇偶性的部分是正确的，考虑路径是否可能有交，假设两条路径有交，起点终点分别为 \(x_i<x_j,y_i<y_j\)，那么合并之后 \((x_i,y_i),(x_j,y_j)\) 是不合法的，但是与之对应的，\((x_i,y_j),(x_j,y_i)\) 是一条交点个数与上面奇偶性不同的一条路径，所以恰好容斥掉了。

所以答案就是相邻邻接矩阵乘积的行列式。

复杂度为 \(O(kn^2+n^3\log n)\)。

inline int ksm(int a,int b,int mod){
    int res=1;while(b){if(b&1){res=1ll*res*a%mod;}a=1ll*a*a%mod;b>>=1;}return res;
}
inline int inv(int x){return ksm(x,mod-2,mod);}

struct Matrix{
    int n,m,a[N][N];
    inline void Clear(){mset(a,0);n=m=0;}
    inline Matrix operator * (const Matrix &b)const{
        assert(m==b.n);
        Matrix c;c.Clear();c.n=n;c.m=b.m;
        rep(i,1,c.n)rep(j,1,c.m)rep(k,1,m){
            c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j]%mod)%mod;
        }
        return c;
    }
    inline void Print(){
        rep(i,1,n){
            rep(j,1,m) printf("%d ",a[i][j]);
            puts("");
        }puts("");
    }
    inline int Det(){
        assert(n==m);
        int x=1;
        rep(i,1,n){
            if(!a[i][i]){
                rep(j,i+1,n) if(a[j][i]){
                    rep(k,1,n) swap(a[j][k],a[i][k]);
                    x*=-1;break;
                }
            }
            if(!a[i][i]) return 0;
            int nowinv=inv(a[i][i]);
            rep(j,i+1,n){
                int K=a[j][i]*nowinv%mod;
                rep(k,1,n) a[j][k]=((a[j][k]-K*a[i][k]%mod)%mod+mod)%mod;
            }
        }
        // (*this).Print();
        int ans=1;
        rep(i,1,n) ans=ans*a[i][i]%mod;return (ans*x%mod+mod)%mod;
    }
};

int t,n[N],m[N],K;

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(t);
    while(t--){
        read(K);
        rep(i,1,K) read(n[i]);rep(i,1,K-1) read(m[i]);
        Matrix A;A.Clear();A.n=n[1];A.m=n[1];rep(i,1,A.n) A.a[i][i]=1;
        rep(i,1,K-1){
            Matrix B;B.Clear();
            rep(j,1,m[i]){
                int u,v;read(u);read(v);
                B.a[u][v]=1;
            }
            B.n=n[i];B.m=n[i+1];
            // B.Print();
            A=A*B;
            // A.Print();
        }
        printf("%lld\n",A.Det());
    }
    return 0;
}

犯的错误:

  • 高斯消元忘记换一个不为 \(0\) 的行上来。
  • 空间开小。

P7913

首先想到三分，但是显然是假的。

考虑能否处理出 \(f_i\) 表示国内放 \(i\) 个桥的最优值是多少，容易想到一个桥对应的那些区间一定是不交的区间，而且如果新加入一个桥，对以前的桥没有影响，我们可以看做是在还没选的区间里新选一些无交的区间，其中没选的区间的第一个区间是一定要选的。

P7915

选一个数后，在另一个也是这个数的位置标号，表示在最后的区间中这个数应该在哪里。比如 1234155324，选了第一个 \(1\) 之后再第二个 \(1\) 上标 \(10\)。

首先考虑我们需要保证前 \(n\) 个数是一个排列，且对于标为 \(k\) 的数往左往右至少有一边小于 \(k\)。也就是说，对于一种合法方案，设已经标号的区间为 \([z,y]\)，假设我们接下来要选的数为 \(k\)，那么一定要保证 \(z-1,y+1\) 这两个位置其中一个为 \(k\)。

同时，注意到在左右都可以选的情况下先选左边和先选右边不影响情况的合法性。所以贪心即可。

代码：

int t,a[N],n,st,b[N];
P p[N];
char s[N];

inline bool Check(int l,int r,int z,int y){
    // puts("Here");
    int cnt=1;
    rep(i,1,2*n) b[i]=0;
    b[z]=2*n;
    while(y-z+1<n){
        // printf("l=%d r=%d\n",l,r);
        // printf("p[a[l]].se=%d\n",p[a[l]].se);
        while(!b[l]&&(p[a[l]].se==z-1||p[a[l]].se==y+1)&&y-z+1<n){
            cnt++;
            if(p[a[l]].se==z-1) z--,b[z]=2*n-cnt+1;else y++,b[y]=2*n-cnt+1;
            s[++st]='L';l++;
            // puts("L");
        }
        if(y-z+1>=n) break;
        if(!b[r]&&(p[a[r]].fi==z-1||p[a[r]].fi==y+1)){
            cnt++;
            if(p[a[r]].fi==z-1) z--,b[z]=2*n-cnt+1;else y++,b[y]=2*n-cnt+1;
            s[++st]='R';r--;
            // puts("R");
        }
        else return 0;
    }
    // rep(i,1,2*n) printf("%d ",b[i]);
    int now=n+1;
    while(z<=y){
        if(b[z]==now) s[++st]='L',z++;
        else if(b[y]==now) s[++st]='R',y--;
        else assert(0);
        now++;
    }
    return 1;
}
inline void Print(){
    rep(i,1,st) putchar(s[i]);puts("");
}

int main(){
    freopen("my.in","r",stdin);
    freopen("my.out","w",stdout);
    read(t);
    while(t--){
        read(n);
        rep(i,1,2*n) read(a[i]);
        rep(i,1,2*n) p[a[i]]=mp(-1,-1);
        rep(i,1,2*n){
            if(p[a[i]].fi==-1){p[a[i]].fi=i;}else p[a[i]].se=i;
        }
        bool op=0;
        st=0;s[++st]='L';
        if(Check(2,2*n,p[a[1]].se,p[a[1]].se)){op=1;Print();continue;}
        st=0;s[++st]='R';
        if(Check(1,2*n-1,p[a[2*n]].fi,p[a[2*n]].fi)){op=1;Print();continue;}
        if(!op){puts("-1");}
    }
}

P7914

显然是一个区间 DP，设 \(f_{l,r}\) 表示一个合法超级括号序列，设 \(A\) 是具有 \((C)\) 形式的合法超级括号序列，其中 \(C\) 为任意字符串，\(S\) 如题意所示，\(B\) 是合法括号序列，那么 \(f_{l,r}\) 有以下部分组成：

  • \(\text{ASB}\)
  • \(\text{AB}\)
  • \(\text{A}\)

设 \(g_{l,r}\) 表示 \(AS\) 的个数，\(h{l,r}\) 表示 \(A\) 的个数。

考虑计算 \(h_{l,r}\)，不难发现其由以下部分组成：

  • \(\text{(B)}\)
  • \(\text{(S)}\)
  • \(\text{(SB)}\)
  • \(\text{(BS)}\)

枚举 \(S\) 的长度转移即可。

考虑计算 \(g_{l,r}\)，直接枚举 \(S\) 长度即可。

代码：

int f[N][N],g[N][N][2],h[N][N],n,K;
char s[N];

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);read(K);scanf("%s",s+1);
    rep(i,1,n-1){
        if((s[i]=='('||s[i]=='?')&&(s[i+1]==')'||s[i+1]=='?')){
            f[i][i+1]=h[i][i+1]=1;
        }
    }
    rep(i,3,n){
        rep(j,1,n-i+1){
            int l=j,r=j+i-1;
            // rep(k,1,K){
            //     if(s[l+k-1]!='*'&&s[l+k-1]!='?') break;
            //     if(l+k-1>=r-1) break;
            //     g[l][r][0]=(g[l][r][0]+h[l+k][r])%mod;
            // }
            rep(k,1,K){
                if(s[r-k+1]!='*'&&s[r-k+1]!='?') break;
                if(l+1>=r-k+1) break;
                g[l][r][1]=(g[l][r][1]+h[l][r-k])%mod;
            }
            if(s[l]!='*'&&s[l]!=')'&&s[r]!='*'&&s[r]!='('){
                int L=l+1,R=r-1;
                bool op=1;
                rep(k,L,R) if(s[k]!='*'&&s[k]!='?'){op=0;break;}
                if(R-L+1<=K&&op) h[l][r]++;
                h[l][r]=(h[l][r]+f[L][R])%mod;
                rep(k,L,R-1){
                    if(s[k]!='*'&&s[k]!='?') break;
                    if(k-L+1>K) break;
                    h[l][r]=(h[l][r]+f[k+1][R])%mod;
                }
                dec(k,L+1,R){
                    if(s[k]!='*'&&s[k]!='?') break;
                    if(R-k+1>K) break;
                    h[l][r]=(h[l][r]+f[L][k-1])%mod;
                }
            }
            else h[l][r]=0;
            rep(k,l,r-1){
                f[l][r]=(f[l][r]+1ll*g[l][k][1]*f[k+1][r]%mod)%mod;
                f[l][r]=(f[l][r]+1ll*h[l][k]*f[k+1][r]%mod)%mod;
            }
            f[l][r]=(f[l][r]+h[l][r])%mod;
            // printf("g[l][r][1]=%d h[l][r]=%d f[l][r]=%d l=%d r=%d\n",g[l][r][1],h[l][r],f[l][r],l,r);
        }
    }
    printf("%d\n",f[1][n]);
    return 0;
}

P7916

参考 Piwry 的博客

首先显然有一个最小割的模型，但是网络流时间复杂度不够优。考虑网格图为平面图，而 \(k=2\) 的时候可以利用平面图转对偶图，考虑如何扩展到一般情况。

利用同样的思路，先建出原图的对偶图，考虑我们只需要考虑那些相邻不用颜色附加点之间的点，把这些点两两配对即可。容易想到路径是不会相交的，如果相交，改变配对的方式，一定不会比原先的方案劣，所以我们只需要建出对偶图，然后跑最短路，最后做一个 DP 去求解最优配对方案即可，做 DP 的时候记得有路径不交的限制。

注意，相邻相同颜色附加点之间的点也是有意义的，可能会出现以下情况：


vc<P> e[N*N];
int c[N][N],r[N][N],n,m,T,d[N*N],f[N][N],xu[N*N],cnt[N*N],w[N][N];
bool vis[N*N];
vi v;
P id[N<<2];
struct Point{
    int w,id,co;
    inline bool operator < (const Point &b)const{return id<b.id;}
}p[N*N];

inline int ID(int a,int b){
    return (a-1)*(m-1)+b;
}
struct Node{
    int id,v;
    inline bool operator < (const Node &b)const{return v>b.v;}
};
priority_queue<Node> q;
inline void dij(int id,int s){
    fill(d+1,d+1000*1000+1,INF);q.push({s,0});d[s]=0;mset(vis,0);
    while(q.size()){
        Node top=q.top();q.pop();
        if(vis[top.id]) continue;
        vis[top.id]=1;
        for(P to:e[top.id]){
            if(vis[to.fi]||d[to.fi]<=d[top.id]+to.se) continue;
            d[to.fi]=d[top.id]+to.se;
            q.push({to.fi,d[to.fi]});
        }
    }
    for(int i=0;i<(int)v.size();i++){
        // printf("w[%d][%d=%d\n",i,id,d[v[i]]);
        w[id][i]=w[i][id]=d[v[i]];
    }
}
inline void Print(int a,int b,int c){
    // printf("from=%lld to=%lld w=%lld\n",a,b,c);
    cnt[a]++;cnt[b]++;
    assert(cnt[a]<=e[a].size());
    assert(cnt[b]<=e[b].size());
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout); 
    read(n);read(m);read(T);
    rep(i,1,n-1)rep(j,1,m){
        read(c[i][j]);
    }
    rep(i,1,n)rep(j,1,m-1){
        read(r[i][j]);
    }
    rep(i,1,n-2)rep(j,1,m-1){
        // Print(ID(i,j),ID(i+1,j),r[i+1][j]);
        e[ID(i,j)].pb(mp(ID(i+1,j),r[i+1][j]));
        e[ID(i+1,j)].pb(mp(ID(i,j),r[i+1][j]));
    }
    // puts("Finish colu");
    rep(i,1,n-1)rep(j,1,m-2){
        // Print(ID(i,j),ID(i,j+1),c[i][j+1]);
        e[ID(i,j)].pb(mp(ID(i,j+1),c[i][j+1]));
        e[ID(i,j+1)].pb(mp(ID(i,j),c[i][j+1]));
    }
    rep(i,1,m-1) id[i]=mp(1,i);id[m]=mp(-1,-1);rep(i,m+1,m+n-1) id[i]=mp(i-m,m-1);id[m+n]=mp(-1,-1);
    rep(i,m+n+1,2*m+n-1) id[i]=mp(n-1,2*m+n-i);id[2*m+n]=mp(-1,-1);
    rep(i,2*m+n+1,2*m+2*n-1) id[i]=mp(2*m+2*n-i,1);id[2*m+2*n]=mp(-1,-1);
    // puts("Finish");
    //矩形内部建边。
    while(T--){
        // printf("T=%d\n",T);
        int pc;read(pc);
        if(pc==1){puts("0");continue;}
        rep(i,1,pc){
            int w,id,co;read(w);read(id);read(co);
            p[i].w=w;p[i].id=id;p[i].co=co;
        }
        sort(p+1,p+pc+1);
        int tot=ID(n-1,m-1);
        v.clear();
        rep(i,2,pc){
            // printf("i=%lld\n",i);
            ++tot;
            rep(j,p[i-1].id,p[i].id-1){
                if(id[j]==mp(-1ll,-1ll)) continue;
                int w=-1;
                if(j<=m){w=r[id[j].fi][id[j].se];}
                else if(j<=m+n){w=c[id[j].fi][id[j].se+1];}
                else if(j<=2*m+n){w=r[id[j].fi+1][id[j].se];}
                else if(j<=2*m+2*n){w=c[id[j].fi][id[j].se];}
                e[tot].pb(mp(ID(id[j].fi,id[j].se),w));
                e[ID(id[j].fi,id[j].se)].pb(mp(tot,w));
                Print(tot,ID(id[j].fi,id[j].se),w);
            }
            if(i!=2){
                e[tot].pb(mp(tot-1,p[i-1].w));
                e[tot-1].pb(mp(tot,p[i-1].w));
                Print(tot,tot-1,p[i-1].w);
            }
            if(p[i].co!=p[i-1].co) v.pb(tot);
        }
        ++tot;
        e[tot-1].pb(mp(tot,p[pc].w));
        e[tot].pb(mp(tot-1,p[pc].w));
        Print(tot-1,tot,p[pc].w);
        rep(j,p[pc].id,2*m+2*n){
            if(id[j]==mp(-1ll,-1ll)) continue; 
            int w=-1;
            if(j<=m){w=r[id[j].fi][id[j].se];}
            else if(j<=m+n){w=c[id[j].fi][id[j].se+1];}
            else if(j<=2*m+n){w=r[id[j].fi+1][id[j].se];}
            else if(j<=2*m+2*n){w=c[id[j].fi][id[j].se];}
            // printf("id[%lld].fi=%lld if[%lld].se=%lld w=%lld\n",j,id[j].fi,j,id[j].se,w);
            e[tot].pb(mp(ID(id[j].fi,id[j].se),w));
            e[ID(id[j].fi,id[j].se)].pb(mp(tot,w));
            Print(tot,ID(id[j].fi,id[j].se),w);
        }
    // exit(0);
        rep(j,1,p[1].id-1){
            if(id[j]==mp(-1ll,-1ll)) continue;
            int w=-1;
            if(j<=m){w=r[id[j].fi][id[j].se];}
            else if(j<=m+n){w=c[id[j].fi][id[j].se+1];}
            else if(j<=2*m+n){w=r[id[j].fi+1][id[j].se];}
            else if(j<=2*m+2*n){w=c[id[j].fi][id[j].se];}
            e[tot].pb(mp(ID(id[j].fi,id[j].se),w));
            e[ID(id[j].fi,id[j].se)].pb(mp(tot,w));
            Print(tot,ID(id[j].fi,id[j].se),w);
        }
    // exit(0);
        if(p[1].co!=p[pc].co) v.pb(tot);
        e[tot].pb(mp(ID(n-1,m-1)+1,p[1].w));
        e[ID(n-1,m-1)+1].pb(mp(tot,p[1].w));
        Print(tot,ID(n-1,m-1)+1,p[1].w);
        if(v.empty()){
            puts("0");rep(i,1,tot){
                while(cnt[i]) e[i].pop_back(),cnt[i]--;
            }continue;
        }
        //初始化完成
        for(int i=0;i<(int)v.size()-1;i++) dij(i,v[i]);
        //最短路
        rep(i,0,(int)v.size()-1) xu[i+1]=i;rep(i,v.size()+1,2*v.size()) xu[i]=xu[i-v.size()];
        int len=2*v.size();
        // rep(i,1,len/2)rep(j,1,len/2) printf("w[%lld][%lld]=%lld\n",xu[i],xu[j],w[xu[i]][xu[j]]);
        rep(i,1,len-1) f[i][i+1]=w[xu[i]][xu[i+1]];
        for(int i=4;i<=len;i+=2){
            rep(j,1,len-i+1){
                int l=j,r=j+i-1;
                f[l][r]=f[l+1][r-1]+w[xu[l]][xu[r]];
                rep(k,l,r-1){
                    if((k-l+1)&1) continue;
                    f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]);
                }
                // printf("f[%d][%d]=%d\n",l,r,f[l][r]);
            }
        }
        // printf("e[9307].size()=%d\n",e[9307].size());
        int ans=INF;
        rep(i,1,len/2+1) ans=min(ans,f[i][i+len/2-1]);
        printf("%lld\n",ans);
        rep(i,1,len) xu[i]=0;
        rep(i,1,tot){
            // assert(cnt[i]>=0);
            while(cnt[i]>0){
                if(e[i].empty()) assert(0);
                e[i].pop_back();
                cnt[i]--;
            }
        }
        // exit(0);
    }wx0
}

犯的错误：

  • 建边时下标弄错。
  • 建图出错。
  • 小于等于写成小于。

CF1194G Another Meme Problem

首先考虑可以枚举 \(a,b\)，然后对 \(ax,bx\) 中的 \(x\) 来 DP，只需要记录进位，是否存在 \(a,b\)，以及是否小于 \(n\)。但是有可能一对 \(A,B\) 可能对应多个 \(a,b\),所以我们规定 \(a,b\) 互质，但是有可能一个 \(A,B\)，对应的 \(a,b\) 并不互质，而 \(a,b\) 只有可能是 \(a',b'\) \(1\) 到 \(4\) 倍，所以我们改一下 DP 状态，记录是否存在 \(a,b\) 和它们的 \(1\) 至 \(4\) 倍即可。

#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 110
#define M number
using namespace std;

typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;

const int INF=0x3f3f3f3f;
const dd eps=1e-9;
const int mod=998244353;

template<typename T> inline void read(T &x){
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int c[N],n,f[N][21][21][4][4][4][4][2][2],a,b;
string s;

inline int cm(int i,int j,int co){
    if(i<j) return 0;
    else if(i>j) return 1;
    else return co;
}
inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}

inline int dfs(int posi,int axj,int bxj,int s1,int s2,int s3,int s4,int lim1,int lim2){
    if(posi==n+1){
        if(!axj&&!bxj&&!lim1&&!lim2&&(s1==3||s2==3||s3==3||s4==3)) return 1;return 0;
    }
    int &now=f[posi][axj][bxj][s1][s2][s3][s4][lim1][lim2];
    if(now!=-1) return now;
    int ans=0;
    rep(i,0,9){
        int nowa=(i*a+axj)%10;
        int nowaxj=(i*a+axj)/10;
        int nowb=(i*b+bxj)%10;
        int nowbxj=(i*b+bxj)/10;
        int nows1=s1|((nowa==a)<<1)|(nowb==b);
        int nows2=s2|((nowa==a*2)<<1)|(nowb==b*2);
        int nows3=s3|((nowa==a*3)<<1)|(nowb==b*3);
        int nows4=s4|((nowa==a*4)<<1)|(nowb==b*4);
        ans=(ans+dfs(posi+1,nowaxj,nowbxj,nows1,nows2,nows3,nows4,cm(nowa,c[posi],lim1),cm(nowb,c[posi],lim2)))%mod;
    }
    now=ans;
    return ans;
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    cin>>s;int len=s.length()-1;
    dec(i,0,len) c[len-i]=s[i]-'0';n=len;
    int ans=0;
    int now=1;
    rep(i,0,n){
        ans=(ans+c[i]*now%mod)%mod;now=now*10%mod;
    }
    // printf("ans=%d\n",ans);
    rep(i,1,9)rep(j,i+1,9){
        if(gcd(i,j)!=1) continue;
        mset(f,-1);
        a=i;
        b=j;
        // ans=(ans+dfs(0,0,0,0,0,0,0,0,0))%mod;
        int nowans=dfs(0,0,0,0,0,0,0,0,0);
        // printf("a=%d b=%d ans=%d\n",a,b,nowans);
        ans=(ans+nowans*2%mod)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}

标签：return,int,rep,那些,刚刚,ans,define,解法,mod
From： https://www.cnblogs.com/HeNuclearReactor/p/17552240.html

相关文章

  • 最大公约数和最小公倍数的解法
    最大公约数和最小公倍数的解法什么是最大公约数和最小公倍数？最大公约数（GreatestCommonDivisor，GCD）是指两个或多个整数共有约数中最大的一个。例如，12和18的最大公约数是6，因为它们都可以被6整除，而且没有比6更大的约数。最小公倍数（LeastCommonMultiple，LCM）是指两个或多......
  • 多元融合：流媒体传输网络的全盘解法
    我们在寻找「网络」的全盘解法。音视频数字化在消费领域的红利俨然见顶，而产业级视频应用激活了更多场景下的业务模式。与此同时，音视频客户也从单一的业务需求，趋向于多种业务并行存在的需求。固有的网络能满足新兴的业态吗？延时与成本之间存在区间最优解吗？业务的升级切换如何不再......
  • 2023-7-10 #65 我守着虚构的幻想 那些我珍视的模样
    448QOJ6669Mapa这谁想得到啊？？？？？？？？？？？？？？？？？？插出一个模1e9+7下的多项式，保存系数。449CF1456EXOR-ranges感觉挺难的。类似406HDU6358Innocence，我们将每一段拆成\(\log\)个trie上的区间，每一个形如“固定前缀\(S\)，长为\(l\)的后缀任选”，并将选择\([l,r]\)内的数改为在这\(\l......
  • 盘点那些 FZQOJ 被 ban 掉的功能
    原链接在【洛谷博客】。目录前言初\(2023\)届（c2023）1.犇犇（卒于2021/07/27）2.一言（和犇犇同时挂的）3.评论（卒于2021/07/28）初\(2024\)届（c2024）1.Python2.7（卒于2022/03/15）2.难度标签（卒于2022/07/21）3.HTML（卒于2023/01/04）初\(2025\)届（c2025）前言身为FZOIer的我们十分的......
  • 那些神奇的转化到坐标或网格上的题目
    [AGC002E]CandyPiles[AGC015E]Mr.AokiIncubator......
  • RNA-seq中的那些统计学问题
    <aname="data-preprocess"><h2>1.数据预处理[<sup>目录</sup>](#content)</h2></a><aname="filt-low-exp-genes"><h3>1.1.过滤低表达的基因[<sup>目录</sup>](#content)</h3></a>>......
  • 盘一盘那些高性能设计的点（一）
    狭义地讲，性能是指软件在尽可能少地占用系统资源的前提下，尽可能高地提高运行速度。谈及性能，我们的关注点不再是软件或者系统的功能，而是在其实现功能过程中所表现出来的资源效率。一、池化思想什么是池化？简单的说就是设置一个公共对象池，对于其中的对象直接复用而不再使用新创建......
  • Qt杂谈5.浅谈Qt程序乱码那些事
    1为啥聊这个？你是否也在为Qt程序乱码的问题发愁？网上查了一大堆文章，十篇文章九篇一样，虽然碰运气把问题解决了，但是下次遇到同样的问题还是无从下手，如果你想从根本上理解并解决这个问题，那么可以看看这篇文章，希望能帮到你。2从代码出发2.1使用的Qt版本本人的测试环境：Qt版本：Desk......
  • 【LeetCode剑指offer#05】回文链表的两种解法+删除链表中间节点（链表的基本操作）
    回文链表给你一个单链表的头节点head，请你判断该链表是否为回文链表。如果是，返回true；否则，返回false。示例1：输入：head=[1,2,2,1]输出：true示例2：输入：head=[1,2]输出：false提示：链表中节点数目在范围[1,105]内0<=Node.val<=9思路将值复制到数组中后用双指针......
  • P9381 [THUPC 2023 决赛] 那些脑海里最珍贵的
    小清新大模拟（？写起来挺顺的，就是浮点误差那块整破防了，最后问了神虎用了科学计数法存浮点数才过stO神虎Orz坑点：注意精度误差死亡后要清除Average的主动技能，防止重复触发死亡处理导致被动技能被弄乱Average的主动技能里的“\(3\)个回合”指的是南北两边各行动一次算一......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99