Void Space

发表于 更新于 分类于

题目 字符串哈希

https://oi-wiki.org/string/hash/

字符串哈希求数组

表示为

\[hash[i] = (hash[i - 1] * b + ss[i]) \% mod\]

字符串哈希求解子串哈希值

\[ h[r] - (h[l - 1] * bs[r - l + 1]) \% mod + mod) \% mod \]

题目1460. 我在哪？

https://www.acwing.com/problem/content/1462/

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <unordered_map>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f

const ll mod=998244353;
const ll b=133;

char ss[110];
ll h[110];
ll bs[1010];

int main(){
	int n;
	cin>>n;
	cin>>ss;
	bs[0]=1;
	for(int i=1;i<=110;i++){
		bs[i]=bs[i-1]*b;
		bs[i]%=mod;
		// printf("%lld ",bs[i]);
	}
	h[0]=ss[0]-'A'+1;
	for(int i=1;i<n;i++){
		h[i]=h[i-1]*b+ss[i]-'A'+1;
		h[i]%=mod;
		// printf("%lld\n",h[i]);
	}
	// printf("ENS::%d\n",(h[6]-(h[3]*bs[3])%mod+mod)%mod);
	int lside=1,rside=n;
	while(lside!=rside){
		int mid=(lside+rside)>>1;
		unordered_map<int,int> hash;
		bool flag=false;
		for(int l=0,r=l+mid-1; r!=n ; l++,r++){
			ll key=0;
			if(l==0){
				key=h[r];
			}
			else{
				key=(h[r]-h[l-1]*bs[mid]%mod+mod)%mod;
				// cout<<"KEY:::"<<key<<endl;
			}
			if(hash[key]){
				//test:::
				// cout<<"KEY::"<<key<<endl; 
				flag=true;
				break;
			}
			else{
				hash[key]=1;
			}
		}
		if(flag){
			lside=mid+1;
		}
		else{
			rside=mid ;
		}
	}
	cout<<lside<<endl;
	return 0;
}

发表于 更新于 分类于

PHP 8.0 配置

添加源

add-apt-repository -y ppa:ondrej/php

即可添加php8以上的源

安装php和组件

sudo apt install php8.0 php8.0-fpm php8.0-gb php8.0-curl php8.0-mysql

切换php

update-alternatives --config php

For apache2

a2dismod php7.2
a2enmod php8.0
service apache2 restart

测试php

<?php phpinfo(); ?>
<?php
var_dump(curl_version());

发表于 更新于 分类于

数论逆元

欧几里得算法

辗转相除

欧几里得算法的递归实现

int gcd(int a, int b)
{
    return b==0 ? a : gcd(b, a%b);
}
  • 今天的内容和欧几里得算法密切相关——
阅读全文 »

发表于 更新于 分类于

计算几何

导引问题

求三边形面积：

  • 在解析几何里，\(\triangle\text{ABC}\)的面积可以通过如下方法求得：

  • 点坐标 \(\Rightarrow\) 边长 \(\Rightarrow\) 海伦公式 \(\Rightarrow\) 面积

  • 缺点？

  • 计算量大、精度损失，更好的方法？

阅读全文 »

发表于 更新于 分类于

差分约束

最长路径

新问题：如何求最长路径？

1、Dijkstra按最短路的方法直接去求最长路？ 思考：为何不可以？ 思考：转换成负权求最短路？（Dij算法的软肋）

2、常见方案： Floyd算法求每对节点之间的最长路经 （因为最长路径也满足最优子结构性质，而Floyd算法的实质就是动态规划）

阅读全文 »

发表于 更新于 分类于

最短路进阶

回顾

  • 按照最短路径的长度递增的次序，依次求得——源点到其余各点的最短路径！
  • 先求——最短的那条最短路径（特点？）
  • 再求——第二短的最短路径（特点？）
  • ……
  • 依次类推（特点？）
  • ……
  • 最终求出所有的最短路径
阅读全文 »
0%