Codeforces Round #583 题解

算法竞赛 比赛-Codeforces
编辑文章

rk800,终于上蓝啦

A.Optimal Currency Exchange

题意

卢布兑美元为 $a:1$ ,兑欧元为 $b:1$ 。美元面值最少为 $1$ ,欧元为 $5$ 。要把 $N$ 卢布尽量兑换出去,求最少剩下多少。

$N\le 10^8 \ , \ 30\le a,b\le 100$

题解

水题,枚举某种货币用了几张即可。我还sb的T了一次

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int n,a,b;

signed main()
{
    n=read(); a=read(); b=read();
    b*=5;
    int ans=1e9;
    int maxi=n/b;
    for (int i=0;i<=maxi;i++)
    {
        int left=n-i*b;
        int maxj=left/a;
        ans=min(ans,left-a*maxj);
    }
    return !printf("%d",ans);
}

B.Badges

题意杀我,看了5min才懂

题意

在 $B$ 个男孩和 $G$ 个女孩中有 $N$ 个人会参加活动,要给男孩准备蓝色徽章,女孩红色。共有 $N+1$ 组徽章,第 $i$ 组有 $i$ 个蓝色和 $N-i$ 个红色。要求不管来多少个男孩女孩都能准确分配徽章,问需要准备多少组。

$B,G\le 300$ 。

题解

就是求男孩人数种类和女孩人数种类的较大值。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int b,g,n;

signed main()
{
    b=read(); g=read(); n=read();
    int maxb=min(n,b),ming=n-maxb;
    int maxg=min(n,g),minb=n-maxg;
    return !printf("%d",max(maxb-minb,maxg-ming)+1);
}

C.Bad Sequence

题意

给出一个括号序列,最多只能移动一个元素到另一个位置,问能否变成匹配的括号序列。

长度 $N\le 10^5$ 。

题解

$O(n)$ 扫一遍,如果有两个不匹配就直接输出 NO ,如果最后完美匹配就是 YES。因为不匹配的都是 ),所以如果有一个不匹配的且最后栈中有 $1$ 个元素也是 YES。其它情况是 NO

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int n,cnt;
char ch[200005];

signed main()
{
    n=read();
    scanf("%s",ch+1);
    bool flag=0;
    for (int i=1;i<=n;i++)
    {
        if (ch[i]=='(') cnt++;
        else if (ch[i]==')')
        {
            if (cnt) cnt--;
            else if (!flag) flag=1;
            else return 0&puts("NO");
        }
    }
    if ((!flag && !cnt) || (flag && cnt==1)) return 0&puts("YES");
    return 0&puts("NO");
}

D.Treasure Island

upd:好像 1e9+71e9+9 都被卡掉了,看来出题人并不知道这个大质数。。所以以后还是应该多膜几个数。

题意

从 $(1,1)\rightarrow (n,m)$ ,只能向上向右走,图中的障碍物不能通过。问至少要再放置几个障碍物,使得无法到 $(n,m)$ 。

$n\times m\le 10^6$ 。

题解

可以发现答案最多为 $2$ ,即在 $(1,2)$ 和 $(2,1)$ 放上障碍物。所以只需要考虑答案为 $1,0$ 的情况。

如果答案为 $0$ ,说明本来就无法到 $(n,m)$ ,用 $\text{bfs}$ 搜索一遍即可判断。

如果答案为 $1$ ,就说明有一个格子是类似割点一样的状态。用 $gs[i][j]$ 表示从 $(1,1)\rightarrow (i,j)$ 的路径方案数,$gt[i][j]$ 表示从 $(n,m)\rightarrow (i,j)$ 的方案数,方程式为:

$$\begin{cases} gs[i][j]=gs[i-1][j]+gs[i][j-1] \\ gt[i][j]=gt[i+1][j]+gt[i][j+1] \end{cases}$$

如果存在一个点 $(i,j)$ ,使得 $gs[i][j]\times gt[i][j]=gs[n][m]$ ,就说明所有路径都会经过这个点,那么就可以放障碍物在这个点,答案为 $1$ 。

不过 $gs,gt$ 可能会很大,所以需要膜一个大质数。我当时想过多膜几个,但仔细想来就算要叉我构造数据也很麻烦,就没写。

其它情况答案就是 $2$ 。

#include<bits/stdc++.h>
#define ha 19260817
#define pii pair<int,int>
#define mp make_pair

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

char ch[1000005];
bool s[1000005],vis[1000005];
int n,m,gs[1000005],gt[1000005];
const int fx[2]={1,0},fy[2]={0,1};

inline int f(int x,int y) //将二维坐标转为一维
{
    if (x<1 || x>n || y<1 || y>m) return 0;
    return (x-1)*m+y;
}

inline void bfs()
{
    vis[f(1,1)]=1;
    queue <pii> q;
    q.emplace(mp(1,1));
    while (!q.empty())
    {
        int x=q.front().first,y=q.front().second; q.pop();
        for (int i=0;i<2;i++)
        {
            int tx=x+fx[i],ty=y+fy[i];
            if (tx<1 || tx>n || ty<1 || ty>m || s[f(tx,ty)] || vis[f(tx,ty)]) continue;
            vis[f(tx,ty)]=1;
            q.emplace(mp(tx,ty));
        }
    }
}

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++)
    {
        scanf("%s",ch+1);
        for (int j=1;j<=m;j++) s[f(i,j)]=ch[j]=='#';
    }
    bfs();
    if (!vis[f(n,m)]) return 0&puts("0"); //如果无法到达说明答案是0
    gs[f(1,1)]=1;
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) 
        if ((i!=1 || j!=1) && !s[f(i,j)]) gs[f(i,j)]=(gs[f(i-1,j)]+gs[f(i,j-1)])%ha;
    gt[f(n,m)]=1;
    for (int i=n;i;i--) for (int j=m;j;j--)
        if ((i!=n || j!=m) && !s[f(i,j)]) gt[f(i,j)]=(gt[f(i+1,j)]+gt[f(i,j+1)])%ha;
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++)
    {
        if ((i==1 && j==1) || (i==n && j==m)) continue;
        if (1ll*gs[f(i,j)]*gt[f(i,j)]%ha==gs[f(n,m)]%ha) return 0&puts("1"); //(i,j)是割点,答案为1
    }
    return 0&puts("2");
}

E.Petya and Construction Set

题意

要求构造一棵 $2N$ 个点树,使得 $i\rightarrow (i+1)$ 中间有 $d_i$ 条边。

$N\le 10^5$ 。

题解

神奇的构造题。

先按 $d_i$ 从大到小进行排序,然后把 $1,3,5,...,2N-1$ 这些奇数点按照排序后的顺序连成一条链。

然后把这些组依次扫一遍,同时用 deque 记录最长链,将偶数点与 距同组奇数点 $d_i$ 的点相连即可。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

struct node {
    int id,d;
} s[100005];
int n;
deque <int> q;

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) s[i].d=read(),s[i].id=i;
    sort(s+1,s+n+1,[](const node &x,const node &y){ return x.d>y.d; });
    for (int i=1;i<=n;i++)
    {
        q.emplace_back(s[i].id*2-1);
        if (i<n) printf("%d %d\n",s[i].id*2-1,s[i+1].id*2-1);
    }
    for (int i=1;i<=n;i++)
    {
        printf("%d %d\n",s[i].id*2,q[s[i].d-1]);
        if (s[i].d==(int)q.size()) q.emplace_back(s[i].id*2);
        q.pop_front();
    }
    return 0;
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空