付诺の小站

Robot on the Board 2题目大意 机器人站在一个$n\times m$大小的矩阵上，每个单元格都写有’L’、’R’、’U’和’D’当中的某一字符，表示机器人在此格移动方向——分别为左、右、上和下。 当走出矩阵或者走到已经访问过的单元格时停止移动。问，机器人从哪个单元格出发能移动的步数最多，输出单元格的坐标以及最大数量的步数。 解题思路 翻译一下题意即为，给定一个有向图，每个点的权值为$1$，且每个点只有一条出边，从某个点出发，每个点只能经过一次，求从何处出发所经过点的权值和最大，并求出最大值。 那么直接枚举每个点进行记忆化搜索即可，考虑到有环的存在，可以开个数组记录当前点的状态，如：$0$表示未被搜索到，$1$表示正在被搜索中，$2$表示已经被搜索过了。那么如果我们在搜索中遇到了状态为$1$的点就意味着碰到环了，此时记录一下环的大小即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include <bits/stdc++.h ...

Pa?sWorD题目大意 给定一个字符串s，其中只包含小写字母，大写字母，数字和问号$?$。可以进行一下操作： 将小写字母变为相对应的大写字母或不变； 将问号$?$变为大写字母，小写字母或数字中的任意一个字符。 要求满足以下条件的所有方案数的数量： 字符串中至少有一个小写字母； 字符串中至少有一个大写字母； 字符串中至少有一个数字； 字符串中任意相邻字符不能相同。 解题思路 先考虑简单的三维$dp[i][j][k]$，表示第$i$个字符为$j$且前$i$个字符中各种字符的存在状态为$k$的合法数量。 其中$k$为一个三位二进制数，如： 100表示只存在数字； 010表示只存在大写字母； 001表示只存在小写字母。 剩余状态也是类似的道理。 然后考虑状态转移，转移的过程只有一个限制条件，即相邻字符不能相同，则状态转移如下： $$dp[i][x][k|t]=dp[i-1][j][k],x!=j$$ 其中，当$x$分别为小写字母，大写字母，数字的时候$t$分别为$1$，$2$，$4$。 假设当前遍历到小写字母，则当它为大、小写字母的时候分别进行状态转移；假设遍 ...

Klee likes making friends题目大意 总共n个人，从任意m个人里选两个人，求所需的最小价值。 解题思路 一眼看过去很像单调队列优化dp的典题，然后用单调队列做了半天，发现单调队列存储的信息太少了，做不了这个题。然后就想到了用后缀数组。$dp[i][j]$表示倒数第一个朋友是$i$，倒数第二个朋友是$j$，那么很容易得出倒数第三个朋友所属的区间为$[i-m,j-1]$，拿后缀最小值数组记录一下即可。 参考代码123456789101112131415161718192021222324252627282930313233343536373839404142#include <bits/stdc++.h>#define maxm 20010#define maxn 2010typedef __int128_t int128;using namespace std;const int inf=1e9;int w[maxm],dp[maxn][maxn]; //dp[i][j]表示到第i位且i,j是朋友的合法情况下的最小答案int g[maxn][maxn ...