STEP BY STEP

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.4k 阅读时长 ≈ 1 分钟

裸的字符串匹配，子串最长10,000，母串最长1,000,000。
求子串在母串中出现的次数。
如果子串长度较小，那么直接RK匹配即可，hash值相同时候，直接比较字符串是否相同。
但是这个题的子串太长了，还比较字符串会超时，如果不比较字符串理论上是错误的，虽然
出错的概率很小，而且概率还是跟模数的选择以及运算时候是否溢出有关。
刚开始用了int，发现一直wa了，估计就是运算时候就超int了，取模没起到作用。模数的选
择能够提高正确率。Rabin-Karp 字符串匹配虽然比较好写，也很容易理解，但是适用情况感
觉不是很广，比如子串太长了，处理就麻烦了，舍弃子串比较也不是很好。
但是子串不长的话，Rabin-Karp 字符串匹配还是很不错的。
相比而言，这个题用kmp应该会好很多。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;

typedef long long INT;
char szStrM[1000010];
char szStrS[10010];
const INT MOD = 16381 * 4733 + 1;

int main()
{
    int nT;

    scanf("%d", &nT);
    while (nT--)
    {
        scanf("%s%s", szStrS, szStrM);
        INT nMatch = szStrS[0] - 'A';
        INT nPowN = 1;
        int nSizeS = 1;
        char* pszStr = szStrS + 1;
        while (*pszStr)
        {
            nMatch = (26 * nMatch + *pszStr - 'A') % MOD;
            nPowN = (nPowN * 26) % MOD;
            ++nSizeS;
            ++pszStr;
        }
        //prINTf("match:%d\n", nMatch);

        int nSizeM = strlen(szStrM);
        INT nKey = 0;
        for (int i = 0; i < nSizeS; ++i)
        {
            nKey = (26 * nKey + szStrM[i] - 'A') % MOD;
        }
        //prINTf("key:%d\n", nKey);

        int nAns = 0;
        for (int i = 0; i <= nSizeM - nSizeS; ++i)
        {
            //prINTf("key:%d\n", nKey);
            if (nKey == nMatch)
               //  memcpy(szStrS, szStrM + i, nSizeS) == 0)
            {
                ++nAns;
            }
            nKey = (26 * (nKey - nPowN * (szStrM[i] - 'A')) % MOD
                    + szStrM[i + nSizeS] - 'A') % MOD;
            nKey = (nKey + MOD) % MOD;
        }

        printf("%d\n", nAns);
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.6k 阅读时长 ≈ 1 分钟

这个题是求一个字符串里面出现了多少个长度为N的不同子串，同时给出了母串里面不同字符
的个数NC。
保存子串到set里面直接暴力肯定超时了。这个题有个利用字符串hash的解法，虽然理论上有
bug，但是能过这个题。
利用给出的NC，对长度为N的字符串，将其当作NC进制的数字，求出其值，对值进行hash，
求出不同的hash位置个数。
这个算法其实类似于Karp-Rabin字符串匹配算法。不过，Karp-Rabin算法做了点改进，对
进制为D的字符串求值的时候为了防止溢出会模一个素数，而且不会每次都迭代求下一个子串的
值，而是从当前子串的值直接递推出下一个字符的值。怎么递推了，其实很简单，就是当前值去
掉最高位再乘以D(相当于左移一位,不过是D进制的，不能直接用<<符号)，再加上新的最低位。
Karp-Rabin算法应该主要在于设计出合理的hash算法，比如，用取模hash函数的话，得保
证hash表足够大，否则冲突太多，速度就不会怎么好了。比如这个题，hash表小了就AC不了了。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <stdio.h>
#include <string.h>

const int MAX = 13747347;
int nHash[MAX];
char szStr[17000001];
int nN, nNC;
int nW[200];

void Insert(int nKey)
{
    int nPos = nKey;
    while (nHash[nPos] != -1  nHash[nPos] != nKey)
    {
        nPos = (nPos + 1) % MAX;
    }
    nHash[nPos] = nKey;
}

bool Find(int nKey)
{
    int nPos = nKey;
    while (nHash[nPos] != -1 && nHash[nPos] != nKey)
    {
        nPos = (nPos + 1) % MAX;
    }
    return nHash[nPos] != -1;
}

int main()
{
    while (scanf("%d%d%s", &nN, &nNC, szStr) == 3)
    {
        memset(nW, 0, sizeof(nW));
        memset(nHash, -1, sizeof(nHash));
        int nNum = 0;
        int nSize = 0;
        for (char* pszStr = szStr; *pszStr; ++pszStr)
        {
            if (!nW[*pszStr])
            {
                nW[*pszStr] = ++nNum;
            }
            ++nSize;
        }

        int nKey = 0;
        int nAns = 0;
        int nPowN = 1;
        for (int j = 0; j < nN; ++j)
        {
            nKey = (nKey * nNC + nW[szStr[j]]) % MAX;
            nPowN *= nNC;
        }
        nPowN /= nNC;
        if (!Find(nKey))
        {
            Insert(nKey);
            nAns++;
        }

        for (int i = nN; i < nSize; ++i)
        {
            nKey = (nNC * (nKey - nPowN * nW[szStr[i - nN]])
                    + nW[szStr[i]]) % MAX;
            nKey = (nKey + MAX) % MAX;

            if (!Find(nKey))
            {
                Insert(nKey);
                nAns++;
            }
        }

        printf("%d\n", nAns);
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.6k 阅读时长 ≈ 2 分钟

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
typedef unsigned long long LL;
#define MAX (5000000)
bool bPrime[MAX];
void InitPrime()
{
    int nMax = sqrt((double)MAX) + 1;
    bPrime[0] = bPrime[1] = true;
    for (int i = 2; i <= nMax; ++i)
    {
        if (!bPrime[i])
        {
            for (int j = 2 * i; j < MAX; j += i)
            {
                bPrime[j] = true;
            }
        }
    }
}
LL multAndMod(LL a, LL b, LL n)
{
    LL tmp = 0;
    while (b)
    {
        if(b & 1)
        {
            tmp = (tmp + a) % n;
        }
        a = (a << 1) % n;
        b >>= 1;
    }
    return tmp;
}
//计算a^u%n
LL ModExp(LL a, LL u, LL n)
{
    LL d = 1;
    a %= n;
    while (u)
    {
        if (u & 1)
        {
            d = multAndMod(d, a, n);
        }
        a = multAndMod(a, a, n);
        u >>= 1;
    }
    return d % n;
}
//判断nN是不是合数
bool Witness(LL a, LL nN)
{
    LL u = nN - 1, t = 0;//将nN-1表示为u*2^t
    while (u % 2 == 0)
    {
        t++;
        u >>= 1;
    }
    LL x0 = ModExp(a, u, nN);//x是a^u
    LL x1;
    for (int i = 1; i <= t; ++i)
    {
        x1 = multAndMod(x0, x0, nN);
        if (x1 == 1 && x0 != nN - 1 && x0 != 1)
        {
            return true;
        }
        x0 = x1;
    }
    if (x1 != 1)
    {
        return true;
    }
    return false;
}
//素数测试
bool MillerRabin(LL nN)
{
    //if (nN < MAX)return !bPrime[nN];
    const int TIME = 10;
    for (int i = 0; i < TIME; ++i)
    {
        LL a = rand() % (nN - 1) + 1;
        if (Witness(a, nN))
        {
            return false;
        }
    }
    return true;
}
LL gcd(LL a, LL b)
{
    if (a < b)swap(a, b);
    while (b)
    {
        LL t = a;
        a = b;
        b = t % b;
    }
    return a;
}
//启发式寻找nN的因子
LL PollardRho(LL n, LL c)
{
    LL i = 1, t = 2;
    LL x, y;
    LL ans;
    srand(time(NULL));  
    y = x = rand() % n;
    while(1)
    {
        i++;
        x = (multAndMod(x, x, n) + c) % n;
        ans = gcd(y - x, n);
        if(ans > 1 && ans < n)
            return ans;
        if(x == y)
            return n;
        if(t == i)
        {
            y = x;
            t <<= 1;
        }
    }
}
LL FindMin(LL nN, LL c)
{
    //printf("nN:%I64u\n", nN);
    if (MillerRabin(nN) || nN <= 1)
    {
        return nN;
    }
    LL p = nN;
    while (p >= nN) p = PollardRho(p, c--);
    if (p > 1)
        p = FindMin(p, c);//分解p的最小因子
    if (p < nN)
    {
        LL q = nN / p;
        q = FindMin(q, c);//找到q的最小因子
        p = min(p, q);
    }
    return p;
}
int main()
{
    int nTest;
    srand(time(NULL));
    //InitPrime();
    scanf("%d", &nTest);
    while (nTest--)
    {
        LL nN;
        scanf("%I64u", &nN);
        if (nN > 2 && nN % 2 == 0)
        {
            printf("2\n");
        }
        else if (nN == 2 || MillerRabin(nN))
        {
            printf("Prime\n");
        }
        else
        {
            printf("%I64u\n", FindMin(nN, 181));
        }
    }
    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 3.2k 阅读时长 ≈ 3 分钟

这是前天成都网赛的题，比赛时候确实一点思路也没有。比完之后看了人家的解题报告，还是不会怎么搜出答案，太弱了。
题意是给出N,K，求M，使得M是N的正倍数，而且M用K进制表示后所需要的不同数字(0,1,2,3,…,k-1)最少，如果有多组这样的情况，求出最小的M。很数学的题意。
用到了一个结论，就是任意数字的正倍数均可以用不超过2个不同数字的数得到。
证明如下：
任意数M % N 总共有N种结果，假如有N+1个不同的M，那么肯定有2个M对N取模后的结果是相同，这个是所谓鸽巢原理。那么，我取a,aa,aaa,…,aaaaaaaaaa….，总共N+1个，同样满足上面的结论。那么我取那2个对N取模相同的数字相减得到数字aaaaa…000….，这个数字肯定是N的倍数。
综合上面的证明，只能得到2个数字肯定能表示N的倍数。但是不能说形式就是aaaaa…000….。

到了这里我还是一点思路都没有，一点都不知道怎么搜索。。。
想了1个多小时，无头绪，问过了这题的同学，还是无头绪。看解题报告，他们的代码写得太牛了，完全看不懂，无头绪。也许也是我对bfs理解太浅，才看不懂他们的搜索代码。而且，我连可以搜索的地方都没有找到，都不知道搜什么了。
想了好久，昨天吃饭的时候，终于发现可以对余数进行搜索。
对于任意的N，其余数就是范围是[0, N -1]。这个其实就可以代表状态了，或者代表bfs中的点了。从当前余数转移到其它余数的是MOD K + A 或者 MOD K + B，如果要转移到得余数以前没被搜过，那就可以转移过去。这个刚好就是一个优化了。也可以看成是子问题了。但是，dfs完全不行。刚开始用dfs，绝对的超时。
用dfs也是我对思路理解不深，侥幸认为能过。。。后面发现，这题完全和bfs吻合。[0, N -1]刚好代表N个点，我要通过从外面的一个点，最短的遍历到点0，可以bfs或者最短路算法。这题我觉得还有个难点就是保存答案，因为答案最长的长度可能是N(N<=10000)，所以把答案直接放到节点里面肯定不行的。但是，我还仔细看过算法导论。因此想到了可以利用bfs搜索出来的那颗树或者最短路算法跑出来的那颗树，从目标节点逆序寻找答案，找到出发节点之后，再把答案reverse一下就行了。
这题还得注意0不能是N的倍数，所以注意bfs(0,i)这种情况的处理。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX_N = 10010;
int nOut[MAX_N];
int nOLen;
int nAns[MAX_N];
int nALen;
bool bMod[MAX_N];
int nFather[MAX_N];
int nChoose[MAX_N];
int nN;
int nK;
bool bFind;

int Cmp(int* A, int nLA, int* B, int nLB)
{
    if (nLA != nLB)
    {
        return nLA - nLB;
    }
    for (int i = 0; i < nLA; ++i)
    {
        if (A[i] != B[i])
        {
            return A[i] - B[i];
        }
    }
    return 0;
}

void Bfs(int nA, int nB)
{
    memset(bMod, false, sizeof(bMod));
    queue<int> que;
    que.push(0);
    int nTemp;
    bool bFirst = true;
    bFind = false;

    if (nA > nB)swap(nA, nB);
    //printf("nA:%d, nB:%d\n", nA, nB);
    while (!que.empty())
    {
        //printf("nMod:%d\n", que.front());
        int nMod = que.front();
        que.pop();
        if (nMod == 0)
        {
            if (bFirst)bFirst = false;
            else
            {
                bFind = true;
                break;
            }
        }

        nTemp = (nMod * nK + nA) % nN;
        if (!(nMod == 0  nA == 0)  !bMod[nTemp])
        {
            nFather[nTemp] = nMod;
            nChoose[nTemp] = nA;
            que.push(nTemp);
            bMod[nTemp] = true;
            //printf("nTemp:%d\n", nTemp);
        }
        if (nA == nB)continue;
        nTemp = (nMod * nK + nB) % nN;
        if (!bMod[nTemp])
        {
            nFather[nTemp] = nMod;
            nChoose[nTemp] = nB;
            que.push(nTemp);
            bMod[nTemp] = true;
            //printf("nTemp:%d\n", nTemp);
        }
    }

    if (bFind)
    {
        int nF = 0;
        nALen = 0;
        do
        {
            nAns[nALen++] = nChoose[nF];
            nF = nFather[nF];
        }
        while (nF);
        reverse(nAns, nAns + nALen);
    }
}

int main()
{
    while (scanf("%d%d", &nN, &nK) == 2)
    {
        bool bOk = false;
        nOLen = 0;
        for (int i = 1; i < nK; ++i)
        {
            Bfs(i, i);
            if (bFind)
            {
                if (nOLen == 0 || Cmp(nOut, nOLen, nAns, nALen) > 0)
                {
                    nOLen = nALen;
                    memcpy(nOut, nAns, sizeof(int) * nALen);
                }
                bOk = true;
            }
        }
        if (!bOk)
            for (int i = 0; i < nK; ++i)
            {
                for (int j = i + 1; j < nK; ++j)
                {
                    Bfs(i, j);
                    if (bFind)
                    {
                        if (nOLen == 0 || Cmp(nOut, nOLen, nAns, nALen) > 0)
                        {
                            nOLen = nALen;
                            memcpy(nOut, nAns, sizeof(int) * nALen);
                        }
                    }
                }
            }
        for (int k = 0; k < nOLen; ++k)
        {
            printf("%d", nOut[k]);
        }
        printf("\n");
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.4k 阅读时长 ≈ 2 分钟

用线段树成段更新不能立即全部更新，必须搞延迟操作。其实，就是针对每个节点，另外搞一个域表示延迟
更新的数目。然后，在更新操作和查找操作的时候都把父亲节点的延迟域往2个儿子走。
这个题是要成段增加值，所以在写PushDown函数的时候要注意，只能给儿子节点加上父亲节点压过来的值乘以儿子区间的长度。这题貌似用树状数组也可以做，不过解法肯定意思不是那么直白的。不过速度肯定会快。
树状数组解法：http://kenby.iteye.com/blog/962159
线段树网上流行的解法都是开最多节点数目4倍的数组。以位置1作为根，每个位置其实代表的是一个区间。某人位置1代表1-N或者0-(N-1)区间，具体看题目了。那么2就代表区间1-(1+N)/2，3就代表区间(1+N)/2+1 - N了。
至于lazy标记还是搞个大数组，意义和线段树数组一样，搞清楚之后写起来都比较简单，最重要的是变形来解决一些要求奇怪的题目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long INT;

const INT MAX_N = 100010;
const INT INF = 0x7ffffffffffffffLL;
INT nTree[MAX_N << 2];
INT nAdd[MAX_N << 2];
INT nN, nQ;

void PushUp(INT nRt)
{
    nTree[nRt] = nTree[nRt << 1] + nTree[nRt << 1 | 1];
}

void BuildTree(INT nL, INT nR, INT nRt)
{
    nAdd[nRt] = 0;
    if (nL == nR)
    {
        scanf("%I64d", nTree[nRt]);
        return;
    }

    INT nMid = (nL + nR) >> 1;
    BuildTree(nL, nMid, nRt << 1);
    BuildTree(nMid + 1, nR, nRt << 1 | 1);
    PushUp(nRt);
}

void PushDown(INT nL, INT nR, INT nRt)
{
    INT nMid = (nL + nR) >> 1;
    INT nLs = nRt << 1;
    INT nRs = nLs | 1;

    if (nAdd[nRt])
    {
        nAdd[nLs] += nAdd[nRt];
        nAdd[nRs] += nAdd[nRt];
        nTree[nLs] += (nMid - nL + 1) * nAdd[nRt];
        nTree[nRs] += (nR - nMid) * nAdd[nRt];
        nAdd[nRt] = 0;
    }
}

void Update(INT nL, INT nR, INT nRt, INT nX, INT nY, INT nV)
{
    if (nL >= nX && nR <= nY)
    {
        nTree[nRt] += nV * (nR - nL + 1);
        nAdd[nRt] += nV;
        return;
    }

    PushDown(nL, nR, nRt);
    INT nMid = (nL + nR) >> 1;
    if (nX <= nMid) Update(nL, nMid, nRt << 1, nX, nY, nV);
    if (nY > nMid) Update(nMid + 1, nR, nRt << 1 | 1, nX, nY, nV);
    PushUp(nRt);
}

INT Query(INT nL, INT nR, INT nRt, INT nX, INT nY)
{
    if (nL >= nX && nR <= nY)
    {
        return nTree[nRt];
    }
    PushDown(nL, nR, nRt);
    INT nAns = 0;
    INT nMid = (nL + nR) >> 1;
    if (nX <= nMid) nAns += Query(nL, nMid, nRt << 1, nX, nY);
    if (nY > nMid) nAns += Query(nMid + 1, nR, nRt << 1 | 1, nX, nY);
    return nAns;
}

int main()
{
    INT nTemp;
    while (scanf("%I64d%I64d", &nN, &nQ) == 2)
    {
        BuildTree(1, nN, 1);

        while (nQ--)
        {
            char szCmd[10];
            INT nX, nY, nV;
            scanf("%s", szCmd);
            if (szCmd[0] == 'Q')
            {
                scanf("%I64d%I64d", &nX, &nY);
                printf("%I64d\n", Query(1, nN, 1, nX, nY));
            }
            else
            {
                scanf("%I64d%I64d%I64d", &nX, &nY, &nV);
                Update(1, nN, 1, nX, nY, nV);
            }
        }
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.5k 阅读时长 ≈ 2 分钟

直接模拟约瑟夫环是N^2，况且这题每次移动的距离和方向都是不确定的，只能模拟，如果加快查找和移动的话，可以提高速度，果断用线段树维护当前位置前面有多少个人。
至于反素数指的是求一个小于等于N的数字，使得其因子个数在1-N中是最大的。这个利用一个必要条件暴力搜索即可。

其实就是利用下面这2个性质搜索的。 性质一:一个反素数的质因子必然是从2开始连续的质数。性质二:p=2^t13^t25^t3*7^t4…..必然t1>=t2>=t3>=….。

代码如下：</div>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;

int nPrime[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
int nAns;
int nCN;
const int MAX_N = 500010;
//nPow不会超过20
void InitBest(int nCur, int nI, int nMax, int nN, int nNum)
{
    if (nCur > nN) return;
    if (nNum > nCN){nAns = nCur;nCN = nNum;}
    if (nNum == nCN){nAns = min(nAns, nCur);}
    for (int i = 1; i <= nMax; ++i)
    {
        nCur *= nPrime[nI];
        if (nCur > nN)return;//不加这句优化会超时
        if (nI < 15)
        InitBest(nCur, nI + 1, i, nN, nNum * (i + 1));
    }
}

char szNames[MAX_N][10];
int nValue[MAX_N];
int nTree[MAX_N << 2];
void PushUp(int nRt)
{
    nTree[nRt] = nTree[nRt << 1] + nTree[nRt << 1 | 1];
}

void BuildTree(int nL, int nR, int nRt, int nV)
{
    if (nL == nR)
    {
        nTree[nRt] = nV;
        return;
    }
    int nMid = (nL + nR) >> 1;
    BuildTree(nL, nMid, nRt << 1, nV);
    BuildTree(nMid + 1, nR, nRt << 1 | 1, nV);
    PushUp(nRt);
}

void Add(int nL, int nR, int nRt, int nP, int nV)
{
    if (nL == nR)
    {
        nTree[nRt] += nV;
    }
    else
    {
        int nMid = (nL + nR) >> 1;
        if (nP <= nMid)Add(nL, nMid, nRt << 1, nP, nV);
        else Add(nMid + 1, nR, nRt << 1 | 1, nP, nV);
        PushUp(nRt);
    }
}

int Query(int nL, int nR, int nRt, int nSum)
{
    if (nL == nR)
    {
        return nL;
    }
    int nMid = (nL + nR) >> 1;
    int nLs = nRt << 1;
    int nRs = nLs | 1;
    if (nTree[nLs] >= nSum) return Query(nL, nMid, nLs, nSum);
    else return Query(nMid + 1, nR, nRs, nSum - nTree[nLs]);
}

int main()
{
    //InitBest(1, 0, 15);
    int nN, nK;

    while (scanf("%d%d", &nN, &nK) == 2)
    {
        nK--;
        nAns = 2;
        nCN = 0;
        InitBest(1, 0, 20, nN, 1);
        //printf("ans:%d cn:%d\n", nAns, nCN);
        for (int i = 0; i < nN; ++i)
        {
            scanf("%s%d", szNames[i], nValue[i]);
        }

        BuildTree(0, nN - 1, 1, 1);
        int nTotal = nN;
        int nPos;
        for (int i = 0; i < nAns; ++i)
        {
            nPos = Query(0, nN - 1, 1, nK + 1);
            //printf("nK:%d %s %d\n", nK, szNames[nPos], nValue[nPos]);
            nTotal--;
            Add(0, nN - 1, 1, nPos, -1);
            if (!nTotal)break;
            if (nValue[nPos] >= 0)
            {
                nK = (nK - 1 + nValue[nPos] + nTotal) % nTotal;
            }
            else
            {
                nK = ((nK + nValue[nPos]) % nTotal + nTotal) % nTotal;
            }
        }
        printf("%s %d\n", szNames[nPos], nCN);
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.4k 阅读时长 ≈ 1 分钟

此题是求一个数字序列中，长度为3的子序列(a,b,c)，且满足条件a<=b<=c或者c<=b<=a的子序列的个数。
明显枚举每个b，求每个b左边的a的个数和右边c的个数，以及左边c的个数和右边a的个数，然后累加左右乘积求和即可。刚开始只求了满足条件a<=b<=c的部分，而且忘记用64位了。wa了几次。求左边a的个数其实就是求小于等于b的数字的个数，这个刚好可以用树状数组或者线段树求。具体见代码。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long INT;
const INT MAX_N =  100010;
const INT N = 20010;
INT nN;
INT nNum[N];
INT nTree[MAX_N + 10];
INT nLeft[2][N], nRight[2][N];

INT LowBit(INT nI)
{
    return nI  & (-nI);
}

void Add(INT nI, INT nAdd)
{
    while (nI <= MAX_N)
    {
        nTree[nI] += nAdd;
        nI += LowBit(nI);
    }
}

INT Query(INT nPos)
{
    INT nAns = 0;
    while (nPos > 0)
    {
        nAns += nTree[nPos];
        nPos -= LowBit(nPos);
    }
    return nAns;
}

int main()
{
    INT nT;

    scanf("%I64d", &nT);
    while (nT--)
    {
        scanf("%I64d", &nN);
        memset(nTree, 0, sizeof(nTree));
        for (INT i = 1; i <= nN; ++i)
        {
            scanf("%I64d", nNum[i]);
            nLeft[0][i] = Query(nNum[i]);
            nLeft[1][i] = Query(MAX_N) - Query(nNum[i] - 1);
            Add(nNum[i], 1);
        }
        memset(nTree, 0, sizeof(nTree));
        for (INT i = nN; i >= 1; --i)
        {
            nRight[0][i] = Query(MAX_N) - Query(nNum[i] - 1);
            nRight[1][i] = Query(nNum[i]);
            Add(nNum[i], 1);
        }
        INT nAns = 0;
        for (INT i = 1; i <= nN; ++i)
        {
            nAns += nLeft[0][i] * nRight[0][i] + nLeft[1][i] * nRight[1][i];
        }
        printf("%I64d\n", nAns);
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.8k 阅读时长 ≈ 2 分钟

这个题意思是翻转一个01立方体。翻转多次后再查询某个点的值。
还是利用上一篇文章的思想，把翻转操作转换为单点更新操作。把查询操作转换为利用树状数组查询和的方式。这样每次操作的复杂度都是logN的3次。而直接翻转立方体的复杂度是N的3次。
这个题最麻烦的地方是空间想象能力。因为要翻转8个点才能完成一次立方体翻转。比如，翻转(x,y,z)相当于以该点作为左上角做一个无限立方体，把该立方体翻转。这样就会翻转多余的部分，那么需要把多翻转的部分翻转回来。最后的思考结果发现，只要对每个顶点翻转一次即可。至于为什么这样，自己去计算重复翻转的部分就会明白了。刚好确实是把每个点翻转了一次。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAX_N = 110;
int nSum[MAX_N + 10][MAX_N + 10][MAX_N + 10];
int nN, nM;

int LowBit(int nPos)
{
    return nPos & (-nPos);
}

void Add(int nX, int nY, int nZ)
{
    for (int i = nX; i <= nN; i += LowBit(i))
    {
        for (int j = nY; j <= nN; j += LowBit(j))
        {
            for (int k = nZ; k <= nN; k += LowBit(k))
            {
                nSum[i][j][k]++;
            }
        }
    }
}

int Query(int nX, int nY, int nZ)
{
    int nAns = 0;

    for (int i = nX; i > 0; i -= LowBit(i))
    {
        for (int j = nY; j > 0; j -= LowBit(j))
        {
            for (int k = nZ; k > 0; k -= LowBit(k))
            {
                nAns += nSum[i][j][k];
            }
        }
    }
    return nAns;
}

int main()
{
    int nCmd;
    int nX, nY, nZ;
    int nX1, nY1, nZ1;
    int nX2, nY2, nZ2;

    while (scanf("%d%d", &nN, &nM) == 2)
    {
        memset(nSum, 0, sizeof(nSum));
        while (nM--)
        {
            scanf("%d", &nCmd);
            if (nCmd == 0)
            {
                scanf("%d%d%d", &nX, &nY, &nZ);
                printf("%d\n", Query(nX, nY, nZ) % 2);
            }
            else
            {
                scanf("%d%d%d%d%d%d", &nX1, &nY1, &nZ1, &nX2, &nY2, &nZ2);
                if (nX1 > nX2)swap(nX1, nX2);
                if (nY1 > nY2)swap(nY1, nY2);
                if (nZ1 > nZ2)swap(nZ1, nZ2);
                Add(nX1, nY1, nZ1);

                Add(nX2 + 1, nY1, nZ1);
                Add(nX1, nY2 + 1, nZ1);
                Add(nX1, nY1, nZ2 + 1);

                Add(nX1, nY2 + 1, nZ2 + 1);
                Add(nX2 + 1, nY1, nZ2 + 1);
                Add(nX2 + 1, nY2 + 1, nZ1);

                Add(nX2 + 1, nY2 + 1, nZ2 + 1);
            }
        }
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.2k 阅读时长 ≈ 1 分钟

这个题的意思是给定一个长为N的区间。不断的给某个子区间[A,B]中的每个点涂一次色。最后问每个点的涂色次数。
这个题貌似可以扩展到多维的情况，但是多维的情况下必须用树状数组求和以加快速度，一维的情况直接求和即可。
假如，第一次涂色是对区间[A,B]涂色一次，可以让nNum[nA]++,nNum[nB+1]—即可。因为这样对于区间[0,nA-1]的任意值i有都要nNum[1]+nNum[2]+…+nNum[i] = 0。而对于区间[nA,nB]的任意值i有nNum[1]+nNum[2]+…+nNum[i] = 0。对于区间[nB+1, nN]的任意值i有nNum[1]+nNum[2]+…+nNum[i] = 0。那么重复多次了。如果上述求和nNum[1]+nNum[2]+…+nNum[i] 刚好代表每个结点i的涂色次数，那么这个题就可解了。
用例子验证一下，发现肯定是这样的。证明略了。至于树状数组网上一大堆资料。树状数组模板单一，敲代码太方便了。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int nNum[100000 + 10];
int nN;
int LowBit(int nI)
{
    return nI & (-nI);
}

void Add(int nI, int nAdd)
{
    while (nI <= nN)
    {
        nNum[nI] += nAdd;
        nI += LowBit(nI);
    }
}

int GetSum(int nI)
{
    int nAns = 0;

    while (nI > 0)
    {
        nAns += nNum[nI];
        nI -= LowBit(nI);
    }
    return nAns;
}

int main()
{
    int nA, nB;

    while (scanf("%d", &nN), nN)
    {
        memset(nNum, 0, sizeof(nNum));

        for (int i = 1; i <= nN; ++i)
        {
            scanf("%d%d", nA, nB);
            Add(nA, 1);
            Add(nB + 1, -1);
        }
        for (int i = 1; i <= nN; ++i)
        {
            printf("%d%s", GetSum(i), i == nN ? "\n" : " ");
        }
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.2k 阅读时长 ≈ 2 分钟

这个题是求次短路。有个不错的解法，是根据一个结论，替换调最短路里面的一条边肯定能得到次短路。
那么，只要枚举所有边就可以了。比如，假设开始点为s，目标点是d，设最短路为dis(s,d)。对于边(u,v)，dis(s, u) + w(u, v) + dis(v, d) 大于dis(s, d)，则该路径就可能是次短路。求出最小的大于dis(s,d)的值就可以了。方式是从s开始和从d开始进行2次单源多终点最短路径算法。然后枚举边即可。
该算法可以这样理解。因为替换最短路径里面的边，路径的长度只会变大或者不变。如果存在让更短路径变小的边，这本身就与最短路径是矛盾的。所以替换2条或者更多的边只会让路径变得更大。因此，只需考虑替换一条边的情况即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

const int MAX_N = 5000 + 10;
struct Edge
{
    int nE;
    int nDis;
    Edge(int e, int d):nE(e), nDis(d) {}
};
vector<Edge> graph[MAX_N];
bool bVisit[MAX_N];
int nSDis[MAX_N];
int nEDis[MAX_N];

struct Node
{
    int nN;
    int nDis;

    bool operator < (const Node node) const
    {
        return nDis > node.nDis;
    }
};

int ShortestPath(int nS, int nE, int* nDis, int nN)
{
    priority_queue<Node> pq;
    memset(bVisit, false, sizeof(bVisit));
    for (int i = 1; i <= nN; i++)
    {
        nDis[i] = 0x7fffffff;
    }
    nDis[nS] = 0;
    Node head;
    head.nDis = 0, head.nN = nS;
    pq.push(head);

    while (pq.empty() == false)
    {
        Node head = pq.top();
        pq.pop();
        int nU = head.nN;
        if (bVisit[nU]) continue;
        bVisit[nU] = true;

        for (int i = 0; i < graph[nU].size(); ++i)
        {
            int nV = graph[nU][i].nE;
            int nLen = head.nDis + graph[nU][i].nDis;
            if (nLen < nDis[nV])
            {
                nDis[nV] = nLen;
                Node node;
                node.nDis = nLen;
                node.nN = nV;
                pq.push(node);
            }
        }
    }

    return nDis[nE];
}

int Second(int nS, int nE, int nN)
{
    int nShortest = ShortestPath(nS, nE, nSDis, nN);
    ShortestPath(nE, nS, nEDis, nN);

    int nAns = 0x7fffffff;

    for (int i = 1; i <= nN; ++i)
    {
        for (int j = 0; j < graph[i].size(); ++j)
        {
            int nU = i;
            int nV = graph[i][j].nE;
            int nLen = nSDis[i] + graph[i][j].nDis + nEDis[nV];
            if (nLen != nShortest)
            {
                nAns = min(nAns, nLen);
            }
        }
    }

    return nAns;
}

int main()
{
    int nN, nR;
    int nA, nB, nD;

    while (scanf("%d%d", &nN, &nR) == 2)
    {
        for (int i = 1; i <= nN; ++i)
        {
            graph[i].clear();
        }

        while (nR--)
        {
            scanf("%d%d%d", &nA, &nB, &nD);
            graph[nA].push_back(Edge(nB, nD));
            graph[nB].push_back(Edge(nA, nD));
        }
        printf("%d\n", Second(1, nN, nN));
    }

    return 0;
}