猫萌

题解

未归档(1) 读书笔记(1)

/ 注册

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

题解 | #A Simple Problem with Integers#

这其实是个结论题，猜到结论后就不需要脑子了首先直接报结论，2018以下的数字的平方对2018取余存在一个长度为6的循环节，这个结论得出我们可以直接暴力去验证，重要的是我们怎么想到它，首先让我们回忆下扩展欧拉定理 ab mod c=abmod φ(c)+φ(c) mod ca^{b} \bmod...

2022-08-26

1 505

题解 | #回文子序列计数#

定义状态dpi,jdp_{i,j}dpi,j,代表以iii位字符为中心,111到i−1i-1i−1的子序列与从第jjj位的字符为开头的jjj到nnn中的子序列构成回文的方案数那么当第jjj位与第i−1i-1i−1位匹配的时候,dpi,j=∑k=j+1k=lendpi−1,j+1dp_{i,j}=...

2022-08-16

1 368

题解 | #wyh的吃鸡#

Bfs入门题具体思路为，从起点到终点有两种走法一种是直接步行从起点走到终点一种是先步行到某辆车的位置，再走到终点由于n<=100，一次bfs的复杂为O(n2)O(n^2)O(n2),T<=10,汽车的数量又小于100，可以算出最坏时间复杂度为1e7左右，轻松过时限我们可以先算出...

2022-07-02

0 714

题解 | #异或和#

异或运算满足交换律，所以我们把所有数字异或起来就好，偶数的会自己异或成0，而0异或任何数字都是其本身。 #include<bits/stdc++.h> using namespace std; int main() { int n;scanf("%d",&n); ...

2022-03-11

1 433

题解 | #Forsaken喜欢玩自走棋#

经典SOS dp问题。考虑到本题源自小白月赛，可能出题人本意也是给大伙介绍介绍科技，那我就简单来讲下什么是SOS dp。如果觉得自己的英文还过的去的话强烈推荐阅读SOSdp出处的这篇博客 SOS指的是the Sum over Subsets，即子集的求和，该算法就是用动态规划的方法来快速求解如下问...

2022-03-11

0 412

题解 | #Forsaken遇到了毒瘤#

在做本题之前你需要掌握的快速幂与逆元欧拉筛与线性求约数和数论分块一点点的数学推导能力现在开始推导 n mod d+m mod d≥d⟺n−d⌊nd⌋+m−d⌊md⌋≥d⟺⌊nd⌋+⌊md⌋+1≥⌊n+md⌋\begin{aligned} &n \bmod d+m...

2022-03-10

0 329

题解 | #文艺平衡树#

板子题，FHQ-treap秒杀只要将懒标记定义为翻转所有数即可 #include<bits/stdc++.h> using namespace std; using ll = long long ; const int M=2e5+10; ll cnt,x,y,z,root; stru...

2022-03-09

0 404

题解 | #Forsaken给学生分组#

比较简单的一题，只要注意下有几种情况即可第一种，每个组都能拥有两个或两个以上的学生第二种，只有部分组有。那么我们考虑到底有几个组能获得两个以上的，那不就是先分配一个给他们再分配两个。那么假如有十个学生分配7组，我们就可以知道有3组是有两个的，但如果是10个学生分配三组，那么必然每组都两个朝上...

2022-03-09

0 571

题解 | #Forsaken的数列#

平衡树板子题，随便整个平衡树都能做。下面是代码，用的是FHQ treap，核心是维护一个节点下所有节点的总和与个数，还有懒标记，区间加就拆开来维护中间那颗树的头节点，插入就是拆开来然后加入一个树再合并，区间查询就不用我多说了吧。 #include<bits/stdc++.h> usin...

2022-03-09

0 400

题解 | #【模板】同余方程#

简单的模板题。利用扩展欧几里得即可求。首先，你要知道在初等数论里，我们把a和b的最大公约数记错记作(a,b)，把b可被a整除记作a|b,把b不可被a整除记作a∤b 扩展欧几里得的证明需要用翡蜀定理对任意的正整数a b，必然存在x y，使得ax+by=(a,b) 若b=0，那么（a,b）=a。此...

C++

2021-10-27

2 566