T1:

A了

T2:

我原本想的是直接模拟，用一个指针记录现在要配对的t的字符，如果发现s的第一个字符就是错的，那直接就直接输出No，如果发现两个字符不一样,那么就有两种情况:一个是配对到的t的字符是t中第一个字符那么可能是前面有个字符串压住了这个字符串的头那么只需要找到这一个字符能配对的那个字符来配对(很明显，这是错的)如果找到，最后发现没有相同的,那么就输出No,然后就是配对到的字符不是t中第一个字符那么可能是这个字符串压到了别的字符串的头,要判断一下是不是这种情况,如果是的话指针就移回第一个字符,如果发现不一样,那就不可能了,要输出No。如果两个字符全一样,指针往后偏移一位就行了。
实际上可以用贪心或dp，我觉得dp简单一些，所以写的是dp， $dp_{ij}$ 代表s前i位匹配且当前s[i]匹配t[j]，初始第零位匹配，然后就是枚举s和t的匹配情况
每次的dp有两种情况：
1. s[i]==t[j]：有两种情况，一个是s[i-1]和t[j]相同,一个是s[i-1]和t[m]相同,其他的情况是不可能的,比如样例二ABBCABC是不能完成的
2. s[i]==t[1]：有一种情况，因为第一个字符前可以是t中的任何字符，所以s[i-1]可以直接配对t[j]，因为我们需要枚举，就不用多枚举了

T3:

原本想的是打暴力，用vector数组存每个桶里的球，但不去重，每次清空一个标记数组f，遍历b的vector，然后算出有多少种球。
实际上是用一个map数组来存每个球，这样就可以不用手动去重，但是这样也会超时，我们就可以用启发式合并来合并map，这样就不会超时，也就是小集合合并到大集合里，那所以如果a的map存的数(mp[a].size())少一些，那么就把a合到b，如果b的map存的数(mp[b].size())少一些，那么就把b合到a，然后再交换两个map就行了

总结5.8

文章操作

T1:

T2:

T3:

相关推荐

评论

总结5.8