{"id":437,"date":"2018-08-16T15:47:13","date_gmt":"2018-08-16T15:47:13","guid":{"rendered":"https:\/\/www.haoyuan.info\/?p=437"},"modified":"2018-08-16T15:47:13","modified_gmt":"2018-08-16T15:47:13","slug":"cup-4367-tyvj1952-easy-bzoj","status":"publish","type":"post","link":"https:\/\/haoyuan.info\/?p=437","title":{"rendered":"CUP 4367: Tyvj1952 Easy BZOJ"},"content":{"rendered":"

\u9898\u89e3<\/h2>\n

\u7531\u4e8e\u7ed9\u5b9a\u5e8f\u5217\uff0c$o$\u7684\u6982\u7387\u4e00\u5b9a\u662f1\uff0c$x$\u7684\u6982\u7387\u4e00\u5b9a\u662f0.
\n$?$\u7684\u671f\u671b\u5b9e\u9645\u4e0a\u662f0.5
\n\u6211\u4eec\u8981\u6c42\u7684\u662f$E_{x^2}$,\u4ee4$dp_i$\u4ee3\u8868\u5230\u7b2ci\u4f4d\u65f6$E_{x^2i}$\uff0c$l_i$\u4e3a\u5230\u8fbe$i$\u4f4d\u7f6e\u65f6\u7684\u671f\u671b\u957f\u5ea6\u3002\u6839\u636e\u4e0a\u8ff0\u6761\u4ef6\uff0c$o$\u65f6$l_i = l_{i-1} + 1$,$x$\u65f6$l_i = 0$,\u800c$x$\u7684\u65f6\u5019$l_i = 0.5 \\times (l_{i-1} + 1)$<\/p>\n

\u6839\u636e$l$\uff0c\u89c2\u5bdf$E_i – E_{i-1}$,\u53ef\u4ee5\u53d1\u73b0$x^2 – (x – 1)^2 = 2x + 1$
\n\u56e0\u6b64$dp_i = dp_{i – 1} + 2 \\times l_{i – 1} + 1$
\n$dp_n$\u4e3a\u7b54\u6848<\/p>\n

AC\u4ee3\u7801<\/h2>\n
#include <iostream>\n#include <iomanip>\nusing namespace std;\nconst int maxn = 3e5+6;\nlong double dp[maxn],l[maxn];\nint main()\n{\n    int n;\n    string s;\n    cin >> n >> s;\n    s = \" \" + s;\n    for(int i = 1;i<=n;++i)\n    {\n        if(s[i] == 'o') {\n            dp[i] = dp[i - 1] + l[i - 1] * 2 + 1;\n            l[i] = l[i - 1] + 1;\n        }\n        else if(s[i] == 'x') {\n            dp[i] = dp[i - 1];\n            l[i] = 0;\n        }\n        else {\n            dp[i] = dp[i - 1] + l[i - 1] + 0.5;\n            l[i] = l[i - 1] \/ 2 + 0.5;\n        }\n    }\n    cout << setiosflags(ios::fixed) << setprecision(4);\n    cout << dp[n] << '\\n';\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u89e3 \u7531\u4e8e\u7ed9\u5b9a\u5e8f\u5217\uff0c$o$\u7684\u6982\u7387\u4e00\u5b9a\u662f1\uff0c$x$\u7684\u6982\u7387\u4e00\u5b9a\u662f0. $?$\u7684\u671f\u671b\u5b9e\u9645\u4e0a\u662f0.5 \u6211\u4eec\u8981\u6c42\u7684\u662f$E […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","footnotes":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false},"categories":[39,59,25,60,22],"tags":[24,61],"class_list":["post-437","post","type-post","status-publish","format-standard","hentry","category-c","category-59","category-25","category-dp","category-22","tag-cpp","tag-61"],"jetpack_featured_media_url":"","jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p8UC2c-73","jetpack_likes_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/437","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=437"}],"version-history":[{"count":0,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/437\/revisions"}],"wp:attachment":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=437"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=437"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=437"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}