1 〆℡小短腿走快点ゝ

尚未进行身份认证

我要认证

爱吃扒鸡

等级
TA的排名 12w+

字符串哈希

字符串哈希十进制数1234=1103+2102+3*10+4对于字符串”abcd”我们将它看做p进制的数,那么hash=’a’*p3+’b’*p2+’c’*p+’d’。但是如果字符串足够长的话,long long是存不下的,所以还需要取模。字符串哈希的两个问题1、任意字符不能等0。假设字符a=0,那么对于字符串a和aa的hash值都会等0,就会发生冲突。2、不同的字符串的hash值取模后可能会相等,就是发生冲突了。选择合理的p和mod可以降低冲突的概率,p一般取131、13331或者2333,mod

2020-08-11 09:35:42

树状数组

放一个简单的板子记录一下int tr[N];int a[N];int n; int lowbit(int x){ return x&(-x);} void add(int x,int c) //x的位置+c{ for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c; } int sum(int x)//1~x的和{ int res=0; for(int i=x;i;i-=lowbit(i)) { res+=tr[i];

2020-07-28 10:39:57

博弈论(2)

上篇博客简单的介绍了一些经典的博弈,这篇继续写一些博弈问题。移动棋子游戏这个是一个应用SG函数的板子题.#include <bits/stdc++.h>using namespace std;const int N=2010,M=6010;int n,m,k,a,b,x;vector<int> ve[N];int sg[N];int SG(int u){ if(sg[u]!=-1) return sg[u]; set<int&

2020-05-25 09:54:36

Tarjan算法求强连通分量

dfu[u] 表示遍历到u的时间戳low[u] 从u走,所能遍历到最小的时间戳假如u是其所在的强连通分量的最高点,则dfu[u]==low[u]

2020-05-18 13:58:20

Codeforces Round #634 (Div. 3)

A. Candies and Two Sisters姐姐和妹妹分n颗糖,姐姐必须比妹妹的少,问有几种情况,必须每人至少有一颗//答案:(n-1)/2B. Construct the String有n,a,b,长度是n的字符串,构造一个长度为n的字符串,每a个字符串,都有b个不同字母,输出其中一个。思路:直接按照(i%b+‘a’))构造就行#include <bits/stdc+...

2020-04-14 09:04:50

Codeforces Round #630 (Div. 2)

D. Walk on MatrixD 他的错误dp是因为&过程中的最大值不一定能使后面的&操作最大要使最优解与他输出的差值为k,感觉两个值分别等 k和0是比较好构造吧,所以我的目的是使最优解为k,而dp输出0,假设点[n,m]位置为k,为方便构造减少分支情况就把所有情况都从一个方向来,就令[n-1,m]为0,这个方向一定为0。接下来就是使 dp[n][m-1]&k 等...

2020-04-01 20:15:21

求组合数总结

Educational Codeforces Round 83 (Rated for Div. 2)的D题所用到的Lucas定理,小编看了多篇博文后总结了一下,他其实是求组合数的一种方法,求组合数总共有以下几种方法。1.当数据范围较小时,差不多1000左右,直接用递归打表求,这里用到原理就是从n个球取m个球,相当于(取第n个,然后从前n-1个再取m-1个 + 不取第n个,从前n-1个取m...

2020-03-11 15:29:52

Educational Codeforces Round 83 (Rated for Div. 2)

总体来说菜得很…D题有点思路但是实现不了。。。Two Regular Polygons#include<bits/stdc++.h>using namespace std;typedef long long ll;int t,n,m;int main(){ cin>>t; while(t--) { cin>>n>>m; i...

2020-03-10 20:20:58

矩阵计算器+求线性代数n阶行列式代码

算的实在是心烦,上网找了一篇大佬的代码真的是牛逼,附:大佬博客#include <malloc.h>#include <stdio.h>#include <stdlib.h>//包含的头文件不解释#define bool int //因为标准c里边没有bool类型才这么做#define false 0#define true 1//定义...

2020-03-01 10:02:37

Codeforces Round #622 (Div. 2)

C2. Skyscrapers (hard version)C c1和c2的题意是一样的,只是数据范围不同,已知一个数组m,让你构造一个数组a是的任意ai<=mi,而且任意j<i<k不能有aj>ai<ak(ijk不一定相邻)就是是这个数组是单峰的,在最高点两边是单调下降的。而且数组的和得最大我们需要假设以每个点是最高点来计算这时的数组的和取最大的情况,c1可以直...

2020-02-25 20:07:40

计算机系统概论

唉,文章开头还是感谢那吃蝙蝠的人吧…感谢你让我记个笔记还得记在博客上…1.计算机硬件能直接执行的是:机器语言2.在计算机系统层次结构中,微程序属于硬件3.寄存器的数据位对微程序级用户不是透明4.软件与硬件具有逻辑功能等价性5.计算机的字长与运算精确度有关6.CPU地址线数量与内存容量密切相关7.低层用户对硬件的透明度比高层用户低8.不同层次的面对不同用户,看到的计算机属性不同9....

2020-02-23 15:07:18

欧拉函数+欧拉定理

Visible Lattice Points 写这篇博客是因为上面那个题,人家是欧拉函数,看我这贪心一下午…定义:欧拉函数是小于x的整数中与x互质的数的个数,一般用φ(x)表示。例如φ(6)=2.特殊的,φ(1)=1。求法:φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…(1-1/pn),其中p1,p2……pn为x的所有质因数,x是不为0的整数.证明:容斥原理...

2020-02-19 15:30:47

Codeforces Round #620 (Div. 2)

心态崩了丫…一个小时A出ABC,然后就WA了一小时的D…A. Two Rabbits#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int,int> pii;const int N=1e6+10; vector<pair<int,strin...

2020-02-15 23:14:07

Codeforces Round #619 (Div. 2)(A~D)

A. Three Strings#include<bits/stdc++.h>using namespace std;const int N=100010;int main(){ string a,b,c; int t; cin>>t; while(t--) { cin>>a>>b>>c; bool flag=...

2020-02-14 11:02:43

素数,分解质因数, 约数,扩展欧几里得

//判断一个数是不是素数bool is_prime(int n){ if(n<2) return false; for(int i=2;i<=n/i;i++) { if(n%i==0) return false; } return true;}//判断一堆数是不是素数int prim[N]; ...

2020-02-13 22:33:26

Educational Codeforces Round 82 (Rated for Div. 2)(A~D)

唉,有点可惜,感觉D题能做出来,可惜时间有点不够了…先写三个题的题解吧,剩下的慢慢补。A. Erasing ZeroesA就没什么好说的了,统计出最左和最右的位置看一下中间有多少0就行。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=100010,mod=1e9+...

2020-02-13 10:09:50

动态规划(7)-------树形DP

昨天本来就能写的,结果写了俩个题写了四五个小时,于是乎拖到今天了。没有上司的舞会这个题就很好写了,不像状态压缩,真的是难理解…大佬博客f[u][0]表示从以U为根节点,不选u的方案。f[u][1]表示从以U为根节点,选u的方案。所以f[u][0]=求和max(f[si][0],f[si][1])i是遍历下一层的子节点f[u][0]=求和f[si][0] i是遍历下一层的子节点#i...

2020-02-12 15:08:18

Codeforces Round #618 (Div. 2)(A~E)

再写题解前,首先得感谢一波AtCode的出题人成功浪费我一上午时间…最后还是不会(Almost Everywhere Zero),感谢哪位大佬赐教…AB就没有没有什么可说的了,看完题直接写就行!A. Non-zero#include<bits/stdc++.h>using namespace std;typedef long long ll;const int mod=1e...

2020-02-10 18:48:21

感谢那些分享的人

真的是感动,今天翻到一些博客,写的是真的好,真的是感谢!!!顺便我也在此记录顺便为大家分享一波。2020 我把大学四年ACM模板分享了出来【总结】 ACMer一定要来看!【ACM刷题专题】这个假期一起来刷题把,刷完冲击区域赛,刷完拿不到奖随便打!...

2020-02-08 15:38:16

动态规划(6)-------状态压缩DP

蒙德里安的梦想

2020-02-07 21:25:51

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。