{"id":178,"date":"2018-10-21T19:08:00","date_gmt":"2018-10-21T11:08:00","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=178"},"modified":"2018-10-22T12:21:20","modified_gmt":"2018-10-22T04:21:20","slug":"cf1072","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2018\/10\/21\/cf1072\/","title":{"rendered":"CF1072"},"content":{"rendered":"

CF1072A
\n\u4e00\u9053\u7b80\u5355\u9898\u3002
\n\u53ef\u4ee5\u4e0d\u65ad\u5730\u5207\u5272\u6210\u5b50\u95ee\u9898\u3002
\n\u7136\u540e\u7edf\u8ba1\u8ba1\u7b97\u5373\u53ef\u3002<\/p>\n

CF1072B
\n\u4e00\u9053\u731c\u7ed3\u8bba\u9898\u3002
\n\u6211\u4eec\u731c\u6d4b\uff0c\u5bf9\u4e8e\\([0,3]\\)\u5f53\\(t_i\\)\u786e\u5b9a\u7684\u65f6\u5019\uff0c\\(t_i | t_{i+1}==a_i\\)\u4e0e\\(t_i \\& t_{i+1}==b_i\\)\u53ef\u4ee5\u63a8\u5bfc\u51fa\u552f\u4e00\u786e\u5b9a\u7684\\(t_{i+1}\\)
\n\u8bc1\u660e\u5f88\u590d\u6742\uff0c\u4f46\u662f\u6b63\u786e\u6027\u5f88\u663e\u7136\u3002
\n\u90a3\u4e48\u4f9d\u636e\u8fd9\u4e2a\u7ed3\u8bba\uff0c\u53ef\u4ee5\u7b80\u5355\\(DFS\\)\uff0c\u4ece\u800c\u5f97\u51fa\u7ed3\u679c\u3002<\/p>\n

CF1072C
\n\u4e00\u9053\u590d\u6742\u9898\u3002
\n\u5b83\u518d\u4e00\u6b21\u8b66\u9192\u4e86\u6211\u2014\u2014
\n\u4f60tm\u4e0d\u4f1a\u4e8c\u5206\u3002<\/p>\n

\u505a\u6cd5\u5f88\u663e\u7136\uff0c\u56e0\u4e3a\u7b54\u6848\u663e\u7136\u5177\u6709\u5355\u8c03\u6027\uff0c\u6240\u4ee5\u4e8c\u5206\\(k\\)\uff0c\u7136\u540e\\(O(n)\\)\u68c0\u9a8c\u5373\u53ef\u3002
\n\u68c0\u9a8c\u7684\u65f6\u5019\u8d2a\u5fc3\u5730\u6392\u5e03\u5373\u53ef\u3002<\/p>\n

#include<iostream>\r\n#include<cstdio>\r\n#include<cstring>\r\n#include<cmath>\r\n#include<algorithm>\r\nusing namespace std;\r\n#define Max(_A,_B) (_A>_B?_A:_B)\r\n#define Min(_A,_B) (_A<_B?_A:_B)\r\n#define Abs(_A) ((_A)?(_A):(-(_A))\r\n#define INF 0x3f3f3f3f\r\n\/*\r\nCF1072A\r\n*\/\r\nint w,h,k;\r\nvoid init(){\r\n    int ans=0;\r\n    scanf(\"%d%d%d\",&w,&h,&k);\r\n    while(k){\r\n        ans+=((w<<1)+(h<<1)-4);\r\n        --k;\r\n        h-=4,w-=4;\r\n    }\r\n    printf(\"%d\",ans);\r\n}\r\nint main(){\r\n\tinit();\r\n\treturn 0;\r\n}\r\n<\/code><\/pre>\n
#include<iostream>\r\n#include<cstdio>\r\n#include<cstring>\r\n#include<cmath>\r\n#include<algorithm>\r\nusing namespace std;\r\n#define Max(_A,_B) (_A>_B?_A:_B)\r\n#define Min(_A,_B) (_A<_B?_A:_B)\r\n#define Abs(_A) ((_A)?(_A):(-(_A))\r\n#define INF 0x3f3f3f3f\r\n\/*\r\nCF1072B\r\n*\/\r\nint n,a[100005],b[100005],t[100005];\r\nvoid init(){\r\n    scanf(\"%d\",&n);\r\n    for(int i=1;i<n;++i){\r\n        scanf(\"%d\",&a[i]);\r\n    }\r\n    for(int i=1;i<n;++i){\r\n        scanf(\"%d\",&b[i]);\r\n    }\r\n    for(int i=0;i<=4;++i){\r\n        if(i==4){\r\n            puts(\"NO\");\r\n            return;\r\n        }\r\n        t[1]=i;\r\n        for(int j=1;j<n;++j){\r\n            for(int k=0;k<=4;++k){\r\n                if(k==4){\r\n                    goto loop;\r\n                }\r\n                if((t[j]|k)==a[j]&&(t[j]&k)==b[j]){\r\n                    t[j+1]=k;\r\n                    break;\r\n                }\r\n            }\r\n            if(j==n-1){\r\n                puts(\"YES\");\r\n                for(int i=1;i<=n;++i){\r\n                    printf(\"%d \",t[i]);\r\n                }\r\n                return;\r\n            }\r\n        }\r\n        loop:;\r\n    }\r\n    \r\n}\r\nint main(){\r\n\tinit();\r\n\treturn 0;\r\n}\r\n<\/code><\/pre>\n
#include<iostream>\r\n#include<cstdio>\r\n#include<cstring>\r\n#include<cmath>\r\n#include<algorithm>\r\nusing namespace std;\r\n#define Max(_A,_B) (_A>_B?_A:_B)\r\n#define Min(_A,_B) (_A<_B?_A:_B)\r\n#define Abs(_A) ((_A)?(_A):(-(_A))\r\n#define INF 0x3f3f3f3f\r\n\/*\r\nCF1072C\r\n*\/\r\nbool bo[100005];\r\nint a,b,at,bt,al[50005],bl[50005];\r\ninline bool chck(int k){\r\n    memset(bo,0,sizeof(bo));\r\n    int nw=k,att=0,btt=0;\r\n    at=0,bt=0;\r\n    while(nw){\r\n        if(att+nw<=a){\r\n            att+=nw;\r\n            bo[nw]=1;\r\n            al[at++]=nw;\r\n        }\r\n        --nw;\r\n    }\r\n    nw=k;\r\n    while(nw){\r\n        if((!bo[nw])&&(btt+nw<=b)){\r\n            btt+=nw;\r\n            bo[nw]=1;\r\n            bl[bt++]=nw;\r\n        }\r\n        --nw;\r\n    }\r\n    for(int i=1;i<=k;++i){\r\n        if(!bo[i]){\r\n            return 0;\r\n        }\r\n    }\r\n    return 1;\r\n}\r\n\r\nvoid init(){\r\n    scanf(\"%d%d\",&a,&b);\r\n    int l=0,r=100000,mid,ans=0;\r\n    while(l<=r){\r\n        mid=((l+r)>>1);\r\n        if(chck(mid)){\r\n            ans=Max(ans,mid);\r\n            l=mid+1;\r\n        }else{\r\n            r=mid-1;\r\n        }\r\n    }\r\n    chck(ans);\r\n    printf(\"%d\\n\",at);\r\n    for(int i=0;i<at;++i){\r\n        printf(\"%d \",al[i]);\r\n    }\r\n    puts(\"\");\r\n    printf(\"%d\\n\",bt);\r\n    for(int i=0;i<bt;++i){\r\n        printf(\"%d \",bl[i]);\r\n    }\r\n    puts(\"\");\r\n}\r\nint main(){\r\n\tinit();\r\n\treturn 0;\r\n}\r\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
CF1072A \u4e00\u9053\u7b80\u5355\u9898\u3002 \u53ef\u4ee5\u4e0d\u65ad\u5730\u5207\u5272\u6210\u5b50\u95ee\u9898\u3002 \u7136\u540e\u7edf\u8ba1\u8ba1\u7b97\u5373\u53ef\u3002 CF1072B \u4e00\u9053\u731c\u7ed3\u8bba\u9898\u3002 \u6211 … <\/p>\n
\u7ee7\u7eed\u9605\u8bfb\u201cCF1072\u201d<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[20,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/178"}],"collection":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/comments?post=178"}],"version-history":[{"count":1,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/178\/revisions"}],"predecessor-version":[{"id":179,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/178\/revisions\/179"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=178"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=178"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=178"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}