首页 > 其他分享 >#10 有人写莫队不设块长，除0调了半天

#10 有人写莫队不设块长，除0调了半天

时间：2023-09-14 11:02:16浏览次数：36  
标签：10 int void write 块长 inline 不设 col define

Jeff and Removing Periods

题面

因为删除后可以任意排序，所以除第一次删除，每次都可以删去一种颜色，统计区间中有多少种颜色，可以使用莫队维护。对于第一次操作，如果其不能删去一种颜色，则操作次数加一，反之不变。因此我们问题变为了判断区间中是否存在颜色，使得这些颜色对应的位置形成等差数列。

这个也可以在莫队加点或删点时维护。令 \(dis_i\) 表示位置 \(i\) 到上一个颜色与 \(a_i\) 相同的点 \(x\) 的距离，如果 \(i\) 可以接在 \(x\) 的后面和它在一个等差数列中，则 \(dis_i=dis_x\)。用并查集维护这种在一个等差数列中的数，再用双端队列维护在区间中的颜色为 \(a_i\) 的数，最后只要判断队列大小是否为 \(1\)，或者队列中的第 \(2\) 个数和最后一个数是否在一个并查集中就可以判断是否存在一个颜色的数的位置构成一个等差数列了。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=1e5+10;
int n,Q,B,a[N],pos[N],dis[N],fa[N],cnt,ans[N],sum[N],tot;
struct query{
    int l,r,id;
}que[N];
bool cmp(query x,query y){
    if(x.l/B==y.l/B){
        return x.r<y.r;
    }
    return x.l<y.l;
}
int getfa(int x){
    if(fa[x]!=x){
        fa[x]=getfa(fa[x]);
    }
    return fa[x];
}
deque<int>q[N];
bool check(int x){
    if(!q[x].size()){
        return 0;
    }
    if(q[x].size()==1){
        return 1;
    }
    int first=q[x].front(),flag=0;
    q[x].pop_front();
    if(getfa(q[x].front())==getfa(q[x].back())){
        flag=1;
    }
    q[x].push_front(first);
    return flag;
}
void add(int id,int type){
    if(check(a[id])){
        tot--;
    }
    sum[a[id]]++;
    if(sum[a[id]]==1){
        cnt++;
    }
    if(type){
        q[a[id]].push_back(id);
    }
    else{
        q[a[id]].push_front(id);
    }
    if(check(a[id])){
        tot++;
    }
}
void del(int id,int type){
    if(check(a[id])){
        tot--;
    }
    if(sum[a[id]]==1){
        cnt--;
    }
    sum[a[id]]--;
    if(type){
        q[a[id]].pop_back();
    }
    else{
        q[a[id]].pop_front();
    }
    if(check(a[id])){
        tot++;
    }
}
void solve(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        if(!pos[a[i]]){
            fa[i]=i;
            dis[i]=0;
        }
        else{
            if(i-pos[a[i]]==dis[pos[a[i]]]){
                fa[i]=pos[a[i]];
            }
            else{
                fa[i]=i;
            }
            dis[i]=i-pos[a[i]];
        }
        pos[a[i]]=i;
    }
    read(Q);
    B=sqrt(Q);
    for(int i=1;i<=Q;i++){
        read(que[i].l),read(que[i].r);
        que[i].id=i;
    }
    sort(que+1,que+Q+1,cmp);
    int l=1,r=0;
    for(int i=1;i<=Q;i++){
        while(l>que[i].l){
            add(--l,0);
        }
        while(r<que[i].r){
            add(++r,1);
        }
        while(l<que[i].l){
            del(l++,0);
        }
        while(r>que[i].r){
            del(r--,1);
        }
        ans[que[i].id]=cnt+(tot==0);
    }
    for(int i=1;i<=Q;i++){
        write_endl(ans[i]);
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

[CERC2016] 二分毯 Bipartite Blanket

题面

需要注意的是题目求的是 \(V\subseteq S\text{（S表示一个匹配的点集）}\)，而不是 \(V=S\)。可以发现该题意中左右两侧是无关的，只要左右两边分别能在匹配中，两个点集的并就能在匹配中，具体证明详见zltqwq的P3679题解。

这样，我们可以分开求一个左边的点集和右边的点集是否在一个匹配中。根据hall定理，对于一个左部图大小为 \(X\)、右部图大小为 \(Y\) 的二分图，如果存在左侧点的完美匹配，则对于任意一个左侧点的子集 \(S\)，所有与该子集中的点相邻的点所构成的集合大小必须大于等于该子集的大小。自行使用高维前缀和维护，再用一遍双指针维护两边子集的权值和大于等于 \(t\) 的方案数。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=50,M=1<<21;
int n,m,val[2][N],e[N][N],mn,couple[N],vis[N],s[M],t[M],ansl[M],ansr[M];
vector<int>suma,sumb;
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    read(n),read(m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char opt=getchar();
            while(opt!='0'&&opt!='1'){
                opt=getchar();
            }
            e[i][j]=opt-'0';
            if(e[i][j]){
                s[1<<(i-1)]|=(1<<(j-1));
                t[1<<(j-1)]|=(1<<(i-1));
            }
        }
    }
    for(int i=1;i<=n;i++){
        read(val[0][i]);
    }
    for(int i=1;i<=m;i++){
        read(val[1][i]);
    }
    read(mn);
    suma.pb(0),sumb.pb(0);
    ll p=0,ans=0;
    for(int k=1;k<(1<<n);k*=2){
        for(int i=0;i<(1<<n);i+=k*2){
            for(int j=i;j<i+k;j++){
                s[j+k]|=s[j];
            }
        }
    }
    for(int k=1;k<(1<<m);k*=2){
        for(int i=0;i<(1<<m);i+=k*2){
            for(int j=i;j<i+k;j++){
                t[j+k]|=t[j];
            }
        }
    }
    ansl[0]=ansr[0]=1;
    for(int i=1;i<(1<<n);i++){
        if(__builtin_popcount(i)<=__builtin_popcount(s[i])){
            ansl[i]=1;
        }
    }
    for(int i=1;i<(1<<m);i++){
        if(__builtin_popcount(i)<=__builtin_popcount(t[i])){
            ansr[i]=1;
        }
    }
    for(int k=1;k<(1<<n);k*=2){
        for(int i=0;i<(1<<n);i+=k*2){
            for(int j=i;j<i+k;j++){
                ansl[j+k]&=ansl[j];
            }
        }
    }
    for(int k=1;k<(1<<m);k*=2){
        for(int i=0;i<(1<<m);i+=k*2){
            for(int j=i;j<i+k;j++){
                ansr[j+k]&=ansr[j];
            }
        }
    }
    for(int i=1;i<(1<<n);i++){
        if(ansl[i]){
            int sum=0;
            for(int j=1;j<=n;j++){
                if(i>>(j-1)&1){
                    sum+=val[0][j];
                }
            }
            suma.pb(sum);
        }
    }
    for(int i=1;i<(1<<m);i++){
        if(ansr[i]){
            int sum=0;
            for(int j=1;j<=m;j++){
                if(i>>(j-1)&1){
                    sum+=val[1][j];
                }
            }
            sumb.pb(sum);
        }
    }
    sort(suma.begin(),suma.end());
    sort(sumb.begin(),sumb.end());
    for(int i=suma.size()-1;i>=0;i--){
        while(p<sumb.size()&&suma[i]+sumb[p]<mn){
            p++;
        }
        ans+=(sumb.size()-p);
    }
    write_endl(ans);
    // cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
    return 0;
}

Nezzar and Hidden Permutations

题面

洛谷翻译太难绷了，写个题意。

题意：给定一张无向图，要求构造两个排列 \(a,b\)，使得对于任意一条边 \((u,v)\) 都满足 \((a_u-a_v)(b_u-b_v)>0\)，在这个要求下，使得 \(a_u=b_u\) 的数量最少。

假定当前有 \(n\) 个点，如果存在一个点 \(x\) 连了 \(n-1\) 条边，此时该点 \(a_x=b_x\)。为了方便，令 \(a_x=b_x=n\)。删去该点后继续进行上述操作，直到不存在这样的点 \(x\)。此时对于剩下的任意一个点 \(u\)，都存在 \(deg_u\le n-2\)。因为这个限制不好做，考虑求剩下的图的补图，对于补图上的一条边，可以构造 \((x,x+1),(x+1,x)\)，对于一条没处理的边，相当于加了一个限制，条件更加严格。但是这样会出现很多单点，这些单点显然只能填 \(x,x\) 不满足 \(a_u=b_u\) 的数量最少，最典型的情况是菊花图，会造出 \(n-2\) 个 \(a_i=b_i\) 的点。但是其实菊花图我们是有处理的方法的，令大小为 \(n\)，将根赋为 \((1,n)\)，将第 \(i\) 个叶子赋为 \((i+1,i)\)，对于整个菊花是一定满足条件，且能够得到 \(0\) 个 \(a_u=b_u\) 的点。

上述提醒了我们可以将一个图求出生成树后，将其拆成若干个菊花图，对于每个菊花图做一遍上述做法，并令菊花图与菊花图之间满足限制，将一段区间的值赋给一个菊花图。求生成树也很简单，直接求dfs树即可。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=5e5+10;
int n,m,deg[N],a[N],b[N],siz[N],rt[N],col[N],col_cnt,vis[N];
vector<int>e[N],v_col[N];
set<int>S,G[N];
queue<int>q;
void init(){
    col_cnt=0;
    for(int i=1;i<=n;i++){
        vis[i]=deg[i]=col[i]=siz[i]=a[i]=b[i]=0;
        vector<int>().swap(e[i]);
        vector<int>().swap(v_col[i]);
        set<int>().swap(G[i]);
        S.insert(i);
    }
}
void build(int u,int fa){
    for(auto v:S){
        if(!G[u].count(v)){
            e[u].pb(v);
            e[v].pb(u);
        }
    }
    for(auto v:e[u]){
        if(v==fa){
            continue;
        }
        S.erase(v);
    }
    for(auto v:e[u]){
        if(v==fa){
            continue;
        }
        build(v,u);
    }
}
void dfs(int u,int fa){
    bool f=0;
    if(!col[u]){
        for(auto v:e[u]){
            if(!col[v]){
                f=1;
            }
        }
        if(f){
            col[u]=++col_cnt;
            rt[col_cnt]=u;
            siz[col_cnt]=1;
            for(auto v:e[u]){
                if(!col[v]){
                    ++siz[col_cnt];
                    col[v]=col_cnt;
                }
            }
        }
        else{
            for(auto v:e[u]){
                if(col[v]){
                    if(rt[col[v]]==v){
                        ++siz[col[v]];
                        col[u]=col[v];
                    }
                    else if(siz[col[v]]>2){
                        col[u]=++col_cnt;
                        rt[col_cnt]=u;
                        siz[col_cnt]=2;
                        --siz[col[v]];
                        col[v]=col_cnt;
                    }
                    else{
                        rt[col[v]]=v;
                        ++siz[col[v]];
                        col[u]=col[v];
                    }
                    break;
                }
            }
        }
    }
    for(auto v:e[u]){
        if(v==fa){
            continue;
        }
        dfs(v,u);
    }
}
void solve(){
    read(n),read(m);
    int tot=n;
    init();
    for(int i=1;i<=m;i++){
        int u,v;
        read(u),read(v);
        G[u].insert(v);
        G[v].insert(u);
        deg[u]++;
        deg[v]++;
    }
    for(int i=1;i<=n;i++){
        if(deg[i]==n-1){
            S.erase(i);
            q.push(i);
        }
    }
    while(q.size()){
        int u=q.front();
        q.pop();
        a[u]=b[u]=tot--;
        vis[u]=1;
        for(auto v:e[u]){
            --deg[v];
            if(S.count(v)&&deg[v]==tot-1){
                q.push(v);
                S.erase(v);
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(S.count(i)){
            S.erase(i);
            build(i,0);
        }
    }
    for(int i=1;i<=n;i++){
        if(!a[i]&&!col[i]){
            dfs(i,0);
        }
    }
    for(int i=1;i<=n;i++){
        if(col[i]){
            v_col[col[i]].pb(i);
        }
    }
    for(int i=1,s=1;i<=col_cnt;i++,s++){
        b[rt[i]]=s;
        for(auto u:v_col[i]){
            if(u!=rt[i]){
                a[u]=s;
                b[u]=++s;
            }
        }
        a[rt[i]]=s;
    }
    for(int i=1;i<=n;i++){
        write_space(a[i]);
    }
    putchar('\n');
    for(int i=1;i<=n;i++){
        write_space(b[i]);
    }
    putchar('\n');
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

[POI2006] MET-Subway

题面

看题目容易让人想到最小路径覆盖问题，但是这个问题的全局最优显然和局部最优的策略是不同的。

贪心地考虑，本题的每条路径一定是从叶子到叶子，因为若存在路径的端点不是叶子，扩展到叶子一定能在路径数不增多的情况下，答案更大。同理，在选定某个点为根时，我们一定会优先选贡献更多的点，因此我们令一个点的阶数为该点到叶子的最远距离。因此如果能选一个 \(x\) 阶点，必然能选到对应的 \(0\sim x-1\) 阶点。因此对于一个高阶点，显然是能选就选，对于一个 \(i\) 阶点，令 \(cnt_i\) 表示 \(i\) 阶点的数量，则能选的数量的最大值为 \(\min(k\times 2,cnt_i)\)。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=1e6+10;
int n,cnt,deg[N],dep[N],tot[N];
vector<int>e[N];
void solve(){
    read(n),read(cnt);
    for(int i=1;i<n;i++){
        int u,v;
        read(u),read(v);
        e[u].pb(v);
        e[v].pb(u);
        deg[u]++;
        deg[v]++;
    }
    queue<int>q;
    for(int i=1;i<=n;i++){
        if(deg[i]==1){
            q.push(i);
            tot[0]++;
        }
    }
    while(q.size()){
        int u=q.front();
        q.pop();
        for(auto v:e[u]){
            deg[v]--;
            if(deg[v]==1){
                dep[v]=dep[u]+1;
                tot[dep[v]]++;
                q.push(v);
            }
        }
    }
    int ans=0;
    for(int i=0;i<=n;i++){
        ans+=min(cnt*2,tot[i]);
    }
    write_endl(ans);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

Garden of the Sun

题面

一开始有个想法是两行为一组，但如果这两行上都没有关键点，就很难处理，于是考虑三行一组。此时我们可以将每一组的第一行全染，因为任意两个关键点都没有交点或交边，所以这样是不会出现两组之间有两个竖着的直接穿过，形成环。上面两行一组就不能这么做，因为中间的一行只要存在两个及以上的关键点就一定会形成环。

接下来只要维护连通性即可，对于第 \(i\) 组和第 \(i+1\) 组（$i<\lfloor\frac{n}{3}\rfloor$）之间的部分，如果第 \(i\) 组 \(2\) 列有关键点，则将第 \(2\) 列的两个点都染色，否则染第一列的两个点。可行性很显然，因为若第 \(2\) 列有关键点，则第 \(1,3\) 列肯定没有关键点，不会形成 \(4\) 格环；若第 \(2\) 列没有关键点，则第 \(1\) 列连上肯定不会和第 \(2\) 列的点产生 \(4\) 格环。需要注意的是如果最后一组也有 \(3\) 行，需要将最后一行的点连通到上面的连通块中，特判一下即可。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=510;
int n,m,a[N][N];
void solve(){
    read(n),read(m);
    for(int i=1;i<=n+1;i++){
        for(int j=1;j<=m+1;j++){
            a[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char opt=getchar();
            while(opt!='.'&&opt!='X'){
                opt=getchar();                
            }
            if(opt=='.'){
                a[i][j]=0;
            }
            else{
                a[i][j]=1;
            }
        }
    }
    for(int i=1;i<=n;i+=3){
        for(int j=1;j<=m;j++){
            a[i][j]=1;
        }
    }
    for(int i=2;i<=n;i+=3){
        if(a[i][2]||a[i+1][2]){
            a[i][2]=a[i+1][2]=1;
        }
        else{
            a[i][1]=a[i+1][1]=1;
        }
    }
    if(n%3==0){
        for(int i=1;i<=m;i++){
            if(a[n][i]||a[n-1][i]){
                a[n][i]=a[n-1][i]=1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]){
                putchar('X');
            }
            else{
                putchar('.');
            }
        }
        putchar('\n');
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

BFS Trees

题面

首先注意到如果两个点的 bfs 树是相同的，两个点 \(x,y\) 之间的最短路的路径一定只有一条。如果存在多条，则 \(x\) 的 bfs 树中会删掉若干条与 \(y\) 相连的边，但这些边是一定在 \(y\) 的 bfs 树中的，同理 \(y\) 的 bfs 树中也一定会删掉若干条一定在 \(x\) 的 bfs 树中的边。

再考虑一条边 \((u,v)\) 可能在 bfs 树中要满足什么条件，令 bfs 树的根为 \(rt\)，\(d_{i,j}\) 表示 \(i\) 到 \(j\) 的最短路的长度，则 \(d_{rt,u}+1=d_{rt,v}\)，同理对于同时在两棵 bfs 树中，则对于两棵树都要满足上述条件，对于所有的不在最短路上的点 \(v\)，找到这样的边 \((u,v)\) 的数量，答案为乘积，复杂度 \(O(n^2m)\)

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=410,mod=998244353;
int n,m,d[N][N],cnt[N][N];
vector<int>e[N];
void bfs(int st){
    queue<int>q;
    q.push(st);
    for(int i=1;i<=n;i++){
        d[st][i]=inf;
    }
    d[st][st]=0;
    cnt[st][st]=1;
    while(q.size()){
        int u=q.front();
        q.pop();
        for(auto v:e[u]){
            if(d[st][v]>d[st][u]+1){
                d[st][v]=d[st][u]+1;
                cnt[st][v]=cnt[st][u];
                q.push(v);
            }
            else if(d[st][v]==d[st][u]+1){
                cnt[st][v]+=cnt[st][u];
            }
        }
    }
}
void solve(){
    read(n),read(m);
    for(int i=1;i<=m;i++){
        int u,v;
        read(u),read(v);
        e[u].pb(v);
        e[v].pb(u);
    }
    for(int i=1;i<=n;i++){
        bfs(i);
    }
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=n;j++){
    //         cerr<<cnt[i][j]<<' ';
    //     }
    //     cerr<<endl;
    // }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(cnt[i][j]>1){
                write_space(0);
                continue;
            }
            int ans=1;
            for(int k=1;k<=n;k++){
                if(d[i][k]+d[k][j]==d[i][j]){
                    continue;
                }
                int cnt=0;
                for(auto v:e[k]){
                    if(d[i][v]+1==d[i][k]&&d[j][v]+1==d[j][k]){
                        cnt++;
                    }
                }
                ans=1ll*ans*cnt%mod;
            }
            write_space(ans);
        }
        putchar('\n');
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

标签：10,int,void,write,块长,inline,不设,col,define
From： https://www.cnblogs.com/luoshen0/p/17694595.html

相关文章

  • 差分信号隔离转换称重传感器压力应变桥信号处理隔离变送器0-10mV/0-20mV/0-±10mV/0-
    主要特性DIN11IPO压力应变桥信号处理系列隔离放大器是一种将差分输入信号隔离放大、转换成按比例输出的直流信号导轨安装变送模块。产品广泛应用在电力、远程监控、仪器仪表、医疗设备、工业自控等行业。此系列模块内部嵌入了一个高效微功率的电源，向输入端和输出端提供隔离的电源......
  • 保证接口数据安全的10种方案
    前言我们日常开发中，如何保证接口数据的安全性呢？个人觉得，接口数据安全的保证过程，主要体现在这几个方面：一个就是数据传输过程中的安全，还有就是数据到达服务端，如何识别数据，最后一点就是数据存储的安全性。今天跟大家聊聊保证接口数据安全的10个方案。1.数据加密，防止报文明文传输。......
  • CSP 202109-2 非零段划分
    题目C++代码//202109-2非零段划分#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;constintN=500010;constintM=10010;inta[N],d[M];//d[i]为差分数组boolc[N];intn,ans,sum;intmain(){scanf(&q......
  • 综合实力再获认可！巨杉数据库蝉联2023「Cloud 100 China」榜单
    巨杉数据库凭借在分布式文档型数据库领域的技术实力及商业市场拓展方面的优异表现再度荣登「Cloud100China」榜单，体现了业界对其在基础设施平台领域的高度认可。近日，由靖亚资本和崔牛会联合主办的2023「Cloud100China」榜单发布暨线下峰会在上海举办，本次评选活动由国内外Clou......
  • Redis7 10大数据类型(Redis列表)
    一、常用二、单key多value三、简单说明一个双端链表的结构，容量是2的32次方减1个元素，大概40多亿，主要功能有push/pop等，一般用在栈、队列、消息队列等场景。left、right都可以插入添加；如果键不存在，创建新的链表；如果键已存在，新增内容；如果值全移除，对应的键也就消失了。它的底层实......
  • CF1043D Mysterious Crime 题解
    CF1043DMysteriousCrime题解题意给定\(m\)个长为\(n\)的序列，问它们的公共子串的个数。\(n\le10^5,m\le10\)。已经死掉的做法一眼广义后缀自动机。建出后缀自动机，然后在parenttree上面跑dfs。正确性会在下面证明。但是因为广义SAM巨大的常数，蒟蒻的代码跑了1......
  • 复杂指针解读typedef double(* (* (*p3)() )[10] )()
    1#include<stdio.h>2/*“右左法则”：*/3//*p3指针4//(*p3)()函数指针函数参数列表为()5//*(*p3)()函数指针函数参数列表为()、返回值类型为指针6//(*(*p3)())[10]数组指针指针为函数指针函数参数列表为()、返回值类型为指针7//double(*(*p3......
  • 特斯拉100G数据泄露事件：系内部员工违规操作
    近日，特斯拉向其员工以及美国执法部门通报了“100G数据泄露事件”的具体规模及原因。这起今年5月份发生的大规模数据泄露事件影响了逾7.5万人，其中包括与员工相关的各种敏感信息，而这一切竟然源自“内部员工的不法行为”。内部员工违规致使泄露事件调查显示，两名特斯拉前员工违反了特斯......
  • 记一次在 win10 家庭版上安装 docker desktop
    docker在很久之前，我尝试过在我的笔记本上安装这个玩意失败了。今天，在公司台式机上，终于折腾出来了。记一下遇到的问题和解决办法现在PS直接可以运行docker命令首先安装hyper-VWin10家庭中文版安装Hyper-Vhttps://zhuanlan.zhihu.com/p/51939654检查下载安装docker......
  • win10照片查看器不见了
    1、右键桌面空白处，新建一个“文本文档”2、在文档自己中粘贴以下内容WindowsRegistryEditorVersion5.00;ChangeExtension'sFileType[HKEY_CURRENT_USER\Software\Classes\.jpg]@="PhotoViewer.FileAssoc.Tiff";ChangeExtension'sFileType[HKEY_CURRENT_U......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99