shyyhs

题解

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

/ 注册

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

G - Count Sequences

考虑差分. b1=a1,bi=ai−ai−1,bn+1=m−anb_1=a_1,b_i=a_i-a_{i-1},b_{n+1}=m-a_nb1=a1,bi=ai−ai−1,bn+1=m−an. 对于bib_ibi%333来说. 显然除了第111项和第n+1n+1n+1项可以是任意模3...

组合数学差分

2022-11-11

0 569

《人间油物》

在利用卷积使得各项相乘的时候,由于顺序会被交换,所以b数组要倒序输入,可以看成是两个卷积之间的配对. 画个图就懂了~ code: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int...

fft

2022-09-01

0 730

多重集下的组合数

与多重集的排列数不同组合数即是不含有相同数交换的数. 并不是很难. Devu and Flowers 题面翻译 Devu 有 nnn 个花瓶，第 iii 个花瓶里有 fif_ifi 朵花。他现在要选择 sss 朵花。你需要求出有多少种方案。两种方案不同当且仅当两种方案中至少有一个花瓶选择花的数量...

容斥

2022-09-01

0 653

G - Yet Another RGB Sequence

数学不好的记录一下. 题目是给定R,G,BR,G,BR,G,B的数量.然后给你一个kkk,要求字符串中有kkk个RGRGRG的方案数. 考虑先放G,B,RGG,B,RGG,B,RG,最后补RRR. 考虑先放的方案数就是(numG+numB)!/(numG−k)!∗(numB)!∗(k)!(num_G...

2022-08-31

0 749

D. MEX Tree 来自专栏

一些我不会做的题,加上没有正常题解...就会变得very hard. 其实并没有多难. 这个先容斥一下,然后lca分三种情况讨论就好了. 贴个智商代码: using namespace std; typedef long long ll; typedef unsigned long long ull...

思维题

2022-04-25

0 558

E. Bored Bakry 来自专栏

陷入思维误区的一个题目. 首先肯定知道的是一定是最高位全为111,而且长度为偶数是最优,且前面的位异或和为000. 那么我在解这个题的时候,因为使用了局部最优,从而忽视了某些情况,导致一直wawawa而且无法理解别人的代码. 其实这个不能使用dpdpdp.而应该使用贪心. 怎么贪,记录当前位的1的数...

思维

2022-04-25

0 398

Coloring 来自专栏

好难的题目啊！写个博客记录一下. 首先显然满足要求的一定是相邻行取反或者列取反的矩阵.画下图可推出来. 然后,分别考虑行列肯定是2^n,和2^m,可以看成确定一排后面的都确定了,也可以看成每一排都有两种选法. 然后考虑修改...和去重重复即是两种情况都满足的,其实只有两种取法,即是黑白染色,确定...

思维题

2022-04-21

0 506

题解 | #游戏# 来自专栏

本来一开始就写完了... 可惜读错题了,我读的题更复杂一点点... 所以越写到后面脑子越晕... 直接导致后面调傻了,在原代码上. 我读的题里面他是每一轮都可以出它集合里面的东西.而不是固定一种. 两者处理方法是一样的,但是前者更为复杂? 好了... 考虑第iii个人怎么才能赢,那么就是第iii个人...

C++

2022-04-16

0 443

牛牛的方格图来自专栏

感觉自己在降智... 一开始写c想二分,二分半天也没二分出什么...最后是枚举. 想e的时候一直想偏序,我不知道正解是啥,最后写完我的想法刚好没时间了..当然还没调qwq 介绍下自己的想法,将方格的横坐标看成是时间,然后在维护时间的一个优先队列,假如现在的时间要大于优先队列对头的时间,那么对头就要去...

排序

2022-04-08

0 516

异度之刃

首先考虑贡献如何算? 比如1 2 3 4 5 2 3 4,很显然的一个算就是把2 3 4去掉,然后只求1 2 3 4 5的贡献. 考虑i以及相邻的一段的贡献,很显然i的贡献就是相邻一段的长度,比如说1 2 3,1的贡献是1,2的贡献是2,3的贡献是3. 知道贡献怎么算了,下面就分为几步解决这个问题....

线段树

2022-04-07

4 420