lightoj1427

maksyuki 发表于 oj 分类，标签: 字符串-AC自动机

27 8月 2015

1427 - Substring Frequency (II)

InputA string is a finite sequence of symbols that are chosen from an alphabet. In this problem you are given a string T and n queries each with a string P_i, where the strings contain lower case English alphabets only. You have to find the number of times P_i occurs as a substring of T.

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 500). The next line contains the string T (1 ≤ |T| ≤ 10⁶). Each of the next n lines contains a string P_i (1 ≤ |P_i| ≤ 500).

Output

For each case, print the case number in a single line first. Then for each string P_i, report the number of times it occurs as a substring of T in a single line.

Sample Input

Output for Sample Input

25ababacbabcababa

abc

lightoj

light

lit

Case 1:2314

Case 2:

Notes

Dataset is huge, use faster I/O methods.
If S is a string then |S| denotes the length of S.

题目类型：AC自动机

算法分析：将子串插入到Trie树中，然后使用cnt数组统计在文本串T中，相应子串出现的个数即可，注意子串可能出现重复的情况！！！由于n比较小，所以可以使用O(n^2)的枚举将标号后面重复的相应子串的个数求解得到

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 1e9 + 7;
const int maxn = 26;
const int nodemaxn = 250000 + 66;

char ss[1000000+maxn];
int cnt[500+maxn];
char val[500+maxn][500+maxn];

struct ACNode
{
    int next[nodemaxn][maxn], pre[nodemaxn], last[nodemaxn], id[nodemaxn];
    int root, len;

    void Init ()
    {
        len = 0;
        root = newnode ();
    }

    int newnode ()
    {
        for (int i = 0; i < maxn; i++)
            next[len][i] = -1;
        last[len] = id[len] = 0;
        len++;

        return len - 1;
    }

    void Insert (char *s, int ff)
    {
        int p = root;
        for(int i = 0; s[i]; i++)
        {
            if(next[p][s[i]-'a'] == -1)
                next[p][s[i]-'a'] = newnode ();

            p = next[p][s[i]-'a'];
        }
        last[p]++;
        id[p] = ff;
    }

    void Build ()
    {
        queue <int> qu;
        pre[root] = root;
        for(int i = 0; i < maxn; i++)
        {
            if(next[root][i] == -1)
                next[root][i] = root;

            else
            {
                pre[next[root][i]] = root;
                qu.push (next[root][i]);
            }
        }

        while (!qu.empty ())
        {
            int p = qu.front(); qu.pop ();
            for (int i = 0; i < maxn; i++)
            {
                if (next[p][i] == -1)
                    next[p][i] = next[pre[p]][i];

                else
                {
                    pre[next[p][i]] =  next[pre[p]][i];
                    qu.push (next[p][i]);
                }
            }
        }
    }

    void Query (char *s)
    {
        int p = root;
        for (int i = 0; s[i]; i++)
        {

            p = next[p][s[i]-'a'];//一步到位，重要!!! 当存在时走到下一层，否则回溯!!!
            int temp = p;

            while (temp != root)
            {
                if (last[temp])
                {
                    cnt[id[temp]]++;
                }
                temp = pre[temp];
            }
        }
    }
};

ACNode ac;

int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int n, t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        printf ("Case %d:\n", flag++);
        scanf ("%d", &n);
        scanf ("%s", ss);

        ac.Init ();
        memset (cnt, 0, sizeof (cnt));

        for (int i = 1; i <= n; i++)
        {
            scanf ("%s", val[i]);

            int j;
            for (j = 1; j < i; j++)
                if (!strcmp (val[j], val[i]))
                    break;

            if (j >= i)
                ac.Insert (val[i], i);
        }

        ac.Build ();
        ac.Query (ss);

        for (int i = 1; i <= n; i++)
        {
            int j;
            for (j = 1; j < i; j++)
                if (!strcmp (val[j], val[i]))
                    break;

            if (j < i)
                printf ("%d\n", cnt[j]);

            else
                printf ("%d\n", cnt[i]);
        }
    }

return 0;
}

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

175

176

177

178

179

180

181

182

183

184

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 1e9 + 7;

const int maxn = 26;

const int nodemaxn = 250000 + 66;

char ss[1000000+maxn];

int cnt[500+maxn];

char val[500+maxn][500+maxn];

struct ACNode

{

int next[nodemaxn][maxn], pre[nodemaxn], last[nodemaxn], id[nodemaxn];

int root, len;

void Init ()

{

len = 0;

root = newnode ();

}

int newnode ()

{

for (int i = 0; i < maxn; i++)

next[len][i] = -1;

last[len] = id[len] = 0;

len++;

return len - 1;

}

void Insert (char *s, int ff)

{

int p = root;

for(int i = 0; s[i]; i++)

{

if(next[p][s[i]-'a'] == -1)

next[p][s[i]-'a'] = newnode ();

p = next[p][s[i]-'a'];

}

last[p]++;

id[p] = ff;

}

void Build ()

{

queue <int> qu;

pre[root] = root;

for(int i = 0; i < maxn; i++)

{

if(next[root][i] == -1)

next[root][i] = root;

else

{

pre[next[root][i]] = root;

qu.push (next[root][i]);

}

while (!qu.empty ())

{

int p = qu.front(); qu.pop ();

for (int i = 0; i < maxn; i++)

{

if (next[p][i] == -1)

next[p][i] = next[pre[p]][i];

else

{

pre[next[p][i]] = next[pre[p]][i];

qu.push (next[p][i]);

}

void Query (char *s)

{

int p = root;

for (int i = 0; s[i]; i++)

{

p = next[p][s[i]-'a'];//一步到位，重要!!! 当存在时走到下一层，否则回溯!!!

int temp = p;

while (temp != root)

{

if (last[temp])

{

cnt[id[temp]]++;

}

temp = pre[temp];

}

};

ACNode ac;

int main()

{

// freopen ("aaa.txt", "r", stdin);

int n, t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d:\n", flag++);

scanf ("%d", &n);

scanf ("%s", ss);

ac.Init ();

memset (cnt, 0, sizeof (cnt));

for (int i = 1; i <= n; i++)

{

scanf ("%s", val[i]);

int j;

for (j = 1; j < i; j++)

if (!strcmp (val[j], val[i]))

break;

if (j >= i)

ac.Insert (val[i], i);

}

ac.Build ();

ac.Query (ss);

for (int i = 1; i <= n; i++)

{

int j;

for (j = 1; j < i; j++)

if (!strcmp (val[j], val[i]))

break;

if (j < i)

printf ("%d\n", cnt[j]);

else

printf ("%d\n", cnt[i]);

}

return 0;

}

lightoj1369

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

27 8月 2015

1369 - Answering Queries

long long f( int A[], int n ) { // n = size of AThe problem you need to solve here is pretty simple. You are give a function f(A, n), where A is an array of integers and n is the number of elements in the array. f(A, n) is defined as follows:

long long sum = 0;

for( int i = 0; i < n; i++ )

for( int j = i + 1; j < n; j++ )

sum += A[i] - A[j];

return sum;

}

Given the array A and an integer n, and some queries of the form:

1) 0 x v (0 ≤ x < n, 0 ≤ v ≤ 10⁶), meaning that you have to change the value of A[x] to v.

2) 1, meaning that you have to find f as described above.

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case starts with a line containing two integers: n and q (1 ≤ n, q ≤ 10⁵). The next line contains n space separated integers between 0 and 10⁶ denoting the array A as described above.

Each of the next q lines contains one query as described above.

Output

For each case, print the case number in a single line first. Then for each query-type "1" print one single line containing the value of f(A, n).

Sample Input

Output for Sample Input

13 51 2 310 0 310 2 1

Case 1:-404

Note

Dataset is huge, use faster I/O methods.

题目类型：简单数学

算法分析：首先将sum求出来，然后更新时只更新a[x]的值所引起的变化，查询时直接输出结果，注意两个int型变量相乘的中间结果也是int的，可能会溢出！！！

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const int mod = 1000000000 + 7;
const int maxn = 100000 + 66;

long long a[maxn];

int main()
{
//    ifstream cin ("aaa.txt");
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);
    while (t--)
    {
        printf ("Case %d:\n", flag++);
        int n, q;
        scanf ("%d%d", &n, &q);

        long long res = 0;
        for (int i = 1;i <= n; i++)
            scanf ("%d", &a[i]);

        if (n == 1)
            res = 0;

        else if (n == 2)
            res = a[1] - a[2];

        else
        {
            for (int i = 1; i <= n - 1; i++)
                res += (n - i) * a[i];

            long long temp = 0, tempsum = 0;
            for (int i = n; i >= 2; i--)
            {
                temp += a[i];
                tempsum += temp;
            }
            res -= tempsum;
        }

        int vv, x, y;
        for (int i = 1; i <= q; i++)
        {
            scanf ("%d", &vv);

            if (vv == 0)
            {
                scanf ("%d%d", &x, &y);
                x++;

                if (n == 1)
                    continue ;

                else if (n == 2)
                {
                    if (x == 1)
                        res += (y - a[x]);

                    else if (x == 2)
                        res -= (y - a[x]);

                    a[x] = y;
                }

                else
                {
                    if (x <= n - 1)
                        res += (n - x) * (y - a[x]);

                    if (x >= 2)
                        res -= (x - 1) * (y - a[x]);

                    a[x] = y;
                }
            }

            else
                printf ("%lld\n", res);
        }
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const int mod = 1000000000 + 7;

const int maxn = 100000 + 66;

long long a[maxn];

int main()

{

// ifstream cin ("aaa.txt");

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d:\n", flag++);

int n, q;

scanf ("%d%d", &n, &q);

long long res = 0;

for (int i = 1;i <= n; i++)

scanf ("%d", &a[i]);

if (n == 1)

res = 0;

else if (n == 2)

res = a[1] - a[2];

else

{

for (int i = 1; i <= n - 1; i++)

res += (n - i) * a[i];

long long temp = 0, tempsum = 0;

for (int i = n; i >= 2; i--)

{

temp += a[i];

tempsum += temp;

}

res -= tempsum;

}

int vv, x, y;

for (int i = 1; i <= q; i++)

{

scanf ("%d", &vv);

if (vv == 0)

{

scanf ("%d%d", &x, &y);

x++;

if (n == 1)

continue ;

else if (n == 2)

{

if (x == 1)

res += (y - a[x]);

else if (x == 2)

res -= (y - a[x]);

a[x] = y;

}

else

{

if (x <= n - 1)

res += (n - x) * (y - a[x]);

if (x >= 2)

res -= (x - 1) * (y - a[x]);

a[x] = y;

}

else

printf ("%lld\n", res);

}

return 0;

}

lightoj1337

maksyuki 发表于 oj 分类，标签: 基础算法-搜索(DFS\BFS)\记忆化

27 8月 2015

1337 - The Crystal Maze

To be more exact, the maze can be modeled as an M x N 2D grid where M denotes the number of rows and N denotes the number of columns. There are three types of cells in the grid:You are in a plane and you are about to be dropped with a parasuit in a crystal maze. As the name suggests, the maze is full of crystals. Your task is to collect as many crystals as possible.

A '#' denotes a wall, you may not pass through it.
A 'C' denotes a crystal. You may move through the cell.
A '.' denotes an empty cell. You may move through the cell.

Now you are given the map of the maze, you want to find where to land such that you can collect maximum number of crystals. So, you are spotting some position x, y and you want to find the maximum number of crystals you may get if you land to cell (x, y). And you can only move vertically or horizontally, but you cannot pass through walls, or you cannot get outside the maze.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing three integers M, N and Q (2 ≤ M, N ≤ 500, 1 ≤ Q ≤ 1000). Each of the next M lines contains N characters denoting the maze. You can assume that the maze follows the above restrictions.

Each of the next Q lines contains two integers x_i and y_i (1 ≤ x_i ≤ M, 1 ≤ y_i ≤ N) denoting the cell where you want to land. You can assume that cell (x_i, y_i) is empty i.e. the cell contains '.'.

Output

For each case, print the case number in a single line. Then print Q lines, where each line should contain the maximum number of crystals you may collect if you land on cell (x_i, y_i).

Sample Input

Output for Sample Input

14 5 2..#...C#C.##..#..C#C

1 1

4 1

Case 1:12

Note

Dataset is huge, use faster I/O methods.

题目类型：记忆化搜索

算法分析：本题其实求每一个连通块中所有水晶的数量，如果对于每个查询都调用一次DFS或者是BFS会TLE，此时应该使用记忆化搜索的思想使能通过调用一次搜索算法计算出的所有节点(在同一个连通块中)的水晶数量记录下来，然后对于已经计算过的查询操作(查询的坐标在已经计算过的连通块中)，则直接输出相应的记录即可

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

const int INF = 0x7FFFFFFF;
const int maxn = 600 + 66;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

char ans[maxn][maxn];
bool visited[maxn][maxn];
int maxval[maxn][maxn];
int fval[1000+66];
int row, col, q;

struct Node
{
    int x, y;
    Node (int xx, int yy) : x (xx), y (yy) {}
    Node () {}
};


inline bool OkMove (int x, int y)
{
    if (x >= 0 && x <= row - 1 && y >= 0 && y <= col - 1 && !visited[x][y] && ans[x][y] != '#')
        return true;

return false;
}

queue <Node> qu;

void BFS (int x, int y, int flag)
{
    int Ctot = 0;

    qu.push(Node (x, y));

    while (!qu.empty ())
    {
        Node temp = qu.front ();
        qu.pop ();

        if (ans[temp.x][temp.y] == 'C')
            Ctot++;

        maxval[temp.x][temp.y] = flag;

        int i;
        for (i = 0; i < 4; i++)
        {
            if (OkMove (temp.x + dx[i], temp.y + dy[i]))
            {
                int val_x = temp.x + dx[i];
                int val_y = temp.y + dy[i];
                visited[val_x][val_y] = true;
                qu.push (Node (val_x, val_y));
            }
        }
    }

    fval[flag] = Ctot;
}


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        scanf ("%d%d%d", &row, &col, &q);

        int i;
        for (i = 0; i < row; i++)
            scanf ("%s", ans[i]);

        printf ("Case %d:\n", flag++);

        memset (visited, false, sizeof (visited));
        memset (maxval, 0, sizeof (maxval));

        int val_x, val_y;
        for (i = 0; i < q; i++)
        {
            scanf ("%d%d", &val_x, &val_y);
            val_x--, val_y--;

            if (!visited[val_x][val_y])
            {
                visited[val_x][val_y] = true;
                BFS (val_x, val_y, i);
            }

            cout << fval[maxval[val_x][val_y]] << endl;
        }
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

#include <iostream>

#include <fstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

const int INF = 0x7FFFFFFF;

const int maxn = 600 + 66;

const int dx[] = {-1, 1, 0, 0};

const int dy[] = {0, 0, -1, 1};

char ans[maxn][maxn];

bool visited[maxn][maxn];

int maxval[maxn][maxn];

int fval[1000+66];

int row, col, q;

struct Node

{

int x, y;

Node (int xx, int yy) : x (xx), y (yy) {}

Node () {}

};

inline bool OkMove (int x, int y)

{

if (x >= 0 && x <= row - 1 && y >= 0 && y <= col - 1 && !visited[x][y] && ans[x][y] != '#')

return true;

return false;

}

queue <Node> qu;

void BFS (int x, int y, int flag)

{

int Ctot = 0;

qu.push(Node (x, y));

while (!qu.empty ())

{

Node temp = qu.front ();

qu.pop ();

if (ans[temp.x][temp.y] == 'C')

Ctot++;

maxval[temp.x][temp.y] = flag;

int i;

for (i = 0; i < 4; i++)

{

if (OkMove (temp.x + dx[i], temp.y + dy[i]))

{

int val_x = temp.x + dx[i];

int val_y = temp.y + dy[i];

visited[val_x][val_y] = true;

qu.push (Node (val_x, val_y));

}

fval[flag] = Ctot;

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

scanf ("%d%d%d", &row, &col, &q);

int i;

for (i = 0; i < row; i++)

scanf ("%s", ans[i]);

printf ("Case %d:\n", flag++);

memset (visited, false, sizeof (visited));

memset (maxval, 0, sizeof (maxval));

int val_x, val_y;

for (i = 0; i < q; i++)

{

scanf ("%d%d", &val_x, &val_y);

val_x--, val_y--;

if (!visited[val_x][val_y])

{

visited[val_x][val_y] = true;

BFS (val_x, val_y, i);

}

cout << fval[maxval[val_x][val_y]] << endl;

}

return 0;

}

lightoj1325

maksyuki 发表于 oj 分类，标签: 数论-离散对数

27 8月 2015

1325 - Distributing Chocolates

InputNow as the result can be large, I asked for the result modulo 100 000 007 (a prime). But after that I found that this problem is easier than I thought. So, I changed the problem a little bit. I will give you the number of my cousins K and the result modulo 100 000 007. Your task is to find the number of chocolates I have bought. If there are several solutions, you have to find the minimum one.I have bought n chocolates for my young cousins. Every chocolate is different. So, in the contest I added the problem that how many ways I can distribute the chocolates to my K cousins. I can give more chocolates to some cousins, and may give no chocolate to some. For example, I have three cousins and I bought 2 chocolates a and b. Then I can distribute them in the following 9 ways:

Input starts with an integer T (≤ 1000), denoting the number of test cases.

Each case starts with a line containing two integers K (2 ≤ K ≤ 10⁷) and result (0 ≤ result < 100000007). You can assume that the input data is valid, that means a solution exists.

Output

For each case, print the case number and the minimum possible number of chocolates I have bought.

Sample Input	Output for Sample Input
23 92 100	Case 1: 2Case 2: 23502611

题目类型：离散对数

算法分析：直接使用BSGS算法求解即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 100000 + 66;

struct hashtable
{
    long long key[maxn];
    long long value[maxn];

    void Init()
    {
        for (long long i = 0; i < maxn; i++)
        {
            key[i] = -1, value[i] = -1;
        }
    }

    void Insert (long long k, long long v)
    {
        long long kk = k % maxn;

        while (key[kk] != -1 && key[kk] != k)
            kk = (kk + 1) % maxn;

        key[kk] = k,value[kk] = v;
    }

    long long Find (long long k)
    {
        long long kk = k % maxn;

        while (key[kk] != -1 && key[kk] != k)
            kk = (kk + 1) % maxn;

        return value[kk];
    }
}Hash;


long long baby_giant (long long x, long long k, long long z)
{
    x %= z,k %= z;
    long long m = (long long) ceil (sqrt (1.0 * z)), pre = 1;

    Hash.Init();Hash.Insert (k, 0);

    for (long long i = 1; i <= m; i++)
    {
        pre = (1ll * pre * x) % z;
        Hash.Insert ((1ll * pre * k) % z, i);
    }

    for (long long i = 0,xm = pre, y = 1; i * m <= z; i++)
    {
        long long j = Hash.Find (y);

        if (j >= 0 && i * m - j >= 0)
            return i * m - j;

        y = (1ll * y * xm) % z;
    }

return -1;
}

int main()
{
//    ifstream cin ("aaa.txt");
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    long long A, B, C = 100000007;

    while (t--)
    {
        printf ("Case %d: ", flag++);
        scanf ("%lld%lld", &A, &B);
        long long ans = baby_giant (A, B, C);

        printf ("%lld\n", ans);
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 100000 + 66;

struct hashtable

{

long long key[maxn];

long long value[maxn];

void Init()

{

for (long long i = 0; i < maxn; i++)

{

key[i] = -1, value[i] = -1;

}

void Insert (long long k, long long v)

{

long long kk = k % maxn;

while (key[kk] != -1 && key[kk] != k)

kk = (kk + 1) % maxn;

key[kk] = k,value[kk] = v;

}

long long Find (long long k)

{

long long kk = k % maxn;

while (key[kk] != -1 && key[kk] != k)

kk = (kk + 1) % maxn;

return value[kk];

}

}Hash;

long long baby_giant (long long x, long long k, long long z)

{

x %= z,k %= z;

long long m = (long long) ceil (sqrt (1.0 * z)), pre = 1;

Hash.Init();Hash.Insert (k, 0);

for (long long i = 1; i <= m; i++)

{

pre = (1ll * pre * x) % z;

Hash.Insert ((1ll * pre * k) % z, i);

}

for (long long i = 0,xm = pre, y = 1; i * m <= z; i++)

{

long long j = Hash.Find (y);

if (j >= 0 && i * m - j >= 0)

return i * m - j;

y = (1ll * y * xm) % z;

}

return -1;

}

int main()

{

// ifstream cin ("aaa.txt");

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

long long A, B, C = 100000007;

while (t--)

{

printf ("Case %d: ", flag++);

scanf ("%lld%lld", &A, &B);

long long ans = baby_giant (A, B, C);

printf ("%lld\n", ans);

}

return 0;

}

lightoj1319

maksyuki 发表于 oj 分类，标签: 数论-线性同余方程(组)

27 8月 2015

1319 - Monkey Tradition

1) There are N monkeys who play this game and there are N bamboos of equal heights. Let the height be L meters.In 'MonkeyLand', there is a traditional game called "Bamboo Climbing". The rules of the game are as follows:

2) Each monkey stands in front of a bamboo and every monkey is assigned a different bamboo.

3) When the whistle is blown, the monkeys start climbing the bamboos and they are not allowed to jump to a different bamboo throughout the game.

4) Since they are monkeys, they usually climb by jumping. And in each jump, the i^th monkey can jump exactly p_i meters (p_i is a prime). After a while when a monkey finds that he cannot jump because one more jump may get him out of the bamboo, he reports the remaining length r_i that he is not able to cover.

5) And before the game, each monkey is assigned a distinct p_i.

6) The monkey, who has the lowest r_i, wins.

Now, the organizers have found all the information of the game last year, but unluckily they haven't found the height of the bamboo. To be more exact, they know N, all p_i and corresponding r_i, but not L. So, you came forward and found the task challenging and so, you want to find L, from the given information.

Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 12). Each of the next n lines contains two integers p_i (1 < p_i < 40, p_i is a prime) and r_i (0 < r_i < p_i). All p_i will be distinct.

Output

For each case, print the case number and the minimum possible value of L that satisfies the above conditions. If there is no solution, print 'Impossible'.

Sample Input

Output for Sample Input

235 47 6

11 3

2 1

3 2

5 3

7 1

Case 1: 69Case 2: 113

题目类型：CRT

算法分析：直接使用中国剩余定理求解即可，注意在迭代求解时要注意%M防止溢出ans = (ans % M + M) % M，本题不存在Impossible的情况

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 10 + 66;

long long M, n, a[maxn], r[maxn];

long long gcd_ex (long long a, long long b, long long &x, long long &y)
{
    if (b == 0) { x = 1; y = 0; return a; }
    long long d = gcd_ex (b, a % b, y, x);
    y = y - a / b * x;
    return d;
}

long long CRT ()
{
    M = 1;
    long long i, Mi, x, y, d, ans = 0;

    for (i = 0; i < n; i++)
        M *= a[i];

    for (i = 0; i < n; i++)
    {
        Mi = M / a[i];
        d = gcd_ex (Mi, a[i], x, y);
        ans = (ans + Mi * x * r[i]) % M;
    }

    ans = (ans % M + M) % M;

return ans;
}

int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%lld", &t);

    while (t--)
    {
        printf ("Case %d: ", flag++);

        scanf ("%lld", &n);

        for (int i = 0; i < n; i++)
            scanf ("%lld%lld", &a[i], &r[i]);

        long long ans = CRT ();

        printf ("%lld\n", ans);

    }

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 10 + 66;

long long M, n, a[maxn], r[maxn];

long long gcd_ex (long long a, long long b, long long &x, long long &y)

{

if (b == 0) { x = 1; y = 0; return a; }

long long d = gcd_ex (b, a % b, y, x);

y = y - a / b * x;

return d;

}

long long CRT ()

{

M = 1;

long long i, Mi, x, y, d, ans = 0;

for (i = 0; i < n; i++)

M *= a[i];

for (i = 0; i < n; i++)

{

Mi = M / a[i];

d = gcd_ex (Mi, a[i], x, y);

ans = (ans + Mi * x * r[i]) % M;

}

ans = (ans % M + M) % M;

return ans;

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%lld", &t);

while (t--)

{

printf ("Case %d: ", flag++);

scanf ("%lld", &n);

for (int i = 0; i < n; i++)

scanf ("%lld%lld", &a[i], &r[i]);

long long ans = CRT ();

printf ("%lld\n", ans);

}

return 0;

}

lightoj1294

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

27 8月 2015

1294 - Positive Negative Sign

-1 -2 -3 +4 +5 +6 -7 -8 -9 +10 +11 +12Given two integers: n and m and n is divisible by 2m, you have to write down the first n natural numbers in the following form. At first take first m integers and make their sign negative, then take next m integers and make their sign positive, the next m integers should have negative signs and continue this procedure until all the n integers have been assigned a sign. For example, let n be 12 and m be 3. Then we have

If n = 4 and m = 1, then we have

-1 +2 -3 +4

Now your task is to find the summation of the numbers considering their signs.

Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case starts with a line containing two integers: n and m (2 ≤ n ≤ 10⁹, 1 ≤ m). And you can assume that n is divisible by 2*m.

Output

For each case, print the case number and the summation.

Sample Input	Output for Sample Input
212 34 1	Case 1: 18Case 2: 2

题目类型：数学题

算法分析：直接模拟计算会TLE，这里应该将负数项和正数项分开，发现每一个序列都构成一个等差序列，然后直接使用公式计算出两个序列的和，最后两个序列和再相减即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 66 + 66;

int main()
{
//    ifstream cin ("aaa.txt");

    int t, flag = 1;
    cin >> t;

    while (t--)
    {
        cout << "Case " << flag++ << ": ";

        long long n, m;
        cin >> n >> m;

        long long a1 = (1 + m) * m / 2, b1 = ((1 + m) + (1 + m + m - 1)) * m / 2;
        long long len = n / (2 * m);

        long long an = a1 + (len - 1) * (2 * m), bn = b1 + (len - 1) * (2 * m);
        long long suma = (a1 + an) * len / 2, sumb = (b1 + bn) * len / 2;

        cout << sumb - suma << endl;
    }

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 66 + 66;

int main()

{

// ifstream cin ("aaa.txt");

int t, flag = 1;

cin >> t;

while (t--)

{

cout << "Case " << flag++ << ": ";

long long n, m;

cin >> n >> m;

long long a1 = (1 + m) * m / 2, b1 = ((1 + m) + (1 + m + m - 1)) * m / 2;

long long len = n / (2 * m);

long long an = a1 + (len - 1) * (2 * m), bn = b1 + (len - 1) * (2 * m);

long long suma = (a1 + an) * len / 2, sumb = (b1 + bn) * len / 2;

cout << sumb - suma << endl;

}

return 0;

}

lightoj1266

maksyuki 发表于 oj 分类，标签: 数据结构-树状数组

27 8月 2015

1266 - Points in Rectangle

InputAs the name says, this problem is about finding the number of points in a rectangle whose sides are parallel to axis. All the points and rectangles consist of 2D Cartesian co-ordinates. A point that lies in the boundary of a rectangle is considered inside.

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing an integer q (1 ≤ q ≤ 30000) denoting the number of queries. Each query is either one of the following:

1) 0 x y, meaning that you have got a new point whose co-ordinate is (x, y). But the restriction is that, if a point (x, y) is already listed, then this query has no effect.

2) 1 x₁ y₁ x₂ y₂ meaning that you are given a rectangle whose lower left co-ordinate is (x₁, y₁) and upper-right corner is (x₂, y₂); your task is to find the number of points, given so far, that lie inside this rectangle. You can assume that (x₁ < x₂, y₁ < y₂).

You can assume that the values of the co-ordinates lie between 0 and 1000 (inclusive).

Output

For each case, print the case number in a line first. Then for each query type (2), you have to answer the number of points that lie inside that rectangle. Print each of the results in separated lines.

Sample Input

Output for Sample Input

190 1 10 2 6

1 1 1 6 6

1 2 2 5 5

0 5 5

1 0 0 6 5

0 3 3

0 2 6

1 2 1 10 10

Case 1:202

Note

Dataset is huge, use faster I/O methods.

题目类型：二维树状数组

算法分析：由于题目中点的坐标最大值<=1000，所以可以直接使用二维树状数组存图，再维护一个布尔数组hasval[x][y]表示(x,y)处是否有点，如果有则不进行UpDate操作，反之则UpDate，每次直接查询矩阵中有多少点即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 1600;

int ans[maxn][maxn];
bool hasval[maxn][maxn];

int lowbit (int val)
{
    return val & (-val);
}


void UpDate (int x, int y, int val)
{
    while (x <= maxn)
    {
        int temp = y;
        while (temp <= maxn)
        {
            ans[x][temp] += val;
            temp += lowbit (temp);
        }
        x += lowbit (x);
    }
}

int Query (int x, int y)
{
    int sum = 0;
    while (x > 0)
    {
        int temp = y;
        while (temp > 0)
        {
            sum += ans[x][temp];
            temp -= lowbit (temp);
        }
        x -= lowbit (x);
    }

return sum;
}


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        printf ("Case %d:\n", flag++);

        memset (ans, 0, sizeof (ans));
        memset (hasval, false, sizeof (hasval));

        int q;
        scanf ("%d", &q);

        int i, cmd;
        for (i = 0; i < q; i++)
        {
            scanf ("%d", &cmd);
            if (cmd == 0)
            {
                int x, y;
                scanf ("%d%d", &x, &y);
                x++, y++;
                if (!hasval[x][y])
                {
                    UpDate (x, y, 1);
                    hasval[x][y] = true;
                }
            }

            else
            {
                int x1, x2, y1, y2;
                scanf ("%d%d%d%d", &x1, &y1, &x2, &y2);
                x1++, x2++, y1++, y2++;
                printf ("%d\n", Query (x2, y2) + Query (x1 - 1, y1 - 1) - Query (x1 - 1, y2)
                        - Query (x2, y1 - 1));

            }
        }
    }

return 0;
}

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 1600;

int ans[maxn][maxn];

bool hasval[maxn][maxn];

int lowbit (int val)

{

return val & (-val);

}

void UpDate (int x, int y, int val)

{

while (x <= maxn)

{

int temp = y;

while (temp <= maxn)

{

ans[x][temp] += val;

temp += lowbit (temp);

}

x += lowbit (x);

}

int Query (int x, int y)

{

int sum = 0;

while (x > 0)

{

int temp = y;

while (temp > 0)

{

sum += ans[x][temp];

temp -= lowbit (temp);

}

x -= lowbit (x);

}

return sum;

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d:\n", flag++);

memset (ans, 0, sizeof (ans));

memset (hasval, false, sizeof (hasval));

int q;

scanf ("%d", &q);

int i, cmd;

for (i = 0; i < q; i++)

{

scanf ("%d", &cmd);

if (cmd == 0)

{

int x, y;

scanf ("%d%d", &x, &y);

x++, y++;

if (!hasval[x][y])

{

UpDate (x, y, 1);

hasval[x][y] = true;

}

else

{

int x1, x2, y1, y2;

scanf ("%d%d%d%d", &x1, &y1, &x2, &y2);

x1++, x2++, y1++, y2++;

printf ("%d\n", Query (x2, y2) + Query (x1 - 1, y1 - 1) - Query (x1 - 1, y2)

- Query (x2, y1 - 1));

}

return 0;

}

lightoj1259

maksyuki 发表于 oj 分类，标签: 数论-素性分析

27 8月 2015

1259 - Goldbach`s Conjecture

Every even integer, greater than 2, can be expressed as the sum of two primes [1].Goldbach's conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. It states:

Now your task is to check whether this conjecture holds for integers up to 10⁷.

Input

Input starts with an integer T (≤ 300), denoting the number of test cases.

Each case starts with a line containing an integer n (4 ≤ n ≤ 10⁷, n is even).

Output

For each case, print the case number and the number of ways you can express n as sum of two primes. To be more specific, we want to find the number of (a, b) where

1) Both a and b are prime

2) a + b = n

3) a ≤ b

Sample Input	Output for Sample Input
264	Case 1: 1Case 2: 1

Note

An integer is said to be prime, if it is divisible by exactly two different integers. First few primes are 2, 3, 5, 7, 11, 13, ...

题目类型：素数筛+枚举

算法分析：使用Euler筛将素数表预先打出，然后对于每个读入的n，枚举小于等于n/2的素数，满足条件的cnt自加即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

//const int dx[] = {0, 0, -1, 1, -1, 1, -1, 1};
//const int dy[] = {-1, 1, 0, 0, -1, 1, 1, -1};
const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 10000000 + 66;

bool prime[maxn+10];
long long primelist[700000+10], prime_len;

void GetPrime ()
{
    memset (prime, true, sizeof (prime));
    prime_len = 0;

    for (long long i = 2; i <= maxn; i++)
    {
        if (prime[i])
            primelist[prime_len++] = i;

        for (long long j = 0; j < prime_len; j++)
        {
            if (i * primelist[j] > maxn)
                break;

            prime[i*primelist[j]] = false;
            if (i % primelist[j] == 0)
                break;
        }
    }
}

int main()
{
	GetPrime ();
//	freopen("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
	{
        printf ("Case %d: ", flag++);
		int n;
		scanf ("%d", &n);

        long long res = 0;
        for (int i = 0; i < prime_len; i++)
		{
            if (n - primelist[i] >= primelist[i] && prime[n-primelist[i]])
				res++;

			if (n - primelist[i] < primelist[i])
				break;
		}

		printf ("%lld\n", res);
	}
return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

//const int dx[] = {0, 0, -1, 1, -1, 1, -1, 1};

//const int dy[] = {-1, 1, 0, 0, -1, 1, 1, -1};

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 10000000 + 66;

bool prime[maxn+10];

long long primelist[700000+10], prime_len;

void GetPrime ()

{

memset (prime, true, sizeof (prime));

prime_len = 0;

for (long long i = 2; i <= maxn; i++)

{

if (prime[i])

primelist[prime_len++] = i;

for (long long j = 0; j < prime_len; j++)

{

if (i * primelist[j] > maxn)

break;

prime[i*primelist[j]] = false;

if (i % primelist[j] == 0)

break;

}

int main()

{

GetPrime ();

// freopen("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d: ", flag++);

int n;

scanf ("%d", &n);

long long res = 0;

for (int i = 0; i < prime_len; i++)

{

if (n - primelist[i] >= primelist[i] && prime[n-primelist[i]])

res++;

if (n - primelist[i] < primelist[i])

break;

}

printf ("%lld\n", res);

}

return 0;

}

lightoj1255

maksyuki 发表于 oj 分类，标签: 字符串-KMP

27 8月 2015

1255 - Substring Frequency

InputA string is a finite sequence of symbols that are chosen from an alphabet. In this problem you are given two non-empty strings A and B, both contain lower case English alphabets. You have to find the number of times B occurs as a substring of A.

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case starts with two lines. First line contains A and second line contains B. You can assume than 1 ≤ length(A), length(B) ≤ 10⁶.

Output

For each case, print the case number and the number of times B occurs as a substring of A.

Sample Input

Output for Sample Input

4axbyczdabcabcabcabcabc

abc

aabacbaabbaaz

aab

aaaaaa

Case 1: 0Case 2: 4Case 3: 2Case 4: 5

Note

Dataset is huge, use faster I/O methods.

题目类型：KMP

算法分析：这是一道使用KMP算法求解模式串在目标串中数量的题目，思路是如果模式串匹配成功，则将模式串指针j回溯至Next[j]，看看能不能再一次匹配

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 1000000 + 66;

char pattern[maxn], target[maxn];

int suffix[maxn];

void Build ()
{
	int len = strlen (pattern);

	suffix[0] = -1;
	suffix[1] = 0;
	int k = 0;

	int i;
	for (i = 2; i <= len; i++)
	{
		while (k >= 0 && pattern[i-1] != pattern[k])
			k = suffix[k];

		suffix[i] = ++k;
	}
}

int KMP ()
{
	int len_pattern = strlen (pattern);
	int len_target = strlen (target);
    int cnt = 0;

	int i = 0, j = 0;
    while (i < len_target)
    {
        if (pattern[j] == target[i] || j == -1)
        {
            i++;
            j++;
        }

        else
            j = suffix[j];

        if (j == len_pattern)
        {
            cnt++;
            j = suffix[j];
        }
    }

return cnt;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 1000000 + 66;

char pattern[maxn], target[maxn];

int suffix[maxn];

void Build ()

{

int len = strlen (pattern);

suffix[0] = -1;

suffix[1] = 0;

int k = 0;

int i;

for (i = 2; i <= len; i++)

{

while (k >= 0 && pattern[i-1] != pattern[k])

k = suffix[k];

suffix[i] = ++k;

}

int KMP ()

{

int len_pattern = strlen (pattern);

int len_target = strlen (target);

int cnt = 0;

int i = 0, j = 0;

while (i < len_target)

{

if (pattern[j] == target[i] || j == -1)

{

i++;

j++;

}

else

j = suffix[j];

if (j == len_pattern)

{

cnt++;

j = suffix[j];

}

return cnt;

}

lightoj1215

maksyuki 发表于 oj 分类，标签: 数论-素因子分解

27 8月 2015

1215 - Finding LCM

You will be given a, b and L. You have to find c such that LCM (a, b, c) = L. If there are several solutions, print the one where c is as small as possible. If there is no solution, report so.LCM is an abbreviation used for Least Common Multiple in Mathematics. We say LCM (a, b, c) = L if and only if L is the least integer which is divisible by a, b and c.

Input

Input starts with an integer T (≤ 325), denoting the number of test cases.

Each case starts with a line containing three integers a b L (1 ≤ a, b ≤ 10⁶, 1 ≤ L ≤ 10¹²).

Output

For each case, print the case number and the minimum possible value of c. If no solution is found, print 'impossible'.

Sample Input	Output for Sample Input
33 5 30209475 6992 770868002 6 10	Case 1: 2Case 2: 1Case 3: impossible

题目类型：素因子分解

算法分析：这是一道使用素因子分解求解LCM相关问题的典型例题。首先将a、b和L进行素因子分解，然后从小到大枚举判断L的每个素因子的指数值k，若a和b对应的指数值的最大值小于k，则c的对应的指数值就是k。若a和b对应的指数值的最大值等于k，则不需要进行任何操作。若大于k，则不可能出现这种情况，直接输出”impossible”即可。枚举完L的所有素因子之后，注意要查看此时a和b是否还有没在前面判断中出现的素因子。若还有，则也输出”impossible”。反之，则输出c的值

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-6;
const double PI = 2 * acos (0.0);
const int maxn = 1e6 + 66;

LL aa[maxn], bb[maxn], cc[maxn], lena, lenb, lenc;
LL maxval, cnta, cntb;

LL PP (LL vala, LL valb, LL valL)
{
    lena = lenb = lenc = 0;
    memset (aa, 0, sizeof (aa));
    memset (bb, 0, sizeof (bb));
    memset  (cc, 0, sizeof (cc));
    cnta = cntb = 0;

    for (LL i = 2; i * i <= vala; i++)
    {
        if (vala % i == 0)
        {
            cnta++;
            while (vala % i == 0)
            {
                aa[i]++;
                vala /= i;
            }
        }
    }
    if (vala > 1)
    {
        aa[vala]++;
        cnta++;
    }

    for (LL i = 2; i * i <= valb; i++)
    {
        if (valb % i == 0)
        {
            cntb++;
            while (valb % i == 0)
            {
                bb[i]++;
                valb /= i;
            }
        }
    }
    if (valb > 1)
    {
        bb[valb]++;
        cntb++;
    }

    maxval = -INF;
    for (LL i = 2; i * i <= valL; i++)
    {
        if (valL % i == 0)
        {
            while(valL % i == 0)
            {
                cc[i]++;
                valL /= i;
                maxval = max (maxval, i);
            }
        }
    }
    if (valL > 1)
    {
        cc[valL]++;
        maxval = max (maxval, valL);
    }
}

inline LL power (LL a, LL num)
{
    LL res = 1;
    for (LL i = 1; i <= num; i++)
        res *= a;

    return res;
}

int main()
{
//    CPPFF;
    LL t, flag = 1;
    cin >> t;

    while (t--)
    {
        cout << "Case " << flag++ << ": ";
        LL A, B, L;
        cin >> A >> B >> L;
        PP(A, B, L);

        LL ttmax, res = 1;
        bool is_valid = true;
        for (LL i = 2; i <= maxval; i++)
        {
            ttmax = max (aa[i], bb[i]);
            if (ttmax > cc[i])
            {
                is_valid = false;
                break;
            }

            else if (ttmax < cc[i])
            {
                res *= power (i, cc[i]);
            }

            if (aa[i] > 0)
                cnta--;

            if (bb[i] > 0)
                cntb--;
        }

        if (!is_valid)
            cout << "impossible" << endl;

        else
        {
            if (cnta == 0 && cntb == 0)
                cout << res << endl;

            else
                cout << "impossible" << endl;
        }
    }
    return 0;
}

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define LL long long

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-6;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 66;

LL aa[maxn], bb[maxn], cc[maxn], lena, lenb, lenc;

LL maxval, cnta, cntb;

LL PP (LL vala, LL valb, LL valL)

{

lena = lenb = lenc = 0;

memset (aa, 0, sizeof (aa));

memset (bb, 0, sizeof (bb));

memset (cc, 0, sizeof (cc));

cnta = cntb = 0;

for (LL i = 2; i * i <= vala; i++)

{

if (vala % i == 0)

{

cnta++;

while (vala % i == 0)

{

aa[i]++;

vala /= i;

}

if (vala > 1)

{

aa[vala]++;

cnta++;

}

for (LL i = 2; i * i <= valb; i++)

{

if (valb % i == 0)

{

cntb++;

while (valb % i == 0)

{

bb[i]++;

valb /= i;

}

if (valb > 1)

{

bb[valb]++;

cntb++;

}

maxval = -INF;

for (LL i = 2; i * i <= valL; i++)

{

if (valL % i == 0)

{

while(valL % i == 0)

{

cc[i]++;

valL /= i;

maxval = max (maxval, i);

}

if (valL > 1)

{

cc[valL]++;

maxval = max (maxval, valL);

}

inline LL power (LL a, LL num)

{

LL res = 1;

for (LL i = 1; i <= num; i++)

res *= a;

return res;

}

int main()

{

// CPPFF;

LL t, flag = 1;

cin >> t;

while (t--)

{

cout << "Case " << flag++ << ": ";

LL A, B, L;

cin >> A >> B >> L;

PP(A, B, L);

LL ttmax, res = 1;

bool is_valid = true;

for (LL i = 2; i <= maxval; i++)

{

ttmax = max (aa[i], bb[i]);

if (ttmax > cc[i])

{

is_valid = false;

break;

}

else if (ttmax < cc[i])

{

res *= power (i, cc[i]);

}

if (aa[i] > 0)

cnta--;

if (bb[i] > 0)

cntb--;

}

if (!is_valid)

cout << "impossible" << endl;

else

{

if (cnta == 0 && cntb == 0)

cout << res << endl;

else

cout << "impossible" << endl;

}

return 0;

}

lightoj1213

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

27 8月 2015

1213 - Fantasy of a Summation

#include <stdio.h>If you think codes, eat codes then sometimes you may get stressed. In your dreams you may see huge codes, as I have seen once. Here is the code I saw in my dream.

int cases, caseno;
int n, K, MOD;
int A[1001];

int main() {
scanf("%d", &cases);
while( cases-- ) {
scanf("%d %d %d", &n, &K, &MOD);

int i, i1, i2, i3, ... , iK;

for( i = 0; i < n; i++ ) scanf("%d", &A[i]);

int res = 0;
for( i1 = 0; i1 < n; i1++ ) {
for( i2 = 0; i2 < n; i2++ ) {
for( i3 = 0; i3 < n; i3++ ) {
...
for( iK = 0; iK < n; iK++ ) {
res = ( res + A[i1] + A[i2] + ... + A[iK] ) % MOD;
}
...
}
}
}
printf("Case %d: %d\n", ++caseno, res);
}
return 0;
}

Actually the code was about: 'You are given three integers n, K, MOD and n integers: A₀, A₁, A₂ ... A_n-1, you have to write K nested loops and calculate the summation of all A_i where i is the value of any nested loop variable.'

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with three integers: n (1 ≤ n ≤ 1000), K (1 ≤ K < 2³¹), MOD (1 ≤ MOD ≤ 35000). The next line contains n non-negative integers denoting A₀, A₁, A₂ ... A_n-1. Each of these integers will be fit into a 32 bit signed integer.

Output

For each case, print the case number and result of the code.

Sample Input

Output for Sample Input

23 1 350001 2 32 3 35000

1 2

Case 1: 6Case 2: 36

题目类型：简单数学

算法分析：可以直接计算出每一位中可能出现的数的和，然后再乘以位数k就可以了，公式为sum * (n ^ (k - 1)) * k % mod，sum表示一位中所有数的总和，n ^ (k - 1)表示在一位中出现一种数字的次数，由于数据比较大，所以需要使用整数快速幂取模来计算

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;

const int maxn = 50000 + 66;

long long mult_mod (long long a,long long b,long long mod)
{
    a %= mod;
    b %= mod;
    long long ans = 0;
    long long temp = a;

    while (b)
    {
        if (b & 1)
        {
            ans += temp;
            if (ans > mod)
                ans -= mod;//直接取模慢很多
        }

        temp <<= 1;
        if (temp > mod)
            temp -= mod;
        b >>= 1;
    }

return ans;
}

long long pow_mod (long long a,long long n,long long mod)
{
    long long ans = 1;
    long long temp = a % mod;
    while (n)
    {
        if (n & 1)
            ans = mult_mod (ans, temp, mod);

        temp = mult_mod (temp, temp, mod);
        n >>= 1;
    }

return ans;
}

int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        printf ("Case %d: ", flag++);

        long long temp, sum = 0, n, k, mod;
        scanf ("%lld%lld%lld", &n, &k, &mod);

        for (long long i = 0; i < n; i++)
        {
            scanf ("%lld", &temp);
            sum += temp;
        }

        long long ans = pow_mod (n, k - 1, mod);
        ans = (ans % mod) * (sum % mod) % mod;
        ans = (ans % mod) * (k % mod) % mod;

        printf ("%lld\n", ans);
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 50000 + 66;

long long mult_mod (long long a,long long b,long long mod)

{

a %= mod;

b %= mod;

long long ans = 0;

long long temp = a;

while (b)

{

if (b & 1)

{

ans += temp;

if (ans > mod)

ans -= mod;//直接取模慢很多

}

temp <<= 1;

if (temp > mod)

temp -= mod;

b >>= 1;

}

return ans;

}

long long pow_mod (long long a,long long n,long long mod)

{

long long ans = 1;

long long temp = a % mod;

while (n)

{

if (n & 1)

ans = mult_mod (ans, temp, mod);

temp = mult_mod (temp, temp, mod);

n >>= 1;

}

return ans;

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d: ", flag++);

long long temp, sum = 0, n, k, mod;

scanf ("%lld%lld%lld", &n, &k, &mod);

for (long long i = 0; i < n; i++)

{

scanf ("%lld", &temp);

sum += temp;

}

long long ans = pow_mod (n, k - 1, mod);

ans = (ans % mod) * (sum % mod) % mod;

ans = (ans % mod) * (k % mod) % mod;

printf ("%lld\n", ans);

}

return 0;

}

lightoj1212

maksyuki 发表于 oj 分类，标签: 数据结构-队列\双端\单调\优先

27 8月 2015

1212 - Double Ended Queue

pushLeft(): inserts an item to the left end of the queue with the exception that the queue is not full.A queue is a data structure based on the principle of 'First In First Out' (FIFO). There are two ends; one end can be used only to insert an item and the other end to remove an item. A Double Ended Queue is a queue where you can insert an item in both sides as well as you can delete an item from either side. There are mainly four operations available to a double ended queue. They are:

pushRight(): inserts an item to the right end of the queue with the exception that the queue is not full.
popLeft(): removes an item from the left end of the queue with the exception that the queue is not empty.
popRight(): removes an item from the right end of the queue with the exception that the queue is not empty.

Now you are given a queue and a list of commands, you have to report the behavior of the queue.

Input

Input starts with an integer T (≤ 20), denoting the number of test cases.

Each case starts with a line containing two integers n, m (1 ≤ n ≤ 10, 1 ≤ m ≤ 100), where n denotes the size of the queue and m denotes the number of commands. Each of the next mlines contains a command which is one of:

pushLeft x pushes x (-100 ≤ x ≤ 100) in the left end of the queue

pushRight x pushes x (-100 ≤ x ≤ 100) in the right end of the queue

popLeft pops an item from the left end of the queue

popRight pops an item from the right end of the queue

Output

For each case, print the case number in a line. Then for each operation, show its corresponding output as shown in the sample. Be careful about spelling.

Sample Input

Output for Sample Input

13 8pushLeft 1pushLeft 2pushRight -1pushRight 1

popLeft

popRight

popLeft

popRight

Case 1:Pushed in left: 1Pushed in left: 2Pushed in right: -1The queue is fullPopped from left: 2

Popped from right: -1

Popped from left: 1

The queue is empty

题目类型：双端队列

算法分析：直接使用STL中的deque模拟即可，只不过还要动态维护一个队列中元素个数cnt

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

int main()
{
//    ifstream cin ("aaa.txt");

    int t, flag = 1;
    cin >> t;

    while (t--)
    {
        int n, m;

        cin >> n >> m;
        string input;

        int i, cnt = 0;
        deque <int> dq;

        cout << "Case " << flag++ << ":" << endl;

        for (i = 0; i < m; i++)
        {
            cin >> input;

            if (input == "pushLeft")
            {
                int temp;
                cin >> temp;
                if (cnt < n)
                {
                    cout << "Pushed in left: " << temp << endl;
                    dq.push_front (temp);
                    cnt++;
                }

                else
                    cout << "The queue is full" << endl;
            }

            else if (input == "pushRight")
            {
                int temp;
                cin >> temp;
                if (cnt < n)
                {
                    cout << "Pushed in right: " << temp << endl;
                    dq.push_back (temp);
                    cnt++;
                }

                else
                    cout << "The queue is full" << endl;
            }

            else if (input == "popLeft")
            {
                if (cnt > 0)
                {
                    cout << "Popped from left: " << dq.front () << endl;
                    dq.pop_front ();
                    cnt--;
                }

                else
                    cout << "The queue is empty" << endl;
            }

            else if (input == "popRight")
            {
                if (cnt > 0)
                {
                    cout << "Popped from right: " << dq.back () << endl;
                    dq.pop_back ();
                    cnt--;
                }

                else
                    cout << "The queue is empty" << endl;
            }
        }
    }

return 0;
}

100

#include <iostream>

#include <fstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

int main()

{

// ifstream cin ("aaa.txt");

int t, flag = 1;

cin >> t;

while (t--)

{

int n, m;

cin >> n >> m;

string input;

int i, cnt = 0;

deque <int> dq;

cout << "Case " << flag++ << ":" << endl;

for (i = 0; i < m; i++)

{

cin >> input;

if (input == "pushLeft")

{

int temp;

cin >> temp;

if (cnt < n)

{

cout << "Pushed in left: " << temp << endl;

dq.push_front (temp);

cnt++;

}

else

cout << "The queue is full" << endl;

}

else if (input == "pushRight")

{

int temp;

cin >> temp;

if (cnt < n)

{

cout << "Pushed in right: " << temp << endl;

dq.push_back (temp);

cnt++;

}

else

cout << "The queue is full" << endl;

}

else if (input == "popLeft")

{

if (cnt > 0)

{

cout << "Popped from left: " << dq.front () << endl;

dq.pop_front ();

cnt--;

}

else

cout << "The queue is empty" << endl;

}

else if (input == "popRight")

{

if (cnt > 0)

{

cout << "Popped from right: " << dq.back () << endl;

dq.pop_back ();

cnt--;

}

else

cout << "The queue is empty" << endl;

}

return 0;

}

lightoj1202

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

27 8月 2015

1202 - Bishops

Now you are given the position of the two bishops. You have to find the minimum chess moves to take one to another. With a chess move, a bishop can be moved to a long distance (along the diagonal lines) with just one move.There is an Infinite chessboard. Two bishops are there. (Bishop means the chess piece that moves diagonally).

Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains four integers r₁ c₁ r₂ c₂ denoting the positions of the bishops. Each of the integers will be positive and not greater than 10⁹. You can also assume that the positions will be distinct.

Output

For each case, print the case number and the minimum moves required to take one bishop to the other. Print 'impossible' if it's not possible.

Sample Input	Output for Sample Input
31 1 10 101 1 10 111 1 5 3	Case 1: 1Case 2: impossibleCase 3: 2

题目类型：简单数学

算法分析：如果两个点的坐标都不相等且之间的直线的斜率为1或者是-1，则输出1，反之继续判断。判断的思路是做两条过两点，斜率分别为1和-1的直线，判断两直线的交点是否在整数点上

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 1e9 + 7;
const int maxn = 10000 + 66;


int main()
{
//    ifstream cin ("aaa.txt");

    int t,  flag = 1;
    cin >> t;

    while (t--)
    {
        cout << "Case " << flag++ << ": ";

        long long a1, b1, a2, b2;
        cin >> a1 >> b1 >> a2 >> b2;

        if (a2 != a1 && b2 != b1 && (b2 - b1) % (a2 - a1) == 0)
        {
            int temp = (b2 - b1) / (a2 - a1);
            if (temp == 1 || temp == -1)
            {
                cout << "1" << endl;
                continue;
            }
        }

        if (abs (a2 + b2 + a1 - b1) % 2)
            cout << "impossible" << endl;

        else
            cout << "2" << endl;
    }

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 1e9 + 7;

const int maxn = 10000 + 66;

int main()

{

// ifstream cin ("aaa.txt");

int t, flag = 1;

cin >> t;

while (t--)

{

cout << "Case " << flag++ << ": ";

long long a1, b1, a2, b2;

cin >> a1 >> b1 >> a2 >> b2;

if (a2 != a1 && b2 != b1 && (b2 - b1) % (a2 - a1) == 0)

{

int temp = (b2 - b1) / (a2 - a1);

if (temp == 1 || temp == -1)

{

cout << "1" << endl;

continue;

}

if (abs (a2 + b2 + a1 - b1) % 2)

cout << "impossible" << endl;

else

cout << "2" << endl;

}

return 0;

}

lightoj1198

maksyuki 发表于 oj 分类，标签: 基础算法-贪心

27 8月 2015

1198 - Karate Competition

Your secret agents have determined the skill of every member of the opposing team, and of course you know the skill of every member of your own team. You can use this information to decide which opposing player will play against each of your players in order to maximize your score. Assume that the player with the higher skill in a game will always win, and if the players have the same skill then they will draw.Your karate club challenged another karate club in your town. Each club enters N players into the match, and each player plays one game against a player from the other team. Each game that is won is worth 2 points, and each game that is drawn is worth 1 point. Your goal is to score as many points as possible.

You will be given the skills of your players and of the opposing players, you have to find the maximum number of points that your team can score.

Input

Input starts with an integer T (≤ 70), denoting the number of test cases.

Each case starts with a line containing an integer N (1 ≤ N ≤ 50). The next line contains N space separated integers denoting the skills of the players of your team. The next line also contains N space separated integers denoting the skills of the players of the opposite team. Each of the skills lies in the range [1, 1000].

Output

For each case, print the case number and the maximum number of points your team can score.

Sample Input

Output for Sample Input

424 76 2

6 2

4 7

5 10 1

10 7 1 4

15 3 8 7

Case 1: 4Case 2: 2Case 3: 4Case 4: 5

题目类型：贪心

算法分析：贪心策略是如果我最强比对方最强的能力高，则两者比；如果我最强的比对方最强的弱，则拿我队最弱的和对方最强的比；如果我最强的和对方最强的能力相同，则比较我队最弱的和对方最弱的，如果我队最弱的比对方最弱的强，则两者比；否则拿我最弱和对方最强的比

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 100 + 66;

int val_a[maxn], val_b[maxn];

int main()
{
//    ifstream cin ("aaa.txt");

    int t, flag = 1;
    cin >> t;

    while (t--)
    {
        cout << "Case " << flag++ << ": ";

        int n;
        cin >> n;

        for (int i = 0; i < n; i++)
            cin >> val_a[i];

        for (int i = 0; i < n; i++)
            cin >> val_b[i];

        sort (val_a, val_a + n, greater <int> ());
        sort (val_b, val_b + n, greater <int> ());

        int sum = 0, s_a = 0, e_a = n - 1, s_b = 0, e_b = n - 1, num = 0;

        while (num < n)
        {
            if (val_a[s_a] > val_b[s_b])
            {
                s_a++;
                s_b++;
                num++;
                sum += 2;
            }

            else if (val_a[s_a] == val_b[s_b])
            {
                if (val_a[e_a] > val_b[e_b])
                {
                    e_a--;
                    e_b--;
                    num++;
                    sum += 2;
                }

                else
                {
                    if (val_a[e_a] == val_b[s_b])
                        sum++;

                    e_a--;
                    s_b++;
                    num++;
                }
            }

            else
            {
                if (val_a[e_a] == val_b[s_b])
                    sum++;

                e_a--;
                s_b++;
                num++;
            }
        }

        cout << sum << endl;
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 100 + 66;

int val_a[maxn], val_b[maxn];

int main()

{

// ifstream cin ("aaa.txt");

int t, flag = 1;

cin >> t;

while (t--)

{

cout << "Case " << flag++ << ": ";

int n;

cin >> n;

for (int i = 0; i < n; i++)

cin >> val_a[i];

for (int i = 0; i < n; i++)

cin >> val_b[i];

sort (val_a, val_a + n, greater <int> ());

sort (val_b, val_b + n, greater <int> ());

int sum = 0, s_a = 0, e_a = n - 1, s_b = 0, e_b = n - 1, num = 0;

while (num < n)

{

if (val_a[s_a] > val_b[s_b])

{

s_a++;

s_b++;

num++;

sum += 2;

}

else if (val_a[s_a] == val_b[s_b])

{

if (val_a[e_a] > val_b[e_b])

{

e_a--;

e_b--;

num++;

sum += 2;

}

else

{

if (val_a[e_a] == val_b[s_b])

sum++;

e_a--;

s_b++;

num++;

}

else

{

if (val_a[e_a] == val_b[s_b])

sum++;

e_a--;

s_b++;

num++;

}

cout << sum << endl;

}

return 0;

}

lightoj1197

maksyuki 发表于 oj 分类，标签: 数论-素性分析

27 8月 2015

1197 - Help Hanzo

Before reaching Amakusa's castle, Hanzo has to pass some territories. The territories are numbered as a, a+1, a+2, a+3 ... b. But not all the territories are safe for Hanzo because there can be other fighters waiting for him. Actually he is not afraid of them, but as he is facing Amakusa, he has to save his stamina as much as possible.Amakusa, the evil spiritual leader has captured the beautiful princess Nakururu. The reason behind this is he had a little problem with Hanzo Hattori, the best ninja and the love of Nakururu. After hearing the news Hanzo got extremely angry. But he is clever and smart, so, he kept himself cool and made a plan to face Amakusa.

He calculated that the territories which are primes are safe for him. Now given a and b he needs to know how many territories are safe for him. But he is busy with other plans, so he hired you to solve this small problem!

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case contains a line containing two integers a and b (1 ≤ a ≤ b < 2³¹, b - a ≤ 100000).

Output

For each case, print the case number and the number of safe territories.

Sample Input	Output for Sample Input
32 363 733 11	Case 1: 11Case 2: 20Case 3: 4

Note

A number is said to be prime if it is divisible by exactly two different integers. So, first few primes are 2, 3, 5, 7, 11, 13, 17, ...

题目类型：素数

算法分析：由于问题的规模比较大，不可能将所有的范围内的素数都打表出来，只能将1~sqrt (2 ^ 31 - 1)内的素数先打表出来，然后再对于每个给定的区间(区间长度小于1000000)进行求解

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;

const int maxn = 50000 + 66;

bool prime[maxn*20];
long long primelist[maxn], prime_len;

void GetPrime ()
{
    memset (prime, true, sizeof (prime));
    prime_len = 0;

    long long i;
    for (i = 2; i <= maxn; i++)
    {
        if (prime[i])
            primelist[prime_len++] = i;

        long long j;
        for (j = 0; j < prime_len; j++)
        {
            if (i * primelist[j] > maxn)
                break;

            prime[i*primelist[j]] = false;
            if (i % primelist[j] == 0)
                break;
        }
    }
}


void Solve (long long a, long long b)
{
    memset (prime, true, sizeof (prime));

    for (long long i = 0; i < prime_len; i++)
    {
        long long temp = a / primelist[i];

        while (temp * primelist[i] < a || temp <= 1)
            temp++;

        for (long long j = temp * primelist[i]; j <= b; j += primelist[i])
        {
            if (j >= a)
                prime[j-a] = false;
        }
    }

    if (a == 1)
        prime[0] = false;

    long long tot = 0;
    for (long long i = a; i <= b; i++)
        if (prime[i-a])
            tot++;

    printf ("%lld\n", tot);
}


int main()
{
    GetPrime ();

//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        printf ("Case %d: ", flag++);

        long long a, b;
        scanf ("%lld%lld", &a, &b);

        Solve (a, b);
}
return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 50000 + 66;

bool prime[maxn*20];

long long primelist[maxn], prime_len;

void GetPrime ()

{

memset (prime, true, sizeof (prime));

prime_len = 0;

long long i;

for (i = 2; i <= maxn; i++)

{

if (prime[i])

primelist[prime_len++] = i;

long long j;

for (j = 0; j < prime_len; j++)

{

if (i * primelist[j] > maxn)

break;

prime[i*primelist[j]] = false;

if (i % primelist[j] == 0)

break;

}

void Solve (long long a, long long b)

{

memset (prime, true, sizeof (prime));

for (long long i = 0; i < prime_len; i++)

{

long long temp = a / primelist[i];

while (temp * primelist[i] < a || temp <= 1)

temp++;

for (long long j = temp * primelist[i]; j <= b; j += primelist[i])

{

if (j >= a)

prime[j-a] = false;

}

if (a == 1)

prime[0] = false;

long long tot = 0;

for (long long i = a; i <= b; i++)

if (prime[i-a])

tot++;

printf ("%lld\n", tot);

}

int main()

{

GetPrime ();

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d: ", flag++);

long long a, b;

scanf ("%lld%lld", &a, &b);

Solve (a, b);

}

return 0;

}

lightoj1183

maksyuki 发表于 oj 分类，标签: 数据结构-线段树

27 8月 2015

1183 - Computing Fast Average

1 i j v - change the value of the elements from i^th index to j^th index to v.Given an array of integers (0 indexed), you have to perform two types of queries in the array.

2 i j - find the average value of the integers from i^th index to j^th index.

You can assume that initially all the values in the array are 0.

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case contains two integers: n (1 ≤ n ≤ 10⁵), q (1 ≤ q ≤ 50000), where n denotes the size of the array. Each of the next q lines will contain a query of the form:

1 i j v (0 ≤ i ≤ j < n, 0 ≤ v ≤ 10000)

2 i j (0 ≤ i ≤ j < n)

Output

For each case, print the case number first. Then for each query of the form '2 i j' print the average value of the integers from i to j. If the result is an integer, print it. Otherwise print the result in 'x/y' form, where x denotes the numerator and y denotes the denominator of the result and x and y are relatively prime.

Sample Input

Output for Sample Input

110 61 0 6 62 0 1

1 1 1 2

2 0 5

1 0 3 7

2 0 1

Case 1:616/37

Note

Dataset is huge. Use faster i/o methods.

题目类型：线段树+Lazy-Tag

算法分析：直接使用Lazy标记的线段树求解即可，注意多组数据之间要初始化lazy数组和sum数组！！！

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

const int INF = 0x7FFFFFFF;
const int MOD = 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 66;

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

long long sum[maxn<<2], lazy[maxn<<2];

void PushUp (int rt)
{
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}

void PushDown (int rt, int l, int m, int r)
{
    if(lazy[rt] != -1)
    {
        lazy[rt<<1] = lazy[rt];
        lazy[rt<<1|1] = lazy[rt];
        sum[rt<<1] = lazy[rt] * (m - l + 1);
        sum[rt<<1|1] = lazy[rt] * (r - m);
        lazy[rt] = -1;
    }
}

void UpDate (int rt, int l, int r, long long L, long long R, long long vv)
{
    if (L <= l && r <= R)
    {
        lazy[rt] = vv;
        sum[rt] = vv * (r - l + 1);
        return ;
    }

    int m = (l + r) >> 1;
    PushDown (rt, l, m, r);
    if (L <= m)
        UpDate (lson, L, R, vv);

    if (R > m)
        UpDate (rson, L, R, vv);

    PushUp (rt);
}

long long Query(int rt, int l, int r, long long L, long long R)
{
    if (L <= l && r <= R)
        return sum[rt];

    int m = (l + r) >> 1;
    PushDown (rt, l, m, r);

    long long res = 0;
    if (L <= m)
        res += Query (lson, L, R);

    if (R > m)
        res += Query (rson, L, R);

    return res;
}

long long gcd (long long a, long long b)
{
    if (b == 0)
        return a;

    return gcd (b, a % b);
}

/*
    Case 1:
    23/2
    Case 2:
    9/2
    Case 3:
    622/3
*/

int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        printf ("Case %d:\n", flag++);

        long long n, q;
        scanf ("%lld%lld", &n, &q);

        memset (sum, 0, sizeof (sum));
        fill (lazy, lazy + (maxn << 2), -1);

        for (int i = 1; i <= q; i++)
        {
            long long oper, a, b, c;
            scanf ("%lld%lld%lld", &oper, &a, &b);

            if (oper == 2)
            {
                long long tt = Query (1, 0, n - 1, a, b);

                if (tt % (b - a + 1) == 0)
                    printf ("%lld\n", tt / (b - a + 1));

                else
                {
                    long long aa = gcd (tt, (b - a + 1));
                    printf ("%lld/%lld\n", tt / aa, (b - a + 1) / aa);
                }

            }

            else
            {
                scanf ("%lld", &c);
                UpDate (1, 0, n - 1, a, b, c);
            }
        }
    }
    return 0;
}

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

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

const int INF = 0x7FFFFFFF;

const int MOD = 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 66;

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

long long sum[maxn<<2], lazy[maxn<<2];

void PushUp (int rt)

{

sum[rt] = sum[rt<<1] + sum[rt<<1|1];

}

void PushDown (int rt, int l, int m, int r)

{

if(lazy[rt] != -1)

{

lazy[rt<<1] = lazy[rt];

lazy[rt<<1|1] = lazy[rt];

sum[rt<<1] = lazy[rt] * (m - l + 1);

sum[rt<<1|1] = lazy[rt] * (r - m);

lazy[rt] = -1;

}

void UpDate (int rt, int l, int r, long long L, long long R, long long vv)

{

if (L <= l && r <= R)

{

lazy[rt] = vv;

sum[rt] = vv * (r - l + 1);

return ;

}

int m = (l + r) >> 1;

PushDown (rt, l, m, r);

if (L <= m)

UpDate (lson, L, R, vv);

if (R > m)

UpDate (rson, L, R, vv);

PushUp (rt);

}

long long Query(int rt, int l, int r, long long L, long long R)

{

if (L <= l && r <= R)

return sum[rt];

int m = (l + r) >> 1;

PushDown (rt, l, m, r);

long long res = 0;

if (L <= m)

res += Query (lson, L, R);

if (R > m)

res += Query (rson, L, R);

return res;

}

long long gcd (long long a, long long b)

{

if (b == 0)

return a;

return gcd (b, a % b);

}

Case 1:

23/2

Case 2:

9/2

Case 3:

622/3

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d:\n", flag++);

long long n, q;

scanf ("%lld%lld", &n, &q);

memset (sum, 0, sizeof (sum));

fill (lazy, lazy + (maxn << 2), -1);

for (int i = 1; i <= q; i++)

{

long long oper, a, b, c;

scanf ("%lld%lld%lld", &oper, &a, &b);

if (oper == 2)

{

long long tt = Query (1, 0, n - 1, a, b);

if (tt % (b - a + 1) == 0)

printf ("%lld\n", tt / (b - a + 1));

else

{

long long aa = gcd (tt, (b - a + 1));

printf ("%lld/%lld\n", tt / aa, (b - a + 1) / aa);

}

else

{

scanf ("%lld", &c);

UpDate (1, 0, n - 1, a, b, c);

}

return 0;

}

1 2 3 4 下一页最后一页

2015年8月
一	二	三	四	五	六	日
« 7月				9月 »
					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

Output

Sample Input

Output for Sample Input

Notes

Input

Output

Sample Input

Output for Sample Input

Note

Input

Output

Sample Input

Output for Sample Input

Note

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

Output

Sample Input

Output for Sample Input

Note

Input

Output

Sample Input

Output for Sample Input

Note

Output

Sample Input

Output for Sample Input

Note

Input

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

Note

Input

Output

Sample Input

Output for Sample Input

Note

分类目录

标签云

书签

近期评论