2017-2018 ACM-ICPC, Asia Daejeon Regional Contest H - Rock Paper Scissors【FFT】

题意：给你两个字符串，由RSP组成，分别代表石头剪刀布，你可以改变你开始出拳的时间（但不能小于0），求最多能赢几次。

分析：对手是s串，自己是t串，即把t串中的R换成S，S换成P，P换成R，然后在S中找一个子串匹配个数最多。

固定s不动，移动t，令，我们把RSP分开算3次，以R为例，s[i]=1表示这个位置是R，反之不是，t同理。然后把RSP三种情况对应求和，然后再求个最大值就可以了，问题在于如何求X(n)。

其实只需要把t数组翻转一下，就变成了，然后就可以了直接求卷积了，总共9次FFT就可以得到答案，最后去一个max就可以了。

#includeusing namespace std;
const double pi = acos(-1.0);
char s[100004], t[100004];struct Complex {double x, y;Complex(double _x = 0.0, double _y = 0.0) {x = _x;y = _y;}Complex operator-(const Complex &b) const {return Complex(x - b.x, y - b.y);}Complex operator+(const Complex &b) const {return Complex(x + b.x, y + b.y);}Complex operator*(const Complex &b) const {return Complex(x * b.x - y * b.y, x * b.y + y * b.x);}
};Complex s1[800004], s2[800004], p1[800004], p2[800004], r1[800004], r2[800004];void change(Complex y[], int len) {int i, j, k;for (i = 1, j = len / 2; i < len - 1; i++) {if (i < j) swap(y[i], y[j]);k = len / 2;while (j >= k) {j -= k;k /= 2;}if (j < k) j += k;}
}void fft(Complex y[], int len, int on) {change(y, len);for (int h = 2; h <= len; h <<= 1) {Complex wn(cos(-on * 2 * pi / h), sin(-on * 2 * pi / h));for (int j = 0; j < len; j += h) {Complex w(1, 0);for (int k = j; k < j + h / 2; k++) {Complex u = y[k];Complex t = w * y[k + h / 2];y[k] = u + t;y[k + h / 2] = u - t;w = w * wn;}}}if (on == -1) {for (int i = 0; i < len; i++) y[i].x /= len;}
}int main() {int n, m;scanf("%d%d", &n, &m);scanf("%s%s", s, t);for (int i = 0; i < m; i++) {if (t[i] == 'R')t[i] = 'S';else if (t[i] == 'S')t[i] = 'P';else t[i] = 'R';if (t[i] == 'R')r2[m - i - 1].x = 1;else if (t[i] == 'S')s2[m - i - 1].x = 1;else p2[m - i - 1].x = 1;}for (int i = 0; i < n; i++) {if (s[i] == 'R')r1[i].x = 1;else if (s[i] == 'S')s1[i].x = 1;else p1[i].x = 1;}int len = 1;while (len < 2 * (n + m)) len <<= 1;fft(s1, len, 1);fft(s2, len, 1);fft(p1, len, 1);fft(p2, len, 1);fft(r1, len, 1);fft(r2, len, 1);for (int i = 0; i < len; ++i) {s1[i] = s1[i] * s2[i];p1[i] = p1[i] * p2[i];r1[i] = r1[i] * r2[i];}fft(s1, len, -1);fft(p1, len, -1);fft(r1, len, -1);long long ans = 0;for (int i = m - 1; i < n + m + 1; i++) {ans = max(ans, (long long) (s1[i].x + 0.5) + (long long) (p1[i].x + 0.5) + (long long) (r1[i].x + 0.5));}cout << ans << endl;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！