牛客竞赛每日俩题 - Day13
目录
洪泛法BFS
26进制计数字符串
洪泛法BFS
红与黑__牛客网
- 找到‘@’所在的位置，即起始搜索的点
- 使用DFS搜索地板中的每块瓷砖，如果是黑色，给计数+1，然后像该黑色的上下左右四个方 向继续搜索
#include
using namespace std;
#include
#includeconst int N=21;
typedef pair PII;
int n,m,x,y;
int d[N][N];
char g[N][N];int bfs(int x,int y)
{queue> q;q.push({x,y});memset(d,-1,sizeof d);d[x][y]=0;int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};int sum=1;while(q.size()){PII t=q.front();q.pop();for(int i=0;i<4;i++){int gx=t.first+dx[i],gy=t.second+dy[i];if(gx>=0&&gx=0&&gy>n>>m){for(int i=0;i>g[i][j];if(g[i][j]=='@'){x=i,y=j;}}cout< 26进制计数字符串
字符串计数_美团笔试题_牛客网
思路：
题目非常简单，求字典序在s1和s2之间的，长度在len1到 len2的字符串的个数,
我们可以利用ASCII码（字符相减）快速求出两个字符之间含有的字符数
字符有26个，于是我们想到将字符串转化为26进制数，做相减操作，即可求出之间的字符串数
问题一：长度不同如何计算
思路是像计数一样补位相减，如：len2==2时，“a_” 与 “b_” 之间有aa、ab.....az（26个字符串），所以在s1后面补 ‘a’，在s2后面补 ‘z’+1即可
问题二：如何转26进制
为了防止数字太大，采用逐位相减后乘对应进制位；如23 - 17，变为（2-1）*10^1+(3-7)*10^0=6;
利用array数组存储各个位的差值，由题目性质发现字符串第0位，就是进制数第0位，累加和
for (int k = 0; k < i; k++) {result += array[k] * pow(26, 字符串长度 - 1 - k);//加上每一位的差值 }
#include
#include
#include
#include
#define N 1000007
#include
using namespace std;
int main()
{string s1, s2;int len1, len2;while (cin >> s1 >> s2 >> len1 >> len2){//将该字符串看成是26进制数，为了简单起见，将s1和s2补长到len2长度// 注意：s2补的是'z'+1, 因为'z' - 'a' = 25s1.append(len2 - s1.size(), 'a');s2.append(len2 - s2.size(), (char)('z' + 1));// 确认s1和s2的两个字符串每个位置上的差值vector array(len2);for (int i = 0; i < len2; i++) {array[i]=s2[i] - s1[i];}// 确认len1和len2之间可组成的不同字符串的个数long long result = 0;//long long 防止爆intfor (int i = len1; i <= len2; i++) {//查找每种长度的字符数for (int k = 0; k < i; k++) {result += array[k] * pow(26, i - 1 - k);//加上每一位的差值}}//所有字符串最后都不包含是s2自身，所以最后要减1；cout << (result - 1) % N << endl;}return 0;
} 
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！