AHOI2013 Round1 题解&&总结

（首先声明一下，今年AHOI R1的题==JSOI R3 Day1的题）
【题解】
sport:
首先很容易证明，最优方案必然是左边都是-，右边都是+（从样例也可以看出来囧）……
因此问题转化为了第几次开始+，可以使得开始+的时候，目标元素的位置最左……
注意到排队的过程实际上是个冒泡……因此本题的关键在于发掘出冒泡的性质囧……
设最初的序列为A[0..N-1]，目标元素为A[pos]。设S[0]为排在A[pos]之左的比A[pos]大的元素的个数（因为一开始排在A[pos]之左的且<=A[pos]的元素，不管肿么搞都一直在目标元素之左，不管它们了囧……），然后，考察所有一开始排在A[pos]之右的，比A[pos]小（注意是<A[pos]，不是<=）的所有元素，设它们之间的间隔分别为S[1]、S[2]、S[3]……（具体见图，其中S[1]为A[pos]和第一个比A[pos]小的元素之间的间隔）

然后来审视一下整个冒泡的过程。一开始，必然是将目标元素左边的一个比目标元素大的元素移到右边去，在目标元素右边它可能会停下来，但紧接着必然是一个值更大的元素继续往右移，最终的效果等价于将目标元素左边的一个比目标元素大的元素“移出去”了（即移到了最右边的比目标元素小的元素的右边），也就是S[0]减了1，而S[1]、S[2]……都没变，这个过程显然只能持续S[0]次，目标元素左边比它大的元素就全部移出去，此时目标元素到达了它“可能到达”的最左位置。
接着，目标元素和右边第一个比它小的元素（即图中的A[i1]）之间的，比目标元素大的那些元素将被依次的移出去，也就是S[1]不断减1，而S[2]及后面的都没变。这一过程会持续S[1]次，目标元素就和A[i1]靠在一起了（注意，在这个过程中，目标元素的位置是不会变的）。
如果此时继续冒泡，则目标元素就会和A[i1]交换，右移一个位置，并且就从这次冒泡开始，S[2]不断减1，减到0为止，接着目标元素和A[i2]交换，右移一个位置，S[3]不断减1……直到最后一个S[]值也减到0后，目标元素到达它的目标位置。
也就是，设“第i阶段”为S[i]值减少的这个阶段，则在第0阶段，目标元素会不断左移，显然不用+，第1阶段，目标元素不动，也不用+，但从第2阶段开始，在每阶段的第一次冒泡时，目标元素都会向右移一个位置。因此，开始+的时候，必然是第x（x>=2）阶段的开始的那次。由于最多只能+ K次，因此可能的最左位置就是满足N-1-∑(0<=j<x)S[j] <=K的最小的x值减2，加上一开始就在目标元素之左的，且值不大于目标元素的元素个数（它们必然在目标元素之左）。注意特殊情况：x<2（此时当成x=2处理），或者x不存在（全是-）。
因此，本题就是预处理求出所有S之后，扫一遍得出最小的x值就行了，O(N)。
当然，二分答案+暴力判断可以得50，有神犇说二分答案之后可以在O(N)时间内判断，从而O(NlogN)解决，我太弱了，完全搞不懂囧……（Orz！！）

mole：
首先，一个很重要的事实就是，“整个过程中左手所在的位置严格小于右手”其实是一个废条件！！因为如果左右手交叉了，必然是左手试图去打靠右的一个，而右手试图去打靠左的一个，此时，让它们交换，则两只手移动的距离都变小，方案仍然合法，且更优（我太弱了，当时就是在这里想抽了很久，以至于木有做这题……后来才知道这题很水……真悲剧！！！）
接下来就变成了一个全局统筹的问题，可以用网络流解决：每个地鼠i拆成两个点：入点i'、出点i''，中间连一条容量为1（表示只能打一次），费用为它的得分的边，两只手开始的位置也当成有地鼠，只不过得分为0而已。如果某只手在打完第i个地鼠后能接着去打第j个地鼠，就连边<i'', j'>，容量1，费用0。s往表示两只手开始的两个点的入点连一条容量为1，费用为0的边，每个出点往T连一条容量为1，费用为0的边。求这个图的最大费用最大流即可。
当然，用O(N3)的DP也可以得到至少60分，如果卡的好的话可能有80以上囧……

bus：
裸的数据结构题，用一坨Splay Tree维护即可，唯一要注意的就是链可以翻转，因此要rev标记……
还是不会搞的可以去做ZJOI2012 Day2的某题……
这题在数据结构题中还是比较好写的……值得吐槽的是它的对拍很难写……本沙茶写正解用了50min，写对拍用了75min……
———————————————————————————————————————————————————
【总结 && 一些闲扯】
（1）（Orz @sunzhouyi）
“要想滚粗：
0.仔细看错或者记错题。
1.选对不可做题。
2.思考坑爹题[鉴于‘坑爹’一词在AH的特殊含义，建议这一点改为“思考废条件怎么处理”]。
3.认真写自己不会的东西。
4.最后还不写暴力分。”
本沙茶中了其中的三点，因此悲剧了……
（2）热烈庆祝今年的题目不再坑爹了！！！！！！（因为用的是JSOI的题，bus还抄袭了ZJOI……）
（3）这次的题目……要么是难想、好写（sport代码只有1K多），要么是好想、较难写，但还可以写的完的（指bus，和BZOJ上最近的那些数据结构相比真是太人道了……）
（4）要善于发掘题目的本质，特别是一些隐含的最优性质（比如mole的那个废条件为什么废）；
（5）遇到想了很久想不出的题，一定要换一个方向去想，因为很可能是一开始的方向疵了；
（6）对于代码量较大的题（如数据结构题），到底写不写是要看情况的，灵活掌握；

一些闲扯：
（1）本沙茶所在的考场几乎全是神犇，就我一个沙茶……于是被虐傻了……
（2）比赛时看到对面的一个人在喝“和其正”……瞬间吓傻了……（话说肿么木有看到喝阿华田的囧……）
（3）昨天试机的时候，被Atbiter虐了半天，一开始肿么配置都是“找不到答案文件”……后来才发现Atbiter已经改版了，players下面的第一层文件夹应该是考试场数编号（Day1、Day2……）；
（4）试机的时候发现鼠标是坏的，后来才知道这个考场有6个鼠标坏了，3个键盘坏了，2个系统时间显示错误……
（5）总之这次挂惨了，不过前30应该能进，重点是Round2，加油！！我要复仇！！

posted @ 2013-05-18 17:38 Mato_No1 阅读(1092) | 评论 (4) | 编辑 收藏

【AHOI2013复仇】数论之神

原题地址
这题真是太神犇了……可以让人完全搞懂数论同余部分的全部内容……

题解……由于虹猫大神已经在空间里写得很详细了，所以就不肿么写了囧……
主要说一下一些难想的和容易搞疵的地方：
（1）中国剩余定理的那个推论（多个同余方程的模数互质，则整个方程组在小于所有模数之积的范围内的解数等于各个方程解数之积）其实是很强大的，不光对线性同余方程有用，对这种非线性的同余方程也有用，只需要所有方程都满足：若模数为MOD，则a是解当且仅当(a+MOD)是解……本题显然满足，因此，只要在按质因数拆分后求出各个方程的解数，再相乘即可（本沙茶就是这里木有想起来，结果看了虹猫的题解囧……）；
（2）对于余数不为0且和模数不互质的情况要特别注意（这个好像很多标程都疵了，比如虹猫给的标程，不过数据弱，让它们过了囧），首先必须是余数含p（p为该方程模数的质因数）因子的个数j是a的倍数（也就是余数是p^a的倍数）才能有解，然后，当有解时，转化为解必须是p^(j/a)的倍数以及x/(p^(j/a))满足一个模数指数为原来指数减j的方程，这里需要注意，这个新方程的解数乘以p^(j-j/a)才是原来方程的解数！！道理很简单，因为模数除以了p^j，而x只除以了p^(j/a)……可以用一组数据检验：3 330750 6643012，结果是135而不是15；
（3）原根只能暴力求（不过最小原根都很小，1000以内的所有质数最小原根最大只有19……），但在求的时候有一个小的优化：首先p的原根也是p的任意整数次方的原根，然后求p的原根时，将(p-1)的非自身因数（预先求出）递减排序，这样可以比较快地排除不合法解；
（4）求逆元时一定要注意，如果得到的逆元是负数，要转化为正数，另外要取模；
（5）BSGS的时候一定要注意去重，在保留重复元素的情况下即使使用另一种二分查找也会疵的；
（6）数组不要开小了；

代码：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 110, MAXP = 50010, INF = ~0U >> 2;
int P_LEN, _P[MAXP + 1], P[MAXP + 1];
int A, B, M, n, DS[MAXN], DK[MAXN], R[MAXN], KR[MAXP], res;
struct sss {
    int v, No;
    bool operator< (sss s0) const {return v < s0.v || v == s0.v && No < s0.No;}
} Z[MAXP];
void prepare0()
{
    P_LEN = 0; int v0;
    for (int i=2; i<=MAXP; i++) {
        if (!_P[i]) P[P_LEN++] = _P[i] = i; v0 = _P[i] <= MAXP / i ? _P[i] : MAXP / i;
        for (int j=0; j<P_LEN && P[j]<=v0; j++) _P[i * P[j]] = P[j];
    }
}
void prepare()
{
    n = 0; int M0 = M;
    re(i, P_LEN) if (!(M0 % P[i])) {
        DS[n] = P[i]; DK[n] = 1; M0 /= P[i]; while (!(M0 % P[i])) {DK[n]++; M0 /= P[i];} n++;
        if (M0 == 1) break;
    }
    if (M0 > 1) {DS[n] = M0; DK[n++] = 1;}
    int x;
    re(i, n) {
        x = 1; re(j, DK[i]) x *= DS[i];
        R[i] = B % x;
    }
}
ll pow0(ll a, int b, ll MOD)
{
    if (b) {ll _ = pow0(a, b >> 1, MOD); _ = _ * _ % MOD; if (b & 1) _ = _ * a % MOD; return _;} else return 1;
}
void exgcd(int a, int b, int &x, int &y)
{
    if (b) {
        int _x, _y; exgcd(b, a % b, _x, _y);
        x = _y; y = _x - a / b * _y;
    } else {x = 1; y = 0;}
}
int gcd(int a, int b)
{
    int r = 0; while (b) {r = a % b; a = b; b = r;} return a;
}
void solve()
{
    int x, y; res = 1;
    re(i, n) if (!R[i]) {
        if (DK[i] < A) x = 1; else x = (DK[i] - 1) / A + 1;
        re2(j, x, DK[i]) res *= DS[i];
    } else if (!(R[i] % DS[i])) {
        x = 0; while (!(R[i] % DS[i])) {R[i] /= DS[i]; x++;}
        if (x % A) {res = 0; return;} else {
            DK[i] -= x; y = x / A;
            re2(j, y, x) res *= DS[i];
        }
    }
    int phi, m0, m1, KR_len, _r, v0, _left, _right, _mid, T; bool FF;
    re(i, n) if (R[i]) {
        x = DS[i] - 1; KR_len = 0;
        for (int j=2; j*j<=x; j++) if (!(x % j)) {
            KR[KR_len++] = j;
            if (j * j < x) KR[KR_len++] = x / j;
        }
        KR[KR_len++] = 1;
        re2(j, 2, DS[i]) {
            FF = 1;
            rre(k, KR_len) {
                _r = (int) pow0(j, KR[k], DS[i]);
                if (_r == 1) {FF = 0; break;}
            }
            if (FF) {x = j; break;}
        }
        phi = DS[i] - 1; re2(j, 1, DK[i]) phi *= DS[i]; v0 = phi / (DS[i] - 1) * DS[i];
        m0 = (int) ceil(sqrt(phi) - 1e-10);
        Z[0].v = 1; Z[0].No = 0; re2(j, 1, m0) {Z[j].v = (ll) Z[j - 1].v * x % v0; Z[j].No = j;}
        _r = (ll) Z[m0 - 1].v * x % v0; sort(Z, Z + m0);
        m1 = 1; re2(j, 1, m0) if (Z[j].v > Z[j - 1].v) Z[m1++] = Z[j];
        exgcd(_r, v0, x, y); if (x < 0) x += v0; y = R[i];
        re(j, m0) {
            _left = 0; _right = m1 - 1; T = -1;
            while (_left <= _right) {
                _mid = _left + _right >> 1;
                if (y == Z[_mid].v) {T = j * m0 + Z[_mid].No; break;}
                else if (y < Z[_mid].v) _right = _mid - 1; else _left = _mid + 1;
            }
            if (T >= 0) break; else y = (ll) y * x % v0;
        }
        x = gcd(A, phi); if (T % x) {res = 0; break;} else res *= x;
    }
}
int main()
{
    int tests;
    scanf("%d", &tests);
    prepare0();
    re(testno, tests) {
        scanf("%d%d%d", &A, &B, &M); M += M + 1; B %= M;
        if (!A) {
            if (B == 1) res = M; else res = 0;
        } else {
            prepare();
            solve();
        }
        printf("%d\n", res);
    }
    return 0;
}

posted @ 2013-03-15 19:24 Mato_No1 阅读(1388) | 评论 (2) | 编辑 收藏

【AHOI2013复仇】二维DP优化的几道题总结

【1】BZOJ1713
F[i][j]=max{F[i1][j1] - (sA[i-1]-sA[i1])2 - (sB[j-1]-sB[j1])2} + A[i]*B[j], 0<=i1<i, 0<=j1<j
对这个式子进行化简：
F[i][j]=max{F[i1][j1] - sA[i1]2 + 2*sA[i-1]*sA[i1] - sB[j1]2 + 2*sB[j-1]*sB[j1]}+A[i]*B[j]-sA[i-1]2-sB[j-1]2
对于一维的情况，很容易处理——中间就是一条直线，然而这是二维的，对于这种2D/2D的DP方程，要优化到O(N2)级别，需要两步。
注意到决策式中除了F[i1][j1]外，其它部分都要么只与i1有关，要么只与j1有关。因此，可以把阶段i的各个状态作为一个整体，在之前得出的各个F[i][j]中，对于相同的j，找到对于目前的i，最优的那个决策——注意，对于相同的j1，里面所有与j1有关的东西都可以先不考虑了，只考虑(F[i1][j1] - sA[i1]2 + 2*sA[i-1]*sA[i1])对于目前i的最优决策。这一步可以在这些直线形成的上凸壳中找到，且满足决策单调性，可以用一个栈处理（斜率优化）。然后，将这些最优决策以j为自变量再组成一些直线，用栈维护它们的上凸壳，对于每个j，找到最优值即可。
注意事项：在栈中删除直线的时候，如果之前的最优决策是这个被删掉的直线，则要将最优决策先置为不存在，然后再插入新直线后设为新直线。另外，要特别注意平行的情况。

【2】LCIS
经典问题，利用上面的分步优化思想，很容易用线段树得到一个O(N2logN)的做法。

【3】[SCOI2010]股票交易
F[i][j]=max{F[i-1][j], max{F[i-W-1][j-a]-A*a, F[i-W-1][j+b]+b*B}}, j<=maxP, 1<=a<=maxA, 1<=b<=maxB
注意对于相同的j，计算方法是一样的，且是一条直线（由于有范围所以其实是线段）。
所以，计算阶段i时，可以将(i-W-1)阶段所有的决策当成线段插入，这些线段的斜率都相等，因此比较好维护，只需要判断边界即可。

注意，NOI2011的show虽然也符合对于相同的j计算方法一样，但它就不能优化，因为它的决策是不连续且无规律的，没有任何几何性质。因此，它只能用O(N3)的算法计算出所有状态。

posted @ 2013-03-03 15:25 Mato_No1 阅读(998) | 评论 (0) | 编辑 收藏

【AHOI2013复仇】动态凸包

     摘要: 原题地址写了几天终于写出来了……（显然，我太弱了，请各位神犇不要鄙视）在有加点的情况下，动态地维护凸包，有以下两种方法：<1>维护上、下凸壳（本沙茶采用的方法）：凸包可以拆成上、下凸壳，对它们分别维护。两个凸壳均按照下面定义的<关系（即先x增、再y增）排序，注意，两个凸壳的两端是相同的，均为整个凸包的最小点与最大点，除两端外，它们没有公共定点。以上凸壳为例...  阅读全文

posted @ 2013-02-28 18:29 Mato_No1 阅读(2797) | 评论 (0) | 编辑 收藏

【AHOI2013复仇】向JZPKIL认输了

RT，
今天又优化了一下JZPKIL，用上了各种无耻的手段，仍然无法干掉后两个点，并且BZOJ上的总时间50s也无法实现（后两个点一个就要20s），
看来基于组合数的做法由于要枚举因数，确实不行……
（注：后两个点是人工构造的猥琐数据，所有的N都是若干个小质数之积，因数个数都上千，有的甚至上万……）

认输了……
Orz @sevenk

posted @ 2013-02-06 23:26 Mato_No1 阅读(1180) | 评论 (1) | 编辑 收藏

明天就要去受虐了

又是一次WC……
本沙茶这半年来过得真是颓废啊囧（虽然比上赛季同期好一些）……实力虽然有所提高，但比起别人来说太不值得一提了……
本次WC又不知道要被多少人（神犇或一般人）虐了……

三个愿望：
（1）能听懂尽可能多的知识点，最好能将自己以前搞不懂的那些都搞懂囧……
（2）能认识尽可能多的神犇（包括集训队的和本届的），最好能找到一个人以后共勉，这样就不会再颓废了囧……
（3）明年还能去WC囧（nimendongde）……

posted @ 2013-01-23 22:37 Mato_No1 阅读(381) | 评论 (0) | 编辑 收藏

【AHOI2013复仇】两道有关删边后最短路径维护的猥琐题

     摘要: 【先祝贺一下@Jollwish神犇进入CMO国家集训队……合肥OI人总算出了个国家集训队员（虽然不是OI的）……】最近捉了两道猥琐题……都是有关图中删去某边后的最短路径的问题……核心思想几乎相同……但是，它们很明显是综合题，代码量太大了（与NOIP2012的drive和block...  阅读全文

posted @ 2013-01-19 16:49 Mato_No1 阅读(2608) | 评论 (0) | 编辑 收藏

【AHOI2013复仇】BZOJ2165

原题地址
2013年第一题……纪念一下……

设F[i][j]表示坐i次电梯到达房间j，最多能到几楼，则有
F[i][j]=max{F[i-1][k]+W[k][j]}, 0<=k<n；
这里W[k][j]要注意，如果不存在从k到j的电梯，W[k][j]应设为-INF。
这个方程显然是可以用矩阵乘法来优化的。
然后，问题就是求出最小的i使得F[i]的状态中有值>=M的，这个可以二分（每次看当前解与W的(2^K-1)次方的运算结果，若有解则实际不进行这次运算，否则与W的2^K次方运算）……总时间复杂度是O(n3logM)的，对于本题可能要进行一些常数优化才能过（20个点，每个点5个数据，相当于100个点，时限只有40s），反正本沙茶是卡线过的。

但是，本题有一个细节很重要，必须要说一下（因为本沙茶在这里卡了1h+）……那就是溢出问题……
F[i][j]的值是有可能超过long long的范围的，然而如果硬加高精度的话稳T，这时，在进行矩阵乘法（实际是加法）的时候，需要特判一下，如果这个和超过了INF（INF是~0Ull>>2，>1018），就取INF。这样可能会破坏结合律，但是木有事，因为若两个加数都是非负数，则不会破坏，若有负数，则一定表示无解（-INF），这个特判一下就行了（若两个加数之中有负数，则结果取-INF）。

代码：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 110, MAXLEN = 61;
const ll INF = ~0Ull >> 2;
int n;
ll M, A[MAXLEN][MAXN][MAXN], W0[MAXN][MAXN], _[MAXN][MAXN], res;
void mult(ll A0[][MAXN], ll B0[][MAXN])
{
    re(i, n) re(j, n) _[i][j] = -INF; ll __;
    re(i, n) re(j, n) re(k, n) if (A0[i][k] >= 0 && B0[k][j] >= 0) {
        __ = A0[i][k] + B0[k][j];
        if (__ > INF) __ = INF;
        if (__ > _[i][j]) _[i][j] = __;
    }
}
void prepare()
{
    re2(i, 1, MAXLEN) {
        mult(A[i - 1], A[i - 1]);
        re(j, n) re(k, n) A[i][j][k] = _[j][k];
        mult(A[i], A[0]);
        re(j, n) re(k, n) A[i][j][k] = _[j][k];
    }
}
void solve()
{
    re(i, n) re(j, n) if (i == j) W0[i][j] = 0; else W0[i][j] = -INF; bool FF; res = 0;
    rre(i, MAXLEN) {
        FF = 0; re(j, n) if (A[i][0][j] >= M) {FF = 1; break;}
        if (FF) continue;
        mult(W0, A[i]);
        FF = 0; re(j, n) if (_[0][j] >= M) {FF = 1; break;}
        if (!FF) {
            re(j, n) re(k, n) W0[j][k] = _[j][k];
            mult(W0, A[0]);
            re(j, n) re(k, n) W0[j][k] = _[j][k];
            res += 2ll << i;
        }
    }
    FF = 0; re(i, n) if (W0[0][i] >= M) {FF = 1; break;}
    if (!FF) res++;
}
int main()
{
    int tests;
    scanf("%d", &tests);
    re(testno, tests) {
        cin >> n >> M;
        re(i, n) re(j, n) {scanf("%lld", &A[0][i][j]); if (!A[0][i][j]) A[0][i][j] = -INF;}
        prepare();
        solve();
        cout << res << endl;
    }
    return 0;
}

posted @ 2013-01-01 15:39 Mato_No1 阅读(507) | 评论 (0) | 编辑 收藏

【AHOI2013复仇】关于线段树下标的一种优化表示法

在线段树中，一般都不需要刻意保存其左右子结点的下标，而直接由其本身的下标导出，传统的写法是：
根结点：1
A的左子结点：2A（写成A<<1）
A的右子结点：2A+1（写成(A<<1)+1）
这种表示法可以表示出整棵线段树，因为：
（1）每个结点的子结点的下标都比它大，这样就不会出现环；
（2）每个结点的父结点都是唯一的（其本身下标整除2）；
但是，这种表示法有一个弱点：结点的下标是有可能超过2N的，但不会超过4N，因此，为了表示出跨度为N的线段，我们需要开4N的空间，然而，其中只有2N-1个位置是有用的（因为表示跨度为N的线段的线段树共有(2N-1)个结点），这样，就有一半的空间被浪费。尤其是这种线段树推广到多维的时候——K维线段树就只有1/2K的位置是有用的，空间利用率非常低。在某些卡空间的场合，它就囧掉了。

那么，有木有好一点的写法呢？最好能使空间利用率达到100%——也就是所有结点的下标刚好就是1~(2N-1)！！（0号结点一般作为“哨兵”，不被占用）
并且，这种写法要保证仅仅由结点的下标和它表示的线段的左右端点（因为在遍历线段时，下标和左右端点基本上都是同时知道的），就能得出其子结点的下标，而不需要借助额外的东东（最好mid都不需要算）。
这种写法就是——直接将每个结点的DFS遍历次序当做它的下标！！
比如，跨度为6的线段树：

容易发现，根结点下标为1，下标为A的结点的左子结点下标为(A+1)，右子结点下标为A+SZ(A.L)+1，其中SZ(A.L)为A的左子树大小。
若A的左右端点为l、r，mid=(l+r)/2（下取整），则A的左子树所表示的线段为[l, mid]，所以SZ(A.L)=(mid-l+1)*2-1=(mid-l)*2+1=((r-l-1)/2（上取整）)*2+1
这样，A的右子结点下标就是A+((r-l+1)/2（上取整))*2，也就是A加上大于(r-l)的最小的偶数；
写在代码里就是：
int mid=l+r>>1;
opr(l, mid, A+1);
opr(mid+1, r, (r-l&1?A+r-l+1:A+r-l+2));
或者，借助位运算，可以免去条件判断：
int mid=l+r>>1;
opr(l, mid, A+1);
opr(mid+1, r, A+r-l+2-((r^l)&1));
经测试，后者（使用位运算的）虽然总的运算次数多于前者（使用条件判断的），但后者比前者快一点点，其原因可能与C语言中的条件运算符速度较慢有关；

这样，我们就成功地将线段树下标的空间利用率提高到了100%！！以后只需要开2N空间就行了囧……
与传统表示法相比，这种新式表示法虽然可以节省空间，但时间消耗要更大一些（时间和空间总是矛盾的囧……），因为它在找右子结点的时候需要较多的运算。平均起来，新式表示法比传统表示法要慢10~15%，对于某些坑爹的数据（对右子结点调用比较多的那种）可能慢得更多。此外，在下放标记的时候，传统表示法只需要知道结点下标就行了，而新式表示法必须同时知道结点的左右端点，这样在dm中就需要传递三个参数，从而要慢一些，当然，我们可以不用dm，直接在操作里面写标记下放。

posted @ 2012-12-01 12:11 Mato_No1 阅读(3332) | 评论 (2) | 编辑 收藏

【AHOI2013复仇】再看HDU2871

原题地址
本沙茶去年曾经用双线段树的方法捉了这题（详见这里），最近重新审视这题发现，借助平衡树，可以得到更简单的方法。

题目大意：
有一个长度为N的内存条，每个位置的状态有占用和不占用两种，有4种操作：
（1）Reset：清空所有内存（即将所有位置的状态改为不占用，删除所有内存块）；
（2）New x：申请一个新的内存块，即找到一个长度为x的连续不占用位置区间，将它们标记为占用，若有多个这样的区间，取最左边的，若木有输出Reject New；
（3）Free x：在已申请的内存块中，找到包含位置x的并释放（将该内存块删除，同时其占用的所有位置改为不占用），若木有内存块包含位置x，则输出Reject Free；
（4）Get x：找出已申请的内存块中，左起第x个，并输出其左端点；若已申请的内存块数目不足x个，则输出Reject Get。

可以发现，每个已经申请的内存块尽管代表一段区间，但仍然是独立的单位，因此，可以把内存块当成结点，用平衡树维护（关键字为内存块的左端点位置），New操作中内存块的插入与Free操作中内存块的删除均在此平衡树内进行，Reset操作只需要将整棵树销毁即可。
问题是，在New操作中，需要找到一个长度为x的连续不占用区间，而连续的不占用区间并不是独立的单位，因此需要使用线段树维护。在线段树中，需要维护<1>结点区间内最长连续不占用块的长度；<2>结点区间左端、右端连续不占用块的长度（否则无法维护<1>）；同时，由于在New操作中需要区间整体改占用，Free操作中又需要区间整体改不占用，所以应当支持整体改值的标记，对于Reset操作，只需要全部位置改不占用即可（不能重新建树！！）；

这样，利用一棵平衡树加一棵线段树，就可以得到一个很简单的方法了（代码量是双平衡树或双线段树的一半左右）；

这题的启示是，在解决数据结构统计类题的时候，到底选用什么样的数据结构，是有讲究的，因为它将直接影响到编程复杂度。一般来说，线段树比平衡树好写，但是对本题而言，双线段树反而不如平衡树加线段树好写，这是因为对于内存块使用平衡树维护比使用线段树维护更好。在以后做这种题的时候，要多想一下，找到简便方法。

posted @ 2012-11-25 14:54 Mato_No1 阅读(625) | 评论 (0) | 编辑 收藏

仅列出标题
共12页: 1 2 3 4 5 6 7 8 9 Last