[数据结构与算法]一周中较有趣的题目

南昌理工集训队

1.AcWing 154.滑动窗口

（1）题目描述：


（2）解法：单调队列

（3）代码+注释:

#include<iostream>
using namespace std;
int n,k,a[1000010],q[1000010];//q存下标 
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	int hh=0,tt=-1;//初始化队头、队尾 
	for(int i=0;i<n;i++)
	{
		//处理出窗队头 
		if(hh<=tt&&i-k+1>q[hh])
		{
			hh++;
		}
		//维持单调队列 
		while(hh<=tt&&a[q[tt]]>=a[i])
		{
			tt--;
		}
		q[++tt]=i;//将元素下标放入队列中
		//从前k个数输出,不足不输出 
		if(i>=k-1)
		{
			printf("%d ",a[q[hh]]);
		}
	}
	puts("");
	hh=0,tt=-1;// 
	for(int i=0;i<n;i++)
	{
		if(hh<=tt&&i-k+1>q[hh])
		{
			hh++;
		}
		while(hh<=tt&&a[q[tt]]<=a[i])
		{
			tt--;
		}
		q[++tt]=i;
		if(i>=k-1)
		{
			printf("%d ",a[q[hh]]);
		}
	}
	puts("");
	return 0;
}

2.Trie

（1）.含义：高效的存储和查找字符串集合的数据结构。
（2）.类似一棵树
1.题目1:AcWing 835 Trie字符串统计
(1)题目描述:

(2)代码+注释:

#include<iostream>
using namespace std;
const int N=100010;
int son[N][26],cnt[N],idx,n;
char s[N];
void insert(char *s)
{
	int p=0;
	for(int i=0;s[i];i++)
	{
		int u=s[i]-'a';//映射 
		//创建结点 
		if(!son[p][u])
		{
			son[p][u]=++idx;
		}
		p=son[p][u];//下一结点的位置 
	}
	cnt[p]++;//标记并记录次数 
}
int query(char *s)
{
	int p=0;
	for(int i=0;s[i];i++)
	{
		int u=s[i]-'a';
		//没有找到 
		if(!son[p][u])
		{
			return 0;
		}
		p=son[p][u];
	}
	return cnt[p];
}
int main()
{
	scanf("%d",&n);
	while(n--)
	{
		char op[2];
		scanf("%s%s",op,s);
		if(*op=='I')
		{
			insert(s);
		}
		else 
		{
			printf("%d\n",query(s));
		}
	}
	return 0;
}

2.题目2：AcWing 143. 最大异或对

（1）题目描述:

(2)代码+注释

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010,M=3100010;
int n,son[M][2],a[N],idx,ans;
//创建Trie
void insert(int x)
{
	int p=0;
	for(int i=31;i>=0;i--)
	{
		int t=x>>i&1;//每一位二进制上的值 
		if(!son[p][t])
		{
			son[p][t]=++idx;
		}
		p=son[p][t];
	}
}
//查找 
int query(int x)
{
	int p=0,res=0;
	for(int i=31;i>=0;i--)
	{
		int t=x>>i&1;
		//最优:相反(1^0=1) 
		if(son[p][!t]) 
		{
			p=son[p][!t];
			res=res*2+!t;
		}
		else
		{
			p=son[p][t];
			res=res*2+t;
		}
	}
	return res;
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=0;i<n;i++)
	{
		insert(a[i]);
		int tt=query(a[i]);
		ans=max(ans,a[i]^tt);
	}
	printf("%d\n",ans);
	return 0;
}

3.AcWing 839. 模拟堆

(1).题目描述:

(2)代码+注释

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int N=100010;
//hp[x]:堆中某个点x，是第几个插入
//ph[k]:第k个插入的点,在堆中的下标 
int h[N],hp[N],ph[N],cnt,m,n;
void heap_swap(int a,int b)
{
	swap(h[a],h[b]);//顺序不影响 
	swap(hp[a],hp[b]);
	swap(ph[hp[a]],ph[hp[b]]);
}
void up(int u)
{
	while(u/2>0&&h[u]<h[u/2])
	{
		heap_swap(u,u/2);
		u/=2;
	}
}
void down(int u)
{
	int t=u;//用来记录最的小点
	if(u*2<=cnt&&h[u*2]<h[t])
	{
		t=u*2;
	}
	if(u*2+1<=cnt&&h[u*2+1]<h[t])
	{
		t=u*2+1;
	}
	if(t!=u)
	{
		heap_swap(u,t);
		down(t);
	}
}
int main()
{
	scanf("%d",&n);
	while(n--)
	{
		char op[3];
		scanf("%s",&op);
		int k,x;
		if(!strcmp(op,"I"))
		{
			scanf("%d",&x);
			cnt++;
			m++;
			h[cnt]=x;
			hp[cnt]=m,ph[m]=cnt;
			up(cnt);
		}
		else if(!strcmp(op,"PM"))
		{
			printf("%d\n",h[1]);
		}
		else if(!strcmp(op,"DM"))
		{
			heap_swap(1,cnt);
			cnt--;
			down(1);
		}
		else if(!strcmp(op,"D"))
		{
			scanf("%d",&k);
			k=ph[k];//注意 
			heap_swap(k,cnt);//执行后ph[k]会变 
			cnt--;
			up(k),down(k);//只会执行其中一个 
		}
		else
		{
			scanf("%d%d",&k,&x);
			h[ph[k]]=x;
			up(ph[k]),down(ph[k]);
		}
	}
	return 0;
}

如有错误,欢迎指出。