AtCoder Beginner Contest 278「A」「B」「C」「D」「E」「F 对抗博弈」

AtCoder Beginner Contest 278

A - Shift

题目描述：

给你n个数字，进行k轮左移操作，左移即将最左边的元素被删掉，并在最右边加一个0

输出最后的结果

#include
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define m_p(a, b) make_pair(a, b)
#define mod9 998244353
#define mod7 1000000007
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair<int, int>pii;

#define MAX 300050
int n, m, k, x;
int tr[MAX];

void work()
{
    cin >>n >>k;
    for(int i=  1; i <= n; ++i)cin >>tr[i];
    for(int i = k +1; i <= n; ++i)cout <<tr[i] << ' ';
    for(int i = 1; i <= min(k, n); ++i)cout << 0 << ' ';
    cout << endl;
}

int main()
{
    io;
    work();
    return 0;
}

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

B - Misjudge the Time

题目描述：

给你一个24小时制的时间，表示为AB:CD，如果一个时间满足AC:BD也是合法时间，则这个时间是好时间

现在给你一个时间点，问从这个点(包括这个点)开始的下一个好时间是什么时候

#include
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define m_p(a, b) make_pair(a, b)
#define mod9 998244353
#define mod7 1000000007
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair<int, int>pii;

#define MAX 300050
int n, m, k, x;
int tr[MAX];

bool judge(int x, int y)
{
    if(x >= 0 && x < 24 && y >= 0 &&y<60)return true;
    else return false ;
}

void work()
{
    cin >>n >>k;
    int x, y = k;
    for(int i = n; i <= 23; ++i)
    {
        int a = i / 10, b = i % 10;
        for(int j = y; y <= 59; ++y)
        {
            int c = j / 10,d = j % 10;
            if(judge(a*10+c, b*10+d))
            {
                cout << i <<' ' <<j << endl;
                return;
            }
        }
        y = 0;
    }
    cout << 0 << ' ' << 0 << endl;
}

int main()
{
    io;
    work();
    return 0;
}

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

C - FF

题目描述：

三种操作

• 1 a b，如果a没有指向b的边，则给a和b连一条有向边
• 2 a b，如果a存在指向b的边，则去掉这条有向边
• 3 a b，问a到b是否有一条有向边，有就输出Yes，没有就输出No

思路：

用map, bool>进行暴力就行

#include
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define m_p(a, b) make_pair(a, b)
#define mod9 998244353
#define mod7 1000000007
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair<int, int>pii;

#define MAX 300050
int n, m, k, x;
int tr[MAX];
int op, a, b;

void work()
{
    cin >>n >>m;
    map<pii, bool>mp;
    for(int i = 1; i <= m; ++i)
    {
        cin >> op >> a >>b;
        if(op == 1)mp[m_p(a, b)] = 1;
        else if(op == 2)
        {
            if(mp.count(m_p(a, b)) == 1)mp[m_p(a, b)] = 0;
        }
        else
        {
            if(mp[m_p(a, b)] == 1 && mp[m_p(b, a)] == 1)cout <<"Yes\n";
            else cout <<"No\n";
        }
    }
}

int main()
{
    io;
    work();
    return 0;
}

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

D - All Assign Point Add

题目描述：

长度为n的数组，进行q次操作

• 1 x，把数组所有元素都变成x
• 2 i x，给a[i]+=x
• 3 i，输出a[i]

#include
using namespace std;
#define int long long
#define endl '\n'
#define inf 0x3f3f3f3f
#define m_p(a, b) make_pair(a, b)
#define mod9 998244353
#define mod7 1000000007
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair<int, int>pii;

#define MAX 300050
int n, m, k, x;
int op, a, b;
int tr[MAX];
bool vis[MAX];
void work()
{
    vector<int>v;
    cin >>n;
    for(int i = 1; i <= n; ++i)
    {
        cin >>tr[i];
        vis[i] = 1;
        v.push_back(i);

    }
    cin >> m;

    x = 0;
    for(int i=  1; i <= m; ++i)
    {
        cin >>op;
        if(op == 1)
        {
            cin >> a;
            for(auto u :v)vis[u] = 0;
            v.clear();
            x = a;
        }
        else if(op == 2)
        {
            cin >> a >> b;
            if(vis[a])tr[a] += b;
            else
            {
                vis[a] = 1;
                v.push_back(a);
                tr[a] = x + b;
            }
        }
        else
        {
            cin >> a;
            if(vis[a])cout << tr[a] << endl;
            else cout << x << endl;
        }
    }

}

signed main()
{
    io;
    work();
    return 0;
}

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

E - Grid Filling

题目描述：

给定一个 H∗W 的矩阵，矩阵上每个元素的数值在 1∼N 之间。给定 h,w ，对于所有的 (k,l) ， 0≤k≤H−h,0≤l≤W−w ，都要输出：

如果把以 (k,l) 为左上角，长为 h ，宽为 w 的长方形盖住，矩阵上一共能剩下多少种数字。

$1\le H,W,N\le 300,1\le h\le H,1\le w\le W$

思路：

暴力就可以

对于每一层，先暴力扣掉整个矩阵的影响，然后开始向右移动，每次移动的时候只需要加回左边那列，扣掉右边那列的影响就可以了

#include
using namespace std;
#define int long long
#define endl '\n'
#define inf 0x3f3f3f3f
#define m_p(a, b) make_pair(a, b)
#define mod9 998244353
#define mod7 1000000007
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair<int, int>pii;

#define MAX 300050
int n, m, k, p, q, x, y;
int op, a, b;
int tr[305][305];
void work()
{
    cin >>n >> m >> k >> p >>q;
    map<int, int>mp;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {

            cin >>tr[i][j];
            ++mp[tr[i][j]];
        }
    }
    for(int i = 1; i + p - 1 <= n; ++i)
    {
        map<int, int>mpp;mpp = mp;
        for(int x = i; x <= i + p - 1; ++ x)
        {
            for(int y = 1; y <= q; ++y)
            {
                --mpp[tr[x][y]];
                if(mpp[tr[x][y]] == 0)mpp.erase(tr[x][y]);
            }
        }
        cout << mpp.size();
        for(int j = 2; j + q - 1 <= m; ++j)
        {
            for(int x = i; x <= i +p - 1; ++x)
            {
                ++mpp[tr[x][j-1]];
                --mpp[tr[x][j+q-1]];
                if(mpp[tr[x][j+q-1]] == 0)mpp.erase(tr[x][j+q-1]);
            }
            cout << ' ' << mpp.size();
        }
        cout << endl;
    }

}

signed main()
{
    io;
    work();
    return 0;
}

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

F - Shiritori

题目描述：

给定n个字符串，进行博弈

除了第一次可以随便取字符串以外，其他每次都只能取以上一次取的字符串最后一个字符为开头的字符串

问谁先不能取就输了

思路：

第一次赛时成功出了F题，还是很开心的

这个题看起来像一种对抗博弈的经典问题，我们可以直接暴力去dfs

首先先建个图

我们定义dfs(x)表示上一个人选择了s[x]串时，现在先手的状态，如果先手必胜就返回true,先手必输就返回false

显然当前的状态可以由后面的状态推过来，如果以x后继节点中存在先手必输的状态，那当前这个点可以通过走那个点使得后手必输，则达到先手必赢的状态，所以返回true；反之，如果后继节点都是先手必胜的状态，则这个点无论怎么都都会面对后手必胜，则自己就是先手必输，也就返回flase

由于第一个字符串可以随便选，所以我们可以以每个串为起点去搜

#include
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define m_p(a, b) make_pair(a, b)
#define mod9 998244353
#define mod7 1000000007
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair<int, int>pii;

#define MAX 300050
int n, m, k, p, q, x, y;
int op, a, b;
vector<int>G[30];
string s[20];
bool vis[MAX];
bool dfs(int u)
{
    for(auto v : G[s[u].back() - 'a'+1])
    {
        if(vis[v])continue;
        vis[v] = 1;
        if(dfs(v) == 0){
            vis[v] = 0;
            return 1;
        }
        vis[v] = 0;
    }
    return 0;
}

void work()
{
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        cin >>s[i];
        G[s[i][0]-'a'+1].push_back(i);
    }
    for(int i = 1; i <= n; ++i)
    {
        vis[i] = 1;
        if(dfs(i) == 0)
        {
            cout <<"First\n";
            return;
        }
        vis[i] = 0;
    }
    cout <<"Second\n";
}

int main()
{
    io;
    work();
    return 0;
}

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