ID_BePosit-CSDN博客

原创 NTRURU

import randomimport mathimport numpy as npdef C(n,m): res=1 mx=max(n-m,m) mi=min(n-m,m) for i in range(mx+1,n+1): res=res*i for i in range(1,mi+1): res=res//i return resn=16q=256# A=np.random.randint(0,256,(1.

2022-05-23 22:02:09 185

原创 SIS背包

#include <bits/stdc++.h>using namespace std;int N=251,p=3,q=197,d=83;int H[2000][2000],m[2000],r[2000],e[2000],f[40][2000][2000];int id[4]={0,1},path[44];vector<int>v[2];void FX(int id1,int id2){ //id1=id2; int n=15,cnt=0; m...

2022-05-10 22:28:15 192

原创格基约化算法

import randomn=3m=9q=107a=[]for i in range(0,m): b=[] for j in range(0,m): b.append(0) a.append(b)for i in range(0,n): for j in range(n,m): a[i][j]=random.choice(range(q))*11111111111111for i in range(0,n): a[i][i...

2022-04-05 20:35:53 764

原创 Python

print('hello world')print('aaa')a=10print (a)a='11'print(type(a))a=2a=a**10print(a)name='老子'QQ='22222'phone='11234'addr='bj'name=int(input())QQ=input()print('姓名:%d'%(name))print('QQ:{}'.format(QQ))score=int(input('请输入'))if score>60:.

2022-04-05 12:02:05 176

原创 JM2007矩阵构造

#include <bits/stdc++.h>using namespace std;struct node{ int xi[5];}temp;bool vis[22][22][22][22];int pos[22][22][22][22];string cstr[22]={"0000","1000","0100","0010","0001","0011","0110","1001","1100"};string str[222][222],aw[22]={"-1",".

2021-12-11 20:37:27 412

原创 QYQ-icpc备战训练赛1（2016多校9）

B - Best Divisiondp[ i ]表示截止到位置i能划分出的最大数量合法段，前缀和+01字典树优化dp转移即可F - Flight不会I - Intersection is not allowed!LGV 定理裸题J - Jong Hyok and Stringsam裸题。广义自动机识别子串，求endpos类K - K-th value二分答案。小于mid...

2019-10-20 22:20:00 41

原创 Hawala Arrests CodeChef - AMR16G

题意：一棵树，每个点可以有 0-K 种颜色，每种颜色在树上的点连续的，选择最少的点覆盖K种颜色，思路：树上贪心，对应到序列上，类似于 k个区间，选择最少的点，让每个区间至少包含一个点的经典贪心问题解决方法是按照右端点排序，贪心的选择点，那么在树上问题类似，我们把每个颜色块的根看作区间右端点，按照deep进行排序，贪心的选点即可。#include<bits/stdc++....

2019-09-25 15:38:00 33

原创查分约束

#include<bits/stdc++.h>using namespace std;#define N 11222#define inf 1e15#define ll long long#define go(i,a,b) for(int i=a;i<=b;i++)int T,n,m,A,B,C,D,head[N],tot,inque[N],cas;struct...

2019-09-20 18:24:00 31

原创 BM&EXCRT

#include <bits/stdc++.h>using namespace std;#define rep(i,a,n) for (long long i=a;i<n;i++)#define per(i,a,n) for (long long i=n-1;i>=a;i--)#define pb push_back#define mp make_pair...

2019-09-20 18:23:00 28

原创杨丰磊

一般图带花树匹配：#include <bits/stdc++.h>using namespace std;#define N 230int nex[N],spo[N],w[N],q[N],vis[N],mark[N];vector<int>path[N];int n,r,u,to;int finds(int x){ return w[x]==x?x:w[...

2019-09-18 17:06:00 29

原创课程设计

#include<bits/stdc++.h>#define N 8typedef struct hm{ char ch; char code[20];} HuffM;typedef struct s{ char ch; int frq;} mytype;typedef struct bt{ struct bt *lchi...

2019-06-27 08:46:00 30

原创大数模板

大数加法string temp1,temp2,temp,str;string sum(string s1,string s2){ if(s1.length()<s2.length()) { string temp=s1; s1=s2; s2=temp; } int i,j; for(i=s1....

2019-06-18 16:51:00 28

原创点分治

题意后两个求和符号代表的是有多少异或值为0的路径。前两个符号代表有多少路径包含异或值为0的路径。即每个权值为0的路径对答案的贡献为有多少路径包含当前路径，所有的贡献加起来就是答案。思路点分治，权值太大，桶只能用map了。x与y之间的路径(x与y间权值异或为0)对答案的贡献是(x可以扩展的点数)**(y可以扩展的点数)。如上图，设2与3之间的权值异或为0，那么这条边对答案的贡献为2*3...

2019-05-28 11:37:00 30

原创 A - A Secret -扩展KMP

题目大意：给你两个字符串A,B，现在要你求B串的后缀在A串中出现的次数和后缀长度的乘积和为多少。题解：扩展KMP模板题，将A和B串都逆序以后就变成了求前缀的问题了，扩展KMP求处从i位置开始的最长公共前缀存于数组。最后通过将数组的值不为0的进行一个桶计数，倒着进行一下求和就可以了。注意，在这个题目上扩展kmp处理出来的是ex[ i ]数组是 A串的每个从 i 位置开始的后缀，与B串的...

2019-02-16 19:01:00 29

原创 G - Surf Gym - 100819S -逆向背包DP

G - SurfGym - 100819S思路：有点类似逆向背包DP ，因为这些事件发生后是对后面的时间有影响。所以，我们进行逆向DP，具体见代码实现。#include<bits/stdc++.h>using namespace std;#define maxn 1000000#define ll long longstruct node{ ...

2019-01-23 19:31:00 806

原创 C - Thief in a Shop - dp完全背包-FFT生成函数

C - Thief in a Shop思路：严格的控制好k的这个数量，这就是个裸完全背包问题.(复杂度最极端会到1e9)他们随意原来随意组合的方案，与他们都减去最小的一个 a[ i ] 组合的方案数目是不会改变的那么我们就 dp [ i ]表示 i 这个价格需要的最少个数。这样求最小个数保证不会漏解然后如果这个 i 能通过 1 - k 个物品组合出来，那么一定能通过k...

2019-01-23 19:25:00 34

原创 Sightseeing trip POJ - 1734 -Floyd 最小环

POJ - 1734思路 : Floyd 实质 dp ,优化掉了第三维. dp [ i ] [ j ] [ k ] 指的是前k个点优化后 i -> j 的最短路。所以我们就可以利用这个性质去求最小环，最小环的构成可以看作是由一条 i -> k k->j 加上 dp [ i ] [ j ]的最短路那么我们可以利用还没有用 k 优化的 i...

2019-01-23 19:08:00 31

原创 P2733 家的范围 Home on the Range-弱DP

P2733家的范围 Home on the Range思路：转化为以每个点为右下角的最大正方形的边长#include<bits/stdc++.h>using namespace std;#define maxn 303int tong[maxn],dp[maxn][maxn],n;char a[maxn][maxn];int main(){ scanf...

2019-01-22 11:20:00 32

原创 Love Live!-01字典树启发式合并

链接：https://ac.nowcoder.com/acm/contest/201/D?&headNav=www思路：题目要求的是每个等级下的最大简单路径中的最大异或值，那么我们为了保证目前的路径中最大的权值为当前访问的边，先进行排序，然后一条一条的插入边，并查集维护各个联通块，启发式合并，由当前边连接起来的两个联通块，所谓启发式合并也就是把小的块合并到大的上。然后查...

2019-01-22 10:47:00 32

原创 Kilani and the Game-扩散形式的搜索

Kilani and the Game思路：这种扩散走法的并且有速度。我们需要一层一层的入队，而且根据题目要求按编号处理例如q1队列中有 1 1 1 2 2 2 2 3 3 3 3 3 3 3 那么我们需要把 id = 1 的一起处理把 1 1 1 push 到 q2 然后只要不超过 s [ id = 1 ] 的速度，就一直进行bfs ，当到达了 s [ id = 1...

2019-01-21 19:23:00 31

原创 Little Sub and Isomorphism Sequences ZOJ - 4089

ZOJ - 4089思路：可以反正最长重构序列必然符合此模式 x + { } 与 { } + x那么题意转化为了找两个距离最长的相同的数。eeee 先离散化然后开 2e5 个set 可插入可删除的维护每个数的出现的位置。然后。如果有set .size > = 2 则可以更新。最值。最值可用线段树or mulitset 维护#in...

2019-01-20 17:03:00 20

原创 Wish-递推DP记数

链接：https://nanti.jisuanke.com/t/35618题意：如果一个数大于等于1010且任意连续两位都是质数，那么就称之为 Wish 数。当然，第一个 Wish 数是1111。比如9797，111111，131131，119119都是 Wish 数，而1212，136136则不是。问第NN个 Wish 数是多少。思路：预处理一下 1 - 9 每个...

2019-01-20 14:26:00 16

原创 Little Sub and Mr.Potato's Math Problem-构造

链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5864思路 : 判断小于它的合法的，再看大于它的合法的，特判10000、10、1000.... 这种情况.#include<bits/stdc++.h>using namespace std;#define ll long longll t,n...

2019-01-20 10:17:00 19

原创 C - 树的统计Count - 树链剖分

思路：树剖模板，线段树维护即可。#include<bits/stdc++.h>using namespace std;#define MID int m = (l+r)/2#define maxn 56789#define inf 0x3f3f3f3fint data[maxn],n,m,id[maxn],fa[maxn],u,ans,head[maxn];int...

2019-01-18 12:01:00 22

原创 B - Housewife Wind-树链剖分-树状数组

思路：边权转化到点权上，统一把每一条边的边权集中到深度较深的点上去。#include<stdio.h>#include<iostream>#include<cstring>using namespace std;#define maxn 134567struct edg{ int v,to,w,u;} edge[maxn*2],in[...

2019-01-17 19:14:00 16

原创 Aragorn's Story HDU - 3966 -树剖模板

HDU - 3966思路：树链剖分就是可以把一个路径上的点映射成几段连续的区间上。这样对于连续的区间可以用线段树维护，对于每一段连续的区间都可以通过top [ ]数组很快的找到这段连续区间的头。跳的过程类似于 lca ，但这里要注意的是每一个点只属于一条链。 (重载运算符时要注意 node 一个新的结点，不要乱用*this 指针)#include<bits/stdc...

2019-01-17 14:29:00 27

原创 BZOJ-10-1176: [Balkan2007]Mokia-CDQ第二类应用

思路：按照操作的时间进行分治，这样转化成了时间t ，x坐标，y坐标经典的三维偏序。最初时间就是递增顺序，无需排序直接进行第二维的分治，类似归并排序处理x坐标，在保证x有序的情况下进行更新y坐标的树状数组。求一个 (x1,y1) - (x2,y2)矩形内点的个数，简单容斥一下求[ (1,1) ——(x1-1,y1-1) ]+[ (1,1) ——(x2,y2) ]-[ (1,1) ...

2019-01-17 08:43:00 15

原创 String painter HDU - 2476 -区间DP

HDU - 2476思路：分解问题，先考虑从一个空串染色成 B串的最小花费，区间DP可以解决这个问题具体的就是，当 str [ l ] = = str [ r ]时dp [ L ] [ R ] = min (dp [ L + 1] [ R ],dp [ L ] [ R-1 ] )其他情况可以选择任意一个断点tmp = min ( tmp , dfs ( l ,k ) + dfs ...

2019-01-15 19:51:00 25

原创 GCD Counting-树形DP

GCD Counting思路：预处理每个权值的素因子。问题转化为以同一个素数作为因子最长的链，树形DP求解，ans 由此点的最长子链 + 次长子链相加得到，然后再更新最长子链#include<bits/stdc++.h>using namespace std;#define maxn 234567int pri[maxn+10],n,a[maxn+1...

2019-01-15 11:30:00 34

原创 XOR UVALive - 8512 -区间线性基合并

UVALive - 8512题意 :给出一个包含n个元素的数组A以及一个k，接下来进行q次询问，每次询问给出 l 和 r ，要你求出从A[l] , A[l+1] , A[l + 2],...,A[r]中任选出若干个数异或起来的值val，使得 k | val 最大，输出这个最大值。思路：既然是要使得k | val得到的值最大，那么val必然是k这个数上二进制位为0的位置为1的数，同时1的...

2019-01-15 09:45:00 18

原创 BZOJ-9-3295: [Cqoi2011]动态逆序对

题意：N个数的排列，M次操作，每次求当前的逆序对数量并删掉一个数思路 :动态说的很到位。hiahia ... 最初一直没想明白为什么大佬的cdq 中统计了两次。先定义给出的删除的点的 t 值依次是N,N-1,N-2...(越先删除的视为越后插入的)注意不在询问范围内的点的t值可以任意设置，为了方便按照x从左到右。给没有删除的点 t 值递增赋值。我们求的就是按顺序插入每一个数时，这个...

2019-01-14 16:29:00 14

原创 E - Andrew and Taxi-二分答案-topo判环

E - Andrew and Taxi思路：min max 明显二分答案，二分需要破坏的那些边的中机器人数量最多的那个。check 过程建边时直接忽略掉小于 mid 的边，这样去检验有无环存在即可。当时有一点担心会出现有一个环有一条边反过来之后这个环破坏了却成就了另一个环，但是画图发现这样的图，它们两边会形成一个大环。那个大环一定会通过别的边破坏掉，所以不需要担心这...

2019-01-14 10:52:00 16

原创 Stars HDU - 1541

HDU - 1541思路：二维偏序，一维排序，一维树状数组查询即可。#include<bits/stdc++.h>using namespace std;#define maxn 33333int ans[maxn],n,sum[maxn];int lowbit(int x){ return x&(-x);}struct node{ ...

2019-01-13 20:53:00 16

原创常犯小错误-不断更新

1 . " %f " " %lf "注意切换。2. 结构体排序问题，记得记录 id 操作完后根据题目要求看是否需要按照 id 恢复。3. dp [ ] [ ] 转移时，有时候一个 dp [ i ] [ j ]可能由多个状态转移而来，不要直接赋值，而是累加。4. 二进制运算符优先级较低使用时 ( 加括号 )5.分解素因子时注意特判最后一个来加速6 .递归函数里的变量不要...

2019-01-13 19:38:00 17

原创 Area POJ - 1265 -皮克定理-叉积

AreaPOJ - 1265皮克定理是指一个计算点阵中顶点在格点上的多边形面积公式，该公式可以表示为2S=2a+b-2，其中a表示多边形内部的点数，b表示多边形边界上的点数，S表示多边形的面积。适用范围：必须是格点多边形。S = A / 2 + B - 1#include<stdio.h>#include<cmath>#include<cstri...

2019-01-13 19:34:00 15

原创牛客练习赛37-筱玛的字符串-DP递推

筱玛的字符串思路：dp [ i ] [ j ] [ 3 ] 分别代表到第 i 位时左括号比右括号多 j ，后面有三个状态分别表示当前位置 S3的字符是正在反转的，还是反转完成的，还是没有反转的，根据提议要求反转的只能是一段连续区间，然后转移即可。注意反转完成之后不能再开始一段新的反转过程。#include<bits/stdc++.h>using name...

2019-01-13 17:22:00 15

原创 BZOJ-8-2115: [Wc2011] Xor

https://www.lydsy.com/JudgeOnline/problem.php?id=2115题意：给出一个连通无向图,求从1到n异或和最小的路径.思路：随意找一条简单路径 1-n 的，然后在这个过程中统计出图中的环然后，对这些环的异或值求一下线性基，最后贪心去异或取最值即可。#include<bits/stdc++.h>using namesp...

2019-01-13 11:53:00 30

原创 (Zero XOR Subset)-less-线性基

(Zero XOR Subset)-less题意：把n个数分成多个集合，要求不能有集合为空，最终不能有非空子集合异或值为0，尽可能划分的多一些。思路：非法情况就只有 n个数异或为0，其他的情况集合个数就是线性基的内元素的个数。(因为有基就可以保证不为0，并且不可以再增加元素)基类似极大线性无关组。已经是最大的了，不可以再多。#include<bits/stdc+...

2019-01-13 10:47:00 26

原创 P4781 【模板】拉格朗日插值

P4781【模板】拉格朗日插值证明：https://wenku.baidu.com/view/0f88088a172ded630b1cb6b4.htmlhttp://www.ebola.pro/article/notes/Lagrange#include<bits/stdc++.h>using namespace std;#define mod 998244353#...

2019-01-13 00:13:00 13

原创 BZOJ-7-2655: calc-DP-拉格朗日插值

https://www.lydsy.com/JudgeOnline/problem.php?id=2655以上是对 dp 一小部分打的表。dp[ i ] [ j ]含义为前 i 个数中选 j 个的价值总和 ,则转移方程为dp [ i] [ j ] = dp [ i -1 ] [ j ]+ dp [ i - 1] [ j - 1] * j * i ....

2019-01-13 00:12:00 14

空空如也

空空如也