我不是手机-CSDN博客

原创字符串主题 KMP，next数组问题，哈希，Manacher，暴力匹配，尺取，ac自动机,kuangbin题单

kmp子串在母串出现的次数，解决字符串匹配的问题char a[maxn],b[maxn];ll lena,lenb;int next1[maxn];void getnext(){ next1[0]=-1; int i=0,j=-1; while(i<lena){//子串 if(j==-1||a[i]==a[j]){//子串 i++;j++; if(a[i]==a[j]) next1[i]=next1[j]; else next1[i]=j; } else{

2020-10-16 19:51:04 107

原创博弈论专题 kuangbin题单（巴什，威佐夫，nim，fib博弈）+SG函数打表

省赛前先练着，回来补完巴什博弈：一堆n个物品两个人来拿，每人至少拿一个，最多拿m个，问最后取完的人win判断条件：n%(m+1)!=0cin>> n>>m;if (n%(m+1)!=0) cout<<first win<<endl;else cout<<second win<<endl;威佐夫博弈：两堆物品a,b，有两个人轮流来取，从一堆中取至少一个没有上限，或者从两堆中取相同数量的物品。两堆最后都取完的人win

2020-10-02 11:01:14 339

原创 LeetCode 678. 有效的括号字符串括号序列+栈

题目链接class Solution {public: bool checkValidString(string s) { stack<int>st; stack<int>st1; int len=s.size(); for(int i=0;i<len;i++){ if(s[i]=='(') st.push(i); else

2021-03-02 16:05:39 128

原创 LeetCode 672. 灯泡开关 Ⅱ

题目链接class Solution {public: //12-3; //13-2; //23-1; //0 1 2 3 4 14 24 34 int state[8][6]={ {1,1,1,1,1,1}, {0,0,0,0,0,0}, {1,0,1,0,1,0}, {0,1,0,1,0,1}, {0,1,1,0,1,1}, {1,0,0,1,0,0},

2021-03-01 12:37:05 146

原创 acwing 1230. K倍区间前缀和+同余

题目链接#include<bits/stdc++.h>using namespace std;const int N=100100; ;long long res=0,cnt[N],s[N];int main(){ int n,k; cin>>n>>k; for(int i=1;i<=n;i++){ cin>>s[i]; s[i]+=s[i-1]; } cnt[0]=1;

2021-02-18 15:47:11 179

原创 acwing 1414. 牛异或异或前缀和+trie树

题目链接对于异或来说，组成前缀和数组时应该对上一位取异或值，在判断范围[i,j]时会与普通前缀和相同：普通的前缀和sum=w[j]-w[i-1],但是异或区间的前缀和是sum=w[j]^w[i-1]因为如果在数组中遍历两遍的端点，时间复杂度是on2的，所以需要使用01trie来维护。对于每个点都insert到trie中创建当前的空间和记录当前的位置，每次插入一个就query一次寻找当前长度中最长的异或值，如果当前点有分支的话就走到不同分支，否则就走到相同分支#include<bits/std

2021-02-17 17:19:42 147

原创 acwing 1102. 移动骑士马走日bfs

题目链接总共8个方向#include<bits/stdc++.h>using namespace std;const int N=350;typedef pair<int, int> PII;PII a,b;int n,m,d;int dist[N][N];int bfs(PII start,PII end){ if(start==end) return 0; queue<PII>qu; qu.push(start); m

2021-02-03 10:36:13 122

原创 acwing 1613. 数独简单版 DFS爆搜

题目连接数独问题，需要在横、纵、每9个方格之中填1到9数字。我们可以构建一棵dfs树，对于每一个节点要求满足以上三总条件才可以更新这一个点，如果这个点可以走下去那么就深度搜索下去，并且更新当点的状态以此复原现场。y总代码#include<bits/stdc++.h>using namespace std;const int N=10;char g[N][N];bool row[N][N],col[N][N],cell[3][3][N];bool dfs(int x,int y)

2021-02-02 20:58:11 95

原创 acwing 1402. 星空之夜哈希+连通块

题目链接对于结构特别的连通块可以将它的每个点到其他点的距离之和作为hash值并且在判断浮点数是否出现过时，应该比较fabs的差值#include<bits/stdc++.h>#define lowbit(x) x&(-x)#define x first#define y secondusing namespace std;typedef pair<int,int>PII;const int N=110;const double eps=1e-6;int

2021-02-02 11:26:43 125

原创 acwing 243. 一个简单的整数问题2 树状数组区间操作

题目链接树状数组对于单点操作只需要开一个树状数组就可以了，但是对于区间的整体进行修改需要开两个树状数组，通过差分操作去维护，一个维护bi，一个维护bi×i#include <bits/stdc++.h>using namespace std;#define ll long long#define lowbit(x) x&(-x)const int N=2e5;ll c1[N],c2[N],n,m,a[N];inline void add(ll x,ll v){ f

2021-01-29 14:08:03 108

原创 acwing 482. 合唱队形最长上升子序列+最长下降子序列寒假集训

题目链接假设中间有一个数n，那么排队的最多人数就是它左边的最长上升子序列和它右边的最长下降子序列的和。我们把每个点上的点作为中间的点去做同样的操作，取两个值的和的最大值#include<bits/stdc++.h>using namespace std;const int maxn=500;int a[maxn],dp[maxn],dp1[maxn];int main(){ int n,id,mx; cin>>n; for(int i=1;i&lt

2021-01-27 20:51:22 82

原创 acwing 297. 赤壁之战树状数组优化DP 寒假集训

题目链接想要求长度为M的子序列，我们可以拿DP方程来计算，并且这个DP也是比较好看出来的DP[i][j]代表着i后j位置中的所有长度为j的子序列，递推方程为for(int i=1;i<=n;i++){ for(int j=2;j<=m;j++){ for(int k=1;k<i;k++){ if(a[k]<a[i]) dp[i][j]+=dp[k][j-1] } } }}的一个三重循环，但是n^3的暴力一定是会超时的，所以我们可以用树状数组来优化一个

2021-01-27 19:14:06 110

原创 K Smallest Sums UVA - 11997 贪心+优先队列寒假集训

题目链接这道题网上说的奇奇怪怪，在加上我地址符看不太懂，所以比较难以理解其实原理比较简单，我们先把所有的数组进行sort，并将第一个数组命名为A数组，后面的命名为Bn数组，那么我们利用优先队列进行选择最优解，就是一直用B数组去维护A数组。将A1去加上B1到n所有数并放入优先队列，同样一直遍历到An去加上B1到n的值放入优先队列，这样我们取A的前n个作为维护后新的A数组，重复这样的操作到Bn这样答案就是数组A的所有值了。这里有个小问题，如果你不断把A1加B1到n的值，An加B1到n的值放入队列，再去取

2021-01-26 20:30:30 95

原创 power oj 2920: 第K大1.0 优先队列

题目链接题意是在一组数组里面，对每一个数求它右边的最大值。题解：我们把可以不断将数字都放进一个优先队列里面，做一个在线操作：对于每一次放入a[i]的数，通过比较将队列前面比他小的所有数字弹出，记录这些数字被弹出的次数。如果==3就直接用数组记录这个数右边第k个数的下标为i，如果不等于3就将它暂且放在一个双端队列中（至于为什么是deque,是因为比较好操作，用queue或者stack都是可以的）。在这个放入的a[i]将它前面所有的数字都弹出并标记后，我们把在deque中的所有数字再放回优先队列中，因为

2021-01-26 20:15:19 100

原创 acwing 1432. 棋盘挑战 DFS爆搜

给定一个 N×N 的棋盘，请你在上面放置 N 个棋子，要求满足：每行每列都恰好有一个棋子每条对角线上都最多只能有一个棋子1 2 3 4 5 61 | | O | | | | |2 | | | | O | | |3 | | | | | | O |4 | O | | | | | |5 | | | O | | | |6 | | | | | O | |上图给

2021-01-22 20:47:48 91

原创 Round Numbers POJ - 3252 01二进制数位DP 寒假集训

The cows, as you know, have no fingers or thumbs and thus are unable to play Scissors, Paper, Stone’ (also known as ‘Rock, Paper, Scissors’, ‘Ro, Sham, Bo’, and a host of other names) in order to make arbitrary decisions such as who gets to be milked first

2021-01-22 20:43:58 111

原创 P1886 滑动窗口 /【模板】单调队列寒假集训

有一个长为 nn 的序列 aa，以及一个大小为 kk 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。例如：The array is [1,3,-1,-3,5,3,6,7][1,3,−1,−3,5,3,6,7], and k = 3k=3。输入格式输入一共有两行，第一行有两个正整数 n,kn,k。第二行 nn 个整数，表示序列 aa输出格式输出共两行，第一行为每次窗口滑动的最小值第二行为每次窗口滑动的最大值输入输出样例输入 #1复制8 3

2021-01-22 20:37:13 77

原创 Subsequence HDU - 3530 维护区间最大差值单调队列寒假集训

There is a sequence of integers. Your task is to find the longest subsequence that satisfies the following condition: the difference between the maximum element and the minimum element of the subsequence is no smaller than m and no larger than k.InputThe

2021-01-22 20:35:01 230 1

原创 Balanced Number HDU - 3709 寻找力矩数位DP 寒假集训

A balanced number is a non-negative integer that can be balanced if a pivot is placed at some digit. More specifically, imagine each digit as a box with weight indicated by the digit. When a pivot is placed at some digit of the number, the distance from a

2021-01-22 20:29:15 82

原创 Bomb HDU - 3555 出现多少个49，数位DP，寒假集训

反恐精英在尘土中发现了一枚定时炸弹。但这次恐怖分子改进了定时炸弹。定时炸弹的编号顺序从1到N计数。如果当前的编号顺序包括(子串!!)“49”，爆炸威力将增加一个点。问最后爆炸的时候威力为多少。输入描述输入T代表T组(T <= 1e4)每组输入一个n(1 <= n<=2^63 - 1)输出描述输出爆炸的威力样例输入11样例输出0区间里面的数字间出现了多少个49，数位dp板子#include <stdio.h>#include <string.h&

2021-01-22 20:25:28 150 1

原创 Dire Wolf HDU - 5115 区间DP，寒假集训

有n头狼排成一排，每只狼两个属性，攻击力和加成值，狼的实际攻击力等于自身攻击力加相邻狼的加成值，被杀死之后的狼对相邻的狼的攻击力的加成会被取消，同时，原先与被杀死的狼相邻的两头狼会变成相邻的狼。问杀死所有狼受到的伤害值最小是。Input多组输入，第一行一个T每组输入一个n(n <= 200)输入n个数，代表每只狼的攻击力(0<=a[i] <=1e5)输入n个数，代表每只狼的加成值(0<=b[i]<=5e4)Output每组样例输出一个Case，然后输出答案。S

2021-01-22 20:22:55 93

原创 X mod f(x) HDU - 4389 数位DP 寒假集训

定义一个函数 f(x):int f ( int x ) {　　　if ( x == 0 ) return 0;　　　return f(x/10) + x%10;}现在，我们有个区间 (1 <= A <= B <= 10 9), 查询有多少个整数 x mod f(x) 等于 0.Input第一行是一个整数 T (1 <= T <= 50), 表示数据组数。接下来 T 行每行包含两个整数 A B (1 <= A <= B <= 10 9)Outp

2021-01-22 20:09:20 93

原创 Maximum Sequence HDU 6047 单调队列思维题寒假集训

Steph is extremely obsessed with “sequence problems” that are usually seen on magazines: Given the sequence 11, 23, 30, 35, what is the next number? Steph always finds them too easy for such a genius like himself until one day Klay comes up with a problem

2021-01-22 19:59:36 84

原创 Common Subsequene POJ 1458 LCS最长公共子序列问题，寒假集训

A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = < x1, x2, …, xm > another sequence Z = < z1, z2, …, zk > is a subsequence of X if there exists a strictly increasing seque

2021-01-22 19:19:15 79

原创数字游戏区间内取模数位DP 寒假集训

由于科协里最近真的很流行数字游戏，某人又命名了一种取模数，这种数字必须满足各位数字之和 modN 为 0。现在大家又要玩游戏了，指定一个整数闭区间 [a,b]，问这个区间内有多少个取模数。输入格式题目有多组测试数据。每组只含三个数字 a,b,N。输出格式对于每个测试数据输出一行，表示各位数字和 modN 为 0 的数的个数。样例Input Output1 19 92数据范围与提示对于全部数据，1≤a,b≤231−1,1≤N<100。取模即使在当前位置上改变余数状态，板子记下来吧

2021-01-20 20:15:34 236 4

原创 Windy 数 LibreOJ - 10165 每一位比前一位大2，数位DP，寒假集训

Windy 定义了一种 Windy 数：不含前导零且相邻两个数字之差至少为 2 的正整数被称为 Windy 数。Windy 想知道，在 A 和 B 之间，包括 A 和 B，总共有多少个 Windy 数？输入格式一行两个数，分别为 A,B。输出格式输出一个整数，表示答案。样例 1Input Output1 109样例 2Input Output25 5020数据范围与提示20% 的数据，满足 1≤A≤B≤106；100% 的数据，满足 1≤A≤B≤2×109。直接看代码吧，

2021-01-20 20:13:53 84

原创数字游戏1 区间内的不降数，数位DP 寒假集训

科协里最近很流行数字游戏。某人命名了一种不降数，这种数字必须满足从左到右各位数字成小于等于的关系，如 123，446。现在大家决定玩一个游戏，指定一个整数闭区间 [a,b]，问这个区间内有多少个不降数。输入格式有多组测试数据。每组只含两个数字 a,b，意义如题目描述。输出格式每行给出一个测试数据的答案，即 [a,b] 之间有多少不降数。样例Input Output1 91 19918数据范围与提示对于全部数据，1≤a≤b≤231−1。简单题，只要记得使位数上的数字进行排序#inc

2021-01-20 20:12:33 292

原创 B-number HDU - 3652 数字取模数位DP 寒假集训

统计区间 [1,n] 中含有 ‘13’ 且模 13 为 0 的数字有多少个。输入格式多组数据每行一个正整数n(1 ≤ n ≤ 1e9)一直输入到文件结束输出格式输出一行表示满足条件的答案样例输入131002001000样例输出1122多了一维来记录这个当前位置上的数字mod的余数，当板子写把。#include <stdio.h>#include <string.h>#include <math.h>#include <map

2021-01-20 20:09:37 158 1

原创不要62 HDU - 2089 数位dp 除62以外的数字个数寒假集训

杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。不吉利的数字为所有含有4或62的号码。例如：62315 73418 88914都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。Input输入的

2021-01-20 20:06:19 71

原创 Aeroplane chess HDU - 4405 飞行棋问题期望DP 寒假集训

Hzz loves aeroplane chess very much. The chess map contains N+1 grids labeled from 0 to N. Hzz starts at grid 0. For each step he throws a dice(a dice have six faces with equal probability to face up and the numbers on the faces are 1,2,3,4,5,6). When Hzz

2021-01-19 20:52:36 159

原创 Park Visit HDU - 4607 树的直径链试前向星寒假集训

Claire and her little friend, ykwd, are travelling in Shevchenko’s Park! The park is beautiful - but large, indeed. N feature spots in the park are connected by exactly (N-1) undirected paths, and Claire is too tired to visit all of them. After considerati

2021-01-19 13:11:38 91

原创 Bag of mice CodeForces - 148D 公主与龙概率DP 寒假集训

The dragon and the princess are arguing about what to do on the New Year’s Eve. The dragon suggests flying to the mountains to watch fairies dancing in the moonlight, while the princess thinks they should just go to bed early. They are desperate to come to

2021-01-19 13:04:40 158

原创 Anniversary party HDU-1520员工聚会树形DP（链试前向星法）寒假集训

There is going to be a party to celebrate the 80-th Anniversary of the Ural State University. The University has a hierarchical structure of employees. It means that the supervisor relation forms a tree rooted at the rector V. E. Tretyakov. In order to mak

2021-01-18 18:07:39 172

原创 Godfather POJ-3107 树的重心链试前向星寒假集训

Last years Chicago was full of gangster fights and strange murders. The chief of the police got really tired of all these crimes, and decided to arrest the mafia leaders.Unfortunately, the structure of Chicago mafia is rather complicated. There are n pers

2021-01-18 17:59:18 80

原创 Mondriaan‘s Dream poj-2411 铺瓷砖状压dp 寒假集训

Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his ‘toilet series’ (where he had to use his toilet paper to draw on, for all of his paper was filled with squares and rectangles), he dre

2021-01-17 19:49:13 111

原创 Palindrome subsequence HDU-4632区间dp 回文问题寒假集训

In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the sequence <A, B, D> is a subsequence of <A, B, C, D, E, F>.(h

2021-01-17 13:49:41 85

原创 Brackets POJ -2955 括号匹配区间dp 寒假集训

We give the following inductive definition of a “regular brackets” sequence:the empty sequence is a regular brackets sequence,if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, andif a and b are regular brackets sequen

2021-01-17 13:42:19 93

原创 Codeforces Round #693 (Div. 3) D. Even-Odd Game 简单博弈

During their New Year holidays, Alice and Bob play the following game using an array a of n integers:Players take turns, Alice moves first.Each turn a player chooses any element and removes it from the array.If Alice chooses even value, then she adds it

2021-01-06 21:17:28 304

原创 Codeforces Round #693 (Div. 3) C. Long Jumps

Polycarp found under the Christmas tree an array a of n elements and instructions for playing with it:At first, choose index i (1≤i≤n) — starting position in the array. Put the chip at the index i (on the value ai).While i≤n, add ai to your score and mov

2021-01-06 21:14:58 328

原创 Codeforces Round #693 (Div. 3) B. Fair Division 模拟

Alice and Bob received n candies from their parents. Each candy weighs either 1 gram or 2 grams. Now they want to divide all candies among themselves fairly so that the total weight of Alice’s candies is equal to the total weight of Bob’s candies.Check if

2021-01-06 21:07:49 182

空空如也

空空如也