原SDAU暑假训练第18天做题(2018816)

原SDAU暑假训练第18天做题(2018816)

训练第18天了啊。今天是16号了,还有一周半就结束了。

感觉前面看数学知识好像又开始有遗忘了。看来强扭的瓜不甜,必须深刻理解才行。

队内分工是我搞数据结构,图论,今天有一部分时间看了这个,另外也看了看DP,也是前面训练的全都忘了。

HDU一直关着,很烦。做了几个洛谷的题,挑了几个题解发我新博客上了,点击查看

备注:两个博客大概一周同步一次,新博客上只会挑一些比较精华的东西发过去,是CSDN的子集。CSDN依旧发文章(因为我怕哪天服务器会崩掉)

原SDAU暑假训练第16天做题(2018814)

原SDAU暑假训练第16天做题(2018814)

上午HDU还是上不去没法做题,于是就在那看背包60题。

除了第一题整个人都是懵逼的。

前面已经都忘的差不多了,正式开始攻略DP之前估计要复习一遍基础。

前面练习一和二还有不少题没做完,杭电不让做真的挺烦。

又拖到了很晚才写博客,睡觉,明天继续加油。

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

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

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

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

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

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

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

 

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

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

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

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

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

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

明天继续加油。

原【字符串】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;
}

 

原【模拟】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;
}