2021.11.15 NOIP模拟

信心赛。除了第四题。

T1

• 题面
  
• 解法
  模拟即可。当时极其懒惰的我用了set，虽然过掉是没有问题，但时间上被手写哈希的xsy大佬吊打……

#include
#include
//#define zczc
using namespace std;
inline void read(int &wh){
	wh=0;int f=1;char w=getchar();
	while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
	while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
	wh*=f;return;
}
inline char get(){
	char w=getchar();
	while(w<'A'||w>'Z')w=getchar();
	return w;
}

struct node{
	int x,y;
};
bool operator <(node s1,node s2){
	return s1.x!=s2.x?s1.xa;

signed main(){
	
	#ifdef zczc
	freopen("in.txt","r",stdin);
	#endif
	#ifndef zczc
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	#endif
	
	int m,x=0,y=0;
	read(m);
	a.insert((node){0,0});
	while(m--){
		switch(get()){
			case 'U':y++;break;
			case 'D':y--;break;
			case 'R':x++;break;
			case 'L':x--;break;
		}
		if(a.count((node){x,y})==0)a.insert((node){x,y});
	}
	printf("%d",a.size());
	
	return 0;
}

T2

• 题面
  
• 解法
  同班的大佬们考完之后纷纷说是找规律，但本蒟蒻硬是没想出来，于是使用了某些奇怪的方法转到线性筛上面了，于是时间再次被吊打。

#include
#include
//#define zczc
#define ll long long
using namespace std;
const int N=1000010;
inline void read(int &wh){
	wh=0;int f=1;char w=getchar();
	while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
	while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
	wh*=f;return;
}
inline void check(ll &s1,ll s2){
	if(s1>1];
int p[N>>1],cnt;
bool s[N];

signed main(){
	
	#ifdef zczc
	freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	#endif
	#ifndef zczc
	freopen("b.in","r",stdin);
	freopen("b.out","w",stdout);
	#endif
	
	memset(f,-1,sizeof(f));
	f[3]=1;f[4]=2;
	for(int i=2;i

#include
#include
//#define zczc
#define ll long long
using namespace std;
const int N=500010;
inline void read(int &wh){
	wh=0;int f=1;char w=getchar();
	while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
	while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
	wh*=f;return;
}
inline void check(ll &s1,ll s2){
	if(s1st;

signed main(){
	
	#ifdef zczc
	freopen("in.txt","r",stdin);
	#endif
	#ifndef zczc
	freopen("c.in","r",stdin);
	freopen("c.out","w",stdout);
	#endif
	
	read(m);ll ans=0;
	for(int i=1;i<=m;i++)read(a[i]);
	st.push((node){0,-1});
	for(int i=1;i<=m;i++){
		while(st.top().data>=a[i])st.pop();
		pl[i]=st.top().pl;
		st.push((node){i,a[i]});
	}
	while(!st.empty())st.pop();
	st.push((node){m+1,-1});
	for(int i=m;i;i--){
		while(st.top().data>=a[i])st.pop();
		int npl=st.top().pl;
		check(ans,(ll)(npl-pl[i]-1)*a[i]);
		st.push((node){i,a[i]});
	}
	printf("%lld",ans);
	
	return 0;
}