shyyhs

分类

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

/ 注册

TA的专栏 440篇文章 0人订阅

415篇文章 3901人学习

AtCoder思维大提升

6篇文章 753人学习

kuangbin专题记录

0篇文章 0人学习

牛客每日一题推介(裙子计划~)

19篇文章 848人学习

全部文章（共469篇）

[SCOI2009]最长距离来自专栏

100%的数据,满足1<=N,M<=30,0<=T<=30---来自洛谷的数据范围.简单来说就是暴力,暴力枚举一个点,然后再算到其他点的之间最少需要移除多少障碍物.然后就结束了. #include <bits/stdc++.h> using namespace s...

DFS

2020-09-25

6 908

【SWTR-02】Picking Gifts 来自专栏

直接离线即可.对于每一步都存值即可.(凡是难做的题,都可以考虑离线.)代码如下: #include <bits/stdc++.h> using namespace std; const int N=1e6+5,M=5e5+5; int ans[M],p[N],v[N],l[M],sum[...

树状数组

2020-09-25

4 634

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 684

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 624

[HAOI2008]硬币购物来自专栏

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

容斥原理 DP

2020-09-24

4 681

[SCOI2009]游戏来自专栏

很巧妙的变形...大概cf也有很多,这个题首先是一个排列的关系可能会形成1~n个环..然后就是问你环的大小的lcm,这个可以转化,我们知道lcm可以写成每个质因数的乘积.又有个巧妙的转化了,因为1的存在.我们可以任意分配质因子个数,这样是不影响方案数的(因为到了最后也最多这个值,其他值也会被包含)....

DP

2020-09-23

3 533

最后的晚餐(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 1160

红色的幻想乡来自专栏

树状数组一般都是计数问题,这个题目也不例外,我们可以发现题目讲的很复杂,但是换一种理解方式(或者画图可以知道),行列是可以单独考虑的,单独考虑行列,一行和一列一定是存在交点的,对于两个相同的行/列出现了,就等同于这里没有行/列了,我们只需要维护拿树状数组区间有多少行列就行了.代码如下: #inclu...

树状数组

2020-09-21

2 743

Contest 来自专栏

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

树状数组

2020-09-21

8 779

感想... 来自专栏

老实说牛客的题真的挺不错的,但是题解太少了,萌新做着难受唉............................................................................................................................

日记

2020-09-20

5 580