E. 2-Letter Strings
发布时间
阅读量：
阅读量
https://codeforces.com/contest/1669/problem/E
我的做法是考虑所有可能的集合情况吗？
虽然我的队友选择将问题转化为图论模型，并使用入度来解决这个问题（雾
input
4
6
ab
cb
db
aa
cc
ef
7
aa
bb
cc
ac
ca
bb
aa
4
kk
kk
ab
ab
5
jf
jf
jk
jk
jk
AI写代码output
5
6
0
6
AI写代码
具体要求
给定n个长度为2且仅由小写字母a至k组成的所有字符串，请计算其中有多少对这样的字符串在其串上存在两个位置：一个位置的字符相同而另一个位置的字符不同。（注释内容可忽略）
思路
为了实现某字符在不同位置的一致性需求, 我打算从前到后依次检查每个字符. 这种方法能够帮助我们高效地确定字符匹配的情况. 比如:
观察样例 1 的情况时, 在第 1 位进行分析.
- 对于左边：
发现只有一个 aa 的字符串与之配对，即贡献答案 1
- 对于右边
可以发现在这之后有两个 b 出现，可以贡献答案 2
因此我们可以通过 左右两边 每个字母上 计算其前缀和 我们定义了一个数组： pre[i][j][k] 其中i表示对应字母在字符集中的索引（例如a=0, b=1, \dots) j用于区分左右两侧的情况 而k则表示字符串中各个位置上的累积值
但发现这一点有些令人困惑。假设我们将样例中的 aa 替换成 ab，
这意味着该串在左右两边被重复计算了两次。
然而必须明确的是，
我们的目标是找到恰好在一个位置上相同、另一个位置上不同的情况，
因此相同的字符串不会对结果产生影响
我们需要找到一个办法来解决这个问题。
我们使用 map 来映射每种字符串的出现频率，并构建前缀和的形式；这样就能迅速确定在后续位置上与当前字符串相同的数量。
每当处理完某个位置后，在处理下一个位置时需要清空该位置对应的映射信息。
AC代码
（一开始没有看题目是仅 a-k，所以我才遍历26个全部小写字母）
#include <bits/stdc++.h>
#include <utility>
#define endl '\n'
#define AC return 0;
using namespace std;
//#define ll long long
#define int long long
int pre[27][2][100005];
map<string,int>p;
string e[100005];
void slove()
{
int n;
cin >> n;
p.clear();
for(int i = 1; i <= n; i++)
{
cin >> e[i];
p[e[i]]++;
for(int j = 0; j < 26; j++)
pre[j][0][i] = pre[j][1][i] = 0;
}
for(int i = 1; i <= n; i++)
{
pre[e[i][0] - 'a'][0][i]++;
pre[e[i][1] - 'a'][1][i]++;
for(int j = 0; j < 26; j++)
{
pre[j][0][i] += pre[j][0][i - 1];
pre[j][1][i] += pre[j][1][i - 1];
}
}
int ans = 0;
for(int i = 1; i < n; i++)
{
int a = e[i][0] - 'a';
int b = e[i][1] - 'a';
ans += pre[a][0][n] - pre[a][0][i];
ans += pre[b][1][n] - pre[b][1][i];
ans -= (p[e[i]] - 1) * 2;
p[e[i]]--;
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T;cin >> T; while(T--)
slove();
AC
}
AI写代码全部评论 (0)
还没有任何评论哟~