lightoj1062

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

27 8月 2015

1062 - Crossed Ladders

InputA narrow street is lined with tall buildings. An x foot long ladder is rested at the base of the building on the right side of the street and leans on the building on the left side. A y foot long ladder is rested at the base of the building on the left side of the street and leans on the building on the right side. The point where the two ladders cross is exactly c feet from the ground. How wide is the street?

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

Each test case contains three positive floating point numbers giving the values of x, y, and c.

Output

For each case, output the case number and the width of the street in feet. Errors less than 10^-6 will be ignored.

Sample Input

Output for Sample Input

430 40 1012.619429 8.163332 310 10 3

10 10 1

Case 1: 26.0328775442Case 2: 6.99999923Case 3: 8Case 4: 9.797958971

题目类型：二分

算法分析：直接手算得出求c的公式，然后二分枚举胡同的宽度即可，注意二分枚举的开始区间为[0, min (a,b)]!!!!!!

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

double x, y, c;

bool BinSearch (double val)
{
    double k = sqrt (x * x - val * val), q = sqrt (y * y - val * val);

    double ans = (k * q) / (k + q);

    if (ans < c)
        return false;

return true;
}


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

    int t;

    cin >> t;

    int i;
    for (i = 1; i <= t; i++)
    {

        cin >> x >> y >> c;

        double L = 0, R = min (x, y), mid = 0;

        int cnt = 1;

        while (cnt <= 66)
        {
            mid = (L + R) / 2.0;

            if (BinSearch (mid))
                L = mid;

            else
                R = mid;

            cnt++;
        }

        cout << "Case " << i << ": " << fixed << setprecision (6) << L << 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;

double x, y, c;

bool BinSearch (double val)

{

double k = sqrt (x * x - val * val), q = sqrt (y * y - val * val);

double ans = (k * q) / (k + q);

if (ans < c)

return false;

return true;

}

int main()

{

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

int t;

cin >> t;

int i;

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

{

cin >> x >> y >> c;

double L = 0, R = min (x, y), mid = 0;

int cnt = 1;

while (cnt <= 66)

{

mid = (L + R) / 2.0;

if (BinSearch (mid))

L = mid;

else

R = mid;

cnt++;

}

cout << "Case " << i << ": " << fixed << setprecision (6) << L << endl;

}

return 0;

}

lightoj1056

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

27 8月 2015

1056 - Olympics

One of the most important tasks is to build the stadium. You are appointed as a programmer to help things out in certain matters - more specifically in designing and building the athletics tracks. After some study, you find out that athletics tracks have a general shape of a rectangle with two sliced circles on two ends. Now the turf that is placed inside this rectangle is prepared elsewhere and comes in different shapes - different length to width ratios. You know one thing for certain - your track should have a perimeter of 400 meters. That's the standard length for athletics tracks. You are supplied with the design parameter - length to width ratio. You are also told that the sliced circles will be such that they are part of the same circle. You have to find the length and width of the rectangle.The next Olympic is approaching very shortly. It's a hard job for the organizers. There are so many things to do - preparing the venues, building the Olympic village for accommodating athletes and officials, improving the transportation of the entire city as the venues are located all over the city and also there will be great number of tourists/spectators during the Olympics.

Input

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

Each case starts with the ratio of the length and width of the rectangle in the format: "a : b". Here, a and b will be integers and both will be between 1 and 1000 (inclusive).

Output

For each case, print the case number, the length and the width. Errors less than 10^-6 will be ignored.

Sample Input	Output for Sample Input
23 : 25 : 4	Case 1: 117.1858168 78.12387792Case 2: 107.29095604 85.8327648

题目类型：简单二分

算法分析：二分体育场的长，然后对于每一个长通过几何关系计算出体育场跑道的总周长。如果周长大于400，则向小的方向二分，反之，则向大的方向二分

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <iomanip>
using namespace std;

double len, wid;

bool BinSearch (double val)
{
	double ang = atan (wid / len);
	double R = val / 2 / cos (ang);
	double arc = 2 * 2 * ang * R;

	double temp = arc + val * 2;

	if (temp > 400)
		return false;

return true;
}


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

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

	while (cases--)
	{
		scanf ("%lf : %lf", &len, &wid);

		double left = 0, right = 800, mid;
		int i = 0, cnt = 66;
		
		while (i <= cnt)
		{
			mid = (left + right) / 2;

			if (BinSearch (mid))
				left = mid;

			else
				right = mid;

			i++;
		}

		cout << "Case " << flag++ << ": " << fixed << setprecision (6) << left << " "  
			<< fixed << setprecision (6) << left * wid / len << endl;
	}

return 0;
}

#include <iostream>

#include <fstream>

#include <cstdio>

#include <cmath>

#include <iomanip>

using namespace std;

double len, wid;

bool BinSearch (double val)

{

double ang = atan (wid / len);

double R = val / 2 / cos (ang);

double arc = 2 * 2 * ang * R;

double temp = arc + val * 2;

if (temp > 400)

return false;

return true;

}

int main()

{

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

int cases, flag = 1;

scanf ("%d", &cases);

while (cases--)

{

scanf ("%lf : %lf", &len, &wid);

double left = 0, right = 800, mid;

int i = 0, cnt = 66;

while (i <= cnt)

{

mid = (left + right) / 2;

if (BinSearch (mid))

left = mid;

else

right = mid;

i++;

}

cout << "Case " << flag++ << ": " << fixed << setprecision (6) << left << " "

<< fixed << setprecision (6) << left * wid / len << endl;

}

return 0;

}

lightoj1054

maksyuki 发表于 oj 分类，标签: 数值- 整数快速幂取模, 数论-乘法逆元, 数论-素因子分解

27 8月 2015

1054 - Efficient Pseudo Code

pseudo codeSometimes it's quite useful to write pseudo codes for problems. Actually you can write the necessary steps to solve a particular problem. In this problem you are given a pseudo code to solve a problem and you have to implement the pseudo code efficiently. Simple! Isn't it? 🙂

{

take two integers n and m

let p = n ^ m (n to the power m)

let sum = summation of all the divisors of p

let result = sum MODULO 1000,000,007

}

Now given n and m you have to find the desired result from the pseudo code. For example if n = 12 and m = 2. Then if we follow the pseudo code, we get

pseudo code

{

take two integers n and m

so, n = 12 and m = 2

let p = n ^ m (n to the power m)

so, p = 144

let sum = summation of all the divisors of p

so, sum = 403, since the divisors of p are 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72, 144

let result = sum MODULO 1000,000,007

so, result = 403

}

Input

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

Each test case will contain two integers, n (1 ≤ n) and m (0 ≤ m). Each of n and m will be fit into a 32 bit signed integer.

Output

For each case of input you have to print the case number and the result according to the pseudo code.

Sample Input	Output for Sample Input
312 212 136 2	Case 1: 403Case 2: 28Case 3: 3751

题目类型：素因子分解+逆元+整数快速幂取模

算法分析：首先使用Euler筛将素数预打表，然后从小到大判断每个素数在a中出现的指数值，然后带入约数和公式边模边求解，这里使用了一个求逆元非常好的公式：a / b mod (p) = a mod (mb) / m，由于指数比较大，所以要使用整数快速幂来加速运算，注意在判断条件primelist[i] * primelist[i] <= a时primelist[i]*primelist[i]相乘的结果应该强制转换成long long，否则会RE

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

const int maxn = 1000000 + 666;

bool prime[maxn];
int primelist[maxn], prime_len;

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

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

        int 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;
        }
    }
}

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

long long GetFactorSum (long long a, long long b, long long mod)
{
    long long ans = 1;

    for (long long i = 0; (long long ) primelist[i] * primelist[i] <= a; i++)
    {
//        printf ("%lld %lld\n", i, primelist[i]);

        if (a % primelist[i] == 0)
        {
            long long tempsum = 0;
            while (a % primelist[i] == 0)
            {
                tempsum++;
                a /= primelist[i];
            }

            long long m = (primelist[i] - 1) * mod;
            ans *= (pow_mod (primelist[i], tempsum * b + 1, m) + m - 1) / (primelist[i] - 1);
            ans %= mod;
        }
    }

    if (a > 1)
    {
        long long m = (a - 1) * mod;
        ans *= (pow_mod (a, b + 1, m) + m - 1) / (a - 1);
        ans %= mod;
    }

return ans;
}


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

    GetPrime ();

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

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

        long long a, b;
        scanf ("%lld%lld", &a, &b);
        printf ("%lld\n", GetFactorSum (a, b, MOD));
    }

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

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

const int maxn = 1000000 + 666;

bool prime[maxn];

int primelist[maxn], prime_len;

void GetPrime ()

{

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

prime_len = 0;

int i;

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

{

if (prime[i])

primelist[prime_len++] = i;

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

}

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;

}

long long GetFactorSum (long long a, long long b, long long mod)

{

long long ans = 1;

for (long long i = 0; (long long ) primelist[i] * primelist[i] <= a; i++)

{

// printf ("%lld %lld\n", i, primelist[i]);

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

{

long long tempsum = 0;

while (a % primelist[i] == 0)

{

tempsum++;

a /= primelist[i];

}

long long m = (primelist[i] - 1) * mod;

ans *= (pow_mod (primelist[i], tempsum * b + 1, m) + m - 1) / (primelist[i] - 1);

ans %= mod;

}

if (a > 1)

{

long long m = (a - 1) * mod;

ans *= (pow_mod (a, b + 1, m) + m - 1) / (a - 1);

ans %= mod;

}

return ans;

}

int main()

{

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

GetPrime ();

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

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

long long a, b;

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

printf ("%lld\n", GetFactorSum (a, b, MOD));

}

return 0;

}

lightoj1045

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

27 8月 2015

1045 - Digits of Factorial

f(0) = 1 f(n) = f(n - 1) * n, if(n > 0)Factorial of an integer is defined by the following function

So, factorial of 5 is 120. But in different bases, the factorial may be different. For example, factorial of 5 in base 8 is 170.

In this problem, you have to find the number of digit(s) of the factorial of an integer in a certain base.

Input

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

Each case begins with two integers n (0 ≤ n ≤ 10⁶) and base (2 ≤ base ≤ 1000). Both of these integers will be given in decimal.

Output

For each case of input you have to print the case number and the digit(s) of factorial n in the given base.

Sample Input

Output for Sample Input

55 108 1022 3

1000000 2

0 100

Case 1: 3Case 2: 5Case 3: 45Case 4: 18488885

Case 5: 1

题目类型：简单数学

算法分析：结果是log base n!，直接打表计算出ln i的值(前缀和)，然后对于每一个查询直接计算结果，注意使用cout输出格式可能会出现问题！输出结果要加上EPS！！！！！！

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

double val[maxn+66];

void Solve ()
{
    for (int i = 1; i <= maxn; i++)
        val[i] = val[i-1] + log (i);

}


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

    Solve ();

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

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

        printf ("%d\n", (int) (val[n] / log (base) + EPS) + 1);
    }

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

double val[maxn+66];

void Solve ()

{

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

val[i] = val[i-1] + log (i);

}

int main()

{

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

Solve ();

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

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

int n, base;

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

printf ("%d\n", (int) (val[n] / log (base) + EPS) + 1);

}

return 0;

}

lightoj1043

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

27 8月 2015

1043 - Triangle Partitioning

You are given AB, AC and BC. DE is parallel to BC. You are also given the area ratio between ADE and BDEC. You have to find the value of AD.See the picture below.

Input

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

Each case begins with four real numbers denoting AB, AC, BC and the ratio of ADE and BDEC (ADE / BDEC). You can safely assume that the given triangle is a valid triangle with positive area.

Output

For each case of input you have to print the case number and AD. Errors less than 10^-6 will be ignored.

Sample Input

Output for Sample Input

4100 100 100 210 12 14 17 8 9 10

8.134 9.098 7.123 5.10

Case 1: 81.6496580Case 2: 7.07106781Case 3: 6.6742381247Case 4: 7.437454786

题目类型：简单二分

算法分析：可以直接的手算出计算的公式计算AD长

#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;

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

	int cases, flag = 1;

	cin >> cases;

	double ab, ac, bc, rad;

	while (cases--)
	{
		cin >> ab >> ac >> bc >> rad;
		cout << "Case " << flag++ << ": " << fixed << setprecision (6) << ab * sqrt (rad / (rad + 1))
		<< endl;
	}

return 0;
}

#include <iostream>

#include <fstream>

#include <iomanip>

#include <cmath>

using namespace std;

int main()

{

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

int cases, flag = 1;

cin >> cases;

double ab, ac, bc, rad;

while (cases--)

{

cin >> ab >> ac >> bc >> rad;

cout << "Case " << flag++ << ": " << fixed << setprecision (6) << ab * sqrt (rad / (rad + 1))

<< endl;

}

return 0;

}

lightoj1042

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

27 8月 2015

1042 - Secret Origins

But we do know the story of the first time she set out to chart her own path in the time stream. Zephyr had just finished building her time machine which she named - "Dokhina Batash". She was making the final adjustments for her first trip when she noticed that a vital program was not working correctly. The program was supposed to take a number N, and find what Zephyr called its Onoroy value.This is the tale of Zephyr, the greatest time traveler the world will never know. Even those who are aware of Zephyr's existence know very little about her. For example, no one has any clue as to which time period she is originally from.

The Onoroy value of an integer N is the number of ones in its binary representation. For example, the number 13 (1101₂) has an Onoroy value of 3. Needless to say, this was an easy problem for the great mind of Zephyr. She solved it quickly, and was on her way.

You are now given a similar task. Find the first number after N which has the same Onoroy value as N.

Input

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

Each case begins with an integer N (1 ≤ N ≤ 10⁹).

Output

For each case of input you have to print the case number and the desired result.

Sample Input	Output for Sample Input
5231423239178	Case 1: 27Case 2: 14241Case 3: 395Case 4: 11Case 5: 16

题目类型：位运算

算法分析：如果直接枚举比n大的数并判断二进制中1的个数是否相同会TLE，此时使用的方法是将n的二进制表示存储到数组中，然后依次求长度为i的二进制位中的下一个排列，如果长度为i的二进制位存在下一个排列，则直接将该数转化为十进制输出即可。如果没有下一个合理的排列，则尝试下一个长度的二进制位的排列。由于尝试的二进制的排列的长度不超过2次，所以时间复杂度几乎为O(n)的，其中n为原十进制数的二进制表示的长度，而由已知可得n不超过32，所以不会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 ans[maxn], temp[maxn];

int Get (int val)
{
    int cnt = 0;
    do
    {
        ans[cnt++] = val % 2;
        val /= 2;
    } while (val);

    int i;
    for (i = 0; i < cnt / 2; i++)
    {
        int temp = ans[i];
        ans[i] = ans[cnt-1-i];
        ans[cnt-1-i] = temp;
    }

return cnt;
}

int Trans (int val)
{
    int i, sum = 0, wei = 1;
    for (i = val - 1; i >= 0; i--)
    {
        sum += wei * temp[i];
        wei *= 2;
    }

return sum;
}


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

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

    while (t--)
    {
        memset (ans, 0, sizeof (ans));
        memset (temp, 0, sizeof (temp));
        int n;
        cin >> n;

        int val_a, val_b;
        val_a = Get (n);

        int i;
        for (i = val_a; ; i++)
        {
            int j;
            for (j = 0; j < val_a; j++)
                temp[j] = ans[j];

            bool is_find = false;
            while (next_permutation (temp + 1, temp + i))
            {
                is_find = true;
                break;
            }

            if (is_find || i > val_a)
                break;
        }


        cout << "Case " << flag++ << ": " << Trans (i) << 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>

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 ans[maxn], temp[maxn];

int Get (int val)

{

int cnt = 0;

{

ans[cnt++] = val % 2;

val /= 2;

} while (val);

int i;

for (i = 0; i < cnt / 2; i++)

{

int temp = ans[i];

ans[i] = ans[cnt-1-i];

ans[cnt-1-i] = temp;

}

return cnt;

}

int Trans (int val)

{

int i, sum = 0, wei = 1;

for (i = val - 1; i >= 0; i--)

{

sum += wei * temp[i];

wei *= 2;

}

return sum;

}

int main()

{

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

int t, flag = 1;

cin >> t;

while (t--)

{

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

memset (temp, 0, sizeof (temp));

int n;

cin >> n;

int val_a, val_b;

val_a = Get (n);

int i;

for (i = val_a; ; i++)

{

int j;

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

temp[j] = ans[j];

bool is_find = false;

while (next_permutation (temp + 1, temp + i))

{

is_find = true;

break;

}

if (is_find || i > val_a)

break;

}

cout << "Case " << flag++ << ": " << Trans (i) << endl;

}

return 0;

}

lightoj1041

maksyuki 发表于 oj 分类，标签: 图论-最小生成树

27 8月 2015

1041 - Road Construction

You are given the description of roads. Damaged roads are formatted as "city₁ city₂ cost" and non-damaged roads are formatted as "city₁ city₂ 0". In this notation city₁ and city₂ are the case-sensitive names of the two cities directly connected by that road. If the road is damaged, cost represents the price of rebuilding that road. Every city in the country will appear at least once in roads. And there can be multiple roads between same pair of cities.There are several cities in the country, and some of them are connected by bidirectional roads. Unfortunately, some of the roads are damaged and cannot be used right now. Your goal is to rebuild enough of the damaged roads that there is a functional path between every pair of cities.

Your task is to find the minimum cost of the roads that must be rebuilt to achieve your goal. If it is impossible to do so, print "Impossible".

Input

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

Each case begins with a blank line and an integer m (1 ≤ m ≤ 50) denoting the number of roads. Then there will be m lines, each containing the description of a road. No names will contain more than 50 characters. The road costs will lie in the range [0, 1000].

Output

For each case of input you have to print the case number and the desired result.

Sample Input

Output for Sample Input

212Dhaka Sylhet 0

Ctg Dhaka 0

Sylhet Chandpur 9

Ctg Barisal 9

Ctg Rajshahi 9

Dhaka Sylhet 9

Ctg Rajshahi 3

Sylhet Chandpur 5

Khulna Rangpur 7

Chandpur Rangpur 7

Dhaka Rajshahi 6

Dhaka Rajshahi 7

Rajshahi Khulna 4

Kushtia Bhola 1

Case 1: 31Case 2: Impossible

题目类型：MST

算法分析：读入字符串然后将字符串转化为数字标识，然后调用kruskal算法直接计算即可

#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 maxn = 3600;

int parent[maxn];
struct Node
{
    int u, v, w;
};

Node edge[maxn];
int len;

vector <string> vec;

int UnFind (int val)
{
    if (parent[val] == val)
        return val;

return parent[val] = UnFind (parent[val]);
}

bool Cmp (Node a, Node b)
{
    return a.w < b.w;
}

int GetVal (string val)
{
    int i;
    for (i = 0; i < vec.size (); i++)
        if (val == vec[i])
            return i;

    vec.push_back (val);
return i;
}


void kruskal ()
{
    int i, sum = 0;

    for (i = 0; i < len; i++)
    {
        if (UnFind (edge[i].u) != UnFind(edge[i].v))
        {
            parent[UnFind(edge[i].u)] = UnFind (edge[i].v);
            sum += edge[i].w;
        }
    }

    int cnt = 0;
    for (i = 0; i < vec.size (); i++)
    {
        if (parent[i] == i)
        {
            cnt++;
            if (cnt > 1)
            {
                cout << "Impossible" << endl;
                return ;
            }
        }
    }

    cout << sum << endl;
}


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

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

    while (t--)
    {
        int m;
        string val_a, val_b;
        int val;

        cin >> m;
        int i;

        for (i = 0; i < maxn; i++)
            parent[i] = i;

        len = 0;
        vec.clear ();

        for (i = 0; i < m; i++)
        {
            cin >> val_a >> val_b >> val;

            int u = GetVal (val_a);
            int v = GetVal (val_b);
            if (val == 0)
            {
                parent[UnFind(u)] = UnFind (v);
            }

            else
            {
                edge[len].u = u;
                edge[len].v = v;
                edge[len++].w = val;
            }
        }

        sort (edge, edge + len, Cmp);

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

        kruskal ();

    }

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

#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 maxn = 3600;

int parent[maxn];

struct Node

{

int u, v, w;

};

Node edge[maxn];

int len;

vector <string> vec;

int UnFind (int val)

{

if (parent[val] == val)

return val;

return parent[val] = UnFind (parent[val]);

}

bool Cmp (Node a, Node b)

{

return a.w < b.w;

}

int GetVal (string val)

{

int i;

for (i = 0; i < vec.size (); i++)

if (val == vec[i])

return i;

vec.push_back (val);

return i;

}

void kruskal ()

{

int i, sum = 0;

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

{

if (UnFind (edge[i].u) != UnFind(edge[i].v))

{

parent[UnFind(edge[i].u)] = UnFind (edge[i].v);

sum += edge[i].w;

}

int cnt = 0;

for (i = 0; i < vec.size (); i++)

{

if (parent[i] == i)

{

cnt++;

if (cnt > 1)

{

cout << "Impossible" << endl;

return ;

}

cout << sum << endl;

}

int main()

{

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

int t, flag = 1;

cin >> t;

while (t--)

{

int m;

string val_a, val_b;

int val;

cin >> m;

int i;

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

parent[i] = i;

len = 0;

vec.clear ();

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

{

cin >> val_a >> val_b >> val;

int u = GetVal (val_a);

int v = GetVal (val_b);

if (val == 0)

{

parent[UnFind(u)] = UnFind (v);

}

else

{

edge[len].u = u;

edge[len].v = v;

edge[len++].w = val;

}

sort (edge, edge + len, Cmp);

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

kruskal ();

}

return 0;

}

lightoj1040

maksyuki 发表于 oj 分类，标签: 图论-最小生成树

27 8月 2015

1040 - Donation

You will be given the lengths (in meters) of cables between each pair of rooms in your house. You wish to keep only enough cable so that every pair of rooms in your house is connected by some chain of cables, of any length. The lengths are given in n lines, each having n integers, where n is the number of rooms in your house. The j^th integer of i^th line gives the length of the cable between rooms i and j in your house.A local charity is trying to gather donations of Ethernet cable. You realize that you probably have a lot of extra cable in your house, and make the decision that you will donate as much cable as you can spare.

If both the j^th integer of i^th line and the i^th integer of j^th line are greater than 0, this means that you have two cables connecting rooms i and j, and you can certainly donate at least one of them. If the i^th integer of i^th line is greater than 0, this indicates unused cable in room i, which you can donate without affecting your home network in any way. 0 means no cable.

You are not to rearrange any cables in your house; you are only to remove unnecessary ones. Return the maximum total length of cables (in meters) that you can donate. If any pair of rooms is not initially connected by some path, return -1.

Input

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

Each case begins with a blank line and an integer n (1 ≤ n ≤ 50) denoting the number of rooms in your house. Then there will be n lines, each having n space separated integers, denoting the lengths as described. Each length will be between 0 and 100.

Output

For each case of input you have to print the case number and desired result.

Sample Input

Output for Sample Input

3227 26

1 52

0 10 10 0

0 0 1 1

0 0 0 2

0 0 0 0

0 1 0 0

1 0 0 0

0 0 0 1

0 0 1 0

Case 1: 105Case 2: 12Case 3: -1

题目类型：MST

算法分析：使用kruskal算法计算最小生成树的权值和sum，然后直接使用总长度tot减去计算得到的sum，如果图不连通则直接输出-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 = 166;

struct Node
{
    int u, v, w;
};

Node edge[maxn*maxn];

int ans[maxn][maxn], len, parent[maxn], sum;
int n;
bool is_valid;

void Init ()
{
    int i;
    for (i = 0; i < maxn; i++)
        parent[i] = i;
}


int UnFind (int val)
{
    if (parent[val] == val)
        return val;

return parent[val] = UnFind (parent[val]);
}


void kruskal ()
{
    is_valid = true;
    int i, remain = n;
    sum = 0;
    for (i = 0; i < len && remain > 1; i++)
    {
        if (UnFind (edge[i].u) != UnFind (edge[i].v) && edge[i].w)
        {
            parent[UnFind(edge[i].u)] = UnFind (edge[i].v);
            remain--;
            sum += edge[i].w;
        }
    }

    if (remain > 1)
        is_valid = false;
}

bool Cmp (Node a, Node b)
{
    return a.w < b.w;
}


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

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

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

        cin >> n;

        int i, j, tot = 0;
        for (i = 0; i < n; i++)
            for (j = 0; j < n; j++)
            {
                cin >> ans[i][j];
                tot += ans[i][j];
            }

        len = 0;
        for (i = 0; i < n; i++)
        {
            for (j = 0; j < n; j++)
            {
                if (i == j)
                    continue;

                edge[len].u = i;
                edge[len].v = j;
                edge[len++].w = ans[i][j];
            }
        }

        sort (edge, edge + len, Cmp);
        kruskal ();

        if (is_valid)
            cout << tot - sum << endl;

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

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

struct Node

{

int u, v, w;

};

Node edge[maxn*maxn];

int ans[maxn][maxn], len, parent[maxn], sum;

int n;

bool is_valid;

void Init ()

{

int i;

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

parent[i] = i;

}

int UnFind (int val)

{

if (parent[val] == val)

return val;

return parent[val] = UnFind (parent[val]);

}

void kruskal ()

{

is_valid = true;

int i, remain = n;

sum = 0;

for (i = 0; i < len && remain > 1; i++)

{

if (UnFind (edge[i].u) != UnFind (edge[i].v) && edge[i].w)

{

parent[UnFind(edge[i].u)] = UnFind (edge[i].v);

remain--;

sum += edge[i].w;

}

if (remain > 1)

is_valid = false;

}

bool Cmp (Node a, Node b)

{

return a.w < b.w;

}

int main()

{

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

int t, flag = 1;

cin >> t;

while (t--)

{

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

Init ();

cin >> n;

int i, j, tot = 0;

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

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

{

cin >> ans[i][j];

tot += ans[i][j];

}

len = 0;

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

{

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

{

if (i == j)

continue;

edge[len].u = i;

edge[len].v = j;

edge[len++].w = ans[i][j];

}

sort (edge, edge + len, Cmp);

kruskal ();

if (is_valid)

cout << tot - sum << endl;

else

cout << "-1" << endl;

}

return 0;

}

lightoj1035

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

27 8月 2015

1035 - Intelligent Factorial Factorization

Input

Given an integer N, you have to prime factorize N! (factorial N).

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

Each case contains an integer N (2 ≤ N ≤ 100).

Output

For each case, print the case number and the factorization of the factorial in the following format as given in samples.

Case x: N = p₁ (power of p₁) * p₂ (power of p₂) * ...

Here x is the case number, p₁, p₂ ... are primes in ascending order.

Sample Input	Output for Sample Input
3236	Case 1: 2 = 2 (1)Case 2: 3 = 2 (1) * 3 (1)Case 3: 6 = 2 (4) * 3 (2) * 5 (1)

Notes

The output for the 3^rd case is (if we replace space with '.') is

Case.3:.6.=.2.(4).*.3.(2).*.5.(1)

题目类型：素因子分解

算法分析：N!中有素数p的个数为[N/p] + [N/p^2] + [N/p^3] + …由于N不太大，可以先将100以内的素数都打出来，然后从小到大判断每一个素数及其倍数是否满足 N / p ^ k != 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 = 100 + 66;

bool prime[maxn];

void GetPrime ()
{
    memset (prime, true, sizeof (prime));

    int i;
    for (i = 2; i < maxn; i++)
    {
        int j;
        for (j = 2; j * i < maxn; j++)
            prime[i*j] = false;
    }
}


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

    GetPrime ();

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

    while (t--)
    {
        int n;
        cin >> n;

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

        int i, sum;
        bool is_first = true;

        for (i = 2; i < maxn; i++)
        {
            if (prime[i])
            {
                if (n / i == 0)
                    break;

                sum = n / i;
                int temp = i;
                while (n / (temp * i))
                {
                    sum += n / (temp * i);
                    temp *= i;
                }

                if (is_first)
                {
                    is_first = false;
                    cout << i << " " << "(" << sum << ")";
                }

                else
                    cout << " * " << i << " " << "(" << sum << ")";
            }
        }

        cout << endl;
    }
    
return 0;
}

100

101

102

103

104

105

106

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

bool prime[maxn];

void GetPrime ()

{

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

int i;

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

{

int j;

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

prime[i*j] = false;

}

int main()

{

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

GetPrime ();

int t, flag = 1;

cin >> t;

while (t--)

{

int n;

cin >> n;

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

int i, sum;

bool is_first = true;

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

{

if (prime[i])

{

if (n / i == 0)

break;

sum = n / i;

int temp = i;

while (n / (temp * i))

{

sum += n / (temp * i);

temp *= i;

}

if (is_first)

{

is_first = false;

cout << i << " " << "(" << sum << ")";

}

else

cout << " * " << i << " " << "(" << sum << ")";

}

cout << endl;

}

return 0;

}

lightoj1029

maksyuki 发表于 oj 分类，标签: 图论-最小生成树

27 8月 2015

1029 - Civil and Evil Engineer

Since the Civil Engineer is clever enough and tries to make some profit, he made a plan. His plan is to find the best possible connection scheme and the worst possible connection scheme. Then he will report the average of the costs.A Civil Engineer is given a task to connect n houses with the main electric power station directly or indirectly. The Govt has given him permission to connect exactly n wires to connect all of them. Each of the wires connects either two houses, or a house and the power station. The costs for connecting each of the wires are given.

Now you are given the task to check whether the Civil Engineer is evil or not. That's why you want to calculate the average before he reports to the Govt.

Input

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

Each case contains a blank line and an integer n (1 ≤ n ≤ 100) denoting the number of houses. You can assume that the houses are numbered from 1 to n and the power station is numbered0. Each of the next lines will contain three integers in the form u v w (0 ≤ u, v ≤ n, 0 < w ≤ 10000, u ≠ v) meaning that you can connect u and v with a wire and the cost will be w. A line containing three zeroes denotes the end of the case. You may safely assume that the data is given such that it will always be possible to connect all of them. You may also assume that there will not be more than 12000 lines for a case.

Output

For each case, print the case number and the average as described. If the average is not an integer then print it in p/q form. Where p is the numerator of the result and q is the denominator of the result; p and q are relatively-prime. Otherwise print the integer average.

Sample Input

Output for Sample Input

310 1 10

0 1 20

0 0 0

0 1 99

0 2 10

1 2 30

2 3 30

0 0 0

0 1 10

0 2 5

0 0 0

Case 1: 15Case 2: 229/2Case 3: 15

题目类型：MST

算法分析：将边表edge按照边权从小到大和从大到小排两次并使用kruskal分别计算权值和，最后求两者之和并按照题目要求输出即可

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

struct Node
{
    int u, v, w;
};

Node edge[maxn];
int len, suma, sumb, parent[666];
int n;

void Init ()
{
    int i;
    for (i = 0; i < 666; i++)
        parent[i] = i;
}

int UnFind (int val)
{
    if (parent[val] == val)
        return val;

return parent[val] = UnFind (parent[val]);
}

void kruskal ()
{
    Init ();

    int i, remain = n;
    for (i = 0; i < len && remain > 1; i++)
    {
        if (UnFind (edge[i].u) != UnFind (edge[i].v))
        {
            parent[UnFind(edge[i].u)] = UnFind (edge[i].v);
            remain--;
            suma += edge[i].w;
        }
    }
}

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

return gcd (b, a % b);
}

bool Cmpa (Node a, Node b)
{
    return a.w < b.w;
}

bool Cmpb (Node a, Node b)
{
    return a.w > b.w;
}


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

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

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

        cin >> n;
        n++;

        len = 0;
        while (cin >> edge[len].u >> edge[len].v >> edge[len].w)
        {
            if (edge[len].u == 0 && edge[len].v == 0 && edge[len].w == 0)
                break;

            len++;
        }

        suma = 0;
        sort (edge, edge + len, Cmpa);
        kruskal ();

        sumb = suma;
        suma = 0;
        sort (edge, edge + len, Cmpb);
        kruskal ();

        int tot = suma + sumb;
        if (tot % 2 == 0)
            cout << tot / 2 << endl;

        else
        {
            int temp = gcd (max (tot, 2), min (tot, 2));
            cout << tot / temp << "/" << 2 / temp << 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

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

struct Node

{

int u, v, w;

};

Node edge[maxn];

int len, suma, sumb, parent[666];

int n;

void Init ()

{

int i;

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

parent[i] = i;

}

int UnFind (int val)

{

if (parent[val] == val)

return val;

return parent[val] = UnFind (parent[val]);

}

void kruskal ()

{

Init ();

int i, remain = n;

for (i = 0; i < len && remain > 1; i++)

{

if (UnFind (edge[i].u) != UnFind (edge[i].v))

{

parent[UnFind(edge[i].u)] = UnFind (edge[i].v);

remain--;

suma += edge[i].w;

}

int gcd (int a, int b)

{

if (b == 0)

return a;

return gcd (b, a % b);

}

bool Cmpa (Node a, Node b)

{

return a.w < b.w;

}

bool Cmpb (Node a, Node b)

{

return a.w > b.w;

}

int main()

{

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

int t, flag = 1;

cin >> t;

while (t--)

{

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

cin >> n;

n++;

len = 0;

while (cin >> edge[len].u >> edge[len].v >> edge[len].w)

{

if (edge[len].u == 0 && edge[len].v == 0 && edge[len].w == 0)

break;

len++;

}

suma = 0;

sort (edge, edge + len, Cmpa);

kruskal ();

sumb = suma;

suma = 0;

sort (edge, edge + len, Cmpb);

kruskal ();

int tot = suma + sumb;

if (tot % 2 == 0)

cout << tot / 2 << endl;

else

{

int temp = gcd (max (tot, 2), min (tot, 2));

cout << tot / temp << "/" << 2 / temp << endl;

}

return 0;

}

lightoj1020

maksyuki 发表于 oj 分类，标签: 博弈-Bash

27 8月 2015

1020 - A Childhood Game

Both Alice and Bob know the number of marbles initially. Now the game can be started by any one. But the winning condition depends on the player who starts it. If Alice starts first, then the player who takes the last marble looses the game. If Bob starts first, then the player who takes the last marble wins the game.Alice and Bob are playing a game with marbles; you may have played this game in childhood. The game is playing by alternating turns. In each turn a player can take exactly one or two marbles.

Now you are given the initial number of marbles and the name of the player who starts first. Then you have to find the winner of the game if both of them play optimally.

Input

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

Each case contains an integer n (1 ≤ n < 2³¹) and the name of the player who starts first.

Output

For each case, print the case number and the name of the winning player.

Sample Input	Output for Sample Input
31 Alice2 Alice3 Bob	Case 1: BobCase 2: AliceCase 3: Alice

题目类型：Bash博弈变形

算法分析：当Bob先手时，本题可以看做是Bash博弈问题，因为求解谁拿走最后一个石头和求解留给对方没法选石子的状态这两个问题是等价的。而当Alice先手时，由于谁拿走最后一个石子会输，所以初始时石子的个数%3 == 1的话，那个先手的人就会输，这可由Bash博弈推得

#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 main()
{
//    freopen ("aaa.txt", "r", stdin);

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

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

        int n;
        char s[16];

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

        if (!strcmp (s, "Alice"))
        {
            if (n % 3 == 1)
                printf ("Bob\n");

            else
                printf ("Alice\n");
        }

        else
        {
            if (n % 3 == 0)
                printf ("Alice\n");

            else
                printf ("Bob\n");
        }
    }

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

int main()

{

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

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

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

int n;

char s[16];

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

if (!strcmp (s, "Alice"))

{

if (n % 3 == 1)

printf ("Bob\n");

else

printf ("Alice\n");

}

else

{

if (n % 3 == 0)

printf ("Alice\n");

else

printf ("Bob\n");

}

return 0;

}

lightoj1019

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

27 8月 2015

1019 - Brush (V)

The city they live in is divided by some junctions. The junctions are connected by two way roads. They live in different junctions. And they can go to one junction to other by using the roads only.Tanvir returned home from the contest and got angry after seeing his room dusty. Who likes to see a dusty room after a brain storming programming contest? After checking a bit he found that there is no brush in him room. So, he called Atiq to get a brush. But as usual Atiq refused to come. So, Tanvir decided to go to Atiq's house.

Now you are given the map of the city and the distances of the roads. You have to find the minimum distance Tanvir has to travel to reach Atiq's house.

Input

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

Each case starts with a blank line. The next line contains two integers N (2 ≤ N ≤ 100) and M (0 ≤ M ≤ 1000), means that there are N junctions and M two way roads. Each of the next Mlines will contain three integers u v w (1 ≤ u, v ≤ N, w ≤ 1000), it means that there is a road between junction u and v and the distance is w. You can assume that Tanvir lives in the 1^stjunction and Atiq lives in the N^th junction. There can be multiple roads between same pair of junctions.

Output

For each case print the case number and the minimum distance Tanvir has to travel to reach Atiq's house. If it's impossible, then print 'Impossible'.

Sample Input

Output for Sample Input

23 21 2 50

2 3 10

3 1

1 2 40

Case 1: 60Case 2: Impossible

题目类型：单源最短路(Bellman-ford)

算法分析：直接使用Bellman-ford算法迭代求解即可，注意对于无向图来说要将无向图看作(u,v),(v,u)同属于边集E的有向图

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

struct Node
{
    int u, v, w;
};

Node edge[maxn*2];
int dis[maxn];
int n, m, len;


void bellman_ford (int s)
{
    int i;
    for (i = 1; i <= n; i++)
    {
        dis[i] = INF;
    }

    dis[s] = 0;

    for (i = 1; i < n; i++)
    {
        int j;
        for (j = 0; j < len; j++)
        {
            if (dis[edge[j].u] < INF)
            {
                dis[edge[j].v] = min (dis[edge[j].v], dis[edge[j].u] + edge[j].w);
            }
        }
    }
}

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

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

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

        cin >> n >> m;

        int i, temp_u, temp_v, temp_w;
        len = 0;

        for (i = 0; i < m; i++)
        {
            cin >> temp_u >> temp_v >> temp_w;
            edge[len].u = temp_u, edge[len].v = temp_v, edge[len].w = temp_w;
            len++;
            edge[len].u = temp_v, edge[len].v = temp_u, edge[len].w = temp_w;
            len++;
        }

        bellman_ford (1);

        if (dis[n] == INF)
            cout << "Impossible" << endl;

        else
            cout << dis[n] << endl;
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

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

struct Node

{

int u, v, w;

};

Node edge[maxn*2];

int dis[maxn];

int n, m, len;

void bellman_ford (int s)

{

int i;

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

{

dis[i] = INF;

}

dis[s] = 0;

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

{

int j;

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

{

if (dis[edge[j].u] < INF)

{

dis[edge[j].v] = min (dis[edge[j].v], dis[edge[j].u] + edge[j].w);

}

int main()

{

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

int t, flag = 1;

cin >> t;

while (t--)

{

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

cin >> n >> m;

int i, temp_u, temp_v, temp_w;

len = 0;

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

{

cin >> temp_u >> temp_v >> temp_w;

edge[len].u = temp_u, edge[len].v = temp_v, edge[len].w = temp_w;

len++;

edge[len].u = temp_v, edge[len].v = temp_u, edge[len].w = temp_w;

len++;

}

bellman_ford (1);

if (dis[n] == INF)

cout << "Impossible" << endl;

else

cout << dis[n] << endl;

}

return 0;

}

lightoj1016

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

27 8月 2015

1016 - Brush (II)

You can assume that the rope is sufficiently large. Now Samee wants to clean the room with minimum number of moves. Since he already had a contest, his head is messy. So, help him.After the long contest, Samee returned home and got angry after seeing his room dusty. Who likes to see a dusty room after a brain storming programming contest? After checking a bit he found a brush in his room which has width w. Dusts are defined as 2D points. And since they are scattered everywhere, Samee is a bit confused what to do. So, he attached a rope with the brush such that it can be moved horizontally (in X axis) with the help of the rope but in straight line. He places it anywhere and moves it. For example, the y co-ordinate of the bottom part of the brush is 2 and its width is 3, so the y coordinate of the upper side of the brush will be 5. And if the brush is moved, all dusts whose y co-ordinates are between 2 and 5 (inclusive) will be cleaned. After cleaning all the dusts in that part, Samee places the brush in another place and uses the same procedure. He defined a move as placing the brush in a place and cleaning all the dusts in the horizontal zone of the brush.

Input

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

Each case starts with a blank line. The next line contains two integers N (1 ≤ N ≤ 50000) and w (1 ≤ w ≤ 10000), means that there are N dust points. Each of the next N lines will contain two integers: x_i y_i, denoting coordinates of the dusts. You can assume that (-10⁹ ≤ x_i, y_i ≤ 10⁹) and all points are distinct.

Output

For each case print the case number and the minimum number of moves.

Sample Input

Output for Sample Input

23 20 0

20 2

30 2

3 1

0 0

20 2

30 2

Case 1: 1Case 2: 2

Note

Data set is huge, so 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 = 66666;

int ans[maxn];

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

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

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

        int n, w;
        scanf ("%d%d", &n, &w);

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

        sort (ans, ans + n);

        int sum = 1, p = ans[0];
        for (i = 1; i < n; i++)
        {
            if (ans[i] > w + p)
            {
                sum++;
                p = ans[i];
            }
        }

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

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 = 66666;

int ans[maxn];

int main()

{

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

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

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

int n, w;

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

int temp, i;

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

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

sort (ans, ans + n);

int sum = 1, p = ans[0];

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

{

if (ans[i] > w + p)

{

sum++;

p = ans[i];

}

printf ("%d\n", sum);

}

return 0;

}

lightoj1014

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

27 8月 2015

1014 - Ifter Party

Now you have to find the number of piaju's each contestant ate.I have an Ifter party at the 5^th day of Ramadan for the contestants. For this reason I have invited C contestants and arranged P piaju's (some kind of food, specially made for Ifter). Each contestant ate Q piaju's and L piaju's were left (L < Q).

Input

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

Each case contains two non-negative integers P and L (0 ≤ L < P < 2³¹).

Output

For each case, print the case number and the number of possible integers in ascending order. If no such integer is found print 'impossible'.

Sample Input	Output for Sample Input
410 013 2300 981000 997	Case 1: 1 2 5 10Case 2: 11Case 3: 101 202Case 4: impossible

题目类型：因子个数

算法分析：直接枚举小于sqrt(P - L)的所有因子，然后生成大于sqrt (P – L)的所有因子，注意枚举因子中的下标i必须使用long long类型，否则会RE

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

long long ans[maxn], len;


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

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

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

        long long P, L;
        scanf ("%lld%lld", &P, &L);

        long long val = P - L;

        if (val <= L)
        {
            puts (" impossible");
            continue ;
        }

        len = 0;
        for (long long i = 1; i * i <= val; i++)
        {
            if (val % i == 0)
            {
                if (i > L)
                    printf (" %lld", i);

                if (i * i == val)
                    continue;

                ans[len++] = i;
            }
        }

        for (long long i = len - 1; i >= 0; i--)
            if (val / ans[i] > L)
                printf (" %lld", val / ans[i]);


        puts ("");
    }

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

long long ans[maxn], len;

int main()

{

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

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

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

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

long long P, L;

scanf ("%lld%lld", &P, &L);

long long val = P - L;

if (val <= L)

{

puts (" impossible");

continue ;

}

len = 0;

for (long long i = 1; i * i <= val; i++)

{

if (val % i == 0)

{

if (i > L)

printf (" %lld", i);

if (i * i == val)

continue;

ans[len++] = i;

}

for (long long i = len - 1; i >= 0; i--)

if (val / ans[i] > L)

printf (" %lld", val / ans[i]);

puts ("");

}

return 0;

}

lightoj1012

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

27 8月 2015

1012 - Guilty Prince

For simplicity, you can consider the place as a rectangular grid consisting of some cells. A cell can be a land or can contain water. Each time the prince can move to a new cell from his current position if they share a side.Once there was a king named Akbar. He had a son named Shahjahan. For an unforgivable reason the king wanted him to leave the kingdom. Since he loved his son he decided his son would be banished in a new place. The prince became sad, but he followed his father's will. In the way he found that the place was a combination of land and water. Since he didn't know how to swim, he was only able to move on the land. He didn't know how many places might be his destination. So, he asked your help.

Now write a program to find the number of cells (unit land) he could reach including the cell he was living.

Input

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

Each case starts with a line containing two positive integers W and H; W and H are the numbers of cells in the x and y directions, respectively. W and H are not more than 20.

There will be H more lines in the data set, each of which includes W characters. Each character represents the status of a cell as follows.

1) '.' - land

2) '#' - water

3) '@' - initial position of prince (appears exactly once in a dataset)

Output

For each case, print the case number and the number of cells he can reach from the initial position (including it).

Sample Input

Output for Sample Input

46 9....#......#

......

#@...#

.#..#.

11 9

.#.........

.#.#######.

.#.#.....#.

.#.#.###.#.

.#.#..@#.#.

.#.#####.#.

.#.......#.

.#########.

...........

11 6

..#..#..#..

..#..#..###

..#..#..#@.

..#..#..#..

7 7

..#.#..

###.###

...@...

###.###

..#.#..

Case 1: 45Case 2: 59Case 3: 6Case 4: 13

题目类型：DFS/BFS

算法分析：调用DFS/BFS计算连通的’.’数量即可

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

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

char ans[maxn][maxn];
bool visited[maxn][maxn];

int sum, row, col, flag = 1, s_x, s_y;

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


void DFS (int x, int y)
{
    int i;
    for (i = 0; i < 4; i++)
    {
        if (OkMove (x + dx[i], y + dy[i]))
        {
            int val_x = x + dx[i], val_y = y + dy[i];

            visited[val_x][val_y] = true;
            sum++;
            DFS (val_x, val_y);
        }
    }
}
int main()
{
//    ifstream cin ("aaa.txt");

    int t;
    cin >> t;

    while (t--)
    {
        cin >> col >> row;

        int i, j;
        for (i = 0; i < row; i++)
        {
            for (j = 0; j < col; j++)
            {
                cin >> ans[i][j];

                if (ans[i][j] == '@')
                {
                    s_x = i;
                    s_y = j;
                }
            }
        }

        memset (visited, false, sizeof (visited));
        sum = 1;

        visited[s_x][s_y] = true;

        DFS (s_x, s_y);

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

const int maxn = 66 + 6;

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

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

char ans[maxn][maxn];

bool visited[maxn][maxn];

int sum, row, col, flag = 1, s_x, s_y;

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;

}

void DFS (int x, int y)

{

int i;

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

{

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

{

int val_x = x + dx[i], val_y = y + dy[i];

visited[val_x][val_y] = true;

sum++;

DFS (val_x, val_y);

}

int main()

{

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

int t;

cin >> t;

while (t--)

{

cin >> col >> row;

int i, j;

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

{

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

{

cin >> ans[i][j];

if (ans[i][j] == '@')

{

s_x = i;

s_y = j;

}

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

sum = 1;

visited[s_x][s_y] = true;

DFS (s_x, s_y);

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

}

return 0;

}

lightoj1010

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

27 8月 2015

1010 - Knights in Chessboard

Those who are not familiar with chess knights, note that a chess knight can attack 8 positions in the board as shown in the picture below.Given an m x n chessboard where you want to place chess knights. You have to find the number of maximum knights that can be placed in the chessboard such that no two knights attack each other.

Input

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

Each case contains two integers m, n (1 ≤ m, n ≤ 200). Here m and n corresponds to the number of rows and the number of columns of the board respectively.

Output

For each case, print the case number and maximum number of knights that can be placed in the board considering the above restrictions.

Sample Input	Output for Sample Input
38 83 74 10	Case 1: 32Case 2: 11Case 3: 20

题目类型：找规律

算法分析：维持row <= col，然后当row == 1时，直接输出col。当row == 2时，那么可以一次性把一个田字格全部放上马，然后间隔一个田字格，然后再放马。当row >= 3时，则直接判断棋盘上黑白格最大的那一个的个数即可(因为同一个颜色的格子中的马不会相互攻击)

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

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

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

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

        if (row > col)
            swap (row, col);

        if (row == 1)
        {
            printf ("%d\n", col);
        }

        else if (row == 2)
        {
            int sum = 4 * (col / 4);
            int temp = col % 4;
            if (temp < 3)
                sum += temp * 2;

            else
                sum += 4;

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

        else
        {
            int tot = row * col;
            if (tot % 2)
                printf ("%d\n", tot / 2 + 1);

            else
                printf ("%d\n", tot / 2);
        }
    }

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 = 66666;

int main()

{

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

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

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

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

int row, col;

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

if (row > col)

swap (row, col);

if (row == 1)

{

printf ("%d\n", col);

}

else if (row == 2)

{

int sum = 4 * (col / 4);

int temp = col % 4;

if (temp < 3)

sum += temp * 2;

else

sum += 4;

printf ("%d\n", sum);

}

else

{

int tot = row * col;

if (tot % 2)

printf ("%d\n", tot / 2 + 1);

else

printf ("%d\n", tot / 2);

}

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

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

Input

Output

Sample Input

Output for Sample Input

Input

Output

Sample Input

Output for Sample Input

Notes

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

分类目录

标签云

书签

近期评论