https:\/\/codeforces.com\/contest\/2037<\/a><\/p>\n\n\n\nE. Kachina's Favorite Binary String<\/h2>\n\n\n\n
\u901a\u8fc7\u4e0d\u65ad\u8be2\u95ee$k_i=f(1,i),i=1,2,...,n$\uff0c\u5982\u679cki>ki-1\uff0c\u5219\u8868\u793a\u6539\u4f4d\u7f6e\u4e3a1\uff0c\u4f1a\u4ea7\u751f\u65b0\u7684\u6ee1\u8db3\u6761\u4ef6\u7684\u5b50\u4e32\uff1b\u5982\u679c$k_i=k_{i-1}$\uff0c\u5219\u8868\u793a\u5f53\u524d\u4f4d\u7f6e\u662f0\uff0c\u4e0d\u4f1a\u4ea7\u751f\u65b0\u7684\u6ee1\u8db3\u6761\u4ef6\u7684\u5b50\u4e32\u3002\u5728\u5b57\u7b26\u4e32\u6700\u5f00\u59cb\u7684\u4f4d\u7f6e\u5982\u679c\u4e3a1\u7684\u8bdd\uff0c\u4e5f\u4e0d\u4f1a\u4ea7\u751f\u65b0\u7684\u5b50\u4e32\uff0c\u6240\u4ee5\u901a\u8fc7\u627e\u5230\u7b2c\u4e00\u4e2a\u4e0d\u4e3a\u96f6\u7684$k_i$\uff0c\u5176\u503c\u4e3a\u591a\u5c11\u5c31\u8868\u793a\u5728\u8fd9\u4e2a1\u524d\u6709\u591a\u5c11\u4e2a0\uff0c\u518d\u7ed3\u5408\u5176\u4f4d\u7f6e$i$\u5c31\u53ef\u4ee5\u77e5\u9053\u5728\u6700\u524d\u9762\u6709\u591a\u5c11\u4e2a1\u4e86\u3002<\/p>\n\n\n\n
#include<bits\/stdc++.h>\r\nusing namespace std;\r\nint n,t;\r\nint a[200005],k[200005];\r\nint query(int l,int r)\r\n{\r\n cout<<\"? \"<<l<<\" \"<<r<<endl;\r\n int x;\r\n cin>>x;\r\n return x;\r\n}\r\nint main()\r\n{\r\n\tcin>>t;\r\n while (t--)\r\n {\r\n cin>>n;\r\n for (int i=0;i<=n;i++) \r\n \ta[i]=0;\r\n for (int i=2;i<=n;i++)\r\n \tk[i]=query(1,i);\r\n if (k[n]==0) \r\n {\r\n cout<<\"! IMPOSSIBLE\"<<endl;\r\n continue;\r\n }\r\n for (int i=2;i<=n;i++)\r\n \tif (k[i]>k[i-1]) a[i]=1;\r\n for (int i=2;i<=n;i++)\r\n \tif (a[i]!=0)\r\n {\r\n for (int j=1;j<=i-1-k[i];j++)\r\n \ta[j]=1;\r\n }\r\n cout<<\"! \";\r\n for (int i=1;i<=n;i++)\r\n \tcout<<a[i];\r\n cout<<endl;\r\n }\r\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u9898\u76ee\u94fe\u63a5\uff1ahttps:\/\/codeforces.com\/contest\/2037 E. Kachina’s Favorite Bi ̷","protected":false},"author":1,"featured_media":1586,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,35],"tags":[40,12,34,22,39],"class_list":["post-1581","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-3","category-35","tag-codeforces","tag-12","tag-34","tag-22","tag-39"],"_links":{"self":[{"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/posts\/1581","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/comments?post=1581"}],"version-history":[{"count":1,"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/posts\/1581\/revisions"}],"predecessor-version":[{"id":1721,"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/posts\/1581\/revisions\/1721"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/media\/1586"}],"wp:attachment":[{"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/media?parent=1581"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/categories?post=1581"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/tags?post=1581"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}