@Dmaxiya 2018-08-17T10:23:43.000000Z 字数 5903 阅读 1103

Codeforces Round #442 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #442 (Div. 2)
过题数：3
排名：518/12327

A. Alex and broken contest

题意

判断给定字符串 $s$ 是否只包含 "Danil", "Olya", "Slava", "Ann" 和 "Nikita" 中的一个，且只包含一次。

输入

输入只包含一个字符串 $s~(1\leq|s|\leq100)$ ，字符串中每个字符只可能是小写字母、大写字母或者下划线。

输出

如果是则输出 $YES$ ，否则输出 $NO$ 。

样例

输入	输出
Alex_and_broken_contest	NO
NikitaAndString	YES
Danil_and_Olya	NO

题解

按题意判断。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
unsigned int pos;
string str;
string sub[5] = {"Danil", "Olya", "Slava", "Ann", "Nikita"};
bool judge() {
    int ret = 0;
    for(int i = 0; i < 5; ++i) {
        pos = str.find(sub[i]);
        if(pos != string::npos) {
            ++ret;
            ret += (str.find(sub[i], pos + 1) != string::npos);
        }
    }
    return ret == 1;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    while(cin >> str) {
        if(judge()) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

B. Nikita and string

题意

如果一个只包含字符 'a', 'b' 的字符串可以被分割成三个部分（这三个部分中任意一个部分都可能为空），第一个部分只包含 'a'，第二个部分只包含 'b'，第三个部分只包含 'a'，那么这个字符串就是漂亮的字符串。现在给出任意一个只包含 'a' 和 'b' 的字符串，从这个字符串中删除一些字符，使剩下的字符顺序不变地拼成的字符串是一个漂亮的字符串，问最后得到的字符串的长度最长为多少？

输入

输入只包含一个字符串 $s~(1\leq|s|\leq5000)$ ，字符串中的每一个字符只可能为 'a' 或者 'b'。

输出

最后得到的字符串的最大长度。

样例

输入	输出	提示
abba	4	这个字符串本身就是一个漂亮的字符串。
bab	2	这个字符串需要删去其中一个 'b' 来让这个字符串成为一个漂亮的字符串。

题解

用 $dp[i][0]$ 表示以第 $i$ 个字符为结尾，最后形成的漂亮字符串中，第一部分的最大长度， $dp[i][1]$ 表示以第 $i$ 个字符为结尾，最后形成的漂亮字符串中，第一部分加上第二部分的最大长度， $dp[i][2]$ 表示以第 $i$ 个字符为结尾，最后形成的漂亮的字符串中，三个部分的最大长度，由于第一部分与第二部分的字符都是 'a'，所以应该用一个 $flag$ 标记这个字符串中是否出现过 'b'。于是可以得到下面的 $dp$ 方程：

$dp[i][0]=\begin{cases} \max(dp[j][0])+1&j\in[0,i)&s[i]='a'\\ \max(dp[j][0])&j\in[0,i)&s[i]='b' \end{cases}\\ dp[i][1]=\begin{cases} \max(dp[j][1])&j\in[0,i)&s[i]='a'\\ \max(dp[j][0],dp[j][1])+1&j\in[0,i)&s[i]='b' \end{cases}\\ dp[i][2]=\begin{cases} \max(dp[j][1],dp[j][2])+1&j\in[0,i)&s[i]='a',flag=true\\ \max(dp[j][2])&j\in[0,i)&s[i]='b' \end{cases}$
由于 $\max(dp[j][t]),j\in[0,i),t\in[0,2]$ 表示的是离 $i$ 最近的 $dp$ 值，所以实际上只要用 $dp[3]$ 就能维护整个 $dp$ ，最新的 $dp$ 值就是 $\max(dp[j][t]),j\in[0,i)$ ，时间复杂度为 $O(n)$ （上面的 $dp$ 方程的时间复杂度为 $O(n^2)$ ）。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 5000 + 100;
bool flag;
int dp[3];
char str[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    while(scanf("%s", str) != EOF) {
        flag = false;
        memset(dp, 0, sizeof(dp));
        for(int i = 0; str[i]; ++i) {
            if(str[i] == 'a') {
                ++dp[0];
                if(flag) {
                    dp[2] = max(dp[1], dp[2]) + 1;
                }
            } else {
                dp[1] = max(dp[0], dp[1]) + 1;
                flag = true;
            }
        }
        printf("%d\n", max(dp[0], max(dp[1], dp[2])));
    }
    return 0;
}

C. Slava and tanks

题意

在一个 $1\times n$ 的一排格子上，每一格都可能有一辆坦克，当某一辆坦克被炸弹打中时，它就会移动向旁边的一个格子里，如果某辆坦克在第 $n$ 个格子里，它只能向第 $n-1$ 个格子移动，如果某辆坦克在第 $1$ 个格子里，它只能向第 $2$ 个格子移动，坦克只有在被打中时才会移动，它们不会主动移动，现在要设计一个投弹方案，使得投下最少炸弹的情况下，保证所有坦克都被打中至少两次。

输入

输入只包含一个整数 $n~(2\leq n\leq10^5)$ 。

输出

第一行输出一个整数 $m$ ，表示最少需要投放的炸弹数，第二行为 $m$ 个整数 $k_1,k_2,\cdots,k_m~(1\leq k_i\leq n)$ ，第 $i$ 个整数表示第 $i$ 次投放的炸弹位置。

样例

输入	输出
2	3 2 1 2
3	4 2 1 3 2

题解

首先将所有坦克逼到第奇数个格子里，然后向所有奇数格子里投弹，那些本来就在奇数格子里的坦克就会跑到偶数格子里，最后向所有偶数格子投弹，就能让所有坦克至少被傻蛋打中两次。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
int n;
bool flag;
void Print(int Index) {
    for(int i = Index; i <= n; i += 2) {
        if(flag) {
            printf(" ");
        }
        flag = true;
        printf("%d", i);
    }
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        flag = false;
        printf("%d\n", n + n / 2);
        Print(2);
        Print(1);
        Print(2);
        printf("\n");
    }
    return 0;
}

D. Olya and Energy Drinks

题意

在一个 $n\times m$ 的迷宫中，只有 '.' 和 '#' 两种字符，'.' 表示这个地方是一块空地，'#' 表示这块地方有障碍物，不能通过，要从起点 $(x_1,y_1)$ 走到 $(x_2,y_2)$ ，每步最长可以直走 $k$ 个方格（不能转弯，如果转弯则要算新的一步），问最少需要多少步。

输入

第一行包含三个整数 $n,m,k~(1\leq n,m,k\leq1000)$ ，接下来 $n$ 行每行一个长度为 $m$ 的字符串表示迷宫，最后一行为四个整数 $x_1,y_1,x_2,y_2~(1\leq x_1,x_2\leq n,1\leq x_2,y_2\leq m)$ ，表示起点和终点。

输出

输出从起点走到终点需要的最少的步数，如果无法到达则输出 $-1$ 。

样例

输入	输出	提示
3 4 4 `....` `###.` `....` 1 1 3 1	3
3 4 1 `....` `###.` `....` 1 1 3 1	8
2 2 1 `.#` `#.` 1 1 2 2	-1

题解

如果每次只能走一格，就是一个 $bfs$ ，对于每次可以走不同的长度，任意两格之间的距离就不再相等，跑最短路就要用 $dij$ ，而这题在转弯的部分要算上新的步数，所以这题需要存两个方向上的距离：水平方向上的最短距离和竖直方向上的最短距离，就可以跑 $dij$ 了。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 1000 + 100;
struct Node {
    int x, y;
    int dis;
    Node() {}
    Node(int xx, int yy, int d) {
        x = xx;
        y = yy;
        dis = d;
    }
};
bool operator<(const Node &a, const Node &b) {
    return a.dis > b.dis;
}
bool operator==(const Node &a, const Node &b) {
    return a.x == b.x && a.y == b.y;
}
int n, m, k;
Node s, t;
int dis[maxn][maxn][2];
char str[maxn][maxn];
priority_queue<Node> que;
const int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool in(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m;
}
int dij() {
    memset(dis, 0x3f, sizeof(dis));
    while(!que.empty()) {
        que.pop();
    }
    que.push(s);
    dis[s.x][s.y][0] = dis[s.x][s.y][1] = 0;
    while(!que.empty()) {
        Node tmp = que.top();
        que.pop();
        if(tmp == t) {
            return tmp.dis;
        }
        for(int i = 0; i < 4; ++i) {
            for(int j = 1; j <= k; ++j) {
                int xx = tmp.x + dir[i][0] * j;
                int yy = tmp.y + dir[i][1] * j;
                if(in(xx, yy) && str[xx][yy] != '#' && dis[xx][yy][i >> 1] > tmp.dis + 1) {
                        dis[xx][yy][i >> 1] = tmp.dis + 1;
                        que.push(Node(xx, yy, tmp.dis + 1));
                } else {
                    break;
                }
            }
        }
    }
    return -1;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    while(scanf("%d%d%d", &n, &m, &k) != EOF) {
        s.dis = 0;
        for(int i = 1; i <= n; ++i) {
            scanf("%s", str[i] + 1);
        }
        scanf("%d%d%d%d", &s.x, &s.y, &t.x, &t.y);
        printf("%d\n", dij());
    }
    return 0;
}

Codeforces Round #442 (Div. 2)

A. Alex and broken contest

题意

输入

输出

样例

题解

过题代码

B. Nikita and string

题意

输入

输出

样例

题解

过题代码

C. Slava and tanks

题意

输入

输出

样例

题解

过题代码

D. Olya and Energy Drinks

题意

输入

输出

样例

题解

过题代码

内容目录