XCPC Notes

Appearance

发布时间：2025-04-24

A ​

签到模拟题

M ​

签到

F. Make Max ​

在这里插入图片描述

  • 每次可以选择一段区间，必须包含不同的数，然后修改区间所有数为当前区间最大值
  • 考虑每个数作为最大值的区间范围，可以贪心地修改
  • 因此直接建出笛卡尔树模拟贪心即可
  • 复杂度O(n)O(n)
cpp
int stk[N],top,cur,n,a[N],ls[N],rs[N];
int dfs(int u,int l,int r){
    if(l==r)return 0;
    int ans=0;
    if(ls[u])ans+=dfs(ls[u],l,u-1);
    if(rs[u])ans+=dfs(rs[u],u+1,r);
    if(ls[u]&&a[ls[u]]!=a[u])ans+=u-l;
    if(rs[u]&&a[rs[u]]!=a[u])ans+=r-u;
    return ans;
}
void solve(){ 
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],ls[i]=rs[i]=0;
    top=0;
    for(int i=1;i<=n;i++){
        cur=top;
        while(cur&&a[stk[cur]]<a[i])cur--;
        if(cur)rs[stk[cur]]=i;
        if(cur<top)ls[i]=stk[cur+1];
        stk[++cur]=i;
        top=cur;
    }
    cout<<dfs(stk[1],1,n)<<"\n";
}

G. The Median of the Median of the Median ​

题意：

在这里插入图片描述

  • 看到中位数，想到二分
  • 则在check函数里面，所有数都变成0或1，用前缀和判断即可
  • 复杂度O(n2log⁡V)O(n^2 \log V)
cpp
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define F first
#define S second
#define TR tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
typedef pair<int,int> PII;
const int N=2e5+10,M=2e5+10;
const int INF=1e18;
const int mod=998244353;
// const int mod=1e9+7;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve(){ 
    int n;
    cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    vector s(n+1,vector<int>(n+1)),s2(n+1,vector<int>(n+1));
    vector b(n+1,vector<int>(n+1));
    vector<int> A(n+1);
    auto check=[&](int mid){
        for(int i=1;i<=n;i++)A[i]=a[i]>=mid;
        for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)b[i][j]=0;
        for(int i=1;i<=n;i++){
            int c=0;
            for(int j=i;j<=n;j++){
                c+=A[j];
                if(c>=(j-i+1)/2+1)b[i][j]=1;
            }
        }
        int c=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+b[i][j];
                s2[i][j]=s2[i][j-1]+s2[i-1][j]-s2[i-1][j-1]+(i<=j);
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=i;j<=n;j++){
                int all=s2[j][j]-s2[i-1][j]-s2[j][i-1]+s2[i-1][i-1];
                if(s[j][j]-s[i-1][j]-s[j][i-1]+s[i-1][i-1]>=all/2+1)c++;
            }
        }
        return c>=(n*(n+1)/2)/2+1;
    };
    int l=1,r=1e9;
    while(l<r){
        int mid=l+r+1>>1;
        if(check(mid))l=mid;
        else r=mid-1;
    }
    cout<<l<<"\n";
}   
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

C. Permutation Counting 4 ​

在这里插入图片描述

从线性代数的角度出发，第ii行[li,ri][l_i,r_i]为11，其余为00

回顾线代的知识

永久式：per(A)=∑σ∈Sn∏i=1nAi,σ(i)\text{per}(A) = \sum_{\sigma \in S_n} \prod_{i=1}^n A_{i, \sigma(i)} 行列式：det(A)=∑σ∈Snsgn(σ)∏i=1nAi,σ(i)\text{det}(A) = \sum_{\sigma \in S_n} \text{sgn}(\sigma)\prod_{i=1}^n A_{i, \sigma(i)}，sgn(σ)=(−1)Nσ\text{sgn}(\sigma)=(-1)^{N_{\sigma}},NσN_{\sigma}是排列的逆序数

比如矩阵$$ \begin{bmatrix} a & b\ c & d \end

永久式为$ad+bc$,行列式为$ad-bc$ 由题意可知，方案数即矩阵的永久式的值 由于$\text{per}(A) \equiv \text{det}(A) \mod 2$，因此转化为求矩阵行列式的奇偶性 考虑高斯消元求解行列式的过程，转化成上三角后，如果主对角线全1则为1，否则为0，但是高斯消元为$n^3$ 由于只有0，1的特殊性，我们可以考虑加速这个过程 枚举行从$1-n$，那么考虑第$i$行，必须找到一行1的最前列是$i$，如果没有说明当前主对角线上的数为$0$，乘积为$0$ 否则，对应于原题目即左端点为$i$的区间集合，对于每个这样的集合我们选取长度最小的那一行，然后执行操作 假设此时的区间为$[i,r]$，那么对于后面的所有$[i,R],r \lt R$,都会被截断成$[r+1,R]$ 因此我们可以set加启发式合并模拟这个过程即可 特判掉相同区间，因为区间相同，那么高斯消元后肯定会使一行全为0，此时主对角线乘积必为0 复杂度$O(n \log^2)$ ```cpp void solve() { int n; cin>>n; set<int> seg[n+1]; bool ok=true; for(int i=1;i<=n;i++){ int l,r; cin>>l>>r; if(seg[l].find(r)!=seg[l].end())ok=false; seg[l].insert(r); } if(!ok){ cout<<"0\n"; return; } for(int i=1;i<=n;i++){ if(seg[i].empty()){ cout<<"0\n"; return; } auto it=seg[i].begin(); int v=*it; seg[i].erase(it); if(v==n)continue; if(seg[v+1].size()<seg[i].size())swap(seg[v+1],seg[i]); for(auto &r:seg[i]){ if(seg[v+1].find(r)!=seg[v+1].end()){ cout<<"0\n"; return; } seg[v+1].insert(r); } } cout<<"1\n"; } ``` 题解做法： 最左边补一列，最上边补一行，左上角置1，然后从最后一列往前，每一列减去后一列，此时不改变行列式的值，相当于每一行差分，那么矩阵变为只有$-1$和$1$ 发现如果$[l_i-1,r_i]$连边，成环的话，行列式必为0，因此判环即可 # Rainbow Bracket Sequence ![在这里插入图片描述](/assets/img/remote/fc415bb216.png) 我们考虑合法括号序的trick: * 前$2i-1$必须有$i$个左括号 * 即对于第$i$个位置而言，需要$\lceil \frac{i}{2} \rceil$个左括号 还有一个条件左括号的颜色数大于等于$l_i$ 因为$n$很小，考虑上下界费用流如何建图，定义一单位的流为左括号数量 分为两类点：颜色点，位置点 *$(下界，上界，费用)$ * 源点$S$向每种颜色$i$建边$(l_i,\infty,0)$ * 颜色$c_i$向对应的下标$i$建边$(0,1,v_i)$ * 下标$i$向$i+1$建边$(\lceil \frac{i}{2} \rceil,\infty,0)$ * 下标$2n+1$向汇点$T$建边$(n,n,0)$ 点数$n+m=1000$,边数$3000$左右，上界$3e9$左右 套板子即可，只跑了18ms ```cpp #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define int long long #define F first #define S second #define TR tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> typedef pair<int,int> PII; const int N=3e4+10,M=3e4+10; const int INF=1e18; const int mod=998244353; // const int mod=1e9+7; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); int h[N],e[M],f[M],w[M],ne[M],Low[M],idx; int dis[N],cur[N];//d表示最短距离,cur为当前弧 int n,m,S,T; bool vis[N]; int height[N];// 势能函数 vector<int> dot;// 点数 void add(int a,int b,int c,int d,int val){ e[idx]=b,f[idx]=d-c,w[idx]=val,Low[idx]=c,ne[idx]=h[a],h[a]=idx++; e[idx]=a,f[idx]=0,w[idx]=-val,ne[idx]=h[b],h[b]=idx++; } bool dijk(){ for(auto &i:dot)dis[i]=INF,cur[i]=h[i]; priority_queue<PII,vector<PII>,greater<>> pq; dis[S]=0; pq.emplace(0,S); while(!pq.empty()){ auto [d,u]=pq.top(); pq.pop(); if(dis[u]!=d)continue; for(int i=h[u];~i;i=ne[i]){ int v=e[i]; if(f[i]&&dis[v]>d+height[u]-height[v]+w[i]){ dis[v]=d+height[u]-height[v]+w[i]; pq.emplace(dis[v],v); } } } return dis[T]!=INF; } int find(int u,int limit){ if(!limit||u==T)return limit; int flow=0; vis[u]=1; for(int &i=cur[u];~i&&flow<limit;i=ne[i]){ int v=e[i]; if(dis[v]==dis[u]+height[u]-height[v]+w[i]&&f[i]&&!vis[v]){ int t=find(v,min(f[i],limit-flow)); f[i]-=t,f[i^1]+=t,flow+=t; if(flow==limit)break; } } vis[u]=0; return flow; } void mcmf(int &flow,int &cost){ flow=cost=0; int r; for(auto &i:dot)height[i]=0; while(dijk()){ int r=find(S,INF); flow+=r; for(auto &i:dot)height[i]+=dis[i]; cost+=height[T]*r; } } void clear(){ for(auto &i:dot)h[i]=-1; dot.clear(); for(int i=0;i<idx;i++)e[i]=f[i]=w[i]=ne[i]=Low[i]=0; idx=0; } void solve() { clear(); cin>>n>>m; int s=0,t=m+2*n+2; S=m+2*n+3,T=m+2*n+4; vector<int> F(m+2*n+3);// 出入 for(int i=0;i<=m+2*n+4;i++)dot.push_back(i); for(int i=1;i<=m;i++){ int l; cin>>l; add(s,i,l,INF,0); F[s]-=l,F[i]+=l; } vector<int> c(2*n+1),v(2*n+1); for(int i=1;i<=2*n;i++)cin>>c[i]; for(int i=1;i<=2*n;i++)cin>>v[i]; for(int i=1;i<=2*n;i++){ add(c[i],i+m,0,1,-v[i]); add(i+m,i+m+1,(i+1)/2,INF,0); F[i+m]-=(i+1)/2,F[i+m+1]+=(i+1)/2; } add(m+2*n+1,t,n,n,0); F[m+2*n+1]-=n,F[t]+=n; int tot=0; for(int i=0;i<=m+2*n+2;i++){ if(F[i]>0)add(S,i,0,F[i],0),tot+=F[i]; else add(i,T,0,-F[i],0); } add(t,s,0,INF,0); int flow,cost; mcmf(flow,cost); // cout<<flow<<" "<<cost<<"\n"; if(flow!=tot){ cout<<"-1\n"; return; } int res=-cost; for(int i=0;i<idx;i+=2){ res+=Low[i]*w[i]; } cout<<res<<"\n"; } signed main(){ cin.tie(0)->sync_with_stdio(0); int T=1; memset(h,-1,sizeof h); cin>>T; while(T--)solve(); return 0; } ``` # L. Bull Farm ![在这里插入图片描述](/assets/img/remote/93ac8317dd.png) 有$n$个点，恰好有一个点没有奶牛，其他都有奶牛，还有$l$个按钮，第$i$个按钮按下后，可以控制点$j$处的奶牛移动到$t_{i,j}$位置，只有保证奶牛不能移动到同一个点才能去按按钮。还有$q$次询问，每次询问，初始没有奶牛的点在$a$处，最终想要让$b$点没有奶牛，并且仅使用前$c$个按钮，问能否实现，用0/1回答。 做法： 我们想象成空格的移动，题目转化为使用一些边是否能到达另一个点 观察每个操作的合法性，发现只有两种情况： * 操作是个排列，即每个数只出现一次 * 重复出现的数只有两个，位置记为$x,y$，设$[1,n]$没有出现的数为$z$，相当于$x \rightarrow z,y \rightarrow z$连边 * 对询问离线，那么现在的瓶颈在于维护可达性，这里参考[P10480 可达性统计](https://www.luogu.com.cn/problem/P10480)的方法，使用**bitset**维护 * 加边的复杂度是$\frac{n^2}{\omega}$的 * 那么对于第二种情况是很好做的，但是对于第一种情况要加$n$次边，太多了不好做 * 对于第一种情况加边加的都是双向边，因此我们可以维护一颗生成树，只加生成树的边，那么第一种情况最多只会加边$n-1$次 * 第二种情况显然最多加边$2l$次 * 因此复杂度为$O((l+n) \cdot \frac{n^2}{\omega})$ ```cpp struct DSU { std::vector<int> f, siz; DSU() {} DSU(int n) { init(n); } void init(int n) { f.resize(n); std::iota(f.begin(), f.end(), 0); siz.assign(n, 1); } int find(int x) { while (x != f[x]) { x = f[x] = f[f[x]]; } return x; } bool same(int x, int y) { return find(x) == find(y); } bool merge(int x, int y) { x = find(x); y = find(y); if (x == y) { return false; } siz[x] += siz[y]; f[y] = x; return true; } int size(int x) { return siz[find(x)]; } } dsu; void solve(){ int n,l,q; cin>>n>>l>>q; vector t(l+1,vector<int>(n+1)); for(int i=1;i<=l;i++){ string s; cin>>s; for(int j=0,k=1;j<s.size();j+=2,k++){ t[i][k]=(s[j]-'0')*50+(s[j+1]-'0'); } } vector<array<int,3>> que(q+1); for(int i=1;i<=q;i++){ string s; cin>>s; for(int j=0,k=0;j<s.size();j+=2,k++){ que[i][k]=(s[j]-'0')*50+(s[j+1]-'0'); } } // for(int i=1;i<=l;i++)for(int j=1;j<=n;j++)cout<<t[i][j]<<" \n"[j==n]; // for(int i=1;i<=q;i++)cout<<que[i][0]<<" "<<que[i][1]<<" "<<que[i][2]<<"\n"; vector<array<int,3>> Que[l+1]; vector<int> ans(q+1); for(int i=1;i<=q;i++){ if(que[i][2])Que[que[i][2]].push_back({que[i][0],que[i][1],i}); else{ ans[i]=que[i][0]==que[i][1]; } } bitset<N> f[n+1]; for(int i=1;i<=n;i++)f[i][i]=1; dsu.init(n+1); for(int i=1;i<=l;i++){ vector<int> same; vector<bool> vis(n+1); for(int j=1;j<=n;j++){ if(vis[t[i][j]])same.push_back(j); vis[t[i][j]]=1; } auto link=[&](int x,int y){ for(int j=1;j<=n;j++){ if(f[j][x])f[j]|=f[y]; } }; if(same.size()<=1){ if(same.size()==0){ for(int j=1;j<=n;j++){ int x=j,y=t[i][j]; if(dsu.merge(x,y)){ link(x,y); link(y,x); } } } else{ int z=t[i][same[0]]; int x=-1,y=-1; vector<bool> vis(n+1); for(int j=1;j<=n;j++){ if(t[i][j]==z){ if(x==-1)x=j; else y=j; } vis[t[i][j]]=1; } for(int j=1;j<=n;j++){ if(!vis[j]){ z=j; break; } } link(x,z),link(y,z); } } for(auto [x,y,id]:Que[i])ans[id]=f[x][y]; } for(int i=1;i<=q;i++)cout<<ans[i]; cout<<"\n"; } ``` 第二种在线解法： * 对于每条边我们记录它的权值为加入的时间，那么询问即是$a$到$b$最大权值最小的路径是否满足条件 * 对于每个点跑一遍dijk即可 * 复杂度$O(n(n+l)\log n)$

Wenwei Lin · 2022 — 2025