STEP BY STEP

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

并查集应用的变形。题目意思是一个图中，只有上下左右四个方向的边。给出这样的一些边，求任意指定的2个节点之间的距离。
有可能当前给出的信息，没有涉及到要求的2个节点，或者只涉及到了1个节点，那么肯定无法确定它们的距离。或者根据已经给出的边只知道这2个节点在不同的联通分量里面，那么其距离也是无法确定的，根据题目要求，输出-1。
问题是如果能够确定它们在一个联通分量里面，如何确定它们的距离了。这个题的关键在于，只有上下左右四个方向的边，假设每个节点都有一个坐标的话，那么它们相对于代表该联通分量节点的坐标肯定是固定的，那么就不需要考虑图里面有环之类的情况了。这样就可以很方便的应用并查集来解了。
利用并查集，给每个节点附加其它信息，即相对于代表该并查集的节点的坐标（x，y）。在FindSet里面求出坐标，在UnionSet里面修改合并后新加入的另外一个集合的根节点的坐标即可。
代码如下：

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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

const int MAX_N = 40010;
int nN, nM;
int nSets[MAX_N];
int nX[MAX_N];
int nY[MAX_N];
char szInput[MAX_N][100];

void MakeSets(int nNum)
{
    for (int i = 0; i < nNum; ++i)
    {
        nSets[i] = i;
        nX[i] = nY[i] = 0;
    }
}

int FindSets(int nI)
{
    if (nSets[nI] != nI)
    {
        int nPre = nSets[nI];
        nSets[nI] = FindSets(nSets[nI]);
        nX[nI] += nX[nPre];
        nY[nI] += nY[nPre];
    }
    return nSets[nI];
}

void UnionSets(int nBeg, int nEnd, int dx, int dy)
{
    int nA = FindSets(nBeg);
    int nB = FindSets(nEnd);
    if (nA != nB)
    {
        nSets[nB] = nA;//把集合B合并到集合A中
        nX[nB] = nX[nBeg] + dx - nX[nEnd];//因为方向逆过来了,所以是减去
        nY[nB] = nY[nBeg] + dy - nY[nEnd];
    }
}

int main()
{
    int nBeg, nEnd, nL;
    char szDir[10];

    while (scanf("%d%d%*c", &nN, &nM) == 2)
    {
        MakeSets(nN);
        for (int i = 0; i < nM; ++i)
        {
            fgets(szInput[i], 100, stdin);
        }
        int nK;
        int nF1, nF2, nI;
        scanf("%d", nK);
        int nCur = 0;
        while (nK--)
        {
            scanf("%d%d%d", nF1, nF2, nI);
            for (int i = nCur; i < nI; ++i)
            {
                sscanf(szInput[i], "%d%d%d%s", &nBeg,
                       &nEnd, &nL, szDir);
                int dx = 0, dy = 0;
                switch (szDir[0])
                {
                case 'N':
                    dy += nL;
                    break;
                case 'S':
                    dy -= nL;
                    break;
                case 'E':
                    dx += nL;
                    break;
                case 'W':
                    dx -= nL;
                    break;
                }
                UnionSets(nBeg, nEnd, dx, dy);
            }
            nCur = nI;

            if (FindSets(nF1) != FindSets(nF2))
            {
                printf("-1\n");
            }
            else
            {
                printf("%d\n", abs(nX[nF1] - nX[nF2])
                       + abs(nY[nF1] - nY[nF2]));
            }
        }
    }

    return 0;
}

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

并查集应用的变形。
给出的是2个节点是敌对关系的信息，最后询问任意2个节点的关系。根据这些信息，
节点之间可能是敌对的，也可能不是的（因为敌人的敌人就是朋友），也可能给出的
信息根本描述不了它们的关系。
看起来跟原始的并查集应用差远了。。。
有个比较直接的做法，那么就是把不在一个集合的节点直接用并查集合并在一起。这样的话，
如果询问的2个节点在同一个并查集里面，那么它们之间的关系是确定的，否则无法确定它们的
关系。
现在还有一个问题是，在同一个并查集里面的2个节点是敌对关系还是朋友关系。。。
可以给每个节点另外附加个信息，记录其距离并查集根节点的距离。如果，询问的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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAX_N = 100010;
int nSets[MAX_N];
int nDis[MAX_N];

int nN, nM;

void MakeSets(int nNum)
{
    for (int i = 0; i < nNum; ++i)
    {
        nSets[i] = i;
        nDis[i] = 0;
    }
}

int FindSet(int nI)
{
    if (nSets[nI] != nI)
    {
        int nPre = nSets[nI];
        nSets[nI] = FindSet(nSets[nI]);
        nDis[nI] = (nDis[nI] + nDis[nPre]) % 2;
    }
    return nSets[nI];
}

void UnionSet(int nI, int nJ)
{
    int nA = FindSet(nI);
    int nB = FindSet(nJ);
    if (nA != nB)
    {
        nSets[nA] = nB;
        nDis[nA] = (nDis[nI] + nDis[nJ] + 1) % 2;
    }
}

int main()
{
    int nT;

    scanf("%d", nT);
    while (nT--)
    {
        scanf("%d%d", nN, nM);
        MakeSets(nN);
        char szOper[10];
        int nA, nB;
        while (nM--)
        {
            scanf("%s%d%d", szOper, &nA, &nB);
            if (szOper[0] == 'D')
            {
                UnionSet(nA, nB);
            }
            else
            {
                int nX = FindSet(nA);
                int nY = FindSet(nB);
                if (nX == nY)
                {
                    if (nDis[nA] == nDis[nB])
                    {
                        printf("In the same gang.\n");
                    }
                    else
                    {
                        printf("In different gangs.\n");
                    }
                }
                else
                {
                    printf("Not sure yet.\n");
                }
            }
        }
    }

    return 0;
}

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

此题本来模拟即可，但是注意有容易出错的地方。
这题主要是可以用中国剩余定理来做。
根据题意可以抽象出这样的模型。给出三个数A,B,C分别是模23,28,33后的余数，求最小的数字
使得其模23,28,33分别为A,B,C，并且要大于给定的数字D。
中国剩余定理很好的解决了这种余数问题。令模数为Ni,余数为Ai,设Mi = N1N2…Ni-1Ni+1…Nn，
那么答案一定满足形式ans = ΣAiMi(Mi对Ni的乘法逆) % N。(N为所有Ni的乘积)。
很明显，由于ans的第i项有Mi因子，所以模N1-Ni-1和Ni+1-Nn肯定是0，而AiMi(Mi对Ni的乘法逆) %Ni就是Ai。这样就满足了要求。
代码如下：

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
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;

int Egcd(int nN, int nM, int nX, int nY)
{
    if (nM == 0)
    {
        nX = 1, nY = 0;
        return nN;
    }
    int nRet = Egcd(nM, nN % nM, nX, nY);
    int nT = nX;
    nX = nY;
    nY = nT - (nN / nM) * nY;
    return nRet;
}

int main()
{
    int nA, nB, nC, nD;
    int nDays = 21252;
    int nCase = 1;

    while (scanf("%d%d%d%d", &nA, &nB, &nC, &nD),
            nA != -1 || nB != -1 || nC != -1 || nD != -1)
    {
        int nFirst = 0;
        nA %= 23;
        nB %= 28;
        nC %= 33;
        int nM1= 28 * 33, nM2 = 23 * 33, nM3 = 23 * 28;
        int nN1, nN2, nN3, nTemp;
        Egcd(23, nM1, nTemp, nN1);
        Egcd(28, nM2, nTemp, nN2);
        Egcd(33, nM3, nTemp, nN3);
        nFirst = (nA * nM1 * nN1 + nB * nM2 * nN2 + nC * nM3 * nN3) % nDays;
        while (nFirst <= nD)nFirst += nDays;
        printf("Case %d: the next triple peak occurs in %d days.\n",
               nCase++, nFirst - nD);
    }

    return 0;
}

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

这个题是求一个字符串的最小重复单元的重复次数，那么求出最小重复单元的长度即可。这个题有3种方法，方法一：直接枚举长度为[1,len/2]内的子串，暴力就过了。方法二：将原串重复一次形成一个新串，用原串去匹配新串，但是得从第二个位置开始匹配，第一次成功匹配的位置减一就代表最小重复单元的长度。方法三：利用kmp的next函数，如果len能够整除len-next[len]，那么len-next[len]就代表最小重复单元的长度。
方法一明显是对的，数据不强的情况下就能水过了。方法二也不是那么容易想到的，不过将原串扩展为2倍的做法也不是太奇葩，比如判断2个循环串是否相等就可以用这个办法做。
方法三就比较难理解了。
方法三的理解：
next[len]代表的是str的最长前缀(使得这个前缀与同样长度的后缀相等)的长度。所谓的next
数组就是长度为1-len的str的满足上述描述的最长前缀的长度。如果len是len-next[len]的倍数，假设m= len-next[len] ，那么str[1-m] = str[m-2 m]，以此类推下去，m肯定是str的最小重复单元的长度。假如len不是len-next[len]的倍数， 如果前缀和后缀重叠，那么最小重复单元肯定str本身了，如果前缀和后缀不重叠，那么str[m - 2 m] != str[len-m,len]，所以str[1-m]!= str[m - 2 * m] ,最终肯定可以推理出最小重复单元是str本身，因为只要不断递增m证明即可。

方法三的代码如下：

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

char szStr[1000010];
int nNext[1000010];

void GetNext(char* szStr, int nLen, int* nNext)
{
    nNext[0] = -1;
    for (int i = 1, j = -1; i < nLen; ++i)
    {
        while (j > -1  szStr[i] != szStr[j + 1])
        {
            j = nNext[j];
        }
        if (szStr[i] == szStr[j + 1])
        {
            ++j;
        }
        nNext[i] = j;
    }
}

int main()
{
    while (scanf("%s", szStr), strcmp(szStr, "."))
    {
        int nLen = strlen(szStr);

        GetNext(szStr, nLen, nNext);
        if (nLen % (nLen - nNext[nLen - 1] - 1))
        {
            printf("1\n");
        }
        else
        {
            printf("%d\n", nLen / (nLen - nNext[nLen - 1] - 1));
        }
    }

    return 0;
}

发表于 分类于 ， 阅读次数： 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;
}