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;

}

lightoj1174

maksyuki 发表于 oj 分类，标签: 图论-最短路

27 8月 2015

1174 - Commandos

InputA group of commandos were assigned a critical task. They are to destroy an enemy head quarter. The enemy head quarter consists of several buildings and the buildings are connected by roads. The commandos must visit each building and place a bomb at the base of each building. They start their mission at the base of a particular building and from there they disseminate to reach each building. The commandos must use the available roads to travel between buildings. Any of them can visit one building after another, but they must all gather at a common place when their task in done. In this problem, you will be given the description of different enemy headquarters. Your job is to determine the minimum time needed to complete the mission. Each commando takes exactly one unit of time to move between buildings. You may assume that the time required to place a bomb is negligible. Each commando can carry unlimited number of bombs and there is an unlimited supply of commando troops for the mission.

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

The first line of each case starts with a positive integer N (1 ≤ N ≤ 100), where N denotes the number of buildings in the head quarter. The next line contains a positive integer R, where Ris the number of roads connecting two buildings. Each of the next R lines contain two distinct numbers u v (0 ≤ u, v < N), this means there is a road connecting building u to building v. The buildings are numbered from 0 to N-1. The last line of each case contains two integers s d (0 ≤ s, d < N). Where s denotes the building from where the mission starts and d denotes the building where they must meet. You may assume that two buildings will be directly connected by at most one road. The input will be given such that, it will be possible to go from any building to another by using one or more roads.

Output

For each case, print the case number and the minimum time required to complete the mission.

Sample Input

Output for Sample Input

2430 1

2 1

1 3

0 3

0 1

1 0

Case 1: 4Case 2: 1

题目类型：最短路

算法分析：使用SPFA和一个邻接表、一个逆邻接表分别求得最短路径，然后将每个点的两个最短路相加再取最大值，否则会WA！！！！！！

#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 i64 long long

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


//分别表示顶点v。w和下一个邻接的位置
struct Node
{
    int v, w, next;
};

Node edge[maxn*maxn];
int head[maxn], edgelen;//分别表示顶点的表头节点和边的数量

Node redge[maxn*maxn];
int rhead[maxn], redgelen;

//将所有的数组均初始化为-1
void Init ()
{
    memset (head, -1, sizeof (head));
    memset (edge, -1, sizeof (edge));
    edgelen = 0;

    memset (rhead, -1, sizeof (rhead));
    memset (redge, -1, sizeof (redge));
    redgelen = 0;
}

//使用头插法构建
void AddEdge (int u, int v, int w)
{
    edge[edgelen].v = v;
    edge[edgelen].w = w;
    edge[edgelen].next = head[u];
    head[u] = edgelen++;

    redge[redgelen].v = u;
    redge[redgelen].w = w;
    redge[redgelen].next = rhead[v];
    rhead[v] = redgelen++;
}

//分别表示源点到其他顶点的最短距离、顶点是否在队列中的判断数组、顶点入队列的次数和顶点个数
long long dis[maxn], inq[maxn];
int n, m;

long long rdis[maxn], rinq[maxn];


//数组下标从1开始
void spfa (int s)
{
    for (int i = 1; i <= n; i++)//初始化dis数组和inq数组
    {
        dis[i] = INF;
        inq[i] = 0;
    }

    dis[s] = 0;//将源点的dis数组值初始化为0，重要！！
    queue <int> qu;
    qu.push (s);
    inq[s]++;//将源点标志为在队列中
    while (!qu.empty ())
    {
        int tt = qu.front(); qu.pop (); inq[tt]--;
        int pa = head[tt];
        while (pa != -1)
        {
            int pb = edge[pa].v;
            if (dis[tt] < INF && dis[pb] > dis[tt] + edge[pa].w)//松弛操作
            {
                dis[pb] = dis[tt] + edge[pa].w;
                if (!inq[pb])//如果被松弛的节点不在队列中，则将该节入队
                {
                    qu.push (pb);
                    inq[pb]++;
                }
            }
            pa = edge[pa].next;
        }
    }
}

//数组下标从1开始
void rspfa (int s)
{
    for (int i = 1; i <= n; i++)//初始化dis数组和inq数组
    {
        rdis[i] = INF;
        rinq[i] = 0;
    }

    rdis[s] = 0;//将源点的dis数组值初始化为0，重要！！
    queue <int> qu;
    qu.push (s);
    rinq[s]++;//将源点标志为在队列中
    while (!qu.empty ())
    {
        int tt = qu.front(); qu.pop (); rinq[tt]--;
        int pa = rhead[tt];
        while (pa != -1)
        {
            int pb = redge[pa].v;
            if (rdis[tt] < INF && rdis[pb] > rdis[tt] + redge[pa].w)//松弛操作
            {
                rdis[pb] = rdis[tt] + redge[pa].w;
                if (!rinq[pb])//如果被松弛的节点不在队列中，则将该节入队
                {
                    qu.push (pb);
                    rinq[pb]++;
                }
            }
            pa = redge[pa].next;
        }
    }
}

int main()
{
//    CPPFF;

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

    while (t--)
    {
        Init ();
        cin >> n >> m;
        for (int i = 1; i <= m; i++)
        {
            int u, v;
            cin >> u >> v;
            u++, v++;
            AddEdge(u, v, 1);
            AddEdge(v, u, 1);
        }

        int s, e;
        cin >> s >> e;
        spfa (s + 1);
        rspfa (e + 1);

       long long maxval = -INF;
       for (int i = 1; i <= n; i++)
            maxval = max (maxval, dis[i] + rdis[i]);

        cout << "Case " << flag++ <<": " << maxval << 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

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

#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 i64 long long

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 300 + 66;

//分别表示顶点v。w和下一个邻接的位置

struct Node

{

int v, w, next;

};

Node edge[maxn*maxn];

int head[maxn], edgelen;//分别表示顶点的表头节点和边的数量

Node redge[maxn*maxn];

int rhead[maxn], redgelen;

//将所有的数组均初始化为-1

void Init ()

{

memset (head, -1, sizeof (head));

memset (edge, -1, sizeof (edge));

edgelen = 0;

memset (rhead, -1, sizeof (rhead));

memset (redge, -1, sizeof (redge));

redgelen = 0;

}

//使用头插法构建

void AddEdge (int u, int v, int w)

{

edge[edgelen].v = v;

edge[edgelen].w = w;

edge[edgelen].next = head[u];

head[u] = edgelen++;

redge[redgelen].v = u;

redge[redgelen].w = w;

redge[redgelen].next = rhead[v];

rhead[v] = redgelen++;

}

//分别表示源点到其他顶点的最短距离、顶点是否在队列中的判断数组、顶点入队列的次数和顶点个数

long long dis[maxn], inq[maxn];

int n, m;

long long rdis[maxn], rinq[maxn];

//数组下标从1开始

void spfa (int s)

{

for (int i = 1; i <= n; i++)//初始化dis数组和inq数组

{

dis[i] = INF;

inq[i] = 0;

}

dis[s] = 0;//将源点的dis数组值初始化为0，重要！！

queue <int> qu;

qu.push (s);

inq[s]++;//将源点标志为在队列中

while (!qu.empty ())

{

int tt = qu.front(); qu.pop (); inq[tt]--;

int pa = head[tt];

while (pa != -1)

{

int pb = edge[pa].v;

if (dis[tt] < INF && dis[pb] > dis[tt] + edge[pa].w)//松弛操作

{

dis[pb] = dis[tt] + edge[pa].w;

if (!inq[pb])//如果被松弛的节点不在队列中，则将该节入队

{

qu.push (pb);

inq[pb]++;

}

pa = edge[pa].next;

}

//数组下标从1开始

void rspfa (int s)

{

for (int i = 1; i <= n; i++)//初始化dis数组和inq数组

{

rdis[i] = INF;

rinq[i] = 0;

}

rdis[s] = 0;//将源点的dis数组值初始化为0，重要！！

queue <int> qu;

qu.push (s);

rinq[s]++;//将源点标志为在队列中

while (!qu.empty ())

{

int tt = qu.front(); qu.pop (); rinq[tt]--;

int pa = rhead[tt];

while (pa != -1)

{

int pb = redge[pa].v;

if (rdis[tt] < INF && rdis[pb] > rdis[tt] + redge[pa].w)//松弛操作

{

rdis[pb] = rdis[tt] + redge[pa].w;

if (!rinq[pb])//如果被松弛的节点不在队列中，则将该节入队

{

qu.push (pb);

rinq[pb]++;

}

pa = redge[pa].next;

}

int main()

{

// CPPFF;

int t, flag = 1;

cin >> t;

while (t--)

{

Init ();

cin >> n >> m;

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

{

int u, v;

cin >> u >> v;

u++, v++;

AddEdge(u, v, 1);

AddEdge(v, u, 1);

}

int s, e;

cin >> s >> e;

spfa (s + 1);

rspfa (e + 1);

long long maxval = -INF;

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

maxval = max (maxval, dis[i] + rdis[i]);

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

}

return 0;

}

lightoj1164

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

27 8月 2015

1164 - Horrible Queries

0 x y v - you have to add v to all numbers in the range of x to y (inclusive), where x and y are two indexes of the array.World is getting more evil and it's getting tougher to get into the Evil League of Evil. Since the legendary Bad Horse has retired, now you have to correctly answer the evil questions of Dr. Horrible, who has a PhD in horribleness (but not in Computer Science). You are given an array of n elements, which are initially all 0. After that you will be given q commands. They are -

1 x y - output a line containing a single integer which is the sum of all the array elements between x and y (inclusive).

The array is indexed from 0 to n - 1.

Input

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

Each case contains two integers n (1 ≤ n ≤ 10⁵) and q (1 ≤ q ≤ 50000). Each of the next q lines contains a task in one of the following form:

0 x y v (0 ≤ x ≤ y < n, 1 ≤ v ≤ 1000)

1 x y (0 ≤ x ≤ y < n)

Output

For each case, print the case number first. Then for each query '1 x y', print the sum of all the array elements between x and y.

Sample Input

Output for Sample Input

210 50 0 9 101 1 6

0 3 7 2

0 4 5 1

1 5 5

20 3

0 10 12 1

1 11 12

1 19 19

Case 1:6013Case 2:

Note

Dataset is huge. Use faster i/o methods.

题目类型：线段树

算法分析：线段树的成段更新和区间求和问题，直接按照题目的要求求解即可

#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;
long long lazy[maxn<<2];
long long sum[maxn<<2];

int n, q;

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])
    {
        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] = 0;
    }
}

/*void Build (int rt, int l, int r)
{
    lazy[rt] = 0;

    if (l == r)
    {
        scanf ("%lld", &sum[rt]);
        return ;
    }

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

	Build (lson);
	Build (rson);
	PushUp (rt);
}*/

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

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

    if (L <= m)
        UpDate (lson, L, R, add);

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

	PushUp (rt);
}

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

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

    if (L <= m)
        ans += Query (lson, L, R);

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

return ans;
}



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

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

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


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

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

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

            if (cmd == 0)
            {
                int val_a, val_b, val;
                scanf ("%d%d%d", &val_a, &val_b, &val);
                val_a++, val_b++;
                UpDate (1, 1, n, val_a, val_b, val);
            }

            else
            {
                int val_a, val_b;
                scanf ("%d%d", &val_a, &val_b);
                val_a++, val_b++;
                printf ("%lld\n", Query (1, 1, n, val_a, val_b));
            }
        }
    }

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

#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;

long long lazy[maxn<<2];

long long sum[maxn<<2];

int n, q;

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])

{

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] = 0;

}

/*void Build (int rt, int l, int r)

{

lazy[rt] = 0;

if (l == r)

{

scanf ("%lld", &sum[rt]);

return ;

}

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

PushDown (rt, l, m, r);

Build (lson);

Build (rson);

PushUp (rt);

}*/

void UpDate (int rt, int l, int r, int L, int R, int add)

{

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

{

lazy[rt] += add;

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

return ;

}

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

PushDown (rt, l, m, r);

if (L <= m)

UpDate (lson, L, R, add);

if (R > m)

UpDate (rson, L, R, add);

PushUp (rt);

}

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

{

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

{

return sum[rt];

}

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

PushDown (rt, l, m, r);

long long ans = 0;

if (L <= m)

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

if (R > m)

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

return ans;

}

int main()

{

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

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

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

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

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

memset (lazy, 0, sizeof (lazy));

int i;

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

{

int cmd;

scanf ("%d", &cmd);

if (cmd == 0)

{

int val_a, val_b, val;

scanf ("%d%d%d", &val_a, &val_b, &val);

val_a++, val_b++;

UpDate (1, 1, n, val_a, val_b, val);

}

else

{

int val_a, val_b;

scanf ("%d%d", &val_a, &val_b);

val_a++, val_b++;

printf ("%lld\n", Query (1, 1, n, val_a, val_b));

}

return 0;

}

lightoj1140

maksyuki 发表于 oj 分类，标签: 组合数学-计数

27 8月 2015

1140 - How Many Zeroes?

InputJimmy writes down the decimal representations of all natural numbers between and including m and n, (m ≤ n). How many zeroes will he write down?

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

Each case contains two unsigned 32-bit integers m and n, (m ≤ n).

Output

For each case, print the case number and the number of zeroes written down by Jimmy.

Sample Input

Output for Sample Input

510 11100 2000 500

1234567890 2345678901

0 4294967295

Case 1: 1Case 2: 22Case 3: 92Case 4: 987654304

Case 5: 3825876150

题目类型：组合计数

算法分析：每次从小到大判断N的每一位上的数字，如果当前位上的数字不为0，则该位左边的所有的数字都可以和该位右边的每一位上的数字构成一个合理的结果(每一位上有0~9共10个数)。如果当前位上的数字为0，则该位左边只有小于当前数1的个数可以和右边的right+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>
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 = 6000 + 66;

long long Get (long long val)
{
    if (val < 0)
        return 0;

    long long cnt = 1, right = 0, res = 1;
    while (val >= 10)
    {
        long long tt = val % 10;
        val /= 10;
        if (tt)
            res += val * cnt;

        else
            res += (val - 1) * cnt + right + 1;

        right += tt * cnt;
        cnt *= 10;
    }

    return res;
}


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

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

    long long a, b;
    while (t--)
    {
        cin >> a >> b;

        cout << "Case " << flag++ << ": " << Get (b) - Get (a - 1) << 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>

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 = 6000 + 66;

long long Get (long long val)

{

if (val < 0)

return 0;

long long cnt = 1, right = 0, res = 1;

while (val >= 10)

{

long long tt = val % 10;

val /= 10;

if (tt)

res += val * cnt;

else

res += (val - 1) * cnt + right + 1;

right += tt * cnt;

cnt *= 10;

}

return res;

}

int main()

{

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

int t, flag = 1;

cin >> t;

long long a, b;

while (t--)

{

cin >> a >> b;

cout << "Case " << flag++ << ": " << Get (b) - Get (a - 1) << endl;

}

return 0;

}

lightoj1131

maksyuki 发表于 oj 分类，标签: 数值-矩阵快速幂取模

27 8月 2015

1131 - Just Two Functions

Find f_n % M and g_n % M. (% stands for the modulo operation.)Let f_n = a₁ * f_n-1 + b₁ * f_n-2 + c₁ * g_n-3g_n = a₂ * g_n-1 + b₂ * g_n-2 + c₂ * f_n-3

Input

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

Each case starts with a blank line. Next line contains three integers a₁ b₁ c₁ (0 ≤ a₁, b₁, c₁ < 25000). Next line contains three integers a₂ b₂ c₂ (0 ≤ a₂, b₂, c₂ < 25000). Next line contains three integers f₀ f₁ f₂ (0 ≤ f₀, f₁, f₂ < 25000). Next line contains three integers g₀ g₁ g₂ (0 ≤ g₀, g₁, g₂ < 25000). The next line contains an integer M (1 ≤ M < 25000).

Next line contains an integer q (1 ≤ q ≤ 100) denoting the number of queries. Next line contains q space separated integers denoting n. Each of these integers is non-negative and less than 2³¹.

Output

For each case, print the case number in a line. Then for each query, you have to print one line containing f_n % M and g_n % M.

Sample Input

Output for Sample Input

21 1 00 0 00 1 1

0 0 0

20000

1 2 3 4 5 6 7 8 9 10

1 1 1

2 2 2

20000

2 4 6 8 10

Case 1:1 01 02 03 0

5 0

8 0

13 0

21 0

34 0

55 0

Case 2:

2 2

10 10

34 34

114 114

386 386

题目类型：矩阵快速幂取模

算法分析：由于两个递推式之间不是独立的，所以需要将两个递推式用一个矩阵乘幂表示！！！之后直接上模板即可

#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 = 6;

long long n = 6;//表示方阵的尺寸，必须恰好为运算的大小

long long MOD;
//申请变量
struct Mat
{
    long long mat[maxn][maxn];
};


//重载Mat乘法运算
Mat operator * (Mat a, Mat b)
{
    Mat c;
    memset (c.mat, 0, sizeof (c.mat));
    for (long long k = 0; k < n; k++)
    {
        for (long long i = 0; i < n; i++)
        {
            if (a.mat[i][k] == 0) continue;

            for (long long j = 0; j < n; j++)
            {
                if (b.mat[k][j] == 0) continue;

                c.mat[i][j] = (c.mat[i][j] + ((a.mat[i][k] % MOD) * (b.mat[k][j] % MOD) % MOD)) % MOD;
            }
        }
    }
return c;
}

//重载Mat乘幂运算
Mat operator ^ (Mat a, long long k)
{
    Mat c;
    for (long long i = 0; i < n; i++)
        for(long long j = 0; j < n; j++)
        c.mat[i][j] = (i == j);

    while (k)
    {
        if(k & 1)
            c = c * a;

        a = a * a;
        k >>= 1;
    }

return c;
}

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

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

    while(t--)
	{
        cout << "Case " << flag++ << ":" << endl;
        long long a1, b1, c1, a2, b2, c2, f0, f1, f2, g0, g1, g2;

        cin >> a1 >> b1 >> c1 >> a2 >> b2 >> c2 >> f0 >> f1 >> f2 >> g0 >> g1 >> g2 >> MOD;

		Mat aa, a0;
        aa.mat[0][0] = a1, aa.mat[0][1] = b1, aa.mat[0][2] = 0, aa.mat[0][3] = 0, aa.mat[0][4] = 0, aa.mat[0][5] = c1;
        aa.mat[1][0] = 1, aa.mat[1][1] = 0, aa.mat[1][2] = 0, aa.mat[1][3] = 0, aa.mat[1][4] = 0, aa.mat[1][5] = 0;
        aa.mat[2][0] = 0, aa.mat[2][1] = 1, aa.mat[2][2] = 0, aa.mat[2][3] = 0, aa.mat[2][4] = 0, aa.mat[2][5] = 0;
		aa.mat[3][0] = 0, aa.mat[3][1] = 0, aa.mat[3][2] = c2, aa.mat[3][3] = a2, aa.mat[3][4] = b2,  aa.mat[3][5] = 0;
		aa.mat[4][0] = 0, aa.mat[4][1] = 0, aa.mat[4][2] = 0, aa.mat[4][3] = 1, aa.mat[4][4] = 0, aa.mat[4][5] = 0;
		aa.mat[5][0] = 0, aa.mat[5][1] = 0, aa.mat[5][2] = 0, aa.mat[5][3] = 0, aa.mat[5][4] = 1, aa.mat[5][5] = 0;

		a0.mat[0][0] = f2, a0.mat[1][0] = f1, a0.mat[2][0] = f0, a0.mat[3][0] = g2, a0.mat[4][0] = g1, a0.mat[5][0] = g0;

        int q;
        cin >> q;

		long long tt;
		Mat res;
        for (int i = 1; i <= q; i++)
		{
			cin >> tt;
//			cout << tt << endl;

            if (tt == 0)
				cout << f0 % MOD << " " << g0 % MOD << endl;

			else if (tt == 1)
				cout << f1 % MOD << " " << g1 % MOD << endl;

			else if (tt == 2)
				cout << f2 % MOD << " " << g2 % MOD << endl;

			else
			{
				res = aa ^ (tt - 2);
				res = res * a0;
				cout << res.mat[0][0] % MOD << " " << res.mat[3][0] % MOD << 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

#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 = 6;

long long n = 6;//表示方阵的尺寸，必须恰好为运算的大小

long long MOD;

//申请变量

struct Mat

{

long long mat[maxn][maxn];

};

//重载Mat乘法运算

Mat operator * (Mat a, Mat b)

{

Mat c;

memset (c.mat, 0, sizeof (c.mat));

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

{

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

{

if (a.mat[i][k] == 0) continue;

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

{

if (b.mat[k][j] == 0) continue;

c.mat[i][j] = (c.mat[i][j] + ((a.mat[i][k] % MOD) * (b.mat[k][j] % MOD) % MOD)) % MOD;

}

return c;

}

//重载Mat乘幂运算

Mat operator ^ (Mat a, long long k)

{

Mat c;

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

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

c.mat[i][j] = (i == j);

while (k)

{

if(k & 1)

c = c * a;

a = a * a;

k >>= 1;

}

return c;

}

int main()

{

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

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

int t, flag = 1;

cin >> t;

while(t--)

{

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

long long a1, b1, c1, a2, b2, c2, f0, f1, f2, g0, g1, g2;

cin >> a1 >> b1 >> c1 >> a2 >> b2 >> c2 >> f0 >> f1 >> f2 >> g0 >> g1 >> g2 >> MOD;

Mat aa, a0;

aa.mat[0][0] = a1, aa.mat[0][1] = b1, aa.mat[0][2] = 0, aa.mat[0][3] = 0, aa.mat[0][4] = 0, aa.mat[0][5] = c1;

aa.mat[1][0] = 1, aa.mat[1][1] = 0, aa.mat[1][2] = 0, aa.mat[1][3] = 0, aa.mat[1][4] = 0, aa.mat[1][5] = 0;

aa.mat[2][0] = 0, aa.mat[2][1] = 1, aa.mat[2][2] = 0, aa.mat[2][3] = 0, aa.mat[2][4] = 0, aa.mat[2][5] = 0;

aa.mat[3][0] = 0, aa.mat[3][1] = 0, aa.mat[3][2] = c2, aa.mat[3][3] = a2, aa.mat[3][4] = b2, aa.mat[3][5] = 0;

aa.mat[4][0] = 0, aa.mat[4][1] = 0, aa.mat[4][2] = 0, aa.mat[4][3] = 1, aa.mat[4][4] = 0, aa.mat[4][5] = 0;

aa.mat[5][0] = 0, aa.mat[5][1] = 0, aa.mat[5][2] = 0, aa.mat[5][3] = 0, aa.mat[5][4] = 1, aa.mat[5][5] = 0;

a0.mat[0][0] = f2, a0.mat[1][0] = f1, a0.mat[2][0] = f0, a0.mat[3][0] = g2, a0.mat[4][0] = g1, a0.mat[5][0] = g0;

int q;

cin >> q;

long long tt;

Mat res;

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

{

cin >> tt;

// cout << tt << endl;

if (tt == 0)

cout << f0 % MOD << " " << g0 % MOD << endl;

else if (tt == 1)

cout << f1 % MOD << " " << g1 % MOD << endl;

else if (tt == 2)

cout << f2 % MOD << " " << g2 % MOD << endl;

else

{

res = aa ^ (tt - 2);

res = res * a0;

cout << res.mat[0][0] % MOD << " " << res.mat[3][0] % MOD << endl;

}

return 0;

}

lightoj1129

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

27 8月 2015

1129 - Consistency Checker

123SETI is receiving some weird signals for the past few days. After converting them to our number system they found out that some numbers are repeating. Due to travelling millions of miles signal gets distorted. Now they asked you check the consistency of their data sets. The consistency is that, no number is the prefix another number in that data set. Let's consider a data set:

5123456
123456

In this data set, numbers not consistent, because the first number is the prefix of the third one.

Input

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

Each case starts with an integer n (1 ≤ n ≤ 10000) denoting the total numbers in their list. Each of the next n lines contains one unique phone number. A number is a sequence of digits and has length from 1 to 10.

Output

For each case, print the case number and 'YES' if the list is consistent or 'NO' if it's not.

Sample Input

Output for Sample Input

2391197625999

91125426

113

12340

123440

12345

98346

Case 1: NOCase 2: YES

题目类型：Trie树

算法分析：将所有的单词插入到Trie树中，然后对于每个输入中的单词，查询其终止节点是否有后继节点即可

#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 = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 10000 + 66;

char ss[maxn][16];

struct Trie
{
    int next[maxn*10+66][10];
	int len, root;

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

		len++;
		return len - 1;
	}

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

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

			p = next[p][s[i]-'0'];
		}
    }

    bool Query (char *s)
    {
        int p = root;
        for (int i = 0; s[i]; i++)
		{
            if (next[p][s[i]-'0'] == -1)
				return false;

			p = next[p][s[i]-'0'];
		}

		for (int i = 0; i < 10; i++)
            if (next[p][i] != -1)
				return true;

		return false;
    }
};

Trie aa;

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

    int t, flag = 1;

    cin >> t;

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

        aa.init ();

        int n;
        cin >>n;
        for (int i = 1; i <= n; i++)
		{
			cin >> ss[i];
			aa.Insert(ss[i]);
		}

		bool is_valid = true;
        for (int i = 1; i <= n; i++)
		{
            if (aa.Query(ss[i]))
			{
				is_valid = false;
				break;
			}
		}

		if (is_valid)
			cout << "YES" << endl;

		else
			cout << "NO" << 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

#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 = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 10000 + 66;

char ss[maxn][16];

struct Trie

{

int next[maxn*10+66][10];

int len, root;

int newnode ()

{

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

next[len][i] = -1;

len++;

return len - 1;

}

void init ()

{

len = 0;

root = newnode ();

}

void Insert (char *s)

{

int p = root;

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

{

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

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

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

}

bool Query (char *s)

{

int p = root;

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

{

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

return false;

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

}

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

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

return true;

return false;

}

};

Trie aa;

int main()

{

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

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

int t, flag = 1;

cin >> t;

while (t--)

{

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

aa.init ();

int n;

cin >>n;

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

{

cin >> ss[i];

aa.Insert(ss[i]);

}

bool is_valid = true;

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

{

if (aa.Query(ss[i]))

{

is_valid = false;

break;

}

if (is_valid)

cout << "YES" << endl;

else

cout << "NO" << endl;

}

return 0;

}

lightoj1127

maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举

27 8月 2015

1127 - Funny Knapsack

InputGiven n integers and a knapsack of weight W, you have to count the number of combinations for which you can add the items in the knapsack without overflowing the weight.

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

Each case contains two integers n (1 ≤ n ≤ 30) and W (1 ≤ W ≤ 2 * 10⁹) and the next line will contain n integers separated by spaces. The integers will be non negative and less than 10⁹.

Output

For each set of input, print the case number and the number of possible combinations.

Sample Input

Output for Sample Input

31 111 12

3 10

1 2 4

Case 1: 2Case 2: 1Case 3: 8

题目类型：折半枚举

算法分析：由于物品的个数比较少，所以将物品大致分为两堆，然后分别枚举组合的情况，最后再查找小于w的组合个数

#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 = 60000 + 66;

long long ans[36], sa[maxn], sb[maxn], len_a, len_b;
long long n, w;

void DFS (int flag, int cur, long long sum)
{
    if (cur == flag)
    {
        if (flag == n / 2)
            sa[len_a++] = sum;

        else
            sb[len_b++] = sum;

        return ;
    }


    DFS (flag, cur + 1, sum);
    DFS (flag, cur + 1, sum + ans[cur]);

}


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

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

    while (t--)
    {

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

        len_a = len_b = 0;

        DFS (n / 2, 0, 0);
        DFS (n, n / 2 , 0);

        sort (sa, sa + len_a);

        long long sum = 0;

        for (i = 0; i < len_b; i++)
        {
            sum += upper_bound (sa, sa + len_a, w - sb[i]) - sa;
        }

        cout << "Case " << flag++ << ": " << sum << 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 = 60000 + 66;

long long ans[36], sa[maxn], sb[maxn], len_a, len_b;

long long n, w;

void DFS (int flag, int cur, long long sum)

{

if (cur == flag)

{

if (flag == n / 2)

sa[len_a++] = sum;

else

sb[len_b++] = sum;

return ;

}

DFS (flag, cur + 1, sum);

DFS (flag, cur + 1, sum + ans[cur]);

}

int main()

{

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

int t, flag = 1;

cin >> t;

while (t--)

{

cin >> n >> w;

int i;

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

cin >> ans[i];

len_a = len_b = 0;

DFS (n / 2, 0, 0);

DFS (n, n / 2 , 0);

sort (sa, sa + len_a);

long long sum = 0;

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

{

sum += upper_bound (sa, sa + len_a, w - sb[i]) - sa;

}

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

}

return 0;

}

lightoj1116

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

27 8月 2015

1116 - Ekka Dokka

They want to divide the cake such that N * M = W, where W is the dashing factor set by them. Now you know their dashing factor, you have to find whether they can buy the desired cake or not.Ekka and his friend Dokka decided to buy a cake. They both love cakes and that's why they want to share the cake after buying it. As the name suggested that Ekka is very fond of odd numbers and Dokka is very fond of even numbers, they want to divide the cake such that Ekka gets a share of N square centimeters and Dokka gets a share of M square centimeters whereN is odd and M is even. Both N and M are positive integers.

Input

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

Each case contains an integer W (2 ≤ W < 2⁶³). And W will not be a power of 2.

Output

For each case, print the case number first. After that print "Impossible" if they can't buy their desired cake. If they can buy such a cake, you have to print N and M. If there are multiple solutions, then print the result where M is as small as possible.

Sample Input	Output for Sample Input
310512	Case 1: 5 2Case 2: ImpossibleCase 3: 3 4

题目类型：位运算

算法分析：直接从小到大枚举所有的合数约数并判断时间复杂度是O(n)的，会TLE。这里使用的方法是首先判断n是否是偶数，如果不是则直接退出判断，输出Impossible；反之则将n左移一位判断移位后的n是否是奇数，如果是则找到，直接退出输出答案即可；反之则继续判断。该方法的时间复杂度也是O(n)的，不过这里的n表示的是输入数的二进制位数，而二进制位数不超过63，所以不会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>
using namespace std;

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

const int maxn = 1000 + 66;

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

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

    while (t--)
    {
        long long n;
        cin >> n;
        cout << "Case " << flag++ << ": ";

        bool is_find = false;
        long long temp = n;

        while (1)
        {
            if (temp & 1)
                break;

            temp >>= 1;
            if (temp & 1)
            {
                is_find = true;
                break;
            }
        }

        if (is_find)
            cout << temp << " " << n / temp << endl;

        else
            cout << "Impossible" << 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>

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 10000007;

const int maxn = 1000 + 66;

int main()

{

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

int t, flag = 1;

cin >> t;

while (t--)

{

long long n;

cin >> n;

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

bool is_find = false;

long long temp = n;

while (1)

{

if (temp & 1)

break;

temp >>= 1;

if (temp & 1)

{

is_find = true;

break;

}

if (is_find)

cout << temp << " " << n / temp << endl;

else

cout << "Impossible" << endl;

}

return 0;

}

lightoj1113

maksyuki 发表于 oj 分类，标签: 数据结构-栈/单调

27 8月 2015

1113 - Discover the Web

BACK: If the backward stack is empty, the command is ignored. Otherwise, push the current page on the top of the forward stack. Pop the page from the top of the backward stack, making it the new current page.Standard web browsers contain features to move backward and forward among the pages recently visited. One way to implement these features is to use two stacks to keep track of the pages that can be reached by moving backward and forward. You are asked to implement this. The commands are:

FORWARD: If the forward stack is empty, the command is ignored. Otherwise, push the current page on the top of the backward stack. Pop the page from the top of the forward stack, making it the new current page.
VISIT <url>: Push the current page on the top of the backward stack, and make the URL specified the new current page. The forward stack is emptied.
QUIT: Quit the browser.

The browser initially loads the web page at the URL 'http://www.lightoj.com/'

Input

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

Each case contains some commands. The keywords BACK, FORWARD, VISIT, and QUIT are all in uppercase. URLs have no whitespace and have at most 50 characters. The end of case is indicated by the QUIT command and it shouldn't be processed. Each case contains at most 100 lines.

Output

For each case, print the case number first. For each command, print the URL of the current page (in a line) after the command is executed if the command is not ignored. Otherwise, print'Ignored'.

Sample Input

Output for Sample Input

1VISIT http://uva.onlinejudge.org/VISIT http://topcoder.com/BACK

BACK

FORWARD

VISIT http://acm.sgu.ru/

BACK

FORWARD

QUIT

Case 1:http://uva.onlinejudge.org/http://topcoder.com/http://uva.onlinejudge.org/

http://www.lightoj.com/

Ignored

http://uva.onlinejudge.org/

http://acm.sgu.ru/

http://uva.onlinejudge.org/

http://www.lightoj.com/

http://uva.onlinejudge.org/

http://acm.sgu.ru/

Ignored

题目类型：简单栈模拟

算法分析：直接按照题目所说的方式进行栈模拟即可

#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--)
    {
        string cmd, cur = "http://www.lightoj.com/";
        stack <string> fs, bs;

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

        while (cin >> cmd)
        {
            bool is_valid = true;

            if (cmd == "QUIT")
                break;

            else if (cmd == "VISIT")
            {
                string temp;
                cin >> temp;
                bs.push (cur);
                cur = temp;

                while (!fs.empty ())
                    fs.pop ();
            }

            else if (cmd == "BACK")
            {
                if (!bs.empty ())
                {
                    fs.push (cur);
                    string temp = bs.top ();
                    bs.pop ();
                    cur = temp;
                }

                else
                    is_valid = false;
            }

            else if (cmd == "FORWARD")
            {
                if (!fs.empty ())
                {
                    bs.push (cur);
                    string temp = fs.top ();
                    fs.pop ();
                    cur = temp;
                }

                else
                    is_valid = false;
            }

            if (is_valid)
                cout << cur << endl;

            else
                cout << "Ignored" << endl;
        }
    }

return 0;
}

#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--)

{

string cmd, cur = "http://www.lightoj.com/";

stack <string> fs, bs;

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

while (cin >> cmd)

{

bool is_valid = true;

if (cmd == "QUIT")

break;

else if (cmd == "VISIT")

{

string temp;

cin >> temp;

bs.push (cur);

cur = temp;

while (!fs.empty ())

fs.pop ();

}

else if (cmd == "BACK")

{

if (!bs.empty ())

{

fs.push (cur);

string temp = bs.top ();

bs.pop ();

cur = temp;

}

else

is_valid = false;

}

else if (cmd == "FORWARD")

{

if (!fs.empty ())

{

bs.push (cur);

string temp = fs.top ();

fs.pop ();

cur = temp;

}

else

is_valid = false;

}

if (is_valid)

cout << cur << endl;

else

cout << "Ignored" << endl;

}

return 0;

}

返回首页上一页 1 2 3 4 5 下一页最后一页

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

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

Output

Sample Input

Output for Sample Input

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

Input

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

分类目录

标签云

书签

近期评论