2023.10笔记2023 10

#### ARC058D 首先有一个 $n\times m$ 的矩阵，从左上走到右下的方案数是 $C_{n+m-2}^{n-1}$. 考虑把原图切分成两个矩阵。（左上和右整边） 计算出走到左上角的矩阵边上每个点的方案数，再乘上这个点走到右下的方案数，求和即可。 #### ARC058E 发现题目条件 ......

# 第八周周报(2023/7/31 - 2023/8/6) ## 本周总结 本周按暑期集训的专题进行练习，同时在准备Tarjan专题，对Tarjan专题进行了初步的学习 ## 大方向 数论，动态规划，Tarjan算法 ## 小专题 矩阵，高斯消元，线性基，GCD，逆元，裴蜀定理，记忆化搜索，数位dp ......

这是等了好久的笔记了。 斜率优化一直是我 OI 中的一个大坑，我刚接触它的时候是在 摆渡车 这题，看到斜率凸包啥的，那时候我才是六年级，十分的不理解，于是一直觉得它十分困难。 暑假终于迎来了转机，NLFS 讲 DP 优化那天顺便讲了下斜率优化，终于大悟，乃写此文章，供复习等用。 先来看一道题： 斜率 ......

发现之前学的真的一塌糊涂呢(*/ω＼*) 很多非常精髓的地方理解的都不够好，比如说为啥我要用一棵 dfs 树来为框架，跑 tarjan？这里我就理解的不好，所以我来重新写一篇，加深加深印象。 以下一切默认为无向图。 ### 0. 基本概念 这里面说的非常不严谨，只是为了方便理解啦 awa - 连通分 ......

## 概述 主要是求以下三个式子： $$f(a,b,c,n)=\sum_{i=0}^n \left\lfloor\dfrac{ai+b}{c}\right\rfloor$$ $$g(a,b,c,n)=\sum_{i=0}^n i\left\lfloor\dfrac{ai+b}{c}\right\rf ......

注意，下面的运算都是在模意义下进行的。 给定 $n$，求 $x^2\equiv n$ $x$ 存在条件为 $n^{\frac {p-1}2}=1$，证明用费马小定理，略。 如何求出 $x$，随机一个 **不存在** 二次剩余的值 $a^2-n$，设为 $w^2$ 这里可以把 $w$ 理解为一个虚数。 ......

前几个月忙着拯救地球所以有比较长时间的空档 这次笔记对应的是games101内容的第六课，至于为什么跳过第五课因为第五课我感觉也没啥需要记笔记的，基本就是光栅化的一些基本概念以及最基本的一些实现理念，视频最后讲到了关于锯齿和走样的一些东西，第六课开头即紧接着这部分进行讲解 采样是光栅化过程中普遍需要 ......

太菜了。 #### T1 求 $$\sum_{L\le a\le b\le R}\lbrack b\space mod\space a=b\space xor\space a\rbrack$$ 值域 $1e18$ . 枚举余数能得到 $\lfloor\frac{b}{a}\rfloor=1$ . 那 ......

### T1 $P$ 是任意一个 $1$ 至 $n$ 的排列，最大化 $$\sum_{i=1}^{n}P_i\space\text{mod}\space i$$ 答案显然 $\frac{n(n+1)}{2}$ . ### T2 一棵有根树，多次操作，给一颗子树中的节点增加权值。 板。 ### T3 ......

### T1 已知 $a,b$ 为互素的正整数，求最大的 $k$， $$ax+by=k$$ 无非负整数解。 [P3951 [NOIP2017 提高组] 小凯的疑惑 / [蓝桥杯 2013 省] 买不到的数目](https://www.luogu.com.cn/problem/P3951) 小丑，答案 ......

### T1 已知 $\gcd(a,b)=G,\text{lcm}(a,b)=L$，求 $\min\{a+b\}$，无解 $-1$. $1\le T\le 5$，$1\le G,L\le 10^{12}$. 无解即当 $G\not|\space L$. 有 $$\frac{a}{G}\cdot\fr ......

### A 求把一张无向图的所有边变为有向边，使得各点出度为 $1$ 的方案数。 答案对 $998244353$ 取模。 $1\le n,m\le 2\times 10^5$. 首先一定有 $n=m$，然后环上的边有两种取法。 把环数找出来，然后判断这个连通块中 $E$ 是否等于 $2V$. ``` ......

### A 排队打水，$n$ 个人，$m$ 个水龙头，最小化总时间。 显然是一个 trival 的贪心。 ```cpp #include #define N 1010 #define pii pair #define mp make_pair #define fi first #define se ......

#### A 01 矩阵，每次可以对一个子矩阵取反，问最少多少次操作后，存在一条只向下或右走，只经过 0，从左上角到右下角的路径。 $n,m\le 1000$. 这个 dp 还是非常 trival 的。 ```cpp #include #define N 1010 #define inf (11?f ......

难啊，很难啊（悲） ### A [Mode](https://codeforces.com/gym/104337/problem/B) 记 $f(x)$ 为数字串 $x$ 中数码众数的出现次数。 求 $\sum_{i=l}^{r}f(i)$. $1\le T\le 10^3$，$1\le l,r\l ......

### T1 一个排列，求所有区间第二大。 只需要求出位置 $i$ 的左边第一大和第二大即可，右边同理。 二分 + $\text{ST}$ 乱搞。 ### T2 每次选择一个 $i$，代价增加 $h_{i-1}+h_i+h_{i+1}$，且令 $h_i\rightarrow0$. 操作进行 $n$ ......

先看个很逆天的图。  不好玩。 罚坐到 1：59，发现炸了，听说延到 4 点，先去睡觉。 睡醒后开题，A 是个很简 ......

[P2163 [SHOI2007] 园丁的烦恼 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P2163) 这个是二维数点的板子题，二维数点这一类题目就是上面的题所描述的，我们用树状数组 + 离散化来解决这个问题 ......

1 #对于int数据类型 2 age int; 3 4 #对于double数据类型，并且保留n位小数 5 score double(总长度 = 整数位数+小数位数，小数点后要保留的位数); 6 7 #对于生日等日期类 8 birthday data; 9 10 #对于字符类型 11 name var ......

洛希极限（Roche limit）是一个天体自身的引力与第二个天体造成的潮汐力相等时的距离。当两个天体的距离少于洛希极限，天体就会倾向碎散，继而成为第二个天体的环。它以首位计算这个极限的人爱德华·洛希命名。（摘自百度百科） 大天体密度与小天体的密度的比值开 3 次方后，再乘以大天体的半径以及一个倍数 ......

## 日常做题 ### 1. [P4198 楼房重建](https://www.luogu.com.cn/problem/P4198) 非常离谱的线段树题，反正我当时看了标签是想不出来怎么线段树的。题意就是求斜率单调上升的序列长度（以下简称该序列为答案序列）。好，我们尽力地去想一下线段树怎么做。同样 ......

# 【狂神说Java】Java零基础学习笔记-Java方法 ## Java方法01：何谓方法? - System.out.println()，那么它是什么呢? - Java方法是语句的集合，它们在一起执行一个功能。 - 方法是解决一类问题的步骤的有序组合 - 方法包含于类或对象中 - 方法在程序中被 ......

# 博弈论 ## 公平组合游戏 > 公平组合游戏（Impartial Game）的定义如下： $\bullet$ 游戏有两个人参与，二者轮流做出决策，双方均知道游戏的完整信息； $\bullet$ 任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关； $\bullet$ ......

2023-08-06：小青蛙住在一条河边, 它想到河对岸的学校去学习 小青蛙打算经过河里 的石头跳到对岸 河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上 给定一个长度为n的数组arr，表示每块儿石头的高度数值 每块石头有一个高度, 每次小青蛙从一块石头起跳 这块石头的高度就会下降 ......

### 前言  本人是自费购买积木，购买原因是给妹妹培养动手能力，减少短视频占用时间，其次是给家里做摆饰，所以选择 ......

所有题都是向[这篇博客学的](https://www.cnblogs.com/PYWBKTDA/p/17298141.html)，orz。 ### *loj3934. 「USACO 2023.1 Platinum」Tractor Paths 首先可以观察到，对于节点 $x$，$x$ 能通过 $k$ ......

惊闻vim作者 Bram Moolenaar 去世，享年 62 岁。 唉，这vim还没学会，太遗憾了。。。几十年致力于这么伟大的工具开发，令人敬佩。致敬。 个人从vim大致入门后，使用了基本配置 vim操作体验来看，vim是在Linux等命令行界面，以及鼠标还未普及的情况下，使得通过纯键盘操作达到十 ......

ABC313，逆天 为了 ABC313G，来学一下最简单形式的类欧算法。 类欧几里得算法似乎和欧几里得唯一的共性是复杂度证明。 形式化的，我们需要计算 $f(a,b,c,n)=\sum_{i=0}^n\lfloor \dfrac{ai+b}{c}\rfloor$。 首先，如果 $a\ge c$ 或者 ......

![image.png](https://cdn.nlark.com/yuque/0/2022/png/25419362/1654587921123-a89cc649-83cb-4219-8cfd-d7b852a0ff2a.png#averageHue=%23dcdbdb&clientId=u793 ......

python的数据模型：python风格的设计思想完全体现在Python的数据模型上，而数据模型所描述的API，为使用最地道的语言特性来构建你自己的对象提供了工具。数据模型其实是对 Python 框架的描述，它规范了这门语言自身构建模块的接口，这些模块包括但不限于序列、迭代器、函数、类和上下文管理器 ......