Codeforces Round #292 (Div. 2)。

现在的位置: 首页 > 综合 > 正文

Codeforces Round #292 (Div. 2)。

2018年04月28日 ⁄ 综合 ⁄ 共 9159字 ⁄ 字号小中大 ⁄ 评论关闭

A题：

Someday, Drazil wanted to go on date with Varda. Drazil and Varda live on Cartesian plane. Drazil's home is located in point(0, 0) and Varda's home is located in
point (a, b). In each step, he can move in a unit distance in horizontal or vertical direction. In other words, from position (x, y) he
can go to positions (x + 1, y), (x - 1, y), (x, y + 1) or (x, y - 1).

Unfortunately, Drazil doesn't have sense of direction. So he randomly chooses the direction he will go to in each step. He may accidentally return back to his house during his travel. Drazil may even not notice that he has arrived to (a, b) and
continue travelling.

Luckily, Drazil arrived to the position (a, b) successfully. Drazil said to Varda: "It took me exactly s steps
to travel from my house to yours". But Varda is confused about his words, she is not sure that it is possible to get from (0, 0) to (a, b) in
exactlys steps. Can you find out if it is possible for Varda?

Input

You are given three integers a, b, and s ( - 109 ≤ a, b ≤ 109, 1 ≤ s ≤ 2·109)
in a single line.

Output

If you think Drazil made a mistake and it is impossible to take exactly s steps and get from his home to Varda's home, print "No" (without quotes).

Otherwise, print "Yes".

Sample test(s)

input
5 5 11

output
No

input
10 15 25

output
Yes

input
0 5 1

output
No

input
0 0 2

output
Yes

Note

In fourth sample case one possible route is: $\text{[math]}$ .

A题其实是为了上来镇定下，而我一开始还没拿到分，，，连续两次WA，第一次是上来就枚举了所以x,y的情况，主要把他们和0比大小，然后和自身比大小，最后果断跪在第五组数据。。。。

想明白后，，忘记加了abs，，又一次WA,第三次，加上abs，终于过了。。。

也就是说，从（0,0）走，开始走到（x,y）这个点后，可以在这个点的周围乱走，只要乱走的步数为偶数步，那么最终一定可以回到(x,y)的

代码：

# include<cstdio>
# include<iostream>
# include<cmath>

using namespace std;

int main(void)
{
    long long x,y;
    long long  step;
    while ( cin>>x>>y>>step )
    {
        long long  ans = step-abs(x)-abs(y);
        if ( ans < 0 )
        {
            cout<<"No"<<endl;
        }
        else
        {
            if ( ans%2==0 )
            {
                cout<<"Yes"<<endl;
            }
            else
            {
                cout<<"No"<<endl;
            }
        }
    }


    return 0;
}

B题：

Drazil has many friends. Some of them are happy and some of them are unhappy. Drazil wants to make all his friends become happy. So he invented the following plan.

There are n boys and m girls among his friends.
Let's number them from 0 to n - 1 and 0 to m - 1 separately.
In i-th day, Drazil invites $\text{[math]}$ -th
boy and $\text{[math]}$ -th
girl to have dinner together (as Drazil is programmer, i starts from 0).
If one of those two people is happy, the other one will also become happy. Otherwise, those two people remain in their states. Once a person becomes happy (or if he/she was happy originally), he stays happy forever.

Drazil wants to know whether he can use this plan to make all his friends become happy at some moment.

Input

The first line contains two integer n and m (1 ≤ n, m ≤ 100).

The second line contains integer b (0 ≤ b ≤ n),
denoting the number of happy boys among friends of Drazil, and then follow bdistinct integers x1, x2, ..., xb (0 ≤ xi < n),
denoting the list of indices of happy boys.

The third line conatins integer g (0 ≤ g ≤ m),
denoting the number of happy girls among friends of Drazil, and then follow gdistinct integers y1, y2, ...
, yg (0 ≤ yj < m),
denoting the list of indices of happy girls.

It is guaranteed that there is at least one person that is unhappy among his friends.

Output

If Drazil can make all his friends become happy by this plan, print "Yes". Otherwise, print "No".

Sample test(s)

input
2 3
0
1 0

output
Yes

input
2 4
1 0
1 2

output
No

input
2 3
1 0
1 1

output
Yes

Note

By $\text{[math]}$ we
define the remainder of integer division of i by k.

In first sample case:

On the 0-th day, Drazil invites 0-th boy and 0-th girl. Because 0-th girl is happy at the beginning, 0-th boy become happy at this day.
On the 1-st day, Drazil invites 1-st boy and 1-st girl. They are both unhappy, so nothing changes at this day.
On the 2-nd day, Drazil invites 0-th boy and 2-nd girl. Because 0-th boy is already happy he makes 2-nd girl become happy at this day.
On the 3-rd day, Drazil invites 1-st boy and 0-th girl. 0-th girl is happy, so she makes 1-st boy happy.
On the 4-th day, Drazil invites 0-th boy and 1-st girl. 0-th boy is happy, so he makes the 1-st girl happy. So, all friends become happy at this moment.

解题思路：

这道题写个暴力就水过去了，Q神告诉我开1000*1000*10的。。然后，我就照着做了，其实开小点也是可以水过去的。因为n和m都是小于等于100的,那么我们只要寻求最大的流动周期就ok了。。

代码：

# include<cstdio>
# include<iostream>
# include<cstring>

using namespace std;

# define MAX 100

int bb[MAX];
int gg[MAX];

int main(void)
{
    int n,m;
    int b,g;
    while ( cin>>n>>m )
    {
        memset(bb,0,sizeof(bb));
        memset(gg,0,sizeof(gg));
        cin>>b;
        for ( int i = 0;i < b;i++ )
        {
            int t;cin>>t;
            bb[t] = 1;
        }
        cin>>g;
        for ( int i = 0;i < g;i++ )
        {
            int t;cin>>t;
            gg[t] = 1;
        }

        for ( int i = 0;i <= 10000000;i++ )
        {
            if ( bb[i%n]+gg[i%m] >= 1 )
            {
                bb[i%n] = 1;
                gg[i%m] = 1;
            }
        }
        int sum1 = 0;
        int sum2=  0;
        for ( int i = 0;i < n;i++ )
        {
            if ( bb[i]==1 )
                sum1++;
        }
        for ( int i = 0;i < m;i++ )
        {
                if ( gg[i]==1 )
                sum2++;
        }
        if ( sum1==n&&sum2==m )
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl;
        }


    }


    return 0;
}

C题：

Drazil is playing a math game with Varda.

Let's define $\text{[math]}$ for
positive integer x as a product of factorials of its digits. For example, $\text{[math]}$ .

First, they choose a decimal number a consisting of n digits
that contains at least one digit larger than 1. This number may possibly start with leading zeroes. Then they should find maximum positive number x satisfying
following two conditions:

1. x doesn't contain neither digit 0 nor digit 1.

2. $\text{[math]}$ = $\text{[math]}$ .

Help friends find such number.

Input

The first line contains an integer n (1 ≤ n ≤ 15)
— the number of digits in a.

The second line contains n digits of a. There
is at least one digit in a that is larger than 1. Number a may
possibly contain leading zeroes.

Output

Output a maximum possible integer satisfying the conditions above. There should be no zeroes and ones in this number decimal representation.

Sample test(s)

input
4
1234

output
33222

input
3
555

output
555

Note

In the first case, $\text{[math]}$

C题就是阶乘拆分问题，题目说的是，给你一个数字a，你把它的每一位分离出来，然后求阶乘，然后在乘起来，最后把这个结果分解为几个尽可能大的数字的组合，当然这个数字组起来也要大了，那么采取贪心的策略，尽可能的多把其他数字的阶乘分解掉2,3,5，7上面，依次枚举出来，比如说,2!=2!, 3！=3！，4！=3！*2！*2！，。。。

然后反过来输出就好了，一开始关于反向输出的问题，卡了好久，但是最后还是想到了~

代码：

# include<cstdio>
# include<iostream>

using namespace std;

int d[10];
char s[20];
int n;

void meiju()
{
    for ( int i = 0;i < n;i++ )
    {
        if (s[i] == '0' || s[i] == '1')
            continue;
        else if (s[i] == '2')
            d[2]++;
        else if (s[i] == '3')
            d[3]++;
        else if (s[i] == '4')
        {
            d[3]++;
            d[2] += 2;
        }
         else if (s[i] == '5')
            d[5]++;
        else if (s[i] == '6')
        {
            d[5]++; d[3]++;
        }
        else if (s[i] == '7')
            d[7]++;
        else if (s[i] == '8')
        {
            d[7]++;
            d[2] += 3;
        }
        else
        {
            d[7]++;
            d[3] += 2;
            d[2] += 1;
        }
    }
}

int main(void)
{
    cin>>n;
    cin>>s;
    meiju();
    for ( int i = 9; i >= 0; i-- )
    {
        while ( d[i]-- )
        {
            cout<<i;
        }
    }

    cout<<endl;

    return 0;
}

D题：

Drazil created a following problem about putting 1 × 2 tiles into an n × m grid:

"There is a grid with some cells that are empty and some cells that are occupied. You should use 1 × 2 tiles to cover all empty cells and no two tiles should cover
each other. And you should print a solution about how to do it."

But Drazil doesn't like to write special checking program for this task. His friend, Varda advised him: "how about asking contestant only to print the solution when it exists and it is unique?
Otherwise contestant may print 'Not unique' ".

Drazil found that the constraints for this task may be much larger than for the original task!

Can you solve this new problem?

Note that you should print 'Not unique' either when there exists no solution or when there exists several different solutions for the original task.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 2000).

The following n lines describe the grid rows. Character '.'
denotes an empty cell, and the character '*' denotes a cell that is occupied.

Output

If there is no solution or the solution is not unique, you should print the string "Not unique".

Otherwise you should print how to cover all empty cells with 1 × 2 tiles. Use characters "<>"
to denote horizontal tiles and characters "^v" to denote vertical tiles. Refer to the sample test for the output format example.

Sample test(s)

input
3 3
...
.*.
...

output
Not unique

input
4 4
..**
*...
*.**
....

output
<>**
*^<>
*v**
<><>

input
2 4
*..*
....

output
*<>*
<><>

input
1 1
.

output
Not unique

input
1 1
*

output
*

Note

In the first case, there are indeed two solutions:

<>^
^*v
v<>

and

^<>
v*^
<>v

so the answer is "Not unique".

解题思路：这道题读完就想搜，因为先前做过很多的搜索题，都是这样的，但是这道题明确的是覆盖，也就是说用1*2的方砖去把这个网格中，所有空白的地方都覆盖住。

这题我当时也没出来，关键是时间不够用了，，，

可以先把每个空位置看做一个点，如果与这个点相邻的位置还有点的话，那么就可以放下一个1*2的砖块了。。。。这时候，就说这个空位置有一个度。

因为最终需要的是放砖的唯一解，并且要铺满整个n*m的格子，我们从度为1的点，开始一步一步的放。如果一开始遍历完成整个格子都没有发现度为1的格子，那么直接输出

Not unique.然后BFS，且度数为1的点放砖块只能有一种情况，那么边bfs，边放砖头，并且及时更新度数，如果出现了度数为1的格子就把它加到队列里面中去，

最后bfs下，再判断是否所以空位置都被砖头覆盖了。。。。

代码：

/*
把每个空位置看做一个点，如果与它相邻还有个空位置，也就是能放一个1×2的砖块，就叫做有一个度。

因为要找放砖块的唯一解，所以我们从度数为1的点开始放。如果没有的话，说明无解或多解，直接输出“Not unique”

然后BFS，度数为1的点放砖块只有一个方向，所以我们边BFS边放砖块，并及时更新度数，如果出现了新的度数为1的点就加到队列里面去。

BFS完后再判断一下是否所有的空位置都放上砖块了。

*/

# include<cstdio>
# include<iostream>
# include<queue>
# define PII pair<int,int>
# define MP make_pair
# define F first
# define S second

using namespace std;

const int maxn = 2000 + 10;

char s[maxn][maxn];
int deg[maxn][maxn];

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
char fillchar[2][5] = { "^<v>", "v>^<" };

inline int caldeg(int i, int j)//计算该点的度数
{ return (int)(s[i-1][j] == '.') + (int)(s[i+1][j] == '.') + (int)(s[i][j-1] == '.') + (int)(s[i][j+1] == '.'); }

int main(void)
{

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

    queue<PII> Q;
    
    int cnt = 0;//统计空位置的个数
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) 
            if ( s[i][j] == '.' )
        {
            deg[i][j] = caldeg(i, j);
            cnt++;
            if( deg[i][j] == 1 )
                Q.push(MP(i, j));
        }

    if( cnt & 1 ) { puts("Not unique"); return 0; }

    while(!Q.empty())
    {
        PII cur = Q.front(); Q.pop();
        int x = cur.F; int y = cur.S;
        if(s[x][y] == '.')
        {
            int i, nx, ny;
            for(i = 0; i < 4; ++i)
            {
                nx = x + dx[i];
                ny = y + dy[i];
                if(s[nx][ny] == '.') break;
            }
            if( i == 4 ) 
            { 
                puts("Not unique");
                return 0; 
            }
            s[x][y] = fillchar[0][i];//放砖块
            s[nx][ny] = fillchar[1][i];
            deg[x][y] = deg[nx][ny] = 0;
            cnt -= 2;
            for(i = 0; i < 4; ++i)
            {
                int nnx = nx + dx[i];
                int nny = ny + dy[i];
                if(s[nnx][nny] == '.')
                {
                    deg[nnx][nny]--;//更新周围点的度数
                    if(deg[nnx][nny] == 1) 
                        Q.push(MP(nnx, nny));
                }
            }
        }
    }

    if(cnt != 0)
        puts("Not unique");//还存在空位置
    else
        for(int i = 1; i <= n; ++i) 
            printf("%s\n", s[i]+1);

    return 0;
}

E题：

【上篇】HDU 2089 不要62（数位dp/暴力打表）
【下篇】Codeforces Round #291 (Div. 2)

作者: slag

该日志由 slag 于6年前发表在综合分类下，最后更新于 2018年04月28日.
转载请注明: Codeforces Round #292 (Div. 2)。 | 学步园 +复制链接

抱歉!评论已关闭.

学步园

Codeforces Round #292 (Div. 2)。

作者: slag

书签

最新文章New

本站推荐

返回首页