走方格

BFS+一些信息的预处理。

丙下。

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10,P=131;
int d[N][N],g[N][N],h[N][N][2],n;
struct Node{
    int x,y;
};
void bfs(){
    queue<Node> q;
    q.push({1,1});
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            d[i][j]=-1;
    d[1][1]=0;
    while(q.size()){
        Node t=q.front();q.pop();
        int r=t.x,c=t.y;
        if(d[r+1][c]==-1) q.push({r+1,c}),d[r+1][c]=d[r][c]+1;
        if(d[r][c+1]==-1) q.push({r,c+1}),d[r][c+1]=d[r][c]+1;
        for(int i=h[r][c][0];i<=h[r][c][1];i++){
            if(d[r][i]==-1) q.push({r,i}),d[r][i]=d[r][c]+1;
        }
        if(d[n][n]!=-1){
            cout<<d[n][n];
            return;
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>g[i][j];
    for(int i=1;i<=n;i++){
        h[i][1][0]=1;
        for(int j=2;j<=n;j++){
            if(g[i][j]>g[i][j-1]) h[i][j][0]=h[i][j-1][0];
            else h[i][j][0]=j;
        }
        h[i][n][1]=n;
        for(int j=n-1;j>=1;j--){
            if(g[i][j]>g[i][j+1]) h[i][j][1]=h[i][j+1][1];
            else h[i][j][1]=j;
        }
    }
    bfs();
}

2023

二项式反演，仔细观察后发现对于固定的2023会有很多算重的地方，

对于这种与2023的个数相关（202320232023这类数可能会算重1/2/3次）的算重的地方是不能直接减的，采用二项式反演处理才能消掉这种多项式影响。

丙中。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,P=998244353;
int n,m,f[N],g[N];
int qmi(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=ans*a%P;
        a=a*a%P;
        b>>=1;
    }
    return ans;
}
int C(int a,int b){
    return f[a]*qmi(f[a-b]*f[b]%P,P-2)%P;
}
signed main(){
    cin>>n>>m;
    int res=0;
    f[0]=1;
    for(int i=1;i<=n;i++) f[i]=f[i-1]*i%P;
    for(int i=m;i<=n/4;i++) g[i]=qmi(10,n-4*i)*C(n-3*i,i)%P;
    for(int i=n/4;i>=m;i--){
        if(i-m&1) res=(res-C(i,m)*g[i]%P+P)%P;
        else res=(res+C(i,m)*g[i]%P)%P;
    }
    cout<<res;
}

等腰三角形

等式等于：$\sum_{i}^nmin(\mid a_i - x \mid,\mid a_i - y \mid)$

排序后，选择分界点再计算$x,y$即可。

先取点$x$，对于最有点$x$等于在数轴上取一个点，计算其它点到它的距离，假设左边$l$个点右边$r$个点，则往右平移会减少$r-l$，归纳可知取中位数。点$y$同理。

然而这个数不一定满足不等式，我们需要加上偏量，对于每一个x和满足要求的偏移量最小的y的判断，一个上升一个下降求最小值即可。

乙下。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,a[N],s[N],ans;
int getl(int l,int r,int w){
    return (r-l+1)*w-(s[r]-s[l-1]);
}
int getr(int l,int r,int w){
    return (s[r]-s[l-1])-(r-l+1)*w;
}
int get(int l,int r,int w){
    int mid=lower_bound(a+l,a+r+1,w)-a;
    return getl(l,mid-1,w)+getr(mid,r,w);
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
    ans=get(2,n,a[(2+n)>>1]);
    for(int i=2;i<n;i++){
        int x=a[1+i>>1],y=a[n+i>>1];
        if(2*x<=y){
            int d=y-2*x+1;
            int l=0,r=(d+1)/2;
            while(l<r){
                int mid1=l+(r-l)/3,mid2=r-(r-l)/3;
                int v1=get(1,i,x+mid1)+get(i+1,n,y-max(0ll,d-2*mid1));
                int v2=get(1,i,x+mid2)+get(i+1,n,y-max(0ll,d-2*mid2));
                if(v1<=v2) r=mid2-1;
                else l=mid1+1;
            }
            x+=l,y-=max(0ll,d-2*l);
        }
        ans=min(ans,get(1,i,x)+get(i+1,n,y));
    }
    cout<<ans;
}

彩色二叉树

先将它补全成满二叉树是不会影响答案的，观察后发现往上走等于去掉二进制末尾0/1，往下走等于在末尾加0/1，最多2*dep可以完全覆盖整颗树。

所以直接往上跳加打标记就可以了。

大概会打共$3e6$级别的标记，标记内部是一个单调栈。

查询同理。

难度丙上。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,q;
struct Ed{
    int w,id,col;
};
vector<Ed> tr[N];
void get(int x,int y,int id,int z){
    int ns=0;
    for(auto v:tr[x]){
        if(v.w<=y) ns++;
    }
    while(ns--) tr[x].pop_back();
    tr[x].push_back({y,id,z});
}
auto query(int x,int d){
    int l=0,r=tr[x].size()-1;
    while(l<r){
        int mid=l+r+1>>1;
        if(tr[x][mid].w>=d) l=mid;
        else r=mid-1;
    }
    return tr[x][l];
}
vector<Ed> b;
bool cmp(Ed A,Ed B){
    return A.id>B.id;
}
signed main(){
    cin>>n>>q;
    for(int i=1;i<=q;i++){
        int op,x,y,z;
        cin>>op>>x;
        if(op==1){
            cin>>y>>z;
            while(x){
                get(x,y,i,z);
                if(y==0) break;
                x>>=1;
                y--;
            }
        }
        else{
            int d=0;
            while(x){
                if(tr[x].size()){
                    auto v=query(x,d);
                    if(v.w>=d) b.push_back(v);
                } 
                x>>=1;d++;
            }
            sort(b.begin(),b.end(),cmp);
            if(!b.size()) cout<<0<<"\n";
            else cout<<b[0].col<<"\n";
            b.clear();
        }
    }
}

选段排序

看到区间和排名想到平衡树，

最终区间一定l=p或者r=q。

所以用平衡树维护即可。

#include <bits/stdc++.h>
#define lb(a,y) lower_bound(a.begin(), a.end(), y)
#define ub(a,y) upper_bound(a.begin(), a.end(), y)
using namespace std;

const int N = 2e5 + 10, INF = 1e9;
int n,p,q,a[N],s[N];
vector<int> tr;
int ans,j=1;
int main()
{
    cin>>n>>p>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=q;i>=p;i--){
        tr.insert(lb(tr,a[i]),a[i]);
    }
    ans=max(ans,tr[q-p]-tr[0]);
    for(int i=p-1;i>=1;i--){
        tr.insert(lb(tr,a[i]),a[i]);
        ans=max(ans,tr[q-i]-tr[p-i]);
    }
    tr.clear();
    for(int i=p;i<=q;i++){
        tr.insert(lb(tr,a[i]),a[i]);
    }
    ans=max(ans,tr[q-p]-tr[0]);
    for(int i=q+1;i<=n;i++){
        tr.insert(lb(tr,a[i]),a[i]);
        ans=max(ans,tr[q-p]-tr[0]);
    }
    cout<<ans;
}

难度评分：乙下

最长同类子串

50分暴力

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
char s[N],t[N];
int a[30],b[30],ans;
int main(){
    cin>>s+1>>t+1;
    int n=strlen(s+1),m=strlen(t+1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int op=0;
            memset(a,0,sizeof a);
            memset(b,0,sizeof b);
            for(int k=0;k<=min(n-i,m-j);k++){
                if(a[t[j+k]-'a'+1]==0&&b[s[i+k]-'a'+1]==0){
                    a[t[j+k]-'a'+1]=s[i+k]-'a'+1;
                    b[s[i+k]-'a'+1]=t[j+k]-'a'+1;
                }
                else if(a[t[j+k]-'a'+1]!=s[i+k]-'a'+1||b[s[i+k]-'a'+1]!=t[j+k]-'a'+1){
                    ans=max(k,ans);
                    op=1;
                    break;
                }
            }
            if(!op) ans=max(ans,min(n-i+1,m-j+1));
        }
    }
    cout<<ans;
}

100分正解

考虑到没有什么结构能维护，这启发我们从映射的原理出发，

只需要维护一个字符上一次出现的位置，就可以从距离出发判断了。

这个信息是可以直接用字符串$hash$的技巧储存的，二分后，对于定长的字符串处理这个信息再寻找判断即可。

乙中

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,P=131;
typedef unsigned long long u64;
char s[N],t[N];
int b[32],ans,ne[N],ds[N],n,m;
u64 p[N];
inline vector<u64> get(char s[],int n,int x){
    u64 v=0;vector<u64> res;
    memset(b,0,sizeof b);
    for(int i=1;i<=n;i++){
        if(b[s[i]-'a']) ne[b[s[i]-'a']]=i,ds[i]=i-b[s[i]-'a'];
        else ds[i]=0;
        b[s[i]-'a']=i;
        if(i<=x) v=v*P+ds[i];
    }
    res.push_back(v);
    for(int i=1;i<=n;i++) if(!ne[i]) ne[i]=n+1;
    for(int i=x+1;i<=n;i++){
        v-=p[x-1]*ds[i-x];
        if(ne[i-x]<i){
            v-=ds[ne[i-x]]*p[i-1-ne[i-x]];
            ds[ne[i-x]]=0;
        }
        else ds[ne[i-x]]=0;
        v=v*P+ds[i];
        res.push_back(v);
    }
    return res;
}
inline bool check(int x){
    auto S=get(s,n,x),T=get(t,m,x);
    if(T.size()>S.size()){
        sort(T.begin(),T.end());
        for(auto i:S) if(T[lower_bound(T.begin(),T.end(),i)-T.begin()]==i) return 1;
    }
    else{
        sort(S.begin(),S.end());
        for(auto i:T) if(S[lower_bound(S.begin(),S.end(),i)-S.begin()]==i) return 1;
    }
    return 0;
}
int main(){
    cin>>s+1>>t+1;
    n=strlen(s+1),m=strlen(t+1);
    int l=1,r=min(n,m);p[0]=1;
    for(int i=1;i<=max(n,m);i++) p[i]=p[i-1]*P;
    while(l<r){
        int mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l;
}

刷题时间：4h