HDU4831&&4832&&4834

好久没打代码啦，今天lu一发百度之星，感觉还是学到不少东西的，写点收获。

第一题就是现在的HDU4831啦，题意很清楚，我一开始以为休息区也可以变为风景区，所以就不敢敲了，后来才得知数据里只会改风景区的，然后就有下面的思路。对于每个点我们用pre,post记录它前一个风景区和后一个风景区，对于每个休息区的热度，我们实际上只需要比较pre,post里哪个景点比较近，另外再开一个cnt数组记录每个风景区的点能到直接影响到的点的个数（其中不包括等距的点）。然后开一个树状数组去存热度为i的点有多少,每次更新lk,vk的时候，只需要将hot[lk]减去cnt[lk],然后修改hot[lk]再在hot[lk]上加上cnt[lk]，但是有可能它前后的一些等距的点也会被更新，所以我们看pre[lk]和lk的中点是否存在，存在的话特别的更新一下，同样处理post[lk].

但是好像本题能够直接模拟过掉，就是询问的时候扫一遍也可以，但是我感觉要是询问很多的时候会跪呀。。

第二题就是比赛的时候想了很久的题，没有思路，后来看了别人的代码才明白，纵向和横向是独立的，我们可以分开两个dp数组去记录横向走x步和纵向走k-x步有多少种走法，然后用组合数合起来就好.

最后一题我想应该很多人也是这样做的，先本地打表，然后上OEIS搜，果然搜到一个序列，然后经过对OEIS的资料进行分析就会发现，该数列的二次差分的数列an表示的是n有多少个奇数因子。然后不难发现如果能求出tau(n)（即n有多少个因子），那么就可以O(n)求出an。令我惊讶的是tau(n)居然能线性预处理，实在是太可怕了。。贴个链接以后好好学习http://blog.sina.com.cn/s/blog_82462ac30100y17u.html

到期末了，不能很舒心的欢乐的打代码了，要准备各科的复习了。。想想就觉得蛋疼。。

贴一下代码。

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

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

<code>//HDU4831&lt;br&gt;#pragma warning(disable:4996)</code>

<code>#include &lt;iostream&gt;</code>

<code>#include &lt;cstring&gt;</code>

<code>#include &lt;string&gt;</code>

<code>#include &lt;vector&gt;</code>

<code>#include &lt;cstdio&gt;</code>

<code>#include &lt;algorithm&gt;</code>

<code>#include &lt;cmath&gt;</code>

<code>#include &lt;map&gt;</code>

<code>using</code>

<code>namespace</code> <code>std;</code>

<code>#define ll long long</code>

<code>#define maxn 100000</code>

<code>#define imp 1000000000</code>

<code>#define imp2 1000000001</code>

<code>int</code>

<code>bit[maxn + 50];</code>

<code>void</code>

<code>inc(</code><code>int</code>

<code>x,</code><code>int</code>

<code>val)</code>

<code>{</code>

<code>    </code><code>while</code>

<code>(x &lt;= maxn){</code>

<code>        </code><code>bit[x] += val;</code>

<code>        </code><code>x += x&amp;(-x);</code>

<code>    </code><code>}</code>

<code>}</code>

<code>query(</code><code>int</code>

<code>x)</code>

<code>    </code><code>int</code>

<code>ret = 0;</code>

<code>(x &gt; 0){</code>

<code>        </code><code>ret += bit[x];</code>

<code>        </code><code>x -= x&amp;(-x);</code>

<code>    </code><code>return</code>

<code>ret;</code>

<code>hot[10050];</code>

<code>dis[10050];</code>

<code>pre[10050];</code>

<code>post[10050];</code>

<code>cnt[10050];</code>

<code>map&lt;</code><code>int</code><code>,</code><code>int</code><code>&gt; mm;</code>

<code>n,m;</code>

<code>main()</code>

<code>T; cin &gt;&gt; T;</code><code>int</code>

<code>ca = 0;</code>

<code>(T--)</code>

<code>    </code><code>{</code>

<code>        </code><code>memset</code><code>(cnt, 0,</code><code>sizeof</code><code>(cnt));</code>

<code>        </code><code>memset</code><code>(pre, -1,</code><code>sizeof</code><code>(pre));</code>

<code>        </code><code>memset</code><code>(post, -1,</code><code>sizeof</code><code>(post));</code>

<code>        </code><code>mm.clear();</code>

<code>        </code><code>memset</code><code>(bit, 0,</code><code>sizeof</code><code>(bit));</code>

<code>        </code><code>scanf</code><code>(</code><code>"%d"</code><code>, &amp;n);</code>

<code>        </code><code>for</code>

<code>(</code><code>int</code> <code>i = 1; i &lt;= n; i++){</code>

<code>            </code><code>scanf</code><code>(</code><code>"%d%d"</code><code>, dis + i, hot + i);</code>

<code>            </code><code>mm[dis[i]] = i;</code>

<code>        </code><code>}</code>

<code>        </code><code>int</code>

<code>mark = -1;</code>

<code>            </code><code>if</code>

<code>(hot[i] == 0){</code>

<code>                </code><code>pre[i] = mark;</code>

<code>            </code><code>}</code>

<code>            </code><code>else</code><code>{</code>

<code>                </code><code>mark = i;</code>

<code>        </code><code>mark = -1;</code>

<code>(</code><code>int</code> <code>i = n; i &gt;= 1; i--){</code>

<code>                </code><code>post[i] = mark;</code>

<code>                </code><code>int</code>

<code>dpre =imp , dpost = imp2;</code>

<code>                </code><code>if</code>

<code>(pre[i] != -1) dpre =</code><code>abs</code><code>(dis[pre[i]] - dis[i]);</code>

<code>(post[i] != -1) dpost =</code><code>abs</code><code>(dis[post[i]] - dis[i]);</code>

<code>(dpre == dpost) {</code>

<code>                    </code><code>inc(max(hot[pre[i]], hot[post[i]]), 1);</code>

<code>                    </code><code>hot[i] = max(hot[pre[i]], hot[post[i]]);</code>

<code>                </code><code>}</code>

<code>                </code><code>else</code><code>{</code>

<code>                    </code><code>if</code>

<code>(dpre &gt;= imp &amp;&amp; dpost &gt;= imp){</code>

<code>                        </code><code>inc(0, 1);</code><code>continue</code><code>;</code>

<code>                    </code><code>}</code>

<code>(dpre &lt; dpost){</code>

<code>                        </code><code>cnt[pre[i]]++;</code>

<code>                        </code><code>inc(hot[pre[i]], 1);</code>

<code>                    </code><code>else</code><code>{</code>

<code>                        </code><code>cnt[post[i]]++;</code>

<code>                        </code><code>inc(hot[post[i]], 1);</code>

<code>                </code><code>inc(hot[i], 1);</code>

<code>                </code><code>cnt[i]++;</code>

<code>        </code><code>scanf</code><code>(</code><code>"%d"</code><code>, &amp;m);</code>

<code>        </code><code>printf</code><code>(</code><code>"Case #%d:\n"</code><code>, ++ca);</code>

<code>        </code><code>char</code>

<code>s[5];</code><code>int</code>

<code>lk, vk;</code>

<code>(</code><code>int</code> <code>i = 0; i &lt; m; i++){</code>

<code>            </code><code>scanf</code><code>(</code><code>"%s"</code><code>, s);</code>

<code>(s[0] ==</code><code>‘Q‘</code><code>){</code>

<code>                </code><code>scanf</code><code>(</code><code>"%d"</code><code>, &amp;lk);</code>

<code>                </code><code>printf</code><code>(</code><code>"%d\n"</code><code>, query(lk));</code>

<code>                </code><code>scanf</code><code>(</code><code>"%d%d"</code><code>, &amp;lk, &amp;vk); ++lk;</code>

<code>                </code><code>inc(hot[lk], -cnt[lk]);</code>

<code>                </code><code>hot[lk] = vk;</code>

<code>                </code><code>inc(hot[lk], cnt[lk]);</code>

<code>(post[lk] != -1 &amp;&amp; !((dis[lk] + dis[post[lk]]) &amp; 1)){</code>

<code>                    </code><code>int</code>

<code>d = (dis[lk] + dis[post[lk]]) / 2;</code>

<code>(mm.count(d)){</code>

<code>                        </code><code>int</code>

<code>id = mm[d];</code>

<code>                        </code><code>inc(hot[id], -1);</code>

<code>                        </code><code>hot[id] = max(hot[pre[id]], hot[post[id]]);</code>

<code>                        </code><code>inc(hot[id], 1);</code>

<code>(pre[lk] != -1 &amp;&amp; !((dis[lk] + dis[pre[lk]]) &amp; 1)){</code>

<code>d = (dis[lk] + dis[pre[lk]]) / 2;</code>

<code>0;</code>

<code>//HDU4832&lt;br&gt;#pragma warning(disable:4996)</code>

<code>#define maxn 1200</code>

<code>#define mod 9999991</code>

<code>dp1[maxn][maxn];</code>

<code>dp2[maxn][maxn];</code>

<code>row[maxn];</code>

<code>col[maxn];</code>

<code>c[maxn][maxn];</code>

<code>n, m, k, x, y;</code>

<code>    </code><code>c[1][0] = c[1][1] = 1;</code>

<code>    </code><code>for</code>

<code>(</code><code>int</code> <code>i = 2; i &lt;= maxn-1; i++){</code>

<code>(</code><code>int</code> <code>j = 0; j &lt;= i; j++){</code>

<code>            </code><code>c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;</code>

<code>        </code><code>scanf</code><code>(</code><code>"%d%d%d%d%d"</code><code>, &amp;n, &amp;m, &amp;k, &amp;x, &amp;y);</code>

<code>        </code><code>memset</code><code>(dp1, 0,</code><code>sizeof</code><code>(dp1));</code>

<code>        </code><code>memset</code><code>(dp2, 0,</code><code>sizeof</code><code>(dp2));</code>

<code>        </code><code>memset</code><code>(row, 0,</code><code>sizeof</code><code>(row));</code>

<code>        </code><code>memset</code><code>(col, 0,</code><code>sizeof</code><code>(col));</code>

<code>        </code><code>dp1[0][x] = 1;</code>

<code>(</code><code>int</code> <code>i = 1; i &lt;= k; i++){</code>

<code>            </code><code>for</code>

<code>(</code><code>int</code> <code>j = 1; j &lt;= n; j++){</code>

<code>(j - 2 &gt;= 0) dp1[i][j] = (dp1[i][j] + dp1[i - 1][j - 2]) % mod;</code>

<code>                </code><code>(dp1[i][j] += ((dp1[i - 1][j - 1] + dp1[i - 1][j + 1]) % mod + dp1[i - 1][j + 2]) % mod) %= mod;</code>

<code>        </code><code>dp2[0][y] = 1;</code>

<code>(</code><code>int</code> <code>j = 1; j &lt;= m; j++){</code>

<code>(j - 2 &gt;= 0) dp2[i][j] = (dp2[i][j] + dp2[i - 1][j - 2]) % mod;</code>

<code>                </code><code>(dp2[i][j] += ((dp2[i - 1][j - 1] + dp2[i - 1][j + 1]) % mod + dp2[i - 1][j + 2]) % mod) %= mod;</code>

<code>(</code><code>int</code> <code>i = 0; i &lt;= k; i++){</code>

<code>                </code><code>row[i] = (row[i] + dp1[i][j]) % mod;</code>

<code>                </code><code>col[i] = (col[i] + dp2[i][j]) % mod;</code>

<code>        </code><code>ll ans = 0;</code>

<code>            </code><code>ans = (ans + (ll)row[i] * col[k - i] % mod*c[k][i]%mod) % mod;</code>

<code>        </code><code>printf</code><code>(</code><code>"%I64d\n"</code><code>, ans);</code>

<code>//HDU4834&lt;br&gt;#pragma warning(disable:4996)</code>

<code>#define N 10000050</code>

<code>prime[N], p;</code>

<code>cnt[N];</code>

<code>divv[N];</code>

<code>odd[N];</code>

<code>bool</code>

<code>iscomp[N];</code>

<code>getCount()</code>

<code>(</code><code>int</code> <code>i = 2; i&lt;N; i++)</code>

<code>        </code><code>if</code>

<code>(iscomp[i] ==</code><code>false</code><code>)</code>

<code>        </code><code>{</code>

<code>            </code><code>prime[p++] = i;</code>

<code>            </code><code>cnt[i] = 1;</code>

<code>            </code><code>divv[i] = 2;</code>

<code>(</code><code>int</code> <code>j = 0; j &lt; p&amp;&amp;i*prime[j] &lt; N; j++)</code>

<code>            </code><code>iscomp[i*prime[j]] =</code><code>true</code><code>;</code>

<code>(i%prime[j] == 0)</code>

<code>            </code><code>{</code>

<code>                </code><code>divv[i*prime[j]] = divv[i] / (cnt[i] + 1)*(cnt[i] + 2);</code>

<code>                </code><code>cnt[i*prime[j]] = cnt[i] + 1;</code>

<code>                </code><code>break</code><code>;</code>

<code>            </code><code>else</code>

<code>                </code><code>cnt[i*prime[j]] = 1;</code>

<code>                </code><code>divv[i*prime[j]] = divv[i] * divv[prime[j]];</code>

<code>    </code><code>divv[1] = 1;</code>

<code>a[N];</code>

<code>ll ans[N];</code>

<code>    </code><code>getCount();</code>

<code>(</code><code>int</code> <code>i = 1; i &lt; N; i++){</code>

<code>num = 0;</code><code>int</code>

<code>tmp = i;</code>

<code>        </code><code>while</code>

<code>(tmp % 2 == 0){</code>

<code>            </code><code>tmp &gt;&gt;= 1; num++;</code>

<code>        </code><code>odd[i] = divv[i] / (num + 1);</code>

<code>        </code><code>a[i] = a[i - 1] + odd[i];</code>

<code>    </code><code>ll sum = 0;</code>

<code>        </code><code>ans[i] = 1 + i + sum;</code>

<code>        </code><code>sum += a[i];</code>

<code>x;</code>

<code>(T--){</code>

<code>        </code><code>scanf</code><code>(</code><code>"%d"</code><code>, &amp;x);</code>

<code>        </code><code>printf</code><code>(</code><code>"%I64d\n"</code><code>, ans[x]);</code>