## 2016年3月20日 星期日

### [公告]code風景區暫緩更新 (本文將持續更新直到資奧結束)

【IOI2016結束，本文到此為止
「鑽礦遊戲Digging Game 3」請期待～XD】

2016/8/16

2016/8/12

2016/8/11

2016/4/27

http://toi.csie.ntnu.edu.tw/news_show.php?ID=92

2016/4/24

2016/4/17

2016/3/28

2016/3/20

Surprise!!!

## 2016年3月12日 星期六

### [CodeChef XORSACK]Hououin Kyouma and Xorsack

The problem source is not easy to find, so the problem link is provided.

Definitions:
"A number set" is a set of numbers, "Number sets" means a lot of sets of numbers
"$bit_{i}$" is the $i$-th $bit$ of a number or $\oplus($elements of a number set$)$ ($\oplus$ is the sign of $XOR$)
"$X_{i}$" is number $X$'s $bit_{i}$ ($X$'s $i$-th $bit$)

One $bit$ by one $bit$, we can try maintain the number sets satisfy current conditions.

But the number of number sets is too large ($2^N$)!
What can we do?
It doesn't matter, we can save these $N$ numbers. (call it $s$, $s$ can represent all $2^N$ number sets)
At least later we still can get all the number sets, by enumerate "to choose or not to choose"(call it "choosing state") of each elements of $s$.

The first step is maintain all the number sets, whose $bit_{1}=K_{1}$.

Suppose that $K_{1}=0$
We can know, whether we choose each number (in $s$), whose $bit_{1}=0$, does not matter.
The key point is, how to pick up all the number sets, which has even number of elements satisfy $bit_{1}=1$. ($bit_{1}$ of all the number sets would $=0$ only if we do this)
Consider all elements (in $s$), whose $bit_{1}=1$, $v_{1},v_{2},v_{3},...,v_{n}$
We can prove that $s'=\{v_{1}\oplus v_{2},v_{2}\oplus v_{3},v_{3}\oplus v_{4},...,v_{n-1}\oplus v_{n}\}$ can exactly represent all number sets that contain even number of elements, whose $bit_{1}=1$ (Why? Maybe you could figure out by yourself :))

So, what we should do is replace $s$ with $\{{elements\ (in\ original\ s),\ whose\ bit_{1}=0},s'\}$
Then, we can continue to maintain all the number sets, satisfy $(bit_{i}=K_{i},\forall 1\leq i\leq 2)$, $(bit_{i}=K_{i},\forall 1\leq i\leq 3)$..., and so on!

What if $K_{1}=1$?
We can know, whether we choose each number (in $s$), whose $bit_{1}=0$, does not matter.
The key point is, how to pick up all the number sets, which has odd number of elements satisfy $bit_{1}=1$. ($bit_{1}$ of all the number sets would $=1$ only if we do this)
Consider all elements (in $s$), whose $bit_{1}=1$, $v_{1},v_{2},v_{3},...,v_{n}$
We just know that $s'=\{v_{1}\oplus v_{2},v_{2}\oplus v_{3},v_{3}\oplus v_{4},...,v_{n-1}\oplus v_{n}\}$ can exactly represent all number sets that contain even number of elements, whose $bit_{1}=1$
Why not make each number sets, which originally doesn't contain $v_{1}$, contains $v_{1}$,
and make each number sets, which originally contains $v_{1}$, does not contains $v_{1}$?

Therefore, what should we do was just replace $s$ with $\{\{$elements (in original $s$), whose $bit_{1}=0\},s'$ after modify its $v_{1}$'s choosing state$\}$
Then, we can continue to maintain all the number sets, satisfy $(bit_{i}=K_{i},\forall 1\leq i\leq 2)$, $(bit_{i}=K_{i},\forall 1\leq i\leq 3)$..., and so on!

The problem is, how to modify all number sets' $v_{1}$'s choosing state in $s'$?
We can know that choosing the same number twice, has the effect equals to not to choose the number.
Therefore, we just force it to choose an extra number, $v_{1}$.
For implementation, just let $K\oplus v_{1}$! (But I use another variable, $now$, to represent the changes of $K$)

The answer is $No$ if $v_{1}$ does not exist when we need it.
Or there's nothing going wrong until the last $bit$ is considered (That means there are still number sets satisfy the conditions), the answer is $Yes$

Time complexity: $O(31N)$ (My code enumerates $31$ $bit$s)

code:

### [CodeChef XORSACK]Hououin Kyouma and Xorsack

English version

$bit_{i}$為某數字或某數字集合$\oplus$起來的數字，它的第$i$個$bit$ ($\oplus$為$XOR$的符號)
$X_{i}$為數字$X$的$bit_{i}$

code:

### [Codeforces 631E]Product Sum

Definitions:
$SUM[i]=\sum_{k=1}^{i}A_{k}$

For each element, $A_{i}$, how does the characteristic of the array change if we move $A_{i}$ to position $j$?
It changes $A_{i}(j-i)+SUM[i]-SUM[j]$!

Enumerate $i$ and $j$, we get an $O(N^{2})$ solution.
How to speed up?

Treat $j$ as coordinate $x$.
Then we can treat $SUM[j]$ as a function $f(x)$, $A_{i}*j+SUM[i]-A_{i}*i$ as a line $ax+b$ ($a=A_{i},b=SUM[i]-A_{i}*i$)

What we should find is $\max\{(ax+b)-f(x)\}$, where $f(x)$ is a fixed function, $ax+b$ is a line depend on which $A_{i}$ we choose.

Now we have a new way to enumerate: $x$
Enumerate $x$, and find the line whose $ax+b$ is maximum.
Actually, we can use $deque$ to maintain the $convex\ hull$ of these lines.
For each $x$, we just find the corresponding point on the $convex\ hull$, $(x,y)$, $y$ is what we want to get (maximum $ax+b$).

On this picture, black straight lines are $ax+b$ we want to pick to form the $convex\ hull$, the green one.

How to build the $convex\ null$?
Well, this is a long story... Learn it!
(keywords: $monotone\ queue$,$slope\ optimization$)
(hints: sort the lines by their slopes, $a$)

By enumerating $x$ in increasing order, we can reach linear time complexity with the help of monotonicity of $x$, get the maximum $ax+b$ for every $x$.
Update maximum $ax+b-SUM[x]$, this is how much we can increase the characteristic of the array.
Initial characteristic of the array is $\sum_{i=1}^{N}A_{i}*i$

Time complexity：$O(N\log N)$ (remember that $sorting$ was required)

p.s. Actually, we can avoid $sorting$ to reach $O(N)$, that is, only allow element move toward one direction, then these $ax+b$ become rays (instead of lines), enumerate $x$ in that directions, and dynamic maintain the $convex\ hull$. Please remenber that it's required to do the same thing on another direction.
p.s. For $O(N)$ implementation, you can see this.

code:

## 2016年3月10日 星期四

### [Codeforces g100520F][ASC 45]Flights

$SUM[i]$為城市$i$連出去的道路數字總和

code:

### [TIOJ 1692]Problem B 道路巡邏問題 [Interactive]

(圖有沒有連通甚麼的請自行考慮～～～)

CBD提供了另外一個做法

code:

### [Codeforces 651E]Table Compression

For simplicity, let's assume all values are different.
For each row, we can connect edges from cells of larger values to cells of smaller values.
Considering time and memory usage, we only add edges between cells of adjacent values. (So $sorting$ is required)
For each column, we do the same thing.

Therefore, we get a $DAG$ ($Directed\ Acyclic\ Graph$), whose root is the cell of the largest value.
Each cell becomes a node in the graph.
We can know that if there is an edge from $a$ to $b$, the value of $a$ must be larger than $b$
So, the low bound of maximum number in the compressed table is the height of the whole graph.
How to reassign values of each cell?
Let's reassign each cell's (Call the cell $u$) value to the height of the subgraph, whose root is $u$.
Now that the low bound is reached.

How to calculate the height of a subgraph?
Let $DP[u]$ be the height of the subgraph, whose root is $u$.
Then we can conclude the following recursive formula:
$DP[u]=\max(DP[v]+1,v$ is a child node of $u)$
Specially, if $u$ has no child node, $DP[u]=1$
$Memorized\ Search$ can be used to obtain amortized time complexity $O(1)$.

Now it's possible to have pairs of cells of same values.
We can know:
If two cells of same value are on the same horizontal position, or same vertical position
After compression, both cells' values should still be the same.
So we can treat both cells as one single cell. (A single node in the graph)
$Disjoint\ Sets$ can be used to perform the implementation.

Time complexity：$O(NM(\log M+\log N))$ ($sorting$ of $N$ rows and $M$ columns)

code:

## 2016年3月9日 星期三

### [POI 11 Stage 2]The Tournament

1. 當冠軍，從$set$中移除並加入$queue$
2. 被壓倒性勝利惹QAQ，繼續待在$set$裡面

code:

## 2016年3月8日 星期二

code:

### [Codeforces g100016B]Command Post (中文：圈地問題)

$G[i]$為編號$i$的觀察站位置所在的角度 (參見原題定義)

$DP[n][i]$代表在觀察站位置$1\sim i$選$n$個蓋觀察站 (有個限制是觀察站$i$一定要蓋)，對圓心而言所能覆蓋的最大面積 (就是兩兩點間的弦+它們的兩條半徑形成的很多三角形的面積的總和)

$DP[n][i]=\max_{j=0}^{i-1}(DP[n-1][j]+\frac{\sin(G[i]-G[j])}{2},G[i]-G[j]\leq\pi)$

$DP[0][0]=0$

......

p.s.你以為這麼容易嗎？XD
p.s.這份code會MLE (還沒結束?!)，我們必須有效利用未使用的儲存空間，將記憶體用量減為$\frac{1}{4}$

code:

### [Codeforces g100016B]Command Post (中文：圈地問題) (性質證明)

$DP[j]+a+b-d-g\geq DP[i]$
$DP[i]\geq DP[j]+b+e+f-g$

$\Rightarrow DP[j]+a+b-d-g\geq DP[j]+b+e+f-g$
$\Rightarrow a-d\geq e+f$
$\Rightarrow a\geq d+e+f$

$j_{k}$不可能$>j_{k+1}$

### [BZOJ 1096][ZJOI2007]仓库建设

$DP[i]=\min(DP[j]+\sum_{k=j+1}^{i}(P_{k}(X_{i}-X_{k}))+C_{i},0\leq j<i)$

$PROD[i]=\sum_{k=1}^{i}P_{k}$
$COST[i]=\sum_{k=1}^{i}(P_{k}(X_{N}-X{k}))$

$DP[i]=\min(DP[j]+(COST[i]-COST[j])-(PROD[i]-PROD[j])(X_{N}-X_{i}),0\leq j<i)$

$DP[i]=\min(-PROD[j]X_{i}+DP[j]-COST[j]+PROD[j]X_{N}+COST[i]-PROD[i]X_{N}+PROD[i]X_{i},0\leq j<i)$

$a=-PROD[j]$
$b=DP[j]-COST[j]+PROD[j]X_{N}$
$c=COST[i]-PROD[i]X_{N}+PROD[i]X_{i}$
$x=X_{i}$

code:

## 2016年3月7日 星期一

### [UVa 11802]All Your Bases Belong to Us

$N!$分解後變成$2^{q_{1}}*3^{q_{2}}*5^{q_{3}}*7^{q_{4}}*...$
(每個$q_{i}$可在$O(\log N)$的時間內算出來)

code:
#include<cstdio>
#include<cassert>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;
const LL MOD=1e9+7;
LL N,K;
vector<LL>P;
int main()
{
//    freopen("in.txt","r",stdin);
P.push_back(2LL),P.push_back(3LL);
for(int i=2,j;;i++)
{
P.push_back(P[i-1]);
do
{
P[i]+=2LL;
for(j=0;P[j]*P[j]<=P[i]&&P[i]%P[j]!=0LL;j++);
}while(P[i]%P[j]==0LL);
if(P[i]>=500LL)break;
}
//    printf("%d\n",(int)P.size());
//    for(const LL &v:P)printf("%lld\n",v);
int testcount;scanf("%d",&testcount);
while(testcount--)
{
scanf("%lld%lld",&N,&K);
LL ans1=1LL,ans2=1LL;
for(int i=0;;i++)
{
assert(i<(int)P.size());
LL power=0LL;
{LL n=N;while(n)(power+=(n/=P[i]));}
const LL &up=power/K,&down=power/(K+1LL);
if(up==0LL)break;
(ans1*=(up+1LL))%=MOD;
(ans2*=(down+1LL))%=MOD;
}
static int kase=1;
printf("Case %d: %lld\n",kase++,(ans1-ans2+MOD)%MOD);
}
return 0;
}

## 2016年3月6日 星期日

code:

### [SPOJ COT3]COT3 - Combat on a tree (優化後的code)

$trie$的新節點從動態宣告改成靜態宣告 ($replacement\ new$)

$trie$單字結尾的訊息使用鏈表來儲存，做到$O(1)$合併

code:

### [SPOJ COT3]COT3 - Combat on a tree

$SG\ value$變成$2$了

(之後將通通以這張圖做參考)

$SG(xxx)$為盤面為$xxx$的$SG\ value$

1. 將全部資料$\oplus$一個數字
2. 算出全部資料的$mex$
3. 插入一個數字

$copy-on-write$的二元$trie$，搭配懶惰標記，剛好符合所有需求！

code:

## 2016年3月5日 星期六

### [Codeforces 317D]Game with Powers

$3$的冪次方組成的數字也可以當作獨立的子遊戲
$4$的冪次方就不能了，因為$4$已經被歸類在$2$的冪次方
$5$的冪次方可以
$6$的冪次方也可以
......

$1$自己也是一個獨立的子遊戲，要再把答案$\oplus 1$

code:

（真實事件改編）
（N<=50，M<=50）

code:

code:

## 2016年3月4日 星期五

### [HDU 4787]GRE Words Revenge

1. 學一個單字
2. 讀一篇文章，問你有幾個子字串是背過的單字 (只要位置或長度不同就是不同的子字串)

「沿著失配邊可以走到的單字結尾數量」相當於樹壓平序列上對應點的值，可以使用線段樹的單點查詢

$BIT$ ($Binary\ Indexed\ Tree$) 套$AC$自動機

code:

code:

code:

### [公告]code風景區瀏覽量破五千囉！

Email：fsps60312@yahoo.com.tw

## 2016年3月3日 星期四

### [Codeforces 547E]Mike and Friends

$phone[i]$為第$i$隻熊的電話代表的字串

$Tags$：
$_{tag\ 1}$：將每隻熊的電話號碼由長到短排序，$height$由大到小排序，然後就可以在$x$遞減的情況下，利用$disjoint\ sets$維護$height$上高度$\geq x$的連通塊，當$x$等於第$k$熊的電話號碼長度時，就可以直接利用$disjoint\ sets$求出所在連通塊的左界和右界，也就是$height$陣列中連續高度$\geq \left|phone[k]\right|$的區間

code:

code:

## 2016年3月1日 星期二

### [Codeforces 163E]e-Government

1. 將$A_{i}$從集合中移除
2. 將$A_{i}$加回集合中
3. 給你字串$S$，問你$S$中可以數出幾個$\{A_{i}\}$的元素？

code: