- 博客(138)
- 收藏
- 关注
RSS订阅
原创 关于数据结构一些自己的理解与总结与题目
关于并查集：一定是他的集合与集合里面的最顶层的父亲的关系若是权值并查集 一定是父亲的值相加减 因为成员的值不一定准确acwing 239题目大意 给你一个n 假设有一个01序列给你一个m 给你m个条件 问你第几次条件的时候是矛盾的string am的 格式是 给你一个 l r 和 aa为even 表示 l~r 里面有偶数个1思路有两种 1.用前缀和的想法 若 l ~ r为偶数 那么前缀 l - 1 与 前缀 r 的 1的个数相同 若l ~ r为奇数 则不同2.存一个集合 fa[i]
2021-03-31 20:01:34
281
原创 一些有用的状态转移
1.二进制 子集的最大值for(int i = 0; i < 24; i++){ for(int j = 0; j < (1 << 24); j++{ if((j >> i) & 1){ dp[j] = max(dp[j],dp[j ^ (1 << i)]; } }}
2021-03-24 20:15:12
95
原创 图论的知识
图论之二分图(1) 二分图的最小路径覆盖1.最小不相交路径覆盖 ：Res == 节点数-最大匹配数2.最小可相交路径覆盖：首先floyd算法跑出所有可以到达的点，之后Res==节点数-最大匹配数(2)二分图的最小顶点覆盖：定义：若选择一个点说明选择与它相连的所有边，最小顶点覆盖就是选择最少的点来覆盖所有的边。最小定点覆盖==二分图最大匹配(3)二分图最大独立集定义：选出一些顶点使得这些顶点两两不相邻，则这些点构成的集合称为独立集。最大独立集为包含顶点数最多的独立集。定理：最大独立集 =.
2021-03-02 12:28:37
663
1原创 将图片1920 * 1080图片缩放成 320*180并且填充 320*70 320*70 变成320*320 jpeg
放 rgba转化成jpeg的 部分 其他部分利用了T31开发库 很麻烦//rgba -> rgb int clipRgbaToJpgFile(const char *pFileName, const char* pRgbaData, const int nWidth, const int nHeight, const int nClipLeft, const int nClipTop, const int nClipWidth, const int nClipHeight){ char*
2022-03-31 11:46:26
708
原创 基于HTTP的服务器代码
#include<bits/stdc++.h>#include<sys/socket.h>#include<arpa/inet.h>#include<unistd.h>using namespace std;void headlestaticfunc(int fd,char *filename,char *args){}void headlestatic(int fd,char *filename){}void headledy
2022-03-04 17:00:04
812
原创 ping包原理的解析(可能不准确)
首先明白ping是通过网络层的 ICMP协议发送数据包至对方主机并且对方回包才能ping通的 首先发送ICMP前 我们并不知道对方主机的网卡地址(MAC)我们需要用ARP广播通过路由得到对方的MAC然后再传递ICMP传递的ICMP报头包括IP报头代码步骤如下1.创建原始套接字用来发送ICMP2.创建双线程分别为发送ICMP以及接受ICMP3.发送ICMP前要设置报头内容以及校验码ICMP_ECHO = 8是发送请求的类型计算校验码4.接受对方的ICMP包利用select或者epoll来获
2022-02-28 18:42:27
1879
原创 对于tcp/ip建立小型聊天室的代码
客户端// 三次握手主要是创建连接// 四次挥手主要是释放资源// I/O 复用 epoll模式#include <iostream>#include <arpa/inet.h>#include <unistd.h>#include <strings.h> // bzero()#include <thread>//#include <sys/select.h>#include <sys/epoll.
2022-02-28 17:02:11
1884
原创 利用tcpdump抓包感悟的为什么centos7.6能ping通不同网段的ubuntu 而 ubuntu ping不同centos7.6
利用tcpdump抓包显示centos7.6 ping 通 ubuntu的情形是我们发现原ip和我们的centos的ip是不一样的为什么呢 因为有路由 我们centos是nat与主机共享 ip地址 主机拥有多个 不能网络的 ip地址 所以可以 通过网络ping通 ubuntu 而ubuntu是 桥接 桥接是直接连接物理网络 而我的物理网络是公司无线网 和我的 centos7.6不在同一网段 且 没有路由相连接 因为走的是虚拟路由vmnet0 而我的centos7.6走的是vmnet‘8 所以不成..
2022-02-23 17:14:15
122
原创 bzoj刷题合集
正式开始从2021年12.04年南京站结束由于本人知识点学习较乱使得在比赛中不能熟练运用为了提高这种能力进行一个bzoj经典题的刷与练习1.1001 最小割转换为最短路最小使用对偶图将图变成如下 转换为最短路 使得每个路为一个割的子集#include<iostream>#include<cstring>#include<queue>#include<utility>#define x first#define y secondusing
2021-11-26 14:04:12
540
原创 AtCoder Regular Contest 129 D题
题目题意是给你一个数组 有一个操作 是对于 i - 1 i i + 1 分别 -1 + 2 -1 若选 i == n i + 1 = 1首先我们就知道一个思路 -1 +2 -1 是 很明显的 一个差分数组后的一个方案 但是我有点nt 我进行了两次前缀和 使得最后得题意转化成了 给你个数组 每次操作可以让其中一个数 -1 最后得数组要变为递增 所以。。完全搞不来了 但是只前缀和一次的话 就是个经典问题 每次 操作 -1 +1 使得数组变为0 那就只要进行两次循环 暴力即可#include<
2021-11-25 00:00:29
318
原创 CF1575 K 思维
链接题意就是 给你一个大矩阵 和两个大小相同的子矩阵 但是 左上角的点可能不同 然后矩阵种得点的颜色要相同 问一共有多少种方案我们很容易进入一个误区这种情况里4个点是需要相同颜色的 我们就会想要去找 有多少个点和当前点颜色相同 但是其实 我们只需要考虑第一个矩阵不重叠的部分 因为矩阵2的部分一定会和矩阵1不重叠的部分一一对应 所以我们只需要 qpow(k,nm-rc)就行了...
2021-11-21 17:17:39
235
原创 Codeforces Round #755 (Div. 2, based on Technocup 2022 Elimination Round 2) E题
题意是 给你 个长度为 n的 数组 找到 子区间 l ~ r 使用1个操作 ai - 1 ai +1 - 1使得 所有子区间元素变为 0 的个数方法一: 考虑如何让子区间变为0 那肯定是 从左到右不停减去自身 使得最后一个元素 为 0 既 al - al + 1 <= 0 al + 1 - al - al + 2 <= 0 直到最后一个为0即可 我们只需要找到 第一个 > 0的位置并且 找到 0的个数就行 所以我们考虑维护 维护一个B数组上述1 ~ n的前缀 若我们要使 l为第一个位
2021-11-18 14:18:52
286
原创 CF1600E 博弈论 思维
Alice 和 Bob 正在玩一个游戏。他们得到了一个长度为 NN 由整数组成的数组 AA。他们正在一起建立一个序列。在开始的时候，这个序列是空的。在一个回合中，玩家可以从数组的左边或右边移出一个数字，并将其添加到序列的右侧。规则是：他们所建立的序列必须是单调递增的。赢家就是是做出最后一步的玩家。Alice 是第一个玩的。假设他们都以最佳方式进行游戏的情况下，谁能赢得游戏？题目链接首先能考虑到的就是 最大前缀递增 和最大后缀递减分别设他们大小为 C1 C2若 C1 C2都为奇数的话 无论怎么
2021-11-09 21:30:56
2545
原创 牛客月赛40 H rank1哥的妙蛙思想
题目链接大致思想就是假设有x的话那么直接输出就好了 如果 没有 x我们看他的倍数 y1 y2 y3… ym 如果 y2…ym都是 y1的倍数的话 那么肯定是不行的所以他这里做了一个处理 将每个数做后缀和 并且 开qpow(2,cnt) - 1 第二部分就是相减 如果 都是y1的倍数的话 那么 y1 要减去 y2…ym的数 又因为x是与他们相关的那么 x - y1 - y2…ym 又因为 y1 = y1 - y2…ym 且 x = y1 所以会变为 0 此时就是不存在这种情况 反之则存在 真的妙！#p
2021-11-05 23:16:04
84
原创 牛客2021年国集 第7场第4题和CF 1602E 思维+线段树
牛客题目牛客题意是 给出 1 ~ n其中 n / 2个偶数 的序列 然后插入 1~n n/2个奇数 问最小逆序对首先我们能想到 插入的数对 已经在原序列的数 是没有影响的 每当插入一个点时 逆序对增多的数量就是前面比他大的个数 和后面比他小的个数 这样 可以发现 我们插入 一定是从小到大 从左到右插入 这样后面插入的数 对已经插入的数 也是没有影响了的 我们只需要贪心插入即可 只要找到每个插入的最小影响值即可 我们可以想每当 插入 1 于数组 和插入 2于数组 会对数组产生 什么影响 是不是 若 把
2021-10-26 20:35:48
135
原创 2018 ccpcfinal Gym - 102055B滑动窗口
题意问你 给你 n个人 每个人 有两种属性 可以选择 A 选择 B 但是有些人 不能同时选 A或者 同时选B 问最后得到的 MAX - MIN 最小首先没有 人限制的话 那么就是个经典题 滑动窗口求 差值最小 只需要把两个值拆分 sort一下 然后每次找到 n 个人 的属性取一下 min 即可有限制的话 无非是 把人变成了联通块 多个联通块 组合求差值 此题 是 每个人选择两种值 每个联通块就有两种 maxn 和 minn 我们只需要拆分成 4种值进行排序即可#include<iostream&
2021-10-14 13:14:03
133
原创 hdu 4635 最多能加多少边使得图不变成强连通图
首先跑一遍tarjan 缩点无异议 缩完点后 若scc_cnt = 1 那么直接输出 -1 对于多个点的连通图来说 首先缩了点的那个点 里面的点是随便 连的 sum += sz[i] * (sz[i] - 1) 最后减去已连的就好了再其次就是 缩完点之后的图 是树 因为树 是单向边 所以我们可以把 已经按照那个方向 那个点全都 连上 其次就是还有反向边 反向边一定要剩下至少一个点没有连反向边 并且是叶子节点 这样我们就能完全选完了#include<iostream>#include<
2021-10-07 22:07:32
76
原创 POJ - 3694填边求桥
在无向图求完tarjan 并且缩点后 剩下的是树 树上的边全是 割边 添加 x，y联通块 之间的树边全变为普通边 所以我们只需要 维护联通块 即可 可以使用并查集 复杂度约为 mq 此题我们可以直接考虑 用 on的方法来找lca 复杂度为 nm 考虑一下正确性考虑一下此图 点2到点5与点4到点7是否会错过 因为 倘若先走2 - 5那么6 就会成为7的父节点 而不是 4 若先走2 - 3那么 也是正确 所以on找 父节点是可以的#include<iostream>#include<
2021-10-07 13:41:51
72
原创 hdu2121 最小树形图 (无根）
加入一个虚点 往每条边放入INF 这样的话 最多只有一条边会与他 相连只需要记录一下第几个点是和虚点相连即可注意！不查重比较简便！#include<iostream>#include<cstring>#define INF 0x3f3f3f3fusing namespace std;const int N = 1100,M = 11000 + N;struct node{ int x,y,w;}a[M];int dis[N][N];int n,m
2021-10-03 14:49:56
118
原创 最小生成树prim 求得 树上两点之间的最大最小值
#include<iostream>#include<cmath>#include<cstring>using namespace std;const int N = 1010,M = N * 2;int head[N],to[M],last[M];double w[M];int cnt;void add(int a,int b,double c){ to[++cnt] = b; w[cnt] = c; last[cnt] = h
2021-09-27 20:27:49
136
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人