weixin_43485513的博客

原创 自备ACM模板 —— 数据结构篇

ST表// 求区间最值 洛谷 P3865#include<bits/stdc++.h>using namespace std;int n, k, num[100005];int ma[100005][25]; // n*lognvoid pre(){ for(int i = 1; i <= n; i++) ma[i][0] = num[i]; int s = 2, s2; for(int j = 1; s <= n; j++, s

原创 自备ACM模板 —— 字符串篇

KMP//打印 s2 串在 s1 串的位置 洛谷 P3375#include<bits/stdc++.h>using namespace std;int net[1000005];char s1[1000005], s2[1000005];void getnet(char s[]){ int i = 0, j = -1, len = strlen(s); net[0] = -1; while(i < len){ if(j==-1||s[j]==s[i]) net

原创 自备ACM模板 —— 数学篇

高精度// BigIntegerBigInteger abs() 返回大整数的绝对值BigInteger add(BigInteger val) 返回两个大整数的和BigInteger and(BigInteger val) 返回两个大整数的按位与的结果BigInteger andNot(BigInteger val) 返回两个大整数与非的结果BigInteger divide(BigInteger val) 返回两个大整数的商double doubleValue()

原创 Games101 作业7 路径追踪

       学霸笔记       还是学霸笔记       写这个作业写 bugbugbug 写到吐了，首先强调一点，windowwindowwindow 下跑这份代码的同学，需要修改 global.cppglobal.cppglobal.cpp 中的 get_random_floatget\_

原创 Games101 作业6 AABB包围盒 + BVH 加速结构

       老规矩，上 学霸笔记       光线生成void Renderer::Render(const Scene& scene){ std::vector<Vector3f> framebuffer(scene.width * scene.height); float scale = tan(deg2rad(scen

原创 Games101 作业5 光线与三角形相交

学霸笔记       如果是使用 windows 跑代码的同学，需要把 CMakeLists.txt 下的两处 -fsanitize=undefined 关键字给去掉，才能正常编译。       本次作业非常简单，建议可以看看 RayTracingInOneWeekend 进一步学习。      &nb

原创 Games101 作业4 贝塞尔曲线

       递归即可cv::Point2f recursive_bezier(const std::vector<cv::Point2f> &control_points, float t) { // TODO: Implement de Casteljau's algorithm if(control_points.size() == 1) return control_poin

原创 C++ 面经

文章目录智能指针unique_ptrshared_ptrweak_ptr左值、右值以及派生概念智能指针       使用普通指针，可能造成堆内存泄露（忘记释放），二次释放，程序发生异常时内存泄露等问题等。C++11中引入了智能指针的概念，方便管理堆内存。智能指针的作用是在适当的时间自动的删除指向的对象。在面对异常时格外有用。       智能指针是利用了一种叫做R

原创 Games101 作业3 interpolate + phong + texture + bump

       学霸笔记       又是学霸笔记       还是学霸笔记       rasterize_triangle 在作业2的基础上对法向量、颜色、纹理颜色与底纹颜色(Shading Colors) 进行插值。翻阅代

原创 Games101 作业2 cross + BoundingBox

       设a(x1,y1),b(x2,y2)a(x_1,y_1),b(x_2,y_2)a(x1​,y1​),b(x2​,y2​)，叉乘：a⋅b=x1y2−x2y1a\cdot b=x1y2-x2y1a⋅b=x1y2−x2y1       实现叉乘，代码意思对即可static bool insideTriangle(int x, int y, const Vec

原创 Games101 作业1 旋转矩阵 + 透视投影

       课程链接       学霸笔记       绕 Z 轴旋转很简单，如果希望旋转方向相反，将 alpha 换为 -alpha 即可Eigen::Matrix4f get_model_matrix(float rotation_angle){ Eigen::Matrix

原创 SPOJ LCM Sum(Hard) 欧拉函数 + 换枚举对象

       求 ∑i=1nLCM(i,n),(1≤n≤1e18)\sum_{i=1}^nLCM(i,n),(1\le n\le 1e18)∑i=1n​LCM(i,n),(1≤n≤1e18)       #include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdi

原创 codeforces 1499E DP

       给定两个串 xxx 和 yyy。定义 zzz 为从 xxx 串和 yyy 串的归并而成的字符串，归并顺序自定义，要求得到的 zzz 串相邻字符不相同。问你 xxx 和 yyy 的所有子串能构成 zzz 的方案数有多少种。       定义 dp[i][j][a][b][c]dp[i][j][a][b][c]dp[i][j][a][b][c]，dp[i][

原创 Codeforces 585E 莫比乌斯反演 + 容斥

       给定 n(2≤n≤5e5)n(2\le n\le 5e5)n(2≤n≤5e5) 个数，2≤ai≤1e72\le a_i\le 1e72≤ai​≤1e7。       一次操作中，从数组 aaa 中选定一个 xxx，再从剩下的数中选出一个 gcd⁡>1\gcd>1gcd>1 的非空集合 YYY，使得所有选中的数的 gcd⁡=1\gcd=1

原创 CodeForces1473E 分层图 + 最短路

       定义一条路径上的值为 ∑i=1kwei−max⁡i=1kwei+min⁡i=1kwei\sum\limits_{i=1}^{k}{w_{e_i}} - \max\limits_{i=1}^{k}{w_{e_i}} + \min\limits_{i=1}^{k}{w_{e_i}}i=1∑k​wei​​−i=1maxk​wei​​+i=1mink​wei​​，求 111 到每个点的路径的最小值。  &nbs

原创 Codeforces 919E 中国剩余定理 + 线性时间求逆元 + 折半搜索

       计算有多少 n(1≥n≥x)n(1\ge n\ge x)n(1≥n≥x) 满足n⋅an≡b(mod p)n\cdot a^n\equiv b(mod\ p)n⋅an≡b(mod p)       a,b,p,x(2≤p≤106+3)(1≤a,b<p)(1≤x≤1012)a,b,p,x(2 \leq p \leq 10^6+3)

原创 洛谷 P2387 [NOI2014] 魔法森林 LCT + 排序 + 枚举

       每个点含有两种点权 a,ba,ba,b。问 111 到 nnn 的最小代价，最小代价定义为 111 到 nnn 的路径上的 amax+bmaxa_{max}+b_{max}amax​+bmax​。       我们按 bbb 排序，维护 aaa 的最小生成树。也就是我们考虑把排序后的边，逐个加入到最小生成树中。bmaxb_{max}bmax​ 已经固定了

原创 洛谷 P4234 LCT + 排序 + 枚举

       求边权最大值与最小值的差值最小的生成树，输出这个差值大小。       按权值排序，我们等同于枚举最大值，然后更新生成树让生成树的最小值尽可能最大。       也就是每次加入边，若构成环，则去掉环上最小值。      &

原创 Codeforces 1467E DFS序 + 树上差分

       题目大意为，定义合法的根：根到任意结点的路径上的点权唯一，求合法的根的数量。       我们很容易想到，合法的根的数量 = 总点数 - 非法根的数量。       对于任意点权相同的结点，只有它们之间的路径上的结点以及结点的子树才有可能合法，除此之外一定不合法。 &nb

原创 ACM技能树图示版

转载 ACM 技能树

文章目录ACM-ICPC PreparationProgramming LanguageData StructuresSorting & SearchingStringsAlgorithmsDynamic Programming algorithmsGraph algorithmsGreedy algorithmsGeometric algorithmsNetwork Flow algorithmsMathematicsACM-ICPC PreparationThe first step in

原创 Codeforces gym102471C 狄利克雷卷积性质 + 狄利克雷卷积计算

       首先给出结论：（下述结论成立基于对 modmodmod 取模情况下）。       当 f(1)=1f(1)=1f(1)=1，fmod+1=ϵ(f(1))∗ff^{mod + 1} = \epsilon(f(1))*ffmod+1=ϵ(f(1))∗f，fmod=ϵ(f(1))f^{mod}=\epsilon(f(1))fmod=ϵ(f(1))。&nbs

原创 Codeforces 1451F Nimm博弈变形

       题目给定一个 n∗mn*mn∗m 大小的网格图，每个格子有一个非负整数。       每个人从一个非零格子作为矩形的左上角，将该格子的数减去一个非零值，其余矩形内的格子的数值任意变化（可不变），两人轮流操作，问先手后手赢？       当且仅当所有左斜对角线的异或值为 000 时，后

原创 2018ICPC 南京 Mediocre String Problem 扩展KMP + Manacher

       题目大意为计算 SSS 串的子串 sss 串和 TTT 中的前缀 ttt 串拼起来是回文串的种数的总贡献，要求 sss 串长度大于 ttt，s+ts+ts+t 是回文串，sss 和 ttt 串非空，拼起来的串视作不同种当且仅当 sss 或 ttt 串的位置不同。       我们把 sss 串分成 s1+s2s_1+s_2s1​+s2​ 两个部分，其中

原创 Codeforces 432D 后缀自动机 + 起始位置标记

       这道题我用后缀自动机来写，就加个简单的标记数组，记录下串的结束位置，也就是该串的第一次出现位置。然后建 failfailfail 树，dfsdfsdfs 遍历。       子树代表的就是以当前结点的串为后缀的子串，那么我们从子树那里继承过来的最大 pospospos 也就是该结点的串的最后一次的出现位置，根据题意，我们找同时出现在前缀和后缀的字符串即可

原创 CodeForces 1422F 线段树 + 主席树 + 卡常

       首先 lcm(al,al+1,..,ar)=pimax(ki)pi+1max(ki)...)lcm(a_l,a_{l+1},..,a_{r})=p_i^{max(k_i)}p_{i+1}^{max(k_i)}...)lcm(al​,al+1​,..,ar​)=pimax(ki​)​pi+1max(ki​)​...)，也就是范围内的所有数的质因子的最高幂次的乘积。     &

原创 洛谷 P3181 广义后缀自动机 + DFS序遍历

       建立一个广义后缀自动机然后统计同一节点下 子串个数 * a串的节点出现次数 * b串的节点出现次数，利用 DFSDFSDFS 序遍历所有节点，在返回时将子节点的大小累计至父节点即可。#include<bits/stdc++.h>#define endl '\n'using namespace std;typedef long long LL;const int maxn = 8e5 + 5;cha

原创 Lightoj 1356 分解质因数 + 二分图匹配

       首先我们有一个定理：最大独立子集 = 结点数量 - 最大匹配。       然后这题关键就在于建图了，假设 a=prime∗ba=prime*ba=prime∗b ，我们考虑 a,ba,ba,b 中质因子个数为奇数的数连到质因子个数为偶数的数上面。（反正就是确定一个有向图方向，统一即可）     &nb

原创 Codeforces 1420 D 离散化 + 排序 + 树状数组

       昨天看到题本来就能秒出的，结果组合式公式套错了。。。Cnm=PnmPmm=n!m!(n−m)!C_n^m=\frac{P_n^m}{P_m^m}=\frac{n!}{m!(n-m)!}Cnm​=Pmm​Pnm​​=m!(n−m)!n!​       我们考虑先离散化 lll, rrr，因为如果我们想用树状数组维护的话，1e91e91e9 的数据显然是不

原创 Codeforces 1405E 二分套树状数组 + 树状数组

       给定一个序列，当 ai=ia_i=iai​=i，也就是对应位置的数字等于下标时，可以删除这个数。然后该数之后的数全体前移一位。       于是我们很容易可以得到结论，令 fif_ifi​ 为前 iii 个数可以删的个数。当前数可以删除当且仅当 i−ai≤fii-a_i\le f_ii−ai​≤fi​，且总能找到一个方法删掉它（简单证明，当同时存在 ai

原创 Codeforces 1406E 时间复杂度优化 + 思维

       给你一个 nnn，要求你找到一个 1−n1-n1−n 以内的 xxx。给定三种操作， A aA\ aA a 查询当前有多少 aaa 的倍数，aaa 范围 1−n1-n1−n，B aB\ aB a 查询当前有多少 aaa 的倍数，并删掉所有除 xxx 外 aaa 的倍数，aaa 范围 2−n2-n2−n，CaC aCa，表示打印答案。    &

原创 洛谷 P3346 广义后缀自动机 + 树上求字符串

       题目给定一棵树，树上每个结点有一个特定的值，定义一个序列是任选两点 A,BA, BA,B（可以相同），AAA 点到 BBB 点之间的所有结点上的值构成的一个序列。若 A=BA=BA=B，自然这个序列长度就为 111啦。       题目问你有多少种本质不同的序列，有个小细节，题目说度为 111 的结点不超过 202020 个，这里我们就可以从所有的叶子结

原创 洛谷 P3975 后缀自动机 + 建link树 + 字典树统计字符串个数

       题目给定一个字符串 sss，指令 ttt， ttt 为 111 则不同位置的相同的串视作不同，为 000 则视作相同，问你字典序第 kkk 小的串。       首先按照 linklinklink 来建树，自下而上除 clonecloneclone 点外长度递减。我们标记所有 endposendposendpos 等价类，也就是插入的每个字符对应的状态，

原创 LightOJ 1315 博弈 + SG函数 + 记忆化搜索

       不懂 SGSGSG 函数的可以看我的博客 数学篇 ，这题给定一个无限大的二维平面，但是限制了左上角的位置，棋子的可行方向如图所示。       同样也是两人轮流移动多个棋子，无合法操作时输掉游戏，问你先手胜还是后手胜。       这题因为他的子状态到当前状态的递推关系不是线性的，

原创 HDU 6868 莫比乌斯函数 + 找规律 + 记忆化离线处理

       定义 f(n)=∑d∣n∣μ(d)∣f(n)=\sum_{d \mid n}|\mu(d)|f(n)=∑d∣n​∣μ(d)∣，给定 n,mn,mn,m 求 ∑i=1mf(ni)\sum_{i=1}^mf(ni)∑i=1m​f(ni)，结果对 1e9+71e9+71e9+7 取模。       易得 f(n)=2w(n)f(n)=2^{w(n)}f(n)=

原创 HDU 6791 Border 理论 + 回文自动机 + 树上倍增 + 双哈希

       题目给定一个字符串，两个人都会选取其中一个回文串。接下来，构造一个新串，持续的添加字母，每个字母有等同的概率出现，问你谁选取的字符串最大可能最先出现。       介绍一下 BorderBorderBorder 理论。对于一个长度为 LLL 的序列 AAA，若 A[1, i]=A[L−i+1, L]A[1,\ i] = A[L - i

原创 洛谷 P4762 回文自动机 + 线性动态规划

       题目给定两种操作：       一、复制当前串并将复制后的串翻转，接至当前串末尾或头部（本质上是同一种操作）       二、添加单个字符至当前串开头或结尾。（本质上是同一种操作）       问你，最少几步操作

原创 HDU 6833 莫比乌斯反演 + 数论分块

       给定下列式子:∑a1=1n∑a2=1n...∑ax=1n(∏j=1xajk)f(gcd⁡(a1,a2...,ax))⋅gcd⁡(a1,a2...,ax)\sum_{a_1=1}^n\sum_{a_2=1}^n...\sum_{a_x=1}^n(\prod_{j=1}^xa_j^k)f(\gcd(a_1,a_2...,a_x))⋅ \gcd(a_1,a_2...,a_x)a1​=1∑n​a2​=1∑n​...ax​=1∑n​

原创 HDU 6850 博弈

       首先，我们知道博弈的策略其实是把必输的策略留给对手。体现在这题中，就是当对手选中的边抵达最大边的一端时，然后我们选择最大边，则我们胜利。       那么我们就要想办法把最大边的一端留给对手，以此类推的，我们倒着标记最大边的两端。然后逐个标记，两端没有被标记的次大边，次次大边等。当我们的第一个点被标记时，我们就获得了游戏胜利。  &

原创 洛谷 P2414 AC自动机 + fail树按dfs序求区间和

       题目给定一个字符串，若为小写字母则表示加入该字符。若为 PPP，则打印当前字符串，并换行（打印后当前字符串不变）。若为 BBB ，则删除当前字符串的最后一位。给定 mmm 次查询，问你第 xxx 次打印的字符串在第 yyy 次中出现了几次。       首先我们清楚一点，在 ACACAC 自动机中的 failfailfail 树上，当 aaa 可以通过