精品久久久无码人妻中文字幕,亚洲精品国精品久久99热,成人精品一区二区久久

hdu 3403 回文日期

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

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

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

hdu 3826

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

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

    ��法��是预处�?0^6内的素数�Q�用�q�些素数去除n�Q�发现有p^2能整除的return卛_��
    否则判断剩下的这个n'是否为完全��^�Ҏ��Q�我是用二分判断的，加了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 发表评论

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

/*
    �l�出n<=50000个数的序列a[1]..a[n]�Q�求一个非递减的序列b[1]..b[n]
    使得∑|a[i]-b[i]|最��?br />
    如果只是求一个点x�Q��?#8721;|a[i]-b[i]|最��，昄��x = a[(n+1)/2]�Q�中位数�Q?--------------OMG
    但现在可以有多个点，如果a[]是递增的，那么令b[i] = a[i]卛_��?br />     现在a[]是无规律�?br />
    左偏树的论文题，看了论文�q�不完全�?br />     做法�Q?br />     最后答案的形式是将1..n分成m个连�l�的区间�Q�每个区间的b[i]是一��L��Q�且不同区间是非递减�?br />     在检查n�Ӟ��假设1..n-1已经分成了m个区间了
    现在先把a[n]单独一个区��_��昄��b[n]=a[n]会是1..n的最优��|��因�ؓ前面1..n-1是最优的�Q�而第n�?br />     对答案的贡献�?�Q�，但是不一定满��b[n-1]<=b[n]�Q�算法�ؓ�Q?br />     若b[n-1] <= b[n]�Q�则b[n]��是a[n]�?br />     否则�Q�需要合�q�目前最��两个区间�Q�直臌��两个区间有b[k] <= b[k+1]              -------OMG
    而b[k]昄��是每一个区间的中位��C��
    合�ƈ两个区间求中位数�Q�可用左偏树做最大堆分别�l�护每个区间的前(ni+1)/2��的敎ͼ�-------OMG
    则堆��ؓ每个    区间的中位数了，合�ƈ�Ӟ��右边区间的那些数合�q�到左边卛_��
    O(nlogn)
    左偏树真是神奇漂亮的东西!!

    至于��Z��么是合�ƈ最后两个区��_��第n个数和它之前那个区间的一部分数合��h��不行吗？
    假设a[kn-1]是求出来的一个区��_��则肯定有a[n-1]     同理�Q�a[n]     即a[k..k'], a[k'..n]�Q�这样也不行�Q�由假设知，肯定a[k'..n]的中位数     �Q�大于的话，a[k'+1..n-1]��׃��会合�q�到那里��d��~~�Q?br /> */
#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]中的数的�?br />    1 <= x, y, l, r <= 10^8     x <=y, l <= r

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

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

    数据比较大，有些判断需要用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 发表评论

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

/*
    一个凸多边形n<=10000�Q�cut了m�ơ，每一刀不相�?br />    求边数最多那块的�Ҏ��

    �q�题用错误的做法搞了很久�Q�浪费大量时��_��?img src="http://www.shnenglu.com/Images/dot.gif" alt="" />
    然后�z��M时想��C��可以通过每次找一�?#8220;最��的�?#8221;来做
    �c�M��Q?br />    http://watashi.ws/blog/970/andrew-stankevich-3-solution/
    zoj 2361
    上面�q�题十分推荐�Q�！�Q?br />
    上面那题是按照极角排序，不过�q�题可以按照点的�~�号排序卛_��

    多边形的��点看成囄��点�Q�多边�Ş的边是边�Q�cut也看成边�Q�双向的边）
    建好囑֐��Q�对每个�Ҏ��它所在的环（可能多个�Q?br />    比如现在已经有边pre->now�Q�那么就在now的邻接边中找�W�一个比pre��的�?br />    �Q�没有的话，��最大那个）
    �q�样�Q�走出的环就是最��的了（也即环内没有边）
    ��M��囑ְ�清楚�?br />    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);�q�条边不用加
        }
        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的，�q�样��是最��的环了�Q�类似极角最��?/span>
                while (now != i) {
                    //cout<
                    len ++;
                    jt = lower_bound(e[now].begin(), e[now].end(), pre);
                    //不能写成--jt < e[now].begin()�Q�因�?-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�?0的数�Q�两个�h轮流�?br />    取数不能取之前已取过数的倍数�Q�或之前取过的两个数的倍数之和
    �l�出当前的一个合法局面，问先手要赢的�{�略

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

    注意的是�Q�多case�Q�但是只��一�ơ就行了�Q�不用每个case都clear dp[]
    因�ؓ知道了当前局面，��p��定之前选了什么数�?br />*/
#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��Z��能的位，multiple��Z��前选的那些数的倍数的位
{
    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) )  {//�q�里提前退��Z��Q�有些子状态�ƈ没有��到
            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++) {//�l�出一个数�Q�肯定给��Z��的所有因�?/span>
            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�Q�，需要是x&l... 阅读全文

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

Spoj 1479 最��直径生成树

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

摘要: Amber <> 半径只需计算�q�些盔R��点Li�Q�即为最优��g�� 在这之前�Q�需要去除掉一些点�Q�只保留最外层的那些，才能有上面那样子交点 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

/*
    �l�出两个串A,B <=2000�Q�构造一个新�Ԍ��使得该新串的子序列是A,B�Q�且长度最�?br />     求新串的�Ҏ��?br />     昄��是最��长度n+m-lcs

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

    其实不难�Q�直接dp卛_��
    dp[i,j]表示以A[i]或者B[j]�l�尾的串的个�?br />
    如果A[i] = B[j]�Q�则dp[i,j] = dp[i-1,j-1]   因�ؓ�q�时必须匚w��A[i],B[j]
    否则�Q�lcs[i-1,j] > lcs[i,j-1] 则dp[i,j] = dp[i-1,j]   �q�时��C��肯定是A[i]�l�尾�Q�因为取的是dp[i-1,j]
           lcs[i-1,j] < lcs[i,j-1] 则dp[i,j] = dp[i,j-1]      �q�时��C��肯定是B[i-1]�l�尾
           lcs[i-1,j] = lcs[i,j-1] 则dp[i,j] = dp[i-1,j] +dp[i,j-1]  �q�时��C��可以是A[i]或B[j]�l�尾�Q�但不会重复�Q�因为尾部不�?br />
    坑得�Q�当时比赛时�Q�没��x��如果取dp[i-1,j]�Q�自然是以A[i]�l�尾的！�Q�！
    �l�尾不同�Q�不会导致重复计数的�Q�！
    用组合数学的�Ҏ��时�Q�不清楚��N��是什�?img src="http://www.shnenglu.com/Images/dot.gif" alt="" />
*/
#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 发表评论

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

/*
    n个数�Q�求最长的�q�箋一�D�，使得�q�一�D�|��字，二进制中每一位拥�?的那些数字的个数相等
    n<=10^5�Q�位数k<=30
    �?br />     7 2 1 4 �q�里每一�?都有2个数字拥�?br />
    �Ҏ��惛_��先预处理出sum[n,k]表示前面n个数字中在第k位是1的个�?br />     �q�k个数字sum[n,k]的样子就是曲�U��Ş的，如sum[i,k]�?nbsp;
     _   /\
    /  \/   \_/\
    ��Z��使得sum[i,k] - sum[j,k]�Ҏ��有k都是同一个数
    则sum[j,k]的样子也必须是这��L��Q�这样sum[i,k] - sum[j,k]才是一个同一个数�Q�类似拼接时囑�Ş需��d��Q?br />     好了�Q�所以我们需要保存这个图形，可以通过保存a[i,k] = sum[i,k] - sum[i,0]卛_��Q�即保存相对��|��    -----OMG

    我一开始用map, int>�Q?nbsp;vector是保存图形，int是保存第一�ơ出现的地方
    在for到i�Ӟ��计算出图形，在map中找有没出现�q�，有的话就更新�{�案为i-mp[vt]
    vector是有重蝲比较�q�算�W�的�Q�所以不用写其他
    但是��时了，我在本机��貌��g��会超�?img src="http://www.shnenglu.com/Images/dot.gif" alt="" />  --||

    看了解题报告�Q�方法一��P��但是不是用map�Q�是最后sort一�ơ的
    对哦�Q�我惌��v之前也有一道题�Q�又不需要每个i都输出结果，不用map�Q�直接最后sort一�ơ更�?br />     用map会慢一�?br />
    但这栯��时�Q�原来是vector的比较比较慢
    自己写了个struct Node {int vt[30];}; 再重载比较过�?br />
    sort�Ӟ��可以对下标排序，减少了大数据�U�d��

    �q�题官方有另外解法，��是�Ҏ��l�vt[30] hash
    好的hash函数会快很多�?br />     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的比较会�?img src="http://www.shnenglu.com/Images/dot.gif" alt="" />  可能数据太大�?/span>
{
    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 发表评论