Round #71 (Div. 2 only)

时间：2018-03-01 21:03:33 阅读：126 评论：0 收藏：0 [点我收藏+]

Replace A

Time limit: 1000 ms
Memory limit: 256 MB

You are given a string

Standard input

The first line contains the string

Standard output

Print the final string on the first line.

Constraints and notes

Input	Output	Explanation
AAABB	ABB	At the first step you can choose the first two `A`s, obtaining `AABB`. At the second step, you can choose the only two adjacent `A`s remaining, obtaining `ABB`. You cannot do any more operations on this string.

和上次CF的A一样，直接暴力

#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int main()
{
    ios::sync_with_stdio(false);
    string s,t;
    cin>>s;
    set<char>S;
    S.insert(‘A‘);
    while(true)
    {
        int f=1;
        for(int i=1;s[i]&&f;i++)
        {
            if(S.count(s[i-1])&&S.count(s[i]))
            {
                f=0;
                t=s.substr(0,i)+s.substr(i+1);
            }
        }
        if(f)break;
        s=t;
    }
    cout<<s;
    return 0;
}

Matrix Balls

Time limit: 1000 ms
Memory limit: 256 MB

You are given a matrix $\times MN×M, containing distinct elements. Initially there is a ball placed in every cell of the matrix. Each ball follows the following movement:$

If the current cell is smaller than all of its (at most
otherwise, the ball moves to the smallest neighbouring cell.

Find for each cell of

Standard input

The first line contains two integers

Each of the next

Standard output

Print $j^{th}j?th?? element on the i^{th}i?th?? line should represent the number of balls that end up in cell (i, j)(i,j).$

Constraints and notes

$\leq N, M \leq 5001≤N,M≤500$
$\leq A_{i, j} \leq 3*10^50≤A?i,j??≤3?10?5??$

Input	Output	Explanation
3 3 1 3 4 5 6 7 8 9 2	6 0 0 0 0 0 0 0 3	Considering a ball in each cell, 1 2 3 4 0 1 3 1 1 2 5 2 0 The value on which the ball will be placed after it moved as described in the statement 1 2 3 4 1 1 1 1 1 2 1 2 2
1 6 10 20 3 4 5 6	1 0 5 0 0 0
4 4 20 2 13 1 4 11 10 35 3 12 9 7 30 40 50 5	0 4 0 4 0 0 0 0 4 0 0 0 0 0 0 4	The value on which the ball will be placed after it moved as described in the statement 1 2 3 4 5 2 2 1 1 2 2 1 1 3 3 5 5 3 3 5 5

一个球可以向八个方向滚，滚到最小的里面，问最后每个那里面放几个

必须要记忆化搜索，但是要多搜几个方向的

#include<bits/stdc++.h>
using namespace std;
const int N=505;
int a[N][N],b[N][N],n,m;
int d[8][2]= {1,0,1,1,1,-1,0,1,0,-1,-1,0,-1,1,-1,-1};
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            cin>>a[i][j],b[i][j]=1;
    int f=1;
    while(f)
    {
        f=0;
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                if(b[i][j])
                {
                    int x=i,y=j;
                    for(int k=0; k<8; k++)
                    {
                        int tx=i+d[k][0],ty=j+d[k][1];
                        if(!(tx<0||tx>=n||ty<0||ty>=m)&&a[tx][ty]<a[x][y])
                        x=tx,y=ty;
                    }
                    if(x!=i||y!=j)
                        b[x][y]+=b[i][j],b[i][j]=0,f=1;
                }
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
            cout<<b[i][j]<<" ";
        cout<<"\n";
    }
    return 0;
}

按照数不同往下搜索

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int d[8][2]= {1,0,1,1,1,-1,0,1,0,-1,-1,0,-1,1,-1,-1};
int n,m,a[505][505],b[505][505];
pair<int,int>g[N];
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            b[i][j]=1,cin>>a[i][j],g[a[i][j]]=make_pair(i,j);
    for(int i=300000; i>=0; --i)
    {
        if(g[i].first==0)continue;
        int x=g[i].first,y=g[i].second,mi=i,sx=0,sy=0;
        for(int j=0; j<8; j++)
        {
            int tx=x+d[j][0],ty=y+d[j][1];
            if(tx<1||ty<1||tx>n||ty>m)continue;
            if(a[tx][ty]<mi)
                mi=a[tx][ty],sx=tx,sy=ty;
        }
        if(mi!=i)b[sx][sy]+=b[x][y],b[x][y]=0;
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
            cout<<b[i][j]<<" ";
        cout<<"\n";
    }
    return 0;
}

Binary Differences

Time limit: 1000 ms
Memory limit: 256 MB

You are given a binary array

Standard input

The first line contains one integer

The second line contains

Standard output

Print the answer on the first line.

Constraints and notes

$\leq N \leq 10^51≤N≤10?5??$
The subarray may be empty

Input	Output	Explanation
3 0 1 0	3	We have
4 1 0 0 1	4

这个是模拟

#include<bits/stdc++.h>
using namespace std;
int n,mi,ma,x,s,mis,mas;
int main()
{
    cin>>n;
    for(int i=1; i<=n; ++i)
    {
        cin>>x;
        if(!x)s++;
        else s--;
        mi=min(mi,s-mas),ma=max(ma,s-mis),mas=max(mas,s),mis=min(mis,s);
    }
    cout<<ma-mi+1;
    return 0;
}

Round #71 (Div. 2 only)

原文：https://www.cnblogs.com/BobHuang/p/8490069.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)