Atcoder ABC232 B/C

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]之间有也有边

例:

Atcoder ABC232 B/C

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;
}
上一篇:天猫浏览型应用的CDN静态化架构演变


下一篇:dp算法.