22.1.16

59 阅读 0 评论 39 点赞

我是靠谱客的博主俭朴灰狼，最近开发中收集的这篇文章主要介绍22.1.16，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一.Acwing算法学习

1.双指针算法；双指针算法可以用来优化时间复杂度，将O（n^2）降为O（n）；

eg1:最长不连续字串

#include <iostream>

using namespace std;

const int N = 100010;

int n;
int q[N], s[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    int res = 0;
    for (int i = 0, j = 0; i < n; i ++ )
    {
        s[q[i]] ++ ;
        while (j < i && s[q[i]] > 1) s[q[j ++ ]] -- ;//遇到重复的，将之前的记录清除，并且将j移动到i左边；
        res = max(res, i - j + 1);
    }

    cout << res << endl;

    return 0;
}

eg2：数组元素的目标和，从这个题对双指针算法的重要特性—单调性有了基础认识；

a和b数组都是严格上升的，具有单调性；

#include <iostream>

using namespace std;

const int N = 100010;

int n,m,x;
int a[N],b[N];

int main()
{
	cin>>n>>m>>x;
	for(int i=0;i<n;i++)scanf("%d",&a[i]);
	for(int i=0;i<m;i++)scanf("%d",&b[i]);
	
	for(int i=0,j=m-1;i<n;i++)
	{
		while(j>=0&&a[i]+b[j]>x)j--;
		if(a[i]+b[j]==x)
		{
			cout<<i<<" "<<j;
			exit(0);
		}
	}
    return 0;
}

2.位运算

常用的两个操作

1.n>>k&1

2.lowbit:返回二进制中的最后一个1；x&-x 等同于x&(~x+1);

(1条消息) 位运算操作(超详细)_zju_cbw的博客-CSDN博客_位运算操作https://blog.csdn.net/weixin_44491423/article/details/108186191?ops_request_misc=&request_id=&biz_id=102&utm_term=%E4%BD%8D%E8%BF%90%E7%AE%97%E7%9A%84%E4%B8%A4%E4%B8%AA%E6%93%8D%E4%BD%9C&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-0-108186191.first_rank_v2_pc_rank_v29&spm=1018.2226.3001.4187y总的话，又get到了新知识：

1.使用万能头文件不会影响运行速度，只是会略微增加编译时间。考试的时候编译时间不会被计算在运行时间里，只是在debug的时候每次编译都会慢一点，如果不care这一点的话那使用万能头文件会方便一些~
2.使用bitset统计1的个数相当于杀鸡用牛刀，速度会稍慢一些。

#include <iostream>

using namespace std;

const int N = 100010;
int lowbit(int x){
	return x&-x;
}
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		int x,res=0;
		cin>>x;
		while(x)x-=lowbit(x),res++;//使用lowbit操作，进行，每次lowbit操作截取一个数字最后一个1后面的所有位，每次减去lowbit得到的数字，直到数字减到0，就得到了最终1的个数，
		cout<<res<<' ';
	}
	
   return 0;
}

打cf查漏到的：

1.如何将ascii码上对应的数字转化为相应的字符：用printf("%c",i)；i是数字；

2.C.Monsters And Spells

我想的就是从后面开始用双指针，因为它需要从前往后进行“蓄力”才能达到杀死挂物的伤害，并且因为hi<=ki，所以越在后边，才能出现更大的数据；

#include <bits/stdc++.h>

using namespace std;

int k[110];
int h[110];
int qiuhe(int x)
{
	int s=0;
	for(int i=1;i<=x;i++)s+=i;
	return s;
}
void solve()
{
	int n,maxx=0,f=0,sum=0;
	cin>>n;
	memset(k,0,sizeof k);
	memset(h,0,sizeof h);
	for(int i=0;i<n;i++)scanf("%d",&k[i]);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&h[i]);	
	}
	int i=n-1,j=n-2;

			while(i>=0)
	{
		if(k[i]-k[j]<h[i]-h[j])
		{
			j--;
		}
		else{
			sum+=qiuhe(h[i]);
			i=j;
			j--;
			
		}
	}
		cout<<sum<<endl;	
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	
   return 0;
}