聽(tīng)說(shuō)有版權(quán)問(wèn)題不能貼題目？。那就只能先忍一忍了。
題目抽象為：我們有一個(gè)由有根樹(shù)構(gòu)成的森林，對(duì)這個(gè)森林進(jìn)行兩種操作：
把某棵子樹(shù)拔下來(lái)接到某一棵樹(shù)（可能還是那個(gè)子樹(shù)原來(lái)所在的樹(shù)）的某個(gè)節(jié)點(diǎn)下面，詢問(wèn)某個(gè)節(jié)點(diǎn)在樹(shù)中的深度。
因?yàn)榘岩豢眠厵?quán)為1的樹(shù)的括號(hào)序列拿出來(lái)，樹(shù)上某兩點(diǎn)的距離就是在括號(hào)序列中兩點(diǎn)間沒(méi)匹配括號(hào)的個(gè)數(shù)（有左括號(hào)右括號(hào)選擇的區(qū)別，具體分析處理）。當(dāng)然，既然是對(duì)一群樹(shù)操作，那就直接用動(dòng)態(tài)樹(shù)就行了。
于是就去學(xué)了動(dòng)態(tài)樹(shù)。發(fā)現(xiàn)其實(shí)不算很難（1.指時(shí)間復(fù)雜度均攤logn的算法，還有基于輕重邊剖分的嚴(yán)格logn的算法 2.如果你對(duì)splay熟的話），寫(xiě)起來(lái)也就基本上就是一棵splay，也算比較好寫(xiě)的。。（以后就告別路徑剖分了。。太麻煩了。。復(fù)雜度也沒(méi)動(dòng)態(tài)樹(shù)好。。）
以下所說(shuō)的動(dòng)態(tài)樹(shù)都是基于splay的時(shí)間復(fù)雜度均攤logn的動(dòng)態(tài)樹(shù)。
動(dòng)態(tài)樹(shù)的主要思想就是：類(lèi)似輕重邊剖分一樣，把整棵樹(shù)劃分成若干實(shí)邊(solid edge)和虛邊(dashed edge)，但這個(gè)都是根據(jù)你的需要來(lái)設(shè)定的，不像輕重邊一樣每個(gè)點(diǎn)往下都必須有一條重邊（單獨(dú)的葉子節(jié)點(diǎn)算長(zhǎng)度為0的重邊），而是每次把你所需要操作的點(diǎn)到根的邊都改為實(shí)邊(expose操作)，且每個(gè)點(diǎn)往下的實(shí)邊數(shù)不超過(guò)1。修改沿途如果有一個(gè)點(diǎn)已經(jīng)有了實(shí)邊邊那么就把它原來(lái)的實(shí)邊改成虛邊。這樣每次對(duì)一個(gè)點(diǎn)操作都是在一條實(shí)路徑上(solid path)。對(duì)于每一條實(shí)路徑，都用一棵splay來(lái)維護(hù)就行了。（splay可以亂轉(zhuǎn)亂拔亂接太爽了。。- -!當(dāng)然是在一定規(guī)則下的亂。。）
/*
* $File: bounce.cpp
* $Date: Fri Jul 09 20:59:27 2010 +0800
* $Author: Tim
* $Solution: Dynamic Tree with Splay Tree implementation
* $Time complexity: O(mlogn) , per operation amorized O(logn);
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#define MAXN 200005
using namespace std;
class SplayNode
{
public:
int fa, lt, rt, size;
};
SplayNode node[MAXN + 1];
// functions below are belong to splay tree
// we can see that, this splay tree is quite
// simple, and just 'splay' function
// and size maintaining supported.
// but that what all we need to
// solve this problem
void Renew(int x)
{
if (!x)
return;
node[x].size = node[node[x].lt].size + node[node[x].rt].size + 1;
}
void RightRotate(int x)
{
int lc = node[x].lt, fa = node[x].fa;
node[x].lt = node[lc].rt; node[node[x].lt].fa = x;
node[lc].rt = x; node[x].fa = lc;
node[lc].fa = fa;
if (x == node[fa].lt)
node[fa].lt = lc;
else
node[fa].rt = lc;
Renew(x);
Renew(lc);
}
void LeftRotate(int x)
{
int rc = node[x].rt, fa = node[x].fa;
node[x].rt = node[rc].lt; node[node[x].rt].fa = x;
node[rc].lt = x; node[x].fa = rc;
node[rc].fa = fa;
if (x == node[fa].lt)
node[fa].lt = rc;
else
node[fa].rt = rc;
Renew(x);
Renew(rc);
}
void splay(int x, int FA = 0)
{
int fa, Fa;
while ((fa = node[x].fa) != FA)
{
if ((Fa = node[fa].fa) == FA)
{
if (x == node[fa].lt)
RightRotate(fa);
else
LeftRotate(fa);
}
else
{
if (x == node[fa].lt)
{
if (fa == node[Fa].lt)
{
RightRotate(Fa);
RightRotate(fa);
}
else
{
RightRotate(fa);
LeftRotate(Fa);
}
}
else
{
if (fa == node[Fa].rt)
{
LeftRotate(Fa);
LeftRotate(fa);
}
else
{
LeftRotate(fa);
RightRotate(Fa);
}
}
}
}
}
// end splay
int root;
int query_rank(int id)
{
splay(id);
return node[node[id].lt].size + 1;
}
int father[MAXN + 1];
int n;
void Init()
{
scanf("%d", &n);
for (int i = 1, k; i <= n; i ++)
{
scanf("%d", &k);
k += i;
if (k > n + 1)
k = n + 1;
father[i] = k;
node[i].size = 1;
}
node[n + 1].size = 1;
}
int split(int id)
// isolate id and the node right after it on the solid path
// and return that node
{
splay(id);
if (node[id].rt)
{
int rc = node[id].rt;
node[id].rt = node[rc].fa = 0;
node[id].size -= node[rc].size;
return rc;
}
else
return 0;
}
void Link(int id, int fa)
// let fa be the father of id,
// we assume that before this,
// id is the head of a solid path,
// and fa is the tail of a solid path,
// this was done by function 'cut' and 'split'
{
splay(id);
assert(!node[id].lt);
splay(fa);
assert(!node[fa].rt);
node[fa].rt = id;
node[fa].size += node[id].size;
node[id].fa = fa;
}
int get_head(int x)
// get the head of the solid path which x is in.
{
while (node[x].fa)
x = node[x].fa;
while (node[x].lt)
x = node[x].lt;
splay(x);
return x;
}
void expose(int id)
// turn the edges between id and the root of the tree id is in
// all into solid edges. with this operation, we can query what
// we want conveniently in a splay tree.
{
while (true)
{
id = get_head(id);
if (!father[id])
break;
split(father[id]);
Link(id, father[id]);
}
}
int query_depth(int id)
{
expose(id);
return query_rank(id) - 1;
}
void cut(int id)
// this function isolated the subtree rooted id
{
expose(id);
split(father[id]);
}
void modify_father(int id, int fa)
{
cut(id);
split(fa);
father[id] = fa;
Link(id, fa);
}
void Solve()
{
int m, cmd, id, k;
scanf("%d", &m);
while (m --)
{
scanf("%d%d", &cmd, &id);
id ++;
if (cmd == 1)
printf("%d\n", query_depth(id));
else
{
scanf("%d", &k);
k += id;
if (k > n + 1)
k = n + 1;
modify_father(id, k);
}
}
}
int main()
{
freopen("bounce.in", "r", stdin);
freopen("bounce.out", "w", stdout);
Init();
Solve();
return 0;
}
http://acm.pku.edu.cn/JudgeOnline/problem?id=1739
基于連通性狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃(名字真長(zhǎng)- -！)其實(shí)不算太難，以前都被它嚇住了。
hyf教了一次后，印象極其深刻，回路、路徑條數(shù)啥的從此再也不用向美國(guó)（霧）進(jìn)口了。
簡(jiǎn)要的說(shuō)：f[i][j][k]表示在（i，j）這個(gè)格子的時(shí)候，m+1個(gè)插頭的情況是k，然后根據(jù)(i,j)左邊和上邊插頭（括號(hào)？）的情況進(jìn)行連接，然后轉(zhuǎn)移到下一個(gè)格子。一個(gè)合法的狀態(tài)是一個(gè)括號(hào)表達(dá)式，有左括號(hào)，右括號(hào)和空格，且左右括號(hào)匹配。一個(gè)左括號(hào)和一個(gè)相應(yīng)的右括號(hào)表示這兩個(gè)地方的路徑是連在一起的。轉(zhuǎn)移的時(shí)候分情況討論。
處理的時(shí)候先把所有合法的狀態(tài)都dfs出來(lái)，轉(zhuǎn)移的時(shí)候就方便了。。
PS：居然驚喜地進(jìn)入了status第一頁(yè)？！。。。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXN 8
#define BLANK 0
#define LEFT 1
#define RIGHT 2
#define MAXSTATE 174420
#define MAXSTATEAMOUNT 835
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define ll long long
using namespace std;
int n,m;
char map[MAXN+1][MAXN+1];
int nState = 0;
int State[MAXSTATEAMOUNT+1];
int id[MAXSTATE+1];
int Tx, Ty, FinalState;
ll f[MAXN+1][MAXN+1][MAXSTATEAMOUNT+1];
ll ans;
void Reset(){
nState = 0, Tx = -1;
memset(f, 0, sizeof(f));
ans = 0;
}
bool Init(){
scanf("%d%d",&n,&m);
if (!n) return false;
Reset();
for (int i = n-1; i>=0; i--){
scanf("%s", map[i]);
if (Tx == -1)
for (int j = m-1; j>=0; j--)
if (map[i][j] == '.'){
Tx = i, Ty = j;
break;
}
for (int j = 0; j<m; j++)
if (map[i][j] == '.') map[i][j] = 0;
else map[i][j] = 1;
}
return true;
}
void dfs(int pos, int r_bracket, int state){
if (pos < 0){
State[nState] = state;
id[state] = nState;
/*
printf("%d: ", nState);
for (int i = 0; i<=m; i++)
printf("%d ", buffer[i]);
printf("\n");
*/
nState ++;
return;
}
if (pos >= r_bracket) // blank
dfs(pos - 1, r_bracket, (state << 2));
if (pos > r_bracket) // right bracket
dfs(pos - 1, r_bracket + 1, (state << 2) | RIGHT);
if (r_bracket) // left bracket
dfs(pos - 1, r_bracket - 1, (state << 2) | LEFT);
}
#define MASK 3
#define Get(state, p) (((state) >> (p<<1)) & MASK)
inline bool OK(int i, int j, int state){
if (Get(state, j) == 1 && Get(state, j+1) == 2 && !(i == Tx && j == Ty)) return false;
for (int k = 0; k<j; k++)
if ((map[i][k] || map[i+1][k]) && Get(state, k)) return false;
if (((j && map[i][j-1]) || (map[i][j])) && Get(state, j)) return false;
for (int k = j+1; k<=m; k++)
if (((i && map[i-1][k-1]) || (map[i][k-1])) && Get(state, k)) return false;
return true;
}
inline int Modify(int state, int p, int v){
return state - (((state >> (p << 1)) & MASK) << (p << 1)) + (v << (p << 1));
}
inline int FindRight(int p, int state){
int cnt = 0, t;
for (int i = p; i<=m; i++){
t = Get(state,i);
if (t == 1) cnt++;
if (t == 2) cnt--;
if (cnt == 0) return i;
}
return -1;
}
inline int FindLeft(int p, int state){
int cnt = 0, t;
for (int i = p; i>=0; i--){
t = Get(state, i);
if (t == 2) cnt++;
if (t == 1) cnt--;
if (cnt == 0) return i;
}
return -1;
}
void Solve(){
dfs(m, 0, 0);
f[0][0][id[(1 << 2) + (2 << (2 * m))]] = 1;
FinalState = (1 << (2 * Ty)) + (2 << (2 * (Ty+1)));
int p, q, tmp, tmp2, state, v, i, j, k;
ll *a;
for (i = 0; i < n; i++){
for (j = 0; j < m; j++){
a = f[i][j+1];
for (k = 0; k < nState; k++)
if ((v = f[i][j][k])){
state = State[k];
p = Get(state, j), q = Get(state, j+1);
if (p == 0 && q == 0){
if (!map[i][j]){
tmp = Modify(Modify(state, j, 1), j+1, 2);
if (OK(i, j+1, tmp))
a[id[tmp]] += v;
}else
a[k] += v;
}else if(p == 0){ // conditions below ensured map[i][j] is empty, because there exists at least one bracket on one side of the grid (i,j)
if (OK(i, j+1, state))
a[k] += v;
tmp = Modify(Modify(state, j, q), j+1, 0);
if (OK(i, j+1, tmp))
a[id[tmp]] += v;
}else if (q == 0){
if (OK(i, j+1, state))
a[k] += v;
tmp = Modify(Modify(state, j, 0), j+1, p);
if (OK(i, j+1, tmp))
a[id[tmp]] += v;
}else{
tmp = Modify(Modify(state, j, 0), j+1, 0);
if (p == 1 && q == 1){
tmp2 = Modify(tmp, FindRight(j+1, state), 1);
if (OK(i, j+1, tmp2))
a[id[tmp2]] += v;
}else if (p == 2 && q == 2){
tmp2 = Modify(tmp, FindLeft(j, state), 2);
if (OK(i, j+1, tmp2))
a[id[tmp2]] += v;
}else if (p == 1 && q == 2){
if (i == Tx && j == Ty && state == FinalState){
printf("%I64d\n", v);
return;
}
}else if (p == 2 && q == 1){
if (OK(i, j+1, tmp))
a[id[tmp]] += v;
}
}
}
}
for (int k = 0; k < nState; k++)
if (Get(State[k], m) == 0 && OK(i+1, 0, tmp = (State[k] << 2)))
f[i+1][0][id[tmp]] += f[i][m][k];
}
printf("%I64d\n", ans);
}
int main(){
while (Init())
Solve();
return 0;
}
http://d.namipan.com/d/1d015405c37f1b310d80af62e6bb5697f9367b00b7732d01
。。上邊這個(gè)鏈接如果有人
下載就會(huì)保留7天。。。7天沒(méi)人下就沒(méi)了。。
欲購(gòu)從速。。。
orz一切神牛。。
摘要: 序列操作
【題目描述】
lxhgww最近收到了一個(gè)01序列，序列里面包含了n個(gè)數(shù)，這些數(shù)要么是0，要么是1，現(xiàn)在對(duì)于這個(gè)序列有五種變換操作和詢問(wèn)操作：
0 a b 把[a, b]區(qū)間內(nèi)的所有數(shù)全變成0
1 a b 把[a, b]區(qū)間內(nèi)的所有數(shù)全變成1
2 a b 把[a,b]區(qū)間內(nèi)的所有數(shù)全部取反，也就是說(shuō)把所有的0變成1，把所有的1變成0
3 a b 詢問(wèn)[a, b]...
閱讀全文
摘要: 傳送帶
【題目描述】
在一個(gè)2維平面上有兩條傳送帶，每一條傳送帶可以看成是一條線段。兩條傳送帶分別為線段AB和線段CD。lxhgww在AB上的移動(dòng)速度為P，在CD上的移動(dòng)速度為Q，在平面上的移動(dòng)速度R。現(xiàn)在lxhgww想從A點(diǎn)走到D點(diǎn)，他想知道最少需要走多長(zhǎng)時(shí)間
【輸入】
輸入數(shù)據(jù)第一行是4個(gè)整數(shù)，表示A和B的坐標(biāo)，分別為Ax，Ay，Bx，By
第二行是4個(gè)整數(shù)，表示...
閱讀全文
字符串
【題目描述】
lxhgww最近接到了一個(gè)生成字符串的任務(wù)，任務(wù)需要他把n個(gè)1和m個(gè)0組成字符串，但是任務(wù)還要求在組成的字符串中，在任意的前k個(gè)字符中，1的個(gè)數(shù)不能少于0的個(gè)數(shù)。現(xiàn)在lxhgww想要知道滿足要求的字符串共有多少個(gè)，聰明的程序員們，你們能幫助他嗎？
【輸入】
輸入數(shù)據(jù)是一行，包括2個(gè)數(shù)字n和m
【輸出】
輸出數(shù)據(jù)是一行，包括1個(gè)數(shù)字，表示滿足要求的字符串?dāng)?shù)目，這個(gè)數(shù)可能會(huì)很大，只需輸出這個(gè)數(shù)除以20100403的余數(shù)
【樣例輸入】
2 2
【樣例輸出】
2
【數(shù)據(jù)范圍】
對(duì)于30%的數(shù)據(jù)，保證1<=m<=n<=1000
對(duì)于100%的數(shù)據(jù)，保證1<=m<=n<=1000000
=================================================================
。。。這題是最悲劇的一題。。。以前做過(guò)原題。。。然后考試的時(shí)候緊張的啥都不知道了。。。數(shù)學(xué)不過(guò)關(guān)啊！！T_T
一種推導(dǎo)是這樣的：
總的01串的數(shù)量為C(n+m,n)，考慮除去不符合條件的。
對(duì)于一個(gè)不符合條件的01串，一定有某個(gè)位置使得0的個(gè)數(shù)第一次超過(guò)1的個(gè)數(shù)，比如：
1010011010
|
設(shè)該位置是p，在1~p中1的個(gè)數(shù)為a，0的個(gè)數(shù)為a+1
則在p~n+m中，1的個(gè)數(shù)為n-a，0的個(gè)數(shù)為m-a-1
如果對(duì)p~n+m中的0和1取反，則在p~n+m中，1的個(gè)數(shù)為m-a-1，0的個(gè)數(shù)為n-a
對(duì)于這樣一個(gè)變換后的串，共有m-1個(gè)1，n+1個(gè)0。
由于每一個(gè)不符合條件的有n個(gè)1，m個(gè)0的01串都可以唯一確定對(duì)應(yīng)一個(gè)有m-1個(gè)1，n+1個(gè)0的01串，
并且每一個(gè)有m-1個(gè)1，n+1個(gè)0的01串一定有一個(gè)位置開(kāi)始0的個(gè)數(shù)第一次多于1的個(gè)數(shù)，把這個(gè)位置之后的串取反后得到的01串可以唯一確定對(duì)應(yīng)一個(gè)有n個(gè)1，m個(gè)0的不符合條件的01串，所以這兩種串是一一對(duì)應(yīng)的。
所以不符合條件的串的個(gè)數(shù)為C(n+m,n+1)
所以最后的答案為C(n+m,n) - C(n+m,n+1)
PS：算這個(gè)的時(shí)候可以分解質(zhì)因數(shù)（hyf神牛神做法），也可以用逆元解決除法的問(wèn)題。因?yàn)?span lang=EN-US>20100403是質(zhì)數(shù)，所以逆元就可以不用解方程算了，直接取a^(p-2)次方即可。
#include <iostream>
#define ll long long
#define MOD 20100403
#define MAXN 2100000
using namespace std;
/**//*
C(n+m,n) - C(n+m,n+1)
*/
ll n, m;
ll fact[MAXN+1];
ll PowerMod(ll a, int b)
{
if (b == 0) return 1;
ll t = PowerMod(a, b>>1);
t = (t * t) % MOD;
if (b&1) t = (t * a) % MOD;
return t;
}
ll Rev(ll a){
return PowerMod(a, MOD-2);
}
void Init(){
cin >> n >> m;
}
ll C(int n, int m){
return fact[n] * Rev(fact[m]) % MOD * Rev(fact[n-m]) % MOD;
}
void Solve(){
fact[0] = 1;
for (ll i = 1; i<=n+m; i++)
fact[i] = (fact[i-1] * i) % MOD;
cout << ((C(n+m,n) - C(n+m,n+1)) % MOD + MOD) % MOD;
}
int main(){
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
Init();
Solve();
return 0;
}
摘要: 股票交易
【題目描述】
最近lxhgww又迷上了投資股票，通過(guò)一段時(shí)間的觀察和學(xué)習(xí)，他總結(jié)出了股票行情的一些規(guī)律。
通過(guò)一段時(shí)間的觀察，lxhgww預(yù)測(cè)到了未來(lái)T天內(nèi)某只股票的走勢(shì)，第i天的股票買(mǎi)入價(jià)為每股APi，第i天的股票賣(mài)出價(jià)為每股BPi（數(shù)據(jù)保證對(duì)于每個(gè)i，都有APi>=BPi），但是每天不能無(wú)限制地交易，于是股票交易所規(guī)定第i天的一次買(mǎi)入至多只能購(gòu)買(mǎi)ASi股，...
閱讀全文