A. 「NOIP2022模拟赛一 By RSJ」String Search

Pro

• 给定一个\(01\)字符串，查找一个子串使得\(0\)在这个子串中出现了\(\frac{p}{q}\cdot k\)次，其中\(k\)是子串长度
• \(n,p,q\le 2\times 10^5,p\le q\)

Sol

#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,pfx[N],p,q; char s[N];
int main()
{
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; bool flag=0; scanf("%d%d%d%s",&n,&p,&q,s+1),p=q-p;
		for (i=1;i<=n;++i) pfx[i]=pfx[i-1]+s[i]-'0';
		if (n>5000)
		{
			for (i=1;i<=n&&!flag;++i) if (i>=q&&pfx[i]-pfx[i-q]==p) flag=1,printf("YES\n%d %d\n",i-q+1,i);
		} else
		{
			
			for (j=q;j<=n&&!flag;j+=q) for (i=j;i<=n&&!flag;++i)
			if (1LL*(pfx[i]-pfx[i-j])*q==1LL*p*j) printf("YES\n%d %d\n",i-j+1,i),flag=1;
		}
		if (!flag) puts("NO");
	}
	return 0;
}

B. 「NOIP2022模拟赛一 By RSJ」Give You This Absolutely Amazing Doodle To Demonstrate

Pro

• 有\(n\)个数，你需要将他们分为若干组，每组的落差值等于组内最大的数乘\(2\)减去最小的数
• 求各组落差值之和不超过\(x\)的分组方案数
• \(n\le 100,x\le 5000\)

Sol

#include<cstdio>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=105,X=5005,mod=998244353;
int n,x,f[N][N][X],a[N],d[N],ans;
inline void inc(int& x,CI y)
{
	if ((x+=y)>=mod) x-=mod;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k; for (scanf("%d %d",&n,&x),i=1;i<=n;++i) scanf("%d",&a[i]);
	for (sort(a+1,a+n+1),i=1;i<=n;++i) d[i]=a[i]-a[i-1];
	for (f[0][0][0]=1,i=0;i<n;++i) for (j=0;j<=i;++j)
	{
		int t=d[i+1]*j; for (k=0;k+t<=x;++k) if (f[i][j][k])
		{
			inc(f[i+1][j][k+t],1LL*(j+1)*f[i][j][k]%mod);
			inc(f[i+1][j+1][k+t],f[i][j][k]);
			if (j>0&&k+t+a[i+1]<=x) inc(f[i+1][j-1][k+t+a[i+1]],1LL*j*f[i][j][k]%mod);
		}
	}
	for (i=0;i<=x;++i) inc(ans,f[n][0][i]); return printf("%d",ans),0;
}

C. 「NOIP2022模拟赛一 By RSJ」Stock Trading

Pro

• 你预测了一支股票未来\(n\)天价格，你初始没有票，但有花不完的钱
• 每天最多将\(1\)支股票卖出或买入，但是任何时刻持有的股票数量要在\([l,r]\)之间
• 求出最终利益的最大值
• \(-10^6\le -n\le l\le 0\le r\le n\le 10^6\)

Sol

#include<bits/stdc++.h>
#define Cn const
#define CI Cn int&
#define N 1000000
#define LL long long
using namespace std;
namespace FastIO
{
	#define FS 100000
	#define Tp template<typename Ty>
	#define Ts template<typename Ty,typename... Ar>
	#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
	#define D isdigit(oc=tc())
	int ff;char oc,FI[FS],*FA=FI,*FB=FI;
	Tp void read(Ty& x) {x=0,ff=1;while(!D) ff=oc^'-'?1:-1;while(x=(x<<3)+(x<<1)+(oc&15),D);x*=ff;}
	Ts void read(Ty& x,Ar&... y) {read(x),read(y...);}
}using namespace FastIO;
int n,l,r,a[N+5];multiset<int> G;
int main()
{
	int i,j;for(read(n,l,r),i=1;i<=n;++i) read(a[i]);
	int L=0,R=0;LL t=0;for(i=1;i<=n;++i) G.insert(a[i]),G.insert(a[i]),t-=a[i],
	L==l?(G.erase(G.begin()),0):--L,R==r?(t+=*--G.end(),G.erase(--G.end()),0):++R;
	for(auto x:G) t+=x;return printf("%lld\n",t),0;
}

D. 「NOIP2022模拟赛一 By RSJ」74TrAkToR's Div.2 Problem

Pro

• 给定一个\(n\)个节点，\(m\)条边，无自环，无重边，保证联通的有向图
• 改变一些边的方向后，可使得该有向图无环
• 求所有不同的改变方案需要改变方向的边的数量之和
• \(2\le n\le 18,m\le 200\)

Sol

#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
const int N=1<<18,mod=998244353;
int n,m,lim,f[N],s[N],coef[N],x,y;
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 inc(int& x,CI y)
{
	if ((x+=y)>=mod) x-=mod;
}
int main()
{
	RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
	scanf("%d%d",&x,&y),--x,--y,s[(1<<x)|(1<<y)]=1;
	for (lim=1<<n,j=0;j<lim;++j) for (i=0;i<n;++i) if (j&(1<<i)) s[j]|=s[j^(1<<i)];
	for (f[0]=i=1;i<lim;++i) for (coef[i]=coef[i&(i-1)]^1,j=i;j;j=(j-1)&i)
	if (!s[j]) inc(f[i],coef[j]?f[i^j]:mod-f[i^j]);
	return printf("%d",1LL*f[lim-1]*m%mod*quick_pow(2)%mod),0;
}