Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"QWsin","updateTime":1482412917000,"title":"LA3357 Pinary","dislikeCnt":1,"content":"题目\n-\n[LA3357 Pinary](https://vjudge.net/problem/UVALive-3357)\n\n题解\n-\n不知道是这道数位DP简单了还是我做了有一些数位DP题然后提升了qwq。首先根据套路设出一个函数g(x)表示后x位随便取的时候答案的个数,然后想办法预处理g数组,但是因为题目要求没有连续的1,所以很自然的加一维,g(x,0),表示后x位随便取,第一位取0的时候,的答案个数,1的状态类似。转移就很简单了。g数组搞定。\n\n然后第一步是要确定位数,不难发现如果有lim(先考虑lim\u003e\u003d2)位的话,lim这位肯定是1,lim-1这一位肯定为0,所以长度为lim位的答案共有g[lim-1][0]个,就可以推出答案位数lim了。\n\n知道位数之后,我们已经确定了两位了,继续往后走,因为这道题是01串所以实际上是非常方便的,如果i这一位为0的话答案共有g[i][0]个,当这时的k\u003c\u003dg[i][0]时这一位为0否则为1.(感觉有点像treap,而且kth变化的过程实际上也和treap求rank非常像),只需要特判一下最后一位,就行了。qwq是不是好简单。\n\n代码\n-\n```\n//QWsin\n#include\u003ccmath\u003e\n#include\u003ccstdio\u003e\n#include\u003ccstring\u003e\n#include\u003ciostream\u003e\n#include\u003calgorithm\u003e\nusing namespace std;\nconst int maxn\u003d1000+10;\ntypedef long long ll;\n\nll g[maxn][2];\ninline void init_g()\n{\n\tg[0][0]\u003dg[0][1]\u003dg[1][1]\u003dg[1][0]\u003d1;\n\tfor(int i\u003d2;i\u003c\u003d1000;++i) {\n\t\tg[i][0]\u003dg[i-1][1]+g[i-1][0];\n\t\tg[i][1]\u003dg[i-1][0];\n\t}\n}\n\nint kth;\n\ninline void solve()\n{\n\tscanf(\"%d\",\u0026kth);\n\tint lim\u003d1;\n\twhile(kth \u003e g[lim-1][0]) kth-\u003dg[(lim++)-1][0];\n\tputchar(\u00271\u0027);\n\tif(lim!\u003d1)\n\t{\n\t\tputchar(\u00270\u0027);\n\t\tfor(int i\u003dlim-2;i\u003e\u003d1;--i)\n\t\t{\n\t\t\tif(i\u003d\u003d1)putchar(kth\u003d\u003d1?\u00270\u0027:\u00271\u0027);\n\t\t\telse if(kth \u003e g[i][0]) kth-\u003dg[i][0],putchar(\u00271\u0027);\n\t\t\telse putchar(\u00270\u0027);\n\t\t}\n\t}\n\tputchar(\u0027\\n\u0027);\n}\n\nint main()\n{\n\tinit_g();\n\tint T;cin\u003e\u003eT;\n\twhile(T--) solve();\n\treturn 0;\n}\n\n```","threadId":12301,"likeCnt":4,"createTime":1482412917000,"isWorkbook":false,"viewCnt":3103,"openness":2,"fav":false,"id":7,"trustable":false}