农夫约翰有一条长度为 L 的绳子，可用于农场周围的各种任务。
绳子在不同的位置有 N 个绳结，包括两个端点处各有一个。
约翰注意到，在某些位置，他可以将绳子对折，这样，相对的绳索上的绳结就可以彼此完全对齐：
请帮助约翰统计具有此属性的折叠点数。
允许在某个绳结处折叠，但不允许在端点绳结处折叠。
折叠后，较长的一侧可以有多余节点。
输入格式
第一行包含两个整数 N 和 L。
接下来 N 行，每行包含一个 0∼L 范围内的数，表示一个绳结的位置。其中两行包含的数字分别是 0 和 L。
输出格式
输出有效折叠位置的数量。
数据范围
1≤L≤10000,
1≤N≤100
输入样例：
|
1 |
5 10 0 10 6 2 4 |
输出样例：
|
1 |
4 |
样例解释
有效折叠位置为 1,2,3,8。
题目分析
给定一段绳子，然后绳子上某些位置有绳结，然后判断有多少个位置折叠后，可以将绳结全部匹配（超出的部分可以不匹配，没有超出的部分一定要完全匹配）
难点：折叠的点可能不是整数，可能是一个小数，比如 0 和 1 的中点可以进行折叠，使得 0 和 1 匹配
处理方法：将全部的数据进行 *2 处理，将中点的情况全部规避掉
时间复杂度O(104)
|
1 |
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string"><iostream></span></span> <span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string"><algorithm></span></span> <span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string"><cstring></span></span> <span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string"><cmath></span></span> <span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string"><vector></span></span> <span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string"><stack></span></span> <span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string"><queue></span></span> <span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string"><sstream></span></span> <span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">x</span> <span class="token expression">first</span></span> <span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">y</span> <span class="token expression">second</span></span> <span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span> <span class="token keyword">typedef</span> <span class="token keyword">long</span> <span class="token keyword">long</span> ll<span class="token punctuation">;</span> <span class="token keyword">typedef</span> pair<span class="token operator"><</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span> PII<span class="token punctuation">;</span> <span class="token keyword">const</span> <span class="token keyword">int</span> N <span class="token operator">=</span> <span class="token number">20010</span><span class="token punctuation">;</span> <span class="token keyword">const</span> <span class="token keyword">int</span> MOD <span class="token operator">=</span> <span class="token number">1000000007</span><span class="token punctuation">;</span> <span class="token keyword">const</span> <span class="token keyword">int</span> INF <span class="token operator">=</span> <span class="token number">0x3f3f3f3f</span><span class="token punctuation">;</span> <span class="token keyword">int</span> <span class="token function">gcd</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">,</span> <span class="token keyword">int</span> b<span class="token punctuation">)</span><span class="token punctuation">{<!-- --></span><span class="token keyword">return</span> b <span class="token operator">?</span> <span class="token function">gcd</span><span class="token punctuation">(</span>b<span class="token punctuation">,</span> a <span class="token operator">%</span> b<span class="token punctuation">)</span> <span class="token operator">:</span> a<span class="token punctuation">;</span><span class="token punctuation">}</span> <span class="token keyword">int</span> n<span class="token punctuation">,</span> l<span class="token punctuation">;</span> <span class="token keyword">int</span> a<span class="token punctuation">[</span>N<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token keyword">int</span> <span class="token function">check</span><span class="token punctuation">(</span><span class="token keyword">int</span> u<span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><=</span> u<span class="token punctuation">;</span> i <span class="token operator">++</span> <span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">if</span><span class="token punctuation">(</span>u <span class="token operator">+</span> i <span class="token operator">></span> l <span class="token operator">||</span> u <span class="token operator">-</span> i <span class="token operator"><</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">continue</span><span class="token punctuation">;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>a<span class="token punctuation">[</span>u <span class="token operator">-</span> i<span class="token punctuation">]</span> <span class="token operator">!=</span> a<span class="token punctuation">[</span>u <span class="token operator">+</span> i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> cin <span class="token operator">>></span> n <span class="token operator">>></span> l<span class="token punctuation">;</span> l <span class="token operator">*=</span> <span class="token number">2</span><span class="token punctuation">;</span> <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> n<span class="token punctuation">;</span> i <span class="token operator">++</span> <span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">int</span> x<span class="token punctuation">;</span> cin <span class="token operator">>></span> x<span class="token punctuation">;</span> x <span class="token operator">*=</span> <span class="token number">2</span><span class="token punctuation">;</span> a<span class="token punctuation">[</span>x<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator"><</span> l<span class="token punctuation">;</span> i <span class="token operator">++</span> <span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> ans <span class="token operator">+=</span> <span class="token function">check</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> cout <span class="token operator"><<</span> ans <span class="token operator"><<</span> endl<span class="token punctuation">;</span> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> |
微信扫一扫打赏
支付宝扫一扫打赏
