【题解】牛客OI周赛15-普及组

${A}.$ 咪咪游戏

应该比较简单，就是 ${O(n)}$ 扫一遍即可

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
inline int read()
{
	int sum=0,ff=1; char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		sum=sum*10+(ch^48),ch=getchar();
	return sum*ff;
}
 
const int N=1e5+5;
 
char ch[N];
 
signed main()
{
	int Q=read();
	for (;Q--;)
	{
		
		scanf("%s",ch+1);
		int n=strlen(ch+1);
		if(n&1) 
		{
			printf("No\n");
			goto rp;
		}
		for ( int i=1;i<=n;i+=2 ) 
			if(ch[i]=='m'&&ch[i+1]=='q') continue;
			else 
			{
				printf("No\n");
				goto rp;
			}
		printf("Yes\n");
		rp:;
	}
}

${B}.$ 三角形

${50ptc}$

把所有情况枚举出来，取前m大即可。

${100ptc}$

考虑 ${Dp}$ ，我们先对每种宝箱做背包。

$f_{i,j}$ 表示到第i个宝箱得到价值为 ${j}$ 的方案数，则有 $f_{i,k}=\sum f_{i-1,k-w_{i,j}}$

于是只要 ${O(tot*n*n)}$ 转移即可， ${tot}$ 为每个宝箱最大值的和。

统计答案就很简单了。

#include <bits/stdc++.h>
using namespace std;

const int N=105;
const int M=N*N;

int n,m,f[N][M],a[N][N],ret[M],ans,tot;

inline int read() {
	int sum=0; char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) 
		sum=sum*10+(ch^48),ch=getchar();
	return sum;
}

int main() {
	n=read(),m=read();
	for ( int i=1;i<=n;i++ ) {
		a[i][0]=read();
		int nm=0;
		for ( int j=1;j<=a[i][0];j++ ) {
			a[i][j]=read();
			nm=max(nm,a[i][j]);
		}
		tot+=nm;
	}
	f[0][0]=1;
	for ( int i=1;i<=n;i++ ) 
		for ( int j=1;j<=a[i][0];j++ ) 
			for ( int k=tot;k>=a[i][j];k-- ) 
				if(f[i-1][k-a[i][j]]) 
					f[i][k]+=f[i-1][k-a[i][j]];
	int sum=0,res=0; 
	for ( int i=1;i<=tot;i++ ) {
		while(f[n][i]) {
			res+=i;
			f[n][i]--;
			sum++;
			if(sum==m) return printf("%d\n",res),0;
		}
	}
	return 0;
}

${C}.$ 区间加

$n\leq 10$ 各种暴力随便做，期望得分20ptc

以左括号表示操作区间左端点，右括号表示操作区间右端点，那么一个位置不能出现两个以及上的左括号或右括号。

故一个位置只有四种情况：

- 不放括号

- 放一个左括号

- 放一个右括号

- 放一个左括号放一个右括号

所以我们设f(i,j)表示前i个位置左括号比右括号多j个且使 $a_1=a_2=...=a_i=h$ 的方案数

对于第i个位置不放括号，有f[i][j]+=f[i−1][j]

第i个位置放左括号，有f[i][j]+=f[i−1][j−1]

第i个位置放右括号，有f[i][j]+=(j+1)⋅f[i−1][j+1]，其中乘上j+1是因为要给当前放的这个右括号匹配上左括号

第i个位置放左右括号，有f[i][j]+=(j+1)⋅f[i−1][j]，其中乘上j+1与上一种情况同理

注意对于1,2情况，a[i]位置相当于被加了j，故需要a[i]+j=h该步才可以转移过去。同样的，对于3,4情况，a[i]位置加了j+1，故需要a[i]+j+1=h，

最后f[n][0]即为答案

#include <bits/stdc++.h>
#define int long long
using namespace std;

inline int read()
{
	int sum=0,ff=1; char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		sum=sum*10+(ch^48),ch=getchar();
	return sum*ff;
}

const int mo=998244355;
const int N=4005;

int n,m,f[N][N],a[N],ans;

signed main()
{
	n=read();
	m=read();
	for ( int i=1;i<=n;i++ ) a[i]=read();
	if(a[1]==m-1||a[1]==m) f[1][0]=1;
	if(a[1]==m-1) f[1][1]=1;
	for ( int i=2;i<=n;i++ ) 
		for ( int j=max(0ll,m-a[i]-1);j<=max(m-a[i],i);j++ ) 
		{
			if(a[i]+j==m) 
			{
				f[i][j]=(f[i][j]+f[i-1][j]+mo)%mo;
				if(j) f[i][j]+=f[i-1][j-1]%mo;
				f[i][j]=(f[i][j]+mo)%mo;
			}
			if(a[i]+j==m-1)
			{
				f[i][j]+=(f[i-1][j+1]*(j+1))%mo;
				f[i][j]=(f[i][j]+mo)%mo;
				f[i][j]+=(f[i-1][j]*(j+1))%mo;
				f[i][j]=(f[i][j]+mo)%mo;
			}
		}
	printf("%lld\n",(f[n][0]+mo)%mo);
	return 0;
}

${D}.$ 多元组

其实就是对于M=3的拓展。

对于M=3的情况，考虑树状数组。对于一个a[i]，它的贡献即为左边比他小的 $\times$ 右边比他大的。然后这些就可以用树状数组维护。

考虑到k有两个限制条件，k 具体来说，在外层循环i，建立一个树状数组，以a[k]为下标存储f[i-1][k]的值。当内层循环到j时，f[i][j]+=ask(a[j]-1)，然后在转移到下一个j之前add(a[j],f[i-1][j])。j从小到大循环保证了k
复杂度O(NMlogN)

#include<bits/stdc++.h>
using namespace std;
#define N 100050
const int mod=1e9+7;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}
int a[N],b[N],n,mx,bit[51][N],ans,k;
#define ck(x) (x>=mod?x-mod:x)
inline void Add(int p,int x,int d){
	while(x<=mx){
		bit[p][x]=ck(bit[p][x]+d);
		x+=(x&(-x));
	}
}
inline int Ask(int p,int x){
	int ans=0;
	while(x){
		ans=ck(ans+bit[p][x]);
		x-=(x&(-x));
	}
	return ans;
}
int main(){
	n=read();k=read();
	for(int i=1;i<=n;i++){
		a[i]=b[i]=read();
	}
	sort(b+1,b+n+1);
	mx=unique(b+1,b+n+1)-b-1;
	for(register int i=1;i<=n;i++){
		a[i]=lower_bound(b+1,b+mx+1,a[i])-b;
	}
	for(register int i=1;i<=n;i++){
		Add(1,a[i],1);
		for(int j=2;j<=k;j++){
			int tmp=Ask(j-1,a[i]-1);
			Add(j,a[i],tmp);
		}
	}
	for(int i=1;i<=mx;i++){
		ans=(ans+Ask(k,i)-Ask(k,i-1)+mod)%mod;
	}
	cout<<ans<<endl;
	return 0;
}