C++博客-Yuan

hdu 3403 回文日期

_Yuan — Tue, 09 Aug 2011 02:33:00 GMT

摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->/**//* 求第k<=4000000个回文串的日期，不能有前置0 如10011001 形式为y... 阅读全文

_Yuan 2011-08-09 10:33 发表评论

hdu 3826

_Yuan — Sat, 06 Aug 2011 18:40:00 GMT

/*
    问n<=10^18是否能被一个数的平方整除
    将n分解为：p1p2pk  其中pi为素数，且pi<=pi+1（这里可以等于）
    若n能被一个数的平方整除，它肯定能被一个素因子的平方p^2整除，我们找到最小的这个p即可  ~~~
    1.如果p不是最后的素因子，在p之后的素数pi>=p，这时就有n>=p^3了，
       即p<=n^(1/3)，所以枚举n^(1/3)内的素数看是否p^2|n即可，而n^(1/3)<=10^6
    2.如果p是最后的素因子，所以n的形式就是p1p2p'p^2，而p'<=p，所以P'^3<=n，p'<=n^(1/3)
       所以可以先将n的这些素因子p1,p2,,p'给去掉，p'<=n^(1/3)，所以用n^(1/3)内的素数去除即可
       最后只剩下n'=p^2，通过判断一个数是否为完全平方数即可

    算法就是预处理10^6内的素数，用这些素数去除n，发现有p^2能整除的return即可
    否则判断剩下的这个n'是否为完全平方数，我是用二分判断的，加了double处理long long 溢出
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<iostream>
#include<cassert>

using namespace std;

bool isp[1000010];
int pr[300000], pn;

void init()
{
    for (int p = 2; p <= 1000000; p++) {
        if (!isp[p]) {
            pr[pn++] = p;
            for (long long j = (long long)p*p; j <= 1000000; j+= p) {
                isp[j] = 1;
            }
        }
    }
}

// n = p1p2pk

bool chk(long long n)
{
    for (int i = 0; i < pn && pr[i] <= n; i++) {
        if (n % pr[i] == 0) {
            n /= pr[i];
            if (n%pr[i] == 0) return 0;
        }
    }
    if (n == 1) {
        return 1;
    }
    long long left = 1, right = n;
    while (left <= right) {
        long long mid = (left + right) / 2;
        if ((double)mid*mid > n) right = mid - 1;//double !!
        else left = mid+1;
    }
    return right*right != n;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    init();
    int T, t = 1;
    for (scanf("%d", &T); T--; ) {
        printf("Case %d: ", t++);
        long long n;
        scanf("%I64d", &n);
        puts(chk(n) ? "Yes" : "No");
    }
    return 0;
}

_Yuan 2011-08-07 02:40 发表评论

zoj 3512 左偏树思维中位数

_Yuan — Wed, 03 Aug 2011 09:35:00 GMT

/*
    给出n<=50000个数的序列a[1]..a[n]，求一个非递减的序列b[1]..b[n]
    使得∑|a[i]-b[i]|最小

    如果只是求一个点x，使得∑|a[i]-b[i]|最小，显然x = a[(n+1)/2]（中位数）---------------OMG
    但现在可以有多个点，如果a[]是递增的，那么令b[i] = a[i]即可了
    现在a[]是无规律的

    左偏树的论文题，看了论文还不完全懂
    做法：
    最后答案的形式是将1..n分成m个连续的区间，每个区间的b[i]是一样的，且不同区间是非递减的
    在检查n时，假设1..n-1已经分成了m个区间了
    现在先把a[n]单独一个区间，显然b[n]=a[n]会是1..n的最优值（因为前面1..n-1是最优的，而第n个
    对答案的贡献为0），但是不一定满足b[n-1]<=b[n]，算法为：
    若b[n-1] <= b[n]，则b[n]就是a[n]了
    否则，需要合并目前最尾的两个区间，直至这两个区间有b[k] <= b[k+1]              -------OMG
    而b[k]显然是每一个区间的中位数了
    合并两个区间求中位数，可用左偏树做最大堆分别维护每个区间的前(ni+1)/2小的数，-------OMG
    则堆顶为每个    区间的中位数了，合并时，将右边区间的那些数合并到左边即可
    O(nlogn)
    左偏树真是神奇漂亮的东西!!

    至于为什么是合并最后两个区间，将第n个数和它之前那个区间的一部分数合起来不行吗？
    假设a[kn-1]是求出来的一个区间，则肯定有a[n-1]     同理，a[n]     即a[k..k'], a[k'..n]，这样也不行，由假设知，肯定a[k'..n]的中位数     （大于的话，a[k'+1..n-1]就不会合并到那里去啦~~）
*/
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<set>
#include<list>
#include<numeric>
#include<cassert>
#include<sstream>
#include<ctime>
#include<bitset>
#include<functional>

using namespace std;

const int MAXN = 100010;

struct Node
{
    int key, dist, lc, rc;
};

Node nodes[MAXN];
int alloc;

void initNode()
{
    nodes[0].dist = -1;//0作为NULL节点
    alloc = 1;
}

int newNode(int x)
{
    nodes[alloc].key = x;
    nodes[alloc].dist = 0;
    nodes[alloc].lc = nodes[alloc].rc = 0;
    return alloc++;
}

int merge(int A, int B)
{
    if (A != 0 && B != 0) {
        if (nodes[A].key < nodes[B].key) {//
            swap(A, B);
        }
        nodes[A].rc = merge(nodes[A].rc, B);
        int &lc = nodes[A].lc;
        int &rc = nodes[A].rc;
        if (nodes[lc].dist < nodes[rc].dist) {
            swap(lc, rc);
        }
        nodes[A].dist = nodes[rc].dist + 1;
    } else {
        A = A == 0 ? B : A;
    }
    return A;
}

int pop(int A)
{
    int t = merge(nodes[A].lc, nodes[A].rc);
    nodes[A].lc = nodes[A].rc = 0;//隔离出A后记得将A的儿子也清空
    return t;
}

int a[MAXN];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif

    for (int n;scanf("%d", &n), n; ) {
        initNode();
        stack<pair<int,int> > S;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            pair<int, int> np(newNode(a[i]), 1);//node, len
            while (!S.empty() && nodes[S.top().first].key > nodes[np.first].key) {
                pair<int,int> top = S.top();
                S.pop();
                int n1 = top.second, n2 = np.second;
                np.first = merge(top.first, np.first);
                np.second = n1+n2;
                if ((n1+1)/2 + (n2+1)/2 > (n1+n2+1)/2) {
                    np.first = pop(np.first);
                }
            }
            S.push(np);
        }
        long long ans = 0;
        int id = n;
        while (!S.empty()) {
            int b = nodes[S.top().first].key, num = S.top().second;
            S.pop();
            while (num -- > 0) {
                ans += abs(a[id--] - b);
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

_Yuan 2011-08-03 17:35 发表评论

ural 1720

_Yuan — Mon, 01 Aug 2011 15:14:00 GMT

/*
    为[l,r]区间内有多少个数是区间[x,y]中的数的和
    1 <= x, y, l, r <= 10^8     x <=y, l <= r

    如果范围没这么大的话，对[x,y]这y-x+1个物品进行完全背包，找出覆盖了那些位置
    现在数据这么大，背包不可行
    但是，注意到[x,y]这是一个连续的区间，可以算出他们会覆盖的数是：
    [x,y] , [2x,2y]  [kx, ky]
    这样的话，我们要找满足[l,r]中的数，只要用f[r] - f[l-1]
    f[x]表示[1,x]中被上面那些数覆盖的个数

    要注意的是，有可能[(k-1)x, (k-1)y]与[kx,ky]有重叠部分（即(k-1)y>=kx）
    只要一开始重叠了，之后的所有点都会被覆盖了

    数据比较大，有些判断需要用double
*/
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<set>
#include<list>
#include<numeric>
#include<cassert>
#include<sstream>
#include<ctime>
#include<bitset>
#include<functional>

using namespace std;

long long gao(long long x, long long y, long long z, long long k)
{
    long long l = 0, r = z;
    while (l <= r) {//find first l*y >= z
        long long m = (l+r)/2;
        if ((double)m*y < z) l = m+1;//要用double
        else r = m-1;
    }
    long long ans = 0;
    //[x,y] [2x,2y]  [(l-1)x, (l-1)y], [lx, ly]
    if (l >= k) {
        ans = (y-x)*(k-1)*k/2 + (k-1) + (k*x > z ? 0 : z-k*x+1);
    } else {
        ans = (y-x)*(l-1)*l/2 + (l-1) + (l*x > z ? 0 : z-l*x+1);
    }
    return  ans;
}

int main()
{
#ifndef ONLINE_JUDGE
    //freopen("in.txt","r",stdin);
#endif
    for (long long x, y, l, r; cin>>x>>y>>l>>r; ){
        if (r < x ) {
            cout<<0<<endl;
            continue;
        }
        if (x == y) {
            cout<<r/x - (l-1)/x << endl;
            continue;
        }
        long long lk = 1, rk = y;
        while (lk <= rk) {
            long long mk = (lk+rk)/2;
            //要用double
            if ((double)mk*x > ((double)mk-1)*y) lk = mk + 1;
            else rk = mk-1;
        }
        //[rk*x, oo)

        cout<<gao(x, y, r, rk) - gao(x, y, l-1, rk)<<endl;
    }
    return 0;
}

_Yuan 2011-08-01 23:14 发表评论

zoj 3511 走出一个最小的环

_Yuan — Sun, 31 Jul 2011 18:09:00 GMT

/*
    一个凸多边形n<=10000，cut了m次，每一刀不相交
    求边数最多那块的边数

    这题用错误的做法搞了很久，浪费大量时间，囧
    然后洗澡时想到了可以通过每次找一个“最小的环”来做
    类似：
    http://watashi.ws/blog/970/andrew-stankevich-3-solution/
    zoj 2361
    上面这题十分推荐！！！

    上面那题是按照极角排序，不过这题可以按照点的编号排序即可

    多边形的顶点看成图的顶点，多边形的边是边，cut也看成边（双向的边）
    建好图后，对每个点找它所在的环（可能多个）
    比如现在已经有边pre->now，那么就在now的邻接边中找第一个比pre小的点
    （没有的话，就最大那个）
    这样，走出的环就是最小的了（也即环内没有边）
    画个图就清楚了
    8 4
    2 8
    2 4
    4 6
    6 8
*/
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<set>
#include<list>
#include<numeric>
#include<cassert>
#include<sstream>
#include<ctime>
#include<bitset>
#include<functional>

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 10086;

vector<int> e[MAXN];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif

    for (int N, M; ~scanf("%d%d", &N, &M); ) {
        for (int i = 1; i <= N; i++) {
            e[i].clear();
            e[i].push_back(i == N ? 1 : i+1);
            //e[i].push_back(i == 1 ? N : i-1);这条边不用加
        }
        int x, y;
        for (int i = 0; i < M; i++) {
            scanf("%d%d", &x, &y);
            if (x > y) swap(x, y);
            //双向的边
            e[x].push_back(y);
            e[y].push_back(x);
        }
        for (int i = 1;  i <= N; i++) {
            sort(e[i].begin(), e[i].end());
        }
        int ans = 0;
        for( int i = 1; i <= N; i++) {
            //cout<
            for (vector<int>::iterator it = e[i].begin(), jt; it != e[i].end(); ) {
                int pre = i, now = *it, len = 1;
                //每次在now中寻找第一个小于pre的，这样就是最小的环了，类似极角最小
                while (now != i) {
                    //cout<
                    len ++;
                    jt = lower_bound(e[now].begin(), e[now].end(), pre);
                    //不能写成--jt < e[now].begin()，因为--jt不再属于e[now]的范围了
                    if (jt == e[now].begin()) {
                        jt = --e[now].end();
                    } else jt --;
                    pre = now;
                    now = *jt;
                    e[pre].erase(jt);
                }
                it = e[i].erase(it);
                //cout<
                ans = max(ans, len);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

_Yuan 2011-08-01 02:09 发表评论

zoj 1039 博弈dp

_Yuan — Thu, 28 Jul 2011 16:43:00 GMT

/*
    博弈游戏
    2到20的数，两个人轮流取
    取数不能取之前已取过数的倍数，或之前取过的两个数的倍数之和
    给出当前的一个合法局面，问先手要赢的策略

    n<=20，比较明显的mask dp
    dp[mask]表示剩下mask表示的数，当前下手是赢还是输

    注意的是，多case，但是只算一次就行了，不用每个case都clear dp[]
    因为知道了当前局面，就能确定之前选了什么数了
*/
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<set>
#include<list>
#include<numeric>
#include<cassert>
#include<sstream>
#include<ctime>
#include<bitset>
#include<functional>

using namespace std;

char dp[1<<20];

void add(int &forbiden, int &multiple, int x)//forbiden为不能的位，multiple为之前选的那些数的倍数的位
{
    for (int a = x; a <= 20 ; a += x) {
        forbiden |= 1<<a;
        multiple |= 1<<a;
        forbiden |= multiple<<a;
    }
}

bool win(int mask, int forbiden, int multiple, int x)
{
    if (mask == 0) {
        dp[mask] = -1;
        return false;
    }
    if(dp[mask]) {
        return dp[mask] > 0;
    }
    add(forbiden, multiple, x);
    for (int i = 2; i <= 20; i++) {
        if((mask & (1<<i-2)) == 0 || (forbiden&(1<<i)) )continue;
        if (!win(mask ^ (1<<i-2), forbiden, multiple, i) )  {//这里提前退出了，有些子状态并没有算到
            return dp[mask] = 1;
        }
    }
    dp[mask] = -1;
    return 0;
}

int main()
{
#ifndef ONLINE_JUDGE
    //freopen("in","r",stdin);
    //freopen("out","w",stdout);
#endif

    int T, t = 1, n;
    for (scanf("%d", &T); T--; ) {
        printf("Scenario #%d:\n", t++);
        scanf("%d", &n);
        vector<int> vt, have;
        int vi[30] = {0}, mask = 0;
        for (int i = 1,x; i <= n; i++) {
            scanf("%d", &x);
            vt.push_back(x);
            vi[x] = 1;
            mask |= 1<<(x-2);//
        }
        int forbiden = 0, multiple = 0;
        for (int i = 2; i <= 20; i++) {//给出一个数，肯定给出他的所有因子
            if (vi[i] || (forbiden & (1<<i)) ) continue;
            add(forbiden, multiple, i);
        }
    //    fill(dp, dp+mask+1, 0);   不用每次都clear
        /*
            不要搞一次win(mask)
            然后取dp[mask ^ (1<            所以有些dp[mask']没算到，会为0
            不过取win(mask ^ (1<        */
        vector<int> ans;
        for (int i = 0; i < vt.size(); i++) {
            if (!win(mask^(1<<vt[i]-2), forbiden, multiple, vt[i])) {
                ans.push_back(vt[i]);
            }
        }
        if(ans.empty()) {
            puts("There is no winning move.");
        } else {
            printf("The winning moves are:");
            sort(ans.begin(), ans.end());
            for (int i = 0; i < ans.size(); i++) {
                printf(" %d", ans[i]);
            }
            puts(".");
        }
        puts("");
    }
    return 0;
}

_Yuan 2011-07-29 00:43 发表评论

poj 3373 状态的设计

_Yuan — Tue, 26 Jul 2011 13:36:00 GMT

摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->/**//* 可改变数字串A的每一位，串A的长度n<=100 求改变出的新串（不能有前缀0），需要是x&l... 阅读全文

_Yuan 2011-07-26 21:36 发表评论

Spoj 1479 最小直径生成树

_Yuan — Wed, 20 Jul 2011 17:12:00 GMT

摘要: Amber <> 半径只需计算这些相邻点Li，即为最优值了在这之前，需要去除掉一些点，只保留最外层的那些，才能有上面那样子交点 Code highlighting produced by Actipro CodeHighlighter (freeware)http://w... 阅读全文

_Yuan 2011-07-21 01:12 发表评论

ural 1577 E-mail

_Yuan — Mon, 18 Jul 2011 13:09:00 GMT

/*
    给出两个串A,B <=2000，构造一个新串，使得该新串的子序列是A,B，且长度最短
    求新串的方案数
    显然是最小长度n+m-lcs

    比赛时，我错误做法是对相邻匹配点中间的字符进行排列，如
    abcd
    aefd
    就固定a,d，中间的b,c,e,f排列，当然需要b在c前，e在f前
    但这种做法遇到多个匹配点时就有问题了，如
    be
    babo
    上面的b可以跟下面两个匹配，直接像上面那样子排列会有重复的问题
    当时局限在上面的思路，没搞出.

    其实不难，直接dp即可
    dp[i,j]表示以A[i]或者B[j]结尾的串的个数

    如果A[i] = B[j]，则dp[i,j] = dp[i-1,j-1]   因为这时必须匹配A[i],B[j]
    否则，lcs[i-1,j] > lcs[i,j-1] 则dp[i,j] = dp[i-1,j]   这时新串肯定是A[i]结尾，因为取的是dp[i-1,j]
           lcs[i-1,j] < lcs[i,j-1] 则dp[i,j] = dp[i,j-1]      这时新串肯定是B[i-1]结尾
           lcs[i-1,j] = lcs[i,j-1] 则dp[i,j] = dp[i-1,j] +dp[i,j-1]  这时新串可以是A[i]或B[j]结尾，但不会重复，因为尾部不同

    坑得，当时比赛时，没想打如果取dp[i-1,j]，自然是以A[i]结尾的！！！
    结尾不同，不会导致重复计数的！！
    用组合数学的方法算时，不清楚尾部是什么
*/
#include<cstdio>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<vector>
#include<bitset>
#include<set>
#include<cstring>
#include<string>
#include<stack>
#include<cassert>
#include<sstream>
#include<list>
#include<algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 2010;
const int MOD = 1000000007;

int dp[MAXN][MAXN], lcs[MAXN][MAXN];
char A[MAXN], B[MAXN];

int main()
{
    //freopen("in","r", stdin);
    //freopen("out","w", stdout);
    while (~scanf("%s%s", A+1, B+1)) {
        int n = strlen(A+1);
        int m = strlen(B+1);
        memset(dp, 0, sizeof dp);
        memset(lcs, 0, sizeof lcs);
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i <= m; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m;j ++) {
                if (A[i] == B[j]) {
                    lcs[i][j] = lcs[i-1][j-1]+1;
                    dp[i][j] = dp[i-1][j-1];
                } else if (lcs[i-1][j] > lcs[i][j-1]) {
                    lcs[i][j] = lcs[i-1][j];
                    dp[i][j] = dp[i-1][j];
                } else if (lcs[i-1][j] < lcs[i][j-1]) {
                    lcs[i][j] = lcs[i][j-1];
                    dp[i][j] = dp[i][j-1];
                } else {
                    lcs[i][j] = lcs[i-1][j];
                    dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;
                }
            }
        //cout<
        cout<<dp[n][m]<<endl;
    }
    return 0;
}

_Yuan 2011-07-18 21:09 发表评论

poj 3274 保存相对值

_Yuan — Sat, 16 Jul 2011 02:40:00 GMT

/*
    n个数，求最长的连续一段，使得这一段数字，二进制中每一位拥有1的那些数字的个数相等
    n<=10^5，位数k<=30
    如
    7 2 1 4 这里每一位1都有2个数字拥有

    容易想到先预处理出sum[n,k]表示前面n个数字中在第k位是1的个数
    这k个数字sum[n,k]的样子就是曲线形的，如sum[i,k]为
     _   /\
    /  \/   \_/\
    为了使得sum[i,k] - sum[j,k]对所有k都是同一个数
    则sum[j,k]的样子也必须是这样的，这样sum[i,k] - sum[j,k]才是一个同一个数（类似拼接时图形需吻合）
    好了，所以我们需要保存这个图形，可以通过保存a[i,k] = sum[i,k] - sum[i,0]即可（即保存相对值）    -----OMG

    我一开始用map, int>， vector是保存图形，int是保存第一次出现的地方
    在for到i时，计算出图形，在map中找有没出现过，有的话就更新答案为i-mp[vt]
    vector是有重载比较运算符的，所以不用写其他
    但是超时了，我在本机测貌似不会超时  --||

    看了解题报告，方法一样，但是不是用map，是最后sort一次的
    对哦，我想起之前也有一道题，又不需要每个i都输出结果，不用map，直接最后sort一次更好
    用map会慢一点

    但这样还超时，原来是vector的比较比较慢
    自己写了个struct Node {int vt[30];}; 再重载比较过了

    sort时，可以对下标排序，减少了大数据移动

    这题官方有另外解法，就是对数组vt[30] hash
    好的hash函数会快很多吧
    hsize=997001;
    for(p=0,i=0;i         p=((p<<2)+(v[i]>>4))^(v[i]<<10);
    p=p%hsize;
    if(p<0)    p+=hsize;
*/
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<set>
#include<list>
#include<numeric>
#include<cassert>
#include<sstream>
#include<ctime>
#include<bitset>
#include<functional>

using namespace std;

const int MAXN = 100100;

int n, k;

struct Node
{
    int vt[30];
    void clear()
    {
        memset(vt, 0, sizeof vt);
    }
};

bool operator < (const Node &A, const Node &B) //直接用vector的比较会慢  可能数据太大吧
{
    for (int i = 0; i < k - 1; i++) {
        if (A.vt[i] != B.vt[i]) {
            return A.vt[i] < B.vt[i];
        }
    }
    return false;
}

pair<Node, int> all[MAXN];

inline bool cmp(const int &a, const int &b)
{
    return all[a] < all[b];
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
#endif

    for (; ~scanf("%d%d", &n, &k); ) {
    //    long long start = clock();
        vector<int> vt(k-1), pos(n+1);
        all[0].first.clear();//don't forget to push k-1 zeros
        all[0].second = 0;
        pos[0] = 0;

        vector<int> sum(k);
        for (int i = 1, x; i <= n; i++) {
            scanf("%d", &x);
            for (int j = 0; j < k; j++) {
                sum[j] += (x>>j) & 1;
                if (j > 0) {
                    all[i].first.vt[j-1] = sum[j] - sum[j-1];
                }
            }
            all[i].second = i;
            pos[i] = i;
        }
        sort(pos.begin(), pos.end(), cmp);
        int ans = 0;
        for (int i = 1, last = 0; i <= n+1; i++) {
            if (i == n+1 ||  all[pos[i-1]].first < all[pos[i]].first) {
                ans = max(ans, all[pos[i-1]].second - all[pos[last]].second);
                last = i;
            }
        }
        printf("%d\n", ans);
    //    cout<<"time   "<
    }
    return 0;
}

_Yuan 2011-07-16 10:40 发表评论