Q779’s Blog

note[0] 某个学MO的朋友给我看的题 这题似乎是1994年国家数学集训队选拔考试D1T1 怪不得我做了好久（ upd.20220513 害，他半途而废退役了 题面： 求四个所有的由四个自然数 \(a,b,c,d\) 组成的数组，使数组中任意三个数的乘积除以剩下的一个数余数为 \(1\) 题解： （注：我写的可能有点不太正式，毕竟我只是个OIer） 由题意可得 \(abc \equiv 1 \mod d\) \(abd \equiv 1 \mod c\) \(acd \equiv 1 \mod b\) \(bcd \equiv 1 \mod a\) 可化为 \(d\mid (abc-1)\) \(c\mid (abd-1)\) \(b\mid (acd-1)\) \(a\mid (bcd-1)\) \(\therefore ab\mid (acd-1)(bcd-1) \Rightarrow ab\mid (abc^2d^2-acd-bcd+1)\) \(\therefore ab\mid (acd+bcd-1)\) 同理 \(cd\mid (abc+abd-1)\) \(\...

洛谷P4878 [USACO05DEC]Layout G 题解 题目链接：P4878 [USACO05DEC]Layout G 题意：按编号排了 \(n\) 只奶牛，有的奶牛间必须相距小于等于一个距离，有的奶牛间必须相距大于等于一个距离，问 \(1\) 到 \(n\) 的距离最大值 我们可以发现题目给的数据本质上就是 \(v-u\ge d_i\) 或 \(v-u \le d_i\) 这是什么？差分约束！ 差分约束：根据三角不等式 \(d_u + w(u,v) \ge d_v\) 的构成，我们可以把形如 \(v-u\ge d_i\) 的不等式转化为 \(v-d_i\ge u\) （可以看作 \(v\) 向 \(u\) 连了一条边权为 \(-d_i\) 的有向边），同理 \(v-u \le d_i\) 转化为 \(u+d_i \ge v\) 这里不过多讲解差分约束了 那么为什么差分约束后求最短路就是最大值呢？ 因为求最短路是由无穷大向下不断约束得到的，因此得到的是最大值（同理求最长路就是最小值） 那我们只要按题意建图就行了 要注意的是，每个奶牛 \(i\) 满足 \(d_{i-1...

POJ3723 Conscription 题解 题目链接：POJ3723 Conscription 题意：要招 \(n\) 个女的， \(m\) 个男的，原价 \(10000\)，如果招了关系亲密的（男女）人可以降价，求最小花费 首先，题目给出的格式 \(x_i\ y_i\ d_i\) 很像图论题 我们可以把每个人看作一个结点，为了防止男女编号相同的人搞混了，我们可以让女的编号为 \(1 \sim n\) ，男的编号为 \(n+1 \sim m\) ，显然这题要我们选出所有的结点且花费最小 我们可以发现答案如果存在环则会产生矛盾，例如：a招了b，b招了c，c招了a，这说不通 那是最小生成树吗？不一定 我们可以发现给定的这张图不一定是连通图，而我们要求的是花费最小的树型结构（感性理解下），那么这就是最大权森林问题，同样可以用最小生成树来求解（注：边权设为 \(-d_i\)） 由于不一定是树，所以不需要记录连了多少边 代码如下 #include <cstdio> #include <vector> #include <iostream> #include <...

洛谷P2865 [USACO06NOV]Roadblocks G 题解 题目链接：P2865 [USACO06NOV]Roadblocks G 题意：求结点 \(1\) 到结点 \(n\) 的次短路，所有边有非负权重，边可以重复经过，无向图 如果是求最短路，那么一个dijkstra直接搞定 但是这题要求的是次短路，同样也可以dijkstra解决 我们观察 \(1\) 到 \(v\) 的一条次短路 \(p\) 要么存在 \(1\) 到 \(u\) 的一条最短路 \(k_1\) ，使得 \(k_1\) 加上 \((u,v)\) 等于 \(p\) 要么存在 \(1\) 到 \(u\) 的一条次短路 \(k_2\) ，使得 \(k_2\) 加上 \((u,v)\) 等于 \(p\) 因此我们只需要记录每个结点的最短距离和次短距离即可 （注：由于最短路径可能有多条，但是并不影响结果，因此我们假设只有一条路径） 由于每个结点都可以访问多次，那么怎么防止死循环呢？ 显然对于一个结点，如果在我们的优先队列中将它取出时，我们只要判断它的距离是否大于它的结点的次短距离，如果大于，一定不是次短路 ...

洛谷P1581 A+B Problem（升级版）题解 题目链接：P1581 A+B Problem（升级版） 题意：每一位进制不同，第一位进制为 \(2\) ，第二位进制为 \(3\) ，第 \(i\) 位进制为第 \(i\) 个质数，求A+B 本题就是以普通的高精度加法为基础，改了一下进位的方式而已 这里我用的vector<int>写的高精度 我们可以把每一位的进制打个表，在进位的时候取模就行了 代码如下 #include<bits/stdc++.h> using namespace std; #define int long long #define R register int mod[]={2,3,5,7,11,13,17,19,22}; int t,f=0,len1,len2; vector<int> num1,num2; char ch; signed main() { while(~scanf("%lld%c",&t,&ch)) { if(!f)num...

洛谷P1047 [NOIP2005 普及组] 校门外的树 题解 前言 如何把一道入门题写成省选题？（手动滑稽） 本题解是我在练习分块时突发奇想写的，真就把入门题写成省选题的感觉（ 才发现原来这些简单题这么有趣（ 题目链接： P1047 [NOIP2005 普及组] 校门外的树 题意：马路上砍树，问砍了 \(m\) 次还有几棵树 一、模拟解法（正常解法） 我们只要把每次砍掉的树标记一下，最后统计未标记的数量即可 注意下标从 \(0\) 开始，共 \(n+1\) 个数 代码如下： #include <bits/stdc++.h> using namespace std; #define int long long #define R register #define MAXN (int)(1e4+5) int n,m,ans; bool a[MAXN]; signed main() { scanf("%lld%lld",&n,&m); for(R int i=1,l,r; i<=m; i++) { scanf("%lld...

浅谈珂朵莉树(ODT) 前言 珂学家狂喜（ 一、珂朵莉树来源 珂朵莉树，原名老司机树（Old Driver Tree），在某场CF比赛中提出 因为题目背景是《末日时在做什么？有没有空？可以来拯救吗？》中的珂朵莉，所以就叫珂朵莉树了 二、珂朵莉树 题目链接：CF896C Willem, Chtholly and Seniorious 题目要求维护一种数据结构，支持以下操作 将 \([l,r]\) 区间内所有数加上 \(x\) 将 \([l,r]\) 区间内所有数改成 \(x\) 求 \([l,r]\) 区间第 \(k\) 小的数 求 \([l,r]\) 区间内所有数的 \(x\) 次方的和取模 \(y\) 值得注意的是，数据为随机数据，说明没有故意构造卡的数据 1.珂朵莉树有什么用？ 最主要的就是区间内的推平操作了，即本题中的操作 \(2\) 当然还有别的操作，那就不是最主要的了 2.原理是什么？ 写在前面：这个数据结构唯一前置知识就只有set a.存储 我们可以把区间看作若干个结点，每个结点都有自己的左端点 \(l\) 、右端点 \(r\) 以及值 \(v\) 显然，一开...

裴蜀定理及其证明 一、裴蜀定理 对于 \(x,y\) 的二元一次不定方程 \(ax+by=c\) ，其有解的充要条件为 \(\gcd(a,b)\mid c\) 。 1.充分性证明 充分性 若 \(\gcd(a,b)\mid c\) ，则 \(ax+by=c\) 有解。 证明  设 \(k\) 为 \(a,b\) 线性组合的最小非负解。令 \(q=\left\lfloor\dfrac{a}{k}\right\rfloor\) ，则有 \[ \begin{aligned} r&= a-qk = a-q(ax+by) \\[6pt]&=a(1-qx)+b(-qy) \end{aligned} \] 显然 \(r\) 也为 \(a,b\) 线性组合的解，且 \(0\le r \le k\) 。 由于 \(k\) 为最小非负解，故 \(r = 0\) ，那么 \(k \mid a\) 。同理可得 \(k\mid b\) 。 令 \(d=\gcd(a,b)\) ，则 \(k\mid d\) 且 \(d \ge k\) 。 因为 \(d\mid a,d\mid b\) 且 \...

ubuntu 强制卸载vmware player 不知道什么时候下了vmware-player，然后怎么都删不掉 解决方法 打开终端，输入以下指令 locate vmware-player 然后会出现一大堆vmware player的文件 复制一下，再把每一行都加上 sudo rm或sudo rmdir （注：这里注意一下删除顺序，rmdir似乎不能直接删除非空文件夹） 非常简单，非常暴力，直接删除这些文件 当然如果能正常卸载的话还是这个更好一点 sudo vmware-installer -u vmware-player

浅谈舞蹈链(DLX) 一、舞蹈链 舞蹈链 (Dancing links)，也叫 DLX ，是由 Donald Knuth 提出的数据结构，目的是快速实现他提出的X算法。X算法是一种递归算法，时间复杂度不确定，深度优先，通过回溯寻找精确覆盖问题所有可能的解 （以上摘自维基百科） 舞蹈链的主要思想来源于双向链表 我们设 \(l[x]\) 表示元素 \(x\) 的左指针， \(r[x]\) 表示元素 \(x\) 的右指针 显然，如果想要删除元素 \(x\) ，我们可以做以下操作 r[l[x]]=r[x]; // x左侧的元素的右指针指向x右侧的元素 l[r[x]]=l[x]; // x右侧的元素的左指针指向x左侧的元素 那恢复元素 \(x\) 呢？ 我们可以发现删除 \(x\) 的时候， \(x\) 的左右指针并没有改变，即 \(l[x]\) 和 \(r[x]\) 并没有改变，于是我们可以做以下操作 r[l[x]]=x; // x左侧的元素的右指针重新指向x l[r[x]]=x; // x右侧的元素的左指针重新指向x 这样如果 \(x\) 左右两侧没有改变，我们就可以恢复 \(x\) ...

导数的基本公式推导 主要推导了人教版A版数学选择性必修二上直接给出的基本的导数公式 本文写于作者初三暑假，更新于高一暑假 可能含有很多不足，如果您方便的话可以联系我修改 awa 大概率会在高二暑假再更新一次吧 一、导数的四则运算法则 设 \(f(x),~g(x)\) 均为可导函数 命题：\({[f(x) \pm g(x)]}^{\prime} = f^{\prime}(x) \pm g^{\prime}(x)\) 证明： \[ \begin{aligned} {[f(x) \pm g(x)]}^{\prime}&=\lim\limits_{\Delta x\to 0}{\dfrac{f(x+\Delta x)-f(x) \pm\left[g(x+\Delta x)-g(x)\right]}{\Delta x}} \\\\&=\lim\limits_{\Delta x\to 0}{\dfrac{f(x+\Delta x)-f(x)}{\Delta x}} \pm \lim\limits_{\Delta x\to 0}{\dfrac{g(x+\Delta x)-g(...

蒙提霍尔问题及其推广 前言 蒙提霍尔问题在《人教版A版数学选择性必修三》上作为阅读与思考的材料出现 本文会提供一种简单的解法并推广这个著名的问题 蒙提霍尔问题 一、背景 三门问题（Monty Hall problem）亦称为蒙提霍尔问题、蒙特霍问题或蒙提霍尔悖论，大致出自美国的电视游戏节目Let’s Make a Deal。问题名字来自该节目的主持人蒙提·霍尔（Monty Hall） 二、简介 参赛者会看见三扇关闭了的门，其中一扇的后面有一辆汽车，选中后面有车的那扇门可赢得该汽车，另外两扇门后面则各藏有一只山羊。当参赛者选定了一扇门，但未去开启它的时候，节目主持人开启剩下两扇门的其中一扇，露出其中一只山羊。主持人其后会问参赛者要不要换另一扇仍然关上的门。问题是：换另一扇门是否会增加参赛者赢得汽车的几率 （注：以上摘自百度) 三、分析 题面没什么好说的，我们直接来讨论概率问题 根据直觉，我们可能会有以下两种判断 三扇门中有车的概率都是 \(\dfrac{1}{3}\) ，因此不必换门 既然打开了一扇山羊门，那车在剩下两扇门中的概率都为 \(\dfrac{1}{2}\) ，...