网站建设的关键技术,优质的设计网站有哪些,wordpress主题时尚科技,网站头图设计文章目录 [ Unforgivable Curse (hard version)](https://codeforces.com/contest/1800/problem/E2)问题建模问题分析方法1分析性质1.分析操作对元素位置的影响2.分析可以使用操作的元素可以与相邻元素交换位置的作用代码 方法2通过DFS得到相互可以交换位置的字符集合代码 方法… 文章目录 [ Unforgivable Curse (hard version)](https://codeforces.com/contest/1800/problem/E2)问题建模问题分析方法1分析性质1.分析操作对元素位置的影响2.分析可以使用操作的元素可以与相邻元素交换位置的作用代码 方法2通过DFS得到相互可以交换位置的字符集合代码 方法3通过并查集连通可交换位置代码 Unforgivable Curse (hard version) 问题建模
给定两个字符串s和t每次能让一个字符与其相差k或k1个距离的字符进行交换问能否让字符串s通过若干次该操作使其变为字符串t
问题分析
方法1分析性质
1.分析操作对元素位置的影响
使用一次该操作可以让当前元素与另一个元素交换位置再用一次则可以将该元素放到与之相邻的位置再一次则可以让相邻两个元素完成交换且不影响其余元素。 2.分析可以使用操作的元素可以与相邻元素交换位置的作用
对于可以使用该操作的元素其可以与相邻元素交换位置则所有可以使用该操作的元素之间可以通过连续使用该操作从而可以任意交换顺序则对于这些位置的元素只需检查两个字符串字符是否对应都有即可。而不能使用该操作的元素则需要单独比较是否对应相等
代码
#includebits/stdc.h#define x first
#define y second
#define C(i) str[0][i]!str[1][i]
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pairint, int PII;
typedef pairLL, LL PLL;
const int N 210, Mod 998244353, P 2048;void solve() {int n,k;cin n k;string s,t;cin s t;vectorint cnt(26,0);bool oktrue;for(int i0;in;i){if(ik||ikn){cnt[s[i]-a],cnt[t[i]-a]--;}else {ok(s[i]t[i]);}}if(okcount(cnt.begin(),cnt.end(),0)26) puts(YES);else puts(NO);
}int main() {int t 1;cin t;while (t--) solve();return 0;
}方法2通过DFS得到相互可以交换位置的字符集合
每个位置一次操作可以到达的点为一个可以相互交换的集合可以先通过DFS得到每个点所属集合。然后将两个字符串中对应位置的字符存入所在集合里排序后形成形式同一的字符串进行比较。
代码
#includebits/stdc.h#define x first
#define y second
#define C(i) str[0][i]!str[1][i]
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pairint, int PII;
typedef pairLL, LL PLL;
const int N 2e510, Mod 998244353, P 2048;
int n,k;
int a[N];
vectorchar g[N];
int idx;
void dfs(int u,int idx){if(u0||un||a[u]) return ;a[u]idx;///记录u点所在集合编号dfs(uk,idx),dfs(uk1,idx),dfs(u-k,idx),dfs(u-k-1,idx);
}string make(string str){for(int i1;iidx;i){g[i].clear();}for(int i0;in;i){///将各点字符存入所属集合内g[a[i]].push_back(str[i]);}for(int i1;iidx;i){///将各个集合内的字符排序sort(g[i].begin(),g[i].end());}string ans;///将各个集合内的元素弄成形式统一的字符串用于比较for(int i0;in;i){ansg[a[i]].back();g[a[i]].pop_back();}return ans;
}void solve() {cin n k;string s,t;cin s t;idx0;memset(a,0,sizeof(int)*(n1));for(int i0;in;i){if(!a[i]){dfs(i,idx);} } if(make(s)make(t)) puts(YES);else puts(NO);
}int main() {int t 1;cin t;while (t--) solve();return 0;
}方法3通过并查集连通可交换位置
先通过并查集将每个位置可到达的位置连通然后将连通的字符进行记录最后比较两个字符串每个连通集内的字符。
代码
#includebits/stdc.h#define x first
#define y second
#define C(i) str[0][i]!str[1][i]
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pairint, int PII;
typedef pairLL, LL PLL;
const int N 2e510, Mod 998244353, P 2048;
int n,k;
int a[N];
int cnt[N][26];
int p[N];
int find(int x){if(x!p[x]) p[x]find(p[x]);return p[x];
}void solve() {cin n k;string s,t;cin s t;for(int i0;in;i) p[i]i;for(int i0;in;i) memset(cnt[i],0,sizeof(int)*(26));///将可以相互到达的位置连通for(int i0;in;i){if(ikn){int fafind(i),fbfind(ik);if(fa!fb){p[fa]fb;}}if(ik1n){int fafind(i),fbfind(ik1);if(fa!fb){p[fa]fb;}} } for(int i0;in;i){///将该位置字符记录在对应连通块内cnt[find(i)][s[i]-a];cnt[find(i)][t[i]-a]--;} for(int i0;in;i){if(find(i)i){///检查该连通块内字符是否相等for(int j0;j26;j){if(cnt[i][j]!0){puts(NO);return ;}}}}puts(YES);
}int main() {int t 1;cin t;while (t--) solve();return 0;
}
