Good Bye 2014 A B C

A. New Year Transportation

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

New Year is coming in Line World! In this world, there are _n_ cells numbered
by integers from 1 to _n_ , as a 1 × _n_ board. People live in cells.
However, it was hard to move between distinct cells, because of the difficulty
of escaping the cell. People wanted to meet people who live in other cells.

So, user tncks0121 has made a transportation system to move between these
cells, to celebrate the New Year. First, he thought of _n_ - 1 positive
integers _a_ 1 , _a_ 2 , …, _a_ _n_ - 1 . For every integer _i_ where
1 ≤ _i_ ≤ _n_ - 1 the condition 1 ≤ _a_ _i_ ≤ _n_ - _i_ holds. Next, he
made _n_ - 1 portals, numbered by integers from 1 to _n_ - 1 . The _i_
-th ( 1 ≤ _i_ ≤ _n_ - 1 ) portal connects cell _i_ and cell ( _i_ + _a_
_i_ ) , and one can travel from cell _i_ to cell ( _i_ + _a_ _i_ ) using
the _i_ -th portal. Unfortunately, one cannot use the portal backwards, which
means one cannot move from cell ( _i_ + _a_ _i_ ) to cell _i_ using the
_i_ -th portal. It is easy to see that because of condition 1 ≤ _a_ _i_ ≤ _n_
- _i_ one can’t leave the Line World using portals.

Currently, I am standing at cell 1 , and I want to go to cell _t_ .
However, I don’t know whether it is possible to go there. Please determine
whether I can go to cell _t_ by only using the construted transportation
system.

Input

The first line contains two space-separated integers _n_ ( 3 ≤ _n_ ≤ 3 × 10
4 ) and _t_ ( 2 ≤ _t_ ≤ _n_ ) — the number of cells, and the index of the
cell which I want to go to.

The second line contains _n_ - 1 space-separated integers _a_ 1 , _a_ 2 ,
…, _a_ _n_ - 1 ( 1 ≤ _a_ _i_ ≤ _n_ - _i_ ). It is guaranteed, that using
the given transportation system, one cannot leave the Line World.

Output

If I can go to cell _t_ using the transportation system, print “ YES “.
Otherwise, print “ NO “.

Sample test(s)

input

8 4
1 2 1 2 1 2 1

output

YES

input

8 5
1 2 1 2 1 1 1

output

NO

Note

In the first sample, the visited cells are: 1, 2, 4 ; so we can successfully
visit the cell 4 .

In the second sample, the possible cells to visit are: 1, 2, 4, 6, 7, 8 ; so
we can’t visit the cell 5 , which we want to visit.

A 水题

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<sstream>
#include<time.h>
#include<utility>
#include<malloc.h>

using namespace std;

int n, t;

int p[30010];

int main()
{
    while (cin >> n >> t)
    {
        for (int i = 1; i <= n-1; i++)
            cin >> p[i];

        int pos = 1;

        for (int i = 1; i <= n-1;i++)
        {
            if (pos >= t)
                break;
            pos += p[pos];
        }
        if (pos == t)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

B. New Year Permutation

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

User ainta has a permutation _p_ 1 , _p_ 2 , …, _p_ _n_ . As the New Year
is coming, he wants to make his permutation as pretty as possible.

Permutation _a_ 1 , _a_ 2 , …, _a_ _n_ is prettier than permutation
_b_ 1 , _b_ 2 , …, _b_ _n_ , if and only if there exists an integer _k_ (
1 ≤ _k_ ≤ _n_ ) where _a_ 1 = _b_ 1 , _a_ 2 = _b_ 2 , …, _a_ _k_ - 1 =
_b_ _k_ - 1 and _a_ _k_ < _b_ _k_ all holds.

As known, permutation _p_ is so sensitive that it could be only modified by
swapping two distinct elements. But swapping two elements is harder than you
think. Given an _n_ × _n_ binary matrix _A_ , user ainta can swap the values
of _p_ _i_ and _p_ _j_ ( 1 ≤ _i_ , _j_ ≤ _n_ , _i_ ≠ _j_ ) if and only if
_A_ _i_ , _j_ = 1 .

Given the permutation _p_ and the matrix _A_ , user ainta wants to know the
prettiest permutation that he can obtain.

Input

The first line contains an integer _n_ ( 1 ≤ _n_ ≤ 300 ) — the size of the
permutation _p_ .

The second line contains _n_ space-separated integers _p_ 1 , _p_ 2 , …,
_p_ _n_ — the permutation _p_ that user ainta has. Each integer between 1
and _n_ occurs exactly once in the given permutation.

Next _n_ lines describe the matrix _A_ . The _i_ -th line contains _n_
characters ‘ 0 ‘ or ‘ 1 ‘ and describes the _i_ -th row of _A_ . The
_j_ -th character of the _i_ -th line _A_ _i_ , _j_ is the element on the
intersection of the _i_ -th row and the _j_ -th column of A. It is
guaranteed that, for all integers _i_ , _j_ where 1 ≤ _i_ < _j_ ≤ _n_ , _A_
_i_ , _j_ = _A_ _j_ , _i_ holds. Also, for all integers _i_ where 1 ≤ _i_ ≤
_n_ , _A_ _i_ , _i_ = 0 holds.

Output

In the first and only line, print _n_ space-separated integers, describing
the prettiest permutation that can be obtained.

Sample test(s)

input

7
5 2 4 3 6 7 1
0001001
0000000
0000010
1000001
0000000
0010000
1001000

output

1 2 4 3 6 7 5

input

output

1 2 3 4 5

Note

In the first sample, the swap needed to obtain the prettiest permutation is:
( _p_ 1 , _p_ 7 ) .

In the second sample, the swaps needed to obtain the prettiest permutation is
( _p_ 1 , _p_ 3 ), ( _p_ 4 , _p_ 5 ), ( _p_ 3 , _p_ 4 ) .

A permutation _p_ is a sequence of integers _p_ 1 , _p_ 2 , …, _p_ _n_
, consisting of _n_ distinct positive integers, each of them doesn’t exceed
_n_ . The _i_ -th element of the permutation _p_ is denoted as _p_ _i_ .
The size of the permutation _p_ is denoted as _n_ .

B 弗洛伊德算法，并查集也可以做，有时间敲一下。

#include <iostream>  
#include <stdio.h>  
#include <math.h>  
#include <algorithm>  
#include <string.h>  

using namespace std;

int p[305];
int b[305][305];

int n;

int main()
{
    while (cin >> n)
    {
        for (int i = 1; i <= n; i++)
            cin >> p[i];
        getchar();
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                char c = getchar();
                b[i][j] = (c == '1');
            }
            getchar();
        }

        for (int k = 1; k <= n;k++)
            for (int  i= 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                {
                    if (b[i][k] & b[k][j])
                    {
                        b[i][j] = b[j][i] = 1;
                    }
                }

        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
            {
                if (b[i][j] )
                {
                    if (p[i] > p[j])
                    {
                        swap(p[i],p[j]);
                    }
                }
            }
        for (int i = 1; i <= n; i++)
            cout << p[i] << " ";
    }
    return 0;
}

C. New Year Book Reading

New Year is coming, and Jaehyun decided to read many books during 2015, unlike
this year. He has _n_ books numbered by integers from 1 to _n_ . The weight
of the _i_ -th ( 1 ≤ _i_ ≤ _n_ ) book is _w_ _i_ .

As Jaehyun’s house is not large enough to have a bookshelf, he keeps the _n_
books by stacking them vertically. When he wants to read a certain book _x_ ,
he follows the steps described below.

He lifts all the books above book _x_ .
He pushes book _x_ out of the stack.
He puts down the lifted books without changing their order.
After reading book _x_ , he puts book _x_ on the top of the stack.

He decided to read books for _m_ days. In the _j_ -th ( 1 ≤ _j_ ≤ _m_ )
day, he will read the book that is numbered with integer _b_ _j_ ( 1 ≤ _b_
_j_ ≤ _n_ ). To read the book, he has to use the process described in the
paragraph above. It is possible that he decides to re-read the same book
several times.

After making this plan, he realized that the total weight of books he should
lift during _m_ days would be too heavy. So, he decided to change the order
of the stacked books before the New Year comes, and minimize the total weight.
You may assume that books can be stacked in any possible order. Note that book
that he is going to read on certain step isn’t considered as lifted on that
step. Can you help him?

Input

The first line contains two space-separated integers _n_ ( 2 ≤ _n_ ≤ 500 )
and _m_ ( 1 ≤ _m_ ≤ 1000 ) — the number of books, and the number of days
for which Jaehyun would read books.

The second line contains _n_ space-separated integers _w_ 1 , _w_ 2 , …,
_w_ _n_ ( 1 ≤ _w_ _i_ ≤ 100 ) — the weight of each book.

The third line contains _m_ space separated integers _b_ 1 , _b_ 2 , …,
_b_ _m_ ( 1 ≤ _b_ _j_ ≤ _n_ ) — the order of books that he would read. Note
that he can read the same book more than once.

Output

Print the minimum total weight of books he should lift , which can be
achieved by rearranging the order of stacked books.

Sample test(s)

Input

3 5
1 2 3
1 3 2 3 1

Output

Note

Here’s a picture depicting the example. Each vertical column presents the
stacked books.

贪心后模拟。

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<sstream>
#include<time.h>
#include<utility>
#include<malloc.h>

using namespace std;

int n, m;
int p[510];
int q[1010], qq[1010];
int vis[1010];

int main()
{
    while (cin >> n >> m)
    {
        for (int i = 1; i <= n; i++)
        {
            cin >> p[i];
        }

        memset(vis,0,sizeof(vis));

        int pos = 1;
        for (int i = 1; i <= m; i++)
        {
            int jjq;
            cin >> jjq;
            q[i] = jjq;
            if (!vis[jjq])
            {
                qq[pos++] = jjq;
                vis[jjq] = 1;
            }
        }

        long long ans = 0;
        for (int i = 1; i <= m; i++)
        {
            int tt = q[i];
            for (int j = 1; j <= n; j++)
            {
                if (qq[j] != tt)
                {
                    ans += p[qq[j]];
                }
                else 
                {
                    for (int k = j; k > 1 ; k--)
                    {
                        qq[k] = qq[k-1];
                    }
                    qq[1] = tt;
                    break;
                }
            }
        }

        cout << ans << endl;
    }
    return 0;
}