JILIN.-CSDN博客

原创《算法竞赛入门经典(第2版)》——学习记录

这里主要记录本人在学习紫书过程中充分理解过的题目的AC代码，便于以后回顾时查找代码和思路，毕竟看别人的真的有点难懂。此外，本书的其它知识学习也可能在此留下记录。不太懂怎么分类，我就根据章节标题以及代码重点来分类了。第三章数组和字符串书中编号题目编号标题分类备注例题3-1UVA272Tex Quotes字符串水题例题3-2UVA10082W...

2020-02-19 12:38:12 1527 4

原创例题 9-27 方块消除（Blocks, UVa10559）

先将最右边同色的特意挑选出来，得到p∈[i,j]中最左边的使得a[p]=a[p+1]=…=a[j]的值，即从右边界j位置往左到p位置是同色的最长段。如果[i,p-1]段中仍有与a[j]同色的段，可以找到q满足q

2022-07-17 10:01:03 679 1

原创例题 9-26 一个调度问题（A Scheduling Problem，UVa1380）

原题链接：https://vjudge.net/problem/UVA-1380分类：树形DP备注：树的性质题意：每次输入是一棵树，其中有有向边和无向边。根据拓扑顺序将树上的点全部消除，也就是入度为0的点才能被消除，问最少需要几步能消除完所有点。同时注意，无向边连接的两个点不能同时被消除。因此问题可以转化为对每一条无向边选择一个方向来对点进行消除。因为是树的结构，所以答案的范围很特殊。设忽视无向边时的最长有向链的边数为k（边数为节点数-1），那么把无向边定好方向后答案必定是k+1或k+2。在紫书中是这么

2022-07-03 18:36:55 228

原创关于Oracle使用Mybatis @Delete注解返回为0但不报错的问题

在某些表类似这样根据主键删除的写法能成功，但某些表不能。这种情况，毫无疑问一定是传入的参数String和数据库的列属性不匹配，可能忽略了空格占据的长度。因为在sqldeveloper或者sqlplus里面的SQL语句不是这么严格的匹配也是可以执行的，很可能会忽略这个问题。...

2022-01-27 12:29:39 1738

原创在doGet方法中连接数据库出现oracle驱动异常：java.lang.ClassNotFoundException: oracle.jdbc.driver.OracleDriver

Class.forName(“oracle.jdbc.driver.OracleDriver”);问题：如果是正常配置,从磁盘中导入的jar包可以在一般文件中运行，但是在浏览器访问时会出错。解决方案是把磁盘中的jar包复制到webapp/WEB-INFO/lib下面，从这里直接导入Add As Library。如果是从Project Structure的Modules或Libraries导入，但是没在lib中是不行的。或者可以从Project Structure的Artifacts导入，将Avail

2022-01-22 15:24:37 1021

原创 Codeforces Round #765 (Div. 2) C. Road Optimization

题目链接：https://codeforces.com/contest/1625/problem/C一开始思路是想dp[i][j]，去除的站的数目为i个，终点站为第j个站（站从0开始数，令终点站为第n个），0站和n站是不能被去除的。然后发现不知道dp[i-1][j-1]最后去除的站是哪一个就算不出dp[i][j]，然后变成dp[i][j][k]，k表示最后去除的站。然后又发现之前去除的站是有关联的，如果最后去除的站为k站，k-1站是什么状态就不知道了。那就把k的含义改成左边第一个没有去除的站。调试一会

2022-01-12 22:36:17 258

原创 Codeforces Round #764 (Div. 3) G. MinOr Tree

题目链接：https://codeforces.com/contest/1624/problem/G题意简述：给定一个图，求其中的一棵树，保证所有节点联通，使得树的所有边权或值最小。题解：并查集+位处理。因为最终结果是根据或操作决定的，显然希望高位尽可能没有。所以可以从高位向低位遍历，去除掉当前位为1的所有边获取一个缩小后的子图。如果缩小后的子图不满足其中存在树使得所有节点连通，说明该比特位要加入到答案中；否则该缩小子图合法可以进行传递下去。#include <bits/stdc++.h>

2022-01-11 22:57:15 302

原创 HDU 1827 Summer Holiday (Tarjan + 缩点)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1827思路：求出所有的SCC，将一个SCC看作一个节点，取入度为0的SCC数量为联系人数，每个入度为0的SCC中取花费最小者加到答案中。Tarjan同样是求SCC的算法，比起Kosaraju更为高级，虽然同样是O(V+E)，但是常数更小。原理是，利用和求割点相同的方法，最远祖先相同的点属于同一个SCC之中。#include <bits/stdc++.h>using namespace std;

2021-11-27 22:37:25 131

原创 HDU 1269 迷宫城堡（Kosaraju）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1269题意：给一个有向图，判断是否为强连通图。Kosaraju是罗永军老师的算法竞赛书介绍的求DAG的SCC数量的初级算法。SCC是强连通分量的缩写，即极大连通分量。实现方法是给原图G建立一个反向图rG，即每条边方向取反生成的图。首先对原图G进行一遍DFS，获取原图G的拓扑序列，然后按照拓扑序列的逆序对反向图rG进行DFS，则后者DFS的次数就是SCC的数目。主要原理是，反向图不改变原图的强连通性，G和r

2021-11-27 21:41:24 252

原创 Codeforces Global Round 17 D. Not Quite Lee （裴蜀定理）

题目链接：https://codeforces.com/contest/1610/problem/D贝祖定理：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。n个整数间的裴蜀定理设a1,a2,a3,...,ana_1,a_2,a_3,...,a_na1,a2,a3,...,an为n个整数，ddd是它们的最大公约数，那么存在整数x1,...,xnx_1,...,x_nx1,...,xn使得x1∗a

2021-11-24 15:31:53 776

原创 Codeforces Round #717 (Div. 2) D. Cut（倍增）

题目链接：https://codeforces.com/problemset/problem/1516/D从右往左，记录当前位置数最近的不互质数的位置，设当前位置为l，标记最近位置为go[l]，那么从go[l]到l这一块可以被分出来。（注意：go[l] >= go[l - 1]）这样就可以每次询问时，从最右边开始跳，x = r, x = go[x]直到x<l，但是这么跳很可能会超时，比如整个序列所有的数都是一样的。这里用倍增的思想，dp[i][x]表示从x位置连续跳(1<<i)次

2021-11-24 09:29:52 140

原创 Codeforces Round #592 (Div. 2) D. Paint the Tree

题目链接：https://codeforces.com/problemset/problem/1244/D类似二分图，这里有的要求是，任意连续的三个节点，颜色不能一样，那么只有当这棵树为一条链的时候才符合要求。颜色分别用1，2，3来表示。从度数为1的节点作为根节点开始，如果确定了最开始选的两种颜色，则第三种颜色必定为6-前两种颜色之和，所以前两种颜色的选择就决定了全部的颜色选择。一共六种情况，所以是O(n)的复杂度。#include <bits/stdc++.h>using namespa

2021-11-24 08:17:36 374

原创 2021沈阳 B. Bitwise Exclusive-OR Sequence （签到题）

题目链接：https://codeforces.com/gym/103427/problem/B题目思路非常简单，就是对每个二进制位划分二分图。但是这题难点在于卡常，时限是1000ms，如果30遍DFS的话很容易TLE，最好是进行一次DFS，在这一次内进行30的循环，情况会好不少。这里我用BFS不用递归，200+ms可过。#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 5;int n, m;struct

2021-11-22 23:07:27 777

原创 2021济南 D Arithmetic Sequence （三分）（银牌题）

PTA的教育超市可以找到这场比赛的题。这题属于银牌题的级别，该题有一个应该算是常识性的知识点，即在一个序列中，sum(|a[i] - x|)要取得最小值，x应该为这个序列中的中位数，即第(n + 1) / 2 大的数。然后利用这一性质可以三分求答案。很奇怪的一点是答案要用__int128来保存，否则存储不下这么大的数。有人解释说，在计算等差数列时，中位数可能达到1e18的级别，所以long long不够用。#include <bits/stdc++.h>using namespace

2021-11-22 08:14:35 513

原创 2021桂林 D. Assumption is All You Need（铜牌题）

原题链接：https://codeforces.com/gym/103409/problem/D数组开小了，导致我多试了好多次，还去看了别人的题解。最后发现我原来的做法是可以AC的，别人的基本是如果是从小的开始遍历，就每一步替换最小的可以替换的，如果是从大的开始，每步替换最大可以替换的，和我不太一样。我是从大到小开始遍历，并不要求做完一轮swap操作后归为目标位置，而是要让操作完的位置小于等于目标位置，并且该轮swap操作中不能让更大数的位置大于其目标位置，否则之前的做法就变得无意义了。因为后面要遍历的

2021-11-21 22:17:52 939

原创 Codeforces Round #750 (Div. 2) E. Pchelyonok and Segments

题目链接：https://codeforces.com/contest/1582/problem/Ek的最大值不超过500，所以有O(nk)是可以接收的复杂度。令dp[i][j]为后缀i序列中，长度为j的序列和的最大值。pre[i + j - 1] - pre[i - 1] < dp[i + j][j - 1]，在满足这个条件的前提下，从dp[i+1][j]向dp[i][j]转移，则能保证，dp[i][j]的值是不覆盖dp[i + j][j - 1]的，所以可以满足序列长度依次为j, j - 1

2021-11-17 23:12:46 240

原创 Codeforces Round #750 (Div. 2) F1. Korney Korneevich and XOR (easy version)

题目链接：https://codeforces.com/contest/1582/problem/F1真的是菜的可以，容易想到ai<=500就是有个对512的遍历操作，但是怎么实现却一筹莫展。就一句话，dp[j]表示异或和结果为j的得到该结构的所有递增序列中最小的末尾值。#include <bits/stdc++.h>using namespace std;using ll = long long;const int N = 1e6 + 5;const int INF =

2021-11-17 21:54:01 253

原创 Educational Codeforces Round 116 (Rated for Div. 2) E. Arena

原题链接：https://codeforces.com/contest/1606/problem/EDP题，dp[i][j]表示幸存者个数为i，受到过的伤害总和为j的合法方案数。向着 nj = min(x, j + i - 1), 0 <= k <= i 转移 dp[k][nj] = dp[k][nj] + dp[i][j] * combcomb = C(i, i - k) * 快速幂(nj - j, i - k)，答案为dp[0][0~x]的和。#include <bits/st

2021-11-17 18:20:12 223

原创 2021 ICPC济南站的签到题（铜牌题/银牌题)：C & K

题目在PTA的教育超市里可以找到：https://pintia.cn/market/item/1459833348620926976C题：博弈+组合数学这题给的样例有很好的提示作用。可以想到如果最大的数有偶数个，那么就得成对拿走，如果是有奇数个，那么当前有机会拿的人一定会拿。从小数往大数遍历，可以发现大数可以随意穿插在小数序列之间，不受除了位置数量以外的特殊限制。因为要成对，设当前数的个数为n，如果n是偶数，则可以放的位置有，suf+n/2个，所以是suf+n/2取n/2个位置。suf是更小数的总个数

2021-11-16 19:23:36 1473 1

原创 Codeforces Round #754 (Div. 2) D. Treelabeling

题目链接：https://codeforces.com/contest/1605/problem/D首先很容易退出，只有二进制数最高位相同的两个数，异或和会小于两数最小值，所以要让树中相邻节点的二进制数最高位不同。考虑类似二分图，黑白两种颜色，这个题可以看作是有多种颜色，按顺序来，每个颜色的个数分别为1,2,4,…实现是计算黑节点和白节点个数，然后计算出每种颜色的个数，因为最后一种颜色可能不能达到满的2的倍数，所以还进行了排序，然后把这些颜色填充到黑节点或白节点。按颜色个数从大到小填充，采用贪心策略，

2021-11-13 08:25:46 1070

原创习题 9-2 免费糖果（Free Candies，UVa 10118）

原题链接：https://vjudge.net/problem/UVA-10118分类：记忆化搜索备注：状态分析#include <bits/stdc++.h>using namespace std;int n, pile[4][45], pos[4], dp[45][45][45][45], hav[25];int dfs(int cap) {// printf("%d %d %d %d, cap = %d\n", pos[0], pos[1], pos[2], pos[3]

2021-11-10 16:16:09 307

原创习题 9-1 最长的滑雪路径（Longest Run on a Snowboard,UVa 10285）

原题链接：https://vjudge.net/problem/UVA-10285分类：记忆化搜索备注：水题#include <bits/stdc++.h>using namespace std;const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};char s[105];int t, row, col, g[105][105], d[105][105];bool ok(int r, int c) { retur

2021-11-10 15:45:29 331

原创例题 9-25 轻松爬山（Easy Climb，NWERC 2008，UVa12170）

原题链接：https://vjudge.net/problem/UVA-12170分类：动态规划备注：思维，单调队列#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 200 + 5;const LL INF = 1e18;int t, n, d;LL h[N], x[N * N * 2 + 5], f[N][2 * N * N];struct Node { LL

2021-11-10 15:41:26 198

原创例题 9-24 书架（Bookcase, ACM/ICPC NWERC 2006, UVa12099）

原题链接：https://vjudge.net/problem/UVA-12099分类：动态规划备注：状态优化，类似0-1背包#include <bits/stdc++.h>using namespace std;const int N = 70 + 5;const int INF = 0x3f3f3f3f;int t, n, d[N * 30][N * 30], sum[N];struct Book { int h, t; bool operator < (con

2021-11-10 15:34:12 383

原创例题9-23 有趣的游戏（Fun Game, ACM/ICPC Beijing 2004, UVa1204）

原题链接：https://vjudge.net/problem/UVA-1204分类：动态规划备注：字符串#include <bits/stdc++.h>using namespace std;const int N = 20;const int INF = 0x3f3f3f3f;int n, len[N], cover[N][N][2][2], dp[1 << N][N][2];// dp[s][i][o]，其中s表示已经加入的字符串的集合，i表示结尾串的编号，

2021-11-10 15:32:34 3202

原创 Codeforces Round #753 (Div. 3) F. Robot on the Board 2

题目链接：https://codeforces.com/contest/1607/problem/F看过题解后，觉得这题难度确实不是很高，但是要AC还是有挺困难的。直接DFS超内存了，非得搞个栈来使用，主要是考虑到循环圈里的点贡献是相同的，就很好写了。#include <bits/stdc++.h>using namespace std;using LL = long long;const int N = 2e3 + 5;int t, n, m, num[N][N], d[N]

2021-11-06 10:19:59 115

原创 Codeforces Round #752 (Div. 2) E. Extreme Extension

题目链接：https://codeforces.com/contest/1604/problem/E新知识点：⌊m1⌋,⌊m2⌋,...,⌊mm⌋\lfloor\frac{m}{1}\rfloor,\lfloor\frac{m}{2}\rfloor,...,\lfloor\frac{m}{m}\rfloor⌊1m⌋,⌊2m⌋,...,⌊mm⌋中最多有2m2\sqrt{m}2m个不同的数。证明：https://math.stackexchange.com/questions/1069460/how

2021-11-05 19:13:36 140

原创铜牌题 L.Square（2020 EC-Final）

题面找其中的L题：https://upload-file.xcpcio.com/icpc/2020/2020-ICPC-Asia-East-Continent-Final-Statement.pdf这次学到了快速求质因数分解，即欧拉筛过程保存每个数的最小质数，在分解的时候每次除以自己的最小质数即可。该题是一个明显的思维题，想了好久没做出来然后找题解，发现压根找不到详细的题解（参加EC-Final的大神们并不屑于对该签到水题有过多叙述????）。只有看到什么全是0，全是1的一些提示。最后终于想到了，只看

2021-10-23 19:40:39 778 1

原创铜牌题/银牌题 The Boomsday Project （DP优化）

题目链接：https://ac.nowcoder.com/acm/contest/18713/H按通过数来算，可能也算是银牌题。主要是将该题从二维变成一维，形成线性DP。a[i]为第i次租车是第几天，dp[i] = min(dp[i - 1] + r, min{dp[b[j] - 1] + ca[j].c})r为花钱租一次的代价，ca[j].c为第j种折扣的代价，b[j]为可以使用该折扣的左边界是第几次租车。因为a[i]是非递减的，要满足b[j] + ca[j].d - 1 >= a[i]

2021-10-20 20:06:04 324

原创铜牌题 Walker（三分+分类讨论）

题目链接：https://ac.nowcoder.com/acm/contest/9925/D可以分以下几种情况：①两个人中选一个走完全程②互相向对面走，走到边界，算两者时间久的那个③将两人中间某点作为划分点，两个人分别负责走自己的部分主要是第三点，如果只考虑分类就只能想到一些个别的情况。实际上两人中间的位置，任意点都可能作为划分点，所以需要用三分。注意一个人走自己的部分有两种走法，选时间最少的那种。#include <bits/stdc++.h>using namespace

2021-10-20 09:22:21 129

原创 2020 CCSP【给他文件系统（GeetFS）】

题面描述：http://history.ccfccsp.org.cn/2020/0-tasks.pdf这个题就是模仿Git实现一些简单文件操作功能：write、read、unlink、ls、commit、checkout、merge。可以说按顺序，实现难度越来越高。后面的命令会影响前面命令的执行，所以为了得到后面测试点的分，前面写过的函数往往要做出很大的整改。这是是我第一次写的大型模拟题。断断续续写了好多个小时，后面都是对着测试点的数据来写。现在还是cin和cout的输入输出，可能运行速度还是比较慢，

2021-10-13 23:06:13 426

原创 Codeforces Round #745 (Div. 2) C - Portal

题目链接：https://codeforces.com/contest/1581/problem/C单纯的二维前缀和只能O(n2m2)，看了答案发现需要取后缀最小值，因为可以做到前后两部分互不干扰，时间复杂度为O(n2m)。#include <bits/stdc++.h>using namespace std;const int N = 400 + 5; int t, n, m;char g[N][N];int sum[N][N], f[N];int getSum(int

2021-10-01 09:16:14 196

原创例题9-22 越大越好（Bigger is Better, ACM/ICPC Xi‘an 2006, UVa12105)

原题链接：https://vjudge.net/problem/UVA-12105

2021-09-23 16:42:06 112

原创例题 9-23 有趣的游戏（Fun Game，ACM/ICPC Beijing 2004，UVa1204）

原题链接：https://vjudge.net/problem/UVA-1204分类：状压DP备注：字符串覆盖按紫书的思路，首先排除被覆盖的串，每个串都试着正反两个状态，与当前集合的最后一个串计算覆盖量，取最优。这里固定以某一个串为第一个串，就可以很方便地来把最后一个串和第一个串连起来。注意有效串个数为1，以及长度小于等于1应该变为2的情况。#include <bits/stdc++.h>using namespace std;const int N = 20;const in

2021-09-23 16:37:57 145

原创例题 9-21 修缮长城（Fixing the Great WALL, ACM/ICPC CERC 2004, UVa1336)

原题链接：https://vjudge.net/problem/UVA-1336分类：区间DP备注：记忆化搜索注意一定要加floor，否则会WA。#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 1010;struct Node { double x, c, d; bool operator < (const Node& rhs) const {

2021-08-25 08:31:06 200

原创例题 9-20 装满水的气球（Dropping water balloons, UVa 10934)

原题链接：https://vjudge.net/problem/UVA-10934分类：动态规划备注：经典问题很奇怪的一道题，但lrj将其备注为经典问题。紫书上说，最少多少次实验能够确定气球的硬度。最坏情况是要测到最后一层也不摔破，但实际不知道硬度，所以我们要在不知道硬度的前提下，测出硬度是大于等于n这件事。显然，如果只有一个气球，要确定硬度，必须从第一层开始往上尝试，否则直接破了就不能确定了。如果气球足够的话，显然二分测是最快的，但主要考虑气球不够的情况。设d[i][j]为i个气球实验j次最高能到

2021-08-24 08:18:43 258

原创学堂在线-清华大学-操作系统实验Lab1【练习5-6】

练习5：实现函数调用堆栈跟踪函数（需要编程）我们需要在lab1中完成kdebug.c中函数print_stackframe的实现，可以通过函数print_stackframe来跟踪函数调用堆栈中记录的返回地址。根据要求，要得到类似如下的输出：……ebp:0x00007b28 eip:0x00100992 args:0x00010094 0x00010094 0x00007b58 0x00100096 kern/debug/kdebug.c:305: print_stackframe+22

2021-08-19 00:43:17 764

原创学堂在线-清华大学-操作系统实验Lab1【练习3-4】

练习3：分析bootloader进入保护模式的过程。BIOS将通过读取硬盘主引导扇区到内存，并转跳到对应内存中的位置执行bootloader。请分析bootloader是如何完成从实模式进入保护模式的。lab1/boot/bootasm.S源码如下：#include <asm.h># Start the CPU: switch to 32-bit protected mode, jump into C.# The BIOS loads this code from the first

2021-08-17 12:10:03 577

原创例题 9-19 团队分组（Team them up!, ACM/ICPC NEERC 2001, UVa1627)

原题链接：https://vjudge.net/problem/UVA-1627分类：0-1背包备注：二分图，背包变体按照紫书的思路，将不互相认识的连在一起，这样形成连通图必须要能够变为二分图，否则不合题意，然后黑白染色，两种颜色对应两个分组，互换一下分组，组员数量的差值就会变化，可以据此来进行DP。开始以为，只要对每个连通图看两种情况即可，每次都求出最优结果。WA了之后再看别人的解法，仔细一想发现直接这样的状态转移是一种贪心的做法。在洛谷上有一句总结：对付这种“01背包”，常见的状态设定是：用 d

2021-08-14 22:34:36 191

原创例题 9-18 跳舞机（Tango Tango Insurrection，UVa 10618）

原题链接：https://vjudge.net/problem/UVA-10618分类：多维DP备注：多阶段决策问题主要还是参考了别人的解法，但理解起来很容易。#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int INF = 0x3f3f3f3f;// 0-up 1-left 2-right 3-down// 0:neither 1:l

2021-08-13 21:54:32 136

3Ds Max制作的房屋模型

JPG形式的免费材质贴图资源

请问有什么数据库使用了多粒度封锁协议？