loli的搜索测试-4

其实这已经是第四次搜索测试了...只不过上两次测试时我不在学校，扔两个链接吧：

测试-2：https://www.luogu.org/blog/user35178/loli-di-sou-suo-ce-shi-1-post

测试-3：https://www.luogu.org/blog/user35178/loli-di-sou-suo-ce-shi-2-post

远程感谢一下wzx dalao提供blog。

现在回头说说今天的考试吧：

T1 小木棍：https://www.luogu.org/problemnew/show/P1120

请看https://www.cnblogs.com/shzr/p/9070959.html，已经讲了。。。

T2 weight

为什么不能贴图片！手敲一份放这里：

已知原数列$a_{1}$...$a_{n}$的前一项，前二项...前$n$项和，以及后一项，后两项...后$n$项和。但是这些和被打乱了顺序。还知道原数列中的数都存在于集合$S$中，求原数列。（字典序最小）

$n<=1000$,$S$中的数大于等于1，小于等于500；

考场上的写法是先排序，从$2*n$个数中选出$n$个作为前缀和，可以推出原数列，再check一下，显然是T到飞起啦。

但是这道题的神奇之处在于没有数据，wzx给我们造了一些数据，可是没有$std$，导致$n=100$的数据就成了极限数据...后来想到我的做法可以进行优化，如果确定了一些数是前缀，那么自然就选出了一些数为后缀，边选边判断就可以啦。做完后送到学长那里check一下，结果check过了，答案和学长的却不一样，从头开始比较发现我的这个竟然还更优...于是改来改去弄了半个下午，发现是数组越界的问题。也就是说，从头往后看的确是更优，但是到了结尾处就会发现有的数已经超过了500，这就是数组越界导致的。还学到一个新知识，如果程序中出现过数组越界，再使用cin，cout就会出一些奇怪的问题，这种时候先不要急着改成scanf，关键是看看程序到底哪里出了问题。

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <algorithm>
 4 # define R register int
 5 
 6 using namespace std;
 7 
 8 int n;
 9 int s[2005],ans[1005],t[1005];
10 int m;
11 bool a[505]={false},f=false;
12 
13 void dfs(int x,int p1,int p2,int q,int h)
14 {
15     if(f) return ;
16     if(x==n+1)
17     {
18         for (R i=1;i<=n;++i)
19             ans[i]=t[i];
20         f=true;
21         return;
22     }
23     if(q>n) return ;
24     if(h>n) return ;
25     if(s[x]-s[p1]<=500&&a[ s[x]-s[p1] ])
26     {
27         if(t[q+1]!=0&&t[q+1]!=s[x]-s[p1]) return ;
28         t[q+1]=s[x]-s[p1];
29         dfs(x+1,x,p2,q+1,h);
30         t[q+1]=0;
31     }
32     if(s[x]-s[p2]<=500&&a[ s[x]-s[p2] ])    
33     {
34          if(t[n-h]!=0&&t[n-h]!=s[x]-s[p2]) return ;
35         t[n-h]=s[x]-s[p2];
36         dfs(x+1,p1,x,q,h+1);
37         t[n-h]=0;
38     }
39 }
40 
41 int main()
42 {
43     scanf("%d",&n);
44     for (R i=1;i<=2*n;++i)
45         scanf("%d",&s[i]);
46     sort(s+1,s+1+2*n);
47     scanf("%d",&m);
48     int x;
49     for (R i=1;i<=m;++i)
50     {
51         scanf("%d",&x);
52         a[x]=true;
53     }
54     dfs(1,0,0,0,0);
55     for (R i=1;i<=n;++i)
56         cout<<ans[i]<<' ';
57     return 0;
58 }

weight

T3 靶形数独：https://www.luogu.org/problemnew/show/P1074

这在之前的blog也有：https://www.cnblogs.com/shzr/p/9064787.html。

loli的搜索测试-4

推荐阅读