"蔚来杯"2022牛客暑期多校训练营9

A Car Show

题意：

给定一个数组，请找到有多个区间 [L,R] 满足 1 到 m 的数都出现过。

分析：直接双指针就好

#include<bits/stdc++.h>
using namespace std;
long long n,m,s[100100],v[100100],cnt,ans;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>s[i];
	
	for(int l=1,r=1;r<=n;r++)
	{
		if(v[s[r]]==0) cnt++;
		v[s[r]]++;
		while(v[s[l]]>1) v[s[l++]]--;
		if(cnt==m) ans+=l;
	}
	cout<<ans;
}

B Two Frogs

这个题思想很好 一维和二维位置互换 使得可以差分

#include <stdio.h>
const int N=8005;
int a[N],n;
const long long mod=998244353;
long long f[N],g[N],inv[N],ans;
int main()
{
	scanf("%d",&n);
	inv[1]=1;
	for (int i=2;i<=n;++i) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for (int i=1;i<n;++i) scanf("%d",&a[i]);
	g[1]=1;
	for (int t=1,i;t<n;++t)
	{
		for (i=t;i<n;++i)
		{
			f[i+1]+=g[i]*inv[a[i]]%mod;
			f[i+a[i]+1]-=g[i]*inv[a[i]]%mod;
		}
		g[t]=0;
		for (i=t+1;i<=n;++i)
		{
			g[i]=(g[i-1]+f[i])%mod;
			f[i]=0;
		}
		ans=(ans+g[n]*g[n])%mod;
	}
	printf("%lld\n",ans);
}

E Longest Increasing Subsequence

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

template<class T>inline void read(T&x){
	char c,last=' ';
	while(!isdigit(c=getchar()))last=c;
	x=c^48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+(c^48);
	if(last=='-')x=-x;
}

const int MAXN=1e2+5;
int m;
int n;
int a[MAXN];

int main()
{
	int T;read(T);
	while(T--){
		read(m);
		if(m==1){
			puts("1\n1");
			continue;
		}
		int M=0;
		while(1<<M<=m)++M;
		--M;
		vector<int>v;
		for(int i=1;i<=M;++i){
			v.push_back(2*i);
			v.push_back(2*i-1);
		}
		for(int i=M-1,cnt=0;i>=0;--i){
			if(m>>i&1){
				while(cnt<M-i)v.insert(v.begin()+2*i,0),++cnt;//先标记插入位
			}
		}
		for(int i=0,c=2*M;i<(int)v.size();++i){
			if(v[i]==0)v[i]=++c;//从前往后递增赋值
		}
		cout<<(int)v.size()<<'\n';
		for(int i=0;i<(int)v.size();++i)cout<<v[i]<<" \n"[i+1==(int)v.size()];
	}
	return 0;
}

I The Great Wall II

#include<bits/stdc++.h>
using namespace std;
const int N=8e3+5;
int f[2][N],g[N],mi[N],stk[N],n,a[N],top;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i],f[0][i]=0x3f3f3f3f;
	for(int k=1;k<=n;k++){
		int id=k&1;
		f[id][top=0]=0x3f3f3f3f;
		for(int i=k;i<=n;i++){
			mi[i]=f[id^1][i-1];
			while(top&&a[stk[top]]<=a[i]){
				mi[i]=min(mi[i],mi[stk[top]]);
				top--;
			}
			f[id][i]=min(f[id][stk[top]],mi[i]+a[i]);
			stk[++top]=i;
		}
		cout<<f[id][n]<<'\n';
	}
}