Problem A. Little Elephant and Interval:
\n\u7edf\u8ba1 [l, r] \u533a\u95f4\u4e2d\uff0c\u9996\u672b\u4f4d\u76f8\u540c\u7684\u6570\u6709\u591a\u5c11\u4e2a\u3002
\n\u7565\u3002([\u6570\u4f4dDP] \u6216\u8005\u76f4\u63a5\u7b97\uff1f\u3002\u3002<\/p>\n
Problem B. Little Elephant and Cards:
\n\u7565\u3002([Map][\u8d2a\u5fc3]..<\/p>\n
Problem C. Little Elephant and Furik and Rubik:
\n\u7565\uff09[\u7b97\u6570]<\/p>\n
Problem D. Little Elephant and Retro Strings:
\n\u7ed9\u4f60\u4e00\u5b57\u7b26\u4e32\uff0cB \u548c W \u8868\u793a\u767d\u8272\u548c\u9ed1\u8272\u3001\u6709 X \u8868\u793a\u989c\u8272\u4e0d\u786e\u5b9a\u3001\u7ed9\u5b9a\u6574\u6570 K\u3002
\n\u95ee\u6709\u591a\u5c11\u79cd\u67d3\u8272\u65b9\u6848\u4f7f\u5f97\u5b58\u5728\u4e24\u7ec4\u4e0d\u60f3\u4ea4\u7684\u957f\u5ea6\u4e3a k \u7684\u5b50\u4e32\uff0c\u6ee1\u8db3\u5de6\u4e32\u5168\u90e8\u662f\u767d\u8272\u3001\u53f3\u4e32\u5168\u90e8\u662f\u9ed1\u8272\u3002
\n..<\/p>\n
Problem E. Little Elephant and Strings:
\n\u7ed9\u5b9a n \u4e2a\u4e32\u7684\u96c6\u5408\uff0c\u518d\u7ed9\u5b9a k\uff0c\u6c42\u6bcf\u4e2a\u4e32\u5206\u522b\u6709\u591a\u5c11\u4e2a\u5b50\u4e32\uff0c\u662f\u96c6\u5408\u4e2d\u81f3\u5c11 k \u4e2a\u4e32\u7684\u5b50\u4e32\u3002
\n…
\n<\/p>\n
Problem A. Little Elephant and Interval:
\n..
\nProblem B. Little Elephant and Cards:
\n..
\nProblem C. Little Elephant and Furik and Rubik:
\n..<\/p>\n
Problem D. Little Elephant and Retro Strings:
\n\u6211\u4eec\u7528 F \u548c G \u5206\u522b\u5904\u7406\u5de6\u4e32\u548c\u53f3\u4e32\u3002\u3002\uff08\u65b9\u5411\u76f8\u53cd
\nF1[i]: \u6070\u597d\u4ee5\u7b2c i \u4f4d\u7ed3\u5c3e\uff0c\u5f62\u6210\u957f\u5ea6\u4e3a k \u7684 {BBBBB..} \u7684\u6570\u76ee\u3002
\nF2[i]: \u6240\u6709\u4ee5 i \u4f4d\u7ed3\u5c3e\uff0c\u957f\u5ea6 >= k\u7684 {BBBBB..} \u4e32\u7684\u6570\u76ee\u3002\u3002
\nG1[i]: \u6070\u597d\u4ee5\u7b2c i \u4f4d\u7ed3\u5c3e\uff0c\u5f62\u6210\u957f\u5ea6\u4e3a k \u7684 {WWWWW..} \u7684\u6570\u76ee\u3002
\nG2[i]: \u6240\u6709\u4ee5 i \u4f4d\u7ed3\u5c3e\uff0c\u957f\u5ea6 >= k\u7684 {WWWWW..} \u4e32\u7684\u6570\u76ee\u3002\u3002<\/p>\n
Problem E. Little Elephant and Strings:
\n… ?<\/p>\n
\r\nconst int N = 1000009;\r\n\r\nint F0[N], F1[N], G0[N], G1[N]; char s[N];\r\nint L[N], R[N], n, k, k_, l, r;\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n#endif\r\n\r\n RD(n, k); RS(s+1); k_ = k + 1;\r\n\r\n\tREP_1(i, n) L[i] = L[i-1] + (s[i]=='X');\r\n\tDWN_1(i, n, 1) R[i] = R[i+1] + (s[i]=='X');\r\n\r\n l = 0, r = 0; REP_1(i, n){\r\n if (s[i] == 'X' || s[i] == 'B') ++r; else l = r = i;\r\n F1[i] = sum(pdt(s[i] == 'X' ? 2 : 1, F1[i-1]), F0[i] = r-l>=k && s[i-k] != 'B' ? dff(pow(2, L[i-k_]), F1[i-k_]) : 0);\r\n }\r\n\r\n l = n+1, r = n+1; DWN_1(i, n, 1){\r\n if (s[i] == 'X' || s[i] == 'W') --l; else r = l = i;\r\n G1[i] = sum(pdt(s[i] == 'X' ? 2 : 1, G1[i+1]), G0[i] = r-l>=k && s[i+k] != 'W' ? dff(pow(2, R[i+k_]), G1[i+k_]) : 0);\r\n }\r\n\r\n int res = 0; FOR(i, 1, n) INC(res, pdt(F0[i], G1[i+1]));\r\n OT(res);\r\n}\r\n<\/pre>\n\r\n...\r\n<\/pre>\n…<\/p>\n
External link: <\/h3>\n