Codeforces Round #586 题解

题解 比赛-Codeforces
题目链接 编辑文章

A.Cards

题意

给 $n(n\le 10^5)$ 个字母,要求把它们组合成 onezero 并输出为 1/0

题解

统计 nz 的个数即可。

#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;
char s[100005];

signed main()
{
    n=read();
    scanf("%s",s+1);
    int cntN=0,cntZ=0;
    for (int i=1;i<=n;i++)
    {
        cntN+=s[i]=='n';
        cntZ+=s[i]=='z';
    }
    for (int i=1;i<=cntN;i++) printf("1 ");
    for (int i=1;i<=cntZ;i++) printf("0 ");
    return 0;
}

B.Multiplication Table

题意

给出一个 $n\times n(3\le n\le 1000)$ 的矩阵 $s$ ,$s_{ij}=a_i\times a_j$ 。现在把对角线上的数抹掉,求 $a$ 。

题解

第一行可以表示出 $a_2:a_3:a_4:...:a_n$ ,第二行可以表示 $a_1:a_3:a_4:...:a_n$ 。因为保证有解,所以对第三项求 $\mathrm{lcm}$ 后即可得到所有数的比值。

然后通过任意一个值就可以得到比值和实际的对应关系,然后就可以得到答案。注意先除后乘,防止越界。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar(); ll 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;
}

ll n,s[1005][1005];

ll gcd(ll x,ll y) { return y ? gcd(y,x%y) : x; }

signed main()
{
    n=read();
    for (ll i=1;i<=n;i++) for (ll j=1;j<=n;j++) s[i][j]=read();
    ll lcm=s[1][3]*s[2][3]/gcd(s[1][3],s[2][3]);
    ll d1=lcm/s[1][3];
    for (ll j=2;j<=n;j++) s[1][j]*=d1;
    s[1][1]=s[2][1]*(lcm/s[2][3]);
    ll delta=sqrt(s[1][1]*(s[1][2]/s[2][1])); //对应关系
    for (ll j=1;j<=n;j++) printf("%lld ",s[1][j]/delta);
    return 0;
}

C.Substring Game in the Lesson

题意

给出一个长度为 $n(n\le 5\times 10^5)$ 字符串,由 ab 组成。AnnMike 玩游戏,Ann 先手。

初始状态为 $L=R=k$ ,用 $[L,R]$ 表示 字符串中 $S_L..S_R$ 的字典序,每次可以选择 $L'\le L \ , \ R'\geq R \ ([L',R'] < [L,R])$ ,并把 $L,R$ 挪到 $L',R'$ 。不能操作就算输。

问 $k=[1,n]$ 时谁能赢。

题解

可以发现只向右拓展字典序一定会增大,所以是没有意义的,只考虑向左移动。

向左移动只能移动到比 $S_L$ 小的,如果能移动肯定就直接移到最小的最左边的,后手输;否则先手直接输掉。

#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;
char s[500005];

signed main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    int mn=1e9;
    for (int i=1;i<=n;i++)
    {
        if (mn<s[i]) puts("Ann");
        else puts("Mike"),mn=s[i];
    }
    return 0;
}

D.Alex and Julian

内容转载自 https://www.cnblogs.com/Dup4/p/11552923.html#d.-alex-and-julian

题意

有一个集合 $B$,以及所有的整数组成的点,对于一个整数 $i$ ,那么该点的标号为 $i$,现在如果两个点 $(i,j)$ 满足 $|i-j|\in B$ ,那么 $(i,j)$ 之间有一条无向边。

问至少删去 $$ 中多少个数,使得所有点按要求连完边之后该图是一个二分图。

题解

没有奇圈的图是一个二分图

考虑 $x, y$ ,假设从 $1$ 出发,往后连边,那么他们相遇的点是 $lcm(x, y) + 1$ ,那么这个环的边数是:

$$\frac{lcm(x, y)}{x} + \frac{lcm(x, y)}{y} = \frac{x}{gcd(x, y)} + \frac{y}{gcd(x, y)}$$

我们发现要使得这个式子不能为奇数,那么显然有偶加偶或者奇+奇。

我们考虑先将两个数都尽可能除 $2$ ,直到这两个数的公约数中没有 $2$ 为止。

然后再来判断,那么现在至少有一个数是奇数,假设为 $x$ ,那么剩下的公约数肯定是个奇数。

那么考虑剩下的 $x, y$ :

  • 如果 $x, y$ 都是奇数,那么除掉一个奇数后还是奇数。
  • 如果只有一个是奇数,那么偶数的那个除掉一个奇数还是偶数,奇数那个除掉奇数还是奇数,那么就是奇 + 偶 = 奇,不合法

所以所有可以共存的数必然满足他们的最低二进制位一样。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar(); ll 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;
}

ll n,s[200005];
bool vis[200005];
vector <int> v[64];

signed main()
{
    n=read();
    for (int i=1;i<=n;i++)
    {
        s[i]=read();
        int j=0; for (;!(s[i]>>j&1);j++);
        v[j].emplace_back(i);
    }
    ll mx=0,maxi;
    for (int i=0;i<64;i++)
    {
        if ((ll)v[i].size()>mx)
        {
            mx=v[i].size();
            maxi=i;
        }
    }
    v[maxi].clear();
    printf("%lld\n",n-mx);
    for (int i=0;i<64;i++) for (auto j:v[i]) vis[j]=1;
    for (int i=1;i<=n;i++) vis[i]&&printf("%lld ",s[i]);
    return 0;
}

E.Tourism

题意

有一个 $n(n\le 2\times 10^5)$ 点 $m(m\le 2\times 10^5)$ 边的无重边无自环的无向图,每个点有个点权。从 $1$ 出发,不能连续经过同一条边,问路径上点权和的最大值是多少。

题解

环上每一个点都可以遍历一遍,连接环之间的点也是;如果起点不在这些点上,那么这条边到环上的所有点也能被遍历,但起点到末梢的路径上则不能(到末梢再回来就会连续经过末端的边)。

剩下的与环相连的路径只能选择一条,可以拓扑排序DP,用 $f[i]$ 表示末梢到 $i$ 点权值和的最大值,所有环上的点中取 $f[i]$ 的最大值即是最优的路径。

答案即为所有没被拓扑的点的点权和 $+ \max(f[i])$ 。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar(); ll 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;
}

const ll N=200005;
struct Edge {
    ll next,to;
} edge[N<<1];
queue <ll> q;
ll cnt,head[N],n,m,a,b,st,s[N],deg[N],f[N];

inline void add(ll u,ll v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

signed main()
{
    n=read(); m=read();
    for (ll i=1;i<=n;i++) s[i]=read();
    for (ll i=1;i<=m;i++)
    {
        a=read(); b=read();
        add(a,b); add(b,a);
        deg[a]++; deg[b]++;
    }
    st=read();
    if (n==1) return !printf("%lld",s[1]);
    for (ll i=1;i<=n;i++)
    {
        if (i==st || deg[i]!=1) continue;
        q.emplace(i);
    }
    while (!q.empty()) //拓扑排序
    {
        ll x=q.front(); q.pop();
        deg[x]=0;
        for (ll i=head[x];i;i=edge[i].next)
        {
            ll y=edge[i].to;
            if (!deg[y]) continue;
            f[y]=max(f[y],f[x]+s[x]);
            if (y==st) continue; //遇到起点则不继续
            deg[y]--;
            if (deg[y]==1) q.emplace(y);
        }
    }
    ll ans=0,maxf=0;
    for (ll i=1;i<=n;i++)
    {
        if (!deg[i]) continue;
        ans+=s[i];
        maxf=max(maxf,f[i]);
    }
    return !printf("%lld",ans+maxf);
}

新评论

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