YZBPXX

分类

acm入门练习(1) c#(1) c++，c实用小函数，操作(20) hash/bkdr hash字符串(2) 动态规划—树形dp(1) 动态规划—背包九讲(7) 单调栈(1) 图论—bfs(2) 图论—dfs(6) 图论—最小生成树(1) 图论—最短单源路径(5) 字符串—ac自动机(1) 字符串—扩展KMP/KMP(4) 字符串—马拉车(1) 带权并查集(2) 拓扑排序(2) 数据库学习(6) 数据结构—RMQ(5) 数据结构—字典树(1) 数据结构--红黑二叉树(1) 数论(8) 未归档(2) 矩阵快速幂(1) 算法分析(3) 网络流(1) 集训题(2) 题解(33)

/ 注册

全部文章（共110篇）

CF Destroying Array

http://codeforces.com/contest/722/problem/C 题目描述给你一串正整数数列 a1,a2,a3......an 每次删除一个元素并且输出此时最大连续子串和首先从前向后删可能比较麻烦些（每个区间肯定要遍历），所以考虑从后向前添元素，每...

思维并查集

2019-08-02

0 571

矩阵快速幂入门

首先理一理快速幂之前总结过但没记录下来首先对于将n看成二进制的形式比如那么以此类推每一位都会判断一遍是否是1 是就乘起来现在在来讲矩阵快速幂：首先现代知识矩阵乘法（直接上代码）： void multi(int a[][MAX],int b[][MAX]){ ...

模版

2019-08-01

0 594

CF Valera and Elections

http://codeforces.com/problemset/problem/369/C 题目描述：给你一棵树，每条边有2,1两种情况每次可以选择一个点走到1点（根节点）问最少选择几个点可以把边是2的点走完分析：加入有一个条边是2 那么只需要找有没有子节点有2的边&nb...

2019-07-31

0 557

单调栈入门

http://codeforces.com/group/xrTA2IaQje/contest/249069/problem/B 首先描述一下单调栈的作用如5 2 1 4 3 从左到右入以递减的方式入栈，遇到大的就出栈，直到栈为空或者出现比它大的数那它就入栈在这个过程中有一个现...

模拟

2019-07-31

0 681

背包02—完全背包

与01不同的点只有一个，就是允许物品多次放入首先分析这个问题得到状态转移方程 dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*w[i]]+v[i]*k); 这是最朴素的方法实现代码： for(i=1;i<=n;i++) { ...

2019-07-31

0 451

欧拉函数欧拉定理及欧拉降幂

欧拉函数表示小于等于x的素数有多少个如几个性质： 1、euler(1)=1（唯一和1互质的数就是1本身）。 2、若n是质数p的k次幂，φ(n) = p^k - p^(k-1) = (p - 1)*p^(k - 1)，因为p为质数，所以与n不互质的数只有p的倍数，一共有p^(k...

2019-07-30

0 1130

背包01

经典问题：有n个物品，分别价值为value，重为volume，放入一个m的背包（保证放满）问如何使得价值最大分析：首先从最后那个状态来看 dp[i][j]=max(dp[i-1],dp[i-1][ j-vo[i] ]+va[i])，起始状态显然是dp[0][j]=0，有了起...

2019-07-30

0 572

CF Mahmoud and a Dictionary

题目描述：给你n个单词，并且有m行每行有一个数字两个单词数字代表之间的关系，2表示意思相反，1表示同义之后有q行询问每行两个单词输出它两的关系 2 ≤ n ≤ 10^5, 1 ≤ m, q ≤ 10^5 分析：典型的带权并差集问题，带1...

2019-07-28

0 473

HDU How Many Answers Are Wrong

题意描述给你 m段区间和表示1->n 问有多少段是不满足条件的？ (1 <= N <= 200000, 1 <= M <= 40000) 题目分析：具有很明显的并查集气息（多种情况矛盾），可以把[1 , 2] 变为(0 , 2] 因为我们要...

2019-07-28

0 541

CF The Door Problem

题目描述：有n个房子起始时有的开有的关，有m个开关每个开关控制几个房间（改变一次全部房子的状态就改变原来开（开->关）或者原来关(关->开）），但一个房间恰好由两个开关控制问能否同时打开n个房子 2 ≤ n ≤ 10^5, 2 ≤ ...

2019-07-28

0 519