- \n
- \n
\u9898\u76ee\u63cf\u8ff0<\/strong><\/h3>\n<\/li>\n<\/ul>\n
\u4f60\u6709 \\(n\\) \u53ea\u732b\uff0c\u6bcf\u4e00\u53ea\u732b\u8ba4\u8bc6\u53e6\u4e00\u4e9b\u732b\u3002\u4f46\u82e5 \\(a\\) \u732b\u8ba4\u8bc6 \\(b\\) \u732b\uff0c\\(b\\) \u732b\u4e0d\u4e00\u5b9a\u4f1a\u8ba4\u8bc6 \\(a\\) \u732b\u3002<\/p>\n
\u73b0\u5728\uff0c\u4f60\u9700\u8981\u5c06\u6bcf\u4e00\u53ea\u732b\u67d3\u6210\u7ea2\u8272\u6216\u7eff\u8272\u3002\u4f60\u662f\u5426\u53ef\u4ee5\u901a\u8fc7\u67d3\u8272\u8ba9\u6bcf\u4e00\u53ea\u732b\u90fd\u8ba4\u8bc6\u5076\u6570\u53ea<\/strong>\u548c\u81ea\u5df1\u540c\u8272\u7684\u732b\u5462\uff1f<\/p>\n
- \n
- \n
\u8f93\u5165\u683c\u5f0f<\/strong><\/h3>\n<\/li>\n<\/ul>\n
\u7b2c\u4e00\u884c \\(n\\)\uff1b<\/p>\n
\u63a5\u4e0b\u6765 \\(n\\) \u884c\uff0c\u6bcf\u884c\u7b2c\u4e00\u4e2a\u6570 \\(d_i\\) \u8868\u793a\u732b \\(i\\) \u8ba4\u8bc6\u7684\u732b\u7684\u4e2a\u6570\uff0c\u540e\u9762\u8ddf\u7740 \\(d_i\\) \u4e2a\u6570\u8868\u793a\u8ba4\u8bc6\u7684\u732b\u662f\u54ea\u4e9b\u3002<\/p>\n
- \n
- \n
\u8f93\u51fa\u683c\u5f0f<\/strong><\/h3>\n<\/li>\n<\/ul>\n
\u8fbe\u4e0d\u5230\u8981\u6c42\uff0c\u8f93\u51fa
Impossible<\/code>\u3002<\/p>\n\u5426\u5219\u7b2c\u4e00\u884c\u8f93\u51fa\u7ea2\u8272\u732b\u7684\u4e2a\u6570\uff0c\u7b2c\u4e8c\u884c\u8f93\u51fa\u54ea\u4e9b\u732b\u662f\u7ea2\u8272\uff08\u90a3\u4e48\u5176\u4ed6\u732b\u5c31\u662f\u7eff\u8272\uff09<\/p>\n
\u53ef\u4ee5\u8f93\u51fa\u4efb\u610f\u65b9\u6848\u3002<\/p>\n
- \n
- \n
\u6837\u4f8b\u8f93\u5165<\/strong><\/h3>\n<\/li>\n<\/ul>\n
5\r\n3 2 3 4\r\n2 1 3\r\n4 2 1 4 5\r\n2 1 3\r\n1 3<\/pre>\n
- \n
- \n
\u6837\u4f8b\u8f93\u51fa<\/strong><\/h3>\n<\/li>\n<\/ul>\n
3\r\n1 2 3<\/pre>\n
- \n
- \n
\u6570\u636e\u89c4\u6a21\u4e0e\u7ea6\u5b9a<\/strong><\/h3>\n<\/li>\n<\/ul>\n
\u5bf9\u4e8e \\(100\\%\\) \u7684\u6570\u636e\uff0c\\(n \\leq 2000\\) \u3002<\/p>\n
<\/p>\n
<\/p>\n
<\/p>\n
<\/p>\n
\n<\/p>\n
<\/p>\n
<\/p>\n
![\"\"](\"https:\/\/cf.mnihyc.com\/blog\/wp-content\/uploads\/2019\/07\/QQ\u622a\u56fe20190702171206.png\")
<\/p>\n<\/p>\n
\u9ad8\u65af\u6d88\u5143\u662f \\(O(n^3)\\) \u7684\uff0c\u5957\u4e2a std::bitset<\/span>\u00a0 \u5c31\u53ef\u4ee5 \\(\\O(\\frac{n^2}{32})) \u3002<\/p>\n
<\/p>\n
#include <cstdio>\r\n#include <cstdlib>\r\n#include <cstring>\r\n#include <climits>\r\n#include <bitset>\r\n\r\ninline int getnum()\r\n{\r\n\tregister char c=0;\r\n\twhile(!(c>='0' && c<='9'))\r\n\t\tc=getchar();\r\n\tregister int a=0;\r\n\twhile(c>='0' && c<='9')\r\n\t\ta=a*10+c-'0',c=getchar();\r\n\treturn a;\r\n}\r\n\r\nstd::bitset<2002>a[2001];\r\n\r\nint main()\r\n{\r\n\tregister int N=getnum();\r\n\tfor(register int i=1;i<=N;i++)\r\n\t{\r\n\t\tregister int d=getnum();\r\n\t\tif(d&1)\r\n\t\t\ta[i][i]=a[i][N+1]=true;\r\n\t\tfor(register int j=1;j<=d;j++)\r\n\t\t\ta[i][getnum()]=true;\r\n\t}\r\n\t\r\n\tfor(register int i=1;i<=N;i++)\r\n\t{\r\n\t\tregister int j=i;\r\n\t\twhile(j<=N && !a[j][i])\r\n\t\t\tj++;\r\n\t\tif(j>N)\r\n\t\t\tcontinue;\r\n\t\t\r\n\t\tif(j!=i)\r\n\t\t\ta[i]^=a[j]^=a[i]^=a[j];\r\n\t\tfor(j=i+1;j<=N;j++)\r\n\t\t\tif(a[j][i])\r\n\t\t\t\ta[j]^=a[i];\r\n\t}\r\n\t\r\n\tfor(register int i=N;i>1;i--)\r\n\t\tif(a[i][N+1])\r\n\t\t{\r\n\t\t\tif(!a[i][i])\r\n\t\t\t{\r\n\t\t\t\tprintf(\"Impossible\\n\");\r\n\t\t\t\treturn 0;\r\n\t\t\t}\r\n\t\t\tfor(register int j=i-1;j>=1;j--)\r\n\t\t\t\tif(a[j][i])\r\n\t\t\t\t\ta[j]^=a[i];\r\n\t\t}\r\n\t\r\n\tregister int cnt=0;\r\n\tfor(register int i=1;i<=N;i++)\r\n\t\tif(a[i][N+1])\r\n\t\t\tcnt++;\r\n\tprintf(\"%d\\n\",cnt);\r\n\tfor(register int i=1;i<=N;i++)\r\n\t\tif(a[i][N+1])\r\n\t\t\tprintf(\"%d \",i);\r\n\tprintf(\"\\n\");\r\n\t\r\n\treturn 0;\r\n}<\/pre>\n<\/p>\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
- \n
- \n
- \n
- \n
- \n