本文共 3064 字，大约阅读时间需要 10 分钟。

思维

• 题意
  序列a【1】—a【n】，初始值只为0或1，有q次操作
  定义两种操作为：
  1、输入x，将a【x】变为1-a【x】。
  2、输入k，要求输出当前序列中第k大的元素。

• 思路
  执行操作1时只会让0变成1，1变成0，
  而整个序列中只有0和1，查询时只需要判断当前序列中1的个数和k的数量关系，
  操作1下计数序列中当前1的数量，操作2下判断即可。

• 代码

void solve(){   	cin>>n>>q;	int cnt=0;	for(int i=1;i<=n;i++)	{   		cin>>a[i];		if(a[i])	cnt++;	}	int ob,x,k;	while(q--)	{   		cin>>ob;		if(ob==1)		{   			cin>>x;			if(a[x])	cnt--;			else		cnt++;			a[x]=1-a[x];		}		else		{   			cin>>k;			if(k<=cnt)	cout<<1<

思维

• 题意
  指定图的大小为n行，1e6+1列，有n个障碍物，分别在（i，a【i】）位置上，
  上下移动障碍物消耗u，左右移动障碍物消耗v。
  问：移动障碍物，让图中存在一条从左上角（1,0）到右下角（n,1e6）的路径，最小的消耗是多少？

• 思路
  题意可知，每行都有且只有一个障碍物，障碍物的数量上限为100，远小于列数（1e6+1），那么图的初始情况有以下几种：
  ①、已存在左上角到右下角的路径，即相邻两行的障碍物所在列差值大于1，无需操作，答案为0。
  ②、所有障碍物都在一列上，此时答案即为min（u+v，2*v）。
  ③、不存在已有路径且障碍物不全在一列上，构造出第一种情况即可，则答案为min（u，v）。

• 代码

void solve(){   	cin>>n>>X>>Y;	bool nl=0,fl=0;	for(int i=1;i<=n;i++)	{   		cin>>a[i];		if(i>1)		{   			if(a[i]!=a[i-1]) 		nl=1;//不是一竖排 			if(abs(a[i]-a[i-1])>=2)	fl=1;//已存在路径 		}	}	if(fl)		cout<<0<

暴力 差分

• 题意
  n个点，每个点的初值为a【i】，每次可随意选择一个点起跳，并跳跃至min（n，i+a【i】）。
  每个点被跳过一次后值会减少，一直减至1为止。
  问：将所有点的值都变为1的前提下，最少的起跳（任意一个点开始，直至不能往后继续跳为止）次数是是多少？

• 思路
  毫无疑问，最优方法为：每次都贪心地，在从左往右的第一个值不为1的点起跳。
  显然可知，每个点 i 在处理过程中，直至其变为1前，必会将后续的【i+2，i+a【i】】每个点的值都减少一次。
  存储每个点 i 被它所有前置的点【1，i-1】，在他们处理至1的过程中一共被跳到的次数，
  关键操作：若当前点的被前置点跳到的次数超过a【i】上限，将多余次数向后传递。

• 代码

void solve(){   	cin>>n;	for(int i=1;i<=n;i++)		cin>>a[i],b[i]=0;//bi表示i点被跳过的次数 		ll ans=0;	for(int i=1;i<=n;i++)	{   		ans += max(a[i]-1-b[i],1LL*0);				for(int j=i+2;j<=min(i+a[i],n);j++)// 			b[j]++;				b[i+1] += max(b[i]-a[i]+1,1LL*0);//当前点多跳的次数往后传递 	}	cout<
   
    <<'\n';}
   

数论 规律

• 题意
  输入u，v询问，输出u是否可到达v。
  现定义 有向边是否存在 为：若a&b==b，则存在一条 a=>(a+b) 的有向边。
  对于整个图，若u可通过任意条有向边到达v，则u是可到达v的。

• 思路
  数据范围2^30，可推测与进制上的规律有关，那么，
  通过对按位与（&）的定义和题目有向边的定义，多次模拟推导规律可知：
  每次都可以将u的二进制上的1向左移或将相邻的1替换成1个1，第0位补0，
  即我们可以将u末尾的1任意左移或消去
  当从二进制末尾到高位时，任意位置u包含1的个数> = v包含1的个数，可以到达v

• 代码

void solve(){   	cin>>a>>b;	if(a>b)		Cno	if(a==b)	Cyes		mem(A,0),mem(B,0);	int ca=0,cb=0;	while(a)	{   		A[ca++] = a&1;		a>>=1;	}	while(b)	{   		B[cb++] = b&1;		b>>=1;	}	for(int i=0;i<=30;i++)	{   		A[i]+=A[i-1];		B[i]+=B[i-1];		if(A[i]

二分 搜索 递归

• 题意
  n个点，输入n-1条边，构成一棵树。
  Fib-tree的定义为：
  1、原树的总节点个数是斐波那契数，
  2、可任意选择一条边断开，断开的两个子树也都是Fib-tree。

• 思路
  不是常规的二分方法，但是本质是个二分题, 每次将一棵树尝试分成两棵Fbi树 直到当前这棵树只有一个节点。
  关键是怎么二分的问题, 二分一棵树, 就是找这棵树的一条边把这颗树分成两部分, 递归 判断这两棵子树是不是Fbi树。
  然后就是怎么枚举边, 这个就很巧了, 通过dfs枚举当前这棵树的边, 本来dfs就是枚举边和点的, 一边枚举, 一边二分树。

• 代码

#include
   
    using namespace std;const int N=200005;int n,fb[N];int sz[N],fa[N],m;set
    
     e[N];void sol(int u,int f,int l)//当前节点-父节点-斐波那契序号 {   	//递归给每个节点赋值父节点,并将子节点权值向上传递 	sz[u]=1,fa[u]=f;	for(auto v:e[u]) 	{   		if(v==f) continue;		sol(v,u,l);		sz[u]+=sz[v];	}	// 	if(sz[u]==fb[l])	m=u;}int dfs(int u,int l)//当前节点-斐波那契序号 {   	if(l<=2) return 1;	// 	m=0;	sol(u,0,l-1);	if(m)	{   		int x=fa[m];		e[m].erase(x);		e[x].erase(m);		int a1=dfs(m,l-1),a2=dfs(x,l-2);		return a1&&a2;	}	//	m=0;	sol(u,0,l-2);	if(m)	{   		int x=fa[m];		e[m].erase(x);		e[x].erase(m);		int a1=dfs(m,l-2),a2=dfs(x,l-1);		return a1&&a2;	}	return 0;}int main(){   	//打表 	fb[1]=fb[2]=1;	for(int i=3;i<=27;i++)		fb[i]=fb[i-1]+fb[i-2];	//set存图		scanf("%d",&n);	for(int i=1;i
    
   

转载地址：http://dkwzz.baihongyu.com/