算法题

算法题

23 篇文章

算法

算法

0 篇文章

比赛记录

比赛记录

3 篇文章

杂谈

杂谈

0 篇文章

补题

补题

2 篇文章

记录

记录

0 篇文章

八皇后
2025-12-15 218 字 2 分钟

八皇后

题目传送门 大致思路 经典题目,搜索,$a[i]$表示第i行的皇后在第几列 用dfs按行递归,对当前行的每一列做一个尝试,合法就作为答案备选 判断不合法:与先前的皇后在同一列,或在同一条斜线上($|y_1-y_2| == |x_1-x_2|$) Code 1234567891011121314151617181920212223242526272829303132333435363738void dfs(int row) { if (row >8) { cnt++; for (int i = 1; i &lt
带方向限制的bfs
2025-12-15 332 字 2 分钟

带方向限制的bfs

题目传送门 大致思路 求最短路径,想到bfs,但是带有方向限制,可以在队列中加入一些"标签"来限制 同时要注意vis数组并不能只有二维,因为可能不同方向来到同一个位置产生的答案是不一样的,不能到了一次之后,就不再去了,用三维来加一个方向标签 Code 1234567891011121314151617181920212223242526272829303132void solve() { int m,n; cin>>m>>n; vector<vector<int> > a(n+1,vector
牛客周赛 Round 122(补题)
2025-12-15 389 字 2 分钟

牛客周赛 Round 122(补题)

比赛传送门 E 记dp[i]为以i为起点的数组有几个好数组,如果i位置开始有一个块,那么可以状态转移(自己的块加上后面原有的好数组)注:k为a[i] $$dp[i]=1+dp[i+k] $$否则 $$dp[i]=0 $$最终答案就是dp数组的总和 接下来的问题就是如何快速判断i位置开始是否有一个块了: 预处理一个数组 s 其中s[i]表示从位置 i 开始，向右连续出现且值与 a[i]相同的元素所能到达的最远下标 从右往左扫描: 如果$a[i]==a[i+1]$ 那么$s[i]=s[i+1]$ 否则$s[i]=i$ 如果$i+k-1
牛客周赛 Round 122(比赛记录)
2025-12-15 623 字 4 分钟

牛客周赛 Round 122(比赛记录)

比赛传送门 A 没什么好说的,打表根据 n 输出就行 Code 1234567void solve() { vector<char> a{'A','B','C','D','E','F','G','H','I','J','K','L','M'}; int n; cin &gt
背包判断能否用n个数之和表示某个数
2025-12-11 1.2k 字 6 分钟

背包判断能否用n个数之和表示某个数

内容概述 本篇有两题 第二题为第一题的进阶,个人感觉题很不错 1.题目传送门 大致思路 选取100个数组内的数 k ($1≦k≦10$) 可以明确的是n足够大(可选够多)时肯定可以选出来,接下来讨论怎么解决 n 比较小的时候 我们可以用一个桶记录这些数出现的次数 cnt 十的倍数我们可以转化为 末位数字为 0 的数字 ,那么怎么转化为背包问题? 选100个数(容量) ,这些数字的末位数字就为价值 记dp[s][r],s为当前选了多少数,r表示能取到的末位数字. 遍历每一个数字(1-10) 对应末位数字为 0-9 ,做一个背包问题 $$dp[s+t][newr]=dp[s][ol
矩阵取数游戏
2025-12-11 509 字 3 分钟

矩阵取数游戏

题目传送门 大致思路 不难发现,每一行取数的结果都是相互独立的,故可以对每行单独处理,将每行的结果进行累加得出答案 那么如何计算每行答案? 记dp[i][j],表示区间[i,j]的分数结果,则状态转移方程为 $$dp[i][j]=max(dp[i+1][j]+val,dp[i][j-1]+val) $$val为取对应数能获得的分数,我们可以预处理一个2的幂数组,快速得出答案 注意答案可能很大,我们用__int128类型计算 Code 1234567891011121314151617181920212223242526272829303132333435363738394041
并查集
2025-12-11 322 字 2 分钟

并查集

题目传送门 并查集板题 Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879#include <bits/stdc++.h>using namespace std;#define int long long#define lll __int128#define Mio_qh signed#define el '\n&
观察数据范围并根据数学公式进行枚举(CF2132B)
2025-12-10 350 字 3 分钟

观察数据范围并根据数学公式进行枚举(CF2132B)

题目传送门 蒟蒻的第一篇博客 大致思路 记x右边添加了k个0,那么就有: $$y=10^k*x $$$$n=x+y=x*(10^k+1) $$又有$11≤n≤10^{18}$,于是可以枚举$10^k$,最多枚举18次 当n能被$10^k+1$整除时 答案就是 $n/(10^k+1)$,最后排序一下输出即可 Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626