Codeforces SWERC 2021-2022 – Online Mirror 部分简要题解(Codeforces swerc 2021-2022 – brief explanation of online mirror)

A. Organizing SWERC

签到题

priority_queue<int> a[20];
int n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;cin>>T;
    while (T--) {
        cin>>n;
        rep(i,1,n) {
            int x,y;
            cin>>x>>y;
            a[y].push(x);
        }
        int ans=0;
        rep(i,1,10) {
            if (a[i].empty()) { 
                ans=-1;
                break;
            } else {
                int x=a[i].top();
                ans+=x;
            }
        }
        if (ans<0) cout<<"MOREPROBLEMS"<<endl;
        else cout<<ans<<endl;
        rep(i,1,10) {
            while (!a[i].empty()) a[i].pop();
        }
    }
}

B. Toys

C. European Trip

记图的邻接矩阵为\(A\), 那么从\(i\)到\(j\)的长度为\(k\)的路径一共有\((A^k)_{ij}\)条, 所有起点和终点相同的路径数量为\(\mathrm{tr}(A^k)\).

考虑加上special trip的限制. 依然是考虑矩阵乘法, 假设路径长度为\(k\)时的矩阵为\(F_k\), 那么有转移式

其中\(D\)表示度数矩阵, \(I\)表示单位矩阵. 将转移式写成分块矩阵乘法的形式.

则可直接快速幂.

namespace My_Math{
    #define N 100000

    int fac[N+100],invfac[N+100];

    int add(int x,int y) {return x+y>=maxd?x+y-maxd:x+y;}
    int dec(int x,int y) {return x<y?x-y+maxd:x-y;}
    int mul(int x,int y) {return 1ll*x*y%maxd;}
    ll qpow(ll x,int y)
    {
        ll ans=1;
        while (y)
        {
            if (y&1) ans=mul(ans,x);
            x=mul(x,x);y>>=1;
        }
        return ans;
    }
    int getinv(int x) {return qpow(x,maxd-2);}

    int C(int n,int m)
    {
        if ((n<m) || (n<0) || (m<0)) return 0;
        return mul(mul(fac[n],invfac[m]),invfac[n-m]);
    }

    void math_init()
    {
        fac[0]=invfac[0]=1;
        rep(i,1,N) fac[i]=mul(fac[i-1],i);
        invfac[N]=getinv(fac[N]);
        per(i,N-1,1) invfac[i]=mul(invfac[i+1],i+1);
    }
    #undef N
}
using namespace My_Math;

struct Matrix{
    int n,m;
    int x[N][N];
    void out() {
        rep(i,1,n) {
            rep(j,1,m) cout<<x[i][j]<<" ";
            cout<<endl;
        }
        cout<<endl;
    }
};

Matrix operator *(Matrix &a,Matrix &b) {
    Matrix c;
    c.n=a.n;c.m=b.m;
    rep(i,1,c.n) rep(j,1,c.m) c.x[i][j]=0;
    rep(i,1,a.n) rep(j,1,a.m) rep(k,1,b.m) 
        c.x[i][j]=add(c.x[i][j],mul(a.x[i][k],b.x[k][j]));
    return c;
}

Matrix qpow(Matrix x,int y) {
    Matrix ans;ans.n=ans.m=x.n;
    rep(i,1,ans.n) rep(j,1,ans.n) ans.x[i][j]=(i==j);
    while (y) {
        if (y&1) ans=ans*x;
        x=x*x;y>>=1;
    }
    return ans;
}

Matrix a,b,d,A,tr;
int n,m,k;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>k;
    a.n=a.m=b.n=b.m=n;
    A.n=n;A.m=n*2;tr.n=n*2;tr.m=n*2;
    rep(i,1,m) {
        int u,v;
        cin>>u>>v;
        a.x[u][v]++;a.x[v][u]++;
        d.x[u][u]++;d.x[v][v]++;
    }
    if (k==1) {
        int ans=0;
        rep(i,1,n) ans=add(ans,a.x[i][i]);
        cout<<ans<<endl;
        return 0;
    }
    Matrix s1=a,s2=qpow(a,2);
    
    rep(i,1,n) rep(j,1,n) s2.x[i][j]=dec(s2.x[i][j],d.x[i][j]);
    //s2.out();
    rep(i,1,n) rep(j,1,n) A.x[i][j]=s2.x[i][j];
    rep(i,1,n) rep(j,1,n) A.x[i][j+n]=s1.x[i][j];
    rep(i,1,n) rep(j,1,n) tr.x[i][j]=a.x[i][j];
    rep(i,1,n) rep(j,1,n) tr.x[i+n][j]=dec((i==j),d.x[i][j]);
    rep(i,1,n) rep(j,1,n) tr.x[i][j+n]=(i==j);
    tr=qpow(tr,k-2);
    //tr.out();
    A=A*tr;
    int ans=0;
    rep(i,1,n) ans=add(ans,A.x[i][i]);
    cout<<ans<<endl;
    return 0;
}

D. Evolution of Weasels

提供一个比较奇怪的做法?

考虑一个包含A,B,C和单位元e的群\(G\), 其中元素的运算满足\(AA=BB=CC=ABAB=BCBC=e\). 根据前三项可知\(A,B,C\)的逆元就是本身. 又有\(AB=(AB)^{-1}=B^{-1}A^{-1}=BA\), 同理\(BC=CB\).

或者注意到BA->AA[BA]BB->A[ABAB]B->AB.

所以在串中B的位置是无足轻重的, 可以随便将其挪动. 但A和C之间的相对关系无法被改变. 考虑\(u=v\)等价于\(uv^{-1}=e\). 故可以先计算出\(uv^{-1}\), 将其中所有的B移去后再成对的消去A或C, 判断最后能否得到一个空串.

char sta[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;cin>>T;
    while (T--) {
        string u,v;
        cin>>u>>v;
        reverse(v.begin(),v.end());
        string s=u+v;
        int cnt=0;
        string t="";
        int n=s.size();
        rep(i,0,n-1) {
            if (s[i]=='B') cnt++;
            else t=t+s[i];
        }
        if (cnt&1) cout<<"NO";
        else {
            n=t.size();
            if (n&1) cout<<"NO";
            else {
                int tp=0;
                rep(i,0,n-1) {
                    if ((!tp)||(sta[tp]!=s[i])) sta[++tp]=s[i];
                    else tp--;
                }
                if (tp==0) cout<<"YES";
                else cout<<"NO";
            }
        }
        cout<<endl;
    }
    return 0;
}

E. Round Table

F. Antennas

先把绝对值拆掉, \(i\)只能向\([i-p_i,i+p_i]\)中的点连边, 据此可以把\(p_i\)的限制丢掉.

先只考虑\(i>j\)的情况. 注意到每条边的边权为1, 于是在做dij的过程中, 每个点恰好被松弛一次. 所以可以在所有满足\(i\leq j+p_j\)的点\(j\)中找到一个还未松弛的\(j+p_j\)最大的点, 用\(i\)号点对其松弛, 在将其从考察的范围内删去. 不难发现找到这个点的过程需要进行区间查询和单点删除, 故可直接用线段树维护所有尚未松弛的点.

对于\(i<j\)的情况, 和上面一样再开一棵线段树进行维护即可.

int n,a[N],b[N],c[N],seg[N<<2][2];
bool vis[N];
queue<pii> q;

int max0(int x,int y) {if (b[x]>b[y]) return x;else return y;}
int max1(int x,int y) {if (c[x]<c[y]) return x;else return y;}


void modify(int id,int l,int r,int p,int op) {
    if (l==r) {
        seg[id][op]=0;
        return;
    }
    int mid=(l+r)>>1;
    if (p<=mid) modify(id<<1,l,mid,p,op);
    else modify(id<<1|1,mid+1,r,p,op);
    seg[id][0]=max0(seg[id<<1][0],seg[id<<1|1][0]);
    seg[id][1]=max1(seg[id<<1][1],seg[id<<1|1][1]);
}

int query0(int id,int l,int r,int ql,int qr) {
    if ((l>=ql)&&(r<=qr)) return seg[id][0];
    int mid=(l+r)>>1,ans=0;
    if (ql<=mid) ans=max0(ans,query0(id<<1,l,mid,ql,qr));
    if (qr>mid) ans=max0(ans,query0(id<<1|1,mid+1,r,ql,qr));
    return ans;
}

int query1(int id,int l,int r,int ql,int qr) {
    if ((l>=ql)&&(r<=qr)) return seg[id][1];
    int mid=(l+r)>>1,ans=0;
    if (ql<=mid) ans=max1(ans,query1(id<<1,l,mid,ql,qr));
    if (qr>mid) ans=max1(ans,query1(id<<1|1,mid+1,r,ql,qr));
    return ans;
}

void build(int id,int l,int r) {
    if (l==r) {
        seg[id][0]=seg[id][1]=l;
        return;
    }
    int mid=(l+r)>>1;
    build(id<<1,l,mid); build(id<<1|1,mid+1,r);
    seg[id][0]=max0(seg[id<<1][0],seg[id<<1|1][0]);
    seg[id][1]=max1(seg[id<<1][1],seg[id<<1|1][1]);
}

int main() {
    //ios::sync_with_stdio(false);
    //cin.tie(0); cout.tie(0);
    int T;cin>>T;
    while (T--) {
        int st,ed;
        cin>>n>>st>>ed;
        rep(i,1,n) cin>>a[i];
        rep(i,1,n) {
            b[i]=i+a[i];
            c[i]=i-a[i];
        }
        b[0]=0;c[0]=n*3;
        build(1,1,n);
        q.push(mkp(st,0));
        while (!q.empty()) {
            pii now=q.front();q.pop();
            int u=now.fir;
            if (u==ed) {
                cout<<now.sec<<endl;
                break;
            }
            if (vis[u]) continue;vis[u]=1;
            int l=max(1,u-a[u]),r=min(n,u+a[u]);
            while (1) {
                int v=query0(1,1,n,l,u);
                if (b[v]<u) break;
                q.push(mkp(v,now.sec+1));
                modify(1,1,n,v,0);
            }
            while (1) {
                int v=query1(1,1,n,u,r);
                if (c[v]>u) break;
                q.push(mkp(v,now.sec+1));
                modify(1,1,n,v,1);
            }
        }
        while (!q.empty()) q.pop();
        rep(i,1,n) vis[i]=0;
    }
    return 0;
}

G. Gastronomic Event

H. Boundary

先考虑长宽相等的情况, 不难发现只有\((n-1,m-1),(n,m-2),(n-2,m)\)这三种情况.

再考虑长宽不等的情况, 此时\(n,n-2\)和\(m,m-2\)这两组数中必有一组同时存在, 于是只会有2是可能合法的.

set<int> s;
void solve(int n,int m) {
    if ((n<0)||(m<0)) return;
    int d=__gcd(n,m);
    for (int i=1;i*i<=d;i++) {
        if (d%i==0) {s.insert(i);s.insert(d/i);}
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;cin>>T;
    while (T--) {
        int n,m;
        cin>>n>>m;
        s.clear();
        solve(n-1,m-1);
        solve(n,m-2);
        solve(n-2,m);
        s.insert(2);
        int siz=s.size();
        cout<<siz<<" ";
        set<int>::iterator it;
        for (it=s.begin();it!=s.end();it++) cout<<(*it)<<" ";
        cout<<endl;
    }
}

I. Ice Cream Shop

对于第\(i\)个hut. 假设离它最近的seller与它的距离为\(d_i\), 那么只有将新的商店设在\((y_i-d_i,y_i+d_i)\)里时才能得到\(p_i\)的收益(\(y_i\)为hut的位置). 直接差分统计即可.

int n,m,p[N],b[N];
map<ll,ll> a;

int main() {
    cin>>n>>m;
    rep(i,1,n) cin>>p[i];
    rep(i,1,m) cin>>b[i];
    sort(b+1,b+1+m);
    b[m+1]=2e9;b[0]=-200;
    rep(i,1,n) {
        int np=(i-1)*100;
        int pos=lower_bound(b,b+m+2,np)-b;
        int r=pos,l=pos-1;
        ll d=min(b[r]-np,np-b[l]);
        a[np-d]+=p[i];a[np+d]-=p[i];
    }
    ll ans=0,now=0;
    for (auto &x:a) {
        now+=x.sec;
        ans=max(ans,now);
    }
    cout<<ans<<endl;
    return 0;
}

J. Training Camp

K. Pandemic Restrictions

L. Il Derby della Madonnina

朴素的dp式如下

将绝对值拆开, 当\(a_i\leq a_j\)时有\(vt_i+a_i\geq vt_j+a_j\); 当\(a_i>a_j\)时有\(vt_i-a_i\geq vt_j+a_j\).

分别将这两个式子记作(1)和(2). 注意到当\(a_i\leq a_j\)时若满足(1)式则自动满足(2)式; 当\(a_i> a_j\)时若满足(2)式则自动满足(1)式. 所以最后合法的\(i\)所构成的集合中\((vt_i+a_i,vt_i-a_i)\)的两维均是单调递增的. 仿照LIS的方式进行处理即可.

int n,a[N],b[N],t[N],tot;
ll v,f[N];
pair<ll,ll> p[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>v;
    rep(i,1,n) cin>>t[i];
    rep(i,1,n) cin>>a[i];
    rep(i,1,n) p[i]=mkp(v*t[i]-a[i],v*t[i]+a[i]);
    sort(p+1,p+n+1);
    rep(i,1,n) {
        ll tmp=p[i].sec;
        if ((p[i].fir<0)||(p[i].sec<0)) continue;
        if (tmp>=f[tot]) f[++tot]=tmp;
        else {
            int p=upper_bound(f+1,f+1+tot,tmp)-f;
            f[p]=tmp;
        }
    }
    cout<<tot;
    return 0;
}

M. Bottle Arrangements

如果合法则一定存在一种形如RR…RWW…W的方案.

int n,m;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;cin>>T;
    while (T--) {
        cin>>n>>m;
        int mx1=0,mx2=0;
        rep(i,1,m) {
            int r,w;
            cin>>r>>w;
            mx1=max(r,mx1);
            mx2=max(w,mx2);
        }
        if (mx1+mx2>n) cout<<"IMPOSSIBLE";
        else {
            mx2=n-mx1;
            rep(i,1,mx1) cout<<"R";
            rep(i,1,mx2) cout<<"W";
        }
        cout<<endl;
    }
}

N. Drone Photo

考虑如下的合法情况

1---2       1---3
|   |       |   |
|   |       |   |
3---4       2---4

注意到对于所有的合法情况, 一定恰好存在两个位置. 使得在包含它自身和合法情况中与它相邻的两个数构成的三元组中它的大小处于中间位置.

而对于如下的非法情况

1---4       1---3
|   |       |   |
|   |       |   |
3---2       4---2

一定不存在上述中的位置.

直接对上述描述中的三元组的总数计数, 根据分析其恰好为答案的两倍.

int n,a[N][N],r[N][N],c[N][N],row[N],col[N];
pii pos[N*N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n;
    rep(i,1,n) rep(j,1,n) {
        cin>>a[i][j];
        pos[a[i][j]]=mkp(i,j);
    }
    rep(x,1,n*n) {
        int i=pos[x].fir,j=pos[x].sec;
        r[i][j]=row[i];
        c[i][j]=col[j];
        row[i]++;col[j]++;
    }
    ll ans=0;
    rep(i,1,n) rep(j,1,n) ans+=(n-1-r[i][j])*c[i][j]+r[i][j]*(n-1-c[i][j]);
    cout<<ans/2<<endl;
    return 0;
}

O. Circular Maze

注意到在题设极坐标中\((r,\theta)\)在离散意义上的数量并不多. 于是可以用数组把所有限制表示出来然后从原点暴力dfs即可. 具体细节可查看下面的程序.

int n,a[21][400],b[400],c[21][400];
int vis[21][400];
string s;

void dfs(int r,int d) {
    if (vis[r][d]) return;
    vis[r][d]=1;
    if (r==20) return;
    int dl=0,dr=360;
    if (b[r]>1) {
        dl=d;dr=(d+1)%360;
        while (!c[r][dl]) dl=(dl-1+360)%360;
        while (!c[r][dr]) dr=(dr+1)%360;
    }
    while (dl!=dr) {
        if (!a[r+1][dl]) dfs(r+1,dl);
        if ((r)&&(!a[r][dl])) dfs(r-1,dl);
        if ((dr==360) && (dl==359)) break;
        dl=(dl+1)%360;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;cin>>T;
    while (T--) {
        rep(i,0,20) {
            b[i]=0;
            rep(j,0,359) c[i][j]=a[i][j]=vis[i][j]=0;
        }
        cin>>n;
        rep(i,1,n) {
            cin>>s;
            if (s[0]=='C') {
                int r,d1,d2;
                cin>>r>>d1>>d2;
                while (d1!=d2) {
                    a[r][d1]=1;
                    d1=(d1+1)%360;
                }
            } else {
                int r1,r2,d;
                cin>>r1>>r2>>d;
                while (r1<r2) {
                    c[r1][d]=1;
                    b[r1]++;
                    r1++;
                }
            }
        }
        dfs(0,0);
        int ok=0;
        rep(i,0,359) ok|=vis[20][i];
        if (ok) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}
————————

A. Organizing SWERC

Check in question

priority_queue<int> a[20];
int n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;cin>>T;
    while (T--) {
        cin>>n;
        rep(i,1,n) {
            int x,y;
            cin>>x>>y;
            a[y].push(x);
        }
        int ans=0;
        rep(i,1,10) {
            if (a[i].empty()) { 
                ans=-1;
                break;
            } else {
                int x=a[i].top();
                ans+=x;
            }
        }
        if (ans<0) cout<<"MOREPROBLEMS"<<endl;
        else cout<<ans<<endl;
        rep(i,1,10) {
            while (!a[i].empty()) a[i].pop();
        }
    }
}

B. Toys

Coo

C. European Trip

If the adjacency matrix of the graph is \ (a \), the path with length \ (K \) from \ (I \) to \ (J \) has \ (a ^ k)_ {ij} \), the number of paths with the same starting and ending points is \ (\ mathrm {tr} (a ^ k) \)

Consider adding special trip restrictions The matrix multiplication is still considered. Assuming that the matrix when the path length is \ (K \) is \ (f_k \), there is a transfer formula

Where \ (D \) represents the degree matrix and \ (I \) represents the identity matrix The transfer formula is written in the form of block matrix multiplication

Then the power can be obtained directly and quickly

namespace My_Math{
    #define N 100000

    int fac[N+100],invfac[N+100];

    int add(int x,int y) {return x+y>=maxd?x+y-maxd:x+y;}
    int dec(int x,int y) {return x<y?x-y+maxd:x-y;}
    int mul(int x,int y) {return 1ll*x*y%maxd;}
    ll qpow(ll x,int y)
    {
        ll ans=1;
        while (y)
        {
            if (y&1) ans=mul(ans,x);
            x=mul(x,x);y>>=1;
        }
        return ans;
    }
    int getinv(int x) {return qpow(x,maxd-2);}

    int C(int n,int m)
    {
        if ((n<m) || (n<0) || (m<0)) return 0;
        return mul(mul(fac[n],invfac[m]),invfac[n-m]);
    }

    void math_init()
    {
        fac[0]=invfac[0]=1;
        rep(i,1,N) fac[i]=mul(fac[i-1],i);
        invfac[N]=getinv(fac[N]);
        per(i,N-1,1) invfac[i]=mul(invfac[i+1],i+1);
    }
    #undef N
}
using namespace My_Math;

struct Matrix{
    int n,m;
    int x[N][N];
    void out() {
        rep(i,1,n) {
            rep(j,1,m) cout<<x[i][j]<<" ";
            cout<<endl;
        }
        cout<<endl;
    }
};

Matrix operator *(Matrix &a,Matrix &b) {
    Matrix c;
    c.n=a.n;c.m=b.m;
    rep(i,1,c.n) rep(j,1,c.m) c.x[i][j]=0;
    rep(i,1,a.n) rep(j,1,a.m) rep(k,1,b.m) 
        c.x[i][j]=add(c.x[i][j],mul(a.x[i][k],b.x[k][j]));
    return c;
}

Matrix qpow(Matrix x,int y) {
    Matrix ans;ans.n=ans.m=x.n;
    rep(i,1,ans.n) rep(j,1,ans.n) ans.x[i][j]=(i==j);
    while (y) {
        if (y&1) ans=ans*x;
        x=x*x;y>>=1;
    }
    return ans;
}

Matrix a,b,d,A,tr;
int n,m,k;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>k;
    a.n=a.m=b.n=b.m=n;
    A.n=n;A.m=n*2;tr.n=n*2;tr.m=n*2;
    rep(i,1,m) {
        int u,v;
        cin>>u>>v;
        a.x[u][v]++;a.x[v][u]++;
        d.x[u][u]++;d.x[v][v]++;
    }
    if (k==1) {
        int ans=0;
        rep(i,1,n) ans=add(ans,a.x[i][i]);
        cout<<ans<<endl;
        return 0;
    }
    Matrix s1=a,s2=qpow(a,2);
    
    rep(i,1,n) rep(j,1,n) s2.x[i][j]=dec(s2.x[i][j],d.x[i][j]);
    //s2.out();
    rep(i,1,n) rep(j,1,n) A.x[i][j]=s2.x[i][j];
    rep(i,1,n) rep(j,1,n) A.x[i][j+n]=s1.x[i][j];
    rep(i,1,n) rep(j,1,n) tr.x[i][j]=a.x[i][j];
    rep(i,1,n) rep(j,1,n) tr.x[i+n][j]=dec((i==j),d.x[i][j]);
    rep(i,1,n) rep(j,1,n) tr.x[i][j+n]=(i==j);
    tr=qpow(tr,k-2);
    //tr.out();
    A=A*tr;
    int ans=0;
    rep(i,1,n) ans=add(ans,A.x[i][i]);
    cout<<ans<<endl;
    return 0;
}

D. Evolution of Weasels

Provide a more strange approach?

Consider a group \ (g \) containing a, B, C and unit element E, where the operation of the elements satisfies \ (AA = BB = CC = ABAB = bcbc = e \) According to the first three items, the inverse of \ (a, B, C \) is itself There are also \ (AB = (AB) ^ {- 1} = B ^ {- 1} a ^ {- 1} = BA \), similarly \ (BC = CB \)

Or notice ba – & gt; AA[BA]BB-> A[ABAB]B-> AB.

Therefore, the position of B in the string is insignificant and can be moved at will But the relative relationship between a and C cannot be changed Consider that \ (U = V \) is equivalent to \ (UV ^ {- 1} = e \) Therefore, we can first calculate \ (UV ^ {- 1} \), remove all B, and then eliminate a or C in pairs to judge whether an empty string can be obtained at last

char sta[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;cin>>T;
    while (T--) {
        string u,v;
        cin>>u>>v;
        reverse(v.begin(),v.end());
        string s=u+v;
        int cnt=0;
        string t="";
        int n=s.size();
        rep(i,0,n-1) {
            if (s[i]=='B') cnt++;
            else t=t+s[i];
        }
        if (cnt&1) cout<<"NO";
        else {
            n=t.size();
            if (n&1) cout<<"NO";
            else {
                int tp=0;
                rep(i,0,n-1) {
                    if ((!tp)||(sta[tp]!=s[i])) sta[++tp]=s[i];
                    else tp--;
                }
                if (tp==0) cout<<"YES";
                else cout<<"NO";
            }
        }
        cout<<endl;
    }
    return 0;
}

E. Round Table

Coo

F. Antennas

First remove the absolute value, and \ (I \) can only connect edges to the points in \ ([i-p_i, I + p_i] \), so the limit of \ (p_i \) can be discarded

First, only consider the case of \ (I & gt; J \) Note that the edge weight of each edge is 1, so in the process of DIJ, each point is relaxed exactly once Therefore, we can find the largest point of \ (j + p_j \) that has not been relaxed among all points \ (J \) that meet \ (I \ Leq j + p_j \), relax it with point \ (I \), and delete it from the scope of investigation It is not necessary to use the relaxation tree to find and delete all the segments that have not been found

For the case of \ (I & lt; J \), just open another segment tree for maintenance as above

int n,a[N],b[N],c[N],seg[N<<2][2];
bool vis[N];
queue<pii> q;

int max0(int x,int y) {if (b[x]>b[y]) return x;else return y;}
int max1(int x,int y) {if (c[x]<c[y]) return x;else return y;}


void modify(int id,int l,int r,int p,int op) {
    if (l==r) {
        seg[id][op]=0;
        return;
    }
    int mid=(l+r)>>1;
    if (p<=mid) modify(id<<1,l,mid,p,op);
    else modify(id<<1|1,mid+1,r,p,op);
    seg[id][0]=max0(seg[id<<1][0],seg[id<<1|1][0]);
    seg[id][1]=max1(seg[id<<1][1],seg[id<<1|1][1]);
}

int query0(int id,int l,int r,int ql,int qr) {
    if ((l>=ql)&&(r<=qr)) return seg[id][0];
    int mid=(l+r)>>1,ans=0;
    if (ql<=mid) ans=max0(ans,query0(id<<1,l,mid,ql,qr));
    if (qr>mid) ans=max0(ans,query0(id<<1|1,mid+1,r,ql,qr));
    return ans;
}

int query1(int id,int l,int r,int ql,int qr) {
    if ((l>=ql)&&(r<=qr)) return seg[id][1];
    int mid=(l+r)>>1,ans=0;
    if (ql<=mid) ans=max1(ans,query1(id<<1,l,mid,ql,qr));
    if (qr>mid) ans=max1(ans,query1(id<<1|1,mid+1,r,ql,qr));
    return ans;
}

void build(int id,int l,int r) {
    if (l==r) {
        seg[id][0]=seg[id][1]=l;
        return;
    }
    int mid=(l+r)>>1;
    build(id<<1,l,mid); build(id<<1|1,mid+1,r);
    seg[id][0]=max0(seg[id<<1][0],seg[id<<1|1][0]);
    seg[id][1]=max1(seg[id<<1][1],seg[id<<1|1][1]);
}

int main() {
    //ios::sync_with_stdio(false);
    //cin.tie(0); cout.tie(0);
    int T;cin>>T;
    while (T--) {
        int st,ed;
        cin>>n>>st>>ed;
        rep(i,1,n) cin>>a[i];
        rep(i,1,n) {
            b[i]=i+a[i];
            c[i]=i-a[i];
        }
        b[0]=0;c[0]=n*3;
        build(1,1,n);
        q.push(mkp(st,0));
        while (!q.empty()) {
            pii now=q.front();q.pop();
            int u=now.fir;
            if (u==ed) {
                cout<<now.sec<<endl;
                break;
            }
            if (vis[u]) continue;vis[u]=1;
            int l=max(1,u-a[u]),r=min(n,u+a[u]);
            while (1) {
                int v=query0(1,1,n,l,u);
                if (b[v]<u) break;
                q.push(mkp(v,now.sec+1));
                modify(1,1,n,v,0);
            }
            while (1) {
                int v=query1(1,1,n,u,r);
                if (c[v]>u) break;
                q.push(mkp(v,now.sec+1));
                modify(1,1,n,v,1);
            }
        }
        while (!q.empty()) q.pop();
        rep(i,1,n) vis[i]=0;
    }
    return 0;
}

G. Gastronomic Event

Coo

H. Boundary

Considering the case of equal length and width, it is not difficult to find that there are only \ ((n-1, m-1), (n, m-2), (n-2, m) \)

Considering the case of unequal length and width, one of the two groups of numbers \ (n, n-2 \) and \ (m, m-2 \) must exist at the same time, so only 2 may be legal

set<int> s;
void solve(int n,int m) {
    if ((n<0)||(m<0)) return;
    int d=__gcd(n,m);
    for (int i=1;i*i<=d;i++) {
        if (d%i==0) {s.insert(i);s.insert(d/i);}
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;cin>>T;
    while (T--) {
        int n,m;
        cin>>n>>m;
        s.clear();
        solve(n-1,m-1);
        solve(n,m-2);
        solve(n-2,m);
        s.insert(2);
        int siz=s.size();
        cout<<siz<<" ";
        set<int>::iterator it;
        for (it=s.begin();it!=s.end();it++) cout<<(*it)<<" ";
        cout<<endl;
    }
}

I. Ice Cream Shop

For the \ (I \) th hut Assuming that the distance between the nearest seller and it is \ (d_i \), only when the new store is located in \ ((y_i-d_i, y_i + d_i) \), can we get the benefit of \ (p_i \) (\ (y_i \) is the location of HUT) Direct difference statistics is enough

int n,m,p[N],b[N];
map<ll,ll> a;

int main() {
    cin>>n>>m;
    rep(i,1,n) cin>>p[i];
    rep(i,1,m) cin>>b[i];
    sort(b+1,b+1+m);
    b[m+1]=2e9;b[0]=-200;
    rep(i,1,n) {
        int np=(i-1)*100;
        int pos=lower_bound(b,b+m+2,np)-b;
        int r=pos,l=pos-1;
        ll d=min(b[r]-np,np-b[l]);
        a[np-d]+=p[i];a[np+d]-=p[i];
    }
    ll ans=0,now=0;
    for (auto &x:a) {
        now+=x.sec;
        ans=max(ans,now);
    }
    cout<<ans<<endl;
    return 0;
}

J. Training Camp

Coo

K. Pandemic Restrictions

Coo

L. Il Derby della Madonnina

The simple DP formula is as follows

Disassemble the absolute value. When \ (a_i \ Leq a_j \), there is \ (vt_i + a_i \ GEQ vt_j + a_j \); When \ (a_i & gt; a_j \), there is \ (vt_i-a_i \ GEQ vt_j + a_j \)

Record these two equations as (1) and (2) respectively Note that when \ (a_i \ Leq a_j \), if equation (1) is satisfied, equation (2) is automatically satisfied; When \ (a_i & gt; a_j \), if equation (2) is satisfied, equation (1) will be satisfied automatically Therefore, the two dimensions of \ ((vt_i + a_i, vt_i-a_i) \) in the set composed of the last legal \ (I \) are monotonically increasing It can be processed in the way of LIS

int n,a[N],b[N],t[N],tot;
ll v,f[N];
pair<ll,ll> p[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>v;
    rep(i,1,n) cin>>t[i];
    rep(i,1,n) cin>>a[i];
    rep(i,1,n) p[i]=mkp(v*t[i]-a[i],v*t[i]+a[i]);
    sort(p+1,p+n+1);
    rep(i,1,n) {
        ll tmp=p[i].sec;
        if ((p[i].fir<0)||(p[i].sec<0)) continue;
        if (tmp>=f[tot]) f[++tot]=tmp;
        else {
            int p=upper_bound(f+1,f+1+tot,tmp)-f;
            f[p]=tmp;
        }
    }
    cout<<tot;
    return 0;
}

M. Bottle Arrangements

If it is legal, there must be a form such as RR RWW… W’s plan

int n,m;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;cin>>T;
    while (T--) {
        cin>>n>>m;
        int mx1=0,mx2=0;
        rep(i,1,m) {
            int r,w;
            cin>>r>>w;
            mx1=max(r,mx1);
            mx2=max(w,mx2);
        }
        if (mx1+mx2>n) cout<<"IMPOSSIBLE";
        else {
            mx2=n-mx1;
            rep(i,1,mx1) cout<<"R";
            rep(i,1,mx2) cout<<"W";
        }
        cout<<endl;
    }
}

N. Drone Photo

Consider the following legal circumstances

1---2       1---3
|   |       |   |
|   |       |   |
3---4       2---4

Notice that for all legal situations, there must be exactly two positions So that its size is in the middle of the triplet composed of two numbers adjacent to it in its own and legal case

For the following illegal situations

1---4       1---3
|   |       |   |
|   |       |   |
3---2       4---2

There must be no position in the above

Directly count the total number of triples in the above description. According to the analysis, it is exactly twice the answer

int n,a[N][N],r[N][N],c[N][N],row[N],col[N];
pii pos[N*N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n;
    rep(i,1,n) rep(j,1,n) {
        cin>>a[i][j];
        pos[a[i][j]]=mkp(i,j);
    }
    rep(x,1,n*n) {
        int i=pos[x].fir,j=pos[x].sec;
        r[i][j]=row[i];
        c[i][j]=col[j];
        row[i]++;col[j]++;
    }
    ll ans=0;
    rep(i,1,n) rep(j,1,n) ans+=(n-1-r[i][j])*c[i][j]+r[i][j]*(n-1-c[i][j]);
    cout<<ans/2<<endl;
    return 0;
}

O. Circular Maze

Note that the number of \ ((R, \ theta) \) in the problem polar coordinates is not large in the discrete sense So you can use an array to express all the restrictions, and then use DFS from the origin See the following procedure for details

int n,a[21][400],b[400],c[21][400];
int vis[21][400];
string s;

void dfs(int r,int d) {
    if (vis[r][d]) return;
    vis[r][d]=1;
    if (r==20) return;
    int dl=0,dr=360;
    if (b[r]>1) {
        dl=d;dr=(d+1)%360;
        while (!c[r][dl]) dl=(dl-1+360)%360;
        while (!c[r][dr]) dr=(dr+1)%360;
    }
    while (dl!=dr) {
        if (!a[r+1][dl]) dfs(r+1,dl);
        if ((r)&&(!a[r][dl])) dfs(r-1,dl);
        if ((dr==360) && (dl==359)) break;
        dl=(dl+1)%360;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;cin>>T;
    while (T--) {
        rep(i,0,20) {
            b[i]=0;
            rep(j,0,359) c[i][j]=a[i][j]=vis[i][j]=0;
        }
        cin>>n;
        rep(i,1,n) {
            cin>>s;
            if (s[0]=='C') {
                int r,d1,d2;
                cin>>r>>d1>>d2;
                while (d1!=d2) {
                    a[r][d1]=1;
                    d1=(d1+1)%360;
                }
            } else {
                int r1,r2,d;
                cin>>r1>>r2>>d;
                while (r1<r2) {
                    c[r1][d]=1;
                    b[r1]++;
                    r1++;
                }
            }
        }
        dfs(0,0);
        int ok=0;
        rep(i,0,359) ok|=vis[20][i];
        if (ok) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}