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>