1.Cut the Deck
题意:选择一个位置,将这个位置及这个位置之前的字符移到后面,问是否存在这么一个最小的位置,使得任意位置的B的数量大于R的数量
题解:如果某一位置B的数量小于R的数量,那么舍弃这之前的部分,重新开始计数
#include<stdio.h>
#include<string.h>
char s[1000010];
int main() {
int t;scanf("%d", &t);
while (t--) {
scanf("%s", s);
int b = 0, r = 0, pos = 0, l = strlen(s);
for (int i = 0; i < l - 1; i++) {
if (s[i] == 'B') b++;
else r++;
if (r > b) {
b = r = 0;
pos = i + 1;
}
}
printf("%d\n", pos);
}
}
2.Grid of Letters
题意:八方向,求最长的连续字串
题解:dfs,下一个字符=上一个字符+1,可以剪枝
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int>p;
vector<p>v;
char s[1010][1010];
//int pos[8][2] = {-1, 0, -1, 1, 0, 1, 1, 1, 1, 0, 1, -1, 0, -1, -1, -1};
int maxn = 1;
int n, m;
void dfs(int x, int y, int len)
{
for (int i = -1; i <= 1; i++)
for (int j = -1; j <= 1; j++) {
if (!i && !j) continue;
int nx = x + i, ny = y + j;
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (s[nx][ny] == s[x][y] + 1) {
maxn = max(maxn, len + 1);
if (maxn == 26) return;
if ('Z' - s[nx][ny] + 1 + len <= maxn) return;//下一个字符能达到的最大长度+上一个字符之前的长度
dfs(nx, ny, len + 1);
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
scanf("%s", s[i]);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
int vex = 0;
for (int k = -1; k <= 1; k++)
for (int g = -1; g <= 1; g++)
if (s[i][j] == s[i + k][j + g] + 1) vex++;
if (!vex) v.push_back({i, j});//将入度为0的点放入数组,保证这个点之前没有前继,即这个字符是起点
}
for (int i = 0; i < v.size(); i++) {
int x = v[i].first, y = v[i].second;
if ('Z' - s[x][y] + 1 > maxn) dfs(x, y, 1);
}
printf("%d\n", maxn);
}