目录
展开
6 数字分段 TODO
这个二分法是用什么二分的？是前缀和？可是不是要分成很多段嘛？分成三段的画，怎么二分呢？
4 链表优化 40 TLE TODO
我直接用的 stl 里面的 vector，我想不到有什么优化的方法。找的过程如果用 hashtable，可以缩短到 O(1) 时间找到，但是在插入的时候，hashtable 就要花费 O(n) 的时间来修改，我现在这样是花费多个 O(logn)，改 hash 难道不是得不偿失吗？
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
<div><span class="hljs-meta"># <span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string"><cstdio></span></span>
<span class="hljs-meta"># <span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string"><vector></span></span>
<span class="hljs-meta"># <span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string"><algorithm></span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>{
<span class="hljs-keyword">int</span> n,m,lr,v;
<span class="hljs-built_in">vector</span><<span class="hljs-keyword">int</span>>team(<span class="hljs-number">1</span>,<span class="hljs-number">1</span>);
<span class="hljs-built_in">scanf</span>(<span class="hljs-string">"%d"</span>,&n);
<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>;i<n;i++){
<span class="hljs-built_in">scanf</span>(<span class="hljs-string">"%d %d"</span>,&v,&lr);
team.insert(find(team.begin( ),team.end( ), v)+lr,i+<span class="hljs-number">1</span>);
}
<span class="hljs-built_in">scanf</span>(<span class="hljs-string">"%d"</span>,&m);
<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>;i<m;i++){
<span class="hljs-built_in">scanf</span>(<span class="hljs-string">"%d"</span>,&v);
<span class="hljs-built_in">vector</span><<span class="hljs-keyword">int</span>>::iterator res = find(team.begin( ), team.end( ), v);
<span class="hljs-keyword">if</span> (res != team.end())
team.erase(res);
}
<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>;i<team.size();i++){
<span class="hljs-built_in">printf</span>(<span class="hljs-string">"%d"</span>,team[i]);
<span class="hljs-keyword">if</span>(i != team.size()<span class="hljs-number">-1</span>)<span class="hljs-built_in">printf</span>(<span class="hljs-string">" "</span>);
<span class="hljs-keyword">else</span> <span class="hljs-built_in">printf</span>(<span class="hljs-string">"\n"</span>);
}
<span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}
</div>
|