B - Caesar Cipher

题意描述

给两个字符串S，T。S能执行若干次下列操作

• S中的每个字符都加一

S能否转换成T？

题解

核心： (s[i] - '0') % 26 + a，这样的题有三个点可以作为偏移量，a / z / s[i]

我是直接暴力映射到52个字母的数字中找对应的char字符。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int main(){
	string s, t;
	cin >> s >> t;
	char tmp[53] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
	for(int i = 1; i <= 26; i++){
		for(int j = 0; j < s.size(); j++){
			s[j] = tmp[(s[j] - 'a' + 1)];
		}

		if(s == t){
			cout << "Yes" << endl;
			return 0;
		}
	}

	cout << "No" << endl;
}

C - Graph Isomorphism

题意描述

给n个点，m条边，判断两个图是否同构

同构的条件

• P是一个（1 - n）的全排列
• 对于第一个人图i，j的点之间有边，同时第二个图p[i]，p[j]之间有也有边

例：

i = 1，j = 2 [1 - 2，3 - 2]

i = 3，j = 4 [3 - 4，1 - 4]

...

题解

核心：暴力搜索所有的全排列的情况判断x[i][j] == y[p[i]][p[j]]

一开始统计两个图的点的入度一一对应，但是wa了一个点，有特殊点过不了。由于n为1 - 8，可以直接暴搜所有全排列的情况。

小知识

next_permutation

1. bool next_permutation(iterator start,iterator end)
2. 当不存在下一个排列时，返回false，否则返回true
3. 基本上用于do-while

do{
    for(auto it : v){
        cout << it << end;
    }
}while(next_permutation(v.begin(), v.end()))

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
	int n, m;
	cin >> n >> m;
    vector<int> p(n);
	
	for(int i = 0; i < n; i++){
		p[i] = i;
	}

	int x[10][10], y[10][10];

	for(int i = 0; i < 10; i++){
		for(int j = 0; j < 10; j++){
			x[i][j] = x[j][i] = 0;
			y[i][j] = y[j][i] = 0;
		}
	}
	
	for(int i = 0; i < m; i++){
		int a, b;
		cin >> a >> b;
		x[a - 1][b - 1] = x[b - 1][a - 1] = 1;
	}

	for(int i = 0; i < m; i++){
		int c, d;
		cin >> c >> d;
		y[c - 1][d - 1] = y[d - 1][c - 1] = 1;
	}

	do{
		int f = 1;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(x[i][j] != y[p[i]][p[j]]){
					f = 0;
				}
			}
		}

		if(f){
			cout << "Yes" << endl;
			return 0;
		}
	}while(next_permutation(p.begin(), p.end()));
	cout << "No" << endl;
}