伊人久久亚洲综合影院,久久99精品国产麻豆宅宅,国产精品久久影院

CEOI2010-The Alliances

TimTopCoder — Thu, 15 Jul 2010 03:19:00 GMT

摘要: The Alliances In a fantasy world, there is a large island of a rectangular shape. The sides of the island happen to be exactly R miles and C miles long, and the whole island is divided into a grid ... 阅读全文

TimTopCoder 2010-07-15 11:19 发表评论

HNOI2010-弚w��l늾�-(splay�l�护括号序列 �?动态树)

TimTopCoder — Fri, 09 Jul 2010 13:00:00 GMT

听说有版权问题不能脓(chu��ng)题目�Q�。那��只能先忍一忍了�?br>题目抽象为：我们有一个由有根树构成的��林�Q�对�q�个��林�q�行两种操作�Q?br>把某��子树拔下来接到某一��|��Q�可能还是那个子树原来所在的树）的某个节点下面，询问某个节点在树中的深度�?br>
因�ؓ把一��边权�ؓ1的树的括号序列拿出来�Q�树上某两点的距��d��是在括号序列中两炚w��没匹配括��L��个数�Q�有左括号右括号选择的区别，具体分析处理�Q�。当�Ӟ��既然是对一��树操作�Q�那��q��接用动态树��p��了�?br>
于是��去学了动态树。发现其实不��很难（1.指时间复杂度均摊logn的算法，�q�有��Z��轻重边剖分的严格logn的算�?2.如果你对splay熟的话）�Q�写��h��也就基本上就是一��splay�Q�也��比较好写的。。（以后��告别�\径剖分了。。太�ȝ��了。。复杂度也没动态树好。。）

以下所说的动态树都是��Z��splay的时间复杂度均摊logn的动态树�?br>
动态树的主要思想��是�Q�类��D��重边剖分一��P��把整��|��划分成若�q�实�?solid edge)和虚�?dashed edge)�Q�但�q�个都是�Ҏ(gu��)��你的需要来讑֮�的，不像轻重边一��h��个点往下都必须有一条重边（单独的叶子节点算长度�?的重边）�Q�而是每次把你所需要操作的点到根的辚w��改�ؓ实边(expose操作)�Q�且每个点往下的实边��C��过1。修�Ҏ(gu��)��途如果有一个点已经有了实边辚w��么就把它原来的实�Ҏ(gu��)��成虚辏V��这��h��ơ对一个点操作都是在一条实路径�?solid path)。对于每一条实路径�Q�都用一��splay来维护就行了。（splay可以��p�{乱拔乱接太爽了。�? -!当然是在一定规则下的�ؕ。。）

/*
* $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;
}

TimTopCoder 2010-07-09 21:00 发表评论

TimTopCoder — Wed, 28 Apr 2010 06:39:00 GMT

摘要: 货币兑换问题描述 ��?Y 最�q�在一安��怺�易所工作。该金券交易所只发行交易两�U�金券：A �U?念券�Q�以下简�U?A 券）�?B �U�念券（以下��U?B 券）。每个持有金券的��֮�都有一个自��q��帐户。金券的数目可以是一个实数�?nbsp; 每天随着市场的�v伏�L动，两种金券都有自己当时的�h(hu��n)��|��x��一单位金券当天可以�?.. 阅读全文

TimTopCoder 2010-04-28 14:39 发表评论

TimTopCoder — Sat, 10 Apr 2010 05:59:00 GMT

http://acm.pku.edu.cn/JudgeOnline/problem?id=1739
��Z��q�通性状态压�~�的动态规�?名字真长- -�Q?其实不算太难�Q�以前都被它吓住了�?br>hyf教了一�ơ后�Q�印象极其深刻，回�\、�\径条数啥的从此再也不用向��国�Q�雾�Q�进口了�?br>��要的��_��f[i][j][k]表示在（i�Q�j�Q�这个格子的时候，m+1个插头的情况是k�Q�然后根�?i,j)左边和上�Ҏ(gu��)��_��括号�Q�）的情况进行连接，然后转移��C��一个格子。一个合法的状态是一个括可��辑ּ��Q�有左括��P��x��号和�I�格�Q�且左右括号匚w��。一个左括号和一个相应的��x��可��C��两个地方的�\径是�q�在一��L��。�{�Uȝ��时候分情况讨论�?br>处理的时候先把所有合法的状态都dfs出来�Q��{�Uȝ��时候就方便了。�?br>PS�Q�居然惊喜地�q�入了status�W�一��？�Q�。。�?br>#include
#include
#include
#include
#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             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         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;
}

TimTopCoder 2010-04-10 13:59 发表评论

SCTSC2010-资料下蝲

TimTopCoder — Sat, 10 Apr 2010 03:16:00 GMT

http://d.namipan.com/d/1d015405c37f1b310d80af62e6bb5697f9367b00b7732d01
。。上边这个链接如果有�?span onclick="tagshow(event)" class="t_tag">下蝲��׃��保留7天。。�?天没��Z��没了。�?br>�Ʋ购从速。。�?br>orz一切神牛。�?br>

TimTopCoder 2010-04-10 11:16 发表评论

学习�W�记-Splay

TimTopCoder — Fri, 09 Apr 2010 06:43:00 GMT

摘要: 很久以前有且写过一�ơsplay。。。然后被它要记父亲的旋�{囧到。。然后从此就再也没写�q�。。这几天刚省选完没事做，��准备再写一下。在sqybi��牛的文章的指导下很快又回忆起了splay的操作。。于是从头开始YY一个splay。。。��M��感觉比treap要难写。。（Treap性�h(hu��n)比真的很高）�Q�但要比treap强大许多。。。感觉上splay完全可以代替�U�段树了。。只是常数太大了。。做了两道splay的题�Q?.. 阅读全文

TimTopCoder 2010-04-09 14:43 发表评论

SCTSC2010-序列操作

TimTopCoder — Thu, 08 Apr 2010 02:17:00 GMT

摘要: 序列操作【题目描�q��?lxhgww最�q�收��C��一�?1序列�Q�序列里面包含了n个数�Q�这些数要么�?�Q�要么是1�Q�现在对于这个序列有五种变换操作和询问操作： 0 a b 把[a, b]区间内的所有数全变�? 1 a b 把[a, b]区间内的所有数全变�? 2 a b 把[a,b]区间内的所有数全部取反�Q�也��是说把所有的0变成1�Q�把所有的1变成0 3 a b 询问[a, b]... 阅读全文

TimTopCoder 2010-04-08 10:17 发表评论

SCTSC2010-传送带

TimTopCoder — Thu, 08 Apr 2010 02:06:00 GMT

摘要: 传送带【题目描�q��?在一�?�l��^面上有两条传送带�Q�每一条传送带可以看成是一条线�D�c��两条传送带分别为线�D�A(ch��)B和线�D�CD。lxhgww在AB上的�U�d��速度为P�Q�在CD上的�U�d��速度为Q�Q�在�q�面上的�U�d��速度R。现在lxhgww想从A点走到D点，他想知道最��需要走多长旉�� 【输入�?输入数据�W�一行是4个整敎ͼ�表示A和B的坐标，分别为Ax�Q�Ay�Q�Bx�Q�By �W�二行是4个整敎ͼ�表示... 阅读全文

TimTopCoder 2010-04-08 10:06 发表评论

TimTopCoder — Thu, 08 Apr 2010 01:54:00 GMT

字符�?span lang=EN-US>

【题目描�q��?/span>

lxhgww最�q�接��C��一个生成字�W�串的�Q务，��d��需要他�?/span>n�?/span>1�?/span>m�?/span>0�l�成字符�Ԍ��但是��d��q�要求在�l�成的字�W�串中，在�Q意的�?/span>k个字�W�中�Q?/span>1的个��C��能少�?/span>0的个数。现�?/span>lxhgww惌��知道满��要求的字�W�串共有多少个，聪明的程序员们，你们能帮助他吗？

【输入�?/span>

输入数据是一行，包括2个数�?/span>n�?/span>m

【输出�?/span>

输出数据是一行，包括1个数字，表示满��要求的字�W�串数目�Q�这个数可能会很大，只需输出�q�个数除�?/span>20100403的余�?/span>

【样例输入�?/span>

2 2

【样例输出�?/span>

【数据范围�?/span>

对于30%的数据，保证1<=m<=n<=1000

对于100%的数据，保证1<=m<=n<=1000000

=================================================================
。。。这题是最�(zh��n)�剧的一题。。。以前做�q�原题。。。然后考试的时候紧张的啥都不知道了。。。数学不�q�关啊！�Q�T_T
一�U�推导是�q�样的：
�ȝ��01串的数量为C(n+m,n)�Q�考虑除去不符合条件的�?br>对于一个不�W�合条�g�?1�Ԍ��一定有某个位置使得0的个数第一�ơ超�q?的个敎ͼ�比如�Q?br>1010011010
|
设该位置是p�Q�在1~p�?的个��Cؓa�Q?的个��Cؓa+1
则在p~n+m中，1的个��Cؓn-a�Q?的个��Cؓm-a-1
如果对p~n+m中的0�?取反�Q�则在p~n+m中，1的个��Cؓm-a-1�Q?的个��Cؓn-a
对于�q�样一个变换后的串�Q�共有m-1�?�Q�n+1�?�?br>�׃��每一个不�W�合条�g的有n�?�Q�m�?�?1串都可以唯一��定对应一个有m-1�?�Q�n+1�?�?1�Ԍ��
�q�且每一个有m-1�?�Q�n+1�?�?1串一定有一个位�|�开�?的个数第一�ơ多�?的个敎ͼ�把这个位�|�之后的串取反后得到�?1串可以唯一��定对应一个有n�?�Q�m�?的不�W�合条�g�?1�Ԍ��所以这两种串是一一对应的�?br>所以不�W�合条�g的串的个��CؓC(n+m,n+1)
所以最后的�{�案为C(n+m,n) - C(n+m,n+1)
PS�Q�算�q�个的时候可以分解质因数�Q�hyf��牛��做法）�Q�也可以用逆元解决除法的问题。因�?span lang=EN-US>20100403是质敎ͼ�所以逆元?y��u)��可以不用解方程��了�Q�直接取a^(p-2)�ơ方卛_��?br>

#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;
}

TimTopCoder 2010-04-08 09:54 发表评论

SCTSC2010-股票交易

TimTopCoder — Thu, 08 Apr 2010 01:37:00 GMT

摘要: 股票交易【题目描�q��?最�q�lxhgww又迷上了投资股票�Q�通过一�D�|��间的观察和学习，他�ȝ��Z��股票行情的一些规律�?通过一�D�|��间的观察�Q�lxhgww预测��C��未来T天内某只股票的走势，�W�i天的股票买入价�ؓ每股APi�Q�第i天的股票卖出价�ؓ每股BPi�Q�数据保证对于每个i�Q�都有APi>=BPi�Q�，但是每天不能无限制地交易�Q�于是股��交易所规定�W�i天的一�ơ买入至多只能购买ASi股，... 阅读全文

TimTopCoder 2010-04-08 09:37 发表评论