AtCoder Beginner Contest 232（A~D）题解AtCoder Beginner Contest 232题解

62 阅读 0 评论 41 点赞

我是靠谱客的博主聪明萝莉，最近开发中收集的这篇文章主要介绍AtCoder Beginner Contest 232（A~D）题解AtCoder Beginner Contest 232题解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

AtCoder Beginner Contest 232题解

文章目录

AtCoder Beginner Contest 232题解
- A - QQ solver
- B - Caesar Cipher
- C - Graph Isomorphism
- D - Weak Takahashi

A - QQ solver

【题目链接】A - QQ solver (atcoder.jp)

思路：字符串模拟

【代码实现】

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <string.h>
#include <unordered_set>
#include <unordered_map>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;

const int N = 1010, M = 2e5 + 10;



int main() 
{
    string s;
    cin >> s;

    int a = s[0] - '0';
    int b = s[2] - '0';

    cout << a * b << endl;
}

B - Caesar Cipher

【题目链接】B - Caesar Cipher (atcoder.jp)

题意：问串a再每一个字串再变化k次的情况下，最终能否变为b串

思路：计算出变化次数k：k = (s1[0]-s2[0] + 26)%26。遍历字符串，两两做差，若次数不为k即为false

【代码实现】

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <string.h>
#include <unordered_set>
#include <unordered_map>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;


int main() 
{
	string s1, s2;
	cin >> s1 >> s2;

	int k = (s1[0] - s2[0] + 26) % 26;

	bool flag = true;
	for(int i = 0; i < s1.size(); i ++)
	{
		if((s1[i] - s2[i] + 26) % 26 != k)
		{
			flag = false;
			break;
		}
	}
	if(flag) puts("Yes");
	else puts("No");
    return 0;
}

C - Graph Isomorphism

【题目链接】C - Graph Isomorphism (atcoder.jp)

题意：判断两个图是否同构

思路：把点进行映射，如果存在一组映射与原数据不冲突即为答案。寻找可能解时使用了全排列，因为如果有解必然是排列的一种。数据很小暴力dfs即可。
【代码实现】

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <string.h>
#include <unordered_set>
#include <unordered_map>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;

const int N = 9, M = 2e5 + 10;
bool a[N][N], b[N][N], st[N];
int c[N];
int n, m;

// dfs全排列枚举类型
bool dfs(int u)
{
    if(u == n + 1)
    {
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
            {
                if(i != j && a[i][j] != b[c[i]][c[j]])
                    return false;
            }
        return true;    
    }
    for(int i = 1; i <= n; i ++)
    {
        if(!st[i])
        {
            st[i] = true;
            c[u] = i;
            if(dfs(u + 1))// bool类型的！
                return true;
            st[i] = false; 
        }
    }
    return false;
}

int main() 
{
    cin >> n >> m;
    for(int i = 0; i < m; i ++)
    {
        int x, y;
        cin >> x >> y;
        a[x][y] = a[y][x] = true;
    }

    for(int i = 0; i < m; i ++)
    {
        int x, y;
        cin >> x >> y;
        b[x][y] = b[y][x] = true;
    }

    if(dfs(1)) puts("Yes");
    else puts("No");
  

    return 0;  
        
}

D - Weak Takahashi

【题目链接】D - Weak Takahashi (atcoder.jp)

题意：从起点开始，可以向右向下走，问最多可以经过'.'个个数。

思路：

在这里插入图片描述

【代码实现】

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <string.h>
#include <unordered_set>
#include <unordered_map>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;

const int N = 110, M = 2e5 + 10;

int dp[N][N];//到（i,j）'.'的个数为多少：下一个位置是'.'上一个位置的'.'个数加一，'#'跳过即可
char g[N][N];
int n, m;


int main() 
{
    
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> g[i] + 1;//下标从1开始

    dp[1][1] = 1;
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
        if(dp[i][j])
        {
            if(i != n && g[i + 1][j] == '.')
                dp[i + 1][j] = dp[i][j] + 1;
            if(j != m && g[i][j + 1] == '.')
                dp[i][j + 1] = dp[i][j] + 1;
        }

    int res = 0;    
    for(int i = 1; i <= n; i ++)
    {     
        for(int j = 1; j <= m; j ++)
        {
            // cout << dp[i][j] <<  ' ';
            res = max(res, dp[i][j]);
        }
        // cout << endl;
    }    

    cout << res << endl;    

    return 0;  
        
}