CodeforcesRound#296(Div.2)

题目: http://codeforces测试数据/contest/527/problem/B 题意: 给出两串n( 1?≤? n ?≤?200?000 )个字母的字符串, 求出最多交换一对数, 使得不相同对数变少,求出不相同的对数以及交换的数的位置,若不需交换则 输出-1,-1. 思路: 用矩阵记录两个串相同位置不同的字

题目:

http://codeforces测试数据/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  
#include  
#include  
#include 
#include  

using namespace std;
const int maxn = 200005;
char s[maxn], t[maxn];
bool f[30][30];
vector  v[30];
int n, ans;

void solve()
{
    int a = -1, b = -1;
    bool ok1 = 0, ok2 = 0;
    for(int i = 0; i  

查看更多关于CodeforcesRound#296(Div.2)的详细内容...