- 博客(21)
- 收藏
- 关注
RSS订阅原创 python 风格的序列（流畅的Python学习笔记）
本文为流畅的python第二章笔记，阐述了python风格的序列，包括list，tuple等，以及在写代码时候的trick和习惯，非常值得细致学习。 未完待续。。。
2022-12-13 14:16:55
235
原创 CF1553D. Backspace（正难则反）
传送门题目大意 给定一个字符串S和一个字符串T。可以将S字符串中的任意字符变成退格字符\b，问，能否将字符串变S为T。例如：S=“abcdef”，我们将其中第3个字符变为退格字符，则S=“ab\bdef”=“adef”，如果T为“adef”则输出YES。如果无法变成T字符串则输出NO。解题思路 经过分析可以发现，如果将目标符串中的每个字符看成一个隔板，则原字符串S将被分成strlen(T)+1断，除了第一段，其余段的长度一定为偶数。 这样衍生出了两种方法。第一种从正向考虑，我们可以推导出第一
2021-07-23 21:55:19
474
1
原创 CF1293E Xenon‘s Attack on the Gangs
传送门题目大意 给定一棵树，n−1n-1n−1条边。问如何在边上填数（范围从0到n-1,且每个数仅出现一次）使得SSS 最小S=∑1≤u,v≤nmex(u,,v)S = \sum_{1\leq u,v \leq n}mex(u,,v)S=1≤u,v≤n∑mex(u,,v)其中mex(u,v)mex(u, v)mex(u,v)表示从u到v的路径上最小没出现的自然数。数据范围：2≤n≤30002 \leq n \leq 30002≤n≤3000解题思路 假设我们已经知道填0的边所在的位置（边
2021-01-27 16:42:59
252
原创 LINGO编程（基础）
Lingo程序一般以“Model：”开始，“End”结束。再程序中若没有Model和End也能执行但最好还是写完整。五段程序架构Model:Title "Example";............End集合段集合段：以“SETSL:”开始，“ENDSETS”结束。SETS: Car /1..2/ : a, b; Box /1..6/ : c, d; Link(Car, Box) : x;ENDSETS代码中Car表示集合名称，也是集合存储的数的类别名，后面的1到2表示两个两个
2021-01-17 13:25:52
9563
原创 2020 ICPC南京 M.Monster Hunter(树形背包)
题目大意 给你一棵树，你可以去掉i个点（i∈[0,n]i\in[0,n]i∈[0,n]），然后计算剩余结点的贡献，每个结点的贡献为它本身的价值加上它所有儿子的价值。当然你需要合理安排删去的i个结点使贡献最小化。输出每个i对应的贡献值。解体思路 树形dp，由于结点的贡献与周边的结点有关，所以还需要再开一维状态状态设计：dp[0][i][j]dp[0][i][j]dp[0][i][j] 表示删掉结点i，并且子树中留下j个结点的价值。dp[1][i][j]dp[1][i][j]dp[1][i][j
2021-01-01 19:30:32
1093
1
原创 C语言学习笔记(基础)
C语言数据类型变量名：必须由字母，数字下划线组成，区分大小写。变量名第一个字符必须是字母或下划线。注意不要与标准库内的变量或关键字重名，例如：this next x0等。关键字：就是打出来高亮的字符，用来组成语言结构，例如return if for return，有32个变量初始化和变量赋值是不一样的！！格式化字符数据类型格式64为有符号整数 (long long)%lld32为无符号整型 (usigned int)%u八进制整数%o十六进制数%x
2020-12-22 14:42:46
1439
原创 洛谷2762 太空飞行计划问题
传送门题目大意给定n个实验，m种器材，每个实验都需要使用一些器材。进行某个实验会获得该实验的经费，但是如果没有该实验所需要的仪器，就需要花费一些钱来购买。求选择哪些实验所获得的收益最大。解题思路这是网络流最小割的一个经典应用求最大权闭合图。按照如下方式建图：加入n个点代表每个实验，将这n个点分别于源点S连边，流量为该实验的经费。加入m个点代表每个仪器，将这m个点分别于汇点T连边，流量为仪器的花费。对于每个实验，分别于它所依赖的仪器连边，流量为无穷大。 最小割只会割掉与源点或者汇点相连的
2020-09-24 21:29:55
126
原创 CF 1400E Clear the Multiset（贪心，分治，DP)
传送门题目大意 给你一个有nnn个元素的集合，第iii个元素有aia_iai个，有两个操作：1.取走值从l到r的元素各一个。2.取走值为i的元素任意x个。问最少执行多少次操作把集合内所有元素取完。解题思路思路一：贪心 最坏O(n2)O(n^2)O(n2)，但实际上非常高效 可以发现在对某个区间执行操作1时，一定要反复执行直到该区间中的一个值的个数为0，这样的操作1才是有意义的。因此可以采用分治思想，对于一个区间l,rl, rl,r，要么全用操作2将区间内所有数取走（一共r−l+1r - l
2020-08-27 17:49:03
264
原创 CF 1400D Zigzags（枚举，前缀和优化）
传送门题目大意： 给定一个序列aaa，找四个数满足下标1≤i<j<k<l≤n1 \leq i < j < k < l \leq n1≤i<j<k<l≤n并且ai=aka_i = a_kai=ak， aj=ala_j = a_laj=al，问有多少对这样的(i,j,k,l)(i, j, k, l)(i,j,k,l)。解题思路 设sum[i][x][y]sum[i][x][y]sum[i][x][y] 表示存在多少对(k,l)(k, l)
2020-08-27 12:32:48
304
原创 CF 1105E Helping Hiasat（无向图最大团）
传送门题目大意Hiaset有一个handle，如果来访问的朋友的名字和handle一样朋友将会很开心。Hiaset 知道朋友在何时访问以及访问人的姓名，和他何时可以改变他的handle。问他最多可以使多少个朋友开心。解题思路 我们发现，在一个可以改handle的时间之后，连续访问的朋友中，我们只能让其中的一个朋友开心，也就是说在连续访问的朋友中有一个开心其他必定不开心。这样我们可以在连续访问的朋友间相互连边，这样问题转化成，如果选择某个点那么所有与它相邻的点都不能选，问最多选多少个点。没错这就是无
2020-08-26 20:45:46
205
原创 牛客 NC201908 小睿睿的伤害（dsu on tree, 启发式合并）
传送门题目大意 给你一棵树，每个节点有一个权值valvalval，每一对点对(i,j)(i,j)(i,j) 可以在他们的lcalcalca处造成gcd(val[i],val[j])gcd(val[i],val[j])gcd(val[i],val[j])的伤害，问对于每一个点，点对对它造成最大的伤害是多少，以及造成最大伤害的点对的数量。解题思路 这道题一个比较好想的做法就是暴力，我可以暴力枚举点对计算其在lcalcalca处的贡献（复杂度O(n2)O(n^2)O(n2)），同时我也可以对每个点暴力
2020-08-25 13:58:27
475
原创 牛客 NC205089 牛妹的苹果树(LCA，树的直径，ST表)
传送门题目大意 在一颗树中，询问给定区间内所有点对的最大距离。解题思路 该题主要利用了一个性质：如果一个集合内距离最大的点对为(a,b)(a,b)(a,b)，另一个集合内距离最大的点对为(c,d)(c,d)(c,d)那么这两个集合合并后，距离最大的点对一定在a,b,c,d这四个点中。这样相当于我们知道了如何合并子问题，接下来就是解决区间查询的问题了。用线段树或者RMQ都没问题。代码实现在合并两个子问题时需要查询两点之间的距离：dis(u,v)=dis(root,u)+dis(root,v)−
2020-08-23 18:23:59
165
原创 牛客 NC209881 名作之壁(单调队列)
传送门题目大意 给定一个序列，求有多少个区间满足区间最大值减区间最小值大于k。解题思路 可以从反面入手来解决这个问题，就是把答案变成区间个数减去区间最大值减最小值小于等于k的区间个数，求后者我们可以通过枚举区间的右端点找区间左端点有多少种可能的情况，然后累加起来就行了。我们可以发现如果区间[l,r][l,r][l,r] 满足题意那么区间[l+1,r][l+1,r][l+1,r]也满足题意，所以我们只要对每一个rrr 求出最左边的lll 使[l,r][l, r][l,r]满足题意，那么右端点为rr
2020-08-22 23:47:33
372
原创 CF 1401E Divide Square（扫描线，树状数组）
传送门题目大意 在平面直角坐标系中，区域{(x,y)∣0≤x≤1e6,0≤y≤1e6}\{(x, y)|0 \leq x \leq 1e6, 0 \leq y\leq 1e6\}{(x,y)∣0≤x≤1e6,0≤y≤1e6}中，有n条水平的线段和m条竖直的线段，保证这些线段的某个端点一定在该区域的边界上并且同向线段之间没有重合的部分，问这些线段能将这个区域分为多少个部分。解题思路 首先我们应当发现如果存在一条水平线段与竖直线段相交，那么这两条线段一定能够划分出一个新区域（可以通过剪纸形象的理解一
2020-08-22 19:12:38
558
原创 牛客 NC20893 赞迪卡之声妮莎与奥札奇（无向图删边，博弈论）
赞迪卡之声妮莎与奥札奇（无向图删边，博弈论）传送门题目大意 给一个无向完全图，甲乙两人在玩删边游戏。规则是，从一号点出发，甲先手，挑选一条边前进，并且把这条边删除，乙再选一条边前进，再把这条边删除。两者轮流进行直到一个人无法选边前进，判定该人失败。问甲乙两人都按照最佳方式操作，谁必胜。解题思路 这个题利用了完全图的一种对称性质，下面将以四个点的情况对这种对称性做出具体解释。四个点的完全图在逻辑上更类似于一个四面体而不是一个正方形，因为在正方形中对角线和四条边并不是等价的，但在四面体中这六条边位
2020-08-20 00:31:30
612
原创 CF 1398E Two Types of Spells（set，贪心）
CF 1398E Two Types of Spells（set，贪心）传送门题目大意 有两种技能“电”和“火”，每种技能都有一个伤害值d，同时技能“电”可以使下一个使用的技能的伤害值提高一倍。每次你都会学习一个技能或者遗忘一个技能，问每次通过合理安排技能使用顺序能够造成最大伤害值是多少 。解题思路 首先考虑如何安排顺序使伤害值最大化，我们可以考虑将技能火按伤害值排序，然后将技能电按照从大到小的顺序插入技能火中。第一个插入的技能电一定会放在伤害值最大的技能火前面，然后用这个电的伤害替代后面火的
2020-08-16 18:28:23
259
原创 HDU 6836 Expectation（期望，矩阵树定理）
1010 Expectation（期望，矩阵树定理）传送门题目大意 给一个无向连通图，任意从图中取出一个生成树（该图的所有生成树等概率被取到），求该生成树每条边权进行位运算AND后的期望值。解题思路 位运算题目通用的思路，按位计算，累加贡献。我们可以只看每条边权的第i位，这样就可以把这个图的所有边权变成0和1（1表示原来边权在第i位上的值是1，0同理）。根据期望的线性性质:E(X+Y)=E(X)+E(Y)E(X + Y) = E(X) + E(Y)E(X+Y)=E(X)+E(Y)所求的期望值就
2020-08-06 22:05:33
367
原创 Atcoder 171_f K.Strivore(有技巧的组合数学)
Atcoder 171_f K.Strivore(有技巧的组合数学)传送门题目大意给一个长度为m字符串，问插入n个字母后可以形成多少种不同的字符串。解题思路 一种错误的解法是把给定的字符串中的每个字符看成隔板，然后利用插空法计算有多少种插入方法，最后再乘上26的n次方。这种做法有一个明显的问题就是没有考虑去重。例如：给定字符串abc插入两个字符，首先给定的字符串充当隔板将字符串分隔成“①a②b③c④”。如果我们在②号位插入“ba”得到字符串ababc，同时我们在③号位置插入“ab”也得到字符串a
2020-07-11 23:26:03
358
原创 正弦稳态电路的阻抗和功率
阻抗和导纳 阻抗和导纳是电阻和电导在正弦稳态电路上的一种推广，反应了电路元件两端电压与电流的幅度关系和相位关系。阻抗定义式：Z=defU˙I˙=UI∠(ϕu−ϕi)=∣Z∣∠ϕZZ \xlongequal {def} \frac{\dot{U}}{\dot{I}} = \frac{U}{I} \angle (\phi_u - \phi_i) = |Z|\angle \phi_ZZdefI˙U˙=IU∠(ϕu−ϕi)=∣Z∣∠ϕZ复数形式：Z=R+jXZ = R + jXZ=R+j
2020-06-17 15:50:16
4788
原创 CF 1366F Jog Around The Graph(贪心，DP)
题目描述题目链接 题目大意是给你一个n个点m条边的无向图，从一号点出发，走i条边，找出满足这个条件的路径的最长的长度，记为lil_ili。然后求出l1,l2,⋯ ,lpl_1,l_2,\cdots,l_pl1,l2,⋯,lp之和，答案对109+710^9 + 7109+7取模。注意每条边都可以重复走。数据范围2≤n≤20002 \leq n\leq 20002≤n≤2000n−1≤m≤2000n - 1 \leq m \leq 2000n−1≤m≤2000m≤q≤109m\leq q
2020-06-13 22:41:39
891
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人