- 博客(39)
- 收藏
- 关注
RSS订阅原创 数位 dp
把数当成树来看待1.没有前导0的约束求区间不降数#include<bits/stdc++.h>using namespace std;int dp[11][10];void init(){ for(int i=0;i<10;i++)dp[1][i]=1; for(int i=2;i<=10;i++) { for(int j=0;j<10;j++) { for(int k=j;k<
2021-09-15 16:00:51
119
1
原创 数论bsgs HDU 6956 Pass!
bsgs算法在于求一个最小的非负整数x，a与p互质，使得ax≡ba^x\equiv bax≡b (mod p)根据欧拉定理,aφ(p)≡a^{φ(p)}\equivaφ(p)≡ 1 (mod p)，那么对于ax≡ba^x\equiv bax≡b (mod p)而言，此时x的取值范围为[0,φ(p)(p)(p)-1],因为再取上去，得到的值终会是等于在这个区间取到的某个值。为了计算简单，我们稍微取大一点点，这里取[0,p]即可。我们把区间[1,k×\times×k]（该区间大于[1,p]）分为k=p\sq
2021-09-10 23:04:08
143
1
原创 P1174 打砖块 DP
P1174打地砖我们不难发现，按照打子弹的顺序（不一定是按字典序），除了最后一列，其他列在遇到字符’Y’时，是不消耗子弹的，也就是假设现在只剩下0颗子弹，遇到一个字符’Y’的砖块，此刻还是能够打过去的，而最后一列则不行。因此定义dp[i][j][0]表示前i列里花费了j个子弹并且出现了最后一列的最大价值，而dp[i][j][1]表示还没有出现最后一列，转移此时就比较简单了，注意初始化！#include<bits/stdc++.h>using namespace std;const i
2021-08-29 09:48:12
141
原创 2021牛客暑期多校训练营9 C-Cells
C-Cells题意：给定n个点(0,a1a_1a1),(0,a2a_2a2),(0,a3a_3a3)…(0,ana_nan)求他们各自分别到对应点(1,0),(2,0),(3,0)…(n,0)的不相交路径的所有合法方案数。题解：首先要学习LGV引理。集合A上的点到集合B上的点所有不相交路径的方案数等于题目所求就为求行列式展开对于第j列都有1j!\frac{1}{j!}j!1可以提出来，接着消元，以第一行为例子不难发现答案为范德蒙行列式，但需要提出ai+1a_i+1ai+1，
2021-08-17 20:00:55
137
原创 fft（快速傅立叶变换）
模板从 A(x)=a0+a1x+a2x2+a3x3a_0+a_1x+a_2x^2+a_3x^3a0+a1x+a2x2+a3x3理解更加简单我们可以把A(x)用4个顶点来表示，此时他一定是唯一确定的曲线，易证四个顶点分别取单位根，那么我们要计算A(w40w_4^0w40),A(w41w_4^1w41),A(w42w_4^2w42),A(w43w_4^3w43)分奇偶a(x)=a0+a2xa_0+a_2xa0+a2xb(x)=a1+a3xa_1+a_3xa1+a3x易得A(
2021-08-04 16:41:10
308
原创 类扩展欧几里德 D - It‘s a Mod, Mod, Mod, Mod World
D - It’s a Mod, Mod, Mod, Mod World化简∑i=1n⌊(p∗imod q)⌋\sum_{i=1}^{n} {\lfloor(p*i\mod q)\rfloor}∑i=1n⌊(p∗imodq)⌋=∑i=1np∗i−⌊p∗iq⌋\sum_{i=1}^{n}p*i- {\lfloor\frac {p*i} {q}\rfloor}∑i=1np∗i−⌊qp∗i⌋*q=(n+1)n2\frac {(n+1)n} {2}2(n+1)n*p-q∑i=1n⌊p∗iq⌋\..
2021-07-13 23:19:10
145
原创 Codeforces 842 D Vitya and Strange Lesson
Codeforces 842 D Vitya and Strange LessonToday at the lesson Vitya learned a very interesting function — mex. Mex of a sequence of numbers is the minimum non-negative number that is not present in the sequence as element. For example, mex([4, 33, 0, 1, 1,
2021-05-30 12:21:52
91
原创 FatMouse and Cheese HDU - 1078
FatMouse has stored some cheese in a city. The city can be considered as a square grid of dimension n: each grid location is labelled (p,q) where 0 <= p < n and 0 <= q < n. At each grid location Fatmouse has hid between 0 and 100 blocks of chee
2021-04-21 20:42:47
70
原创 Codeforces Round #716 (Div. 2) D. Cut and Stick
D. Cut and Sticktime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputBaby Ehab has a piece of Cut and Stick with an array a of length n written on it. He plans to grab a pair of scissors and do the foll
2021-04-20 20:42:10
125
原创 HUD 1565方格取数（1）
HUD 1565方格取数（1）思路：状压DP，考虑对于每一行把合法状态全部筛选出来，也就是满足(i)&(i>>1)=0的状态放进集合里面，对于每一行可以转移的上一行的状态是i&j=0,转移方程就出来了。#include<iostream>#include<vector>#include<cstdio>#include<cstring>using namespace std;const int N=30,M=20000
2021-04-18 17:13:27
95
1
原创 HDU 1074Doing Homework
题意：给定n个作业(n<=15)，每个作业有完成的截止时间以及做完这个作业所需时间，一个作业的花费为做完这个作业超过截止时间的时间，求给出最小花费的排列，如果花费一样输出字典序最小的作业顺序。用状压dp来做，dp[i]=min(dp[i],dp[i-(1<<j)])其中(i&j!=0)#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>..
2021-04-18 17:06:12
78
原创 欧拉回路
欧拉回路dfs算法的思想：我们dfs每一个点，遍历这个点的所有的边，如果这条边已经遍历了就跳过，然后不断遍历，直到dfs完。框架如下:void dfs(int x){ for(顶点v的所有的边) { if(used[endge]) { 这条边用过了，continue; } used[endge]=true;//标记这条边 dfs(endge->to);//遍历这条边指向的顶点 load.add(to);//把这个点加入到路径记录当中，load里面就是路径的答
2021-04-16 18:57:34
192
原创 Max Sum Plus Plus HDU - 1024
HDU-1024题意：一段n个数的序列，可以任取其中m段不相交的区间，使得和最大。kuangbin的dp第一道题就让我想了很久，对于这种求不相交或者说连续的dp，dp[i]的状态普遍和dp[i-1]的状态密切相关。定义dp[i][j]表示包含第i个数的j段不相交区间的最大和,那么能够组成dp[i][j]的有两种可能：第一种：dp[i-1][j]即与i-1相连第二种:自己成一段，那枚举他的上一段的末尾是k，就有dp[i][j]=max(dp[k][m-1]),k的范围是[0,i-1]。#inclu
2021-04-11 22:13:59
55
原创 Bound Found POJ - 2566尺取法
题意：给一个无序数组和一个非负数t，让他找一段区间和，让他的绝对值最接近t。一段区间和可以由sum[r]-sum[l-1]来表示，枚举每个l，对于每个l在枚举每个r，这里面肯定是有多余的状态可以去掉的，当存在一个r使得sum[r]-sum[l]>=t，那么对于i满足sum[i]>sum[r]的数而言，是没有必要比较下去的。我们可以考虑对数组sum排序，接着对于每个l找到一个位置pos，使得sum[pos]-sum[l]>=t，那么对于这个左端点/右端点l而言，他最靠近t的区间和肯定是[
2021-04-06 00:03:47
97
原创 序列变换 HDU - 5256
好题，能感觉是最长上升子序列，但是还是不会做，最长上升子序列是对于每一个num[i]，可以往前面找一个数num[j]，只要满足num[j]<num[i]即可，而对于这道题，我们要找的数应该要加上一个限制条件，就是num[i]>=num[j]+i-j，变形一下，num[i]-i>=num[j]-j，因此预处理数组在加上求一次最长不严格上升子序列即可。#include<iostream>#include<algorithm>#include<cstdio&.
2021-04-05 20:00:58
72
原创 HDU 5493 Queue树状数组+二分
HDU-5493面向题解编程，特此做个总结…每个数字都有给定的k（前面或者后面比他高的人的个数），只要这个k不大于等于他在整个序列中大小的排名，一定存在至少一个合法方案！我们模拟下这个过程，把身高从大到小排序，对于当前的身高排名为i这个人，后面的人的位置肯定不影响他合法方案的存在。对于这个排名为i的人，他前面比他高的人的位置有两种可能k+1,n-i+1-k，因为要字典序最小，所以选择最小的位置，往已有的升高比他高的人的序列里面插入即可。按照身高从小到大，整个模拟过程可以理解为对于一个数，假设他在比他
2021-04-04 20:32:42
71
原创 Flyer HDU - 4768
HDU-4768 Flyer题意：社团给1-2322^{32}232编号的学生分发标签为i的宣传单，宣传单有n种，分发给编号是Ai,Ai+Ci,Ai+2Ci,…编号不超过Bi的学生，找出被发到传单为奇数的学生，保证最多只有一个。题解：第一次见到二分是这种姿势的！因为只有包含有奇数的那个区间的区间和才会是奇数，简直妙极了…利用这个性质就可以二分区间了。#include<iostream>#include<algorithm>#include<cstdio>#i
2021-04-02 19:17:47
87
原创 动态规划
计数型DPCodeCraft-21 and Codeforces Round #711 (Div. 2) C Planar Reflections
2021-04-01 07:43:47
127
1
原创 CodeCraft-21 and Codeforces Round #711 (Div. 2) C Planar Reflections
这个DP和平时遇到的不太一样，这里的每一个状态都与给出来的平面数有关！我们定义dp[i][j]表示粒子现在年龄是i处于第j个平面反弹的数量，那有dp[i][j]={粒子i往右边走+粒子i-1往左边走}，粒子i往右边走就是dp[i][j+1]，而粒子i-1往左边走情况很复杂，难道要重新计算吗？利用对称性，可以求解。假设年龄是3，平面是4个，那粒子2往左边第一个撞的数量就等于粒子3往第4个撞的数量。于是有状态转移方程dp[i][j]=dp[i][j+1]+dp[i-1][平面数-j+2]。#include
2021-04-01 07:41:16
149
原创 A M型字符串
如何判断一个前缀是不是回文串，用字符串哈希，判断正过来读以及倒过来读两个字符对应的Hash值是否相等即可。#include<bits/stdc++.h>#define IOS ios::sync_with_stdio(0),cin.tie(0);using namespace std;const int N=2e5+10,P=131;typedef unsigned long long ull;ull p[N],h[N],t[N];char s[N];int n;ull qu.
2021-03-30 15:59:28
54
原创 字符串哈希
字符串哈希全称字符串前缀哈希法，把字符串变成一个p进制数字，实现不同的字符串映射到不同的数字。注意点：任意字符不可以映射成0，否则会出现不同的字符串都映射成0的情况，比如A,AA,AAA皆为0冲突问题：通过巧妙设置P (131 或 13331) , Q (2642^{64}264)的值，一般可以理解为不产生冲突。#include<bits/stdc++.h>using namespace std;typedef unsigned long long ull;const in
2021-03-30 15:15:48
48
原创 G - Ikki‘s Story IV - Panda‘s Trick POJ - 3207（二分图染色/2-sat）
liympanda, one of Ikki’s friend, likes playing games with Ikki. Today after minesweeping with Ikki and winning so many times, he is tired of such easy games and wants to play another game with Ikki.liympanda has a magic circle and he puts it on a plane, t
2021-03-22 17:26:45
96
原创 Codeforces Global Round 13 C
C. Pekora and TrampolineThere is a trampoline park with n trampolines in a line. The i-th of which has strength Si.Pekora can jump on trampolines in multiple passes. She starts the pass by jumping on any trampoline of her choice.If at the moment Pekora
2021-03-01 16:57:01
236
1
原创 Codeforce 1139D Step to one（概率dp+容斥原理）
#include<iostream>#include<cmath>#include<ctime>#include<cstdlib>#include<cstdio>using namespace std;typedef long long ll;const int N=1e5+10;const ll mod=1e9+7;ll dp[N];int fac[20];int p=1;ll f(int n,int x){ ..
2020-12-04 00:12:33
146
原创 codeforce 686div3 F Array Partition单调栈
Array PartitionYou are given an array a consisting of n integers.Let min(l,r) be the minimum value among al,al+1,…,ar and max(l,r) be the maximum value among al,al+1,…,ar.Your task is to choose three positive (greater than 0) integers x, y and z such th
2020-11-26 01:29:03
307
原创 01字典树
我们用curcnt来表示目前插入了多少个节点，用0来表示主节点，那么建树的时候，当前cur=0表示当前节点，那endge[cur][0]表示0这条边连接的下一个节点的位置,endge[cur][1]表示的是1这条边连接的下一个节点的位置，那么如果endge[cur][0]|endge[cur][1]还没有数据，那我们就用curcnt来表示这个节点，然后curcnt++，之后把边的关系描述好即可。...
2020-11-07 14:54:14
68
原创 18361 数绵羊
18361 数绵羊时间限制:1000MS 代码长度限制:10KB提交次数:7 通过次数:4题型: 编程题 语言: 不限定Description小粥今晚依然因相思而失眠，所以开始数绵羊：一只绵羊，两只绵羊，三只绵羊，四只绵羊，五只绵羊，六只绵羊，七只绵羊，八只绵羊，九只绵羊，十只绵羊，十二只绵羊，十一只绵羊，十三只绵羊，十四只绵羊，十五只绵羊。。。什么，你说他数错了？绝对是因为你不够聪明所以看不出来他在数什么。他数绵羊的顺序满足以下条件：(1). 所数的数字为正数整；(2). 在满
2020-11-05 19:55:54
361
原创 scau数据结构习题
18708 最大子段和时间限制:1000MS 代码长度限制:10KB提交次数:0 通过次数:0题型: 编程题 语言: 不限定Description一个整数序列，选出其中连续且非空的一段使得这段和最大。输入格式第一行是一个正整数N，表示了序列的长度（0=<N<=200000）。第二行包含N个绝对值不大于10000的整数ai。输出格式一个整数，为最大的子段和。子段的最小长度为1。数据确保结果在类型int范围内。输入样例72 -4 3 -1 2 -4 3输出样例4
2020-08-15 00:42:10
4673
1
原创 合并回文子串 区间dp
链接：https://ac.nowcoder.com/acm/problem/13230来源：牛客网题目描述输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可输入描述:第一行一个整数T(T ≤ 50)。接下来2T行，每两行两
2020-05-19 10:04:09
134
原创 tokitsukaze and Soldier 优先队列
题目描述在一个游戏中，tokitsukaze需要在n个士兵中选出一些士兵组成一个团去打副本。第i个士兵的战力为v[i]，团的战力是团内所有士兵的战力之和。但是这些士兵有特殊的要求：如果选了第i个士兵，这个士兵希望团的人数不超过s[i]。(如果不选第i个士兵，就没有这个限制。)tokitsukaze想知道，团的战力最大为多少。输入描述:第一行包含一个正整数n(1≤n≤10^5)。接下来n行，每行包括2个正整数v,s(1≤v≤10^9,1≤s≤n)。输出描述:输出一个正整数，表示团的最大战力。
2020-05-18 00:05:27
166
原创 bzoj 2743: [HEOI2012]采花（树状数组）附加HH项链
首先先做HH项链题目描述HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答…… 因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。输入格式一行一个正整数...
2020-04-05 10:25:11
171
2
原创 最大连续子序列和
Description一个整数序列，选出其中连续且非空的一段使得这段和最大。输入格式第一行是一个正整数N，表示了序列的长度（0=<N<=200000）。第二行包含N个绝对值不大于10000的整数ai。输出格式一个整数，为最大的子段和。子段的最小长度为1。数据确保结果在类型int范围内。输入样例72 -4 3 -1 2 -4 3输出样例4提示【样例说明】2,-...
2020-03-12 13:41:48
1436
3
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人