526互联

Hello 2024

发布时间 2024-01-09 13:44:59作者: 空気力学の詩

Preface

好久没打CF了，考完试有空就赶着来打这新年的第一场

由于算起来得有一两个月没有现场打CF了，而且为了准备期末考也两周没摸键盘，因此代码能力有点生疏

D题20min换了两个写法狂WA4发后发现原来是多测清空写假了

E题经典奇妙数数题做不来一点，还好看了眼榜跑路了去把F1写了，最后1h30min准时下班去看漫画去了

没想到这样也能卡卡上分，早知道拿大号打了

A. Wallet Exchange

签到，判断下\(a+b\)的奇偶性即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
int t,a,b;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	scanf("%d%d",&a,&b),puts((a+b)%2?"Alice":"Bob");
	return 0;
}

B. Plus-Minus Split

不难发现以下的贪心策略，若从当前位置开始往后存在某一段的前缀和为\(0\)，则直接选择这一段；否则单独取一个数即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=5005;
int t,n,pfx[N],nxt[N],bkt[N<<1]; char s[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%s",&n,s+1),i=1;i<=n;++i) pfx[i]=pfx[i-1]+(s[i]=='+'?1:-1);
		for (i=-n;i<=n;++i) bkt[i+n]=n+1;
		for (i=n;i>=1;--i) nxt[i]=bkt[pfx[i-1]+n],bkt[pfx[i]+n]=i;
		int ans=0; for (i=1;i<=n;) if (nxt[i]<=n) i=nxt[i]+1; else ++ans,++i;
		printf("%d\n",ans);
	}
	return 0;
}

C. Grouping Increases

经典小贪心，记录下当前两个序列的末尾的数是什么，不妨记为\(a,b(a\le b)\)

考虑对于新加入的一个数\(x\)，将其放在那个序列后面是最优的

  • \(x\le a\)，此时直接放在\(a\)后面，因为这样不会产生贡献并且能把更大的数\(b\)留下来
  • \(x\le b\)，此时直接放在\(b\)后面，因为放在\(a\)后面会产生贡献，不产生贡献一定比产生贡献要优
  • \(x>b\)，此时一定会产生贡献，那么放在\(a\)后面以保留较大的数\(b\)
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005,INF=1e9;
int t,n,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
		int A=INF,B=INF,ans=0; for (i=1;i<=n;++i)
		{
			if (A>B) swap(A,B);
			if (a[i]<=A) { A=a[i]; continue; }
			if (a[i]<=B) { B=a[i]; continue; }
			A=a[i]; ++ans;
		}
		printf("%d\n",ans);
	}
	return 0;
}

D. 01 Tree

挺新颖的一个题，就是有点细节容易写挂

观察这个树的性质，不难发现对于两个父亲相同的叶节点，它们的权值差一定为\(1\)

并且这个性质还可以继续推广，对于满足上述条件的节点对我们可以合并它们，得到一个权值为原来两者间较小的节点

那么现在的问题就抽象为，对于给定的序列，每次可以选择两个相邻的并且权值差为\(1\)的元素，并将其中较大的那个删去，当可以删得只剩下最后一个\(0\)时即为合法

不难发现删除的过程一定是从大到小最优，但考虑到会有例如\(2,2,2,1\)这样的情形，中间的\(2\)要等到边上的\(2\)删除后才能进行

一个比较简单粗暴的做法就是用并查集把所有值相同的数合并在一起，只要一个在同一个集合中的数有一个可以删除则整个集合都可以删除

剩下的就是用链表维护删除过程了，非常trivial

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,a[N],L[N],R[N],fa[N],vis[N]; vector <int> pos[N];
inline int getfa(CI x)
{
	return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d",&n),i=0;i<n;++i) pos[i].clear();
		for (i=1;i<=n;++i) scanf("%d",&a[i]),pos[a[i]].push_back(i),vis[i]=0,fa[i]=i,L[i]=i-1,R[i]=i+1;
		if (pos[0].size()!=1) { puts("NO"); continue; }
		R[0]=1; L[n+1]=n; bool flag=1;
		for (i=n-1;i>0&&flag;--i) if (!pos[i].empty())
		{
			for (j=1;j<pos[i].size();++j)
			if (R[pos[i][j-1]]==pos[i][j]) fa[getfa(pos[i][j-1])]=getfa(pos[i][j]);
			for (auto x:pos[i])
			{
				int pre=L[x],nxt=R[x];
				if ((pre!=0&&a[pre]==a[x]-1)||(nxt!=n+1&&a[nxt]==a[x]-1)) vis[getfa(x)]=1;
			}
			for (auto x:pos[i]) if (!vis[getfa(x)]) { flag=0; break; }
			if (flag) for (auto x:pos[i])
			{
				int pre=L[x],nxt=R[x]; R[pre]=nxt; L[nxt]=pre;
			}
		}
		puts(flag?"YES":"NO");
	}
	return 0;
}

E. Counting Prefixes

好神奇的题，鉴定为混杂着ATC风格的CF题

考虑设前缀和中最小/最大的数为\(L,R\)，则最后序列的和\(s\in[L,R]\)，我们不妨枚举\(s\)的取值

由于前缀和最大值为\(R\)，则序列中一定存在一个和为\(R\)的前缀

不妨用以下方法来构建一个合法的序列，首先列出\(R\)个\(1\)，然后后面放\(R-s\)个\(-1\)以使得序列的和为\(s\)

接下来考虑通过不断地往序列中插入\((-1,1)\)二元组来让序列满足所有前缀和出现次数的要求

不难发现在某个前缀和为\(x\)的数后面插入\((-1,1)\)的影响就是加入一个前缀和为\(x-1\)和一个前缀和为\(x\)的位置

利用这个我们就可以倒推求解了，先根据最后需要有多少个\(R\)就知道要在\(R\)后面插入多少个\((-1,1)\)，然后依次类推\(R-1,R-2,\cdots\)即可

设\(cnt_i\)为我们需要的\(i\)的总个数，\(f_i\)为处理完\(i+1\)后得到的\(i\)的个数，那么现在我们需要将\(cnt_i-f_i\)个\((-1,1)\)插入到已有的\(f_i\)个\(i\)后面，这个用隔板法可以很快算出方案数

具体实现的时候要注意一些细节，比如刚开始那些值出现了两次/一次/零次

总复杂度\(O(n^2)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=10005,mod=998244353,INF=1e9;
int t,n,x,cnt[N],f[N],fact[N],ifac[N];
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
	RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
	for (ifac[n]=quick_pow(fact[n]),i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
inline int C(CI n,CI m)
{
	if (n<0||m<0||n<m) return 0;
	return 1LL*fact[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t),init(10004);t;--t)
	{
		RI i,j; for (scanf("%d",&n),++n,i=0;i<=2*n;++i) cnt[i]=0;
		for (i=1;i<n;++i) scanf("%d",&x),++cnt[x+n]; ++cnt[0+n];
		int l=INF,r=-INF; for (i=0;i<=2*n;++i)
		if (cnt[i]>0) l=min(l,i),r=max(r,i);
		bool flag=1; for (i=l;i<=r&&flag;++i) if (cnt[i]==0) flag=0;
		if (!flag) { puts("0"); continue; }
		int ans=0; for (i=l;i<=r;++i)
		{
			f[r-1]=cnt[r]-1+1;
			if (r==n&&i==n) --f[r-1];
			if (r!=n&&i!=r) ++f[r-1];
			for (j=r-2;j>=l-1;--j)
			{
				f[j]=cnt[j+1]-f[j+1];
				if (j>=n) ++f[j];
				if (j>=i) ++f[j];
			}
			if (f[l-1]!=0) continue;
			auto Comb=[&](CI n,CI m)
			{
				if (n==0&&m==0) return 1; return C(n+m-1,m-1);
			};
			int ret=1; for (j=r-1;j>=l;--j)
			ret=1LL*ret*Comb(cnt[j]-f[j],f[j])%mod;
			(ans+=ret)%=mod;
		}
		printf("%d\n",ans);
	}
	return 0;
}

F1. Wine Factory (Easy Version)

比赛时候只盯着F1的性质去写了，导致没有看出问题的本质就是个网络流模型，导致完全能写出的F2没写出来

先讲下我的F1的做法吧，注意到我们可以把节点根据\(a_i,b_i\)的大小关系分成两类，显然每个节点会产生一些贡献，同时会有多出的\(a\)的值或者\(b\)的值

那么对于区间也是同理，我们对于某个区间\([l,r]\)可以维护一个三元组\((S,A,B)\)，分布表示这个区间的贡献，这个区间能向后传递的多余的\(a_i\)之和，以及这个区间能接收其之前的多余的\(b_i\)之和

合并信息的话只要把两个相邻区间的相互共用的情况算一下即可，拿个线段树维护一下单点修改即可

总复杂度\(O(n\log n)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=500005;
int n,q,a[N],b[N],c[N],p,x,y,z;
class Segment_Tree
{
	private:
		int S[N<<2],A[N<<2],B[N<<2];
		inline void pushup(CI now)
		{
			int ls=now<<1,rs=now<<1|1,tmp=0; S[now]=S[ls]+S[rs];
			if (A[ls]>=0&&B[rs]>=0)	tmp=min(A[ls],B[rs]),S[now]+=tmp;
			A[now]=A[ls]+A[rs]-tmp; B[now]=B[ls]+B[rs]-tmp;
		}
	public:
		#define TN CI now=1,CI l=1,CI r=n
		#define LS now<<1,l,mid
		#define RS now<<1|1,mid+1,r
		inline void build(TN)
		{
			if (l==r)
			{
				S[now]=min(a[l],b[l]); A[now]=B[now]=0;
				if (b[l]<=a[l]) A[now]=a[l]-b[l]; else B[now]=b[l]-a[l];
				return;
			}
			int mid=l+r>>1; build(LS); build(RS); pushup(now);
		}
		inline void updata(CI pos,TN)
		{
			if (l==r)
			{
				S[now]=min(a[l],b[l]); A[now]=B[now]=0;
				if (b[l]<=a[l]) A[now]=a[l]-b[l]; else B[now]=b[l]-a[l];
				return;
			}
			int mid=l+r>>1; if (pos<=mid) updata(pos,LS); else updata(pos,RS); pushup(now);
		}
		inline int query(void)
		{
			return S[1];
		}
		#undef TN
		#undef LS
		#undef RS
}SEG;
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%lld%lld",&n,&q),i=1;i<=n;++i) scanf("%lld",&a[i]);
	for (i=1;i<=n;++i) scanf("%lld",&b[i]);
	for (i=1;i<n;++i) scanf("%lld",&c[i]);
	for (SEG.build(),i=1;i<=q;++i)
	{
		scanf("%lld%lld%lld%lld",&p,&x,&y,&z);
		a[p]=x; b[p]=y; SEG.updata(p); printf("%lld\n",SEG.query());
	}
	return 0;
}

F2. Wine Factory (Hard Version)

其实比赛时候也有想过怎么把F1的做法扩展到F2，但由于没有转化过问题会出现因为一个\(c_i\)的修改导致线段树上要改一大片节点的情况，没法处理

考虑将本问题的本质找出来，其实就是个网络流模型，从源点\(s\)向每个点\(i\)连容量为\(a_i\)的边；每个点\(i\)向汇点\(t\)连容量为\(b_i\)的边；最后\(i\)向\(i+1\)连容量为\(c_i\)的边，最后\(s\)到\(t\)的最大流就是答案

转化为最小割后再考虑其性质，我们可以发现一个关键点：\(s\to i\)和\(i\to t\)的两条边中有且仅有一条会被割掉

具体的证明可以看官方题解，就是根据\(s\)可以/不可以到达\(i\)来分类讨论证明

现在考虑有了这个性质后我们如何抽象问题，不难发现可以对每个\(i\)用一个字符\(A/B\)来表示割掉的是哪条边，最后就能得到一个字符串\(s_i\)

对于两个相邻的字符\(s_i,s_{i+1}\)，若满足\(s_i=B\and s_{i+1}=A\)，则此时仍然存在一条\(s\to i\to i+1\to t\)的路径，不满足割的性质，因此要割去\(c_i\)这条边

那么我们就很好处理问题了，还是用线段树维护区间，对于每个区间分别记录两个端点的不同取值时得到的最小割，合并的时候讨论一下即可

总复杂度\(O(n\log n)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=500005,INF=1e18;
int n,q,a[N],b[N],c[N],p,x,y,z;
class Segment_Tree
{
	private:
		int res[N<<2][2][2];
		inline void pushup(CI now,CI mid)
		{
			int ls=now<<1,rs=now<<1|1;
			for (RI p=0,q,s,t;p<2;++p) for (q=0;q<2;++q)
			for (res[now][p][q]=INF,s=0;s<2;++s) for (t=0;t<2;++t)
			res[now][p][q]=min(res[now][p][q],res[ls][p][s]+res[rs][t][q]+(s==1&&t==0?c[mid]:0));
		}
	public:
		#define TN CI now=1,CI l=1,CI r=n
		#define LS now<<1,l,mid
		#define RS now<<1|1,mid+1,r
		inline void build(TN)
		{
			if (l==r)
			{
				res[now][0][0]=a[l]; res[now][1][1]=b[l];
				res[now][0][1]=res[now][1][0]=INF; return;
			}
			int mid=l+r>>1; build(LS); build(RS); pushup(now,mid);
		}
		inline void updata(CI pos,TN)
		{
			if (l==r)
			{
				res[now][0][0]=a[l]; res[now][1][1]=b[l];
				res[now][0][1]=res[now][1][0]=INF; return;
			}
			int mid=l+r>>1; if (pos<=mid) updata(pos,LS); else updata(pos,RS); pushup(now,mid);
		}
		inline int query(int ret=INF)
		{
			for (RI p=0;p<2;++p) for (RI q=0;q<2;++q) ret=min(ret,res[1][p][q]); return ret;
		}
		#undef TN
		#undef LS
		#undef RS
}SEG;
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%lld%lld",&n,&q),i=1;i<=n;++i) scanf("%lld",&a[i]);
	for (i=1;i<=n;++i) scanf("%lld",&b[i]);
	for (i=1;i<n;++i) scanf("%lld",&c[i]);
	for (SEG.build(),i=1;i<=q;++i)
	{
		scanf("%lld%lld%lld%lld",&p,&x,&y,&z);
		a[p]=x; b[p]=y; c[p]=z; SEG.updata(p); printf("%lld\n",SEG.query());
	}
	return 0;
}

Postscript

byd好像CF最近抓开小号的现象抓的很严啊，不过无所谓我会顶风作案（水平太低官方肯定懒得查）