省赛训练1

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);
}

上一篇:计蒜客 蒜头君回家(有条件的BFS)


下一篇:【教程】BFS学习笔记