{"id":724,"date":"2019-03-26T16:21:11","date_gmt":"2019-03-26T08:21:11","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=724"},"modified":"2019-03-26T16:40:24","modified_gmt":"2019-03-26T08:40:24","slug":"cf1140","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2019\/03\/26\/cf1140\/","title":{"rendered":"CF1140"},"content":{"rendered":"\n
\n\n\n\n

CF1140A
\n\u8fd9\u662f\u4e00\u9053\u7b7e\u5230\u9898\u3002\u6a21\u62df\u5373\u53ef\u3002 <\/p>\n\n\n\n

\n\n\n\n
#include<iostream>\n#include<cstdio>\n#include<cstring>\n#include<algorithm>\n#include<queue>\n#include<vector>\nusing namespace std;\n\nint n;\nint a[10005];\nvoid init(){\n\tscanf(\"%d\",&n);\n\tint ans=0;\n\tfor(int i=1;i<=n;++i){\n\t\tscanf(\"%d\",a+i);\n\t}\n\tint p=1,mx=0;\n\twhile(p<=n){\n\t\t++ans;\n\t\tmx=max(mx,a[p]);\n\t\twhile(p<=mx){\n\t\t\tmx=max(mx,a[p]);\n\t\t\t++p;\n\t\t}\n\t}\n\tprintf(\"%d\\n\",ans);\n}\nint main(){\n\tinit();\n\treturn 0;\n}\n\n<\/code><\/pre>\n\n\n\n
\n\n\n\n
CF1140B
\n\u8fd9\u662f\u4e00\u9053\u82f1\u6587\u9605\u8bfb\u7406\u89e3\u9898\u3002
\n\u4e00\u4e2a\u7b26\u53f7\u53ef\u4ee5\u4f7f\u7528\u4efb\u610f\u591a\u6b21\uff0c\u56e0\u6b64\u5f62\u5982>><><><><><><><\u7684\u5e8f\u5217\u4e5f\u662f\u5408\u6cd5\u7684\u3002 <\/p>\n\n\n\n
\n\n\n\n
#include<iostream>\n#include<cstdio>\n#include<cstring>\n#include<algorithm>\n#include<queue>\n#include<vector>\nusing namespace std;\n\nint n;\nchar ch[100005];\n\nvoid init(){\n\tscanf(\"%d\",&n);\n\tcin>>ch+1;\n\tint j=1,ans=0;\n\twhile(ch[j]!='>'&&ch[n-j+1]!='<'){\n\t\t++j;\n\t\t++ans;\n\t}\n\tprintf(\"%d\\n\",ans);\n}\nint main(){\n\tint T;\n\tscanf(\"%d\",&T);\n\twhile(T--){\n\t\tinit();\n\t}\n\treturn 0;\n}\n\n<\/code><\/pre>\n\n\n\n
\n\n\n\n
CF1140C
\n\u6309\u597d\u542c\u7a0b\u5ea6\u6392\u4e2a\u5e8f\uff0c\u679a\u4e3e\u4e00\u904d\u3002
\n\u663e\u7136\u67d0\u9996\u6b4c\u540e\u9762\u7684\u6240\u6709\u6b4c\u90fd\u53ef\u4ee5\u542c\u3002\u4f46\u662f\u6709k\u7684\u9650\u5236\u3002\u6240\u4ee5\u4ece\u540e\u5f80\u524d\u7528\u4f18\u5148\u961f\u5217\u8ba1\u7b97\u4e00\u4e0b\u524dk\u5927\u548c\u5373\u53ef\u3002<\/p>\n\n\n\n
\n\n\n\n
#include<iostream>\n#include<cstdio>\n#include<cstring>\n#include<algorithm>\n#include<queue>\n#include<vector>\nusing namespace std;\n\ntypedef long long ll;\ninline ll Max(ll A,ll B){\n\treturn A>B?A:B;\n}\nstruct data{\n\tll b;\n\tll t;\n\tinline operator<(const data &B)const{\n\t\treturn t<B.t;\n\t}\n}a[300005]; \n\nint n,k;\nll sm[300005];\npriority_queue< int,vector<int>,greater<int> > q;\nvoid init(){\n\tscanf(\"%d%d\",&n,&k);\n\tfor(int i=1;i<=n;++i){\n\t\tscanf(\"%lld%lld\",&a[i].b,&a[i].t);\n\t}\n\tsort(a+1,a+1+n);\n\tll cnt=0;\n\tfor(int i=n;i>=1;--i){\n\t\tcnt+=a[i].b;\n\t\tq.push(a[i].b);\n\t\twhile(q.size()>k){\n\t\t\tcnt-=q.top();\n\t\t\tq.pop();\n\t\t}\n\t\tsm[i]=cnt;\n\t}\n\tll ans=0;\n\tfor(int i=1;i<=n;++i){\n\t\tans=Max(ans,sm[i]*a[i].t);\n\t}\n\tprintf(\"%lld\\n\",ans);\n}\nint main(){\n\tinit();\n\treturn 0;\n}\n\n<\/code><\/pre>\n\n\n\n
\n\n\n\n
CF1140D
\n\u8d2a\u5fc3\u5730\u8003\u8651\uff0c\u6bcf\u4e2a\u9876\u70b9\u90fd\u9009\u62e91\u7684\u8bdd\u7b54\u6848\u4f1a\u6700\u4f18\u3002
\n\u5982\u679c\u6bcf\u4e2a\u90fd\u628a\u4e00\u4e2a\u9876\u70b9\u9009\u62e91\u7684\u8bdd\uff0c\u90a3\u4e48\u6839\u636e\u57fa\u672c\u4e0d\u7b49\u5f0f\uff0c\u9009\u62e9\u5c3d\u53ef\u80fd\u76f8\u90bb\u7684\u6784\u6210\u4e09\u89d2\u5f62\u4f1a\u66f4\u4f18\u3002<\/p>\n\n\n\n
\n\n\n\n
#include<iostream>\n#include<cstdio>\n#include<cstring>\n#include<algorithm>\n#include<queue>\n#include<vector>\nusing namespace std;\n\nint n;\n\nvoid init(){\n\tscanf(\"%d\",&n);\n\tlong long ans=0;\n\tfor(int i=2;i<n;++i){\n\t\tans+=1*i*(i+1);\n\t}\n\tprintf(\"%lld\\n\",ans);\n}\nint main(){\n\tinit();\n\treturn 0;\n}\n\n<\/code><\/pre>\n\n\n\n
\n\n\n\n
CF1140E
 \u6211\u4eec\u53d1\u73b0\uff0c\u7531\u4e8e\u9650\u5b9a\u4e3a\u5947\u56de\u6587\u4e32\uff0c\u539f\u9898\u7684\u9898\u610f\u53ef\u4ee5\u8f6c\u5316\u4e3a\u6c42\u9694\u4e00\u4e2a\u4e0d\u76f8\u7b49\u7684\u65b9\u6848\u6570\u3002
 \u6545\u800c\uff0c\u5bb9\u6613\u53d1\u73b0\uff0c\u8fd9\u662f\u5947\u5076\u65e0\u5173\u7684\u3002
 \u6211\u4eec\u5bb9\u6613\u5730\u4ee4\\(f_{i,j}\\)\u4e3a\u7b2c\\(i\\)\u4e2a\u586b\\(j\\)\u7684\u65b9\u6848\u6570\u3002\u5bb9\u6613\u5f97\u5230\uff1a
 $$f_{i,j}+=f_{i-1,k},(k\\ne j)$$
 \u7136\u800c\u8fd9\u6837\u7684\u590d\u6742\u5ea6\u662f\u4e0d\u53ef\u63a5\u53d7\u7684\u3002
 \u6211\u4eec\u8003\u8651\u7edf\u8ba1\u4e00\u4e2a-1\u533a\u95f4\u7684\u7b54\u6848\u3002\u9996\u5148\uff0c\u6211\u4eec\u53ef\u4ee5\u53ea\u8003\u8651\u5de6\u7aef\u7684\u975e-1\u6570\u5bf9\u8ba1\u7b97\u5e26\u6765\u7684\u5f71\u54cd\u2014\u2014\u8fd9\u662f\u56e0\u4e3a\u6574\u4e2a\u533a\u95f4\u662f\u5bf9\u79f0\u7684\uff0c\u6240\u4ee5\u53f3\u7aef\u7684\u975e-1\u6570\u9020\u6210\u7684\u989d\u5916\u5f71\u54cd\u662f\u53ef\u4ee5\u7edf\u8ba1\u7684\u3002
 \u4e0d\u59a8\u4ee4\u8fd9\u4e2a-1\u533a\u95f4\u524d\u7684\u7b2c\u4e00\u4e2a\u975e-1\u6570\u4e3a\\(q\\)\uff0c\u90a3\u4e48\u53ef\u4ee5\u53d1\u73b0\uff0c\\(f_{i,q}\\ne f_{i,k},f_{i,j}=f_{i,k},(j\\ne k,j\\ne q,k\\ne q)\\)
 \u53d1\u73b0\u8fd9\u4e2a\u6027\u8d28\u4e4b\u540e\uff0c\u6211\u4eec\u5c31\u53ef\u4ee5\u4f18\u5316\u524d\u9762\u7684\u8f6c\u79fb\u4e86\u3002\u6211\u4eec\u4e0d\u59a8\u4ee4\\(f_{i,0}\\)\u8868\u793a\u7b2c\\(i\\)\u4f4d\u4e0e\\(q\\)\u4e0d\u540c\u7684\u65b9\u6848\u6570\uff0c\\(f_{i,1}\\)\u8868\u793a\u7b2c\\(i\\)\u4f4d\u4e0e\\(q\\)\u76f8\u540c\u7684\u65b9\u6848\u6570\u3002\u53ef\u4ee5\u5f97\u5230\u8f6c\u79fb\u65b9\u7a0b\uff1a
 $$f_{i,0}=(k-2)f_{i-1,0}+(k-1)f_{i-1,1}$$
 $$f_{i,1}=f_{i-1,0}$$
 \u4e8e\u662f\u7edf\u8ba1\u533a\u95f4\u8ba1\u7b97\u5373\u53ef\u3002
 \u7136\u800c\uff0c\u6211\u4eec\u8fd8\u9700\u8981\u8ba1\u7b97\u53f3\u7aef\u7684\u7b2c\u4e00\u4e2a\u975e-1\u6570\u5bf9\u7b54\u6848\u7684\u5f71\u54cd\u3002\u5982\u679c\u5b83\u4e0e\u5de6\u7aef\u7684\u90a3\u4e2a\u6570\u76f8\u540c\uff0c\u90a3\u4e48\u521d\u59cb\u5316\\(f_{0,1}=1,f_{0,0}=0\\)\u76f4\u63a5\u7edf\u8ba1\u5373\u53ef\uff1b\u5982\u679c\u5b83\u548c\u5de6\u7aef\u7684\u90a3\u4e2a\u6570\u4e0d\u540c\uff0c\u90a3\u4e48\u521d\u59cb\u5316\\(f_{0,0}=1,f_{0,1}=0\\)\uff0c\u5219\u53ef\u4ee5\u628a\u4ece\u5de6\u5230\u53f3\u7684\u8d21\u732e\u5bb9\u65a5\u6389\u3002<\/p>\n\n\n\n
\n\n\n\n
#include<iostream>\n#include<cstdio>\n\n\ntypedef long long ll;\nconst ll MOD=998244353;\nll n,k;\nll a[200005],f[200005][2];\n\ninline ll calc(ll LEN,ll L,ll R){\n\tif(!LEN){\n\t\treturn !L||!R||L!=R;\n\t}\n\tfor(int i=0;i<=LEN;++i){\n\t\tf[i][0]=f[i][1]=0;\n\t}\n\tif(!L){\n\t\t--LEN;\n\t\tf[0][0]=k-1;\n\t\tf[0][1]=1;\n\t}else{\n\t\tf[0][L==R]=1;\n\t}\n\tfor(int i=1;i<=LEN;++i){\n\t\tf[i][0]=(f[i-1][0]*(k-2)+f[i-1][1]*(k-1))%MOD;\n\t\tf[i][1]=f[i-1][0];\n\t}\n\treturn R?f[LEN][0]:(f[LEN][0]+f[LEN][1])%MOD;\n}\n\nvoid init(){\n\tscanf(\"%lld%lld\",&n,&k);\n\tfor(int i=1;i<=n;++i){\n\t\tscanf(\"%lld\",&a[i]);\n\t}\n\tll lst=-1,ans=1;\n\tfor(int i=1;i<=n+2;i+=2){\n\t\tif(~a[i]||i>n){\n\t\t\tans*=calc(((i-lst)>>1)-1,lst>0?a[lst]:0,a[i]);\n\t\t\tans%=MOD; \n\t\t\tlst=i;\n\t\t}\n\t}\n\tlst=0;\n\tfor(int i=2;i<=n+2;i+=2){\n\t\tif(~a[i]||i>n){\n\t\t\tans*=calc(((i-lst)>>1)-1,lst>0?a[lst]:0,a[i]);\n\t\t\tans%=MOD;\n\t\t\tlst=i;\n\t\t}\n\t}\n\tprintf(\"%lld\\n\",ans);\n}\n\nint main(){\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
CF1140A \u8fd9\u662f\u4e00\u9053\u7b7e\u5230\u9898\u3002\u6a21\u62df\u5373\u53ef\u3002 CF1140B \u8fd9\u662f\u4e00\u9053\u82f1\u6587\u9605\u8bfb\u7406\u89e3\u9898\u3002 \u4e00\u4e2a\u7b26\u53f7\u53ef\u4ee5\u4f7f\u7528\u4efb\u610f\u591a\u6b21 … <\/p>\n
\u7ee7\u7eed\u9605\u8bfb\u201cCF1140\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\/724"}],"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=724"}],"version-history":[{"count":2,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/724\/revisions"}],"predecessor-version":[{"id":728,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/724\/revisions\/728"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=724"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=724"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=724"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}