shyyhs

题解

DP专题(52) 图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38)

/ 注册

全部文章 / 题解（共329篇）

List Of Integers 来自专栏

首先我们都会求[1,n]与给定的p互质的个数对吧?用容斥原理,拿n-1个p的质因子+2个p的质因子...这样容斥下去即可.题目是要求大于x第k个与p互质的数.很明显是有单调性的,我们来二分n然后ck一下,假定cnt[n]表示[1,n]与给定的p互质的个数,那么我们是要求大于x的第k个,那么我们直接拿...

二分数论

2020-09-25

5 686

P5482 [JLOI2011]不等式组来自专栏

毒瘤题,注意下正数负数的取值就好了... #include <bits/stdc++.h> using namespace std; const int N=2e6+5,M=10,base=1e6+1; char s[M];int pos[N/10],sum[N],id,vis[N/10...

树状数组

2020-09-24

3 625

[HAOI2008]硬币购物来自专栏

讲真的看到题,我都没想容斥原理...是我太菜了吗.首先拿个完全背包进行预处理.然后我们来观察下完全背包的含义.什么含义呢,就是你每个物品都任意取,在容量为x的情况下的方案数.假定我们对于其中的一个做出了限制,那么方案数会不会减少呢>?显然是会的,因为有限制嘛~会减少多少呢...其实假设我们只能...

容斥原理 DP

2020-09-24

4 683

最后的晚餐(dinner) 来自专栏

首先因为是个环,我们得先随机分配一个确定起点,然后剩下的方案总数是(2*n-1)!.然后就是我们的容斥原理了,0个相邻的-1个相邻的+2个相邻的-3+4... 0个相邻的答案就是(2*n-1)! 1个相邻的答案是2*C(n,1)*(2*n-2)!.对于这个的解释就是你n对中选取1对,然后前后顺序考虑...

容斥原理

2020-09-22

9 1162

Contest 来自专栏

原来这题是每日一题......?这题可以用树状数组求逆序对解决,首先我们可以知道..我们把其中一维排序,另外一维按第一维的顺序插入就会产生一组答案.对于可计数的答案来说,我们考虑两种,第一种是我第一维大于它的第二维,我的第二维小于它的第二维,第三维未知但是算出来的答案重复次数只会是1,因为第三维可能...

树状数组

2020-09-21

8 779

Numbers 来自专栏

直接dfs即可...emmm好水,好了,学树状数组线段树去了...ggg #include <bits/stdc++.h> using namespace std; const int N=100; string s; int vis[N],ans; void dfs(int u,in...

DFS

2020-09-18

2 641

2019 来自专栏

一个计数问题,下次看到数据就直接dp吧.有点分治思想在里面.就是一个点一个点的计数,一条链一条链的来,f[i][j]表示到了i这个点值为j的方案数...如此转移下就好了. #include <bits/stdc++.h> using namespace std; const int N=...

树形dp

2020-09-18

6 790

Tufurama 来自专栏

直接按题意模拟计数即可,拿个单调栈和树状数组维护下...题目不是求二元组的数量吗?i<j&&ai>=j&&aj>=i.这是一个二维问题对吧,我们一维一维的解决.首先对于ai>n的直接取n就好,因为n一定是满足条件的.然后我们令val和id,字面...

树状数组

2020-09-18

2 875

array 来自专栏

#include <bits/stdc++.h> using namespace std; const int N=1e5+5; const int inf=2e9; struct vv{ int l,r,id; }tree[N<<2]; int a[N]; void...

线段树

2020-09-16

2 577

子串来自专栏

不会数据结构的人去理解真ri gou #include <bits/stdc++.h> using namespace std; const int N=1e6+5; int n,sum[N]; int lowbit(int x) { return x&(-x); } s...

树状数组

2020-09-14

2 642