0912题解

~ 2025-9-12 18:15:21

养蛊神器

由操作可以发现答案能表示为ak1+ak2+⋯+akma_{k_1}+a_{k_2}+\dots+a_{k_m} ，并且充要条件是k1≡k2≡...≡km(mod  2)k_1 \equiv k_2 \equiv ... \equiv k_m (\mod 2)。

因此可分奇偶位讨论，剩下的数要么是选奇数位中全体非负数，要么是选偶数位中全体非负数。注意边界情况：如果全是负数，则至少选一个，选绝对值最小的。

确定了最后选哪些数剩下之后，只要把相邻数之间连续段删掉就好了，容易发现次数就是长度/2，头尾要特判一下。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6+5;
int n,a[N];
int Get(int x)
{
	if(x==0)return 0;
	else return x/2+1;
}
signed main()
{
	freopen("bug.in","r",stdin);
	freopen("bug.out","w",stdout);
	int flag = 0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]>0){
			flag = 1;
		}
	}
	if(!flag){
		int res = -1e15,res2=0;
		for(int i=1;i<=n;i++){
			if(a[i]>res){
				res = a[i];
				res2=Get(i-1)+Get(n-i);
			}
			else if(a[i]==res){
				res2 = min(res2,Get(i-1)+Get(n-i));
			}
		}
		cout<<res<<"\n"<<res2<<endl;
	}
	else{
		int sum = 0,L=n+1,R=0,res1=0,res2=0;
		for(int i=1;i<=n;i+=2){
			if(a[i]>0){
				sum+=a[i];
				L = min(L,i);
				R = max(R,i);
				if(sum>res1){
					res1 = sum;
					res2 = Get(L-1)+Get(n-R)+(R-L)/2;
				}
				else if(sum==res1){
					res2 = min(res2,Get(L-1)+Get(n-R)+(R-L)/2);
				}
			}
		}
		sum=0,L=n+1,R=0;
		for(int i=2;i<=n;i+=2){
			if(a[i]>0){
				sum+=a[i];
				L=min(L,i);
				R=max(R,i);
				if(sum>res1){
					res1 = sum;
					res2 = Get(L-1)+Get(n-R)+(R-L)/2;
				}
				else if(sum==res1){
					res2 = min(res2,Get(L-1)+Get(n-R)+(R-L)/2);
				}
			}
		}
		cout<<res1<<"\n"<<res2<<endl;
	}
	return 0;
}

导航神器

四联通看作双向边，传送门看做有向边，问题是问有向图上两点可到达性。

首先把每个四连通的连通块缩点。注意到有向边数量很少，所以在四连通连通块缩点之后的图上朴素搜索出每个连通块可到达的连通块集合即可。复杂度 O(n+k2)O(n+k^2)。可以通过本题。

如果有向边不做限制，则是经典问题：有向图可到达性首先强连通分量缩点（同一个强连通分量可达性相同），然后在得到的 DAG 上，用 bitset 维护连通关系即可。时间复杂度 O(nmw)O(\frac{nm}{w})。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int n,m,k,q,tot,cnt;
int dfn[N],low[N],book[N];
int vis[N],flag;
stack<int>stk;
int id[N];
map<pair<int,int>,int>mp;
vector<int>e[N],g[N];
int Get(int x,int y){
	return (x-1)*m+y;
}
void tarjan(int x){
	dfn[x] = low[x] = ++tot;
	stk.push(x);
	book[x] = 1;
	for(auto v:e[x]){
		if(!dfn[v]){
			tarjan(v);
			low[x] = min(low[x],low[v]);
		}
		else if(book[v]){
			low[x] = min(low[x],dfn[v]);
		}
	}
	if(low[x]==dfn[x]){
		int v;
		++cnt;
		do{
			v = stk.top();
			stk.pop();
			book[v] = 0;
			id[v] = cnt;
		}while(v!=x);
	}
}
void dfs(int x,int st)
{
	if(x!=st)
		mp[{st,x}] = 1;
	for(auto v:g[x]){
		mp[{x,v}] = 1;
		dfs(v,st);
	}
}
void DFS(int x,int en){
	if(flag)return;
	if(x==en){
		flag = 1;
		return;
	}
	for(auto v:g[x]){
		DFS(v,en);
		if(flag)return;
	}
}
int main()
{
	freopen("map.in","r",stdin);
	freopen("map.out","w",stdout);
	cin>>n>>m>>k>>q;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char ch;
			cin>>ch;
			if(ch=='#')vis[Get(i,j)]=-1;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(vis[Get(i,j)]==-1)continue;
			else{
				if(i>=2 && vis[Get(i-1,j)]==0)e[Get(i,j)].push_back(Get(i-1,j));
				if(i<n && vis[Get(i+1,j)]==0)e[Get(i,j)].push_back(Get(i+1,j));
				if(j>=2 && vis[Get(i,j-1)]==0)e[Get(i,j)].push_back(Get(i,j-1));
				if(j<m && vis[Get(i,j+1)]==0)e[Get(i,j)].push_back(Get(i,j+1));
			}
		}
	}
	for(int i=1;i<=k;i++){
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		e[Get(x1,y1)].push_back(Get(x2,y2));
	}
	for(int i=1;i<=n*m;i++){
		if(!dfn[i])tarjan(i);
	}
	for(int i=1;i<=n*m;i++){
		for(auto v:e[i]){
			if(id[i]!=id[v]){
				g[id[i]].push_back(id[v]);
			}
		}
	}
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=q;i++){
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		int st=Get(x1,y1),en=Get(x2,y2);
		if(id[st]==id[en]){
			cout<<1<<endl;
			continue;
		}
		flag = 0;
		DFS(id[st],id[en]);
		if(flag==1)cout<<1<<endl;
		else cout<<0<<endl;
	}
	return 0;
}

扰乱神器

subtask 1

暴力翻转并求逆序对即可。

subtask 2

暴力翻转后用线段树/树状树组求逆序对即可，时间复杂度 Θ(mnlog⁡n)\Theta(mn\log n)

subtask 3

考虑分治（参考归并排序）求逆序对的思路：每次分治成两段，计算左边集合对右边集合的贡献。我们维护逆序对的同时维护顺序对，发现翻转后跨块的贡献不变，块内的贡献逆序对和顺序对互换。

预处理出每层的贡献，翻转时更新底 n−qin-q_i 层的贡献即可。

时间复杂度 Θ((n+m)log⁡n)\Theta((n+m) \log n)

subtask 4

同 subtask 3，但翻转的只有一个块。在分治树上考虑，发现就是对某个结点的所有子树的左右儿子翻转。

类似线段树标记，对那个结点打上翻转标记即可。

时间复杂度 Θ((n+m)log⁡n)\Theta((n+m) \log n)，已经很接近正解了。

subtask 5

与 Subtask 4 不同的是，翻转的可以是很多个块。对每个块打标记的话，复杂度会大大降低，考虑优化。这个问题相当于对线段树底下若干层作翻转。于是线段树每个结点 uu 维护一个数组 sum⁡u,i\operatorname{sum}_{u, i} 表示底下第 ii 层是否翻转以及产生的贡献。

询问时更新 $\operatorname{sum}_{u, 1} \sim \operatorname{sum}_{u, n-q}$，打上标记即可。

时间复杂度 Θ(nlog⁡n+mlog⁡2n)\Theta\left(n \log n+m \log ^2 n\right)

#include <bits/stdc++.h>
using namespace std;
inline int read(){
	int s=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
	return s*f;
}
const int N=(1<<20)+5;
int n,m,p[N],tot,a[N],b[N];
#define ll long long
namespace SGT{
	int ls[N<<1],rs[N<<1],tag[N<<1];
	ll *sum[N<<1],*d[N<<1];
	#define lid ls[id]
	#define rid rs[id]
	#define mid ((l+r)>>1)
	void build(int id,int l,int r,int dep){
		sum[id]=new ll[dep+1];d[id]=new ll[dep+1];
		if(l==r)return;
		lid=id<<1;rid=id<<1|1;
		build(lid,l,mid,dep-1);build(rid,mid+1,r,dep-1);
		for(int i=0;i<dep-1;++i)
			sum[id][i]=sum[lid][i]+sum[rid][i],
			d[id][i]=d[lid][i]+d[rid][i];
		sum[id][dep-1]=d[id][dep-1]=0;
		int i=l,j=mid+1,k=0,pre=0;
		for(;j<=r;++j){
			while(i<=mid&&a[i]<a[j])b[++k]=a[i++];
			if(j==mid+1||a[j]!=a[j-1]){
				pre=0;
				while(i<=mid&&a[i]==a[j])b[++k]=a[i++],++pre;
			}
			d[id][dep-1]+=pre;
			sum[id][dep-1]+=mid-i+1;
			b[++k]=a[j];
		}
		while(i<=mid)b[++k]=a[i++];
		memcpy(a+l,b+1,k<<2);
	}
	inline void update(int id,int dep){
		for(int i=0;i<dep-1;++i)sum[id][i]=sum[lid][i]+sum[rid][i];
	}
	inline void cover(int id,int tg,int dep){
		for(int i=0;i<dep;++i)
			if(tg&(1<<i))
				sum[id][i]=(1ll<<(dep+i-1))-d[id][i]-sum[id][i];
		if(tg&(1<<(dep-1)))swap(lid,rid);
		tag[id]^=tg;
	}
	inline void pushdown(int id,int dep){
		if(!tag[id])return;
		tag[id]&=(1<<(dep-1))-1;
		cover(lid,tag[id],dep-1);
		cover(rid,tag[id],dep-1);
		tag[id]=0;
	}
	void modify(int id,int l,int r,int dep,int L,int R,int q){
		if(L<=l&&r<=R){
			cover(id,(1<<q)-1,dep);
			return;
		}
		pushdown(id,dep);
		if(L<=mid)modify(lid,l,mid,dep-1,L,R,q);
		if(R>mid)modify(rid,mid+1,r,dep-1,L,R,q);
		update(id,dep);
	}
	inline ll query(){
		ll ret=0;
		for(int i=0;i<n;++i)ret+=sum[1][i];
		return ret;
	}
}
int main(){
	n=read();m=read();tot=(1<<n);
	for(int i=1;i<=tot;++i)a[i]=p[i]=read();
	SGT::build(1,1,tot,n);
	int l,r,q;
	while(m--){
		q=read();l=read();r=read();q=n-q;
		SGT::modify(1,1,tot,n,(l-1)*(1<<q)+1,r*(1<<q),q);
		printf("%lld\n",SGT::query());
	}
	return 0;
}

阵列神器

因为非零元素数量不多，我们把矩阵看成一个完全二分图的邻接矩阵，用边表示矩阵元素。

两个 log⁡\log：

二分答案 kk ，判断是否能选 ≥k\geq k 条边。这样，题里的限制就变为: 后缀要选 ≥k−ai\geq k-a_i 条边。 在二分图的左边，我们倒序地做扫描线。设当前扫到 ii ，我们维护一个优先队列，存左端点 ≥i\geq i 的未选的边，内部 按照右端点从大到小排序。要选边时我们就从优先队列中拿一条出来。可以观察到两条性质:

  • 不到迫不得已 (即不选边就不符合限制) 的时候，不要选边。
  • 选的边右端点越大越优。 所以贪心地选一组方案，再判断右边合不合法即可。 但 cjc_j 可能比较大，我们在优先队列里存 (vj,cj)\left(v_j, c_j\right) 这样的二元组即可解决。时间 O(nlog⁡nlog⁡V)O(n \log n \log V) 。

一个 log⁡\log：

考虑把边集按照二元组 (u,v)(u, v) 从大到小排序，然后贪心地能选就选。下面证明这个算法是对的。

反证，假设算法进行到某一时刻选了 (x,y)(x, y) 这条边，而不存在最优方案包含它。任取一个最优方案，对于其中所有 的边 (p,q)(p, q) ，找到满足 p<xp<x 且 q>yq>y 且 qq 最小的边，记作 (p0,q0)\left(p_0, q_0\right) 。考虑证明把 (p0,q0)\left(p_0, q_0\right) 替换成 (x,y)(x, y) 仍合法。

首先 p0p_0 变成 xx 是变大了，肯定合法。而 q0q_0 变成 yy 只可能影响编号在区间 [y,q0−1]\left[y, q_0-1\right] 里的限制。我们记该最优方案中 满足 q∈[y+1,q0−1]q \in\left[y+1, q_0-1\right] 的所有边为 $\left(p_1, q_1\right),\left(p_2, q_2\right), \cdots,\left(p_k, q_k\right)$ ，那么一定有 pi>xop_i>x_{\mathrm{o}} 注意到在我们的算法里，这些边 一定已经被选了。而此时 (x,y)(x, y) 仍能被选，这就说明右边选了 q1,q2,⋯ ,qkq_1, q_2, \cdots, q_k 和 yy 仍符合限制，因此 q0q_0 能换成 y0y_0

我们用数据结构维护 bb 数组的余量，只要支持求后缀最小值、后缀减法。用带标记的树状数组维护即可。

最小割模型：

考虑建图:

  • 左侧右侧各 n+1n+1 个点。
  • 左侧 n+1n+1 为源点。
  • 左侧 i+1i+1 向左侧 ii 连容量为 aia_i 的边。
  • 左侧 uju_j 向右侧 vjv_j 连容量为 cjc_j 的边。
  • 右侧 ii 向右侧 i+1i+1 连容量为 bib_i 的边。
  • 右侧 n+1n+1 为汇点。

易证，这个图的最大流就是答案。因为边容量为正，最大流等于最小割。

可以证明：最小割一定是左侧割掉 x+1x+1 到 xx 的边，右侧割掉 yy 到 y+1y+1 的边，最后割掉所有 uj>xu_j>x 且 vj>yv_j>y 的边。

对 xx 这一维倒序做扫描线，维护 yy 这一维的答案。发现对应的操作是前缀加以及全局求 min⁡\min ，用线段树维护，时间 O(nlog⁡n)O(n \log n) 。

直接线段树可能卡常数。

但是因为每次加的都是正数，所以取到 min⁡\min 的位置不会左移，也就是说有决策单调性，用决策单调性的分治做法即可。这个做法的常数很小，虽然时间也是 O(nlog⁡n)O(n \log n)，但是跑得非常快。（时限是标程四倍）

#include<bits/stdc++.h>
#define loop(i,from,to) for(int i=(from);i<=(to);++i)
#define rloop(i,from,to) for(int i=(from);i>=(to);--i)
#define gloop(i,x) for(int i=head[x];i;i=suc[i])
using namespace std;
const int maxn=4e6,maxbuf=2e6;
int n,m,x,y,d,z,tot,ans,a[maxn+1],b[maxn+1],top[maxn+1],head[maxn+1],suc[maxn+1],to[maxn+1],len[maxn+1];
namespace IO{
	inline char getchar(){
		static char ibuf[maxbuf+1],*cur=ibuf+maxbuf;
	    return (cur==ibuf+maxbuf)?fread(cur=ibuf,1,maxbuf,stdin),*cur++:*cur++;
	}
	void read(int &x){
		x=0;
		char t=getchar();
		while(!isdigit(t))t=getchar();
		while(isdigit(t))x=x*10+t-'0',t=getchar();
		return;
	}
}
using namespace IO;
int find(int x){return x==top[x]?x:top[x]=find(top[x]);}
int main(){
    freopen("challenge.in","r",stdin);
    freopen("challenge.out","w",stdout);
	read(n),read(m);
	loop(i,1,n)read(a[i]),top[i]=i,a[i]+=a[i-1];
	loop(i,1,n)read(b[i]);
	loop(i,1,m)read(d),read(y),read(z),suc[++tot]=head[x+=d],head[x]=tot,to[tot]=y,len[tot]=z;
	ans=a[n];
	rloop(i,n,1){
		ans=min(ans,a[i]+b[0]);
		gloop(j,i){
			b[find(to[j])]-=len[j],b[0]+=len[j];
			for(int now=find(to[j]);b[now]<0;now=find(to[j]))b[top[now]=find(now-1)]+=b[now];
		}
		if(b[0]>=ans)break;
	}
	printf("%d",ans);
	return 0;
}

我们会审查剪贴板内容，并对发布不合适内容的同学进行相应的处理
  1. Judging Queue
  2. Service Status
  3. Legacy mode
  4. Theme
  2. 蜀ICP备2022005482号-4
  3. Worker 0, 26ms
  4. Powered by Hydro v5.0.0-beta.9 Community