〇、引言 大家久等的第二期来辣！ 本期要讲述如何用程序来解答数独题目！实际上这个解法涉及算法，需要大家用一定的时间了解一下时间复杂度和搜索算法（与回溯）！ 本期可能内容较复杂且枯燥，请耐心学习。 本期关键词汇：暴力枚举算法、时间复杂度、可行性剪枝（广义） 本文为课后总结，除个人解释和思路外，内容均为上课老师讲解提供，请勿转载！！ 一、暴力枚举法枚举可能答案 众所周知电脑的运行速度很快（伪，理由见下文），所以对于一个数独题目，我们最暴力的方法就是直接把所有可能全部列出来，然后判断每种情况对不对。 我们先设置一个按钮ans，表示点击按钮就会自动填...

〇、引言 QwQ 我们即将用 Python 写一个GUI图形界面数独！（第一部分） 设计效果： 关键词汇：tkinter库、python方法判重、GUI界面简单设计 本文为课后总结，除个人解释和思路外，内容均为上课老师讲解提供，请勿转载！！ 一、tkinter库及数独界面设计 1.GUI界面创建 tkinter，一个神奇的东西。Python自带的控件，只需要调用： import tkinter as tk 我们首先要创建一个图形界面的根界面。我们可以： root = tk.Tk() root.title("数独游戏&qu...

复习 配合yizimi的板子库食用效果更佳。 前言 高中过后一直没有复习，大一要打天梯赛时才想起来复习。这个是个人的算法复习过程，尽量按照顺序进行复习，主要顺序是按照我自己的板子库的顺序复习。也算是对板子库的一个解释吧。 一、数论 1.快速幂 主要的思路就是分治，当幂数过大时，一般采用幂数2进制寻找幂数底数相乘。时间复杂度\(O(logn)\) 2.欧拉函数 欧拉函数\(\varphi(x)\) 返回的是小于x的自然数中与x互质的数的个数，我们有： \[\varphi(x) = x * \prod_{i = 1}^{n} (1 - p_i)...

主要思路：Dijkstra + DP 如果做过最短路计数，这道题就相当于双倍经验了。 就是在跑Dijkstra时，另计一个 \(t_i\) 作为到第 \(i\) 个点时最短路的条数，一个 \(rs_i\) 作为到第 \(i\) 个点最短路点权和的最大值 注意一下维护条数时要分类，是不是 \(dis\) 更新了，更新了要用新值覆盖掉之前的数值。 还有，点的编号 \(0\) ~ \(n-1\)，边是双向边，千万别搞错了 部分代码： struct wtf{ int t,r,rs; }r[505]; struct node{ int u,d; friend b...

若转载请注明出处！！！ GSS1 —— GSS8 简述做法加代码。 GSS1 给出了序列\(A[1]\)，\(A[2]\)，…，\(A[N]\)。 \((a[i]≤15007,1≤N≤50000)\)。查询定义如下： 查询\((x,y)=max\{a[i]+a[i+1]+...+a[j];x≤i≤j≤y\}\)。 给定M个查询，程序必须输出这些查询的结果。 思路： 我们维护四个值： sum, lsum, rsum, msum 然后进行更新，静态查询即可。 具体讲解见 这里了啦 code: #include <algorithm> #...

首先纠正：题目描述中应该是dx - y（这个式子本应该是从原题中证出来的） 题目描述： 给定一个平面上的一些有向边，每条边涂色费用为 \(dx-y\) ， 其中 \(d\) 为边的长度（实数）， \(x,y\) 为题中给定参数。环路的涂色费用为其上各边涂色费用和。找出一些环路，这些环路没有边相交，且环路涂色费用总和最大。 数据范围： 点数 \(n <= 100\)， \(x, y <= 1000\) 主要思路：最大费用循环流 对于最大费用循环流问题，我们先转化成最小费用循环流问题，这样便于套我们所学过的最小费用最大流模板。 转化： ...

题目简述 有 n 个插座，m 个设备和 k (n, m, k ≤ 100) 种转换器，每种转换器有无限多。已知每个插座的类型，每个设备的插头类型，以及每种转换器的插座类型和插头类型。插头和插座类型都用不超过 2424 个字母表示，插座只能插到类型名称相同的插座中。 例如，有 4 个插座，类型分别为 A，B，C，D；有 5 个设备，插头类型分别为 B，C，B，B，X；还有三种转换器，分别是 B->X，X->A 和 X->D。这里用 B -> X 表示插座类型为 B，插头类型为 X，因此一个插座类型为 B 的设备插上这种转换器之后就 “变成” 了一个插头类型为 ...

题目描述 Bytetown城市要进行市长竞选，所有的选民可以畅所欲言地对竞选市长的候选人发表言论。为了统一管理，城市委员会为选民准备了一个张贴海报的electoral墙。 张贴规则如下： electoral墙是一个长度为N个单位的长方形，每个单位记为一个格子； 所有张贴的海报的高度必须与electoral墙的高度一致的； 每张海报以“A B”表示，即从第A个格子到第B个格子张贴海报； 后贴的海报可以覆盖前面已贴的海报或部分海报。 现在请你判断，张贴完所有海报后，在ele...

题目描述 有一个r行c列的全0矩阵，有以下三种操作。 1 X1 Y1 X2 Y2 v 子矩阵（X1,Y1,X2,Y2）的元素加v 2 X1 Y1 X2 Y2 v 子矩阵（X1,Y1,X2,Y2）的元素变为v 3 X1 Y1 X2 Y2 查询子矩阵（X1,Y1,X2,Y2）的和，最大值，最小值 子矩阵（X1,Y1,X2,Y2）满足X1<=X<=X2 Y1<=Y<=Y2的所有元素（X1,Y2）。 输入保证和不超过10^9 追加翻译： 数据范围：r <= 20...

题目简述： 给出n个数q个询问。对于query（a，b），输出区间（a，b）的数的最小值；对于shift（a0，a1，a2，......，an），则将第a1个数的值赋给a0，第a2个数赋给a1......，第an个数赋给an-1，第a0个数赋给an 主要思路：三叉 线段树 （单点修改，区间求最值） 其实就是一道比较裸的线段树模板题，因为题目中shift操作的字符长不超过30 char，也就是说没几个数，我们完全可以直接暴力的每个操作。 我们可以用一个数组a[]来存储原数组，这样便于交换位置时直接赋值。记得把一开始的值先存下来QAQ 然后比较麻烦的就是字符串的操作，...

题目大意 维护一种数据结构，资磁三种操作。 1.在p位置插入一个字符串s 2.从p位置开始删除长度为c的字符串 3.输出第v个历史版本中从p位置开始的长度为c的字符串1≤n≤50000，所有字符串总长度小于等于10^6，输出字符串总长度小于等于20000 强制在线，每次输入中的数字都要减去你的所有输出中字母c的个数 思路 #1：可持久化FHQ Treap （如果你懒得打一大长串的代码，就去看思路#2） 不难看出，这是一道可持久化FHQ Treap的模板题，就是在插入时要O(n)建树，要不会TLE 我们可以直接用一个递归函数build来解决 ...

题目 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度（雷达给出的高度数据是 \le 50000≤50000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 数据范围： 子问题1：n <= 1000 子问题2：n <= 100000 思路：序列DP + 线段树...

有时间就会更新QwQ 例题难度随更新时间可能增大 例题顺序按照更新时间排序的哦QuQ 特别鸣谢 长江东逝水 对本Blog的建议与指正！ 目录： 1.区间DP 例题1：P2858 奶牛零食 例题2：P3146 [USACO16OPEN]248 / P3147 [USACO16OPEN]262144 例题3：P3205 [HNOI2010]合唱队 例题4：P4170 [CQOI2007]涂色 例题5：P1880 [NOI1995]石子合并 2.前缀DP 例题1：P3628 【APIO2010】特别行动队（ O(n ^ 2) ） 例题2：P1944 最长括...

题目描述 有n个函数，分别为F1,F2,...,Fn。定义Fi(x)=Aix^2+Bix+Ci (x∈N*)。给定这些Ai、Bi和Ci，请求出所有函数的所有函数值中最小的m个（如有重复的要输出多个）。 输入输出格式 输入格式： 输入数据：第一行输入两个正整数n和m。以下n行每行三个正整数，其中第i行的三个数分别位Ai、Bi和Ci。Ai<=10，Bi<=100，Ci<=10 000。 输出格式： 输出数据：输出将这n个函数所有可以生成的函数值排序后的前m个元素。这m个数应该输出到一行，用空格隔开。 输入输出样例 输入样例#1： ...