CodeforcesRound#296(Div.2)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了CodeforcesRound#296(Div.2),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1667字,纯文字阅读大概需要3分钟。
内容图文
题目: 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#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 <= 25; ++i) { for(int j = 0; j <= 25; ++j) { if(f[i][j] && f[j][i]) { ans -= 2; for(int k = 0; k < n; ++k) { if(!ok1 && s[k]-'a' == i && t[k]-'a' == j) { a = k+1; ok1 = 1; } if(!ok2 && s[k]-'a' == j && t[k]-'a' == i) { b = k+1; ok2 = 1; } if(ok1 && ok2) { printf("%d\n%d %d\n", ans, a, b); return; } } } } } for(int i = 0; i < n; ++i) { if(s[i] != t[i]) { if(v[t[i]-'a'].size() == 0) continue; ans--; a = i+1; b = v[t[i]-'a'][0]+1; printf("%d\n%d %d\n", ans, a, b); return; } } printf("%d\n%d %d\n", ans, a, b); return; } int main() { //freopen("in", "r", stdin); while(~scanf("%d", &n)) { memset(f, 0, sizeof(f)); scanf("%s%s", s, t); ans = 0; for(int i = 0; i < n; ++i) { if(s[i] != t[i]) { ans++; f[s[i]-'a'][t[i]-'a'] = 1; v[s[i]-'a'].push_back(i); } } solve(); } return 0; }
内容总结
以上是互联网集市为您收集整理的CodeforcesRound#296(Div.2)全部内容,希望文章能够帮你解决CodeforcesRound#296(Div.2)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。