Codeforces Round #322(Div.2) (4/6)

maksyuki 发表于比赛分类，标签: 比赛-codeforces

29 9月 2015

A Vasya the Hipster

One day Vasya the Hipster decided to count how many socks he had. It turned out that he had a red socks and bblue socks. According to the latest fashion, hipsters should wear the socks of different colors: a red one on the left foot, a blue one on the right foot.

Every day Vasya puts on new socks in the morning and throws them away before going to bed as he doesn't want to wash them.

Vasya wonders, what is the maximum number of days when he can dress fashionable and wear different socks, and after that, for how many days he can then wear the same socks until he either runs out of socks or cannot make a single pair from the socks he's got.

Can you help him?

Input

The single line of the input contains two positive integers a and b (1 ≤ a, b ≤ 100) — the number of red and blue socks that Vasya's got.

Output

Print two space-separated integers — the maximum number of days when Vasya can wear different socks and the number of days when he can wear the same socks until he either runs out of socks or cannot make a single pair from the socks he's got.

Keep in mind that at the end of the day Vasya throws away the socks that he's been wearing on that day.

Sample test(s)

input

3 1

output

1 1

input

2 3

output

2 0

input

7 3

output

3 2

Note

In the first sample Vasya can first put on one pair of different socks, after that he has two red socks left to wear on the second day.

题目类型：水题

算法分析：输出两个数的最小值和另一个数减去最小值除以二的结果

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define DB(ccc) cout << #ccc << " = " << ccc << endl

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

int main()
{
//    CPPFF;
    int a, b;
    cin >> a >> b;
    int c = min (a, b);
    cout << c << " ";

    a -= c, b -= c;
    if (a == 0)
        cout << b / 2 << endl;

    else
        cout << a / 2 << endl;
    return 0;
}

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 1666;

int main()

{

// CPPFF;

int a, b;

cin >> a >> b;

int c = min (a, b);

cout << c << " ";

a -= c, b -= c;

if (a == 0)

cout << b / 2 << endl;

else

cout << a / 2 << endl;

return 0;

}

B Luxurious Houses

The capital of Berland has n multifloor buildings. The architect who built up the capital was very creative, so all the houses were built in one row.

Let's enumerate all the houses from left to right, starting with one. A house is considered to be luxurious if the number of floors in it is strictly greater than in all the houses with larger numbers. In other words, a house is luxurious if the number of floors in it is strictly greater than in all the houses, which are located to the right from it. In this task it is assumed that the heights of floors in the houses are the same.

The new architect is interested in n questions, i-th of them is about the following: "how many floors should be added to the i-th house to make it luxurious?" (for all i from 1 to n, inclusive). You need to help him cope with this task.

Note that all these questions are independent from each other — the answer to the question for house i does not affect other answers (i.e., the floors to the houses are not actually added).

Input

The first line of the input contains a single number n (1 ≤ n ≤ 10⁵) — the number of houses in the capital of Berland.

The second line contains n space-separated positive integers h_i (1 ≤ h_i ≤ 10⁹), where h_i equals the number of floors in the i-th house.

Output

Print n integers a₁, a₂, ..., a_n, where number a_i is the number of floors that need to be added to the house number ito make it luxurious. If the house is already luxurious and nothing needs to be added to it, then a_i should be equal to zero.

All houses are numbered from left to right, starting from one.

Sample test(s)

input

5
1 2 3 1 2

output

3 2 0 2 0

input

4
3 2 1 4

output

2 3 4 0

题目类型：区间最值查询

算法分析：直接使用线段树查询每个区间的最值即可，注意此时输出”0”的条件！！！

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl

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

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

LL maxval[maxn<<2], mmax, aa[maxn], len;

void PushUp (int rt)
{
    maxval[rt] = max (maxval[rt<<1], maxval[rt<<1|1]);
}

void Build (int rt, int l, int r)
{
    if (l == r)
    {
        scanf ("%d", &maxval[rt]);
        aa[len] = maxval[rt];
        len++;
        return ;
    }
    int m = (l + r) >> 1;
    Build (lson);
    Build (rson);
    PushUp (rt);
}

void Query (int rt, int l, int r, int L, int R)
{
    if (L <= l && r <= R)
    {
        mmax = max (mmax, maxval[rt]);
        return;
    }
    int m = (l + r) >> 1;
    if (L <= m)
        Query (lson, L, R);

    if (R > m)
        Query (rson, L, R);
}


int main()
{
//    CFF;
    LL n;
    scanf ("%I64d", &n);
    len = 1;
    Build (1, 1, n);

    for (LL i = 1; i <= n; i++)
    {
        mmax = -INF;
        Query (1, 1, n, i + 1, n);
        if (i != 1)
            printf (" ");

        if (aa[i] >= mmax)
            printf ("0");

        else
            printf ("%I64d", mmax - aa[i] + 1);
    }
    return 0;
}

100

101

102

103

104

105

106

107

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 1666;

#define lson rt << 1, l, m

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

LL maxval[maxn<<2], mmax, aa[maxn], len;

void PushUp (int rt)

{

maxval[rt] = max (maxval[rt<<1], maxval[rt<<1|1]);

}

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

{

if (l == r)

{

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

aa[len] = maxval[rt];

len++;

return ;

}

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

Build (lson);

Build (rson);

PushUp (rt);

}

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

{

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

{

mmax = max (mmax, maxval[rt]);

return;

}

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

if (L <= m)

Query (lson, L, R);

if (R > m)

Query (rson, L, R);

}

int main()

{

// CFF;

LL n;

scanf ("%I64d", &n);

len = 1;

Build (1, 1, n);

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

{

mmax = -INF;

Query (1, 1, n, i + 1, n);

if (i != 1)

printf (" ");

if (aa[i] >= mmax)

printf ("0");

else

printf ("%I64d", mmax - aa[i] + 1);

}

return 0;

}

C Developing Skills

Petya loves computer games. Finally a game that he's been waiting for so long came out!

The main character of this game has n different skills, each of which is characterized by an integer a_i from 0 to 100. The higher the number a_i is, the higher is the i-th skill of the character. The total rating of the character is calculated as the sum of the values of for all i from 1 to n. The expression ⌊ x⌋ denotes the result of rounding the numberx down to the nearest integer.

At the beginning of the game Petya got k improvement units as a bonus that he can use to increase the skills of his character and his total rating. One improvement unit can increase any skill of Petya's character by exactly one. For example, if a₄ = 46, after using one imporvement unit to this skill, it becomes equal to 47. A hero's skill cannot rise higher more than 100. Thus, it is permissible that some of the units will remain unused.

Your task is to determine the optimal way of using the improvement units so as to maximize the overall rating of the character. It is not necessary to use all the improvement units.

Input

The first line of the input contains two positive integers n and k (1 ≤ n ≤ 10⁵, 0 ≤ k ≤ 10⁷) — the number of skills of the character and the number of units of improvements at Petya's disposal.

The second line of the input contains a sequence of n integers a_i (0 ≤ a_i ≤ 100), where a_i characterizes the level of the i-th skill of the character.

Output

The first line of the output should contain a single non-negative integer — the maximum total rating of the character that Petya can get using k or less improvement units.

Sample test(s)

input

2 4
7 9

output

input

3 8
17 15 19

output

input

2 2
99 100

output

Note

In the first test case the optimal strategy is as follows. Petya has to improve the first skill to 10 by spending 3 improvement units, and the second skill to 10, by spending one improvement unit. Thus, Petya spends all his improvement units and the total rating of the character becomes equal tolfloor frac{100}{10} rfloor + lfloor frac{100}{10} rfloor = 10 + 10 = 20.

In the second test the optimal strategy for Petya is to improve the first skill to 20 (by spending 3 improvement units) and to improve the third skill to 20 (in this case by spending 1 improvement units). Thus, Petya is left with 4 improvement units and he will be able to increase the second skill to 19 (which does not change the overall rating, so Petya does not necessarily have to do it). Therefore, the highest possible total rating in this example is .

In the third test case the optimal strategy for Petya is to increase the first skill to 100 by spending 1 improvement unit. Thereafter, both skills of the character will be equal to 100, so Petya will not be able to spend the remaining improvement unit. So the answer is equal to .

题目类型：排序+贪心

算法分析：由于最后的和是整除10的结果，所以一个贪心策略是先将每个能加的数加到最近整除10的数，这里可以先排序处理。最后如果还有富余，则看能够累加多少个10(需比较此时每个数的值)

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define DB(ccc) cout << #ccc << " = " << ccc << endl

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

struct node
{
    int v, cnt;
};

bool operator < (const node a, const node b) {return a.cnt < b.cnt;}

node aa[maxn];

int main()
{
//    CFF;
    int n, k;
    scanf ("%d%d", &n, &k);

    for (int i = 1; i <= n; i++)
    {
        scanf ("%d", &aa[i].v);
        aa[i].cnt = 0;
        for (int j = aa[i].v; j % 10 != 0; j++)
            aa[i].cnt++;
    }

    sort (aa + 1, aa + 1 + n);
    for (int i = 1; i <= n; i++)
    {
        if (aa[i].v == 100)
            continue;

        if (aa[i].v < 100 && k >= aa[i].cnt)
        {
            k -= aa[i].cnt;
            aa[i].v += aa[i].cnt;
        }

        else
            break;
    }

    int tt = 0;
    if (k)
    {
        for (int i = 1; i <= n; i++)
            tt += (100 - aa[i].v) / 10;

        k /= 10;
        if (k < tt)
            tt = k;
    }

    int res = 0;
    for (int i = 1; i <= n; i++)
        res += aa[i].v / 10;

    printf ("%d\n", res + tt);

    return 0;
}

100

101

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 1666;

struct node

{

int v, cnt;

};

bool operator < (const node a, const node b) {return a.cnt < b.cnt;}

node aa[maxn];

int main()

{

// CFF;

int n, k;

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

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

{

scanf ("%d", &aa[i].v);

aa[i].cnt = 0;

for (int j = aa[i].v; j % 10 != 0; j++)

aa[i].cnt++;

}

sort (aa + 1, aa + 1 + n);

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

{

if (aa[i].v == 100)

continue;

if (aa[i].v < 100 && k >= aa[i].cnt)

{

k -= aa[i].cnt;

aa[i].v += aa[i].cnt;

}

else

break;

}

int tt = 0;

if (k)

{

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

tt += (100 - aa[i].v) / 10;

k /= 10;

if (k < tt)

tt = k;

}

int res = 0;

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

res += aa[i].v / 10;

printf ("%d\n", res + tt);

return 0;

}

D Three Logos

Three companies decided to order a billboard with pictures of their logos. A billboard is a big square board. A logo of each company is a rectangle of a non-zero area.

Advertisers will put up the ad only if it is possible to place all three logos on the billboard so that they do not overlap and the billboard has no empty space left. When you put a logo on the billboard, you should rotate it so that the sides were parallel to the sides of the billboard.

Your task is to determine if it is possible to put the logos of all the three companies on some square billboard without breaking any of the described rules.

Input

The first line of the input contains six positive integers x₁, y₁, x₂, y₂, x₃, y₃ (1 ≤ x₁, y₁, x₂, y₂, x₃, y₃ ≤ 100), wherex_i and y_i determine the length and width of the logo of the i-th company respectively.

Output

If it is impossible to place all the three logos on a square shield, print a single integer "-1" (without the quotes).

If it is possible, print in the first line the length of a side of square n, where you can place all the three logos. Each of the next n lines should contain n uppercase English letters "A", "B" or "C". The sets of the same letters should form solid rectangles, provided that:

the sizes of the rectangle composed from letters "A" should be equal to the sizes of the logo of the first company,
the sizes of the rectangle composed from letters "B" should be equal to the sizes of the logo of the second company,
the sizes of the rectangle composed from letters "C" should be equal to the sizes of the logo of the third company,

Note that the logos of the companies can be rotated for printing on the billboard. The billboard mustn't have any empty space. If a square billboard can be filled with the logos in multiple ways, you are allowed to print any of them.

See the samples to better understand the statement.

Sample test(s)

input

5 1 2 5 5 2

output

5
AAAAA
BBBBB
BBBBB
CCCCC
CCCCC

input

4 4 2 6 4 2

output

6
BBBBBB
BBBBBB
AAAACC
AAAACC
AAAACC
AAAACC

题目类型：涂色模拟

算法分析：首先如果每个矩形的面积和不是完全平方数，则直接输出”-1”，否则先将A涂上(由于可以旋转且3个矩形要把一个正方形涂满，易知每个矩形至少覆盖两条正方形的边，则A从左上角涂是合理的)。然后开始涂B，此时需要分类判断剩下的位置是否满足B的范围，注意此时涂B不一定要将某一行(列)都涂满！！！涂完B之后将剩下的所有位置都涂上C(不见得是合理的)，最后再判断涂上的C是否是题目所给的矩形，如果不是，则输出”-1”，否则输出答案即可

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl

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

char aa[maxn][maxn];

int main()
{
//    CFF;
    int x1, y1, x2, y2, x3, y3;
//freopen ("bbb.txt", "w", stdout);

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

    int tt = x1 * y1 + x2 * y2 + x3 * y3;
    int val = (int) sqrt ((double) tt);
    if (val * val != tt)
        puts ("-1");


    else
    {
        tt = (int) sqrt ((double)tt);
        for (int i = 1; i <= tt; i++)
            for (int j = 1; j <= tt; j++)
                aa[i][j] = '@';

        for (int i = 1; i <= x1; i++)
            for (int j = 1; j <= y1; j++)
                aa[i][j] = 'A';


        int rrow = tt - x1, rcol = tt - y1;
        if (rrow && rcol)
        {
            if (rcol == x2 || rcol == y2)
            {
                int ta;
                if (rcol == x2)
                    ta = y2;

                else
                    ta = x2;

                for (int i = 1; i <= ta; i++)
                    for (int j = y1 + 1; j <= tt; j++)
                        aa[i][j] = 'B';

                for (int i = 1; i <= tt; i++)
                    for (int j = 1; j <= tt; j++)
                        if (aa[i][j] != 'A' && aa[i][j] != 'B')
                            aa[i][j] = 'C';
            }

            else
            {
                int ta;
                if (rrow == x2)
                    ta = y2;

                else
                    ta = x2;

                for (int i = x1 + 1; i <= tt; i++)
                    for (int j = 1; j <= ta; j++)
                        aa[i][j] = 'B';

                for (int i = 1; i <= tt; i++)
                    for (int j = 1; j <= tt; j++)
                        if (aa[i][j] != 'A' && aa[i][j] != 'B')
                            aa[i][j] = 'C';
            }
        }

        if (!rrow)
        {
            swap (rrow, rcol);
            swap (x1, y1);
            for (int i = 1; i <= tt; i++)
                for (int j = i; j <= tt; j++)
                {
                    if (i == j)
                        continue;

                    swap (aa[i][j], aa[j][i]);
                }
        }

        if (!rcol)
        {
            if (tt == x2 || tt == y2)
            {
                int ta;
                if (tt == x2)
                    ta = y2;

                else
                    ta = x2;

                for (int i = x1 + 1, k = 1; k <= ta; i++, k++)
                    for (int j = 1; j <= tt; j++)
                        aa[i][j] = 'B';
            }

            else
            {
                if (rrow == x2 || rrow == y2)
                {
                    int ta;
                    if (rrow == x2)
                        ta = y2;

                    else
                        ta = x2;

                    for (int i = x1 + 1; i <= tt; i++)
                        for (int j = 0; j <= ta; j++)
                            aa[i][j] = 'B';
                }
            }


            for (int i = 1; i <= tt; i++)
                for (int j = 1; j <= tt; j++)
                    if (aa[i][j] != 'A' && aa[i][j] != 'B')
                        aa[i][j] = 'C';
        }

        bool is_valid = true;
        for (int i = 1; i <= tt; i++)
        {
            int tx = 0;
            for (int j = 1; j <= tt; j++)
                if (aa[i][j] == 'C')
                    tx++;

            if (tx && tx != x3 && tx != y3)
            {
                is_valid = false;
                break;
            }
        }

        if (!is_valid)
            puts ("-1");

        else
        {
            printf ("%d\n", tt);
            for (int i = 1; i <= tt; i++)
            {
                for (int j = 1; j <= tt; j++)
                    printf ("%c", aa[i][j]);
                puts ("");
            }
        }

    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 166;

char aa[maxn][maxn];

int main()

{

// CFF;

int x1, y1, x2, y2, x3, y3;

//freopen ("bbb.txt", "w", stdout);

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

int tt = x1 * y1 + x2 * y2 + x3 * y3;

int val = (int) sqrt ((double) tt);

if (val * val != tt)

puts ("-1");

else

{

tt = (int) sqrt ((double)tt);

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

for (int j = 1; j <= tt; j++)

aa[i][j] = '@';

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

for (int j = 1; j <= y1; j++)

aa[i][j] = 'A';

int rrow = tt - x1, rcol = tt - y1;

if (rrow && rcol)

{

if (rcol == x2 || rcol == y2)

{

int ta;

if (rcol == x2)

ta = y2;

else

ta = x2;

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

for (int j = y1 + 1; j <= tt; j++)

aa[i][j] = 'B';

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

for (int j = 1; j <= tt; j++)

if (aa[i][j] != 'A' && aa[i][j] != 'B')

aa[i][j] = 'C';

}

else

{

int ta;

if (rrow == x2)

ta = y2;

else

ta = x2;

for (int i = x1 + 1; i <= tt; i++)

for (int j = 1; j <= ta; j++)

aa[i][j] = 'B';

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

for (int j = 1; j <= tt; j++)

if (aa[i][j] != 'A' && aa[i][j] != 'B')

aa[i][j] = 'C';

}

if (!rrow)

{

swap (rrow, rcol);

swap (x1, y1);

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

for (int j = i; j <= tt; j++)

{

if (i == j)

continue;

swap (aa[i][j], aa[j][i]);

}

if (!rcol)

{

if (tt == x2 || tt == y2)

{

int ta;

if (tt == x2)

ta = y2;

else

ta = x2;

for (int i = x1 + 1, k = 1; k <= ta; i++, k++)

for (int j = 1; j <= tt; j++)

aa[i][j] = 'B';

}

else

{

if (rrow == x2 || rrow == y2)

{

int ta;

if (rrow == x2)

ta = y2;

else

ta = x2;

for (int i = x1 + 1; i <= tt; i++)

for (int j = 0; j <= ta; j++)

aa[i][j] = 'B';

}

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

for (int j = 1; j <= tt; j++)

if (aa[i][j] != 'A' && aa[i][j] != 'B')

aa[i][j] = 'C';

}

bool is_valid = true;

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

{

int tx = 0;

for (int j = 1; j <= tt; j++)

if (aa[i][j] == 'C')

tx++;

if (tx && tx != x3 && tx != y3)

{

is_valid = false;

break;

}

if (!is_valid)

puts ("-1");

else

{

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

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

{

for (int j = 1; j <= tt; j++)

printf ("%c", aa[i][j]);

puts ("");

}

return 0;

}

2015ACM-ICPC亚洲区合肥站网赛(0/10)

maksyuki 发表于比赛分类，

27 9月 2015

BestCoder Round #57(Div.2) (2/4) (Div.1) (1/4)

maksyuki 发表于比赛分类，标签: 比赛-bestcoder

27 9月 2015

Scaena Felix

Problem Description

Given a parentheses sequence consist of '(' and ')', a modify can filp a parentheses, changing '(' to ')' or ')' to '('. 阅读全文 »

2015ACM-ICPC亚洲区上海站网赛(0/11)

maksyuki 发表于比赛分类，

27 9月 2015

Codeforces Round #321(Div.2) (2/5)

maksyuki 发表于比赛分类，标签: 比赛-codeforces

25 9月 2015

A Kefa and First Steps

Kefa decided to make some money doing business on the Internet for exactly n days. He knows that on the i-th day (1 ≤ i ≤ n) he makes a_i money. Kefa loves progress, that's why he wants to know the length of the maximum non-decreasing subsegment in sequence a_i. Let us remind you that the subsegment of the sequence is its continuous fragment. A subsegment of numbers is called non-decreasing if all numbers in it follow in the non-decreasing order.

Help Kefa cope with this task!

Input

The first line contains integer n (1 ≤ n ≤ 10⁵).

The second line contains n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹).

Output

Print a single integer — the length of the maximum non-decreasing subsegment of sequence a.

Sample test(s)

input

6
2 2 1 3 4 1

output

input

3
2 2 9

output

Note

In the first test the maximum non-decreasing subsegment is the numbers from the third to the fifth one.

In the second test the maximum non-decreasing subsegment is the numbers from the first to the third one.

题目类型：线性DP

算法分析：dp[i]表示以第i个字符结尾的最长连续非递减子序列的长度，则边界为dp[1] = 1，状态转移方程为：若a[i-1] <= a[i]，则dp[i] = dp[i-1] + 1；否则dp[i] = 1

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define DB(ccc) cout << #ccc << " = " << ccc << endl

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

int a[maxn], dp[maxn];

int main()
{
//    CFF;
    int n;
    scanf ("%d", &n);

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

    fill (dp, dp + maxn, 1);
    for (int i = 2; i <= n; i++)
    {
        if (a[i] >= a[i-1])
            dp[i] = dp[i-1] + 1;

        else
            dp[i] = 1;
    }
    int maxval = -INF;
    for (int i = 1; i <= n; i++)
        maxval = max (maxval, dp[i]);

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

    return 0;
}

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 1666;

int a[maxn], dp[maxn];

int main()

{

// CFF;

int n;

scanf ("%d", &n);

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

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

fill (dp, dp + maxn, 1);

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

{

if (a[i] >= a[i-1])

dp[i] = dp[i-1] + 1;

else

dp[i] = 1;

}

int maxval = -INF;

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

maxval = max (maxval, dp[i]);

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

return 0;

}

B Kefa and Company

Kefa wants to celebrate his first big salary by going to restaurant. However, he needs company.

Kefa has n friends, each friend will agree to go to the restaurant if Kefa asks. Each friend is characterized by the amount of money he has and the friendship factor in respect to Kefa. The parrot doesn't want any friend to feel poor compared to somebody else in the company (Kefa doesn't count). A friend feels poor if in the company there is someone who has at least d units of money more than he does. Also, Kefa wants the total friendship factor of the members of the company to be maximum. Help him invite an optimal company!

Input

The first line of the input contains two space-separated integers, n and d (1 ≤ n ≤ 10⁵, ) — the number of Kefa's friends and the minimum difference between the amount of money in order to feel poor, respectively.

Next n lines contain the descriptions of Kefa's friends, the (i + 1)-th line contains the description of the i-th friend of type m_i, s_i (0 ≤ m_i, s_i ≤ 10⁹) — the amount of money and the friendship factor, respectively.

Output

Print the maximum total friendship factir that can be reached.

Sample test(s)

input

4 5
75 5
0 100
150 20
75 1

output

100

input

5 100
0 7
11 32
99 10
46 8
87 54

output

111

Note

In the first sample test the most profitable strategy is to form a company from only the second friend. At all other variants the total degree of friendship will be worse.

In the second sample test we can take all the friends.

题目类型：排序

算法分析：首先将输入的数据按照money从小到大排序，然后使用两个指针从头往后扫，即常说的“追逐法”

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl

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

struct node
{
    LL v, w;
};

bool operator < (const node aa, const node bb) {return aa.v < bb.v;}

node aa[maxn];

int main()
{
//    CFF;
    int n, d;
    scanf ("%d%d", &n, &d);
    for (int i = 1; i <= n; i++)
        scanf ("%I64d%I64d", &aa[i].v, &aa[i].w);

    sort (aa + 1, aa + 1 + n);

    LL maxval = -INF, tt = 0, ta = 1, tb = 1;
    for (; ta <= n; ta++)
    {
        while (tb <= n && aa[tb].v < aa[ta].v + d)
        {
            tt += aa[tb].w;
            tb++;
        }

        maxval = max (maxval, tt);
        tt -= aa[ta].w;
    }
    printf ("%I64d\n", maxval);
    return 0;
}

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 6;

struct node

{

LL v, w;

};

bool operator < (const node aa, const node bb) {return aa.v < bb.v;}

node aa[maxn];

int main()

{

// CFF;

int n, d;

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

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

scanf ("%I64d%I64d", &aa[i].v, &aa[i].w);

sort (aa + 1, aa + 1 + n);

LL maxval = -INF, tt = 0, ta = 1, tb = 1;

for (; ta <= n; ta++)

{

while (tb <= n && aa[tb].v < aa[ta].v + d)

{

tt += aa[tb].w;

tb++;

}

maxval = max (maxval, tt);

tt -= aa[ta].w;

}

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

return 0;

}

算法分析：也可以使用二分的方法来做，此时枚举所有的点a，然后查找a的val值+d的下界，最后通过维护的一个前缀和来将最大值更新，注意此时所有的节点之间的money都要满足差小于d！！！所以只能够计算[val, val + d)的值，不能够计算(val - d, val + d)的值！！！

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl

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

struct node
{
    LL v, w;
};

bool operator < (const node aa, const node bb) {return aa.v < bb.v;}

node aa[maxn];
LL tt[maxn], sum[maxn];

int main()
{
//    CFF;
    int n, d;
    scanf ("%d%d", &n, &d);
    for (int i = 0; i < n; i++)
        scanf ("%I64d%I64d", &aa[i].v, &aa[i].w);

    sort (aa, aa + n);

    tt[0] = aa[0].v;
    for (int i = 0; i < n; i++)
    {
        sum[i+1] = sum[i] + aa[i].w;
        tt[i] = aa[i].v;
    }
//    DB (sum[5]);

    LL res = -INF;
    for (int i = 0; i < n; i++)
    {
        int ta = lower_bound (tt, tt + n, tt[i] + d) - tt;
//        DB(ta);
        res = max (res, sum[ta] - sum[i]);
    }

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

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 6;

struct node

{

LL v, w;

};

bool operator < (const node aa, const node bb) {return aa.v < bb.v;}

node aa[maxn];

LL tt[maxn], sum[maxn];

int main()

{

// CFF;

int n, d;

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

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

scanf ("%I64d%I64d", &aa[i].v, &aa[i].w);

sort (aa, aa + n);

tt[0] = aa[0].v;

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

{

sum[i+1] = sum[i] + aa[i].w;

tt[i] = aa[i].v;

}

// DB (sum[5]);

LL res = -INF;

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

{

int ta = lower_bound (tt, tt + n, tt[i] + d) - tt;

// DB(ta);

res = max (res, sum[ta] - sum[i]);

}

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

return 0;

}

bzoj1087

maksyuki 发表于 oj 分类，标签: DP-状压DP

25 9月 2015

1087: [SCOI2005]互不侵犯King

Description

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。

Input

只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）阅读全文 »

poj2385

maksyuki 发表于 oj 分类，标签: DP-线性DP

24 9月 2015

Apple Catching

It is a little known fact that cows love apples. Farmer John has two apple trees (which are conveniently numbered 1 and 2) in his field, each full of apples. Bessie cannot reach the apples when they are on the tree, so she must wait for them to fall. However, she must catch them in the air since the apples bruise when they hit the ground (and no one wants to eat bruised apples). Bessie is a quick eater, so an apple she does catch is eaten in just a few seconds.

Each minute, one of the two apple trees drops an apple. Bessie, having much practice, can catch an apple if she is standing under a tree from which one falls. While Bessie can walk between the two trees quickly (in much less than a minute), she can stand under only one tree at any time. Moreover, cows do not get a lot of exercise, so she is not willing to walk back and forth between the trees endlessly (and thus misses some apples).

Apples fall (one each minute) for T (1 <= T <= 1,000) minutes. Bessie is willing to walk back and forth at most W (1 <= W <= 30) times. Given which tree will drop an apple each minute, determine the maximum number of apples which Bessie can catch. Bessie starts at tree 1.

Input

* Line 1: Two space separated integers: T and W

* Lines 2..T+1: 1 or 2: the tree that will drop an apple each minute.

Output

* Line 1: The maximum number of apples Bessie can catch without walking more than W times.

Sample Input

7 2

Sample Output

Hint

INPUT DETAILS:

Seven apples fall - one from tree 2, then two in a row from tree 1, then two in a row from tree 2, then two in a row from tree 1. Bessie is willing to walk from one tree to the other twice.

OUTPUT DETAILS:

Bessie can catch six apples by staying under tree 1 until the first two have dropped, then moving to tree 2 for the next two, then returning back to tree 1 for the final two.

Source

USACO 2004 November

题目类型：线性DP

算法分析：dp[i][j]表示前i分钟恰好走j次所能够获得的最多苹果数，初始化dp数组全为0，状态转移方程为：

若第i分钟树1落下一个苹果

(1)此时j是奇数，表示当前人在树2下面，则dp[i][j] = max (dp[i-1][j-1], dp[i-1][j])

(2)此时j是偶数，表示当前人在树1下面，则dp[i][j] = 1 + max (dp[i-1][j-1], dp[i-1][j])

若第i分钟树2落下一个苹果

(1)此时j是奇数，表示当前人在树2下面，则dp[i][j] = 1 + max (dp[i-1][j-1], dp[i-1][j])

(2)此时j是偶数，表示当前人在树1下面，则dp[i][j] = max (dp[i-1][j-1], dp[i-1][j])

注意要特殊处理j = 0的情况！！！最后输出所有可能走的步数时的最大苹果数即可

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl

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

int dp[1000+66][30+6], aa[maxn];

int main()
{
//    CFF;
    int t, w;
    while (scanf ("%d%d", &t, &w) != EOF)
    {
        for (int i = 1; i <= t; i++)
            scanf ("%d", &aa[i]);

        memset (dp, 0, sizeof (dp));
        for (int i = 1; i <= t; i++)
            for (int j = 0; j <= w; j++)
            {
                if (aa[i] == 1)
                {
                    if (j == 0)
                        dp[i][j] = dp[i-1][j] + 1;

                    else if (j & 1)
                        dp[i][j] = max (dp[i-1][j], dp[i-1][j-1]);

                    else
                        dp[i][j] = 1 + max (dp[i-1][j], dp[i-1][j-1]);
                }

                else
                {
                    if (j == 0)
                        dp[i][j] = dp[i-1][j];

                    else if (j & 1)
                        dp[i][j] = 1 + max (dp[i-1][j], dp[i-1][j-1]);

                    else
                        dp[i][j] = max (dp[i-1][j], dp[i-1][j-1]);
                }
            }


        printf ("%d\n", *max_element (dp[t], dp[t] + w + 1));
    }
    return 0;
}

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 6;

int dp[1000+66][30+6], aa[maxn];

int main()

{

// CFF;

int t, w;

while (scanf ("%d%d", &t, &w) != EOF)

{

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

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

memset (dp, 0, sizeof (dp));

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

for (int j = 0; j <= w; j++)

{

if (aa[i] == 1)

{

if (j == 0)

dp[i][j] = dp[i-1][j] + 1;

else if (j & 1)

dp[i][j] = max (dp[i-1][j], dp[i-1][j-1]);

else

dp[i][j] = 1 + max (dp[i-1][j], dp[i-1][j-1]);

}

else

{

if (j == 0)

dp[i][j] = dp[i-1][j];

else if (j & 1)

dp[i][j] = 1 + max (dp[i-1][j], dp[i-1][j-1]);

else

dp[i][j] = max (dp[i-1][j], dp[i-1][j-1]);

}

printf ("%d\n", *max_element (dp[t], dp[t] + w + 1));

}

return 0;

}

poj3659

maksyuki 发表于 oj 分类，标签: DP-树形DP, 图论-最小点支配

24 9月 2015

Cell Phone Network

Farmer John has decided to give each of his cows a cell phone in hopes to encourage their social interaction. This, however, requires him to set up cell phone towers on his N (1 ≤ N ≤ 10,000) pastures (conveniently numbered 1..N) so they can all communicate.

Exactly N-1 pairs of pastures are adjacent, and for any two pastures A and B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B) there is a sequence of adjacent pastures such that A is the first pasture in the sequence and B is the last. Farmer John can only place cell phone towers in the pastures, and each tower has enough range to provide service to the pasture it is on and all pastures adjacent to the pasture with the cell tower.

Help him determine the minimum number of towers he must install to provide cell phone service to each pasture.

Input

* Line 1: A single integer: N
* Lines 2..N: Each line specifies a pair of adjacent pastures with two space-separated integers: A and B

Output

* Line 1: A single integer indicating the minimum number of towers to install

Sample Input

1 3

5 2

4 3

3 5

Sample Output

Source

USACO 2008 January Gold

题目类型：最小点支配(树形DP)

算法分析：dp[u][1]表示以u为根的子树在u这个节点上面安排士兵所具有的最小点支配数，dp[u][2]表示以u为根的子树在u这个节点上不安排士兵，而被其子节点所支配的最小点支配数，dp[u][3]表示以u为根的子树在u这个节点上不安排士兵，而被其父节点所支配的最小点支配数。初始条件是dp[u][1] = 1, dp[u][2] = dp[u][3] = 0，状态转移方程为：
dp[u][1] += min (dp[v][1], dp[v][2], dp[v][3])

dp[u][3] += min (dp[v][1], dp[v][2])

(1)dp[u][2] = INF(若u是叶子节点)

(2)dp[u][2] = 若选择了的u所有子节点中有dp[v][1]则计算完后直接返回即可，反之则使用一个变量来记录dp[v][1] - dp[v][2]的最小值，最后循环完之后再加上这个变量的值

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl

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

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

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

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

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

bool vis[maxn];
int dp[maxn][6];

void dfs (int rt)
{
    vis[rt] = true;
    bool is_valid = true;
    int tt = INF;
    for (int i = head[rt]; i != -1; i = edge[i].next)
    {
        if (!vis[edge[i].v])
        {
            dfs (edge[i].v);
            dp[rt][1] += min (dp[edge[i].v][1], min (dp[edge[i].v][2], dp[edge[i].v][3]));
            dp[rt][3] += min (dp[edge[i].v][1], dp[edge[i].v][2]);
            if (dp[edge[i].v][1] <= dp[edge[i].v][2])
            {
                dp[rt][2] += dp[edge[i].v][1];
                is_valid = false;
            }

            else
            {
                dp[rt][2] += dp[edge[i].v][2];
                tt = min (tt, dp[edge[i].v][1] - dp[edge[i].v][2]);
            }
        }
    }

    if (is_valid)
        dp[rt][2] += tt;
}

int main()
{
//    CFF;
    int n;
    while (scanf ("%d", &n) != EOF)
    {
        Init ();
        for (int i = 1; i <= n; i++)
        {
            int u, v;
            scanf ("%d%d", &u, &v);
            AddEdge (u, v, 1);
            AddEdge (v, u, 1);
        }

        memset (vis, false, sizeof (vis));
        for (int i = 1; i <= n; i++)
            dp[i][2] = dp[i][3] = 0, dp[i][1] = 1;

        dfs (1);
        printf ("%d\n", min (dp[1][1], dp[1][2]));
    }
    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

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 6;

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

struct Node

{

int v, w, next;

};

Node edge[maxn];

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

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

void Init ()

{

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

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

edgelen = 0;

}

//使用头插法构建

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

{

edge[edgelen].v = v;

edge[edgelen].w = w;

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

head[u] = edgelen++;

}

bool vis[maxn];

int dp[maxn][6];

void dfs (int rt)

{

vis[rt] = true;

bool is_valid = true;

int tt = INF;

for (int i = head[rt]; i != -1; i = edge[i].next)

{

if (!vis[edge[i].v])

{

dfs (edge[i].v);

dp[rt][1] += min (dp[edge[i].v][1], min (dp[edge[i].v][2], dp[edge[i].v][3]));

dp[rt][3] += min (dp[edge[i].v][1], dp[edge[i].v][2]);

if (dp[edge[i].v][1] <= dp[edge[i].v][2])

{

dp[rt][2] += dp[edge[i].v][1];

is_valid = false;

}

else

{

dp[rt][2] += dp[edge[i].v][2];

tt = min (tt, dp[edge[i].v][1] - dp[edge[i].v][2]);

}

if (is_valid)

dp[rt][2] += tt;

}

int main()

{

// CFF;

int n;

while (scanf ("%d", &n) != EOF)

{

Init ();

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

{

int u, v;

scanf ("%d%d", &u, &v);

AddEdge (u, v, 1);

AddEdge (v, u, 1);

}

memset (vis, false, sizeof (vis));

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

dp[i][2] = dp[i][3] = 0, dp[i][1] = 1;

dfs (1);

printf ("%d\n", min (dp[1][1], dp[1][2]));

}

return 0;

}

poj1463

maksyuki 发表于 oj 分类，标签: DP-树形DP, 图论-最小点覆盖

22 9月 2015

Strategic game

Bob enjoys playing computer games, especially strategic games, but sometimes he cannot find the solution fast enough and then he is very sad. Now he has the following problem. He must defend a 阅读全文 »

ural1018

maksyuki 发表于 oj 分类，标签: DP-树形DP

22 9月 2015

1018. Binary Apple Tree

Let's imagine how apple tree looks in binary computer world. You're right, it looks just like a binary tree, i.e. any biparous branch splits up to exactly two new branches. We will enumerate by integers the root of binary apple tree, points of branching and the ends of twigs. This way we may distinguish different branches by their ending points. We will assume that root of tree always is numbered by 1 and all numbers used for enumerating are numbered in range from 1 to N, where N is the total number of all enumerated points. For instance in the picture below N is equal to 5. Here is an example of an enumerated tree with four branches:

InputAs you may know it's not convenient to pick an apples from a tree when there are too much of branches. That's why some of them should be removed from a tree. But you are interested in removing branches in the way of minimal loss of apples. So your are given amounts of apples on a branches and amount of branches that should be preserved. Your task is to determine how many apples can remain on a tree after removing of excessive branches.

First line of input contains two numbers: N and Q (2 ≤ N ≤ 100; 1 ≤ Q ≤ N − 1). N denotes the number of enumerated points in a tree. Q denotes amount of branches that should be preserved. NextN − 1 lines contains descriptions of branches. Each description consists of a three integer numbers divided by spaces. The first two of them define branch by it's ending points. The third number defines the number of apples on this branch. You may assume that no branch contains more than 30000 apples.

Output

Output should contain the only number — amount of apples that can be preserved. And don't forget to preserve tree's root 😉

Sample

input

output

5 21 3 11 4 10

2 3 20

3 5 20

题目类型：树形DP

算法分析：dp[i][j]表示以i为根的子树恰好保留j个分支所具有的最多苹果数量，初始化dp全为0。最后直接输出dp[1][m]即可，其中m为保留的分支的个数。状态转移方程为：dp[u][i] = max (dp[u][i], dp[u][i-k] + dp[v][k-1] + w)，其中v为u的子节点，w为u-v这条边上的苹果数

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl

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

int dp[maxn][maxn];
bool vis[maxn];
int n, m;

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

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

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

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

void dfs (int rt)
{
    vis[rt] = true;
    for (int i = head[rt]; i != -1; i = edge[i].next)
    {
        if (vis[edge[i].v])
            continue;

        dfs (edge[i].v);
        for (int j = m; j >= 1; j--)
            for (int k = 1; k <= j; k++)
                dp[rt][j] = max (dp[rt][j], dp[rt][j-k] + dp[edge[i].v][k-1] + edge[i].w);
    }
}

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

        memset (vis, false, sizeof (vis));
        memset (dp, 0, sizeof (dp));
        dfs (1);
        cout << dp[1][m] << endl;
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 100 + 66;

int dp[maxn][maxn];

bool vis[maxn];

int n, m;

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

struct Node

{

int v, w, next;

};

Node edge[maxn*maxn];

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

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

void Init ()

{

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

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

edgelen = 0;

}

//使用头插法构建

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

{

edge[edgelen].v = v;

edge[edgelen].w = w;

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

head[u] = edgelen++;

}

void dfs (int rt)

{

vis[rt] = true;

for (int i = head[rt]; i != -1; i = edge[i].next)

{

if (vis[edge[i].v])

continue;

dfs (edge[i].v);

for (int j = m; j >= 1; j--)

for (int k = 1; k <= j; k++)

dp[rt][j] = max (dp[rt][j], dp[rt][j-k] + dp[edge[i].v][k-1] + edge[i].w);

}

int main()

{

// CPPFF;

while (cin >> n >> m)

{

int u, v, w;

Init();

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

{

cin >> u >> v >> w;

AddEdge (u, v, w);

AddEdge (v, u, w);

}

memset (vis, false, sizeof (vis));

memset (dp, 0, sizeof (dp));

dfs (1);

cout << dp[1][m] << endl;

}

return 0;

}

poj2063

maksyuki 发表于 oj 分类，标签: DP-背包

22 9月 2015

Investment

John never knew he had a grand-uncle, until he received the notary's letter. He learned that his late grand-uncle had gathered a lot of money, somewhere in South-America, and that John was the only inheritor.
John did not need that much money for the moment. But he realized that it would be a good idea to store this capital in a safe place, and have it grow until he decided to retire. The bank convinced him that a certain kind of bond was interesting for him.
This kind of bond has a fixed value, and gives a fixed amount of yearly interest, payed to the owner at the end of each year. The bond has no fixed term. Bonds are available in different sizes. The larger ones usually give a better interest. Soon John realized that the optimal set of bonds to buy was not trivial to figure out. Moreover, after a few years his capital would have grown, and the schedule had to be re-evaluated.
Assume the following bonds are available:

Value	Annual interest
4000 3000	400 250

With a capital of e10 000 one could buy two bonds of $4 000, giving a yearly interest of $800. Buying two bonds of $3 000, and one of $4 000 is a better idea, as it gives a yearly interest of $900. After two years the capital has grown to $11 800, and it makes sense to sell a $3 000 one and buy a $4 000 one, so the annual interest grows to $1 050. This is where this story grows unlikely: the bank does not charge for buying and selling bonds. Next year the total sum is $12 850, which allows for three times $4 000, giving a yearly interest of $1 200.
Here is your problem: given an amount to begin with, a number of years, and a set of bonds with their values and interests, find out how big the amount may grow in the given period, using the best schedule for buying and selling bonds.

Input

The first line contains a single positive integer N which is the number of test cases. The test cases follow.
The first line of a test case contains two positive integers: the amount to start with (at most $1 000 000), and the number of years the capital may grow (at most 40).
The following line contains a single number: the number d (1 <= d <= 10) of available bonds.
The next d lines each contain the description of a bond. The description of a bond consists of two positive integers: the value of the bond, and the yearly interest for that bond. The value of a bond is always a multiple of $1 000. The interest of a bond is never more than 10% of its value.

Output

For each test case, output – on a separate line – the capital at the end of the period, after an optimal schedule of buying and selling.

Sample Input

1
10000 4
2
4000 400
3000 250

Sample Output

14050

Source

Northwestern Europe 2004

题目类型：完全背包

算法分析：直接使用d次完全背包求解即可，注意此时题目已经给出所有的股票的值都是1000的倍数，所以此时要将股票的值除上1000，这样才能优化时间复杂度！！！

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl

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

int v[66], w[66], dp[maxn];


int main()
{
//    CFF;
    int t;
    scanf ("%d", &t);

    while (t--)
    {
        int V, d, n;
        scanf ("%d%d%d", &V, &d, &n);
        for (int i = 1; i <= n; i++)
        {
            scanf ("%d%d", &v[i], &w[i]);
            v[i] /= 1000;
        }

        int maxval;
        for (int i = 1; i <= d; i++)
        {
            memset (dp, 0, sizeof (dp));
            for (int j = 1; j <= n; j++)
                for (int k = v[j]; k <= V / 1000; k++)
                    dp[k] = max (dp[k], dp[k-v[j]] + w[j]);

            maxval = -INF;
            for (int i = 0; i <= V / 1000; i++)
                maxval = max (maxval, dp[i]);

            V += maxval;
        }
        printf ("%d\n", V);
    }
    return 0;
}

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 3e5 + 66;

int v[66], w[66], dp[maxn];

int main()

{

// CFF;

int t;

scanf ("%d", &t);

while (t--)

{

int V, d, n;

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

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

{

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

v[i] /= 1000;

}

int maxval;

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

{

memset (dp, 0, sizeof (dp));

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

for (int k = v[j]; k <= V / 1000; k++)

dp[k] = max (dp[k], dp[k-v[j]] + w[j]);

maxval = -INF;

for (int i = 0; i <= V / 1000; i++)

maxval = max (maxval, dp[i]);

V += maxval;

}

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

}

return 0;

}

poj1014

maksyuki 发表于 oj 分类，标签: DP-背包

20 9月 2015

Dividing

Marsha and Bill own a collection of marbles. They want to split the collection among themselves so that both receive an equal share of the marbles. This would be easy if all the marbles had the same value, because then they could just split the collection in half. But unfortunately, some of the marbles are larger, or more beautiful than others. So, Marsha and Bill start by assigning a value, a natural number between one and six, to each marble. Now they want to divide the marbles so that each of them gets the same total value. Unfortunately, they realize that it might be impossible to divide the marbles in this way (even if the total value of all marbles is even). For example, if there are one marble of value 1, one of value 3 and two of value 4, then they cannot be split into sets of equal value. So, they ask you to write a program that checks whether there is a fair partition of the marbles.

Input

Each line in the input file describes one collection of marbles to be divided. The lines contain six non-negative integers n1 , . . . , n6 , where ni is the number of marbles of value i. So, the example from above would be described by the input-line "1 0 1 2 0 0". The maximum total number of marbles will be 20000.
The last line of the input file will be "0 0 0 0 0 0"; do not process this line.

Output

For each collection, output "Collection #k:", where k is the number of the test case, and then either "Can be divided." or "Can't be divided.".
Output a blank line after each test case.

Sample Input

1 0 1 2 0 0
1 0 0 0 1 1
0 0 0 0 0 0

Sample Output

Collection #1:

Can't be divided.

Collection #2:

Can be divided.

Source

Mid-Central European Regional Contest 1999

题目类型：多重背包

算法分析：使用dp[i]表示恰好组成体积i时所具有的最大价值，递推方程为dp[i] = max (dp[i], dp[i-w[i]] + w[i])，初始化为dp[0] = 0，其他都为-1，最后判断dp[v] == v是否成立即可

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl

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

//c[i]表示第i个物品的花费 w[i]表示第i个物品的价值
//m[i]表示第i个物品的数量 dp[i]表示前i物品组成的最大价值
int c[maxn], w[maxn], m[maxn], dp[maxn];
int V, N;//分别表示背包的总体积和可选的物品的种数

void ZeroOnePack (int c, int w)
{
    for (int i = V; i >= c; i--)
        dp[i] = max (dp[i], dp[i-c] + w);
}

void CompletePack (int c, int w)
{
    for (int i = c; i <= V; i++)
        dp[i] = max (dp[i], dp[i-c] + w);
}

void MultiPack (int c, int w, int m)
{
    if (c * m >= V)
    {
        CompletePack (c, w);
        return ;
    }

    int k = 1;
    while (k < m)
    {
        ZeroOnePack (k * c, k * w);
        m -= k;
        k *= 2;
    }
    ZeroOnePack (m * c, m * w);
}

void Solve ()//可依照题目变化，这里表示背包不需要装满，如果只有dp[0]赋值为0，则表示恰好装满时的最大价值
{
    memset (dp, -1, sizeof (dp));
    dp[0] = 0;
    for (int i = 1; i <= N; i++)
        MultiPack (c[i], w[i], m[i]);
}


int main()
{
//    CFF;
    N = 6;
    int flag = 1;
    while (scanf ("%d%d%d%d%d%d", &m[1], &m[2], &m[3], &m[4], &m[5], &m[6]) != EOF)
    {
        V = 0;
        for (int i = 1; i <= 6; i++)
        {
            V += i * m[i];
            c[i] = w[i] = i;
        }

        if (!V)
            break;

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

        if (V % 2) puts ("Can't be divided.\n");

        else
        {
            V /= 2;
            Solve ();

            if (dp[V] == V)
                puts ("Can be divided.\n");

            else
                puts ("Can't be divided.\n");
        }
    }
    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

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 2e6 + 66;

//c[i]表示第i个物品的花费 w[i]表示第i个物品的价值

//m[i]表示第i个物品的数量 dp[i]表示前i物品组成的最大价值

int c[maxn], w[maxn], m[maxn], dp[maxn];

int V, N;//分别表示背包的总体积和可选的物品的种数

void ZeroOnePack (int c, int w)

{

for (int i = V; i >= c; i--)

dp[i] = max (dp[i], dp[i-c] + w);

}

void CompletePack (int c, int w)

{

for (int i = c; i <= V; i++)

dp[i] = max (dp[i], dp[i-c] + w);

}

void MultiPack (int c, int w, int m)

{

if (c * m >= V)

{

CompletePack (c, w);

return ;

}

int k = 1;

while (k < m)

{

ZeroOnePack (k * c, k * w);

m -= k;

k *= 2;

}

ZeroOnePack (m * c, m * w);

}

void Solve ()//可依照题目变化，这里表示背包不需要装满，如果只有dp[0]赋值为0，则表示恰好装满时的最大价值

{

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

dp[0] = 0;

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

MultiPack (c[i], w[i], m[i]);

}

int main()

{

// CFF;

N = 6;

int flag = 1;

while (scanf ("%d%d%d%d%d%d", &m[1], &m[2], &m[3], &m[4], &m[5], &m[6]) != EOF)

{

V = 0;

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

{

V += i * m[i];

c[i] = w[i] = i;

}

if (!V)

break;

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

if (V % 2) puts ("Can't be divided.\n");

else

{

V /= 2;

Solve ();

if (dp[V] == V)

puts ("Can be divided.\n");

else

puts ("Can't be divided.\n");

}

return 0;

}

2015ACM-ICPC亚洲区北京站网赛(1/10)

maksyuki 发表于比赛分类，

20 9月 2015

H 描述

This is the logo of PKUACM 2016. More specifically, the logo is generated as follows:

Put four points A₀(0,0), B₀(0,1), C₀(1,1), D₀(1,0) on a cartesian coordinate system.
Link A₀B₀, B₀C₀, C₀D₀, D₀A₀separately, forming square A₀B₀C₀D₀.
Assume we have already generated square A_iB_iC_iD_i, then square A_i+1B_i+1C_i+1D_i+1is generated by linking the midpoints of A_iB_i, B_iC_i, C_iD_iand D_iA_isuccessively.
Repeat step three 1000 times.

Now the designer decides to add a vertical line x=k to this logo( 0<= k < 0.5, and for k, there will be at most 8 digits after the decimal point). He wants to know the number of common points between the new line and the original logo.

输入

In the first line there’s an integer T( T < 10,000), indicating the number of test cases.

Then T lines follow, each describing a test case. Each line contains an float number k, meaning that you should calculate the number of common points between line x = k and the logo.

输出

For each test case, print a line containing one integer indicating the answer. If there are infinity common points, print -1.

样例输入

0.375

0.001

0.478

样例输出

-1

题目类型：二分查找

算法分析：由题目可知内部的每个小正方形都可以看作是相对较大的正方形二分边得来的，此时可以对于每个输入的坐标在[0,0. 5)二分坐标值

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl

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

int PP (double val)
{
    double a = 0, b = 0.5, m;
    int res = 0;
    while (b - a > EPS)
    {
        m = (a + b) / 2;
        if (fabs (m - val) < EPS)
            return -1;

        else if (val + EPS < m)
        {
            res += 4;
            break;
        }

        else
        {
            res += 4;
            a = m;
        }
    }
    return res;
}

int main()
{
//    CPPFF;
    int t;
    cin >> t;
    while (t--)
    {
        double val;
        cin >> val;
        if (fabs (val - 0) < EPS)
            cout << "-1" << endl;

        else
            cout << PP (val) << endl;
    }
    return 0;
}

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 3e5 + 66;

int PP (double val)

{

double a = 0, b = 0.5, m;

int res = 0;

while (b - a > EPS)

{

m = (a + b) / 2;

if (fabs (m - val) < EPS)

return -1;

else if (val + EPS < m)

{

res += 4;

break;

}

else

{

res += 4;

a = m;

}

return res;

}

int main()

{

// CPPFF;

int t;

cin >> t;

while (t--)

{

double val;

cin >> val;

if (fabs (val - 0) < EPS)

cout << "-1" << endl;

else

cout << PP (val) << endl;

}

return 0;

}

BestCoder Round #56(Div.2) (0/4) (Div.1) (0/4)

maksyuki 发表于比赛分类，标签: 比赛-bestcoder

20 9月 2015

2015ACM-ICPC亚洲区沈阳站网赛(2/13)

maksyuki 发表于比赛分类，

19 9月 2015

J Jesus Is Here

Problem Description

I've sent Fang Fang around 201314 text messages in almost 5 years. Why can't she make sense of what I mean?
But Jesus is here!" the priest intoned. Show me your messages."
Fine, the first message is s1=‘‘c" and the second one is s2=‘‘ff".
The i-th message is si=si−2+si−1 afterwards. Let me give you some examples.
s3=‘‘cff", s4=‘‘ffcff" and s5=‘‘cffffcff".

I found the i-th message's utterly charming," Jesus said.
Look at the fifth message". s5=‘‘cffffcff" and two ‘‘cff" appear in it.
The distance between the first ‘‘cff" and the second one we said, is 5.
You are right, my friend," Jesus said. Love is patient, love is kind.
It does not envy, it does not boast, it is not proud. It does not dishonor others, it is not self-seeking, it is not easily angered, it keeps no record of wrongs.
Love does not delight in evil but rejoices with the truth.
It always protects, always trusts, always hopes, always perseveres."

Listen - look at him in the eye. I will find you, and count the sum of distance between each two different ‘‘cff" as substrings of the message.

Input

An integer T (1≤T≤100), indicating there are T test cases.
Following T lines, each line contain an integer n (3≤n≤201314), as the identifier of message.

Output

The output contains exactly T lines.
Each line contains an integer equaling to:

∑i<j:sn[i..i+2]=sn[j..j+2]=‘‘cff"(j−i) mod 530600414,

where sn as a string corresponding to the n-th message.

Sample Input

9
5
6
7
8
113
1205
199312
199401
201314

Sample Output

Case #1: 5
Case #2: 16
Case #3: 88
Case #4: 352
Case #5: 318505405
Case #6: 391786781
Case #7: 133875314
Case #8: 83347132
Case #9: 16520782

Source

2015 ACM/ICPC Asia Regional Shenyang Online

题目类型：线性DP

算法分析：使用dp[i]表示第i个序列中任意两个”cff”直接的距离和，则dp[i] = dp[i-2] + dp[i-1] + (第i - 2个序列与第i - 1个序列之间的距离和)，此时易知初始条件是dp[1] = dp[2] = 0。令Si表示第i个序列中的”c”到这个序列的前端的总距离和，Leni表示第i个序列的长度，Ki表示第i个序列中”c”的个数，则序列间距离和为：

Ki-1 * (Ki-2 * Leni-2 - Si-2) + Ki-2 * Si-1

而Ki、Leni、Si都可以递推出来，其中Si = Si-2 + Si-1 + Leni-1，在递推求解时要注意取模！！！而且如果出现求解两个数差的模的话，此时要注意加上一个MOD再对MOD取模！！！

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define DB(ccc) cout << #ccc << " = " << ccc << endl

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

LL dp[maxn], k[maxn], len[maxn], s[maxn];;

int main()
{
    dp[1] = dp[2] = 0;
    k[1] = 1, k[2] = 0, len[1] = 1, len[2] = 2, s[1] = 0, s[2] = 0;
    for (int i = 3; i < maxn; i++)
    {
        dp[i] = dp[i-2] % MOD + dp[i-1] % MOD + ((k[i-1] % MOD) * ((((k[i-2] % MOD) * (len[i-2] % MOD)) % MOD - s[i-2] % MOD + MOD) % MOD)) % MOD +
        (k[i-2] % MOD) * (s[i-1] % MOD) % MOD;
        dp[i] %= MOD;
        s[i] = s[i-2] + s[i-1] + k[i-1] * len[i-2];
        s[i] %= MOD;
        k[i] = k[i-2] + k[i-1];
        k[i] %= MOD;
        len[i] = len[i-2] + len[i-1];
        len[i] %= MOD;
    }

//    CPPFF;
    int t, flag = 1;

    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        cout << "Case #" << flag++ << ": " << dp[n] <<endl;
    }
    return 0;
}

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const LL MOD = 530600414;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 2e5 + 6666;

LL dp[maxn], k[maxn], len[maxn], s[maxn];;

int main()

{

dp[1] = dp[2] = 0;

k[1] = 1, k[2] = 0, len[1] = 1, len[2] = 2, s[1] = 0, s[2] = 0;

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

{

dp[i] = dp[i-2] % MOD + dp[i-1] % MOD + ((k[i-1] % MOD) * ((((k[i-2] % MOD) * (len[i-2] % MOD)) % MOD - s[i-2] % MOD + MOD) % MOD)) % MOD +

(k[i-2] % MOD) * (s[i-1] % MOD) % MOD;

dp[i] %= MOD;

s[i] = s[i-2] + s[i-1] + k[i-1] * len[i-2];

s[i] %= MOD;

k[i] = k[i-2] + k[i-1];

k[i] %= MOD;

len[i] = len[i-2] + len[i-1];

len[i] %= MOD;

}

// CPPFF;

int t, flag = 1;

cin >> t;

while (t--)

{

int n;

cin >> n;

cout << "Case #" << flag++ << ": " << dp[n] <<endl;

}

return 0;

}

L Largest Point

Problem Description

Given the sequence A with n integers t1,t2,⋯,tn. Given the integral coefficients a and b. The fact that select two elements ti and tj of A and i≠j to maximize the value of at2i+btj, becomes the largest point.

Input

An positive integer T, indicating there are T test cases.
For each test case, the first line contains three integers corresponding to n (2≤n≤5×106), a (0≤|a|≤106) and b (0≤|b|≤106). The second line contains nintegers t1,t2,⋯,tn where 0≤|ti|≤106 for 1≤i≤n.

The sum of n for all cases would not be larger than 5×106.

Output

The output contains exactly T lines.
For each test case, you should output the maximum value of at2i+btj.

Sample Input

3 2 1
1 2 3

5 -1 0
-3 -3 0 3 3

Sample Output

Case #1: 20

Case #2: 0

Source

2015 ACM/ICPC Asia Regional Shenyang Online

题目类型：排序+枚举

算法分析：先将a* i ^ 2和b * i的值求出来，然后分别对点按照值从大到小排序，最后判断一次两个数组(分别存a*i^2和b*i的值)的第一个元素和第二个元素的值的相对大小关系，输出相对较大的那个值

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define DB(ccc) cout << #ccc << " = " << ccc << endl

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

struct node
{
    LL v, id;
};

node aa[maxn], bb[maxn];

bool cmp (node aa, node bb)
{
    return aa.v > bb.v;
}


int main()
{
 //   CFF;
    int t;
    int flag = 1;
    scanf ("%d",&t);

    while (t--)
    {
        printf ("Case #%d: ", flag++);
        LL a, b, n;
        scanf ("%lld%lld%lld", &n, &a, &b);

        for (int i = 1; i <= n; i++)
        {
            LL v;
            scanf ("%lld", &v);
            aa[i].v = a * v * v;
            aa[i].id = i;
            bb[i].v = b * v;
            bb[i].id = i;
        }

        sort (aa + 1, aa + 1 + n, cmp);
        sort (bb + 1, bb + 1 + n, cmp);

        if (aa[1].id != bb[1].id)
            printf ("%lld\n", aa[1].v + bb[1].v);

        else
        {
            LL ta = aa[1].v + bb[2].v;
            LL tb = aa[2].v + bb[1].v;
            printf ("%lld\n", max (ta, tb));
        }
    }
    return 0;
}

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 5e6 + 66;

struct node

{

LL v, id;

};

node aa[maxn], bb[maxn];

bool cmp (node aa, node bb)

{

return aa.v > bb.v;

}

int main()

{

// CFF;

int t;

int flag = 1;

scanf ("%d",&t);

while (t--)

{

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

LL a, b, n;

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

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

{

LL v;

scanf ("%lld", &v);

aa[i].v = a * v * v;

aa[i].id = i;

bb[i].v = b * v;

bb[i].id = i;

}

sort (aa + 1, aa + 1 + n, cmp);

sort (bb + 1, bb + 1 + n, cmp);

if (aa[1].id != bb[1].id)

printf ("%lld\n", aa[1].v + bb[1].v);

else

{

LL ta = aa[1].v + bb[2].v;

LL tb = aa[2].v + bb[1].v;

printf ("%lld\n", max (ta, tb));

}

return 0;

}

hdu2795

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

18 9月 2015

Billboard

Problem Description

At the entrance to the university, there is a huge rectangular billboard of size h*w (h is its height and w is its width). The board is the place where all possible announcements are posted: nearest programming competitions, changes in the dining room menu, and other important information.
On September 1, the billboard was empty. One by one, the announcements started being put on the billboard. Each announcement is a stripe of paper of unit height. More specifically, the i-th announcement is a rectangle of size 1 * wi. When someone puts a new announcement on the billboard, she would always choose the topmost possible position for the announcement. Among all possible topmost positions she would always choose the leftmost one. If there is no valid location for a new announcement, it is not put on the billboard (that's why some programming contests have no participants from this university). Given the sizes of the billboard and the announcements, your task is to find the numbers of rows in which the announcements are placed.

Input

There are multiple cases (no more than 40 cases). The first line of the input file contains three integer numbers, h, w, and n (1 <= h,w <= 10^9; 1 <= n <= 200,000) - the dimensions of the billboard and the number of announcements. Each of the next n lines contains an integer number wi (1 <= wi <= 10^9) - the width of i-th announcement.

Output

For each announcement (in the order they are given in the input file) output one number - the number of the row in which this announcement is placed. Rows are numbered from 1 to h, starting with the top row. If an announcement can't be put on the billboard, output "-1" for this announcement.

Sample Input

3 5 5
2
4
3
3
3

Sample Output

-1

Author

hhanger@zju

Source

HDOJ 2009 Summer Exercise（5）

题目类型：线段树+离散化

算法分析：n的规模只有2e5，则易知线段树中的点的个数最多也就是n的。然后将wi插入到树中，然后更新最值即可，线段树的插入操作本身就能够保证当前wi是插入到符合的位置上的

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl

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

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


LL maxval[maxn<<2];

void PushUp (int rt)
{
    maxval[rt] = max (maxval[rt<<1], maxval[rt<<1|1]);
}

LL Query (int rt, int l, int r, int v)
{
    if (l == r)
    {
        maxval[rt] -= v;
        return l;
    }

    int m = (l + r) >> 1;
    LL tt;
    if (v <= maxval[rt<<1])
        tt = Query (lson, v);

    else
        tt = Query (rson, v);

    PushUp (rt);
    return tt;
}


int main()
{
//    CPPFF;
    int h, w, q;
    while (scanf ("%d%d%d", &h, &w, &q) != EOF)
    {
        fill (maxval, maxval + (maxn << 2), w);
        if (h > q) h = q;

        for (int i = 1; i <= q; i++)
        {
            int wi;
            scanf ("%d", &wi);
            if (wi > maxval[1]) puts ("-1");

            else
                printf ("%lld\n", Query (1, 1, h, wi));
        }
    }
    return 0;
}

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

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

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

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 2e5 + 66;

#define lson rt << 1, l, m

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

LL maxval[maxn<<2];

void PushUp (int rt)

{

maxval[rt] = max (maxval[rt<<1], maxval[rt<<1|1]);

}

LL Query (int rt, int l, int r, int v)

{

if (l == r)

{

maxval[rt] -= v;

return l;

}

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

LL tt;

if (v <= maxval[rt<<1])

tt = Query (lson, v);

else

tt = Query (rson, v);

PushUp (rt);

return tt;

}

int main()

{

// CPPFF;

int h, w, q;

while (scanf ("%d%d%d", &h, &w, &q) != EOF)

{

fill (maxval, maxval + (maxn << 2), w);

if (h > q) h = q;

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

{

int wi;

scanf ("%d", &wi);

if (wi > maxval[1]) puts ("-1");

else

printf ("%lld\n", Query (1, 1, h, wi));

}

return 0;

}

1 2 3 4 5 下一页最后一页

超客的水墨烟雨

Codeforces Round #322(Div.2) (4/6)

2015ACM-ICPC亚洲区合肥站网赛(0/10)

BestCoder Round #57(Div.2) (2/4) (Div.1) (1/4)

Scaena Felix

2015ACM-ICPC亚洲区上海站网赛(0/11)

Codeforces Round #321(Div.2) (2/5)

bzoj1087

1087: [SCOI2005]互不侵犯King

Input

poj2385

poj3659

poj1463

ural1018

1018. Binary Apple Tree

Output

Sample

poj2063

poj1014

2015ACM-ICPC亚洲区北京站网赛(1/10)

H 描述

输入

输出

BestCoder Round #56(Div.2) (0/4) (Div.1) (0/4)

2015ACM-ICPC亚洲区沈阳站网赛(2/13)

J Jesus Is Here

L Largest Point

hdu2795

Billboard

分类目录

标签云

书签

近期评论

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