codeforces-round375-div2

亦凉 2022-07-16 04:12 198阅读 0赞

题目链接：[codeforces round 375 div2][]

A题：

读一遍题目就知道是超级水的题目，，就是给你三个坐标，求三个坐标汇集到一个点所走的路程最短，，就是按x排序，，最大的减去最小的就是最短的！

AC代码：

B题：B题模拟题，，题目意思很简单，，关键在于处理，，给你一串字符串，仅有大小写字母，下划线，左右括号。定义一个单词为连续的字母，下划线和括号为单词的分隔符，输入的括号保证匹配，求括号外的单词的最大的长度，括号内的单词的个数，重复的也算，，，，这题只需扫一遍就能得到答案了，，当遇到字母就用while来循环直到不是字母，当然关键在于处理括号内还是括号外，，这里可以用标记变量来标记，也可以遇到‘（’ 就while循环到‘）’ 来分别处理，括号外面就统计单词的长度，括号里面就统计单词的个数，，还有就是结束后还要比较一次最后的单词长度是否大于当前的最大长度（如果是以单词结尾）

AC代码：

C题：C题算比较恶心的题了，，关键在于能不能看懂题目意思，，我也看了好久才看懂，，英语是一大硬伤啊，，，

C. Polycarp at the Radio

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Polycarp is a music editor at the radio station. He received a playlist for tomorrow, that can be represented as a sequence *a*1, *a*2, ..., *a**n*, where *a**i* is a band, which performs the *i*\-th song. Polycarp likes bands with the numbers from 1 to *m*, but he doesn't really like others.

We define as *b**j* the number of songs the group *j* is going to perform tomorrow. Polycarp wants to change the playlist in such a way that the minimum among the numbers *b*1, *b*2, ..., *b**m* will be as large as possible.

Find this maximum possible value of the minimum among the *b**j* (1 ≤ *j* ≤ *m*), and the minimum number of changes in the playlist Polycarp needs to make to achieve it. One change in the playlist is a replacement of the performer of the *i*\-th song with any other group.

Input

The first line of the input contains two integers *n* and *m* (1 ≤ *m* ≤ *n* ≤ 2000).

The second line contains *n* integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 109), where *a**i* is the performer of the *i*\-th song.

Output

In the first line print two integers: the maximum possible value of the minimum among the *b**j* (1 ≤ *j* ≤ *m*), where *b**j* is the number of songs in the changed playlist performed by the *j*\-th band, and the minimum number of changes in the playlist Polycarp needs to make.

In the second line print the changed playlist.

If there are multiple answers, print any of them.

Examples

input

4 2
    1 2 3 2

output

2 1
    1 2 1 2

input

7 3
    1 3 2 2 2 2 1

output

2 1
    1 3 3 2 2 2 1

input

4 4
    1000000000 100 7 1000000000

output

1 4
    1 2 3 4

题目意思： 给你一个演出的序列，a1,a2,a3,,,,,,an;   ai 表示第ai 位歌手唱第 i 首歌，现在polycarp只喜欢前m位歌手，所以他要对演出的序列进行修改，，他希望前m位歌手中唱歌的数量最少的尽量最大，这里其实不好理解，，例如第一个例子   序列为  1 2 3 2  m为2，，，所以歌手 1 唱 1 首，歌手 2 唱 2 首  还有歌手3唱1首，而歌手三十polycarp不喜欢的，所以要被替换掉，当然还有其他情况，所以替换后的序列为  1 2 1 2  因为歌手 1 只有一首，所以替换1

题目思路  ：  首先考虑那个最小最大值，这个不难得出是 n/m ,因为n首个平均分配到m个歌手上才满足题目的条件，然后就很好做了，，知道了最少的唱歌数量，就只需统计出前m个歌手分别唱的歌曲数量，然后与n/m 比较，比他小就要有人替换成他，比他大要替换掉，，所以在输入时可以用map来统计每个歌手的数量，然后遍历1-m的歌手用个数组存小于n/m 的歌手，，接下来就只需遍历一遍序列了，，当遇到1-m内的歌手并且数量大于n/m或编号大于m的歌手，就把它替换成数组里存的歌手的编号，并且用来替换的歌手的map--，然后被替换的歌手map要++，当改歌手唱歌数量达到n/m后换下一个存的歌手的编号，，直到数组为空。

AC代码：

#include<algorithm>
    #include<iostream>
    #include<stdlib.h>
    #include<cstring>
    #include<stdio.h>
    #include<vector>
    #include<string>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<map>
    #include<set>
    using namespace std;
    
    #define lcr(a,b) memset(a,b,sizeof(a))
    #define sfor(i,n) for(i=0;i<n;i++)
    #define dfor(i,n) for(i=n-1;i>=0;i--)
    #define sc(x) scanf("%d",&x)
    #define pr(x) printf("%d\n",x)
    #define ll long long
    #define INF 0x7fffffff
    #define esp 1e-8
    
    int i,j,k;
    int n,m;
    
    int main()
    {
        int s[2005];
        map<int,int>mp;
        set<int>se;
        cin>>n>>m;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&s[i]);
            mp[s[i]]++;
        }
        int msum=0;
        for(int i=1; i<=m; i++)
        {
            msum+=mp[i];
        }
        int min_num=(msum+(n-msum))/m;
        map<int,int>mm;
        vector<int>v;
        int ch=0;
        for(int i=1; i<=m; i++)
        {
            if(mp[i]<min_num)
            {
                ch+=min_num-mp[i];
                v.push_back(i);
            }
        }
        int len=v.size();
        int cnt=0;
        for(int i=0; i<n; i++)
        {
            if((mp[s[i]]>min_num||s[i]>m)&&cnt<len)
            {
                if(s[i]>m)
                {
                    s[i]=v[cnt];
                    mp[v[cnt]]++;
                    if(mp[v[cnt]]>=min_num)cnt++;
                }
                else
                {
                    mp[s[i]]--;
                    s[i]=v[cnt];
                    mp[v[cnt]]++;
                    if(mp[v[cnt]]>=min_num)cnt++;
    
                }
            }
        }
        printf("%d %d\n",min_num,ch);
        for(int i=0; i<n; i++)
            printf("%d ",s[i]);
        return 0;
    }

D题：D题其实是一个相对简单的搜索题，dfs就可以解决，，但是我就因为天真的把数组大小计算错了，结果终判WA了，最后把数组改大就A了，，

D. Lakes in Berland

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

The map of Berland is a rectangle of the size *n* × *m*, which consists of cells of size 1 × 1. Each cell is either land or water. The map is surrounded by the ocean.

*Lakes* are the maximal regions of water cells, connected by sides, which are not connected with the ocean. Formally, lake is a set of water cells, such that it's possible to get from any cell of the set to any other without leaving the set and moving only to cells adjacent by the side, none of them is located on the border of the rectangle, and it's impossible to add one more water cell to the set such that it will be connected with any other cell.

You task is to fill up with the earth the minimum number of water cells so that there will be **exactly** *k* lakes in Berland. Note that the initial number of lakes on the map is **not less** than *k*.

Input

The first line of the input contains three integers *n*, *m* and *k* (1 ≤ *n*, *m* ≤ 50, 0 ≤ *k* ≤ 50) — the sizes of the map and the number of lakes which should be left on the map.

The next *n* lines contain *m* characters each — the description of the map. Each of the characters is either '.' (it means that the corresponding cell is water) or '\*' (it means that the corresponding cell is land).

It is guaranteed that the map contain at least *k* lakes.

Output

In the first line print the minimum number of cells which should be transformed from water to land.

In the next *n* lines print *m* symbols — the map after the changes. The format must strictly follow the format of the map in the input data (there is no need to print the size of the map). If there are several answers, print any of them.

It is guaranteed that the answer exists on the given data.

Examples

input

5 4 1
    ****
    *..*
    ****
    **.*
    ..**

output

1
    ****
    *..*
    ****
    ****
    ..**

input

3 3 0
    ***
    *.*
    ***

output

1
    ***
    ***
    ***

题目意思： 给你一张地图，地图被海包围着，其中 ‘.’ 代表水块，‘\*’ 代表陆地 ，相邻的水块组成一个湖，不能与海相连通，也就是不能在地图的边界上，然后现在要限制湖的数量在k个，问你最少填多少个水块才能满足仅有k个湖，题目保证输入不小于k个湖：

题目思路： 其实只需循环一遍这个地图，当遇到水块并且不在边界且没有被访问过，就对改点进行dfs，dfs找出所有与之相邻的水块并标记防止重复，还有统计出数量，当所有的水块没有出现过边界时就找到了一个湖，然后就可以用个结构体存起来，保存起始的x，y坐标和湖的大小就是水块的数量，最后按湖大小排序，从小到大填掉多出限制的湖，这里也可以dfs去填，然后统计出点的湖的大小的和，，最后就输出答案！

AC代码：

#include<algorithm>
    #include<iostream>
    #include<stdlib.h>
    #include<cstring>
    #include<stdio.h>
    #include<vector>
    #include<string>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<map>
    #include<set>
    using namespace std;
    
    #define lcr(a,b) memset(a,b,sizeof(a))
    #define sfor(i,n) for(i=0;i<n;i++)
    #define dfor(i,n) for(i=n-1;i>=0;i--)
    #define sc(x) scanf("%d",&x)
    #define pr(x) printf("%d\n",x)
    #define ll long long
    #define INF 0x7fffffff
    #define esp 1e-8
    
    int n,m,k,flag,num,cnt;
    
    char s[55][55];
    int vis[55][55];
    
    int fx[4][2]= {1,0,-1,0,0,1,0,-1};
    
    struct nod
    {
        int x,y;
        int num;
    } P[2000];    //保存湖
    
    bool cmp(nod a,nod b)
    {
        return a.num<b.num;
    }
    
    void dfs(int h,int l)    //找湖
    {
        vis[h][l]=1;
        num++;
        for(int kk=0; kk<4; kk++)
        {
            int xx=h+fx[kk][0];
            int yy=l+fx[kk][1];
            if(xx>=0&&xx<n&&yy>=0&&yy<m&&s[xx][yy]=='.'&&!vis[xx][yy])
            {
                if(xx==0||yy==0||xx==n-1||yy==m-1)
                {
                    flag=1;
                }
                dfs(xx,yy);
            }
        }
    }
    
    void Fill(int h,int l)   //填湖
    {
        s[h][l]='*';
        for(int k=0; k<4; k++)
        {
            int xx=h+fx[k][0];
            int yy=l+fx[k][1];
            if(xx>=0&&xx<n&&yy>=0&&yy<m&&s[xx][yy]=='.')
            {
                Fill(xx,yy);
            }
        }
    }
    int main()
    {
        cin>>n>>m>>k;
        cnt=0;
        lcr(vis,0);
        for(int i=0; i<n; i++)
            scanf("%s",s[i]);
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
            {
                if(s[i][j]=='.'&&!vis[i][j]&&i&&j&&i!=n-1&&j!=m-1)
                {
                    num=0;
                    flag=0;
                    dfs(i,j);
                    if(!flag)
                    {
                        P[cnt].x=i;
                        P[cnt].y=j;
                        P[cnt++].num=num;
                    }
                }
            }
        sort(P,P+cnt,cmp);
        int ans=0;
        for(int i=0; i<cnt-k; i++)
        {
            Fill(P[i].x,P[i].y);
            ans+=P[i].num;
        }
        cout<<ans<<endl;
        for(int i=0; i<n; i++)
            printf("%s\n",s[i]);
        return 0;
    }

后面两题没时间看，也可能不会做！

[codeforces round 375 div2]: http://codeforces.com/contest/723