In mathematics you don't understand things, you just get used to them.

分类 笔记 下的文章

Description

Link

给出一个二维平面以及一些点,保证点不在同行 / 同列。每次询问求出一个子矩阵里面的顺序对。

Solution

卡常,卡你吗。

膜拜 dX。

基本是把 dX 的题解贺了过来所以没啥参考的价值。

不过有很多细节的处理不一样,大概能算个 $\frac{1}{50}$ 成新?

对序列分块,把贡献分成 整块 - 散块 / 整块 - 整块/ 散块 - 整块 / 散块 - 散块 以及 散块内部 / 整块内部 共六种贡献。

记 $\textit{ans}_{0}(l,r,x,y)$ 为询问 $l,r,x,y$ 的答案。

同时预处理出 $\textit{lb}(i,j),\textit{ub}(i,j)$ 分别表示在块 $i$ 中数 $j$ 的 std::lower_bound / std::upper_bound 值,下文如果写成单元函数的形式那么就是省去了第一维。

以及预先做一个块内排序,记为 $\textit{ord}(i,j)$,表示块 $i$ 中排序后的第 $j$ 个元素。

注意本文在每个 subtask 定义的东西在其他 subtask 依然适用

  • 散块 - 散块;

两边的都是 $\sqrt{n}$ 级别,拉出来分别排序后归并计算顺序对即可。

  • 散块内部

考虑如何对 $\textit{ans}_{0}(l,r,x,y)$ 进行容斥。

主要矛盾集中在:会出现 $(a\in[1,x),b\in[x,y])$ 这样的贡献。令 $\textit{cnt}_{0}(i,j)$ 表示 $[\textit{lp},i]$ 中 $\textit{rank}_{1}$ 小于 $j$ 的数的数量,其中 $\textit{lp}$ 是当前块的左端点,下同,如果出现 $\textit{rp}$ 同理,$\textit{rank}_{1}$ 的定义见下文。

则容斥可以写为 $\textit{ans}_{0}(l,r,x,y)=\textit{ans}_{0}(l,r,1,y)-\textit{ans}_{0}(l,r,1,x-1)-\sum_{i=l}^{r}[a_{i}\in[x,y]]\cdot\textit{cnt}_{0}(i,\textit{lb}(x)-1)$。

又有 $\textit{ans}_{0}(l,r,1,x)=\sum_{i=l}^{r}[a_{i}\leqslant x]\cdot\textit{cnt}_{0}(i,\textit{rank}_{1}(i))$,我们就可以做到单次 $\mathcal{O}(\sqrt{n})$,注意的 $l,r$ 触及散块边界者不同时,对 $\textit{cnt}_{0}$ 的容斥也有区别。

  • 整块 - 整块

令 $\textit{cnt}_{1}(i,j)$ 为块 $[1,i]$ 中 $\leqslant j$ 的元素个数,$\textit{ans}_{1}(L,R,x,y)$ 为块 $[L,R]$ 的答案,以及 $\textit{rank}_{0}(i,j)$ 是块 $i$ 中排名 $j$ 的元素在原数组中的下标。

我们掏出传统容斥:$\textit{ans}_{1}(L,R,x,y)=\textit{ans}_{1}(L,R,1,y)-\textit{ans}_{1}(L,R,1,x-1)-\sum_{i=L}^{R}P_{i}Q_{i}$,$P_{i}$ 是块 $[L,i)$ 中 $<x$ 的元素个数,$Q_{i}$ 是块 $i$ 种 $\in[x,y]$ 的元素个数。

考虑算 $\textit{ans}_{1}(L,R,1,x)$。

定义 $\textit{rank}_{1}(i,j)$ 为块 $i$ 中第 $j$ 个元素的排名(从小到大,下同),$\textit{rank}_{2}(i,j)$ 为块 $i$ 中满足 $<j$ 的最大元素的排名,$\textit{pre}_{b}(i,j)$ 为块 $[i,j]$ 中所有 $<\textit{rank}_{1}(i,j)$ 的元素数量。

易知 $\textit{pre}_{b}(i,j)=\textit{cnt}_{1}(i,\textit{rank}_{1}(i,j)-1)$,再定义 $\overset{\sqrt{n},\sqrt{n},\sqrt{n}}{\textit{cp}_{0}(i,L,r)}$ 为块 $[1,L]$ 与块 $i$ 前 $r$ 小的元素组成的顺序对数量,同样易知 $\textit{cp}_{0}(i,L,r)=\sum_{k\in T}[\textit{rank}_{1}(i,k)\leqslant r]\cdot\textit{pre}_{b}(L,\textit{rank}_{1}(i,k))$,其中 $T$ 是块 $i$ 的元素集。但这样搞状态数 $\mathcal{O}(n\sqrt{n})$ 转移还要 $\mathcal{\sqrt{n}}$ 而且不好前缀和。

不过可以发现使用 $\textit{ord}$ 数组 $\textit{cp}_{0}$ 就可以递推了:$\textit{cp}_{0}(i,L,r)=\sum_{k=lp}^{r+lp-1}\textit{pre}_{b}(L,k)=\textit{cp}_{0}(i,L,r-1)+\textit{pre}_{b}(L,r+lp-1)$。

然后 $\textit{ans}_{1}(L,R,1,x)=\sum_{i=L+1}^{R}\textit{cp}_{0}(i,i-1,\textit{rank}_{2}(i,x))-\textit{cp}_{0}(i,L-1,\textit{rank}_{2}(i,x))$。

预处理 $\textit{cp}_{0}$ 是 $\mathcal{O}(n\sqrt{n})$,单次回答 $\mathcal{O}(\sqrt{n})$。

  • 散块 - 整块

枚举散块里面的元素,利用 $\textit{cnt}_{1}(i,j)$ 计算答案。

具体是令散块元素集为 $T$,整块编号为 $L,R$, $\sum_{i\in T}\textit{cnt}_{1}(R,i)-\textit{cnt}_{1}(L-1,i)$。

  • 整块 - 散块

和上面有什么区别吗?

  • 整块内部

预处理数组 $\overset{\sqrt{n},\sqrt{n},\sqrt{n}}{\textit{cp}_{1}(i,x,y)}$ 表示取 $\textit{ord}(i,x\dots y)$ 组成的序列的顺序对数量。

用 $\textit{rank}_{0}$ 来预处理:$\textit{cp}_{1}(i,x,y)=\textit{cp}_{1}(i,x,y-1)+\textit{cnt}_{0}(\textit{rank}_{0}(i,y),y-1)-\textit{cnt}_{0}(\textit{rank}_{0}(i,y),x-1)$。


综上,这个问题得以一个 $\mathcal{O}(n\sqrt{n})$ 的在线算法解决。

代码也是抄的 dX,像个 shit 一样就折叠了。

//almost copied from dead_X sry
//kouhu has no qiantu
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int Read()
{
    int x=0;char c=getchar();
    while(c<'0' || c>'9') c=getchar();
    while(c>='0' && c<='9') x=x*10+(c&15),c=getchar();
    return x;
}
const int N=101111,A=460,BS=A+10;
ll cp0[BS][BS][BS];
int a[N],rk0[BS][BS],cnt0[BS][N],cp1[BS][BS][BS],lb[BS][N],rk1[N],cnt1[BS][N],L[BS],R[BS];
bool cmp(int x,int y) { return a[x]<a[y]; }
namespace IO{
    const int sz=1<<22;
    char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[105];
    inline char gc(){
        return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++;
    }
    template<class T> void gi(T& x){
        x=0; char c=gc();
        for(;c<'0'||c>'9';c=gc());
        for(;c>='0'&&c<='9';c=gc())
            x=(x<<3)+(x<<1)+(c-'0');
    }
    inline void flush(){fwrite(b,1,t-b,stdout),t=b; }
    inline void pc(char x){*t++=x; if(t-b==sz) flush(); }
    template<class T> void pi(T x,char c='\n'){
        if(x<0) x=-x;
        if(x==0) pc('0'); int t=0;
        for(;x;x/=10) p[++t]=x%10+'0';
        for(;t;--t) pc(p[t]); pc(c);
    }
    struct F{~F(){flush();}}f; 
}
using IO::gi;
using IO::pi;
inline int read() { int r; gi(r); return r; }
int main(){
#ifdef ONLINE_JUDGE
    freopen("tears.in","r",stdin);
    freopen("tears.out","w",stdout);
#endif
    int n=read(),m=read(),B=n/A;
    for(int i=0;i<n;++i)a[i]=read();
    for(int i=n;i<(B+1)*A;++i)a[i]=i;
    for(int i=0;i<=B;++i){
        for(int j=i*A,k=0;k<A;++j,++k)rk0[i][k]=j;
        sort(rk0[i],rk0[i]+A,[](int x,int y){return a[x]<a[y];});
        for(int j=0;j<A;++j)rk1[rk0[i][j]]=j,cnt0[j][rk0[i][j]]=1;
        for(int j=i*A+1;j<(i+1)*A;++j)
            for(int k=0;k<A;++k)cnt0[k][j]+=cnt0[k][j-1];
        for(int j=i*A;j<(i+1)*A;++j)
            for(int k=1;k<A;++k)cnt0[k][j]+=cnt0[k-1][j];
        for(int j=i*A;j<(i+1)*A;++j)++cnt1[i][a[j]];
        if(i)for(int j=1;j<=101000;++j)cnt1[i][j]+=cnt1[i-1][j];
        for(int j=1,k=0;j<=101000;++j)(k<A)&&(j>=a[rk0[i][k]])&&(++k),lb[i][j]=k;
    }
    for(int i=0;i<=B;++i)
        for(int j=1;j<=101000;++j)cnt1[i][j]+=cnt1[i][j-1];
    for(int i=1;i<B;++i)for(int j=0;j<i;++j)for(int k=0;k<A;++k)
        cp0[i][j][k+1]=cnt1[j][a[rk0[i][k]]]+cp0[i][j][k];
    for(int i=0;i<B;++i)for(int j=0;j<A;++j)for(int k=j+1;k<A;++k)
        cp1[i][j][k]=cp1[i][j][k-1]+cnt0[k-1][rk0[i][k]]-((j==0)?0:cnt0[j-1][rk0[i][k]]);
    for(;m;--m){
        int l=read()-1,r=read()-1,x=read(),y=read(),bl=l/A,br=r/A;
        if(bl==br){
            int ans=0;
            for(int i=l;i<=r;++i){
                if(x<=a[i]&&a[i]<=y&&rk1[i])ans+=cnt0[rk1[i]-1][i]-((l%A)?cnt0[rk1[i]-1][l-1]:0);
                if(lb[bl][x-1]&&x<=a[i]&&a[i]<=y)ans-=cnt0[lb[bl][x-1]-1][i]-((l%A&&lb[bl][x-1])?cnt0[lb[bl][x-1]-1][l-1]:0);
            }
            pi(ans);
        }
        else{
            ll ans=0;
            for(int i=l;i<(bl+1)*A;++i){
                if(x<=a[i]&&a[i]<=y&&rk1[i])ans+=cnt0[rk1[i]-1][i]-((l%A)?cnt0[rk1[i]-1][l-1]:0);
                if(lb[bl][x-1]&&x<=a[i]&&a[i]<=y)ans-=cnt0[lb[bl][x-1]-1][i]-((l%A&&lb[bl][x-1])?cnt0[lb[bl][x-1]-1][l-1]:0);
                if(x<=a[i]&&a[i]<=y)ans+=cnt1[br-1][y]-cnt1[bl][y]-cnt1[br-1][a[i]]+cnt1[bl][a[i]];
            }
            for(int i=br*A;i<=r;++i){
                if(x<=a[i]&&a[i]<=y&&rk1[i])ans+=cnt0[rk1[i]-1][i];
                if(lb[br][x-1]&&x<=a[i]&&a[i]<=y)ans-=cnt0[lb[br][x-1]-1][i];
                if(x<=a[i]&&a[i]<=y)ans+=cnt1[br-1][a[i]]-cnt1[bl][a[i]]-cnt1[br-1][x-1]+cnt1[bl][x-1];
            }
            int lt=0,rt=0;
            for(int i=0;i<A;++i){
                if(rk0[bl][i]>=l&&x<=a[rk0[bl][i]]&&a[rk0[bl][i]]<=y)L[++lt]=rk0[bl][i];
                if(rk0[br][i]<=r&&x<=a[rk0[br][i]]&&a[rk0[br][i]]<=y)R[++rt]=rk0[br][i];
            }
            for(int i=1,t=1;i<=rt;++i){
                while(t<=lt&&a[L[t]]<a[R[i]])++t;
                ans+=t-1;
            }
            for(int i=bl+1;i<br;++i)if(lb[i][y])ans+=cp1[i][lb[i][x-1]][lb[i][y]-1];
            for(int i=bl+2;i<br;++i)
                ans+=cp0[i][i-1][lb[i][y]]-cp0[i][bl][lb[i][y]]-cp0[i][i-1][lb[i][x-1]]+cp0[i][bl][lb[i][x-1]],
                ans-=ll(cnt1[i][y]-cnt1[i-1][y]-cnt1[i][x-1]+cnt1[i-1][x-1])*(cnt1[i-1][x-1]-cnt1[bl][x-1]);
            pi(ans);
        }
    }
    return 0;
}

我是傻逼。

「CF 1539A」Contest Start

Link.

答案是 $\sum_{i=1}^{n-1}\min\{i,\lfloor\frac{t}{x}\rfloor\}$,等差数列求和优化。

#include<bits/stdc++.h>
#define con(typ) const typ
typedef long long ll;
#define all(x) (x).begin(),(x).end()
using namespace std;
template<typename T>void sf(T &x){x=0;T f=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^'0');if(f)x=-x;}
template<typename T>void pf(T x,char l='\n'){static int s[100],t;if(x<0)putchar('-'),x=-x;do s[++t]=x%10,x/=10;while(x);while(t)putchar(s[t--]^'0');putchar(l);}
int main(){
    int T;
    ll n,x,t;
    for(sf(T);T;--T){
        sf(n),sf(x),sf(t);
        ll ans=0,d=t/x;
        --n;
        if(n>=d)ans=(n-d)*d+d*(d+1)/2;
        else ans=n*(n+1)/2;
        pf(ans);
    }
    return 0;
}

「CF 1539B」Love Song

Link.

暴力。

#include<bits/stdc++.h>
#define con(typ) const typ
typedef long long ll;
#define all(x) (x).begin(),(x).end()
using namespace std;
template<typename T>void sf(T &x){x=0;T f=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^'0');if(f)x=-x;}
template<typename T>void pf(T x,char l='\n'){static int s[100],t;if(x<0)putchar('-'),x=-x;do s[++t]=x%10,x/=10;while(x);while(t)putchar(s[t--]^'0');putchar(l);}
int cap[100010][26],n,q;
char ch[100010];
int main(){
    sf(n),sf(q);
    scanf("%s",ch+1);
    for(int i=1;i<=n;++i){
        memcpy(cap[i],cap[i-1],sizeof(int)*26);
        cap[i][ch[i]-'a']++;
    }
    for(int l,r;q;--q){
        sf(l),sf(r);
        ll ans=0;
        for(int i=0;i<26;++i)ans+=(i+1)*(cap[r][i]-cap[l-1][i]);
        pf(ans);
    }
    return 0;
}

「CF 1539C」Stable Groups

Link.

贪心。

对原序列差分,把差分值拿出来排序后把前几个填了。正确性显然。

#include<bits/stdc++.h>
#define con(typ) const typ
typedef long long ll;
#define all(x) (x).begin(),(x).end()
using namespace std;
template<typename T>void sf(T &x){x=0;T f=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^'0');if(f)x=-x;}
template<typename T>void pf(T x,char l='\n'){static int s[100],t;if(x<0)putchar('-'),x=-x;do s[++t]=x%10,x/=10;while(x);while(t)putchar(s[t--]^'0');putchar(l);}
int n;
ll a[200010],k,x,df[200010];
int main(){
    sf(n);sf(k);sf(x);for(int i=1;i<=n;++i)sf(a[i]);
    sort(a+1,a+n+1);
    for(int i=2;i<=n;++i)df[i]=a[i]-a[i-1];
    vector<ll> ald;
    for(int i=2;i<=n;++i){
        if(df[i]>x)ald.emplace_back(df[i]);
    }
    sort(all(ald));
    int del=0;
    for(int i=0;i<int(ald.size());++i){
        ll w=ald[i];
        if(w%x==0){
            if(k>=w/x-1)k-=w/x-1,++del;
            else break;
        }
        else{
            if(k>=w/x)k-=w/x,++del;
            else break;
        }
    }
    pf(int(ald.size())-del+1);
    return 0;
}

「CF 1539D」PriceFixed

Link.

以 $b$ 为关键字排序。

首先考虑把第一个元素「激活」,即填满 $b_{1}$ 个商品。

然后后面的元素有两种决策:

  1. 使用前面已经「激活」的商品来「激活」该商品后买完;
  2. 直接买 $a_{i}$ 个,注意分 $a_{i},b_{i}$ 大小讨论。

两种决策会使总买入商品数不一致,对后面有影响(?)。

现在考场上那个傻逼在想 DP。

但是注意到这样搞的代价是没有差别的,$2-1=1$ 抵了。

那么就一定存在一种最优方案使得每种产品买恰好 $a_{i}$ 个,搞两个指针扫一下就行了。

#include<bits/stdc++.h>
#define con(typ) const typ
typedef long long ll;
#define all(x) (x).begin(),(x).end()
using namespace std;
template<typename T>void sf(T &x){x=0;T f=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^'0');if(f)x=-x;}
template<typename T>void pf(T x,char l='\n'){static int s[100],t;if(x<0)putchar('-'),x=-x;do s[++t]=x%10,x/=10;while(x);while(t)putchar(s[t--]^'0');putchar(l);}
struct st{ll a,b;}a[100010];
int n;
int main(){
    sf(n);for(int i=1;i<=n;++i)sf(a[i].a),sf(a[i].b);
    sort(a+1,a+n+1,[](st x,st y){return x.b<y.b || (x.b==y.b && x.a<y.a);});
    ll nw=0,ans=0;
    for(int i=1,j=n;i<=j;){
        if(nw>=a[i].b){
            ans+=a[i].a;
            nw+=a[i].a;
            ++i;
        }
        else{
            if(a[j].a+nw>=a[i].b){
                ll temp=a[i].b-nw;
                ans+=2*temp;
                nw+=temp;
                a[j].a-=temp;
            }
            else{
                ans+=a[j].a*2;
                nw+=a[j].a;
                --j;
            }
        }
    }
    pf(ans);
    return 0;
}

「CF 1539E」Game with Cards

Link.

gap 略大。搞不动先咕着。

「CF 1539F」Strange Array

Link.

假的,懒得写了,具体看 Rainybunny 的评论吧。

$\ \ \ \ $F:发现对于某个 $a_{i}$,已知包含它的某个区间中,$\le a_{i}$ 与 $>a_{i}$ 的数的数量差就能得到它的特征值。不妨令“大于等于”为 $+1$,“小于”为 $-1$,线段树维护区间最大前缀和与最大后缀和,升序扫描 $a$ 值就能更新答案。$+1,-1$ 反过来再做一遍,最后是 $\mathcal O(n\log_{2}n)$ 的。
$\ \ \ \ $赛后瞬间补题的原因大概是细节有点多√

#include<bits/stdc++.h>
#define con(typ) const typ
typedef long long ll;
#define all(x) (x).begin(),(x).end()
using namespace std;
template<typename T>void sf(T &x){x=0;T f=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^'0');if(f)x=-x;}
template<typename T>void pf(T x,char l='\n'){static int s[100],t;if(x<0)putchar('-'),x=-x;do s[++t]=x%10,x/=10;while(x);while(t)putchar(s[t--]^'0');putchar(l);}
template<typename T,typename... Tt>void sf(T &x,Tt&... aa){sf(x),sf(aa...);}
int n,a[200010],stp,Segres;
vector<int> ps[200010];
struct node{int p,s,sm;node(int a=0,int b=0,int c=0){p=a;s=b;sm=c;}};
struct Segtree{
    const int n;
    vector<node> ns;
    Segtree(int n,int fl):n(n),ns(n*4+5){give(1,n,1,fl);}
    node mrg(node a,node b){
        node c;
        c.p=max(a.p,a.sm+b.p);
        c.s=max(b.s,b.sm+a.s);
        c.sm=a.sm+b.sm;
        return c;
    }
    void give(int l,int r,int p,int v){
        if(r-l==0){ns[p]=node(max(v,0),max(v,0),v);return;}
        int m=(l+r)/2;
        give(l,m,p*2,v),give(m+1,r,p*2+1,v);
        ns[p]=mrg(ns[p*2],ns[p*2+1]);
    }
    void ins(int l,int r,int p,int x,int v){
        if(r-l==0){ns[p]=node(max(v,0),max(v,0),v);return;}
        int m=(l+r)/2;
        if(m>=x)ins(l,m,p*2,x,v);
        else ins(m+1,r,p*2+1,x,v);
        ns[p]=mrg(ns[p*2],ns[p*2+1]);
    }
    void qpre(int l,int r,int p,int x){
        if(l>=x){stp=max(stp,Segres+ns[p].p);Segres+=ns[p].sm;return;}
        int m=(l+r)/2;
        if(m>=x)qpre(l,m,p*2,x);qpre(m+1,r,p*2+1,x);
    }
    void qsuf(int l,int r,int p,int x){
        if(r<=x){stp=max(stp,Segres+ns[p].s);Segres+=ns[p].sm;return;}
        int m=(l+r)/2;
        if(m<x)qsuf(m+1,r,p*2+1,x);qsuf(l,m,p*2,x);
    }
    void ins(int x,int y){ins(1,n,1,x,y);}
    int qpre(int x){Segres=stp=0;qpre(1,n,1,x);return stp;}
    int qsuf(int x){Segres=stp=0;qsuf(1,n,1,x);return stp;}
};
int main(){
    sf(n);for(int i=1;i<=n;++i)sf(a[i]),ps[a[i]].emplace_back(i);
    int value=1;
    vector<int> ans(n);
    for(int value=1;value>-2;value-=2){
        Segtree t(n,value);
        for(int i=1;i<=n;++i){
            if(value==-1)for(int x:ps[i])t.ins(x,-value);
            for(int x:ps[i]){
                int r0,r1;
                r1=t.qpre(x);
                r0=t.qsuf(x);
                if((r0+r1-1)&1)ans[x-1]=max(ans[x-1],(r0+r1-1)/2);
                else{
                    if(value==1)ans[x-1]=max(ans[x-1],(r0+r1-1)/2);
                    else ans[x-1]=max(ans[x-1],(r0+r1-2)/2);
                }
            }
            if(value==1)for(int x:ps[i])t.ins(x,-value);
        }
    }
    for(int x:ans)pf(x,' ');
    return 0;
}

这 1+2?

「CF1534 A」Colour the Flag

Link.

W / R 拉出来广搜,注意判断全空的情况。

#include <bits/stdc++.h>
using ll = long long;
#define all(x) (x).begin(), (x).end()
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T, n, m;
    std::vector<std::vector<int>> DIR({{1, 0}, {0, 1}, {-1, 0}, {0, -1}});
    for (std::cin >> T; T; --T) {
        std::cin >> n >> m;
        std::vector<std::vector<char>> a(n, std::vector<char>(m));
        std::vector<std::vector<bool>> vis(n, std::vector<bool>(m));
        std::queue<std::pair<int, int>> que;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                std::cin >> a[i][j];
                if (a[i][j] != '.') {
                    que.emplace(i, j);
                    vis[i][j] = true;
                }
            }
        }
        if (que.empty()) {
            a[0][0] = 'R';
            que.emplace(0, 0);
            vis[0][0] = true;
        }
        auto check = [&] (std::pair<int, int> x) {
            return x.first < 0 || x.first >= n || x.second < 0 || x.second >= m;
        };
        bool flag = 0;
        while (!que.empty()) {
            auto x = que.front();
            que.pop();
            for (auto d : DIR) {
                auto y = std::make_pair(x.first + d[0], x.second + d[1]);
                if (check(y)) continue;
                if (a[x.first][x.second] == a[y.first][y.second]) {
                    flag = true;
                    break;
                }
                if (vis[y.first][y.second]) continue;
                vis[y.first][y.second] = true;
                if (a[y.first][y.second] == '.') {
                    if (a[x.first][x.second] == 'R') a[y.first][y.second] = 'W';
                    else a[y.first][y.second] = 'R';
                }
                que.emplace(y);
            }
            if (flag) break;
        }
        if (flag) std::cout << "No\n";
        else {
            std::cout << "Yes\n";
            for (auto x : a) {
                for (auto y : x) std::cout << y;
                std::cout << "\n";
            }
        }
    }
    return 0;
}

「CF1534 B」Histogram Ugliness

Link.

我们只会对比 $i+1$ & $i-1$ 都高 $i$ 进行操作,然后答案显然。

#include <bits/stdc++.h>
using ll = long long;
#define all(x) (x).begin(), (x).end()
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T, n;
    for (std::cin >> T; T; --T) {
        std::cin >> n;
        std::vector<int> a(n);
        for (int &x : a) std::cin >> x;
        a.emplace(a.begin(), 0);
        a.emplace_back(0);
        ll ans = 0;
        for (int i = 1; i <= n + 1; ++i) ans += std::abs(a[i] - a[i - 1]);
        for (int i = 1; i <= n; ++i) {
            if (a[i] > std::max(a[i - 1], a[i + 1])) {
                ans -= a[i] - std::max(a[i - 1], a[i + 1]);
                a[i] = std::max(a[i - 1], a[i + 1]);
            }
        }
        std::cout << ans << "\n";
    }
    return 0;
}

「CF1534 C」Little Alawn's Puzzle

Link.

钦定研究第一行。考虑 $i$ 这个下标,我们对在第二行的 $i$ 连个边,同时对在第二行的 $p_{i}$ 的所在下标连边。

然后数出图里面有多少环,答案就是 $2$ 的环数量次方。

#include <bits/stdc++.h>
using ll = long long;
#define all(x) (x).begin(), (x).end()
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T, n;
    for (std::cin >> T; T; --T) {
        std::cin >> n;
        std::vector<std::vector<int>> a(2, std::vector<int>(n)), idx(2, std::vector<int>(n));
        int cur = 0;
        for (int &x : a[0]) {
            std::cin >> x;
            --x;
            idx[0][x] = cur++;
        }
        for (int &x : a[1]) {
            std::cin >> x;
            --x;
            idx[1][x] = cur++;
        }
        bool flag = false;
        for (int i = 0; i < n; ++i) {
            if (a[0][i] == a[1][i]) {
                flag = true;
                break;
            }
        }
        if (flag) {
            std::cout << "0\n";
            continue;
        }
        std::vector<int> fa(n * 2);
        std::iota(all(fa), 0);
        auto find = [&] (int x) {
            while (fa[x] != x) {
                x = fa[x] = fa[fa[x]];
            }
            return x;
        };
        auto merge = [&] (int x, int y) {
            x = find(x);
            y = find(y);
            fa[x] = y;
        };
        for (int i = 0; i < n; ++i) {
            merge(i, i + n);
            merge(idx[0][a[0][i]], idx[1][a[0][i]]);
        }
        int num = 0;
        for (int i = 0; i < n * 2; ++i) {
            if (fa[i] == i) ++num;
        }
        constexpr int P = 1e9 + 7;
        auto power = [&] (int x, int y) {
            int res = 1;
            for (; y; y >>= 1, x = ll(x) * x % P)
                if (y & 1) res = ll(res) * x % P;
            return (res + P) % P;
        };
        std::cout << power(2, num) << "\n";
    }
    return 0;
}

「CF1534 D」Lost Tree

Link.

首先肯定要钦定一个根,对其进行一次询问。

然后查询出来的相当于是深度。观察次数限制 $\lceil\frac{n}{2}\rceil$,大概是一半的节点。

考虑如何规划一半的节点去询问。一次询问能确定的边就是查询出来距离为 $1$ 的。

注意到相邻奇数偶数之间总是相差 $1$。

然后把节点进行关于深度的奇偶分层,查询 奇 / 偶 中数量较少的节点即可。

#include <bits/stdc++.h>
using ll = long long;
#define all(x) (x).begin(), (x).end()
int main() {
//    std::ios_base::sync_with_stdio(false);
//    std::cin.tie(nullptr);
//    std::cout.tie(nullptr);
    int n;
    std::cin >> n;
    auto ask = [&] (int x) {
        std::cout << "? " << x + 1 << "\n";
        std::vector<int> res(n);
        for (int &x : res) std::cin >> x;
        return res;
    };
    std::vector<int> d = ask(0);
    std::vector<std::pair<int, int>> ans;
    std::vector<std::vector<int>> cat(2);
    for (int i = 0; i < n; ++i) {
        if (d[i] == 1) ans.emplace_back(std::make_pair(0, i));
    }
    for (int i = 1; i < n; ++i) {
        if (d[i] & 1) cat[1].emplace_back(i);
        else cat[0].emplace_back(i);
    }
    std::vector<int> point;
    if (cat[0].size() > cat[1].size()) point = cat[1];
    else point = cat[0];
    for (int x : point) {
        d = ask(x);
        for (int i = 0; i < n; ++i) {
            if (d[i] == 1) ans.emplace_back(std::make_pair(x, i));
        }
    }
    for (auto &x : ans) {
        if (x.first > x.second) std::swap(x.first, x.second);
    }
    std::sort(all(ans));
    ans.erase(std::unique(all(ans)), ans.end());
    std::cout << "!\n";
    for (auto x : ans) std::cout << x.first + 1 << " " << x.second + 1 << "\n";
    return 0;
}

「CF1534 E」Lost Array

Link.

将询问的次数看作一个状态,我们考虑它每次往哪里跑。

如果我们想知道新的 $\texttt{XOR}$ 和可以选择全部查没选过的也可以部分选择。

那么就可以做了,因为 $k$ 很小,BFS 搜即可。

#include <bits/stdc++.h>
using ll = long long;
#define all(x) (x).begin(), (x).end()
int main() {
//    std::ios_base::sync_with_stdio(false);
//    std::cin.tie(nullptr);
//    std::cout.tie(nullptr);
    constexpr int INF = std::numeric_limits<int>::max() / 2;
    int n, k;
    std::cin >> n >> k;
    auto ask = [&] (std::vector<int> v) {
        std::cout << "?";
        for (int x : v) std::cout << " " << x + 1;
        std::cout << "\n";
        int res;
        std::cin >> res;
        return res;
    };
    auto link = [&] (std::vector<int> a, std::vector<int> b) {
        std::vector<int> v;
        for (int x : a) v.emplace_back(x);
        for (int x : b) v.emplace_back(x);
        return v;
    };
    std::vector<int> pre(n + 1, 0), dis(n + 1, INF);
    std::queue<int> que;
    pre[0] = -1;
    dis[0] = 0;
    que.emplace(0);
    while (!que.empty()) {
        int x = que.front();
        que.pop();
        for (int i = 1; i <= k; ++i) {
            if (i <= n - x && k - i <= x) {
                int y = x + i * 2 - k;
                if (dis[y] == INF) {
                    dis[y] = dis[x] + 1;
                    pre[y] = x;
                    que.emplace(y);
                }
            }
        }
    }
    if (dis[n] == INF) {
        std::cout << "-1\n";
        return 0;
    }
    std::vector<int> t, f(n), p;
    for (int i = n; ~i; i = pre[i]) p.emplace_back(i);
    std::reverse(all(p));
    int ans = 0;
    std::iota(all(f), 0);
    for (size_t i = 0; i < p.size() - 1; ++i) {
        int x = (p[i + 1] - p[i] + k) / 2, y = k - x;
        std::vector<int> mt, mf;
        for (int j = 0; j < x; ++j) {
            mt.emplace_back(f.back());
            f.pop_back();
        }
        for (int j = 0; j < y; ++j) {
            mf.emplace_back(t.back());
            t.pop_back();
        }
        ans ^= ask(link(mt, mf));
        t.insert(t.end(), all(mt));
        f.insert(f.end(), all(mf));
    }
    std::cout << "! " << ans << "\n";
    return 0;
}

「CF1534 F1」Falling Sand (Easy Version)

Link.

考虑将一块沙块向其能影响到的沙块连有向边。

具体来讲,我们设 $\textit{last}(i,j)$ 为第 $i$ 行第 $j$ 列往下望见的第一个沙块,若没有则设为 $-1$。然后连边方式就是(研究 $(i,j)$):

  1. 首先 $(i,j)$ 本身是沙块;
  2. 向 $\textit{last}(i,j)$ 连边(如果存在,下同);
  3. 若 $(i,j+1)$ 存在,则连 $(i,j+1)$,否则连 $\textit{last}(i,j+1)$;
  4. $(i,j-1)$ 同理。

连出来一张图,你可能觉得这张图里面所有出度为 $0$ 的就是答案,实则需要缩个点,然后才成立(样例 #2 就能 hack 非常良心)。

#include <bits/stdc++.h>
using ll = long long;
#define all(x) (x).begin(), (x).end()
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n, m, cnt = 0;
    std::cin >> n >> m;
    std::vector<std::vector<char>> a(n, std::vector<char>(m));
    std::vector<std::vector<int>> last(n, std::vector<int>(m)), id = last;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            std::cin >> a[i][j];
            if (a[i][j] == '#') id[i][j] = cnt++;
        }
    }
    for (int j = 0; j < m; ++j) {
        int pos = -1;
        for (int i = n - 1; ~i; --i) {
            last[i][j] = pos;
            if (a[i][j] == '#') pos = i;
        }
    }
    int col = 0, tot = 0;
    std::vector<std::pair<int, int>> edgeSet;
    std::vector<std::vector<int>> e(cnt);
    std::vector<int> color(cnt), order(cnt), low(cnt);
    std::vector<bool> inStk(cnt);
    std::stack<int> stk;
    auto add = [&] (int x, int y) {
        e[x].emplace_back(y);
        edgeSet.emplace_back(std::make_pair(x, y));
    };
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (a[i][j] == '#') {
                if (j < m - 1) {
                    if (a[i][j + 1] == '#') add(id[i][j], id[i][j + 1]);
                    else if (~last[i][j + 1]) add(id[i][j], id[last[i][j + 1]][j + 1]);
                }
                if (j > 0) {
                    if (a[i][j - 1] == '#') add(id[i][j], id[i][j - 1]);
                    if (~last[i][j - 1]) add(id[i][j], id[last[i][j - 1]][j - 1]);
                }
                if(~last[i][j]) add(id[i][j], id[last[i][j]][j]);
                if (i > 0) {
                    if (a[i - 1][j] == '#') add(id[i][j], id[i - 1][j]);
                }
            }
        }
    }
    std::function<void(int)> compress = [&] (int x) {
        order[x] = low[x] = tot++;
        inStk[x] = true;
        stk.emplace(x);
        for (int y : e[x]) {
            if (!order[y]) {
                compress(y);
                low[x] = std::min(low[x], low[y]);
            }
            else if (inStk[y]) low[x] = std::min(low[x], order[y]);
        }
        if (order[x] == low[x]) {
            int y = 0;
            ++col;
            while (x != y) {
                y = stk.top();
                stk.pop();
                color[y] = col;
                inStk[y] = false;
            }
        }
    };
    for (int i = 0; i < cnt; ++i) {
        if (!order[i]) compress(i);
    }
    std::vector<int> deg(col);
    for (std::pair<int, int> edge : edgeSet) {
        if (color[edge.first] != color[edge.second]) ++deg[color[edge.second]];
    }
    std::cout << std::count(all(deg), 0) << "\n";
    return 0;
}

「CF1534 F2」Falling Sand (Hard Version)

Link.

「CF1534 G」A New Beginning

Link.

「CF1534 H」Lost Nodes

Link.

应该是最近最水的 ABC 了吧。

「ABC 205A」kcal

Link.

#include <bits/stdc++.h>
using ll = long long;
#define all(x) (x).begin(), (x).end()
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    ll a, b;
    std::cin >> a >> b;
    std::cout << b * a / 100.0 << "\n";
    return 0;
}

「ABC 205B」Permutation Check

Link.

排序 / std::set 均可。

#include <bits/stdc++.h>
using ll = long long;
#define all(x) (x).begin(), (x).end()
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n, cur = 0;
    std::cin >> n;
    std::vector<int> a(n);
    for (int &x : a) {
        std::cin >> x;
        --x;
    }
    std::sort(all(a));
    for (int x : a) {
        if (cur != x) {
            std::cout << "No\n";
            return 0;
        }
        ++cur;
    }
    std::cout << "Yes\n";
    return 0;
}

「ABC 205C」POW

Link.

若 $c$ 为偶数则 $a:=|a|,b:=|b|$,然后比较 $a,b$ 大小即可。

#include <bits/stdc++.h>
using ll = long long;
#define all(x) (x).begin(), (x).end()
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int a, b, c;
    std::cin >> a >> b >> c;
    if (c % 2 == 0) {
        a = std::abs(a);
        b = std::abs(b);
    }
    if (a > b) std::cout << ">\n";
    else if (a < b) std::cout << "<\n";
    else std::cout << "=\n";
    return 0;
}

「ABC 205D」Kth Excluded

Link.

预处理每一个数空出来的位置,然后询问时二分分类讨论。

#include <bits/stdc++.h>
using ll = long long;
#define all(x) (x).begin(), (x).end()
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n, q;
    std::cin >> n >> q;
    std::vector<ll> a(n), b(n);
    for (ll &x : a) std::cin >> x;
    for (size_t i = 0; i < a.size(); ++i) b[i] = a[i] - i - 1;
    for (ll k; q; --q) {
        std::cin >> k;
        ll pos = std::lower_bound(all(b), k) - b.begin();
        if (pos == n) std::cout << a.back() + k - b.back() << "\n";
        else std::cout << a[pos] - b[pos] + k - 1 << "\n";
    }
    return 0;
}

「ABC 205E」White and Black Balls

Link.

答案显然是 $\binom{n+m}{n}-\binom{n+m}{n-k-1}$。

#include <bits/stdc++.h>
using ll = long long;
#define all(x) (x).begin(), (x).end()
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    constexpr int MOD = 1e9 + 7;
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<ll> fac(n + m + 1), ifac(n + m + 1);
    auto pow = [&] (ll x, int y) {
        ll res = 1;
        for (; y; y >>= 1, x = x * x % MOD)
            if (y & 1) res = res * x % MOD;
        return (res + MOD) % MOD;
    };
    fac[0] = ifac[0] = 1;
    for (int i = 1; i < n + m + 1; ++i) {
        fac[i] = fac[i - 1] * i % MOD;
        ifac[i] = pow(fac[i], MOD - 2);
    }
    auto C = [&] (int n, int k) {return n < k ? 0 : fac[n] * ifac[n - k] % MOD * ifac[k] % MOD;};
    if (n - m > k) std::cout << "0\n";
    else std::cout << (C(n + m, n) - C(n + m, n - k - 1) + MOD) % MOD << "\n"; 
    return 0;
}

「ABC 205F」Grid and Tokens

Link.

网络流板题。

#include <bits/stdc++.h>
#include <atcoder/maxflow>
using ll = long long;
#define all(x) (x).begin(), (x).end()
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int h, w, n;
    std::cin >> h >> w >> n;
    std::vector<std::vector<int>> obj(n, std::vector<int>(2));
    std::vector<int> row(h), col(w);
    auto id = [&] () {
        static int cnt = 0;
        return cnt++;
    };
    const int S = id(), T = id();
    for (int &x : row) x = id();
    for (int &x : col) x = id();
    for (std::vector<int> &x : obj) x = std::vector<int>({id(), id()});
    atcoder::mf_graph<int> G(id());
    for (int x : row) G.add_edge(S, x, 1);
    for (int x : col) G.add_edge(x, T, 1);
    for (int i = 0; i < n; ++i) {
        int a, b, c, d;
        std::cin >> a >> b >> c >> d;
        --a, --b;
        G.add_edge(obj[i][0], obj[i][1], 1);
        for (int j = a; j < c; ++j) G.add_edge(row[j], obj[i][0], 1);
        for (int j = b; j < d; ++j) G.add_edge(obj[i][1], col[j], 1);
    }
    std::cout << G.flow(S, T) << "\n";
    return 0;
}

Description

Link.

$$\sum_{i=1}^n\sum_{j=1}^m\sum_{k=1}^p\gcd(i\cdot j,i\cdot k,j\cdot k)\times \gcd(i,j,k)\times \left(\frac{\gcd(i,j)}{\gcd(i,k)\times \gcd(j,k)}+\frac{\gcd(i,k)}{\gcd(i,j)\times \gcd(j,k)}+\frac{\gcd(j,k)}{\gcd(i,j)\times \gcd(i,k)}\right)$$

Solution

考虑把 $i,j,k$ 分别唯一分解,显然 $ij,jk,ik$ 并没有增加唯一分解后使用的质数数量,仅仅改变了指数。再考虑 $\gcd$ 的本质就是唯一分解后对指数取 $\min$ 的乘积结果。钦定研究一个质因数,设 $i,j,k$ 该质因数的指数分别为 $a,b,c$,则 $\gcd$ 上该位的指数为 $\min(a,b,c)$,我们做这样一个容斥:$\min(a+b,b+c,a+c)=\min(a,b)+\min(a,c)+\min(b,c)-\min(a,b,c)$。证明不妨设 $a<b<c$ 即证。

那么有:

$$ \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{k=1}^{p}(ij,ik,jk)(i,j,k)\left(\frac{(i,j)}{(i,k)(j,k)}+\frac{(i,k)}{(i,j)(j,k)}+\frac{(j,k)}{(i,j)(i,k)}\right) \\ \begin{aligned} &=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{k=1}^{p}\frac{(i,j)(i,k)(j,k)}{(i,j,k)}(i,j,k)\frac{(i,j)^{2}+(i,k)^{2}+(j,k)^{2}}{(i,j)(i,k)(j,k)} \\ &=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{k=1}^{p}(i,j)^{2}+(i,k)^{2}+(j,k)^{2} \\ \end{aligned} $$

注意到三个部分并无本质不同,我们设 $F(n,m,p)=p\sum_{i=1}^{n}\sum_{j=1}^{m}(i,j)^{2}$,答案即 $F(n,m,p)+F(n,p,m)+F(m,p,n)$。接下来推导 $F$,同时钦定 $n<m$:

$$ \sum_{i=1}^{n}\sum_{j=1}^{m}(i,j)^{2} \\ \begin{aligned} &=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}d^{2}[(i,j)=1] \\ &=\sum_{d=1}^{n}d^{2}\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\sum_{t\mid(i,j)}\mu(t) \\ &=\sum_{T=1}^{n}\sum_{d\mid T}d^{2}\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\mu(\frac{T}{d}) \\ \end{aligned} $$

令 $f(x)=\sum_{d|x}d^{2}\mu(\frac{x}{d})$,显然是个积性函数,$f(p)=p^{2}-1$,不需要 $k$ 次方就能做了欸。

#include<bits/stdc++.h>
#define con(typ) const typ
typedef long long ll;
template<typename T>void sf(T &x){x=0;T f=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^'0');if(f)x=-x;}
template<typename T>void pf(T x,char l='\n'){static int s[100],t;if(x<0)putchar('-'),x=-x;do s[++t]=x%10,x/=10;while(x);while(t)putchar(s[t--]^'0');putchar(l);}
con(int) MOD=1e9+7;
int T,n,m,p;
ll mu[20000010],f[20000010],tag[20000010],prime[20000010],cnt;
void makePrime(int l)
{
    mu[1]=f[1]=1;
    for(ll i=2;i<=l;++i)
    {
        if(!tag[i])    prime[++cnt]=i,f[i]=(i*i%MOD-1+MOD)%MOD;
        for(int j=1;j<=cnt && prime[j]*i<=l;++j)
        {
            tag[i*prime[j]]=1;
            if(i%prime[j])    f[i*prime[j]]=f[i]*f[prime[j]]%MOD;
            else
            {
                f[i*prime[j]]=f[i]*prime[j]%MOD*prime[j]%MOD;
                break;
            }
        }
    }
    for(int i=1;i<=l;++i)    f[i]+=f[i-1],f[i]%=MOD;
}
ll cal(int n,int m,int p)
{
    if(n>m)    n^=m^=n^=m;
    ll res=0;
    for(int l=1,r;l<=n;l=r+1)
    {
        r=std::min(n/(n/l),m/(m/l));
        res+=(f[r]-f[l-1]+MOD)*(n/l)%MOD*(m/l)%MOD;
        res%=MOD;
    }
    return (res*p%MOD+MOD)%MOD;
}
int main()
{
    makePrime(2e7);
    for(sf(T);T;--T)    sf(n),sf(m),sf(p),pf(((cal(n,m,p)+cal(n,p,m)%MOD)+cal(m,p,n))%MOD);
    return 0;
}