Void Space

发表于 更新于 分类于

进制数枚举

进制字符串输出总值

int get(string a, int b) {
    int res = 0;
    for (auto c : a)
        res = res * b + c - '0';
    return res;
}

b为进制，a为包含进制的字符串

更改n进制的位枚举

二进制

c ^= 1;
S.insert(get(a, 2));
c ^= 1;

n进制处理

for (auto& c : b) {
    int t = c;
    for (int i = 0; i < 3; i ++ ) {
        if (i + '0' != t) {
            c = i + '0';
            int x = get(b, 3);
            if (S.count(x)) {
                cout << x << endl;
                return 0;
            }
        }
    }
    c = t;
}

将3更改为需要的位数

发表于 更新于 分类于

题目 字符串哈希

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\) 面积

  • 缺点？

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

阅读全文 »
0%