## 2016年1月31日 星期日

### [SPOJ MATGAME]MATGAME - Matrix Game

$SG(M)=A_{M}$(代表一個經典的$Nim$遊戲)
$if\ A_{i}\leq SG(i+1)$，$SG(i)=A_{i}-1$
$else$，$SG(i)=A_{i}$
(也是一個$Nim$遊戲，只是0顆石頭時的$SG$函數是$SG(i+1)$，不是0)

code:

### [IOI Camp Judge 41]農田分配

IOI Camp Judge是暫時性的，因此我做了題目備份

1. 枚舉$q$個操作，$O(\log n)$更新每位助手的分數
2. 枚舉$n$位助手，$O(\log q)$求出這位助手的得分

yee~~~，所以$_{註2}$線段樹是用來詢問和維護，所有右界在$[l,r]$的加分操作的分數總合

code:

code:

## 2016年1月29日 星期五

code:

### [Codeforces Beta Round #23]E. Tree

$DP_{0}[u]$：所有連接$u$的邊都必須刪除
$DP_{1}[u]$：如果$u$和子節點$v$之間的邊沒有刪除，那麼$v$的其他邊都要刪除，且$u$的$size$要當作$2$(用來方便計算$DP_{2}$)
$DP_{2}[u]$：沒有限制，所以本題答案為$DP_{2}[0]$(如果根節點為$0$的話)

$DP_{0}[u]$：$\sum_{all\ i}DP_{2}[v_{i}]$
$DP_{1}[u]$：枚舉要連邊的子節點集合$s$，$\max_{all\ s}((\prod_{all\ i}i\in s?DP_{0}[v_{i}]:DP_{2}[v_{i}])*(s.size()+2))$，可以用貪心法將子樹依據$\frac{DP_{0}[v_{i}]}{DP_{1}[v_{i}]}$排序，然後取$\max_{k=0}^{sz}(\prod_{i=1}^{k}DP_{0}[v_{i}])*(\prod_{i=k+1}^{sz}DP_{1}[v_{i}])*(k+2)$，預處理前綴後綴乘積可做到$O(sz\log sz)$，注意這裡要將$u$的$size$當作$2$，也就是上述式子$+2$的由來
$DP_{2}[u]$：$max\{DP_{0}[u],u的size是1時的DP_{1}[u],\max_{all\ i}\frac{(\prod_{all\ j}DP_{2}[v_{j}])*DP_{1}[v_{i}]}{DP_{2}[v_{i}]}\}$

code:

## 2016年1月27日 星期三

### [IOI Camp Judge]D. 串珠吊飾

IOI Camp Judge是暫時性的，因此我做了題目備份

1. $(i,i+\frac{N}{2}), 0\leq i<\frac{N}{2}$(同向匹配)
2. $(i,3N-1-i+1),0\leq i<N$(反向匹配)

p.s.如果你還有良心的話，不要直接複製貼上我的code哦～

code:

### [IOI Camp Judge]C. 區間最大連續和

IOI Camp Judge是暫時性的，因此我做了題目備份

1. 基本的size ($sz$)、priority ($pri$)、value ($v$)
2. 區間總和($sum$)、最長前綴和($lmx$)、最長後綴和($rmx$)、最長區間和($mmx$)，其中$lmx$、$rmx$、$mmx$都必須包含至少一個元素

$tag$代表是否將這個節點的整顆子樹修改為這個節點的$v$

code說得最清楚，請參閱：

p.s.如果你還有良心的話，不要直接複製貼上我的code哦～

code:

### [Codeforces 449D]D. Jzzhu and Numbers

$DP[0][s]$可以直接算

code:

## 2016年1月26日 星期二

### [教學]Windows 10的螢幕亮度無法調整了怎麼辦？

Win10會強制使用者安裝最新的更新，包括驅動程式，而最近有一種叫做「PnP-Monitor(Standard) (PnP監視器 (標準) )」的驅動程式，無緣無故被當作更新裝上來了！在這個驅動程式下，螢幕好像變成不支援亮度調節的樣子Orz

### [Codeforces 448E]Divisors

1. 如果$K>10^{5}$，直接輸出$10^{5}$個$1$，除非$X=1$
2. 如果在任何一層$X=1$，就直接輸出$1$，以防重複遞迴導致TLE
3. 將因數分解的結果記錄下來(可以用vector紀錄因數存在map裡面)，以防超大質數的重複因數分解

code:

code:

### [UVa 11895]Honorary Tickets

We can use priority_queue to maintain the current best choice
A state contains following information:
1. The expect value of number of lucky tickets (I use a pair of long long, $(u,d)$, to represent a fraction)
2. The total number of envelops (called $c$ later)

The possibility of getting from a bag is $\frac{\frac{u}{d}}{c}$, i.e. $\frac{u}{dc}$

Total time complexity: $O(K\log N)$

code:

## 2016年1月25日 星期一

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

 code風景區瀏覽量破千截圖
感謝大家的支持，讓code風景區自1/7開站以來瀏覽量首度破千！
為了讓以後的文章更好，有任何改善建議請隨時留言或寄信給小莫，小莫會盡量在短時間內立即回覆並試用！
也歡迎各位已經寫過相似性質blog的朋友們來信或留言，我們互相加友情連結吧～^_^

Email：fsps60312@yahoo.com.tw

### [UVa 12906]Maximum Score

For simplicity, we call the sequence that fit the restriction of $x_{i}$ $S_{i}$.
We can know that the length of $S_{i}$ would not exceed number of $x_{j}$, such that $x_{j}\leq x_{i}$
If we sort the numbers in increasing order, all $S_{i}$ would reach the maximum length!
So we can calculate the first answer according to descriptions above.

For the second answer, we know that for each $S_{i}$, all values $<x_{i}$ on the left of $x_{i}$ must form a non-increasing sequence, all values$<x_{i}$ on the right of $x_{i}$ must form a non-decreasing sequence, or $S_{i}$ would not be able to reach the maximum length.
So the optimal permutations are composed of a non-increasing sequence and a non-decreasing sequence.

Let's sort the pairs: $\{(v_{k},f_{k})\}$
The number of such optimal permutations is $\prod_{i=1}^{P-1} (f_{i}+1)$

If you don't know why, let's call the location of maximum values $peak$.
for every $v_{k}$, we have $f_{k}$ of such numbers, we can decide to put $0,1,2,...,f_{k}$ on the left of $peak$ and $f_{k},f_{k}-1,f_{k}-2,...,0$ on the right of $peak$, so there are $f_{k}+1$ ways to assign values of $v_{k}$. Therefore, you know, the number of ways to assign all $v_{k}$ is $\prod_{i=1}^{P-1} (f_{i}+1)$. :)

Total time complexity: $O(P\log P)$

Note:
1. The first answer is no need to modulo $10^{9}+7$.
2. The first answer must be handled with unsigned long long, not long long.

code:

### [ZJ a764]pC. Tony 與只有神知道的世界

p.s.如果狀態用三個int(現在的點、上一個點、走過的距離)存會在最後一筆MLE，我把現在的點和上一個點合起來用一個int存就過了=ㄦ=

code:

### [UVa 12581]Divisibility

Let's try to figure out what's the value of $(x_{1},x_{2},x_{3},...)$.
We can discover that the value is the number of different paths from $(0,0,0,...)$ to $(x_{1},x_{2},x_{3},...)$, one step in the path is defined as increase one of the co-ordinates by one.

So we can know the value of $(x_{1},x_{2},x_{3},...)$ is $\frac{(\sum_{k=1}^{N} x_{k})!}{\prod_{k=1}^{N} (x_{k}!)}$
If you don't know why, image that there are $x_{1}$ $vectors$ of $(1,0,0,...)$, $x_{2}$ $vectors$ of $(0,1,0,...)$, and so on. Therefore, no matter how you permutate them, they always form a path from $(0,0,0,...)$ to $(x_{1},x_{2},x_{3},...)$, the number of such permutations is $\frac{(\sum_{k=1}^{N} x_{k})!}{\prod_{k=1}^{N} (x_{k}!)}$ (Let's call it $M$ later)

The problem is, in which condition $M$ is not divisible by P ?

We can just take only $P$'s multiples into consideration.
The number of factor $P$ in $n!$ is $\left[\frac{n}{P}\right]+\left[\frac{n}{P^{2}}\right]+\left[\frac{n}{P^{3}}\right]+...$
For simplicity, we call the value $f(n)$ (regard $P$ as constant)

Then M is not divisible by P if and only if $f(\sum_{k=1}^{N} x_{k})=\sum_{k=1}^{N} f(x_{k})$
i.e., for every $r\in\mathbb{N}$, $\sum_{k=1}^{N} (x_{k}\mod P^{r})<P^{r}$ must hold.

If we transform every $n$ into $P-dicimal$ numbers, call it $T(n)$, then the above equation holds if and only if $\sum_{k=1}^{N} (k_{th}$ digit of $T(x_{k}))<P$.

So be question becomes, how many set, $(x_{1},x_{2},x_{3},...)$, are there, such that for each $i\in\mathbb{N}$, $\sum_{k=1}^{N} (i_{th}$ digit of $T(x_{k}))<P$ ?

Let's try to design a Dynamic Programming method to get the answer.
Suppose that we can enumerate from high digit to low digit.
A state includes the following information:
1. $i$, represent we are considering the $i_{th}$ digit now.
2. For every $T(x_{k})$, the range of its $(i-1)_{th}$ digit should be.(whether the $(i-1)_{th}$ digit has low bound or up bound)

For example, if the $i_{th}$ digit has a low bound of $a$, a up bound of $b$, the $(i-1)_{th}$ digit has no bounds if the $i_{th}$ digit$\in[a+1,b-1]$, has a low bound if the $i_{th}$ digit is $a$, has a up bound if the $i_{th}$ digit is $b$
Thus, we can update the values by enumerate the subsets of its set of bounds.
It's convenient to use bitmask to represent the sets.
Partial time complexity: $O(3^{2N}\log_{P}\max(x_{k}))$
However, we can optimize it by skipping if the value is 0.

Use another DP to calculate the number of cases, such that $\sum_{k=1}^{N} \{ i_{th}$ digit of $x_{k}$, within the given bound$\}<P$.
Partial time complexity: $O(NP)$.

Total time complexity: $O(3^{2N}NP\log_{P}\max(x_{k}))$.

code:

code:

code:

## 2016年1月21日 星期四

### [UVa 12584]Laptop Chargers

Minimum how many chargers does he need to run all the laptops forever:
We can just sum up each discharge rate of the laptops, and then calculate how many chargers do we need to prevent total charge rate from being lower than the total discharge rate.
Explanation:
If total charge rate $<$ total discharge rate, you'll be sure to run out all your batteries someday.
Otherwise, with very fast charger switching, you can try to keep all your batteries from being lower than original conditions, and even better if possible.
For simplicity, we call the answer $\min M$

Maximum how long will he be able to run all his laptops using $M (M < N)$ chargers?
If $M\geq \min M$, the answer is, of course, $-1.000$.
Otherwise, we can come up with a simple method to get an "answer" first. That is, get total charge remaining in the laptop batteries(We call it $TR$ later), total discharge rate of laptops(We call it $TD$ later), and total charge rate of chargers(We call it $TC$ later)
Then we can get $\frac{TR}{TD-TC}$.
What's the problem if we treat it as the answer?
There exists some cases, such that one of the laptop battery is able to sustain for a very long time, even all other laptops have run out of battery with all chargers working.

So the problem is, which laptops don't need to be charged?
We can sort the laptops by the time they run out of battery without charger. For some $m$ ($m\geq M$), we can try use all chargers to make the first $m$ laptops run as long as possible, and see whether the $(m+1)$-th laptop can sustain until the first $m$ laptops are all run out of battery with all $M$ chargers working.

Find the first $m$ that the $(m+1)$-th laptop can sustain to the last. Then the answer is the time when the first $m$ are out of battery.
Otherwise, if we can't find such $m$, the "fake answer", $\frac{TR}{TD-TC}$, mentioned at first is printed.
Notice that if $TC\geq TD$ or $\frac{TR}{TD-TC}>100000$, you should always print "$-1.000$".

Time complexity: $O(N\log N+QN)$

code:

## 2016年1月20日 星期三

3 3
2 0 2
0 2 0
2 0 2

3 3
2 0 2
0 1 0
2 0 2

3 3
1 1 1
1 0 1
1 1 1

3 3
2 2 2
2 0 2
2 2 2

4 4
2 2 2 2
2 0 0 2
2 0 0 2
2 2 2 2

5 5
2 2 2 2 2
2 0 0 0 2
2 0 0 0 2
2 0 0 0 2
2 2 2 2 2

code:

### [TIOJ 1841][POI 21 Stage 1]好．傳囉！ Nice Boat！

(題號打錯所以只好重發文章@@，順便套用剛學的latex語法)

code:

code:

## 2016年1月18日 星期一

### [UVa 12345]Dynamic len(set(a[L:R]))

A[i]為題目給的陣列

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
struct Query
{
char type;
int x,y;
};
vector<Query>QUERY;
int N,M,A[50000];
{
int querycount;
scanf("%d%d",&N,&querycount);
for(int i=0;i<N;i++)scanf("%d",&A[i]);
QUERY.clear();
while(querycount--)
{
static char type[2];
static Query q;
scanf("%s%d%d",type,&q.x,&q.y);
q.type=type[0];
QUERY.push_back(q);
}
}
void Discretize()
{
vector<int>v;
for(int i=0;i<N;i++)v.push_back(A[i]);
for(const Query &q:QUERY)if(q.type=='M')v.push_back(q.y);
sort(v.begin(),v.end()),v.resize(unique(v.begin(),v.end())-v.begin());
M=v.size();
for(int i=0;i<N;i++)A[i]=lower_bound(v.begin(),v.end(),A[i])-v.begin();
for(Query &q:QUERY)
{
if(q.type=='M')q.y=lower_bound(v.begin(),v.end(),q.y)-v.begin();
else q.y--;
}
v.clear(),vector<int>().swap(v);
}
struct Node
{
Node *l,*r;
const int loc;
Node(const int _loc):l(NULL),r(NULL),loc(_loc){}
};
void Insert(vector<int>&s,const int v)
{
const int sz=s.size();
auto it=lower_bound(s.begin(),s.end(),v);
assert(it==s.end()||v<=(*it));
if(it!=s.begin())assert((*--it)<v),it++;
s.insert(it,v);
assert((int)s.size()==sz+1);
}
void Erase(vector<int>&s,const int v)
{
const int sz=s.size();
auto it=lower_bound(s.begin(),s.end(),v);
assert(it!=s.end()&&(*it)==v),s.erase(it);
assert((int)s.size()==sz-1);
}
Node *S[50000],*BEGIN[100000],*END[100000];
set<int>LOCS[100000];
vector<int>LEFT[224];
int GAP;
void Insert(Node* &l,Node* &o,Node* &r)
{
assert(l->r==r&&r->l==l);
if((r->loc)<N)Erase(LEFT[(r->loc)/GAP],l->loc),Insert(LEFT[(r->loc)/GAP],o->loc);
Insert(LEFT[(o->loc)/GAP],l->loc);
l->r=o,o->r=r;
r->l=o,o->l=l;
}
void Extract(Node* &o)
{
Node *l=o->l,*r=o->r;
if((r->loc<N))Erase(LEFT[(r->loc)/GAP],o->loc),Insert(LEFT[(r->loc)/GAP],l->loc);
Erase(LEFT[(o->loc)/GAP],l->loc);
l->r=r,r->l=l;
o->l=o->r=NULL;
}
void PreProcess()
{
assert(M<=100000);
Node **pre=new Node*[M];
for(int i=0;i<M;i++)
{
pre[i]=BEGIN[i]=new Node(-1),END[i]=new Node(N);
BEGIN[i]->r=END[i],END[i]->l=BEGIN[i];
LOCS[i].clear();
}
GAP=min(N,(int)sqrt(N)+1);
for(int i=0;i<=(N-1)/GAP;i++)LEFT[i].clear();
for(int i=0;i<N;i++)
{
const int v=A[i];
LOCS[v].insert(i);
Insert(pre[v],S[i]=new Node(i),END[v]),pre[v]=S[i];
}
delete[]pre;
}
int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
Discretize();
PreProcess();
for(const Query &q:QUERY)
{
if(q.type=='M')
{
Node* &o=S[q.x];
Extract(o);
LOCS[A[q.x]].erase(q.x);
auto itr=LOCS[q.y].upper_bound(q.x),itl=itr;
Insert(itl==LOCS[q.y].begin()?BEGIN[q.y]:S[*--itl],o,itr==LOCS[q.y].end()?END[q.y]:S[*itr]);
//            printf("%d-(%d,%d)-%d\n",o->l->loc,o->loc,q.y,o->r->loc);
LOCS[q.y].insert(q.x);
A[q.x]=q.y;
}
else if(q.type=='Q')
{
const int l=(q.x+GAP-1)/GAP,r=(q.y+1)/GAP-1;
assert((l-1)*GAP<q.x&&q.x<=l*GAP);
assert((r+1)*GAP-1<=q.y&&q.y<(r+2)*GAP-1);
int ans=0;
for(int i=l;i<=r;i++)
{
const vector<int>&s=LEFT[i];
ans+=lower_bound(s.begin(),s.end(),q.x)-s.begin();
}
if(q.x/GAP==q.y/GAP)
{
for(int i=q.x;i<=q.y;i++)if((S[i]->l->loc)<q.x)ans++;
}
else
{
for(int i=q.x;i<l*GAP;i++)if((S[i]->l->loc)<q.x)ans++;
for(int i=q.y;i>=(r+1)*GAP;i--)if((S[i]->l->loc)<q.x)ans++;
}
printf("%d\n",ans);
//            assert(ans==q.y-q.x+1);
}
else assert(0);
//        for(int i=0;i<=(N-1)/GAP;i++)
//        {
//            printf("[%d]:",i);
//            for(const int v:LEFT[i])printf(" %d",v);puts("");
//        }
}
return 0;
}

## 2016年1月17日 星期日

### [HOJ 303]買醬油IV 之 商店問題

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

1. 縮寫「最長嚴格遞增子序列」為LSIS
2. 定義S[i]為第i家商店的醬油價格
3. 定義L[i]為以S[i]為結尾的LSIS長度
4. 定義ANS[i]為以S[i]為結尾的LSIS中花費的最小精力

ps.在我AC這題之後，HOJ馬上就掛了Orz

code:

## 2016年1月16日 星期六

### [HOJ 300][Codechef]Party Invitation

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

DP[u][0]=Pi{DP[v][0]+DP[v][1],v是u的子節點}(Pi是把每個東西乘起來的結果)
DP[u][1]=Pi{DP[v][0],v是u的子節點}

DP[u][l][0]=DP[u-1][l][0]+DP[u-1][l][1]
DP[u][l][1]=DP[u-1][l][0]

TREE[u][c]怎麼算上面說過了XD

DP[u][l][0]=TREE[u][0]*(DP[u-1][l][0]+DP[u-1][l][1])
DP[u][l][1]=TREE[u][1]*DP[u-1][l][0]

code:

### [HOJ 299]比特集合

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

code:

### [HOJ 297][NOIP 2010 提高組]引水入城

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

code:

### [HOJ 294][Codeforces #192]The Evil Temple and the Moving Rocks

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

v.<.<.<.<.<<<<<<<
>>>>>>>.>.>.>.>.^
v.<.<.<.<.<<<<<<<
>>>>>>>.>.>.>.>.^
v.<.<.<.<.<<<<<<<
>>>>>>>.>.>.>.>.^
v.<.<.<.<.<<<<<<<
>>>>>>>.>.>.>.>.^
v.<.<.<.<.<<<<<<<
>>>>>>>.>.>.>.>.^
v.<.<.<.<.<<<<<<<
>>>>>>>.>.>.>.>.^
v.<.<.<.<.<<<<<<<
>>>>>>>.>.>.>.>.^

N=3時，會發出聲響3次
N=5時，會發出聲響6次
N=90時，會發出聲響81044次
N=100時，會發出聲響108949次

code:

### [HOJ 293][Codeforces #192]Graph Reconstruction

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

1. 如果圈的大小是奇數

2. 如果是偶數

(不合法:(1,4),(2,3)，合法:(1,3),(2,4))

(不合法:(2,3)，合法:(1,3),(1,4),(2,4))

(不合法:(1,2),(2,3)，合法:(1,3))

4 3
1 2
2 3
3 4

code:

## 2016年1月15日 星期五

### [HOJ 287][Codeforces #145]Practice

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

(好恐怖><)

code:

### [UVa 12590]Guards II

(Bottom is the English version)

Cover0(N,M,K)：N*M長方形中放K個守衛使得第1行到第M行都有守衛，符合條件的情況數量
Cover1(N,M,K)：和Cover0一樣，只是左上角那個點不能放守衛
Cover2(N,M,K)：和Cover1一樣，只是連右上角也不能放守衛(所以左上角和右上角都不能放)

(English version)

The key point is inclusion-exclusion principle.

Because of the particularity of corner cells (if you place a guard here, he can cover two lines of border) and there are only four such cell, we can enumerate the allocation of corner guards, and then discuss, at what circumstances all border cells can be covered.
Definitions:
Cover0(N,M,K)：place K guards in N*M grid, such that each column from 1-st to M-th has at least one guard. The return value is the number of circumstances that meet the restrictions above.
Cover1(N,M,K)：Same as Cover0, but you can't place a guard at the up-left cell.
Cover2(N,M,K)：Same as Cover1, but you can't place a guard at the up-right cell(So you can place guard in neither up-left cell nor up-right cell).
Time complexities of functions above shouldn't exceed O(max(N,M)).

Case 1：All four corners are empty

First, we can calculate the number of circumstances, such that each of four lines of border has at least one guard, here I use inclusion-exclusion principle.
If there exist a line of border that has no guard, suppose it's down border.
There are still some exceptions that down border can be fully covered.
That is, each column has at least one guard exists.
So the down border is fully covered with human wave tactics.
The number of such exceptions is Cover2(N,M,K).
Notice that this will have duplicates with the exceptions of no guard on the up border, so after adding them together, we must deduct such duplicates.
The number of such duplicates is Cover0(N,M,K).
For another direction, just swap N and M, and handle it the same way.

Case 2: Only one corner has guard

For convenience, we only consider the guard to be placed at up-left corner.
Same as above, we can use inclusion-exclusion principle to get the number of circumstances, such that both down border and right border has at least one guard.
Also, there are exceptions that allow a empty down border.
That is, each column from 2-nd to M-th has at least one guard(Because column 1 already has a guard on the corner).
The number of such exceptions is Cover2(N,M,K)+Cover1(N,M,K).
For another direction, just swap N and M.

Case 3: Two of the adjacent corners has guard

For convenience, we only consider the guard to be placed at up-left corner and up-right corner.
The same, we can use inclusion-exclusion principle to get the number of circumstances, such that down border has at least one guard.
Again, there are exceptions that allow a empty down border.
That is, each column from 2-nd to (M-1)-th has at least one guard.
The number of such exceptions is Cover2(N,M,K)+2*Cover1(N,M,K)+Cover0(N,M,K).
For another direction, just swap N and M.

Case 4: Two of the opposite corners has guard

All border cells are covered even if you haven't placed any on it.
Place guards as you like, the number of circumstances is C(N*M-4,K-2)(Four corners has been decided in advance and need to be excluded, and we've already used two guards).

Case 5: Three of the corners has guard

All border cells are covered even if you haven't placed any on it.
Place guards as you like, the number of circumstances is C(N*M-4,K-3)(Four corners has been decided in advance and need to be excluded, and we've already used three guards).

Case 6: All of the four corners has guard
I don't want to say that again. XD

Cover0, Cover1, Cover2, and C might be calculated many times, so it's recommend to use memorized search to improve performance.

Weight the six numbers above and then plus them together, this should be the answer

Don't forget to module 1000000007 at any time for fear of overflowing~

Time complexity: O(N*M*max(N,M)*K)

code: