暑假集训题目合集-1

Day \(n\) 指第 \(n\) 个讲课日，模拟赛过屎，不放了。 # Day1 ## 单调队列优化 DP 一般形如 \(dp_i=\max_{j\in[l_i,r_i]}(f(j))+g(j)\) 的形式可以进行单调队列优化，其中 \(f(i)\) 是一个关于 \(j\) 的函数，\([l_i,r_i]\) 是滑动窗口。 ### 宝物筛选 多重背包优化。\(O(nW\log m)\) 的二进制拆分优化就不讲了。
考虑朴素的 \(O(nWm)\) 转移： \[dp_{j}=\max_{k=0}^{m_i}(dp_{j-k\times w_i}+k\times v_i)\]
尝试改写成适合单调队列优化的形式，按余数分组：
设当前 \(r=j\bmod w_i\)，\(t=\lfloor j/w_i\rfloor\)，状态转移方程改写为： \[dp_j=\max_{k=0}^{\min(m_i,t)}(dp_{r+(t-k)\cdot w_i}+k\cdot v_i)\] 令 \(t'=t-k\)，则 \(k=t-t'\)： \[\begin{aligned} dp_j&=\max(dp_{r+t'\cdot w_i}+(t-t')\cdot v_i)\\ &=\max(dp_{r+t'\cdot w_i}+t'\cdot v_i)+t\cdot v_i \end{aligned}\] \(t'\in[\max(0,t-m_i),t]\)，构成一个滑动窗口。
时间复杂度 \(O(nW)\)。

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=4e4+10;
struct Queue{
    int val,t;
    Queue(){}
    Queue(int val,int t):val(val),t(t){}
}q[N];
int n,W,v,w,m,dp[N],l,r,tag,ans;
int main(){
    read(n,W);
    memset(dp,0xcf,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=n;i++){
        read(v,w,m);
        if(w==0){
            tag+=v*m;
            continue;
        }
        for(int d=0;d<w;d++){
            l=1,r=0;
            for(int t=0;d+t*w<=W;t++){
                int j=t*w+d,val=dp[j]-t*v;
                while(l<=r&&q[r].val<=val) --r;
                q[++r]=Queue(val,t);
                while(l<=r&&q[l].t<t-m) ++l;
                dp[j]=max(q[l].val+t*v,dp[j]);
            }
        }
    }
    for(int i=0;i<=W;i++) ans=max(ans,dp[i]+tag);
    printf("%d\n",ans);
    return 0;
}

[NOI2005] 瑰丽华尔兹

单调队列优化 DP。
容易想到 \(O(nmT)\) 的方程：设 \(dp_{t,i,j}\) 表示在 \((i,j)\) 位置经过 \(t\) 时间的答案，容易写出转移： \[dp_{t,i,j}=\max(dp_{t-1,i,j},dp_{t-1,i',j'}+1)\] 考虑优化成 \(O(nmk)\)，则我们首先将状态优化为 \(dp_{k,i,j}\) 表示第 \(k\) 个区间，在 \((i,j)\) 位置的答案。转移变为 \[dp_{k,i,j}=\max(dp_{k-1,i',j'}+dis)\] 具体地，假设当前在向 \(i\) 的正方向滑行，我们可以写出： \[dp_{k,i,j}=\max_{pos=i-len_k}^i(dp_{k-1,pos,j}-pos)+i\] 其余三个方向同理，这就可以单调队列优化了。
可以滚动数组去掉 \(k\) 这一维。

code

#include<cstdio>
#include<cstring>
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
template<typename T>
inline T Abs(const T &x){return x<0?~x+1:x;}
template<typename T>
inline T Max(const T &a,const T &b){return a<b?b:a;}
constexpr int N=210,fx[]={0,-1,1,0,0},fy[]={0,0,0,-1,1};
struct Queue{
    int val,x,y;
    Queue(){}
    Queue(int val,int x,int y):val(val),x(x),y(y){}
}q[N];
inline int dis(const int &ax,const int &ay,const int &bx,const int &by){
    return Abs(ax-bx)+Abs(ay-by);
}
int n,m,sx,sy,k,dp[N][N],op,l,r,ans;
char s[N][N];
void dfs(int x,int y,int len){
    l=1,r=0;
    while(x>=1&&y>=1&&x<=n&&y<=m){
        if(s[x][y]=='x'){
            l=1,r=0;
            x+=fx[op],y+=fy[op];
            continue;
        }
        while(l<=r&&dp[x][y]>q[r].val+dis(x,y,q[r].x,q[r].y)) --r;
        q[++r]=Queue(dp[x][y],x,y);
        while(l<=r&&(Abs(x-q[l].x)>len||Abs(y-q[l].y)>len)) ++l;
        dp[x][y]=Max(dp[x][y],q[l].val+dis(x,y,q[l].x,q[l].y));
        ans=Max(ans,dp[x][y]);
        x+=fx[op],y+=fy[op];
    }
}
int main(){
    read(n,m,sx,sy,k);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf(" %c",&s[i][j]);
    memset(dp,0xcf,sizeof(dp));
    dp[sx][sy]=0;
    for(int i=1,s,t;i<=k;i++){
        read(s,t,op);
        if(op==1) for(int j=1;j<=m;j++) dfs(n,j,t-s+1);
        else if(op==2) for(int j=1;j<=m;j++) dfs(1,j,t-s+1);
        else if(op==3) for(int j=1;j<=n;j++) dfs(j,m,t-s+1);
        else for(int j=1;j<=n;j++) dfs(j,1,t-s+1);
    }
    printf("%d\n",ans);
    return 0;
}

闲话：《海上钢琴师》真的非常好看！ ### [SCOI2010] 股票交易 设 \(dp_{i,j}\) 表示 \(i\) 天结束时手上有 \(j\) 个股票时的最大收益。转移： - 什么也不做： \[dp_{i,j}=dp_{i-1,j}\] - 买入： \[dp_{i,j}=\max(dp_{i-W-1,j-k}-k\times AP_i)\] - 卖出： \[dp_{i,j}=\max(dp_{i-W-1,j+k}+k\times BP_i)\]

第一个式子没有研究价值，我们看后两个。将式子转化，用 \(k'\) 分别代替 \(j-k\) 和 \(j+k\)： \[dp_{i,j}=\max(dp_{i-W-1,k'}+k'\times AP_i)-j\times AP_i\quad j-k'\le AS_i\] \[dp_{i,j}=\max(dp_{i-W-1,k'}+k'\times BP_i)-j\times BP_i\quad k'-j\le BS_i\] 显然可以单调队列。

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
typedef long long ll;
constexpr int N=2010;
int t,maxp,w,l,r,ap[N],dp[N][N],bp[N],as[N],bs[N],ans; 
struct Queue{
    int val;
    ll k;
    Queue(){}
    Queue(int val,int k):val(val),k(k){}
}q[N];
int main(){
    read(t,maxp,w);
    memset(dp,0xcf,sizeof(dp));
    for(int i=1;i<=t;i++) read(ap[i],bp[i],as[i],bs[i]);
    for(int i=1;i<=t;i++)
        for(int j=0;j<=as[i];j++) dp[i][j]=-ap[i]*j;
    for(int i=1;i<=t;i++){
        for(int j=0;j<=maxp;j++)
            dp[i][j]=max(dp[i][j],dp[i-1][j]);
        l=1,r=0;
        int pre=i-w-1;
        if(pre<=0) continue;
        for(int j=0;j<=maxp;j++){
            while(l<=r&&q[r].val<=dp[pre][j]+j*ap[i]) --r;
            q[++r]=Queue(dp[pre][j]+j*ap[i],j);
            while(l<=r&&j-q[l].k>as[i]) ++l;
            dp[i][j]=max(dp[i][j],q[l].val-j*ap[i]);
        }
        l=1,r=0;
        for(int j=maxp;j>=0;j--){
            while(l<=r&&q[r].val<=dp[pre][j]+j*bp[i]) --r;
            q[++r]=Queue(dp[pre][j]+j*bp[i],j);
            while(l<=r&&q[l].k-j>bs[i]) ++l;
            dp[i][j]=max(dp[i][j],q[l].val-j*bp[i]);
        }
    }
    for(int i=0;i<=maxp;i++) ans=max(ans,dp[t][i]);
    printf("%d\n",ans);
    return 0;
}

玉蟾宫

插一个单调栈典题。
我们考虑枚举行数，对于一行内，维护每一列向上延伸最多的 F 数量（类似直方图）。例如，对于样例

R F F F F F 
F F F F F F 
R R R F F F 
F F F F F F 
F F F F F F

假设我们枚举到最后一行，那么应该向上延伸最多的 F 数量应当是：

      F F F
      F F F
      F F F
F F F F F F
F F F F F F
2 2 2 5 5 5

此时枚举列，同时对向上延伸最多 F 数量维护单调栈。
时间复杂度 \(O(nm)\)。

code

#include<iostream>
using namespace std;
constexpr int N=1010;
struct Stack{
    int h,len;
    Stack(){}
    Stack(int h,int len):h(h),len(len){}
}st[N];
int n,m,top,h[N][N],ans;
char c;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>c;
            h[i][j]=(c=='F')?h[i-1][j]+1:0;
        }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int temp=0;
            while(top&&st[top].h>h[i][j]){
                temp+=st[top].len;
                ans=max(ans,st[top].h*temp);
                --top;
            }
            st[++top]=Stack(h[i][j],temp+1);
        }
        int temp=0;
        while(top){
            temp+=st[top].len;
            ans=max(ans,st[top].h*temp);
            --top;
        }
    }
    cout<<ans*3<<'\n';
    return 0;
}

并查集

[APIO2008] 免费道路

题意：一个边权为 \(0\) 或 \(1\) 的图，求边权和为 \(n-k\) 的生成树。 首先 Kruskal 求最大生成树，求得必须要加入的 \(0\) 边。 再 Kruskal 一遍，先将 \(0\) 边加至 \(k\) 条，然后一直加 \(1\) 边直到求出生成树。

code

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=2e4+10,M=1e5+10;
int n,m,k,fa[N],tot,cnt,ans[N];
struct edge{int u,v,w;}e[M];
bool l(const edge &x,const edge &y){return x.w<y.w;}
bool g(const edge &x,const edge &y){return x.w>y.w;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int main(){
    read(n,m,k);
    for(int i=1;i<=m;i++)
        read(e[i].u,e[i].v,e[i].w);
    sort(e+1,e+1+m,g);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        int u=find(e[i].u),v=find(e[i].v);
        if(u==v) continue;
        fa[u]=v;
        ++tot;
        if(e[i].w==0) ++cnt,e[i].w=-1;
        if(tot==n-1) break;
    }
    if(cnt>k){
        printf("no solution\n");
        return 0;
    }
    sort(e+1,e+1+m,l);
    for(int i=1;i<=n;i++) fa[i]=i;
    tot=0;
    for(int i=1;i<=m;i++){
        int u=find(e[i].u),v=find(e[i].v);
        if(u==v) continue;
        if(e[i].w==-1){
            fa[u]=v;
            e[i].w=0;
            ans[++tot]=i;
        }
        else if(tot<k&&e[i].w==0){
            fa[u]=v;
            ans[++tot]=i;
        }
        else if(tot>=k&&e[i].w==1){
            fa[u]=v;
            ans[++tot]=i;
        }
        if(tot==n-1) break;
    }
    if(tot!=n-1){
        printf("no solution\n");
        return 0;
    }
    for(int i=1;i<=tot;i++){
        int j=ans[i];
        printf("%d %d %d\n",e[j].u,e[j].v,e[j].w);
    }
    return 0;
}

[AHOI2013] 连通图

线段树分治+可撤销并查集。 在时间轴上开线段树，每个节点维护 std::vector 表示当前区间需要加的边，使用可撤销并查集在回溯时撤销当前节点添加的边。

code

#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=1e5+10,M=2e5+10;
int n,m,fa[N],siz[N],k,last[M];
struct Edge{
    int u,v;
    Edge(){}
    Edge(int u,int v):u(u),v(v){}
}edge[M];
vector<Edge> tree[N<<2];
#define ls (u<<1)
#define rs (u<<1|1)
void modify(int u,int l,int r,int x,int y,Edge t){
    if(x<=l&&y>=r){
        tree[u].push_back(t);
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) modify(ls,l,mid,x,y,t);
    if(y>mid) modify(rs,mid+1,r,x,y,t);
}
int find(int x){return fa[x]==x?x:find(fa[x]);}
stack<Edge> st;
inline void merge(int x,int y){
    x=find(x),y=find(y);
    if(x==y) return;
    if(siz[x]>siz[y]) swap(x,y);
    fa[x]=y;
    siz[y]+=siz[x];
    st.push(Edge(x,y));
}
void get_ans(int u,int l,int r){
    int temp=st.size();
    for(Edge x:tree[u]) merge(x.u,x.v);
    if(l==r){
        if(siz[find(1)]==n) printf("Connected\n");
        else printf("Disconnected\n");
    }
    else{
        int mid=(l+r)>>1;
        get_ans(ls,l,mid);
        get_ans(rs,mid+1,r);
    }
    while((int)st.size()>temp){
        Edge x=st.top();
        int u=x.u,v=x.v;
        st.pop();
        siz[v]-=siz[u];
        fa[u]=u;
    }
}
int main(){
    read(n,m);
    for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;
    for(int i=1;i<=m;i++) read(edge[i].u,edge[i].v);
    read(k);
    for(int i=1,c,x;i<=k;i++){
        read(c);
        while(c--){
            read(x);
            if(last[x]+1<=i-1) modify(1,1,k,last[x]+1,i-1,edge[x]);
            last[x]=i;
        }
    }
    for(int i=1;i<=m;i++) modify(1,1,k,last[i]+1,k,edge[i]);
    get_ans(1,1,k);
    return 0;
}

Day2

Trie

[JSOI2009] 电子字典

Trie 题怎么能用 Trie 做呢？
由于串长极小，直接字符串哈希，实现时需要注意以下几个点： - 使用自然溢出哈希； - 记得去重，去重一定不要用 std::set，会 T 飞。

code

#include<cstdio>
#include<cstring>
#include<set>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef unsigned long long ull;
int n,m;
ull base[25],h[25];
gp_hash_table<ull,int> word;
char s[25];
int main(){
    base[0]=1;
    for(int i=1;i<=22;i++) base[i]=base[i-1]*131;
    scanf("%d%d",&n,&m);
    while(n--){
        memset(s,0,sizeof(s));
        memset(h,0,sizeof(h));
        scanf("%s",s+1);
        h[0]=0;
        int len=strlen(s+1);
        for(int i=1;i<=len;i++)
            h[i]=h[i-1]*131+s[i];
        word[h[len]]=m+1;
    }
    while(m--){
        memset(s,0,sizeof(s));
        memset(h,0,sizeof(h));
        h[0]=0;
        scanf("%s",s+1);
        int len=strlen(s+1);
        for(int i=1;i<=len;i++)
            h[i]=h[i-1]*131+s[i];
        if(word.find(h[len])!=word.end()){
            printf("-1\n");
            continue;
        }
        int res=0;
        for(int i=1;i<=len;i++){
            ull hash1=h[i-1]*base[len-i]+(h[len]-h[i]*base[len-i]);
            auto it=word.find(hash1);
            if(it!=word.end()&&it->second!=m)
                it->second=m,++res;
        }
        for(int i=1;i<=len;i++)
            for(char j='a';j<='z';j++){
                if(j==s[i]) continue;
                ull hash1=h[len]-s[i]*base[len-i]+j*base[len-i];
                auto it=word.find(hash1);
                if(it!=word.end()&&it->second!=m)
                    it->second=m,++res;
            }
        for(int i=0;i<=len;i++)
            for(char j='a';j<='z';j++){
                ull hash1=h[i]*base[len-i+1]+j*base[len-i]+(h[len]-h[i]*base[len-i]);
                auto it=word.find(hash1);
                if(it!=word.end()&&it->second!=m)
                    it->second=m,++res;
            }
        printf("%d\n",res);
    }
    return 0;
}

[USACO12DEC] First! G

建 Trie，在 Trie 上查找时对字母连边，拓扑排序判环。

code

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
constexpr int N=3e5+10;
int n,nxt[N][26],tot,e[26][26],indegree[26],cnt,ans[N];
bool ed[N];
string s[N];
inline void insert(string s){
    int p=0;
    for(char c:s){
        int k=c-'a';
        if(!nxt[p][k]) nxt[p][k]=++tot;
        p=nxt[p][k];
    }
    ed[p]=1;
}
bool find(string s){
    int p=0;
    memset(e,0,sizeof(e));
    memset(indegree,0,sizeof(indegree));
    for(char c:s){
        if(ed[p]) return 0;
        int k=c-'a';
        for(int i=0;i<26;i++)
            if(k!=i&&nxt[p][i]&&!e[k][i]){
                e[k][i]=1;
                ++indegree[i];
            }
        p=nxt[p][k];
    }
    queue<int> q;
    for(int i=0;i<26;i++)
        if(!indegree[i]) q.push(i);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int v=0;v<26;v++)
            if(e[u][v]&&!--indegree[v]) q.push(v);
    }
    for(int i=0;i<26;i++)
        if(indegree[i]) return 0;
    return 1;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        insert(s[i]);
    }
    for(int i=1;i<=n;i++)
        if(find(s[i]))
            ans[++cnt]=i;
    cout<<cnt<<'\n';
    for(int i=1;i<=cnt;i++)
        cout<<s[ans[i]]<<'\n';
    return 0;
}

[IOI 2008] Type Printer

显然先建出 Trie，考虑怎样的遍历顺序更优。
发现这不是老熟人吗？

code

#include<iostream>
using namespace std;
constexpr int N=25010;
int n,nxt[N*20][26],tot;
bool ed[N*20],flag[N*20],f;
string maxlen,ans;
void insert(string s){
    int p=0;
    for(char c:s){
        int k=c-'a';
        if(!nxt[p][k]) nxt[p][k]=++tot;
        p=nxt[p][k];
    }
    ed[p]=1;
}
void query(string s){
    int p=0;
    for(char c:s){
        int k=c-'a';
        p=nxt[p][k];
        flag[p]=1;
    }
}
void dfs(int u){
    if(ed[u]) ans.push_back('P');
    int maxk=-1;
    for(int i=0;i<26;i++){
        int v=nxt[u][i];
        if(!v) continue;
        if(flag[v]) maxk=i;
        else{
            ans.push_back(i+'a');
            dfs(v);
        }
    }
    if(~maxk){
        ans.push_back(maxk+'a');
        dfs(nxt[u][maxk]);
    }
    if(flag[u]&&!~maxk){
        cout<<ans.length()<<'\n';
        for(char c:ans)
            cout<<c<<'\n';
        exit(0);
    }
    ans.push_back('-');
}
int main(){
    f=1;
    cin>>n;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        insert(s);
        if(s.length()>maxlen.length()) maxlen=s;
    }
    query(maxlen);
    dfs(0);
    return 0;
}

笛卡尔树

[TJOI2011] 树的序

考虑 BST 每个节点记录权值 \(k\) 和插入的时间 \(t\)，则 \(k\) 满足 BST 的性质，\(t\) 满足小根堆的性质，这样构建的 BST 是一棵 Treap。
题意转化为：重新分配 \(t\)，使得生成序列最小。
既然 \(t\) 维度是小根堆，那么满足父亲小于后代。贪心地想，较小的 \(t\) 分配顺序为：父亲 \(>\) 左子树 \(>\) 右子树，也就是 BST 的前序遍历。 笛卡尔树同样满足 Treap 的性质。它的 \(k\) 与 \(t\) 正好与本题的 BST 相反。则我们只需交换 \(k\) 和 \(t\) 并 \(O(n)\) 构建笛卡尔树即可。

code

#include<cstdio>
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=1e5+10;
int n,a[N],st[N],top,son[N][2];
bool vis[N];
void dfs(int u){
    printf("%d ",u);
    if(son[u][0]) dfs(son[u][0]);
    if(son[u][1]) dfs(son[u][1]);
}
int main(){
    read(n);
    for(int i=1,x;i<=n;i++) read(x),a[x]=i;
    for(int i=1;i<=n;i++){
        int last=0;
        while(top&&a[st[top]]>a[i]) last=st[top--];
        if(top) son[st[top]][1]=i;
        son[i][0]=last;
        st[++top]=i;
    }
    for(int i=1;i<=n;i++)
        vis[son[i][0]]=vis[son[i][1]]=1;
    for(int i=1;i<=n;i++)
        if(!vis[i]){
            dfs(i);
            break;
        }
    return 0;
}

数据结构

最大异或和

可持久化 01 trie 模板题。
操作与主席树类似，对于查询，设我们已经维护了所有的前缀异或和 \(sum_i=\oplus_{j=1}^ia_j\)，则只需最大化 \(sum_{p-1}\oplus sum_n\oplus x\)。后两项是给定的，则我们只需贪心求出答案即可。

code

#include<cstdio>
#include<algorithm>
using std::max;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=6e5+10;
int n,m,nxt[N*25][2],siz[N*25],tot,root[N],sum;
inline void insert(int u,int old,int x){
    root[u]=++tot;
    int p=root[u],q=root[old];
    siz[p]=siz[q]+1;
    for(int i=24;i>=0;i--){
        int c=(x>>i)&1;
        nxt[p][0]=nxt[q][0],nxt[p][1]=nxt[q][1];
        nxt[p][c]=++tot;
        p=nxt[p][c],q=nxt[q][c];
        siz[p]=siz[q]+1;
    }
}
inline int query(int x,int a,int b){
    int p=root[a],q=root[b],res=0;
    for(int i=24;i>=0;i--){
        int c=(x>>i)&1;
        if(siz[nxt[q][c^1]]>siz[nxt[p][c^1]]){
            res|=1<<i;
            p=nxt[p][c^1];
            q=nxt[q][c^1];
        }
        else{
            p=nxt[p][c];
            q=nxt[q][c];
        }
    }
    return res;
}
int main(){
    read(n,m);
    insert(0,0,0);
    for(int i=1,a;i<=n;i++){
        read(a);
        insert(i,i-1,sum^=a);
    }
    char op;
    int x,l,r;
    while(m--){
        op=getchar();
        while(op!='A'&&op!='Q') op=getchar();
        if(op=='A'){
            read(x);
            ++n;
            insert(n,n-1,sum^=x);
        }
        else{
            read(l,r,x);
            int ans;
            if(l==1) ans=max(query(sum^x,0,r-1),sum^x);
            else ans=query(sum^x,l-2,r-1);
            printf("%d\n",ans);
        }
    }
    return 0;
}

[十二省联考 2019] 异或粽子

类似[NOI2010] 超级钢琴的贪心，由于 \(a_i\oplus a_j=a_j\oplus a_i\)，只需使用堆查询最大的 \(2k\) 个，再令答案除以 \(2\)。可以用 Trie 查询全局第 \(k\) 大，方法类似线段树上二分。

code

#include<cstdio>
#include<queue>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
typedef long long ll;
constexpr int N=5e5+10;
int n,k,nxt[N<<5][2],siz[N<<5],tot=1;
ll a[N],ans;
void insert(ll x){
    int p=1;
    ++siz[p];
    for(int i=32;i>=0;i--){
        int c=(x>>i)&1;
        if(!nxt[p][c]) nxt[p][c]=++tot;
        p=nxt[p][c];
        ++siz[p];
    }
}
ll query(ll x,int rnk){
    int p=1;
    ll res=0;
    for(int i=32;i>=0;i--){
        int c=(x>>i)&1;
        if(siz[nxt[p][c]]>=rnk) p=nxt[p][c];
        else{
            rnk-=siz[nxt[p][c]];
            p=nxt[p][c^1];
            res|=1ll<<i;
        }
    }
    return res;
}
struct node{
    int id,rnk;
    ll val;
    node(int id,int rnk,ll val):id(id),rnk(rnk),val(val){}
    bool operator<(const node &x)const{return val<x.val;}
};
priority_queue<node> q;
int main(){
    read(n,k);k<<=1;
    insert(0);
    for(int i=1;i<=n;i++){
        read(a[i]);
        a[i]^=a[i-1];
        insert(a[i]);
    }
    for(int i=0;i<=n;i++)
        q.push(node(i,n+1,query(a[i],n+1)));
    while(k--){
        node u=q.top();
        q.pop();
        ans+=u.val;
        if(u.rnk) q.push(node(u.id,u.rnk-1,query(a[u.id],u.rnk-1)));
    }
    printf("%lld\n",ans>>1);
    return 0;
}

Day3

字符串哈希

[POI 2006] PAL-Palindromes

容易发现，两个回文串 \(A\)，\(B\) 组合成新回文串当且仅当 \(AB\) 等于 \(BA\)。设 \(A\) 的哈希值为 \(a\)，\(B\) 的哈希值为 \(b\)，有 \[a\times base^{|B|}+b=b\times base^{|A|}+a\] 简单移项 \[\frac{a}{base^{|A|}-1}=\frac{b}{base^{|B|}-1}\] 开哈希桶维护即可。

code

#include<iostream>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#include<utility>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
constexpr int mod1=998244353,mod2=1e9+7;
int n;
ll ans;
int qpow(ll a,int b,int p){
    a%=p;
    int res=1;
    while(b){
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
struct pair_hash{
    size_t operator()(const pair<int,int> &x)const{
        size_t seed=0;
        seed^=hash<int>{}(x.first)+0x9e3779b9+(seed<<6)+(seed>>2);
        seed^=hash<int>{}(x.second)+0x9e3779b9+(seed<<6)+(seed>>2);
        return seed;
    }
};
gp_hash_table<pair<int,int>,int,pair_hash> cnt;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    string s;
    for(int i=1,temp;i<=n;i++){
        cin>>temp>>s;
        ll h1=0,h2=0,base1=1,base2=1;
        for(char c:s){
            h1=(h1*131+c)%mod1;
            base1=base1*131%mod1;
            h2=(h2*131+c)%mod2;
            base2=base2*131%mod2;
        }
        ll x=h1*qpow(base1-1,mod1-2,mod1)%mod1;
        ll y=h2*qpow(base2-1,mod2-2,mod2)%mod2;
        ans+=cnt[make_pair(x,y)];
        ++cnt[make_pair(x,y)];
    }
    cout<<ans*2+n;
    return 0;
}

[POI 2012] OKR-A Horrible Poem

\(A\) 的一个子串 \(B\) 能成为 \(A\) 的一个完整周期，当且仅当其长度为 \(A\) 长度的因数。直接枚举因数。判断是否是完整周期的方法：设 \(h_{l,r}\) 表示 \([l,r]\) 的哈希值，则当一个长为 \(len\) 的子串满足 \(h_{l,r-len}=h_{l+len,r}\) 时，其为一个完整周期。先跑一遍线性筛降低枚举因数的时间复杂度。

code

#include<cstdio>
typedef unsigned long long ull;
constexpr int N=5e5+10;
int n,q,e[N],p[N],tot;
ull h[N],base[N];
char s[N];
ull gethash(int l,int r){return h[r]-h[l-1]*base[r-l+1];}
int main(){
    scanf("%d %s %d",&n,s+1,&q);
    base[0]=1;
    for(int i=1;i<=n;i++){
        base[i]=base[i-1]*131;
        h[i]=h[i-1]*131+s[i];
    }
    for(int i=2;i<=n;i++){
        if(!e[i]) p[e[i]=++tot]=i;
        for(int j=1;j<=e[i]&&p[j]<=n/i;j++)
            e[p[j]*i]=j;
    }
    int a,b,len,ans;
    while(q--){
        scanf("%d %d",&a,&b);
        len=ans=b-a+1;
        while(len>1){
            int prime=p[e[len]];
            if(gethash(a+ans/prime,b)==gethash(a,b-ans/prime))
                ans/=prime;
            len/=prime;
        }
        printf("%d\n",ans);
    }
    return 0;
}

[ONTAK2015] Tasowanie

双指针+二分+哈希。

code

#include<cstdio>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
typedef unsigned long long ull;
constexpr int N=2e5+10;
int n,m,a[N],b[N],len,p1,p2;
ull h1[N],h2[N],base[N];
inline ull gethash1(int l,int r){return h1[r]-h1[l-1]*base[r-l+1];}
inline ull gethash2(int l,int r){return h2[r]-h2[l-1]*base[r-l+1];}
inline bool check(int x){return gethash1(p1,p1+x-1)==gethash2(p2,p2+x-1);}
int main(){
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    read(m);
    for(int i=1;i<=m;i++) read(b[i]);
    if(n<m) for(int i=n+1;i<=m;i++) a[i]=1e3+1;
    if(n>m) for(int i=m+1;i<=n;i++) b[i]=1e3+1;
    base[0]=1;
    len=max(n,m);
    a[len+1]=b[len+1]=1e3+1;
    for(int i=1;i<=len;i++) base[i]=base[i-1]*13331;
    for(int i=1;i<=len;i++)
        h1[i]=h1[i-1]*13331+a[i];
    for(int i=1;i<=len;i++)
        h2[i]=h2[i-1]*13331+b[i];
    p1=1,p2=1;
    for(int i=1;i<=n+m;i++){
        if(a[p1]<b[p2]) printf("%d ",a[p1++]);
        else if(a[p1]>b[p2]) printf("%d ",b[p2++]);
        else{
            int l=1,r=min(len-p1+1,len-p2+1);
            while(l<=r){
                int mid=(l+r)>>1;
                if(check(mid)) l=mid+1;
                else r=mid-1;
            }
            if(a[p1+r]<b[p2+r]) printf("%d ",a[p1++]);
            else printf("%d ",b[p2++]);
        }
    }
    return 0;
}

KMP

[HNOI2008] GT考试

设 \(f_{i,j}\) 表示长串匹配前 \(i\) 个字符，短串匹配前 \(j\) 个字符的方案数。答案为： \[ans=\sum_{i=0}^{m-1} f_{n,i}\] 设 \(g_{i,j}\) 表示匹配到第 \(i\) 位时加入一个数字后匹配到第 \(j\) 位的方案数，可以用 KMP 求出。 \[f_{i,j}=\sum_{k=0}^{m-1}f_{i-1,k}\times g_{k,j}\] 注意到这是矩阵乘法的形式，矩阵快速幂 \(O(m^3\log n)\)。
在转化成矩阵的过程中，\(f_{i,j}\) 被转化为一个一行 \(m-1\) 列的矩阵。

code

#include<cstdio>
#include<cstring>
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
int n,m,mod,nxt[25],ans;
struct Matrix{
    int a[20][20];
    Matrix(){memset(a,0,sizeof(a));}
    Matrix operator*(const Matrix &x)const{
        Matrix res;
        for(int k=0;k<m;k++)
            for(int i=0;i<m;i++)
                for(int j=0;j<m;j++)
                    res.a[i][j]=(res.a[i][j]+a[i][k]*x.a[k][j]%mod)%mod;
        return res;
    }
}base,f,g;
Matrix qpow(Matrix a,int b){
    Matrix res=base;
    while(b){
        if(b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
char s[25];
int main(){
    read(n,m,mod);
    for(int i=0;i<m;i++) base.a[i][i]=1;
    scanf("%s",s+1);
    int j=0;
    for(int i=2;i<=m;i++){
        while(j&&s[j+1]!=s[i]) j=nxt[j];
        if(s[j+1]==s[i]) j++;
        nxt[i]=j;
    }
    for(int i=0;i<m;i++)
        for(char c='0';c<='9';c++){
            j=i;
            while(j&&s[j+1]!=c) j=nxt[j];
            if(s[j+1]==c) j++;
            g.a[i][j]=(g.a[i][j]+1)%mod;
        }
    f.a[0][0]=1;
    f=f*qpow(g,n);
    for(int i=0;i<m;i++) ans=(ans+f.a[0][i])%mod;
    printf("%d\n",ans);
    return 0;
}

Manacher

感觉自己没理解 Manacher 啊，改天重学一次。 ### [国家集训队] 拉拉队排练 由于只需要找长度为奇数的回文串，无需在字符间插入 #，直接跑 Manacher，开差分数组 \(sum\)，表示当前长度的回文串数量。当位置 \(i\) 的最长回文半径为 \(p_i\) 时，容易想到半径长度小于等于 \(p_i\) 的都是回文串，则我们只需在差分数组 \(sum_1\) 处加 \(1\)，\(sum_{p_i\times 2}\) 处减 \(1\) 就行了。最后统计答案时要用快速幂。

code

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
constexpr int N=1e6+10,mod=19930726;
int qpow(ll a,int b){
    a%=mod;
    int res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int n,p[N];
ll k,sum[N],ans;
char s[N];
int main(){
    scanf("%d %lld",&n,&k);
    scanf("%s",s+1);
    s[0]='#';
    for(int i=1,r=0,mid=0;i<=n;i++){
        if(i<=r) p[i]=min(p[mid*2-i],r-i+1);
        while(s[i-p[i]]==s[i+p[i]]) ++p[i];
        if(p[i]+i>r) r=p[i]+i-1,mid=i;
        ++sum[1],--sum[p[i]*2];
    }
    for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
    int tot=n;
    ans=1;
    if(tot%2==0) --tot;
    while(k&&tot>0){
        ans=ans*qpow(tot,min(sum[tot],k))%mod;
        k=max(k-sum[tot],0ll);
        tot-=2;
    }
    if(k) printf("-1\n");
    else printf("%lld\n",ans);
    return 0;
}

[国家集训队] 最长双回文串

在跑 Manacher 同时维护以每个点开头和结尾的最长回文串长度。仅 Manacher 求解的答案不完全，需要再递推地扫一遍，最后枚举中点即可。

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
constexpr int N=1e5+10;
char t[N],s[N<<1];
int len0,len,p[N<<1],a[N<<1],b[N<<1],ans;
int main(){
    scanf("%s",t+1);
    len0=strlen(t+1);
    s[0]=s[1]='#';
    len=1;
    for(int i=1;i<=len0;i++){
        s[++len]=t[i];
        s[++len]='#';
    }
    for(int i=1,r=0,mid=0;i<=len;i++){
        int j=2*mid-i;
        if(i<=r) p[i]=min(r-i+1,p[j]);
        else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]]) ++p[i];
        if(i+p[i]-1>r){
            r=i+p[i]-1;
            mid=i;
        }
        a[i+p[i]-1]=max(a[i+p[i]-1],p[i]-1);
        b[i-p[i]+1]=max(b[i-p[i]+1],p[i]-1);
    }
    for(int i=len;i>=1;i-=2) a[i]=max(a[i],a[i+2]-2);
    for(int i=1;i<=len;i+=2) b[i]=max(b[i],b[i-2]-2);
    for(int i=1;i<=len;i+=2)
        if(a[i]&&b[i]) ans=max(ans,a[i]+b[i]);
    printf("%d\n",ans);
    return 0;
}

Day4

搜索

搜索题真是无聊死了，就少放几道吧…… ### [CSP-S 2022] 假期计划 \(n\) 遍 BFS 求全源最短路，之后考虑枚举。将 \(5\) 个点记作 \(1,2,3,4,5\)，则枚举 \(3,4\) 点，判断 \(2,5\) 是否与已选的点重复。可以预处理出每个能同时到达 \(1\) 点和另一个点的前三大点，因为它最多只有可能与 \(3,4\) 中的一个和 \(2,5\) 中的一个重合。总体时间复杂度 \(O(nm+n^2)\)。

code

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<set>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
typedef long long ll;
constexpr int N=2510;
int n,m,k,dis[N][N];
ll ans,val[N];
vector<int> e[N];
queue<int> q;
struct node{
    int id;
    node(int id):id(id){}
    bool operator<(const node &x)const{
        return val[id]!=val[x.id]?val[id]<val[x.id]:id<x.id;
    }
};
set<node> st[N];
int main(){
    read(n,m,k);++k;
    for(int i=2;i<=n;i++) read(val[i]);
    for(int i=1,u,v;i<=m;i++){
        read(u,v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=n;i++){
        dis[i][i]=0;
        q.push(i);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int v:e[u])
                if(dis[i][u]+1<dis[i][v]&&dis[i][u]+1<=k){
                    dis[i][v]=dis[i][u]+1;
                    q.push(v);
                }
        }
    }
    for(int i=2;i<=n;i++)
        for(int j=2;j<=n;j++){
            if(i==j) continue;
            if(dis[i][j]<=k&&dis[1][j]<=k)
                st[i].insert(node(j));
            if(st[i].size()>3) st[i].erase(st[i].begin());
        }
    for(int b=2;b<=n;b++)
        for(int c=2;c<=n;c++){
            if(b==c||dis[b][c]>k) continue;
            for(auto temp1:st[b]){
                int a=temp1.id;
                if(a==b||a==c) continue;
                for(auto temp2:st[c]){
                    int d=temp2.id;
                    if(d==b||d==c||a==d) continue;
                    ans=max(ans,val[a]+val[b]+val[c]+val[d]);
                }
            }
        }
    printf("%lld\n",ans);
    return 0;
}

[AHOI2012] 铁盘整理

IDA* 板题。先离散化，估价函数为相邻差不为 \(1\) 的个数。

code

#include<cstdio>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=18;
int n,a[N],b[N],lim;
inline int h(){
    int res=0;
    for(int i=1;i<=n;i++) res+=(abs(a[i+1]-a[i])!=1);
    return res;
}
bool dfs(int cnt,int pre){
    int temp=h();
    if(temp==0) return 1;
    if(cnt+temp>lim) return 0;
    bool f=0;
    for(int i=1;i<=n;i++){
        if(i==pre) continue;
        reverse(a+1,a+1+i);
        f|=dfs(cnt+1,i);
        reverse(a+1,a+1+i);
    }
    return f;
}
int main(){
    read(n);
    for(int i=1;i<=n;i++) read(a[i]),b[i]=a[i];
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+n,a[i])-b;
    a[n+1]=n+1;
    lim=1;
    while(1){
        if(dfs(0,0)){
            printf("%d\n",lim);
            break;
        }
        ++lim;
    }
    return 0;
}

Prime Gift

容易发现，\(p_i\) 越小，方案数越多。\(n=16\) 时不可接受，考虑 Meet in the middle。最坏情况下前 \(8\) 个质数 \(2,3,5,7,11,13,17,19\)，在 \(10^{18}\) 内能组成 \(7039193\) 种数字。实际实现时可以将数的分配得更加均匀以降低复杂度。之后二分答案+双指针求解即可。

code

#include<cstdio>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
typedef long long ll;
constexpr ll lim=1e18,N=7039192+10;
int n,p[20],k,tota,totb;
ll a[N],b[N];
void dfs1(int x,ll num){
    if(x>n) return;
    dfs1(x+2,num);
    for(ll i=p[x];;i*=p[x]){
        if(lim/i<num) break;
        a[++tota]=num*i;
        dfs1(x+2,num*i);
    }
}
void dfs2(int x,ll num){
    if(x>n) return;
    dfs2(x+2,num);
    for(ll i=p[x];;i*=p[x]){
        if(lim/i<num) break;
        b[++totb]=num*i;
        dfs2(x+2,num*i);
    }
}
inline bool check(ll x){
    ll cnt=0;
    for(int i=1,j=totb;i<=tota;i++){
        while(j&&x/a[i]<b[j]) --j;
        cnt+=j;
        if(j==0) break;
    }
    return cnt<k;
}
int main(){
    read(n);
    for(int i=1;i<=n;i++) read(p[i]);
    sort(p+1,p+1+n);
    a[++tota]=b[++totb]=1;
    dfs1(1,1);
    dfs2(2,1);
    sort(a+1,a+1+tota);
    sort(b+1,b+1+totb);
    read(k);
    ll l=1,r=1e18;
    while(l<=r){
        ll mid=(l+r)>>1;
        if(check(mid)) l=mid+1;
        else r=mid-1;
    }
    printf("%lld\n",l);
    return 0;
}

[USACO09NOV] Lights G

Meet in the middle，开一个 std::map 记录状态对应的最小操作次数，按照补集相加。

code

#include<cstdio>
#include<map>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
typedef long long ll;
constexpr int N=40;
int n,m,ans;
ll a[N];
map<ll,int> mp;
int main(){
    read(n,m);
    for(int i=0;i<n;i++) a[i]=1ll<<i;
    for(int i=1,u,v;i<=m;i++){
        read(u,v);
        --u,--v;
        a[u]|=1ll<<v;
        a[v]|=1ll<<u;
    }
    ans=n+1;
    for(int i=0;i<(1<<(n>>1));i++){
        ll temp=0;
        for(int j=0;j<(n>>1);j++)
            if((i>>j)&1)
                temp^=a[j];
        if(!mp.count(temp)) mp[temp]=__builtin_popcount(i);
        else mp[temp]=min(mp[temp],__builtin_popcount(i));
    }
    for(int i=0;i<(1<<(n-(n>>1)));i++){
        ll temp=0;
        for(int j=0;j<n-(n>>1);j++)
            if((i>>j)&1)
                temp^=a[(n>>1)+j];
        if(mp.count(((1ll<<n)-1)^temp))
            ans=min(ans,__builtin_popcount(i)+mp[((1ll<<n)-1)^temp]);
    }
    printf("%d\n",ans);
    return 0;
}

机关

坏题。
考虑 A*。容易想到 \(4\) 进制状压，则状态 \(x\) 的估价 \(h(x)\) 应为当前已经旋转的次数与所有不为 \(1\) 的旋钮旋到 \(1\) 所需总步数除以 \(2\) 的和。因为最好情况是旋一个按钮时另一个正好也到了 \(1\)。每个状态记录一个 \(pre\) 表示是从哪个状态转移过来的以输出方案。

code

#include<cstdio>
#include<queue>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=(1<<24)+10;
int st,a[15][4],b[N],pre[N],step[N];
bool vis[N];
void write(int x){
    if(x==st) return;
    write(pre[x]);
    printf("%d ",b[x]);
}
inline int h(int x){
    int res=0;
    for(int i=0;i<12;i++){
        int temp=(x>>(i<<1))&3;
        res+=temp?4-temp:0;
    }
    return res>>1;
}
struct node{
    int x,h;
    node(int x,int h):x(x),h(h){}
    bool operator<(const node &a)const{return h>a.h;}
};
priority_queue<node> q;
int main(){
    for(int i=0,x;i<12;i++){
        read(x);
        st|=(x-1)<<(i<<1);
        for(int j=0;j<4;j++)
            read(a[i][j]),--a[i][j];
    }
    q.push(node(st,h(st)));
    vis[st]=1;
    while(!q.empty()){
        int x=q.top().x;
        q.pop();
        if(x==0) break;
        for(int i=0;i<12;i++){
            int pos1=i<<1,temp1=(x>>pos1)&3,j=a[i][temp1];
            int pos2=j<<1,temp2=(x>>pos2)&3,res=x;
            res&=~(3<<pos1);
            res&=~(3<<pos2);
            res|=((temp1+1)&3)<<pos1;
            res|=((temp2+1)&3)<<pos2;
            if(!vis[res]){
                vis[res]=1;
                step[res]=step[x]+1;
                pre[res]=x,b[res]=i+1;
                q.push(node(res,step[res]+h(res)));
            }
        }
    }
    printf("%d\n",step[0]);
    write(0);
    return 0;
}

Day5

最小生成树

[NOIP 2013 提高组] 货车运输

最优情况一定是走最大生成树上的边，所以先 Kruskal 求最大生成树，接下来求树上两点间路径权值最小值，可以边权下放点权上树剖+线段树或倍增。另外，图不保证连通，实际上要对森林做操作。

code

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=1e4+10,M=5e4+10;
int n,m,q,boss[N],cnt;
int find(int x){return boss[x]==x?x:boss[x]=find(boss[x]);}
struct Edge{
    int u,v,w;
    bool operator<(const Edge &x)const{return w>x.w;}
}edge[M];
struct Edge1{int v,w;};
vector<Edge1> e[N];
void kruskal(){
    for(int i=1;i<=n;i++) boss[i]=i;
    sort(edge+1,edge+1+m);
    for(int i=1;i<=m&&cnt<n-1;i++){
        int u=find(edge[i].u),v=find(edge[i].v);
        if(u==v) continue;
        boss[u]=v;
        ++cnt;
        u=edge[i].u,v=edge[i].v;
        int w=edge[i].w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
}
int dfn[N],dfncnt,son[N],fa[N],siz[N],top[N],dep[N],w[N],P,tree[N<<2];
void dfs1(int u,int f){
    siz[u]=1;
    fa[u]=f;
    dep[u]=dep[f]+1;
    for(auto t:e[u]){
        int v=t.v;
        if(v==f) continue;
        w[v]=t.w;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])
            son[u]=v;
    }
}
void dfs2(int u,int topf){
    top[u]=topf;
    dfn[u]=++dfncnt;
    if(son[u]) dfs2(son[u],topf);
    for(auto t:e[u]){
        int v=t.v;
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
void build(){
    for(int i=1;i<=n;i++)
        if(!siz[i]) w[i]=2e9,dfs1(i,0);
    for(int i=1;i<=n;i++)
        if(!dfn[i]) dfs2(i,i);
    P=1;
    while(P<=n+1) P<<=1;
    memset(tree,0x3f,sizeof(tree));
    for(int i=1;i<=n;i++)
        tree[P+dfn[i]]=w[i];
    for(int i=P-1;i;i--)
        tree[i]=min(tree[ls(i)],tree[rs(i)]);
}
int query(int l,int r){
    l+=P-1,r+=P+1;
    int res=2e9;
    while(l^1^r){
        if(~l&1) res=min(tree[l^1],res);
        if(r&1) res=min(tree[r^1],res);
        l>>=1,r>>=1;
    }
    return res;
}
int ask(int x,int y){
    if(find(x)!=find(y)) return -1;
    int res=2e9;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        res=min(res,query(dfn[top[x]],dfn[x]));
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    if(x!=y) res=min(res,query(dfn[x]+1,dfn[y]));
    return res;
}
int main(){
    read(n,m);
    for(int i=1,u,v,w;i<=m;i++){
        read(u,v,w);
        edge[i]={u,v,w};
    }
    kruskal();
    build();
    read(q);
    int x,y;
    while(q--){
        read(x,y);
        printf("%d\n",ask(x,y));
    }
    return 0;
}

[BJWC2010] 严格次小生成树

跟上一道题一个套路。考虑枚举替换边的过程，首先加一条边形成环，再从环上删去最大的一条小于加入边边权的边。线段树维护区间最大值和区间严格次大值即可。

code

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
typedef long long ll;
constexpr int N=1e5+10,M=3e5+10;
int n,m,boss[N],cnt;
struct node{
    int maxn,se;
    node(int maxn=-1,int se=-1):maxn(maxn),se(se){}
    node operator+(const node &x)const{
        node res;
        res.maxn=max(maxn,x.maxn);
        res.se=max(se,x.se);
        if(maxn!=x.maxn)
            res.se=max(res.se,min(maxn,x.maxn));
        return res;
    }
};
int P;
node tree[N<<2];
node query(int l,int r){
    l+=P-1,r+=P+1;
    node res;
    while(l^1^r){
        if(~l&1) res=res+tree[l^1];
        if(r&1) res=res+tree[r^1];
        l>>=1,r>>=1;
    }
    return res;
}
struct Edge{
    int u,v,w;
    bool operator<(const Edge &x)const{return w<x.w;}
}edge[M];
struct Edge1{int v,w;};
vector<Edge1> e[N];
ll ans,minval;
int dfn[N],top[N],dfncnt,dep[N],fa[N],siz[N],son[N],w[N];
bool vis[N];
int find(int x){return boss[x]==x?x:boss[x]=find(boss[x]);}
void dfs1(int u,int f){
    dep[u]=dep[f]+1;
    fa[u]=f;
    siz[u]=1;
    for(auto t:e[u]){
        int v=t.v;
        if(v==f) continue;
        w[v]=t.w;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])
            son[u]=v;
    }
}
void dfs2(int u,int topf){
    top[u]=topf;
    dfn[u]=++dfncnt;
    if(son[u]) dfs2(son[u],topf);
    for(auto t:e[u]){
        int v=t.v;
        if(v==fa[u]||v==son[u])
            continue;
        dfs2(v,v);
    }
}
node ask(int x,int y){
    node res;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        res=res+query(dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    if(x!=y) res=res+query(dfn[x]+1,dfn[y]);
    return res;
}
int main(){
    read(n,m);
    for(int i=1,u,v,w;i<=m;i++){
        read(u,v,w);
        edge[i]={u,v,w};
    }
    sort(edge+1,edge+1+m);
    for(int i=1;i<=n;i++) boss[i]=i;
    for(int i=1;i<=m&&cnt<n-1;i++){
        int u=find(edge[i].u),v=find(edge[i].v);
        if(u==v) continue;
        boss[u]=v;
        vis[i]=1;
        u=edge[i].u,v=edge[i].v;
        int w=edge[i].w;
        minval+=w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
        if(++cnt==n-1) break;
    }
    dfs1(1,0);
    dfs2(1,1);
    P=1;
    while(P<=n+1) P<<=1;
    for(int i=1;i<=n;i++)
        tree[P+dfn[i]]=w[i];
    for(int i=P-1;i;i--)
        tree[i]=tree[i<<1]+tree[i<<1|1];
    ans=1e18;
    for(int i=1;i<=m;i++){
        if(vis[i]) continue;
        int x=edge[i].u,y=edge[i].v,w=edge[i].w;
        if(x==y) continue;
        node temp=ask(x,y);
        if(temp.maxn==w)
            ans=min(ans,minval-temp.se+w);
        else ans=min(ans,minval-temp.maxn+w);
    }
    printf("%lld\n",ans);
    return 0;
}

Peaks

Kruskal 重构树的在线做法还是太吃操作了，我们直接离线。容易想到将边权和询问的 \(x\) 升序排序后动态加边，查询第 \(k\) 大直接线段树上二分，加边用并查集+线段树合并维护。

code

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=1e5+10,M=5e5+10;
int n,m,q,h[N],b[N],len,tot,root[N],fa[N],now,ans[M];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
struct edge{
    int u,v,w;
    bool operator<(const edge &x)const{return w<x.w;}
}e[M];
struct Query{
    int v,x,k,id;
    bool operator<(const Query &a)const{return x<a.x;}
}qu[M];
struct Tree{
    int ls,rs,sum;
}tree[N<<5];
inline void push_up(int u){
    tree[u].sum=tree[tree[u].ls].sum+tree[tree[u].rs].sum;
}
void modify(int &u,int l,int r,int x){
    if(!u) u=++tot;
    if(l==r){
        ++tree[u].sum;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) modify(tree[u].ls,l,mid,x);
    else modify(tree[u].rs,mid+1,r,x);
    push_up(u);
}
int merge(int a,int b,int l,int r){
    if(!a||!b) return a|b;
    if(l==r){
        tree[a].sum+=tree[b].sum;
        return a;
    }
    int mid=(l+r)>>1;
    tree[a].ls=merge(tree[a].ls,tree[b].ls,l,mid);
    tree[a].rs=merge(tree[a].rs,tree[b].rs,mid+1,r);
    push_up(a);
    return a;
}
int query(int u,int l,int r,int k){
    if(l==r) return l;
    int mid=(l+r)>>1;
    if(k<=tree[tree[u].ls].sum)
        return query(tree[u].ls,l,mid,k);
    else
        return query(tree[u].rs,mid+1,r,k-tree[tree[u].ls].sum);
}
int main(){
    read(n,m,q);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=n;i++){
        read(h[i]);
        b[i]=h[i];
    }
    sort(b+1,b+1+n);
    len=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++){
        int x=lower_bound(b+1,b+1+len,h[i])-b;
        modify(root[i],1,len,x);
    }
    for(int i=1,u,v,w;i<=m;i++){
        read(u,v,w);
        e[i]={u,v,w};
    }
    sort(e+1,e+1+m);
    for(int i=1,v,x,k;i<=q;i++){
        read(v,x,k);
        qu[i]={v,x,k,i};
    }
    sort(qu+1,qu+1+q);
    for(int i=1;i<=q;i++){
        int x=qu[i].x,k=qu[i].k,id=qu[i].id;
        while(e[now+1].w<=x&&now<m){
            ++now;
            int u=find(e[now].u),v=find(e[now].v);
            if(u==v) continue;
            fa[u]=v;
            root[v]=merge(root[v],root[u],1,len);
        }
        int v=find(qu[i].v);
        if(tree[root[v]].sum<k) ans[id]=-1;
        else ans[id]=b[query(root[v],1,len,tree[root[v]].sum-k+1)];
    }
    for(int i=1;i<=q;i++)
        printf("%d\n",ans[i]);
    return 0;
}

最短路

没做。 ## 拓扑排序 ### [ZJOI2007] 最大半连通子图 容易发现，半连通子图就是若干相连的强连通分量，则找最大半连通子图转化为缩点后在 DAG 上找最长链+计数。注意去重。

code

#include<cstdio>
#include<stack>
#include<vector>
#include<set>
#include<queue>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=1e5+10,M=1e6+10;
int n,m,mod,head[N],tot_edge;
struct edge{int to,nxt;}e1[M];
inline void add_edge(int u,int v){
    e1[++tot_edge].to=v;
    e1[tot_edge].nxt=head[u];
    head[u]=tot_edge;
}
stack<int> st;
bool instack[N];
int dfn[N],low[N],dfncnt,scccnt,scc[N],w[N];
void tarjan(int u){
    dfn[u]=low[u]=++dfncnt;
    instack[u]=1;
    st.push(u);
    for(int i=head[u];i;i=e1[i].nxt){
        int v=e1[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        ++scccnt;
        while(1){
            int v=st.top();
            st.pop();
            instack[v]=0;
            scc[v]=scccnt;
            ++w[scccnt];
            if(u==v) break;
        }
    }
}
vector<int> e2[N];
int indegree[N],dp[N],dis[N],ans1,ans2;
set<pair<int,int>> p;
queue<int> q;
int main(){
    read(n,m,mod);
    for(int i=1,u,v;i<=m;i++){
        read(u,v);
        add_edge(u,v);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    for(int u=1;u<=n;u++)
        for(int i=head[u];i;i=e1[i].nxt){
            int v=e1[i].to;
            if(scc[u]==scc[v]) continue;
            if(p.find(make_pair(scc[u],scc[v]))!=p.end())
                continue;
            p.insert(make_pair(scc[u],scc[v]));
            e2[scc[u]].push_back(scc[v]);
            ++indegree[scc[v]];
        }
    for(int i=1;i<=scccnt;i++)
        if(!indegree[i]){
            q.push(i);
            dis[i]=w[i];
            dp[i]=1;
        }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int v:e2[u]){
            if(dis[v]<dis[u]+w[v]){
                dis[v]=dis[u]+w[v];
                dp[v]=dp[u];
            }
            else if(dis[v]==dis[u]+w[v])
                dp[v]=(dp[u]+dp[v])%mod;
            if(!--indegree[v]) q.push(v);
        }
    }
    for(int i=1;i<=scccnt;i++) ans1=max(ans1,dis[i]);
    for(int i=1;i<=scccnt;i++)
        if(dis[i]==ans1) ans2=(ans2+dp[i])%mod;
    printf("%d\n%d\n",ans1,ans2);
    return 0;
}

Day6

二分图

Machine Schedule

连接每个 \(a_i\) 和 \(b_i\)，问题变为了二分图上找最小点覆盖。直接跑二分图最大匹配即可。
Kőnig 定理：二分图中，最小点覆盖中的顶点数量等于最大匹配中的边数量。

code

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=1010;
int n,m,k,ans,match[N];
bool vis[N];
vector<int> e[N];
bool dfs(int u){
    for(int v:e[u])
        if(!vis[v]){
            vis[v]=1;
            if(!match[v]||dfs(match[v])){
                match[v]=u;
                return 1;
            }
        }
    return 0;
}
int main(){
    while(1){
        for(int i=1;i<=n;i++) e[i].clear();
        memset(match,0,sizeof(int)*(n+10));
        read(n);
        if(!n) return 0;
        read(m,k);
        for(int i=1,u,v,a;i<=k;i++){
            read(a,u,v);
            e[u].push_back(v);
        }
        ans=0;
        for(int i=1;i<=n;i++){
            memset(vis,0,sizeof(bool)*(n+10));
            if(dfs(i)) ++ans;
        }
        printf("%d\n",ans);
    }
    return 0;
}

[USACO05JAN] Muddy Fields G

贪心地考虑，极长地放木板一定优。将所有横着的和竖着的木板编号，相交的连边，之后二分图最大匹配。

code

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
constexpr int N=55;
int r,c,tota,totb,a[N][N],b[N][N],match[N*N],ans;
char mp[N][N];
bool vis[N*N];
vector<int> e[N*N];
bool dfs(int u){
    for(int v:e[u])
        if(!vis[v]){
            vis[v]=1;
            if(!match[v]||dfs(match[v])){
                match[v]=u;
                return 1;
            }
        }
    return 0;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>r>>c;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++){
            cin>>mp[i][j];
            if(mp[i][j]=='*'){
                if(mp[i][j-1]=='*')
                    a[i][j]=a[i][j-1];
                else a[i][j]=++tota;
                if(mp[i-1][j]=='*')
                    b[i][j]=b[i-1][j];
                else b[i][j]=++totb;
                if(a[i][j]&&b[i][j])
                    e[a[i][j]].push_back(b[i][j]);
            }
        }
    for(int i=1;i<=tota;i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i)) ++ans;
    }
    cout<<ans<<'\n';
    return 0;
}

Guardian of Decency

最大独立集与最小点覆盖之和为顶点数目，这个推论适用于一般图。

code

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
constexpr int N=510;
int t,n,match[N],ans,cnta,cntb;
bool vis[N];
struct student{
    int h;
    char sex;
    string music,sport;
}a[N],b[N];
vector<int> e[N];
bool dfs(int u){
    for(int v:e[u])
        if(!vis[v]){
            vis[v]=1;
            if(!match[v]||dfs(match[v])){
                match[v]=u;
                return 1;
            }
        }
    return 0;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        for(int i=1;i<=n;i++) e[i].clear();
        memset(match,0,sizeof(int)*(n+10));
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i].h>>a[i].sex>>a[i].music>>a[i].sport;
            for(int j=1;j<i;j++){
                if(abs(a[i].h-a[j].h)>40||a[i].sex==a[j].sex||
                    a[i].music!=a[j].music||a[i].sport==a[j].sport)
                    continue;
                if(a[i].sex=='M') e[i].push_back(j);
                else e[j].push_back(i);
            }
        }
        ans=0;
        for(int i=1;i<=n;i++){
            memset(vis,0,sizeof(bool)*(n+10));
            if(dfs(i)) ++ans;
        }
        printf("%d\n",n-ans);
    }
    return 0;
}

欧拉路径

没做。 ## 连通分量 没做。

参考资料：
https://oi-wiki.org/graph/graph-matching/bigraph-match/