Blackops

初心易得，始终难守

0%

CF #459 Div.2 A B C D

发表于 分类于 ，

A.Eleven

题意就是输出长度为$n$的仅含$O$或$o$的字符串，打表标记一下斐波那契的项再输出就好

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1200;
int F[N] = {0, 1, 1};
int vis[N];

int main(void)
{
    vis[1] = 1;
    for (int i = 3; i < N; ++i)
    {
        F[i] = F[i - 1] + F[i - 2];
        vis[F[i]] = 1;
        if (F[i] > 1000)
            break;
    }
    int n;
    while (cin >> n)
    {
        for (int i = 1; i <= n; ++i)
            if (vis[i])
                cout << 'O';
            else
                cout << 'o';
        cout << endl;
    }
    return 0;
}

B.Radio Station

题意就是给你$n$个主机名字和其对应$ip$地址，再输入$m$个包含给定了$ip$地址的操作，输出同样的操作和其对应的主机名。
用$map$将$ip$地址作为$key$搞搞就行

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1010;
char s[N];

struct info
{
    int a, b, c, d;
    bool operator<(const info &rhs)const {
        if (a != rhs.a)
            return a < rhs.a;
        if (b != rhs.b)
            return b < rhs.b;
        if (c != rhs.c)
            return c < rhs.c;
        return d < rhs.d;
    }
};
map<info, string>st;

int main(void)
{
    int n, m, i, a, b, c, d;
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; ++i)
    {
        scanf("%s %d.%d.%d.%d", s, &a, &b, &c, &d);
        st[ {a, b, c, d}] = string(s);
    }
    while (m--)
    {
        scanf("%s %d.%d.%d.%d;", s, &a, &b, &c, &d);
        printf("%s %d.%d.%d.%d; #%s\n", s, a, b, c, d, st[ {a, b, c, d}].c_str());
    }
    return 0;
}

C.The Monster

题意就是给你一串含有$?$的括号序列，问号可以用$($或者$)$代替，求所有代替之后可以形成合法括号序列的子串个数。
如果把$($记作$1$，把$)$记作$-1$，做一次括号序列的前缀和，对于一个合法的括号序列其前缀和的最后一位必须为$0$且过程中不能出现负数
但是这里有问号怎么处理呢，可以把问号看作是可以随时使用的一个东西，如果当前的前缀和非负且前缀和小于问号数量，说明$($比较多，应该用问号抵消一部分，如果最后剩余未用问号数量和多余的左括号一样多的话，那两者可以互相抵消，可以构成一个合法的括号序列。

比赛的时候WA了好几发没搞出来，看了别人代码发现是自己想复杂了……

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 5010;
char s[N];

int main(void)
{
    register int i, j;
    while (~scanf("%s", s))
    {
        int len = strlen(s);
        int ans = 0;
        for (i = 0; i < len; ++i)
        {
            int pres = 0, wen = 0;
            if (s[i] == ')')
                continue;
            for (j = i; j < len; ++j)
            {
                if (s[j] == '(')
                    ++pres;
                else if (s[j] == ')')
                    --pres;
                else
                    ++wen;
                if (pres < 0)
                    break;
                if (wen > pres)
                {
                    --wen;
                    ++pres;
                }
                if (wen == pres)
                    ++ans;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

D.MADMAX

题意就是给你一个有向无环图($DAG$)，规则只能走边权不降的边，最后不能走的人输，Max先手，Lucas后手，求当Max在$i$点，Lucas在$j$点，两人均取最优策略时谁胜谁负。输出所有情况下的胜负对应字母（$A$代表Max赢，$B$代表Lucas赢）

以为是个贪心+模拟BFS题，实际上是个博弈$DP$，用$dp[i][j][v]$表示当前先手在点$i$，后手在点$j$，最后一次边权值为$v$，$i$是否能获胜。
那么转移方程应该是：

方程意思应该是只要存在当$j$先手时无法取胜，那么$i$先手时就可以按照这个情况取胜，用记忆化搜索加一点剪枝就好。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 110;
const int M = N * N;
struct edge
{
    int to, nxt;
    int c;
    edge() {}
    edge(int _to, int _nxt, int _c): to(_to), nxt(_nxt), c(_c) {}
} E[M];
int head[N], tot;
int dp[130][N][N];

void init()
{
    CLR(head, -1);
    tot = 0;
}
inline void add(int s, int t, int c)
{
    E[tot] = edge(t, head[s], c);
    head[s] = tot++;
}
int dfs(int level, int fi, int se)
{
    if (~dp[level][fi][se])
        return dp[level][fi][se];
    for (int i = head[fi]; ~i; i = E[i].nxt)
    {
        int v = E[i].to;
        if (E[i].c >= level)
        {
            if (!dfs(E[i].c, se, v))//出现另一方先手无法取胜的情况
                return dp[level][fi][se] = 1;//当前方先手就有机会取胜
        }
    }
    return dp[level][fi][se] = 0;
}
int main(void)
{
    register int n, m, a, b, i, j;
    char c[5];
    while (~scanf("%d%d", &n, &m))
    {
        init();
        CLR(dp, -1);
        for (i = 1; i <= m; ++i)
        {
            scanf("%d%d%s", &a, &b, c);
            add(a, b, (int)c[0]);
        }
        for (i = 1; i <= n; ++i)
        {
            for (j = 1; j <= n; ++j)
            {
                if (dfs(0, i, j))
                    putchar('A');
                else
                    putchar('B');
            }
            puts("");
        }
    }
    return 0;
}