好久没打代码啦，今天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
到期末了，不能很舒心的欢乐的打代码了，要准备各科的复习了。。想想就觉得蛋疼。。
贴一下代码。
//HDU4831
#pragma warning(disable:4996)
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std; #define ll long long
#define maxn 100000
#define imp 1000000000
#define imp2 1000000001 int bit[maxn + 50]; void inc(int x, int val)
{
while (x <= maxn){
bit[x] += val;
x += x&(-x);
}
} int query(int x)
{
int ret = 0;
while (x > 0){
ret += bit[x];
x -= x&(-x);
}
return ret;
} int hot[10050];
int dis[10050];
int pre[10050];
int post[10050];
int cnt[10050];
map<int, int> mm; int n,m; int main()
{
int T; cin >> T; int ca = 0;
while (T--)
{
memset(cnt, 0, sizeof(cnt));
memset(pre, -1, sizeof(pre));
memset(post, -1, sizeof(post));
mm.clear();
memset(bit, 0, sizeof(bit));
scanf("%d", &n);
for (int i = 1; i <= n; i++){
scanf("%d%d", dis + i, hot + i);
mm[dis[i]] = i;
}
int mark = -1;
for (int i = 1; i <= n; i++){
if (hot[i] == 0){
pre[i] = mark;
}
else{
pre[i] = mark;
mark = i;
}
}
mark = -1;
for (int i = n; i >= 1; i--){
if (hot[i] == 0){
post[i] = mark;
}
else{
post[i] = mark;
mark = i;
}
}
for (int i = 1; i <= n; i++){
if (hot[i] == 0){
int dpre =imp , dpost = imp2;
if (pre[i] != -1) dpre = abs(dis[pre[i]] - dis[i]);
if (post[i] != -1) dpost = abs(dis[post[i]] - dis[i]);
if (dpre == dpost) {
inc(max(hot[pre[i]], hot[post[i]]), 1);
hot[i] = max(hot[pre[i]], hot[post[i]]);
}
else{
if (dpre >= imp && dpost >= imp){
inc(0, 1); continue;
}
if (dpre < dpost){
cnt[pre[i]]++;
inc(hot[pre[i]], 1);
}
else{
cnt[post[i]]++;
inc(hot[post[i]], 1);
}
}
}
else{
inc(hot[i], 1);
cnt[i]++;
}
}
scanf("%d", &m);
printf("Case #%d:\n", ++ca);
char s[5]; int lk, vk;
for (int i = 0; i < m; i++){
scanf("%s", s);
if (s[0] == 'Q'){
scanf("%d", &lk);
printf("%d\n", query(lk));
}
else{
scanf("%d%d", &lk, &vk); ++lk;
inc(hot[lk], -cnt[lk]);
hot[lk] = vk;
inc(hot[lk], cnt[lk]);
if (post[lk] != -1 && !((dis[lk] + dis[post[lk]]) & 1)){
int d = (dis[lk] + dis[post[lk]]) / 2;
if (mm.count(d)){
int id = mm[d];
inc(hot[id], -1);
hot[id] = max(hot[pre[id]], hot[post[id]]);
inc(hot[id], 1);
}
}
if (pre[lk] != -1 && !((dis[lk] + dis[pre[lk]]) & 1)){
int d = (dis[lk] + dis[pre[lk]]) / 2;
if (mm.count(d)){
int id = mm[d];
inc(hot[id], -1);
hot[id] = max(hot[pre[id]], hot[post[id]]);
inc(hot[id], 1);
}
}
}
}
}
return 0;
}
//HDU4832
#pragma warning(disable:4996)
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std; #define maxn 1200
#define ll long long
#define mod 9999991
using namespace std; int dp1[maxn][maxn];
int dp2[maxn][maxn];
int row[maxn];
int col[maxn];
int c[maxn][maxn]; int n, m, k, x, y; int main()
{
c[1][0] = c[1][1] = 1;
for (int i = 2; i <= maxn-1; i++){
for (int j = 0; j <= i; j++){
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
int T; cin >> T; int ca = 0;
while (T--)
{
scanf("%d%d%d%d%d", &n, &m, &k, &x, &y);
memset(dp1, 0, sizeof(dp1));
memset(dp2, 0, sizeof(dp2));
memset(row, 0, sizeof(row));
memset(col, 0, sizeof(col));
dp1[0][x] = 1;
for (int i = 1; i <= k; i++){
for (int j = 1; j <= n; j++){
if (j - 2 >= 0) dp1[i][j] = (dp1[i][j] + dp1[i - 1][j - 2]) % mod;
(dp1[i][j] += ((dp1[i - 1][j - 1] + dp1[i - 1][j + 1]) % mod + dp1[i - 1][j + 2]) % mod) %= mod;
}
}
dp2[0][y] = 1;
for (int i = 1; i <= k; i++){
for (int j = 1; j <= m; j++){
if (j - 2 >= 0) dp2[i][j] = (dp2[i][j] + dp2[i - 1][j - 2]) % mod;
(dp2[i][j] += ((dp2[i - 1][j - 1] + dp2[i - 1][j + 1]) % mod + dp2[i - 1][j + 2]) % mod) %= mod;
}
}
for (int i = 0; i <= k; i++){
for (int j = 1; j <= n; j++){
row[i] = (row[i] + dp1[i][j]) % mod;
}
}
for (int i = 0; i <= k; i++){
for (int j = 1; j <= m; j++){
col[i] = (col[i] + dp2[i][j]) % mod;
}
}
ll ans = 0;
for (int i = 0; i <= k; i++){
ans = (ans + (ll)row[i] * col[k - i] % mod*c[k][i]%mod) % mod;
}
printf("Case #%d:\n", ++ca);
printf("%I64d\n", ans);
}
return 0;
}
//HDU4834
#pragma warning(disable:4996)
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std; #define N 10000050
#define ll long long
using namespace std; int prime[N], p;
int cnt[N];
int divv[N];
int odd[N];
bool iscomp[N]; void getCount()
{
for (int i = 2; i<N; i++)
{
if (iscomp[i] == false)
{
prime[p++] = i;
cnt[i] = 1;
divv[i] = 2;
}
for (int j = 0; j < p&&i*prime[j] < N; j++)
{
iscomp[i*prime[j]] = true;
if (i%prime[j] == 0)
{
divv[i*prime[j]] = divv[i] / (cnt[i] + 1)*(cnt[i] + 2);
cnt[i*prime[j]] = cnt[i] + 1;
break;
}
else
{
cnt[i*prime[j]] = 1;
divv[i*prime[j]] = divv[i] * divv[prime[j]];
}
}
}
divv[1] = 1;
} int a[N];
ll ans[N]; int main()
{
getCount();
for (int i = 1; i < N; i++){
int num = 0; int tmp = i;
while (tmp % 2 == 0){
tmp >>= 1; num++;
}
odd[i] = divv[i] / (num + 1);
}
for (int i = 1; i < N; i++){
a[i] = a[i - 1] + odd[i];
}
ll sum = 0;
for (int i = 1; i < N; i++){
ans[i] = 1 + i + sum;
sum += a[i];
}
int x;
int T; cin >> T; int ca = 0;
while (T--){
scanf("%d", &x);
printf("Case #%d:\n", ++ca);
printf("%I64d\n", ans[x]);
}
return 0;
}