引用站外地址，不保证站点的可用性和安全性 洛谷文章链接 xyx404 思路： 考虑到题目要求我们求的是出现相同数字的概率，所以我们可以使用 unordered_map 把每一个骰子中出现的数字的数量存下来。 然后进行循环枚举我们使用的两个骰子，注意到使用编号为 111 和 222 的骰子和使用编号为 222 和 111 的骰子的出现相同数字的概率其实是一样的，所以我们枚举使用骰子的时候可以通过让第二个骰子的编号 jjj 大于我们第一个骰子的编号 iii 来减少循环。 在枚举两个 unordered_map 中是否有相同的数时，也可以进行优化，我们可以枚举 unordered_map 中数字少的 unordered_map 中的数字，判断另外一个有没有相同的数字。 注意要开 long long。 浮点数用 double 就可以了。 代码： #include<bits/stdc++.h>using namespa ...

引用站外地址，不保证站点的可用性和安全性 洛谷文章链接 xyx404 题意： 给定 NNN 个袋子，每个袋子里有若干石子。每次操作可以选择两个袋子，将其中一个的所有石子倒入另一个。求所有操作结束后，各袋子石子数的异或和有多少种不同的可能值。 思路： 观察发现最终异或和的值仅与分组方式有关。每次合并操作相当于将两个袋子的石子合并为一个新的袋子，最终的分组可以看作将初始的 NNN 个袋子划分成若干非空子集，每个子集的石子总和构成最终的异或和。 可以通过动态规划逐步生成所有可能的分组方式。 处理每个石子堆时，对当前所有可能的状态进行扩展： 新增分组，将当前石子堆作为独立分组。 合并到已有分组，将当前石子堆合并到任意一个已有分组中。 最后进行去重统计。 代码： #include<bits/stdc++.h>using namespace std;#define LL long long#define itn i ...

引用站外地址，不保证站点的可用性和安全性 洛谷文章链接 xyx404 思路： 语法题。 考点：循环结构和分支结构。 将两个批改结果的和分别存下来，如果第一次的和大于等于 TTT，则输出第二次批改结果的和，否则输出第一次批改结果的和。 代码： #include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsigned long long int T=1;int n; int a[15],b[15];int main(){ cin>>n>>T; LL sum1=0,sum2=0; for(int i=1;i<=n;i++)cin>>a[i],sum1+=a[i]; for(int i=1;i<=n;i++)cin>>b[i] ...

引用站外地址，不保证站点的可用性和安全性 洛谷文章链接 xyx404 思路： 递归构建二叉树，并输出先序排列。 首先要知道后序排列、中序排列是怎么构成的。 后序排列是先左，然后右，最后根；中序排列是先左，然后根，最后右。 依此我们可以确定后序排列中的最后一个一定是这个树的根，我们可以将根的左右两边分为两个子树，左子树和右子树，在中序排列中在根左边的是左子树，在右边的是右子树，最后便可构建出二叉树。 例如样例： 给出了中序排列为 BADC，后序排列为 BDCA，可以看的后序排列的最后一个字母是 A，那么说明 A 是根，然后我们在中序排列中找到 A，此时 A 左边的是左子树里的，右边是右子树里的。 所以现在可以转换为： 左子树：中序排列为 B，后序排列是 B。 右子树：中序排列为 DC，后序排列是 DC。 接着我们一直递归直到不能递归就能构建出二叉树了。 样例可能有点小不好理解这里给出另一组再进行一次解释。 当中序排列为 ...

引用站外地址，不保证站点的可用性和安全性 洛谷文章链接 xyx404 思路： 引用站外地址，不保证站点的可用性和安全性 参考了 OI Wiki 背包 DP 模版题。 首先定义一个 dpdpdp 数组，其中 dpi,jdp_{i,j}dpi,j​ 表示第 iii 个物品在背包容量为 jjj 时的最大价值。 考虑转移。 枚举每一个物品在背包容量剩余 jjj 时可以得到的最大价值。 如果现在枚举的剩余容量 jjj 小于选择这个物品需要的容量，那么 dpi,jdp_{i,j}dpi,j​ 的最大值就是 dpi−1,jdp_{i-1,j}dpi−1,j​。 否则有两种情况，选和不选。 对于选的情况，背包的剩余容量会减小这个物品需要的容量，价值会增加这个物品的价值，故此情 ...

洛谷文章链接 思路： 模拟。 定义一个变量 givegivegive 表示现在可以给珠子的人数，再定义一个数组 RRR，RiR_iRi​ 表示有多少人只能给到第 iii 个人。 每一个成年的人在自己还要珠子的时候必须要给刚刚成年的人一个珠子，所以第 iii 个人要给 n−in-in−i 个珠子，可以得到 givegivegive 个珠子，如果第 iii 个人的数量加上之前成年的人给他的数量不够给后面所有的刚成年的，那么计算他能给到第几个人，更新 RRR 数组，并让 givegivegive 加一还要记得把 AiA_iAi​ 修改为 000；如果够那么 AiA_iAi​ 就等于他加上 givegivegive 后给减去他成年后还有多少个未成年的数量，givegivegive 也要加一。 更新完第 iii 个人后让 givegivegive 减去只能给到第 iii 个人的数量，也就是 RiR_iRi​。 代码： #include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#de ...

洛谷文章链接 思路： BFS。 如没学过，可以先看看 OI Wiki，然后把模版题 P1443 马的遍历做了。 考虑到题目要求，上一次横着走，那下一次就必须竖着走；上一次竖着走，那下一次就必须横着走，所以 BFS 的队列里的变量要多一个变量 cxcxcx 表示上一次走的方向，同时考虑到可能横着走到达这个点不可以到达终点，但是竖着走到达这个点可能可以到达终点，所以标记数组也要多一维，表示方向，当现在到达的点为终点时，说明可以到达输出答案。 其余的就是 BFS 的模版了。 代码： #include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsigned long longint h,w;int sx,sy,ex,ey;bool bj[1200][1200][4];char jz[1200][1200];struct node{ int x,y; int cx;// 上一次的上下/左右/起点 int step;};queue< ...

题目洛谷 思路： 二分答案。 要求找最小值最大，所以考虑二分。 对于每次二分的 midmidmid 最小需要跳跃的距离，进行一次检查，对于检查函数，为了确定编号为 iii 的岩石之前没有被删除的岩石是哪个，要定义一个 lastlastlast 存上一个没有被删除的岩石的编号，每次对比 DiD_iDi​ 和 DlastD_{last}Dlast​ 的差，如果小于我们二分到的距离就说明要移走，否则不要移走更新 lastlastlast 为 iii，如果要移走的岩石小于等于最多可以移走的岩石 mmm 说明这种情况是可能的，否则不可能。 答案为每个满足的 midmidmid 中的最大值。 注意起点和终点要在数组里，DDD 数组输入时不会有终点和起点，自行要添加。 代码： #include<bits/stdc++.h>#define LL long longusing namespace std;LL l,n,m;LL a[50003],maxx;bool check(LL mid){ int last=0,del=0; for(int i=1;i<=n;i+ ...

题目洛谷 题目 AtCoder 思路： 动态规划。 计算出最小编辑距离，并检查其是否小于等于 KKK。 二维动态规划： 现在先考虑二维 dpdpdp 数组的情况。 二维 dpdpdp 数组时，dpi,jdp_{i,j}dpi,j​ 表示将 SSS 的前 iii 个字符转换为 TTT 的前 jjj 个字符所需的最小操作数。 然后考虑转移。 在动态规划中，dpi,jdp_{i,j}dpi,j​ 表示将字符串 SSS 的前 iii 个字符转换为字符串 TTT 的前 jjj 个字符所需的最小操作数。为了计算 dpi,jdp_{i,j}dpi,j​，我们需要考虑三种可能的操作：删除、插入和替换。 具体来说： 删除：如果我们从 SSS 中删除一个字符，那么 dpi,jdp_{i,j}dpi,j​ 可以由 dpi−1,jdp_{i-1,j}dpi−1,j​ 转移而来，因为删除一个字符后，SSS 的前 i−1i-1i−1 个字符需要转换为 TTT 的前 jjj 个字符，这一步对应的操作次数加 111。 插入：如果我们向 SSS 插入一个字符，使得它与 TTT 的第 jjj 个字符匹配，那么 ...