[Java知识库]周末总结2

KMP算法

P2375动物园
题目大意：（动物园是个不错的地方）
“KMP算法只能求出next数组。我现在希望求出一个更强大num数组一一对于字符串S的前i个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作num[i]”
输入：
3
aaaaa
ab
abcababc
输出：
36
1
32
分析：
KMP假期有学但现在像是学了另一个KMP，发现next[]不同的地方存的数据含义也不同，数据结构存公共前后缀的长度，有人存公共前后缀相同的字符个数，可能根据需要来吧。

int getnext(char ch[],int length,int next[])
{
    next[1]=0;
    int i=1,j=0;
    while(j<length)
    {
        if(j==0||ch[i]==ch[j]) next[++i]=++j;
        else j=next[j];
    }
}

手算KMP：(存公共前后缀相同的字符个数的版本，而该题不是)
----->j: 1 2 3 4 5 6 7 8
---->p: a b a a b c a c
next[j]: 0 0 1 2 2 3 1 2
next[j]:第j位字符前j-1位字符组成的子串的前后缀重合字符数+1
当j=1,规定next[1]=0;
当j=2,j前子串位=为“a”,next[2]=1;
当j=3,j前子串位=为“ab”,next[3]=1;
当j=4,j前子串位=为“aba”,next[4]=2;
当j=5,j前子串位=为“abaa”,next[5]=2;
当j=6,j前子串位=为“abaab”,next[6]=3;
当j=7,j前子串位=为“abaabc”,next[7]=1;
当j=8,j前子串位=为“abaabca”,next[8]=2;

以上是KMP知识
继续分析：
这个题并不是只让你求next[]数组，更高级啦，需要去除重叠的前后缀，并计算非重叠前后缀的数量。怎么去除重叠？答：只要让公共前缀长度不超过子串的一半即可。只要 jx2>i 就向前查找next【next【next【j】】】可以无限套娃寻找，直到 jx2<=i，就成功啦

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
const int maxn=1000010;
const int mod=1e9+7;
int n,T;
int ne[maxn],num[maxn];
long long ans;
char s[maxn];
void getnext()
{
    for(int i=2,j=0;i<=n;i++)
    {
        while(j&&s[i]!=s[j+1]) j=ne[j];//j！=0并且不等于
        if(s[i]==s[j+1]) j++;
        ne[i]=j;
        num[i]=num[j]+1;
    }
}
void getnum()
{
    for(int i=2,j=0;i<=n;i++)//这里会用到next的之前存储的数据的虽然没有nexti的出现但就是nextj的地位
    {
        while(j&&s[i]!=s[j+1]) j=ne[j];
        if(s[i]==s[j+1]) j++;
        while((j<<1)>i) j=ne[j];
        ans=(ans*(long long)(num[j]+1))%mod;//这里不要不懂，看题目输出要求！
    }
}
int main()
{
    cin>>T;
    while(T--)
    {
        ans=1;
        num[1]=1;
        cin>>s+1;//下标从1开始
        n=strlen(s+1);
        getnext();
        getnum();
        cout<<ans<<endl;
    }
    return 0;
}

P3435

题目大意：求给定字符串所有前缀的最大周期长度之和。
输入：
8
babababa
输出：
24
分析：
所有前缀中最大周期的长度之和，关键是每个前缀的最大周期长度；
我们要找最大周期的子串长度，abcabcab，最大周期子串应该是abcabc长度为6，就是让其公共前后缀尽可能的短一点，这样就能保证子串较长，周期也就越长。这里我说的可能不是很明白，看例子：
babababa，假设下标从1开始，一般next[8]=6,next[6]=4,next[4]=2;
next[8]=6意思是，1-6和2-8是匹配的，但我们选择最短匹配，套娃找到next[8]=2，就是我们要找的答案：8-next[8]=6;

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
const int maxn=1000010;
int ne[maxn],num[maxn];
long long ans;
char s[maxn];
int n;
//假设起初next[8]=6;next[6]=2;next[2]=0;
int main()
{
    cin>>n;
    cin>>s+1;
    for(int i=2,j=0; i<=n; i++)
    {
        while(j&&s[i]!=s[j+1]) j=ne[j];//j！=0并且不等于
        if(s[i]==s[j+1]) j++;
        ne[i]=j;
        //num[i]=num[j]+1;
    }//求解kmp数组
    for(int i=2,j=2; i<=n; i++,j=i)
    {
        while(ne[j]!=0)//直到为零前一个
        {
            j=ne[j];//递推找到最短的匹配长度next[8]=2;
        }
        if(ne[i]!=0) ne[i]=j;//存储最短匹配长度的元素下标2
        ans+=i-j;//8-2
    }
    cout<<ans<<endl;
    return 0;
}

基础算法

P1483

题目大意：
两种操作第一种是输入三位数 1，x，y,将所有的 a(kx) (k*x<=n,k为正整数) 都加上y。
第二种操作是输入两位数2，j进行输出操作，输出a(j)
输入：
5 4
6 9 9 8 1
2 4
1 2 5
1 3 1
2 4
输出：
8
13
分析：
第一遍超时啦，直接遍历查找遍历相加，如果输入的操作有很多的话一定会超时，因为每一次操作又要来一次大的循环。发现操作二的输出操作只有10000,那我们不防从输出的 j 出发，找到j的约数，有多少约数是x就会相加多少个y。
code:使用到两个数组存方便许多，容易看懂

#include <iostream>
#include <cmath>
using namespace std;
int a[1000010];
int b[1000010];
int n,m;
//我也不知道哪里超时啦，直接模拟只有60分
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    while(m--)
    {
        int x;
        cin>>x;
        if(x==1)
        {
            int aa,bb;
            cin>>aa>>bb;
            b[aa]+=bb;

        }else if(x==2)
        {
            int num,c;
            cin>>c;
            num=a[c];
            for(int i=1;i<=sqrt(c);i++)
            {
                if(c%i==0)
                {
                    num+=b[i];
                    if(i!=(c/i)) num+=b[c/i];//考虑两个因数相同时
                }
            }
            cout<<num<<endl;
        }
    }
    return 0;
}

P1323删数问题
题目大意：
（之前也做过类似的题目）一个集合中的元素有规定：1是集合中的元素，若 P 是集合的元素，则 2×P+1，4×P+5 也是集合的元素。取出最小的k个元素，从小到大组成一个多位数，再删除m个数位上的数是剩下的数字最大，编程输出删除前后的多位数。
分析：
题意很简单，题解代码操作很巧妙
继续分析：
首先我想的是排序但是没法实践，直接存不可以这时候就要换思路了，那就找小的值优先存，那也没办法保证大小关系，这时候就要想可自动排序又可弹出最小值的容器了，优先队列！
code:
1优先队列的使用
2.将一个整数存到一个数组中，使得该数每个数位对应数组的一个下标，不是存放在一个空间，用到反向+取余
3.next实现删除操作，存放下一位的坐标，模拟链表

#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#define ll long long
#define H 0x7FFFFFFF
#define ull unsigned long long
using namespace std;

int a[30005],ans[5000010];
int nex[5000010];
int ii,jj;
priority_queue <int,vector<int>,greater<int> >q;//升序队列
//不用初始化，直接用优先队列比较简单
//next数组很高级可以不用删数直接搞定
int main()
{
	int l,m;
	cin>>l>>m;
	q.push(1);
	memset(ans,0x3f,sizeof(ans));//可以避免之后末尾的特判
	while(1)
    {
        int x=q.top(),d=0;
        q.pop();//一定要弹出这个最小的
        //这个地方，因为我们需要最小值存到数组a中，不断地获得最小值所以弹出它保存在x中
        q.push(2*x+1);
        q.push(4*x+5);
        a[++ii]=x;
        while(x)
        {
            d=d*10+x%10;
            x/=10;
        }//反向
        while(d)
        {
            ans[++jj]=d%10;//下标从1开始
            d/=10;
        }//将数字一位位加入ans中
        if(ii>=l) break;//到达限度就停止
    }
    for(int i=1;i<=ii;i++) cout<<a[i];
    cout<<endl;
//很高级的next数组
    for(int i=0;i<jj;i++)
    {
        nex[i]=i+1;
    }//模拟链表记录当前位置的下一位置就不用删数比较了
    while(m)
    {
        int l=0;
        while(ans[nex[l]]>=ans[nex[nex[l]]])
            l=nex[l];//直到出现前比后小
            
        nex[l]=nex[nex[l]];
        m--;//删除的个数
    }
    for(int i=0;nex[i];i=nex[i])//i==jj时next[i]=0最后就没有了数字就不会输出
        cout<<ans[nex[i]];
    cout<<endl;
    return 0;
}

P1381单词背诵
题目大意：
给出n个要背的单词，和文章中m个单词，输出文章中最多要背单词的最短的连续段的长度。
输入：
3
hot
dog
milk
5
hot
dog
dog
milk
hot
输出：
3
3
分析：
这个题还挺难的，思路好理解，利用哈希判断存到队列里的单词的个数，从队头处理如果队头元素，个数不止这一个就把它去掉。在存的过程中flag的作用是判断是否连续，不连续那么ans就会保持最小值。不说啦

#include<bits/stdc++.h>
#define ll long long
#define H 0x7FFFFFFF
#define ull unsigned long long
using namespace std;

const int maxn=1e5+7;
const ll inf=1e9+7;
char s[20];
map<ull,int>mp;
map<ull,int>mp2;
char a[maxn][15];

ull gethash(char *a)//哈希值
{
    ull sum=0;
    for(int i=0;a[i]!='\0';i++)
    {
        sum=sum*131+a[i];
    }
    return sum&H;
}
int main()
{
	ll n,m;
	cin>>n;
	for(int i=1;i<=n;i++)
    {
        cin>>s;
        mp[gethash(s)]=1;//标记
    }
    cin>>m;
    ll num=0;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i];
        ull x=gethash(a[i]);
        if(mp[x]==1)
        {
            num++;//只有等于1才计数，也就是只有个数为1的时候才计数
            mp[x]++;
        }
    }
    cout<<num<<endl;
    
    queue<int>q;
    bool flag=false;
    ll ans=inf;
    for(int i=1;i<=m;i++)
    {
        if(mp[gethash(a[i])]==0)
        {
            mp2[gethash(a[i])]=inf;
        }
        flag=false;
        if(mp2[gethash(a[i])]==0)//存在，这里flag代表只要一个字母没有，就为不连续就改变ans
            flag=true;
        q.push(i);
        mp2[gethash(a[i])]++;//0会变成1
        int k=q.front();//如果开头元素的个数大于1，就去掉该元素
        while(mp2[gethash(a[k])]>1&&q.size())
        {
            mp2[gethash(a[k])]--;
            q.pop();
            k=q.front();
        }
        ll t=q.size();
        if(flag)
        {
            ans=t;
        }
        else{
            ans=min(t,ans);
        }
    }
    cout<<ans<<endl;//最小值因为会有不连续的情况
    return 0;
}

P1183多边形的面积
给出n个顶点的坐标，输出多边形的面积（简单但不会）
输入：
10
。。。
输出：
9
分析：（纯纯数学知识不懂）
用到行列式，二阶三阶行列式，先捺后撇计算。不会就搜索
从三角形对到多边形
坐标逆时针为正，若顺时针还应该加负号

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	double x[n+1],y[n+1];
	for(int i=0;i<n;i++)
    {
        cin>>x[i]>>y[i];
    }
    double ans=0;
    x[n]=x[0];
    y[n]=y[0];
    for(int i=0;i<n;i++)
    {
        ans+=0.5*(x[i]*y[i+1]-x[i+1]*y[i]);
    }
    cout<<ans<<endl;
    return 0;
}

p1124
题目大意：不说了
字符串经过一系列排序，将形成的这些字符串的末尾输出形成一个新的字符串S’
题目给出S’和S首字母在S’中的位置P
输入：
7
xelpame
7
输出：
example
（规律在纸上自己模拟就知道了）其实不用模拟就可以预测到前后字符串之间的对应关系，但是代码实践总会有这样那样的细节，首尾处理呀等等，纸上模拟吧~
这里必须要用倒叙：但是这有一个问题，每次在S中找字符时候，S是无序的，所以找到S中的某个字符时可能并不能接上已经确定的答案字符串。所以在O中找，所以用逆序。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,p;
	cin>>n;
	char o[10005];
	char s[10005];
	for(int i=1;i<=n;i++)
    {
        cin>>o[i];
        s[i]=o[i];
    }
	sort(s+1,s+n+1);
	cin>>p;
	char ans[10005];
	char c=o[p];//e
	bool v[10005]={};
	for(int i=1;i<=n;i++)
    {
        if(c==s[i])
        {
            c=o[i];//x
            v[i]=true;
            break;
        }
    }
    int cnt=0;
    ans[++cnt]=c;//x
	for(int i=n;i>0;i--)//逆序
    {
        if(c==s[i]&&!v[i])
        {
            c=o[i];//重新设置c要搜索的char值 e l p...
            v[i]=true;
            ans[++cnt]=c;//e l p...
            i=n+1;//重新搜索
        }
    }
	for(int i=cnt;i>0;i--)
    {
        cout<<ans[i];
    }
    return 0;
}

P2412查单词
这是个简单题，不分大小写的时候需要转化就是想说
找一个区间最大的，先排序再while查找就是想说

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;
int n,m;
//首先按照小写的字典序
struct Na{
    string c,s;//分别记录原字符串和进行比较的字符串
    int id;//存放序号
}na[50005];

bool cmp(Na x,Na y)
{
    return x.s>y.s;//细节从大到小，要选找最大的
}

int main()
{
    cin>>n>>m;
    string ss;
    for(int i=1;i<=n;i++)
    {
        cin>>ss;
        int l=sizeof(ss);
        na[i].c=ss;
        for(int j=0;j<l;j++)
        {
            if(ss[j]<='Z'&&ss[j]>='A')//大写转小写
                ss[j]=ss[j]-'A'+'a';
        }
        na[i].s=ss;
        na[i].id=i;
    }
    sort(na+1,na+n+1,cmp);
    int x,y;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        int j=1;
        while(1)
        {
            if(na[j].id>=x&&na[j].id<=y) break;
            //因为是从大到小排列所以说只要遇到第一个在这区间的那么就是要输出
            j++;
        }
        cout<<na[j].c<<endl;
    }
   return 0;
}

为什么总结博客有很多代码像是题解的博客呢，因为作者很菜 优秀，感觉这些代码们都很重要~~~