AC源Day4模拟赛复盘

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

int n,ans=1;
int a[N],b[N],f[N];
int find(int l,int r,int x){	
	int mid=(l+r)/2;
	if((a[mid]>x && a[mid-1]<x) || a[mid]==x) return mid;
	else if(a[mid]<x && a[mid+1]>x) return mid+1;
	else if(x>a[mid]) return find(mid+1,r,x);
	else return find(l,mid,x);
}

signed main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	freopen("apple.in","r",stdin);
	freopen("apple.out","w",stdout);
	
	cin>>n;
	for(int i=1;i<=n;i++) cin>>b[i];
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	if(b[1]>a[1] || b[n]>a[n]){
		cout<<0;
		return 0;
	}
	for(int i=1;i<=n;i++){
		f[i]=n-find(1,n,b[i])+1;
	}
	for(int i=n;i>=1;i--){
		ans*=f[i]-(n-i);
	}
	cout<<ans;
	return 0;
}

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

int n,t;
int last[N],a[N];

signed main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	freopen("tea.in","r",stdin);
	freopen("tea.out","w",stdout);
	
	cin>>t;
	for(int i=1;i<=t;i++){
		memset(last,0,sizeof(last));
		memset(a,0,sizeof(a));
		map<int,bool> mp;
		cin>>n;
		for(int i=1;i<=n;i++){
			int x;
			cin>>x;
			if(last[x] && i-last[x]<=2) mp[x]=1;
			last[x]=i;
		}
		bool hv=0;
		for(auto i:mp){
			if(i.second) hv=1,cout<<i.first<<" ";
		}
		if(!hv) cout<<-1<<"\n";
		else cout<<"\n";
	}
	return 0;
}

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

int n,a[N];
map<int,int> mp;

signed main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	freopen("mex.in","r",stdin);
	freopen("mex.out","w",stdout);
	
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		mp[a[i]]++;
	}
	int ans=0;
	for(int x=0;x<=n;x++){
		if(x>0) if(mp[x-1]==0) ans++;
		cout<<max(mp[x],ans)<<"\n";
	}
	return 0;
}

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

int n;
int h[N],rx[N];

signed main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	freopen("frisbee.in","r",stdin);
	freopen("frisbee.out","w",stdout);
	
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			bool ps=1;
			for(int k=i+1;k<=j-1;k++){
				if(h[k]>min(h[i],h[j])){
					ps=0;
					break;
				}
			}
			if(ps){
				ans+=j-i+1;
			}
		}
	}
	cout<<ans;
	return 0;
}

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

int n;
int h[N],ans=0;
stack<int> s;

signed main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}
	for(int i=1;i<=n;i++){
		while(!s.empty() && h[s.top()]<h[i]) s.pop();
		if(!s.empty()) ans+=i-s.top()+1;
		s.push(i);
	}
	while(!s.empty()) s.pop();
	for(int i=n;i>=1;i--){
		while(!s.empty() && h[s.top()]<h[i]) s.pop();
		if(!s.empty()) ans+=s.top()-i+1;
		s.push(i);
	}
	
	cout<<ans;
	return 0;
}