Buyi.-CSDN博客

MyBatis逆向工程时Mapper.xml中生成多余字段问题解决比如我们有Employee实体类、EmployeeMapper接口、EmployeeMapper.xml映射文件Employee中明明只有employee_id,last_name,email,department_id的字段，而sql映射文件中缺出现了manager_id,first_name,commission_pct等等多余字段原因：逆向工程生成代码的过程中，不光会根据我们指定数据库mybatis中的表employees生成了

2022-02-26 15:45:12 3936 3

原创 *[2020上海ICPC]D. Walker（贪心+二分）

题目链接：http://codeforces.com/gym/102900/problem/D题意：一个坐标轴[0,n]上面有两个点p1,p2,这两个点分别可以以v1,v2的速度向正方向或反方向移动，求轨迹覆盖整个坐标轴的最小时间解题思路：一开始想法是多分几种情况比如：①一个人走完全程②两个人相对着走到端点③两个人先向两端走，然后在中间某点回合④两个人先往中间走，在某点会和后往两边走但是其中第三种和第四种分别讨论的子情况太多了，一直wa在第10个样例上参考了网上的不同的思路，发现可以直接

2020-12-23 17:34:56 603

原创 [2020上海ICPC]M. Gitignore(模拟+思维）

题目链接：http://codeforces.com/gym/102900/problem/M题意：给出n个要删除的文件路径，同时给出m个不能删除的文件路径。每次删除都只能删除一个文件或者一个文件夹（和该文件夹内的所有文件），问最少需要删除多少个路径解题思路：这题直接模拟即可，将n个要删除的放在str1组中，将m个不能删除的放在str2组中，先将m个不能删除的所包含的路径全部标记为1，再去处理n个要删除的路径。当处理到的路径未被标记（即标记为0），那么可以直接删除掉，并将该路径标记为2。如果处理到

2020-12-18 10:44:08 830

原创 [2020上海ICPC]B. Mine Sweeper II(构造+思维）

题目链接：http://codeforces.com/gym/102900/problem/B题意：扫雷游戏，X表示雷，.表示无雷区，每个无雷区上面有一个数字，记录该位置处周围8个位置有多少个雷。现在给出A矩阵雷区和B矩阵雷区，它们无雷区数字之和为suma,sumb，要求(int)(nm/2)次将B矩阵雷区变化成sumb=suma解题思路：首先要找到一个规律就是，将一个矩阵的雷区全部变成无雷区，无雷区全部变为雷区，最后得到的sum相同。然后去找A矩阵与B矩阵每一个位置处不同的数量cnt，如果cnt&

2020-12-18 10:35:33 1492 1

原创 [2020上海ICPC] C.Sum of Log(二进制数位DP）

题目链接：http://codeforces.com/gym/102900/problem/C解题思路：①i和j不能同时为0②要是公式有意义，i和j的二进制必须每一数位都不同或者都为0③log2(i+j)+1在满足条件②的情况下表示i和j中最大的二进制数位使用数位DP对二进制进行处理，使用dp[pos][limit1][limit2]来记忆化搜索，分别表示位置、x是否达到上界、y是否达到上界有两种数位DP处理方式第一种：直接使用for循环来决定最高数位的情况#define NO_SECUR

2020-12-17 11:33:25 615

原创 CodeForces - 149D.Coloring Brackets(递归区间DP)

题目链接：https://vjudge.net/problem/CodeForces-149D题意：在括号匹配问题的基础上，每一对相匹配的括号对，他们之中只有一个括号可以被涂成红色或者蓝色，另一个只能涂成没有颜色。且相邻的两个括号不能是同一种颜色(不包括无颜色）解题思路：①先进行括号匹配，找出每一个位置i处括号对应的位置②dp[i][j][x][y],表示区间[i,j]且i处括号颜色为x,j处括号颜色为y的情况当处理区间[L,R]时，分两种情况进行区间DP，第一种：R和L是一对匹配的括号对，那么

2020-12-11 09:04:00 144

原创 *ZOJ3537.Cake(区间DP+凸包多边形判断）

题目链接：https://zoj.pintia.cn/problemsets/91827364500/problems/91827368971题意：将一个多边形分成多个三角形，求最小代价解题思路：参考首先是凸包的判断Andrew算法：struct Point{ int x,y; Point(){} Point(int xx,int yy):x(xx),y(yy){} void read(){ scanf("%d%d",&x,&y);

2020-12-10 12:03:52 99

原创 *CodeForces - 55D.Beautiful numbers(数位DP+离散化处理）

题目链接：https://vjudge.net/problem/CodeForces-55D题意：要求一个数可以整除它的所有的数位。求L到R范围内所有满足条件的数的个数解题思路：①一个数可以整除它的所有数位，不需要对其每个数位都去除一次，可以直接求出所有数位的公倍数，然后判断这个数能否整除它②采用数位DP，最难的是考虑如何完成记忆化搜索操作。dp[pos][num][lcm]，pos为当前位置，num为当前处理的数大小，lcm为当前所有数位的公倍数。因为数据范围为9e18，所以要开ll数组，同时

2020-12-09 15:47:22 116

原创 *[kuangbin数位DP]HDU4507.吉哥系列故事——恨7不成妻(数位DP+推导）

题目链接：https://vjudge.net/problem/HDU-4507题意：找出一个区间内与7无关的数解题思路:先说一下我自己的错误写法:通过记录所有的数位和、对7取余后的结果以及当前的数值，当最后的情况是sum%7=0并且res%7=0时，将当前数值he的平方返回但是这样做的时候记忆化搜索的时候就会出现错误，因为不同前缀可以通过取余得到相同的sum和res，但是最后在对he进行平方相加的时候前缀不同就会影响到结果的不同，所以这种方法不可行。ll dfs(int pos, int li

2020-12-07 16:41:43 108

原创 [kuangbin数位DP]SPOJ - BALNUM.Balanced Numbers(数位DP+状压）

题目链接:https://vjudge.net/problem/SPOJ-BALNUM题意：要求一个数中的出现过的奇数各自出现次数为偶数次，出现过的偶数各自出现次数为奇数次解题思路:注意本题要求的情况是奇数和偶数各自出现的次数，而不是整体出现的次数，所以要进行0-9每个数字的出现次数的记录，但考虑到数位dp的记忆化搜索，没有办法保存这么，所以使用一个十位二进制保存0-9每个数出现的是奇数次还是偶数次,每次出现一个数字i就对state进行一次异或。最后数位为0，即没有出现过或者出现了偶数次，数位为1，

2020-12-07 16:20:26 95

原创 [kuangbin数位DP]HDU4352.XHXJ‘s LIS（数位DP+状压）

题目链接：https://vjudge.net/problem/HDU-4352题意：前面都是无关的话，只有倒数第二段与题目相关。意思就是寻找[L,R]之间数位最长上升子序列长度为K的数解题思路：数位dp+状态压缩可以用一个十位二进制数来保存最长上升子序列的情况，1的个数即最长上升子序列长度使用dp[pos][state][k]来进行记忆化搜索，pos表示位置，state表示二进制状态，k表示当前要找的长度k关于state的更新：int update(int x, int state) { f

2020-12-07 16:12:31 108

原创 2020CCPC长春D. Meaningless Sequence(思维+数位DP）

题目链接：http://codeforces.com/gym/102832/problem/D解题思路：可以发现一个数的大小与它的二进制表示中的1的个数有关，a=c^(二进制中1的个数）那么题目就转化为求所有数中1的个数使用的是数位dp的方法，枚举1的个数来分配。对于没有上限要求的x长度串中分配y个1的方案数直接可以使用组合数C(y,x)#include<iostream>#include<cstdio>#include<string.h>#inclu

2020-12-01 11:19:46 547

原创 NOJ2452.悲伤的史大佬（字符串处理）

题目链接：https://acm.njupt.edu.cn/problem/NOJ2452题意:给定一个字符串，求它有多少个子字符串中包含sad序列解题思路:①先找出每一组字串[i,j]，a[i]=‘s’,a[j]=‘d’,并且[i,j]中包含一个点a[k]=‘a’。使用的方法是找到每一个‘a’的前面最近的’s’，和后面最近的’d’②处理字符串中的每一个’a’,求出所有包含sad的最短字串，对于相同的L，取R最小的保存③枚举左端点，每次让当前字串包含一个最近的sad字串即可，统计贡献。#defi

2020-11-27 16:43:32 115

原创 *NOJ2446.小陈的气球(树状数组+区间处理+离线处理）

题目链接：https://acm.njupt.edu.cn/problem/NOJ2446题意:有n个气球，每次把区间[L,R]之间的气球去掉，问还剩下多少中颜色的气球解题思路:①先将气球序列扩大两倍，记录下前i个气球中的种类数sum和每一个位置处气球对应相同颜色的下一个气球的位置Next②离线处理询问，那么题目中的删除[L,R]区间内的气球，求[1,L-1]和[R+1,N]之间气球的颜色就可以转换为求[R+1,N+L-1]区间内的气球个数，同时将R+1看成L,N+L-1看作R，重新保存到结构体中

2020-11-27 12:47:27 116

原创幸运匹配（贪心）

贪心处理，每一个数优先和自己相等的数匹配，其次和比自己大一位的匹配即可。#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstdio>#include<string.h>#include<string>#include<vector>using namespace std;const int maxn = 1e5 + 10;#define ll long l...

2020-11-25 18:15:28 542

原创天梯赛（桶排序优化）

#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstdio>#include<vector>#include<queue>#include<math.h>using namespace std;const int maxn = 5e4 + 10;int n,m;int maxg;long long A, B;priority_queue<int...

2020-11-25 18:12:59 205

原创幸运序列（整体处理+中位数定理）

解题思路：#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstdio>#include<vector>#include<queue>#include<algorithm>#include<math.h>using namespace std;#define ll long longconst int maxn = 1e5 + 10;cons..

2020-11-25 09:33:15 229

原创幸运字符串（DP）

解题思路：DP主体：for (int i = 0; i <= 26; i++) dp[0][i] = 1; for (int i = 1; i <= n; i++) { //总长度为n for (int j = 1; j <= 26; j++) { //字母种数为26 for (int k = 0; k <= r && k <= i; k++) { //每个字母最多出现r次 dp[i][j] =(dp[i][j.

2020-11-25 09:20:11 474

原创导弹拦截变形（去点最长上升子序列）

导弹拦截DescriptionAA 国为了防御 BB 国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。因此可能需要配备多套导弹拦截系统才能拦截所有的导弹。某天，雷达捕捉到 BB 国的导弹来袭。AA 国于是向 CC 国请求援助，CC 国可以在这些导弹进入 AA 国领空前炸掉这些导弹中的某一个。现在 AA 国想知道，对于每一个导弹，如果 CC 国把它炸掉，那么至少配备多套导弹拦截系统才能拦截剩下所有的导

2020-11-25 09:12:51 94

原创 2020CCPC威海L.Clock Master(质数预处理+分组背包）

题目链接：http://codeforces.com/gym/102798/problem/L题意：给一个b，要求将b分成任意n个数ti,使得(k%t1,k%t2,…,k%tn)的组合数最多。解题思路：（k%t1,k%t2,…,k%tn)的组合数可以发现是t1.t2…tn的最小公倍数，因为只有k经过最小公倍数次，才能会到最开始的(0,0,0,…,0)状态。所以这个题目就变成了求最小公倍数最大的题目。要求最小公倍数最大，那么就要求充分利用b内的数，要求拆分后的数两两互质，如果a与b不互质，那么就会浪费

2020-11-17 10:20:37 176

原创 2020CCPC威海D.ABC Conjecture(素数筛+素数分解+思维）

题目链接：http://codeforces.com/gym/102798/problem/D题意：给出c，要求找出a+b=c，其中要求abc的素数因子相乘得到结果小于c解题思路：首先排除c为素数的情况，c如果为素数那么结果一定会大于等于c。当c为合数的时候，c可以分解为素数相乘的形式，如果素数中有素数幂的出现，那么一定使得rad(abc)<c判断素数幂的方法:因为c的大小为1e18,可以先预处理1e6内的所有素数①然后判断c%(prim[i] * prim[i])是否为0，为0则直接输出

2020-11-16 16:05:03 467

原创 PTA 基础实验3-2.4 出栈序列的合法性(模拟）

题目链接：https://pintia.cn/problem-sets/988034414048743424/problems/988038770777137152解题思路：将1到n模拟进栈，当当前栈顶与当前给定的待出栈的数字相同时，则出栈，一直模拟，如果将n个数全部模拟进栈后，最后堆栈为空，那么YES,否则NO。同时要注意模拟过程中，判断堆栈容量不能超过m题解：#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<c

2020-11-15 21:21:59 398

原创 2020绵阳J.Joy of Handcraft（线段树/并查集+去重优化）

题目链接：http://codeforces.com/gym/102822/problem/J题意：有n个灯，灯有亮度值x和亮的时间t，每2k*t+1到(2k+1)*t时间内灯亮，(2k+1)*t+1到(2k+2)*t时间内灯熄灭，问m个时间点内每个时间点灯的最大亮度。解题思路：区间修改（区间求最大值）+单点查询①利用线段树，区间修改+单点查询，注意改一下模版，每次不是求和，而是求最大值了。同时注意按Lamb[i].t进行排序，相同的t将亮度x大的放在前面，如果 Lamb[i].t已经处理过，直接

2020-11-12 22:30:55 219

原创 2020CCPC绵阳K.Knowledge is Power(互质数分解）+两数互质规律总结

两个数互质的十种情况：1、两个数都是质数，这两个数互质2、两个连续的自然数互质。如：8和9、14和153、两个连续的奇数互质。如7和9、11和134、两个不连续的奇数但只相隔一个奇数的两个数互质。如13和17、15和195、两个合数不含相同质因子的两数互质。如：4和9，6和256、1和任意一个自然数互质。如：1和8，1和507、2、4或8和任意一个奇数互质，如：2和9，4和218、3、7或11和任一个不成倍数关系的两数互质。如：3和11，7和25，11和149、5和另一个末尾非0非5的数互

2020-11-11 23:25:36 684

原创 2020CCPC绵阳D.Defuse the Bombs(二分）

题目链接：http://codeforces.com/gym/102822题意：n个炸弹，每次只能让一个炸弹的时间不变，其余炸弹爆炸时间均减少1，但有一个炸弹爆炸时间小于0时，那么就会爆炸。问最长可以拖延多少时间解题思路：使用二分，将一个时间认为是可以最大的爆炸时间，然后算出比该爆炸时间小的炸弹求和得到sum，如果sum<=当前爆炸时间，那么说明当前爆炸时间是满足的，可以继续像右二分。反之，向左二分查找PS:注意对ans、res、l、mid、r开long long时间复杂度：NlogC实现代

2020-11-11 16:21:44 388

原创南邮汇编第一次实验(3.1).从键盘输入一个16位二进制数，然后转换成等值的十进制显示

.586CMPD MACRO X ;宏定义比较法法实现二进制转化为十进制 LOCAL LAST,NEXT MOV DL,0 ;存储十进制的值LAST:CMP BX,X JC NEXT INC DL SUB BX,X ;依次算出BX中有多少X JMP LASTNEXT:ADD DL,30H ;显示BX中X个数 MOV AH ,2

2020-10-24 14:54:55 2210 2

原创 UVA - 10766.Organising the Organisation(生成树计数）

题目链接：https://vjudge.net/contest/388044#problem/H题意：给出n m k，n表示有n个点，k表示数的根，m表示有m条不能够相连的边，求生成树数量解题思路：使用Matrix-Tree定理Matrix-Tree定理对于一个无向图G，它的生成树个数等于其Kirchhoff矩阵任何一个n-1阶主子式的行列式的绝对值。所谓n-1阶主子式就是对行列式中任何一个元素，去掉它本身以及与他同行同列的元素后，剩下的元素构成的行列式。代码转自：https://blo

2020-08-08 10:54:07 144

原创 HDU6827（多校第六场）.Road To The 3rd Building（思维+线性逆元）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6827解题思路：本题多次使用逆元操作，使用快速幂时间复杂度为O(nlogn),使用线性求逆元时间复杂度为O(n)线性求逆元求可以按规模k来寻找规律当k=1时，分子为ans[1]=(a1+a2+…+an)/1=(sum[n+k-1]-sum[k-1])/1=p[1]/1;k=2时，分子为ans[2]=[(a1+a2)+(a2+a3)+(a3+a4)+…(an-1 +an)]/2=[(p[1]+(sum

2020-08-08 00:01:01 146

原创 *HDU6832（多校第六场）.A Very Easy Graph Problem(最小生成树+dfs)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6832题意：找出所有满足ai=1&&aj=0的点连成的边的权值和解题思路：给出的第i条边的长度=2^i，2 ^1+2 ^2+…+2 ^(n-1)<2 ^n，所以可以得出越早出现的边或者连通边（间接连在一起的边）越短①使用并查集，保存能够相互连接的边，每加入一条边，先判断这两个点是否已经在同一并查集中，确保最短。经过这样的操作后，可以得到一个最小生成树，每两个点之间只有一条最短的路

2020-08-07 15:57:28 166

原创 **2020暑期牛客多校H.Harmony Pairs(数位DP）

题目链接：https://ac.nowcoder.com/acm/contest/5671/H题意：…解题思路：利用数位DP，dp[pos][sum][limita][limitb][limit]pos当前搜索位置 sum当前A与B数位差 limita A是否为上界情况 limitb B是否为上界情况 limit A小于或等于B因为N最大取十进制100位，所以数位差绝对值最大值小于1000，所以以base=1000为数位差起点，从最高位往后进行数位dp+记忆化注意一下dp转移和条件的

2020-08-03 11:39:22 174

原创 **HDU6805(多校第四场）.Deliver the Cake（拆点+最短路）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6805题意:张三送蛋糕，使用左手或者右手拿，小镇有三种L、R、M，L只能够左手拿蛋糕通过，R只能右手拿蛋糕进入，M是任意手都可以。n个小镇各自有对应方式，张三每一次换手拿蛋糕都需要消耗x秒。然后有m条路来连接这些城镇（无向），每条路有长度d，每单位长度耗时1秒，现在要求最短时间从s地把蛋糕送到t地解题思路：利用拆点的方法，将M点的城镇分别拆分成两个点L和R来进行构图，对于LR的路耗时为d+x，对于RR的路耗

2020-08-03 01:52:58 163

空空如也

空空如也