
OJ算法学习记录笔记
热度: loading...
前言
持续记录OJ算法
pipioj
字符串
char s[N],t[N];
int Next[N],n,m;
void getNext(){
int j=0,k=-1; ///初始时,next[0]=-1,用 k 保存 next[j]
Next[j]=-1;
while(j<m-1){ ///注意是根据第 j 位求 j+1 位,所以 j=m-2 时就能求出 m-1 的值了,然后结束循环
if(k==-1||t[j]==t[k])Next[++j]=++k; /// 第 二 种 情 况 t[j]=t[k] 时 ,满 足 下 一 位next[j+1]的定义
else k=Next[k]; ///第三种情况 根据前后两端完全相同的信息 在前一段[0~next[k]]找满足第二种情况的位置 k
}
}
int kmp(){
getNext(); ///求 next 数组
int i=0,j=0,ans=0;
while(i<n){
if(j==-1||s[i]==t[j]){ ///如果当前位匹配 则都++
if(j+1==m){ ///如果 j 已经匹配满了 说明找到了一个答案
//执行相关操作
}
else{ ///正常操作 i++ j++
++i;++j;
}
}
else j=Next[j]; ///失配的情况
}
return ans;
}
例题:1344
字符串HASH
顾名思义,就是将不同字符串映射成不同数字。
单独地把一个串映射成数字而不能获得这个子串的信息,这种映射是低端的。
如果能够将一个字符串HASH的同时方便的调取子串的HASH值,那么很多操作将十分方便。
题目举例:判断回文串(1345)
要判断S[L ~ R]是否为回文串,只需判断S[L ~ R]的HASH值是否与S[R~L]的HASH值相等。
数学专题
欧氏距离
同余定理
给定一个正整数m,如果两个整数a和b满足a-b能够被m整除,即(a-b)/m得到一个整数,那么就称整数a与b对模m同余,记作a≡b(mod m)。
在算法题中应用场景: 比如我们要计算A%B,但是A非常大,我们就不能再简单的直接使用A%B,这样会内存超限---->在这种情况下我们就必须使用同余定理。
举例:假设A=22345
int ans = 0;
ans = (ans*10+2)%p;
ans = (ans*10+2)%p;
ans = (ans*10+3)%p;
ans = (ans*10+4)%p;
ans = (ans*10+5)%p;
//最终得到的ans值便 等同于 22345%p
例题:1103
中位数定理
现在已知数轴上有 n 个点 x1,x2 … xn,如何找到一个点x,使得|x-x1|+|x-x2|+…+|x-xn|的值最小?
答案: 这个点x就是这些数中的中位数
例题:1018
筛法--因子求和
打表法记录数字的因子之和,利用空间换时间
数字N的因子就是所有比N小又能被N整除的所有正整数,如12的因子有1,2,3,4,6.
假设想求数字的因子和
int q[N];
q[1]=1; //1的因子是1
for(int i=1;i<N;i++) //枚举因子
for(int j=i+i;j<N;j+=i) //枚举拥有该因子的数字(自身除外)
q[j]+=i;
例题:1044
筛法--质数素数
const int N = 1e6+5;
bool p[N]; //0代表质数,1代表合数
int q[N]; //质数数组
void init()
{
int id=0;
p[1] = true;
for(int i=2;i<N;i++) //枚举因子
if(!p[i]) //如果是质数
{
q[id++]=i; //添加进数组
for(int j=i+i;j<N;j+=i)p[j]=true; //它的倍数的数全都是合数
}
}
例题:1053
二分法
记得控制精度
例题:1109

DFS与暴力专题
DFS这块没什么值得记录的,重在理解与多做题目。
暴力
题目:最长公共子序列1084
记录这一题是因为真滴难!
分析问题:
给你n个环,要你求出n个环的最长公共子序列。题目意思非常直白且不可做。好像之前学过的知识都失效了,根本没办法解决这个任务。看一眼数据范围,n<=10,环的长度小于8,这么小的数据范围,指数级别的暴力就登场了。
首先我们来看看二进制和子序列的关系。有一个长度为3的字符串”abc”,它的所有子序列为”a”,”b”,”c”,”ab”,”ac”,”bc”,”abc”考虑二进制001,010,011,100,101,110,111。发现了什么规律吗?
也就是说从001111(17的二进制)完美的表示出了abc的所有子序列。那么要枚举出长度为n的字符串的所有子序列,只需要for(int i=1;i<2^n;i++)对于i这个数字的二进制表示,为0的位置不取,为1的位置取。那么现在就解决了枚举子序列的问题。如何保证公共呢?用我们很熟悉的map<string,bool>mp即可,我们对一个个环来提取子序列,只有之前的环出现过的子序列,才是能保证公共,才是合法的。那么之前是否出现过直接mp.count()即可。具体细节,我们在代码里面体现。
- 个人理解:利用二进制来表示子序列,如果字符串长度为len,那么就是从1~2^len-1(代表二进制数的大小)取遍所有子序列。接下来判断这个子序列有没有出现过,出现过的便是公共序列。
#include<bits/stdc++.h>
using namespace std;
unordered_map<string,bool>legal,mp;//legal代表合法序列,mp代表当前序列
unordered_map<string,bool>::iterator it;
string ans; //最终输出的公共子串
int main()
{
int n;
string s;
while(scanf("%d",&n)!=EOF)
{
ans.clear();
for(int i=0;i<n;i++)
{
cin>>s;
string ts;
mp.clear();
int len = s.size(),tp=(1<<len); //tp:2^len
s+=s; //将字符串s视作一个环
for(int l=0;l<len;l++)//枚举起点
{
for(int j=1;j<tp;j++)//枚举1~2^len-1之间的所有二进制数
{
for(int k=0;k<len;k++)//扫描二进制上的每一位
if(j&(1<<k))ts.push_back(s[l+k]); //将这个二进制数对应的字符串序列放进ts
if(i==0||legal.count(ts)==1)mp[ts]=1;
ts.clear();
}
}
if(i==n-1) //如果访问到了最后一个字符串
{
for(it=mp.begin();it!=mp.end();it++)
{
//有最长串便寻找最长串,如果长度相同便寻找字典序最小的串
if(ans.size()<it->first.size())ans=it->first;
else if(ans.size()==it->first.size()&&ans>it->first)ans=it->first;
}
}
else{
//更新合法序列
//比如legal中的合法序列在当前字符串中的子序列中并没有出现,那么它就不再是公共序列了,所以需要删除更新
legal.clear();
for(it=mp.begin();it!=mp.end();it++)legal[it->first]=1;
}
}
if(ans.size())cout<<ans<<endl;
else printf("0\n");
}
return 0;
}

