原SDAU暑假训练第13天做题(2018811)

原SDAU暑假训练第13天做题(2018811)

上午做了大概三个题,挑软柿子捏的,难的不会还是不会,题解的证明也是似懂非懂。下午HDU莫名其妙的关了,没法做题,就看了看算法进阶那本书的数学部分(之前学数学的时候还没买这本书)

然后,感觉613太冷了,晚上就出去溜达去了,路上跟我爸进行了一些心理学方面算是学术性的瞎扯淡,我俩还真是一扯问题就来劲了,幸福。

回宿舍之后和段大佬谈人生,收获相当大,感谢大佬的指点。

看电影去了,看完再睡

原【模拟】NewBuildingforSIS

原【模拟】NewBuildingforSIS


题意:给你n个相邻的建筑(从左到右编号1到n),每个建筑有h层,每个建筑的a层到b层中任意一层c层可以花一秒通过连廊直接到隔壁建筑的c层。上下楼1层需要1秒。求q次查询(建筑a,层a)到(建筑b,层b)的最短时间。


#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int main()
{
	int n,h,a,b,k;
    scanf("%d%d%d%d%d",&n,&h,&a,&b,&k);
    while(k--)
    {
        int ta,fa,tb,fb;long long ans=0;
        scanf("%d%d%d%d",&ta,&fa,&tb,&fb);
        if(ta==tb)
            ans+=abs(fb-fa);//同楼层
        if(ta!=tb)
        {
            ans+=abs(tb-ta);//计算横向移动时间
            if(fa>=a&&fa<=b)
            {
                ans+=abs(fb-fa);//如果都处于连廊直接通过的楼层,附加纵向距离
            }
            else
            {
				int temp1=0,temp2=0;
                temp1+=abs(fa-a);//temp1代表如果从最下层连廊走
                temp1+=abs(fb-a);
                temp2+=abs(fa-b);//temp1代表如果从最上层连廊走
                temp2+=abs(fb-b);
				ans+=min(temp1,temp2);//取最短距离
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

 

原【字符串】SegmentOccurrences

原【字符串】SegmentOccurrences

Codeforces Round 48 (Rated for Div. 2)


大意:输入字符串s和t、各自的长度和q个询问,询问由第l到r个字母构成的s的子串中,包含t的个数


一开始的傻屌代码,TLE上天了

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
int n,m,w,sum=0;
string s,t;
int main()
{
	int n,m,q;
	scanf("%d%d%d",&n,&m,&q);//s长度,n长度,q次数
	s.resize(1200);
	t.resize(1200);
	scanf("%s%s",&s[0],&t[0]);//s串,t串
	int l,r,ans=0;
	while(q--)
	{
		ans=0;
		scanf("%d%d",&l,&r);
		if(r-l+1>=m) 
		{
			for(int i=l-1;i+m-1<r;i++)
			{
				string temp=s.substr(i,m);
				if(s.substr(i,m)==t.substr(0,m)) ans++;
			}
		}
		printf("%d\n",ans);

	}
}

后来采用了类似打表的思想过了。

#include<iostream>
#include<cstdio>
#include<string>
using namespace std; 
int a[1200];
int main()
{
    int n,m,k,q,l,r,ans;
    string s,t;
    cin>>n>>m>>q;
    cin>>s>>t;
    for(int i=0; i<=n-m; i++)
        if(s.substr(i,m)==t)
            a[i]=1;
    while(q--)
    {
        ans=0;
        cin>>r>>l;
        for(int i=r-1; i<=l-m; i++)
            if(a[i])
                ans++;
        cout<<ans<<endl;
    }
    return 0;
}
 

别人家的题解:

用find的:

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int n,m,q,i,j,l,r,len;
    int counts;
    int vis[10010];
    string s1,s2;
    cin>>n>>m>>q;
    cin>>s1>>s2;
    len=s2.size();
    memset(vis,0,sizeof(vis));
    string::size_type pos=0;
    while((pos=s1.find(s2,pos))!=string::npos)
    {
        vis[pos+1]=pos+1;
        pos++;
    }
    for(i=1;i<=q;i++)
    {
        counts=0;
        scanf("%d%d",&l,&r);
        for(j=l;j<=r;j++)
        {
            if(vis[j]!=0&&vis[j]+len-1<=r)
            {
               counts++;
            }
        }
        printf("%d\n",counts);
    }
    return 0;
}

还有前缀数组的大佬:

#include <bits/stdc++.h>
using namespace std;
int n,m,q;
string s,t;
int l,r;
int hay[10000],shay[10000];
int main()
{
    cin>>n>>m>>q;
    cin>>s>>t;
    s=" "+s;
    t=" "+t;
    for(int i=1;i<=n-m+1;i++)
    {
        hay[i]=1;
        for(int j=0;j<m;j++)
        {
            if(s[i+j]!=t[1+j])
            {
                hay[i]=0;
                break;
            }
        }
        shay[i]=shay[i-1]+hay[i];
    }

    while(q--)
    {
        cin>>l>>r;
        r=r-m+1;
        if(r<l) cout<<"0"<<endl;
        else cout<<shay[r]-shay[l-1]<<endl;
    }
    return 0;
}

 

原SDAU暑假训练第15天做题(2018813)

原SDAU暑假训练第15天做题(2018813)

上午做了几个题,做起来有困难,一个题改好多次,可能还是不够熟练吧。

下午打了场比赛,比赛题变难了(据说选自DIV2)

待会选几个题把题解发上来吧,虽然好多网上都有,但是下午的收获还是蛮大的,也是见识到了什么叫完全不同的思路能做同一道题。

晚上偏头疼的老毛病又犯了,一晚上头昏脑胀的,索性没学习趴着睡觉去了,说不定以后加长锻炼时间会好点?

明天继续加油。

原SDAU暑假训练第14天第二周休息日(2018812)

原SDAU暑假训练第14天第二周休息日(2018812)

这一周的基本上在看博客,做题。

题目大部分还是得靠题解开思路,不够好

前三天效率还行,后三天精力就不够集中了

犯了一个致命错误,练习2布置了一直以为是DP的内容早布置了(因为第一题读了好像就是DP),结果刷题刷的有点少。

总之,对一周的状态不够满意,明天起床之后新的一周好好整!!

 

SDAU训练日志第一篇排序算法(上)(2018年1月29日)

SDAU训练日志第一篇排序算法(上)(2018年1月29日)

引例:

         经过了在山东农业大学一学期的学习,我们迎来了耿霞老师开设C++程序设计课程的期末考试,在程序设计题的第一题给我们出了一道这样的题:

((✺ω✺))给你一组数据(1<n<1000),数据中可能有重复,你的任务是完成去重,并按照从小到大顺序输出数据。(NOIP2006)

考试的时候拿到这个题有两个思路:

1.先去重再排序输出   2. 先排序再去重输出(重复的都在一起)

对于第一种思路,我们可以假设有很多桶,然后我们挨着枚举数据,把数据扔进带有编号的桶中,标记该桶,枚举完成后将带有标记的桶的编号进行输出。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000;
int main()
{
	bool flag[MAXN+1];
	//因为数组下标是少1的,我们多加一个元素表示maxn
	memset(flag,0,sizeof(flag));
	//初始化该桶
	int n=0,temp=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>temp;
		flag[temp]=true;
		//标记该桶
	}
	for(int i=1;i<=1000;i++)
		if(flag[i])
			cout<<i<<' ';
	return 0;
}

对于第二种思路:

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int shuzu[101];
	memset(shuzu,0,sizeof(shuzu));
	int n=0;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>shuzu[i];
	sort(shuzu,shuzu+n);
	cout<<shuzu[0]<<' ';
	for(int i=1;i<n;i++)
	{
		if(shuzu[i]!=shuzu[i-1])//不重复就输出
			cout<<shuzu[i]<<' ';
	}
	return 0;
}

由第一种方法的代码稍加修改可以引出今天学习的第一种排序:简化版的桶排序

#include<iostream>
using namespace std;
const int MAXN=1000;
int main()
{
	int flag[MAXN+1];
	//因为数组下标是少1的,我们多加一个元素表示maxn
	memset(flag,0,sizeof(flag));
	//初始化该桶
	int n=0,temp=0;
	cin>>n;
	for(int i=1;i<=MAXN;i++)
	{
		cin>>temp;
		flag[temp]++;
	}
	for(int i=1;i<=MAXN;i++)
		for(int j=1;j<=flag[i];j++)//划重点
			cout<<i<<' ';
	return 0;
}

简化版桶排序的时间复杂度只有O(M+N),可以看出是一种很快的排序方法,然而却是不完美的,在应用过程中主要有以下几大问题:

  1. 只能对整数进行排序
  2. 以空间的方式纵使降低了时间复杂度,然而空间的浪费问题严重
  3. 无法处理有复杂要求的排序问题

对于第一个问题,别的排序算法能解决这个问题,就不多写了。谈一下第一个问题,假设要对五个数排序,每个数的范围在1-1亿之间,那么且不说系统会不会给你一个1亿大小的数组,为了五个数这样太浪费空间了,也不可行,还是需要别的排序方法(文末会总结各个排序方法的适用情况)。第三个问题:如果每个数据都带着名称,在排序的时候无法同时对别的关联项进行排序。

针对第三个问题,我又学习了冒泡排序和选择排序,再加上结构体关联名称和数据,轻松解决第三个问题;

来聊一聊冒泡排序:

算法思想很简单就不码字了,直接上代码

基本版的冒泡排序:

void bubble_sort(int arr[], int len) {  
    int i, j;  
    for (i = 0; i < len - 1; i++)  
        for (j = 0; j < len - 1 - i; j++)  
            if (arr[j] > arr[j + 1])  
                swap(arr[j], arr[j + 1]);  
}  

冒泡的时间复杂度高达O(n^2),排序速度慢,我们进行如下升级

第一次升级:设立了结束标志的冒泡:

void bubble_sort(int arr[], int len) {  
    int i, j;  
    bool flag;
    for (i = 0; i < len - 1 && flag!=0; i++)  
        {  
                flag=0;  
        for (j = 0; j < len - 1 - i; j++)  
            if (arr[j] > arr[j + 1])  
                        {  
                swap(arr[j], arr[j + 1]);  
                                flag = 1;  
                         }  
        }  
}  

变量flag用于记录每趟冒泡排序是否发生数据元素位置交换。如果没有发生交换,说明序列已经有序了,结束冒泡。

第二次升级:鸡尾酒排序(本段源引自郭威gowill博客)

        鸡尾酒排序又叫定向冒泡排序,搅拌排序、来回排序等,是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。

鸡尾酒排序在于排序过程是先从低到高,然后从高到低;而冒泡排序则仅从低到高去比较序列里的每个元素。它可以得到比冒泡排序稍微好一点的效能,原因是冒泡排序只从一个方向进行比对(由低到高),每次循环只移动一个项目。

以序列(2,3,4,5,1)为例,鸡尾酒排序只需要从低到高,然后从高到低就可以完成排序,但如果使用冒泡排序则需要四次。

但是在乱数序列的状态下,鸡尾酒排序与冒泡排序的效率都很差劲。

void cocktail_sort(int arr[], int len) {  
    int j, left = 0, right = len - 1;  
    while (left < right) {  
        for (j = left; j < right; j++)  
            if (arr[j] > arr[j + 1])  
                swap(arr[j], arr[j + 1]);  
        right--;  
        for (j = right; j > left; j--)  
            if (arr[j - 1] > arr[j])  
                swap(arr[j - 1], arr[j]);  
        left++;  
    }  
}  

还有选择排序:

void SelectSort(int arr[],int n)
{
    for(int i = 0; i <n - 2; ++i)
    {
        int k = i;
        for(int j = i + 1; j < n - 1; ++j)
        {
            //找到最小的数的下标
            if(v[j] < v[k])
                k = j;
        }
        if(k != i)
        {
            swap(v[k],v[i]);
        }
    }
}

选择排序进化!:双极端的选择排序

在每一次查找最小值的时候,也可以找到一个最大值,然后将两者分别放在它们应该出现的位置,这样遍历的次数就会少一半!

void SelectSort(int arr[],int n)
{
    int left = 0;
    int right = n - 1;
    int min = left;//用来存储最小值的下标
    int max = left;//用来存储最大值的下标
    while(left <= right)
    {
        min = left;
        max = left;
        for(int i = left; i <= right; i++)
        {
            if(arr[i]<arr[min])
                min = i;
            if(arr[i] > arr[max])
                max = i;
        }
        swap(arr[left],arr[min]);
        if(left == max)
            max = min;
        swap(arr[right],arr[max]);
		left++,right++;
    }
}

今天第一次写训练日志,就先写到这吧,剩下的几种排序算法明天再写,

总结一下:

今天学习了简化版桶排序,冒泡排序、选择排序及各自的升级版本,还有插入排序和快速排序(这两个明天写吧)

  • 桶排序,以空间换时间,对于处理取值范围小的领域占优势(比如学生成绩),但处理取值大的数据或者有较复杂要求的排序题就弱鸡了,限制较高
  • 选择和冒泡,占用空间比桶排序要小,可是时间复杂度超级高,当排序数据量高的时候会慢出翔。

有没有能对不同类的问题有着更好的适应性能并且能保证排序的速度呢?

且听下回分解:排序算法(下)


注:本人第一次写博客,难免会有错误,希望能在评论指出!十分感谢