• 等级
  • 6282 访问
  • 49 原创
  • 4 转发
  • 117604 排名
  • 5 评论
  • 2 获赞

Round #537 (Div. 2) D

题目意思:给一个长度为偶数n的字符串s,字符串s有大小写的英文字母。再给你一个询问次数q,每个询问有两个数字x,y,表示s[x]和s[y]及其所有相同的字符放在一个集合里面而且长度是n/2(不够用其他字符来凑),其他的放在另一个集合里面(长度为n/2)。两个集合里面字符的顺序不同视为一种排列。两个集合交换为止视为不同的排列。然后,根据每个询问问,问有效的排列数目是多少。 思路(根据官方...

2019-02-14 18:44:26

Codeforces Round #536 (Div. 2) F

题目意思:已知fn=(fn-1^b1*fn-2^b2*...*fn-k^bk)mod998244353,其中b1,b2,...bk都知道,fn=m,n,k,m是给你的数字.要求fk如果不存在,就输出-1 思路:官方题解是这样表述的:1.998244353是一个质数,而且很特殊,它的原根是32.原根(设g是p的原根)的性质有以下两条:(1)g^(p-1...

2019-02-14 18:21:53

鸽了好久,开始更博

咕咕咕

2019-02-14 17:55:20

整数拆分的方案数目

OEIS:http://oeis.org/search?q=1%2C2%2C3%2C5%2C7%2C11%2C15&sort=&language=english&go=Search哈代拆分:对于数字N,有F(N)种拆分方案,见OEISCODE的详细地址:https://blog.csdn.net/u011889952/article/details/44...

2018-09-03 17:27:45

NEXT

AC自动机+最大子段和问题(DP)

2018-09-03 13:37:14

二进制的最小划分

一个数N,划分为M块,使1~N的每一个数字都能由M块内S块且不重复组合相加而成,问:最小分几块?ANS=log2(N)证明:二进制加权+进位拆分 

2018-09-03 01:23:43

字符串与HASH(二)

假设我们有一串字符串:现在求字符串的前缀后缀的最长公共长度:即:满足的最长公共长度是:HASH做法:先定义一个初始公共长度x=0;如果:HASH1==HASH2那么;更新x,x=max(x,i+1);答案就是X ...

2018-08-31 10:26:35

约数个数

有一个数字n:都是质数那么n的约数的个数是: 

2018-08-30 17:51:55

set&multiset

set特性:1.去重性(1个元素只出现一次)2.有序性multiset特性:1.多重性2.有序性(1个元素可以出现很多次)都在<set>内,使用方法相同。

2018-08-30 15:01:42

费马小定理&逆元&欧拉定理(函数)

  目录 1.逆元:2.欧拉函数:3.欧拉定理:4.费马小定理:CODE(A):CODE(B):CODE(F+打表):1.逆元:2.欧拉函数:3.欧拉定理:4.费马小定理:费马小定理是欧拉函数的一种特殊情况:CODE(A):#include<iostream>usingn...

2018-08-30 12:03:28

HDU5015

链接:HDU5015初始矩阵:递推矩阵:overORZcode:#include<cstdio>#include<algorithm>#include<cmath>#definemod(x,y)((x+y)%y)typedeflonglongll;constllMAXN=1e9+10;const...

2018-08-29 10:02:04

字符串与hash(一)

之前有一种普遍使用的字符串hash:可以有效地处理字符串的子串:再者:还有可以代替KMP的hash:+//现在我们从一道题目入手(SPOJ-EPALIN):题意:对给定字符串S,求以S为前缀的、长度最小的回文串并输出它网上由两种解法:一、KMP+逆字符串二、hash+回文我还有一种解法:马拉车+标记以S[LEN-1]为结尾的最长回文串长度的左端点...

2018-08-28 17:45:29

hash算法原理详解

原文地址:hash算法原理详解hash算法原理详解[+]一概念二Hash构造函数的方法  1直接定址法数字分析法折叠法平方取中法减去法基数转换法 7除留余数法随机数法9随机乘数法10字符串数值哈希法旋转法三Hash处理冲突方...

2018-08-28 11:56:16

HASH-TABLE 的简单介绍

HASH-TABLE是什么: hash-tableHASH的优势:开一个长度为L的数组,平摊查找速度提到L倍,搞多个键值让HASH的结果不相等,但最终放到数组里布碰撞是由数组大小决定的。,以(%n)来计算,达到sqrt(n)时,由50%的碰撞概率(摘自夹克老爷)简单来说:HASH就是乱搞,把大范围的离散数据通过一个特定的生成函数转化为一个小范围的定长数据中的一个槽(slot)...

2018-08-26 23:35:03

KMP--字符串匹配(前缀数组)

算法背景:Knuth–Morris–Prattalgorithm数据结构:next数组+ 。。算法原理:预处理匹配串(匹配串与自己匹配)得到失配数组没了。得到失配数组NEXT的函数:voidgetnext(char*p)//匹配串{intm=strlen(p);//匹配串的长度mintk=-1,cur=0;//k是第二匹配串的下...

2018-08-24 15:41:21

滚动数组

滚动数组的好处:和金坷垃一样。。。。txtx自然是节省空间,这是应对动态规划题目中卡空间的常用做法--可能涉及到3维甚至以上的dp转移方程。利用滚动数组,可以把某一维(这一维的用到的地方只有有限个,假设为k,那么我们就可以设这一维大小为k)这里的k与转移方程有关系,所以先要判断转移方程有多少个转移条件。...

2018-08-22 16:29:08

多重背包的二进制优化问题

一般的思路:把多重背包转化为01背包,但这样时间复杂度是不变的,依然会TLE。二进制优化:把第i种物品的num【i】分为数个新的物品:分配为:1,2,4.....2^c (2^c<num[i])剩下的数量都可以由这些二进制组合而成。CODE(以51NOD1086为例):#include<cstdio>intn,m,dp[5...

2018-08-22 12:21:52

多重背包问题 可行性问题O(V N) 算法

原文地址:多重背包问题可行性问题O(VN)算法算法一#include<stdio.h>inta[100],m[100];booldp[100][100];intmain(){intn,w;scanf("%d%d",&n,&w);

2018-08-22 10:28:15

多重背包由01背包转化的写法

由01背包转化的写法:1.嵌套了一层循环:(1~num[i])CODE:#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>constintMAXN=200+10;intt,n,m,dp[MAXN],value[MAXN],we...

2018-08-21 19:17:59

完全背包的两种写法

背包九讲地址:file://C:\Users\PHC\AppData\Local\Packages\903DB504.QQ_a99ra4d2cbcxa\LocalState\User\1021861128\NetworkFile\背包问题九讲_2.0.pdf完全背包的一种正常思路:物品数量: 背包容量: 选择装多少个第i个物品: 完全背包的另一种思路:改变01背包的第二...

2018-08-21 12:03:23

Ivanzn

关注