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;
}
标签:le,08.18,int,赛一,NOIP2022,const,mod,RI,define
From: https://www.cnblogs.com/cjjsb/p/16598417.html