lightoj1112

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

27 8月 2015

1112 - Curious Robin Hood

Now each time he can he can do one of the three tasks.Robin Hood likes to loot rich people since he helps the poor people with this money. Instead of keeping all the money together he does another trick. He keeps n sacks where he keeps this money. The sacks are numbered from 0 to n-1.

1) Give all the money of the i^th sack to the poor, leaving the sack empty.

2) Add new amount (given in input) in the i^th sack.

3) Find the total amount of money from i^th sack to j^th sack.

Since he is not a programmer, he seeks your help.

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). The next line contains n space separated integers in the range [0, 1000]. The i^th integer denotes the initial amount of money in the i^th sack (0 ≤ i < n).

Each of the next q lines contains a task in one of the following form:

1 i Give all the money of the i^th (0 ≤ i < n) sack to the poor.

2 i v Add money v (1 ≤ v ≤ 1000) to the i^th (0 ≤ i < n) sack.

3 i j Find the total amount of money from i^th sack to j^th sack (0 ≤ i ≤ j < n).

Output

For each test case, print the case number first. If the query type is 1, then print the amount of money given to the poor. If the query type is 3, print the total amount from i^th to j^th sack.

Sample Input

Output for Sample Input

15 63 2 1 4 51 4

2 3 4

3 0 3

1 2

3 0 4

1 1

Case 1:5141

Notes

Dataset is huge, use faster I/O methods.

题目类型：线段树

算法分析：线段树简单的单点更新和区间求和问题，直接建树，更新和查询即可

#include <iostream>
#include <fstream>
#include <sstream>
#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>

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

using namespace std;

const int INF = 0x7FFFFFFF;
const int maxn = 100000 +66;

int sum[maxn<<2];
int giveval;

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


void Build (int rt, int l, int r)
{
    if (l == r)
    {
        scanf ("%d", &sum[rt]);

        return;
    }

    int m = (l + r) >> 1;
    Build (lson);
    Build (rson);
    PushUp (rt);
}

void UpDate (int rt, int l, int r, int val, int num)
{
    if (l == r)
    {
        sum[rt] += num;
        return ;
    }

    int m = (l + r) >> 1;
    if (val <= m)
        UpDate (lson, val, num);

    else
        UpDate (rson, val, num);

    PushUp (rt);
}

void Give (int rt, int l, int r, int val)
{
    if (l == r)
    {
        giveval = sum[rt];
        sum[rt] = 0;
        return ;
    }

    int m = (l + r) >> 1;
    if (val <= m)
        Give (lson, val);

    else
        Give (rson, val);

    PushUp (rt);
}


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

    int m = (l + r) >> 1;
    int 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++);


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

      Build (1, 1, n);

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

            if (oper == 1)
            {
                scanf ("%d", &val_a);
                val_a++;
                Give (1, 1, n, val_a);
                printf ("%d\n", giveval);
            }

            else if (oper == 2)
            {
                scanf ("%d%d", &val_a, &val_b);
                val_a++;
                UpDate (1, 1, n, val_a, val_b);
            }

            else if (oper == 3)
            {
                scanf ("%d%d", &val_a, &val_b);
                val_a++, val_b++;
                printf ("%d\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

#include <iostream>

#include <fstream>

#include <sstream>

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

#define lson rt << 1, l, m

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

using namespace std;

const int INF = 0x7FFFFFFF;

const int maxn = 100000 +66;

int sum[maxn<<2];

int giveval;

void PushUp (int rt)

{

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

}

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

{

if (l == r)

{

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

return;

}

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

Build (lson);

Build (rson);

PushUp (rt);

}

void UpDate (int rt, int l, int r, int val, int num)

{

if (l == r)

{

sum[rt] += num;

return ;

}

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

if (val <= m)

UpDate (lson, val, num);

else

UpDate (rson, val, num);

PushUp (rt);

}

void Give (int rt, int l, int r, int val)

{

if (l == r)

{

giveval = sum[rt];

sum[rt] = 0;

return ;

}

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

if (val <= m)

Give (lson, val);

else

Give (rson, val);

PushUp (rt);

}

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

{

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

return sum[rt];

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

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

int n, q;

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

Build (1, 1, n);

int i, oper, val_a, val_b;

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

{

scanf ("%d", &oper);

if (oper == 1)

{

scanf ("%d", &val_a);

val_a++;

Give (1, 1, n, val_a);

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

}

else if (oper == 2)

{

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

val_a++;

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

}

else if (oper == 3)

{

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

val_a++, val_b++;

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

}

return 0;

}

lightoj1088

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

27 8月 2015

1088 - Points in Segments

For example if the points are 1, 4, 6, 8, 10. And the segment is 0 to 5. Then there are 2 points that lie in the segment.Given n points (1 dimensional) and q segments, you have to find the number of points that lie in each of the segments. A point p_i will lie in a segment A B if A ≤ p_i ≤ B.

Input

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

Each case starts with a line containing two integers n (1 ≤ n ≤ 10⁵) and q (1 ≤ q ≤ 50000). The next line contains n space separated integers denoting the points in ascending order. All the integers are distinct and each of them range in [0, 10⁸].

Each of the next q lines contains two integers A_k B_k (0 ≤ A_k ≤ B_k ≤ 10⁸) denoting a segment.

Output

For each case, print the case number in a single line. Then for each segment, print the number of points that lie in that segment.

Sample Input

Output for Sample Input

15 31 4 6 8 100 5

6 10

7 100000

Case 1:232

Note

Dataset is huge, use faster I/O methods.

题目类型：二分法

算法分析：读入数据，然后二分求得所求区间的上下界在输入序列中的下标pos_low和pos_high，最后直接pos_high – pos_low即可

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

int ans[maxn];

int n, q;

int Calc_low (int val)
{
    int low = 0, high = n - 1, mid;

    while (low <= high)
    {
        mid = low + (high - low) / 2;
        if (val <= ans[mid])
            high = mid - 1;

        else
            low = mid + 1;
    }

return low;
}

int Calc_high (int val)
{
    int low = 0, high = n - 1, mid;

    while (low <= high)
    {
        mid = low + (high - low) / 2;
        if (val >= ans[mid])
            low = mid + 1;

        else
            high = mid - 1;
    }

return low;
}

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

    int t, flag = 1;

    scanf ("%d", &t);

    while (t--)
    {


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

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

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

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

            int pos_low = Calc_low (val_low);
            int pos_high = Calc_high (val_high);

            printf ("%d\n", pos_high - pos_low);
        }
    }

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

int ans[maxn];

int n, q;

int Calc_low (int val)

{

int low = 0, high = n - 1, mid;

while (low <= high)

{

mid = low + (high - low) / 2;

if (val <= ans[mid])

high = mid - 1;

else

low = mid + 1;

}

return low;

}

int Calc_high (int val)

{

int low = 0, high = n - 1, mid;

while (low <= high)

{

mid = low + (high - low) / 2;

if (val >= ans[mid])

low = mid + 1;

else

high = mid - 1;

}

return low;

}

int main()

{

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

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

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

int i;

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

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

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

int val_low, val_high;

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

{

scanf ("%d%d", &val_low, &val_high);

int pos_low = Calc_low (val_low);

int pos_high = Calc_high (val_high);

printf ("%d\n", pos_high - pos_low);

}

return 0;

}

lightoj1083

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

27 8月 2015

1083 - Histogram

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3 measured in units where the width of the rectangles is 1.

Input

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

Each case contains a line with an integer N (1 ≤ N ≤ 30000) denoting the number of rectangles. The next line contains N space separated positive integers (≤ 30000) denoting the heights.

Output

For each case, print the case number and the largest rectangle that can be made.

Sample Input	Output for Sample Input
272 1 4 5 1 3 354 4 3 2 4	Case 1: 8Case 2: 10

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

struct Node
{
    int w, h;
    Node (int ww, int hh) : w (ww), h (hh) {}
    Node () {}
};


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

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

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

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

        deque <Node> deq;

        int hei, maxval = -INF, temp_w;

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

            temp_w = 0;
            Node val;
            while (!deq.empty () && deq.back ().h >= hei)
            {
                val = deq.back ();
                deq.pop_back ();
                maxval = max (maxval, val.h * (val.w + temp_w));
                temp_w += val.w;
            }

                deq.push_back (Node (temp_w + 1, hei));
        }

        temp_w = 0;
        while (!deq.empty ())
        {
            Node val = deq.back ();
            deq.pop_back ();
            maxval = max (maxval, val.h * (temp_w + val.w));
            temp_w += val.w;
        }

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

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

struct Node

{

int w, h;

Node (int ww, int hh) : w (ww), h (hh) {}

Node () {}

};

int main()

{

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

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

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

int n;

scanf ("%d", &n);

deque <Node> deq;

int hei, maxval = -INF, temp_w;

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

{

scanf ("%d", &hei);

temp_w = 0;

Node val;

while (!deq.empty () && deq.back ().h >= hei)

{

val = deq.back ();

deq.pop_back ();

maxval = max (maxval, val.h * (val.w + temp_w));

temp_w += val.w;

}

deq.push_back (Node (temp_w + 1, hei));

}

temp_w = 0;

while (!deq.empty ())

{

Node val = deq.back ();

deq.pop_back ();

maxval = max (maxval, val.h * (temp_w + val.w));

temp_w += val.w;

}

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

}

return 0;

}

lightoj1080

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

27 8月 2015

1080 - Binary Simulation

'I i j' which means invert the bit from i to j (inclusive)Given a binary number, we are about to do some operations on the number. Two types of operations can be here.

'Q i' answer whether the i^th bit is 0 or 1

The MSB (most significant bit) is the first bit (i.e. i=1). The binary number can contain leading zeroes.

Input

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

Each case starts with a line containing a binary integer having length n (1 ≤ n ≤ 10⁵). The next line will contain an integer q (1 ≤ q ≤ 50000) denoting the number of queries. Each query will be either in the form 'I i j' where i, j are integers and 1 ≤ i ≤ j ≤ n. Or the query will be in the form 'Q i' where i is an integer and 1 ≤ i ≤ n.

Output

For each case, print the case number in a single line. Then for each query 'Q i' you have to print 1 or 0 depending on the i^th bit.

Sample Input

Output for Sample Input

200110011006I 1 10

I 2 7

Q 2

Q 1

Q 7

Q 5

1011110111

I 1 10

I 2 7

Q 2

Q 1

Q 7

Q 5

Case 1:011

Case 2:

Note

Dataset is huge, use faster i/o methods.

题目类型：线段树

算法分析：需要使用lazy标记来进行区间修改，lazy布尔数组当为false时表示当前区间没有翻转，而true表示当前区间元素需要翻转。由于本题要进行单点查询，所以可以在查询到叶子节点后再判断lazy，且不需要PushUp

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

bool lazy[maxn<<2];
char sum[maxn];

void PushDown (int rt)
{
    if (lazy[rt])
    {
        lazy[rt<<1] = !lazy[rt<<1];
        lazy[rt<<1|1] = !lazy[rt<<1|1];
        lazy[rt] = !lazy[rt];
    }
}


void UpDate (int rt, int l, int r, int L, int R)
{
    if (L <= l && r <= R)
    {
        lazy[rt] = !lazy[rt];
        return ;
    }

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

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

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

}

int Query (int rt, int l, int r, int val)
{
   if (l == r)
   {
       if (lazy[rt])
       {
           sum[val] = !(sum[val] - '0') + '0';
           lazy[rt] = !lazy[rt];
       }

       return sum[val] - '0';
   }

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

   if (val <= m)
        return Query (lson, val);

   else
        return Query (rson, val);
}


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

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

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

        memset (lazy, false, sizeof (lazy));
        scanf ("%s", sum + 1);

        int q, len = strlen (sum + 1);

        scanf ("%d", &q);

        int i;
        char cmd[6];
        for (i = 0; i < q; i++)
        {
            scanf ("%s", cmd);
            if (cmd[0] == 'I')
            {
                int val_a, val_b;
                scanf ("%d%d", &val_a, &val_b);
                UpDate (1, 1, len, val_a, val_b);
            }

            else
            {
                int val;
                scanf ("%d", &val);
                printf ("%d\n", Query (1, 1, len, val));
            }
        }
    }

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

#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 int MOD = 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 100000 + 66;

bool lazy[maxn<<2];

char sum[maxn];

void PushDown (int rt)

{

if (lazy[rt])

{

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

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

lazy[rt] = !lazy[rt];

}

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

{

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

{

lazy[rt] = !lazy[rt];

return ;

}

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

PushDown (rt);

if (L <= m)

UpDate (lson, L, R);

if (R > m)

UpDate (rson, L, R);

}

int Query (int rt, int l, int r, int val)

{

if (l == r)

{

if (lazy[rt])

{

sum[val] = !(sum[val] - '0') + '0';

lazy[rt] = !lazy[rt];

}

return sum[val] - '0';

}

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

PushDown (rt);

if (val <= m)

return Query (lson, val);

else

return Query (rson, val);

}

int main()

{

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

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

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

memset (lazy, false, sizeof (lazy));

scanf ("%s", sum + 1);

int q, len = strlen (sum + 1);

scanf ("%d", &q);

int i;

char cmd[6];

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

{

scanf ("%s", cmd);

if (cmd[0] == 'I')

{

int val_a, val_b;

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

UpDate (1, 1, len, val_a, val_b);

}

else

{

int val;

scanf ("%d", &val);

printf ("%d\n", Query (1, 1, len, val));

}

return 0;

}

lightoj1078

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

27 8月 2015

1078 - Integer Divisibility

For example you have to find a multiple of 3 which contains only 1's. Then the result is 3 because is 111 (3-digit) divisible by 3. Similarly if you are finding some multiple of 7 which contains only 3's then, the result is 6, because 333333 is divisible by 7.If an integer is not divisible by 2 or 5, some multiple of that number in decimal notation is a sequence of only a digit. Now you are given the number and the only allowable digit, you should report the number of digits of such multiple.

Input

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

Each case will contain two integers n (0 < n ≤ 10⁶ and n will not be divisible by 2 or 5) and the allowable digit (1 ≤ digit ≤ 9).

Output

For each case, print the case number and the number of digits of such multiple. If several solutions are there; report the minimum one.

Sample Input	Output for Sample Input
33 17 39901 1	Case 1: 3Case 2: 6Case 3: 12

题目类型：简单数学

算法分析：直接迭代计算temp = (10 * temp + k) % n直到temp == 0为止，输出迭代的次数即可，因为666 = 66 * 10 + 6，则有666 % n = (66 % n * 10 + 6 % n) % n

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

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

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

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

        int n, k;
        cin >> n >> k;

        int sum = 1;
        long long temp = k % n;

        while (temp)
        {
            temp = (10 * temp + k) % n;
            sum++;
        }

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

int main()

{

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

int t, flag = 1;

cin >> t;

while (t--)

{

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

int n, k;

cin >> n >> k;

int sum = 1;

long long temp = k % n;

while (temp)

{

temp = (10 * temp + k) % n;

sum++;

}

cout << sum << endl;

}

return 0;

}

lightoj1074

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

27 8月 2015

1074 - Extended Traffic

InputDhaka city is getting crowded and noisy day by day. Certain roads always remain blocked in congestion. In order to convince people avoid shortest routes, and hence the crowded roads, to reach destination, the city authority has made a new plan. Each junction of the city is marked with a positive integer (≤ 20) denoting the busyness of the junction. Whenever someone goes from one junction (the source junction) to another (the destination junction), the city authority gets the amount (busyness of destination - busyness of source)³ (that means the cube of the difference) from the traveler. The authority has appointed you to find out the minimum total amount that can be earned when someone intelligent goes from a certain junction (the zero point) to several others.

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

Each case contains a blank line and an integer n (1 < n ≤ 200) denoting the number of junctions. The next line contains n integers denoting the busyness of the junctions from 1 to nrespectively. The next line contains an integer m, the number of roads in the city. Each of the next m lines (one for each road) contains two junction-numbers (source, destination) that the corresponding road connects (all roads are unidirectional). The next line contains the integer q, the number of queries. The next q lines each contain a destination junction-number. There can be at most one direct road from a junction to another junction.

Output

For each case, print the case number in a single line. Then print q lines, one for each query, each containing the minimum total earning when one travels from junction 1 (the zero point) to the given junction. However, for the queries that gives total earning less than 3, or if the destination is not reachable from the zero point, then print a '?'.

Sample Input

Output for Sample Input

256 7 8 9 106

1 2

2 3

3 4

1 5

5 4

4 5

10 10

1 2

Case 1:34Case 2:?

题目类型：单源最短路径(SPFA)

算法分析：SPFA算法的直接应用，注意判断输出’?’的条件是不可达、最短路径长度小于3或者是不存在负权值回路，注意一定要判断是否存在负权值回路，否则程序会TLE！！！！！！

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

const int INF = 0x7FFFFFFF;
const int maxn = 366 + 66;

int dis[maxn], ans[maxn], cnt[maxn];
bool inq[maxn];
int n;

struct Node
{
    int v, w;
    Node (int vv, int ww) : v (vv), w (ww) {}
    Node () {}
};

vector <Node> edge[maxn];

inline int power (int val)
{
    return val * val * val;
}

void spfa ()
{
    memset (inq, false, sizeof (inq));
    memset (cnt, 0, sizeof (cnt));

    int i;
    for (i = 1; i <= n; i++)
        dis[i] = INF;

    dis[1] = 0;
    queue <int> qu;

    qu.push (1);
    inq[1] = true;
    cnt[1]++;

    while (!qu.empty ())
    {
        int temp = qu.front ();
        qu.pop ();
        inq[temp] = false;

        if (cnt[temp] >= n)
            break;

        for (i = 0; i < edge[temp].size (); i++)
        {
            if (dis[temp] + edge[temp][i].w < dis[edge[temp][i].v])
            {
                dis[edge[temp][i].v] = dis[temp] + edge[temp][i].w;
                if (!inq[edge[temp][i].v])
                {
                    inq[edge[temp][i].v] = true;
                    qu.push (edge[temp][i].v);
                    cnt[edge[temp][i].v]++;
                }
            }
        }
    }
}


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

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

    while (t--)
    {

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

        int m, val_a, val_b;
        for (i = 1; i <= n; i++)
        {
            edge[i].clear ();
        }


        cin >> m;
        for (i = 0; i < m; i++)
        {
            scanf ("%d%d", &val_a, &val_b);
            edge[val_a].push_back (Node (val_b, power (ans[val_b] - ans[val_a])));
        }

        spfa ();

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

        int q, temp;
        scanf ("%d", &q);
        for (i = 0; i < q; i++)
        {
            scanf ("%d", &temp);
            if (dis[temp] < 3 || dis[temp] == INF || cnt[temp] >= n)
                printf ("?\n");

            else
                printf ("%d\n", dis[temp]);
        }
    }

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

#include <iostream>

#include <fstream>

#include <sstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

const int INF = 0x7FFFFFFF;

const int maxn = 366 + 66;

int dis[maxn], ans[maxn], cnt[maxn];

bool inq[maxn];

int n;

struct Node

{

int v, w;

Node (int vv, int ww) : v (vv), w (ww) {}

Node () {}

};

vector <Node> edge[maxn];

inline int power (int val)

{

return val * val * val;

}

void spfa ()

{

memset (inq, false, sizeof (inq));

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

int i;

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

dis[i] = INF;

dis[1] = 0;

queue <int> qu;

qu.push (1);

inq[1] = true;

cnt[1]++;

while (!qu.empty ())

{

int temp = qu.front ();

qu.pop ();

inq[temp] = false;

if (cnt[temp] >= n)

break;

for (i = 0; i < edge[temp].size (); i++)

{

if (dis[temp] + edge[temp][i].w < dis[edge[temp][i].v])

{

dis[edge[temp][i].v] = dis[temp] + edge[temp][i].w;

if (!inq[edge[temp][i].v])

{

inq[edge[temp][i].v] = true;

qu.push (edge[temp][i].v);

cnt[edge[temp][i].v]++;

}

int main()

{

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

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

scanf ("%d", &n);

int i;

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

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

int m, val_a, val_b;

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

{

edge[i].clear ();

}

cin >> m;

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

{

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

edge[val_a].push_back (Node (val_b, power (ans[val_b] - ans[val_a])));

}

spfa ();

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

int q, temp;

scanf ("%d", &q);

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

{

scanf ("%d", &temp);

if (dis[temp] < 3 || dis[temp] == INF || cnt[temp] >= n)

printf ("?\n");

else

printf ("%d\n", dis[temp]);

}

return 0;

}

lightoj1070

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

27 8月 2015

1070 - Algebraic Problem

InputGiven the value of a+b and ab you will have to find the value of aⁿ+bⁿ. a and b not necessarily have to be real numbers.

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

Each case contains three non-negative integers, p, q and n. Here p denotes the value of a+b and q denotes the value of ab. Each number in the input file fits in a signed 32-bit integer. There will be no such input so that you have to find the value of 0⁰.

Output

For each test case, print the case number and (aⁿ+bⁿ) modulo 2⁶⁴.

Sample Input	Output for Sample Input
210 16 27 12 3	Case 1: 68Case 2: 91

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

算法分析：首先推出递推公式：Sn = p*Sn-1 - q * Sn-2，然后使用矩阵快速幂取模求解。注意要使用unsigned long long 来定义变量，输入、输出！！！！！！

#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 unsigned long long MOD = 18446744073709551615uLL;
//18446744073709551615
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 2;

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

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


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

            for (unsigned 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;
                c.mat[i][j] = (c.mat[i][j] + (a.mat[i][k] * b.mat[k][j]) % MOD) % MOD;
            }
        }
    }
return c;
}

//重载Mat乘幂运算
Mat operator ^ (Mat a, unsigned long long k)
{
    Mat c;
    for (unsigned long long i = 0; i < n; i++)
        for(unsigned 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);

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

	while (t--)
	{
		unsigned long long p, q, n;
		scanf ("%llu%llu%llu", &p, &q, &n);
        printf ("Case %d: ", flag++);

		if (n == 0)
			puts ("2");

		else if (n == 1)
            printf ("%llu\n", p % MOD);
            //cout << p % MOD << endl;

		else if (n == 2)
			printf ("%llu\n", (p * p - 2 * q) % MOD);
			//cout << (p * p - 2 * q) % MOD << endl;

		else
		{
			aa.mat[0][0] = p, aa.mat[0][1] = -q;
			aa.mat[1][0] = 1, aa.mat[1][1] = 0;
			Mat bb = aa ^ (n - 2), cc;

//			cout << aa.mat[0][0] << " " << aa.mat[0][1] << endl;

//			cout << aa.mat[1][0] << " " << aa.mat[1][1] << endl;

			cc.mat[0][0] = (p * p - 2 * q) % MOD;
			cc.mat[1][0] = p % MOD;

            bb = bb * cc;
            //printf ("%ulld\n", (bb.mat[0][0] + MOD) % MOD);

            if (bb.mat[0][0] > 0)
                printf ("%llu\n", bb.mat[0][0] % MOD);
                //cout << bb.mat[0][0] % MOD << endl;

			else
				printf ("%llu\n", (bb.mat[0][0] + MOD) %MOD);
				//cout << (bb.mat[0][0] + MOD) % MOD + 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

143

#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 unsigned long long MOD = 18446744073709551615uLL;

//18446744073709551615

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 2;

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

//申请变量

struct Mat

{

unsigned long long mat[maxn][maxn];

};

//重载Mat乘法运算

Mat operator * (Mat a, Mat b)

{

Mat c;

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

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

{

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

{

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

for (unsigned 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;

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

}

return c;

}

//重载Mat乘幂运算

Mat operator ^ (Mat a, unsigned long long k)

{

Mat c;

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

for(unsigned 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);

Mat aa;

int t, flag =1;

scanf ("%d", &t);

while (t--)

{

unsigned long long p, q, n;

scanf ("%llu%llu%llu", &p, &q, &n);

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

if (n == 0)

puts ("2");

else if (n == 1)

printf ("%llu\n", p % MOD);

//cout << p % MOD << endl;

else if (n == 2)

printf ("%llu\n", (p * p - 2 * q) % MOD);

//cout << (p * p - 2 * q) % MOD << endl;

else

{

aa.mat[0][0] = p, aa.mat[0][1] = -q;

aa.mat[1][0] = 1, aa.mat[1][1] = 0;

Mat bb = aa ^ (n - 2), cc;

// cout << aa.mat[0][0] << " " << aa.mat[0][1] << endl;

// cout << aa.mat[1][0] << " " << aa.mat[1][1] << endl;

cc.mat[0][0] = (p * p - 2 * q) % MOD;

cc.mat[1][0] = p % MOD;

bb = bb * cc;

//printf ("%ulld\n", (bb.mat[0][0] + MOD) % MOD);

if (bb.mat[0][0] > 0)

printf ("%llu\n", bb.mat[0][0] % MOD);

//cout << bb.mat[0][0] % MOD << endl;

else

printf ("%llu\n", (bb.mat[0][0] + MOD) %MOD);

//cout << (bb.mat[0][0] + MOD) % MOD + 1<< endl;

}

return 0;

}

lightoj1067

maksyuki 发表于 oj 分类，标签: 组合数学-组合数取模(Lucas)

27 8月 2015

1067 - Combinations

For example, say there are 4 items; you want to take 2 of them. So, you can do it 6 ways.Given n different objects, you want to take k of them. How many ways to can do it?

Input

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

Each test case contains two integers n (1 ≤ n ≤ 10⁶), k (0 ≤ k ≤ n).

Output

For each case, output the case number and the desired value. Since the result can be very large, you have to print the result modulo 1000003.

Sample Input	Output for Sample Input
34 25 06 4	Case 1: 6Case 2: 1Case 3: 15

题目类型：组合数取模(Lucas)

算法分析：由于模值p不算太大且为质数，则可以使用Lucas定理求解

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

const int maxn = 1000000 + 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;
}

long long fac[maxn];//注意fac数组的大小一定要小于模值p

//在调用Lucas之前一定要先调用GetFactor函数
long long GetFactor (long long p)
{
    fac[0] = 1;
    for (long long i = 1; i <= p; i++)
        fac[i] = (fac[i-1] * i) % p;
}

long long Lucas (long long n, long long m, long long p)
{
    long long ret = 1;
    while (n && m)
    {
        long long a = n % p, b = m % p;
        if (a < b)
            return 0;

        ret = (ret * fac[a] * pow_mod (fac[b] * fac[a-b] % p, p - 2, p)) % p;
        n /= p;
        m /= p;
    }

return ret;
}

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

    GetFactor (MOD);

    long long flag = 1, t, n, k;
    scanf ("%lld", &t);

    while (t--)
    {
        scanf ("%lld%lld", &n, &k);
        printf ("Case %lld: %lld\n",  flag++, Lucas (n, k, 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

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

const int maxn = 1000000 + 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;

}

long long fac[maxn];//注意fac数组的大小一定要小于模值p

//在调用Lucas之前一定要先调用GetFactor函数

long long GetFactor (long long p)

{

fac[0] = 1;

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

fac[i] = (fac[i-1] * i) % p;

}

long long Lucas (long long n, long long m, long long p)

{

long long ret = 1;

while (n && m)

{

long long a = n % p, b = m % p;

if (a < b)

return 0;

ret = (ret * fac[a] * pow_mod (fac[b] * fac[a-b] % p, p - 2, p)) % p;

n /= p;

m /= p;

}

return ret;

}

int main()

{

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

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

GetFactor (MOD);

long long flag = 1, t, n, k;

scanf ("%lld", &t);

while (t--)

{

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

printf ("Case %lld: %lld\n", flag++, Lucas (n, k, MOD));

}

return 0;

}

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;

}

返回首页上一页 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

Input

Output

Sample Input

Output for Sample Input

Notes

Input

Output

Sample Input

Output for Sample Input

Note

Input

Output

Sample Input

Output for Sample Input

Note

Input

Output

Sample Input

Output for Sample Input

Note

Input

Output

Sample Input

Output for Sample Input

Output

Sample Input

Output for Sample 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

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

分类目录

标签云

书签

近期评论