집 >데이터 베이스 >MySQL 튜토리얼 >Codeforces Round #296 (Div. 2)
题目: http://codeforces.com/contest/527/problem/B 题意: 给出两串n( 1?≤? n ?≤?200?000 )个字母的字符串, 求出最多交换一对数, 使得不相同对数变少,求出不相同的对数以及交换的数的位置,若不需交换则输出-1,-1. 思路: 用矩阵记录两个串相同位置不同的字
题目:
http://codeforces.com/contest/527/problem/B
题意:
给出两串n(1?≤?n?≤?200?000)个字母的字符串, 求出最多交换一对数, 使得不相同对数变少,求出不相同的对数以及交换的数的位置,若不需交换则输出-1,-1.
思路:
用矩阵记录两个串相同位置不同的字母, 并记录每一个出现的字母的位置. 计算不相同的对数ans.
先枚举一遍字符串, 若f[i][j] == f[j][i] == 1, 则ans -= 2;
否则不相同的字母对中t字母中s串存在, 则交换,且ans--.
AC.
#include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <cstring> using namespace std; const int maxn = 200005; char s[maxn], t[maxn]; bool f[30][30]; vector<int> v[30]; int n, ans; void solve() { int a = -1, b = -1; bool ok1 = 0, ok2 = 0; for(int i = 0; i <br> <br> </int></cstring></algorithm></vector></cstdio></iostream>