Codeforces Round #580 (Div. 2) 题解

算法竞赛 比赛-Codeforces
编辑文章
最难受的事情莫过于比赛还剩20min,你锁了题,然后叉了自己。

锁题有风险,叉人需谨慎。

A. Choose Two Numbers

题意

从两个序列中各选取一个数,要求这两个数的和不属于这两个序列。

序列长度 $N\le 200$

题解

水题,$N^2$ 枚举。

#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;
}

bool vis[405];
int n,m,x[105],y[105];

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) x[i]=read(),vis[x[i]]=1;
    m=read();
    for (int i=1;i<=m;i++) y[i]=read(),vis[y[i]]=1;
    int cnt=0;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            if (vis[x[i]+y[j]]) continue;
            printf("%d %d",x[i],y[j]);
            return 0;
        }
    }
}

B. Make Product Equal One

题意

有一个长度为 $N$ 的序列,可以修改其中的数字,每 $+1,-1$ 的代价为 $1$ 。要求修改后所有数的乘积为 $1$ ,求最小代价。

$N\le 100000$ 。

题解

显然 $1$ 和偶数个 $-1$ 乘积才为 $1$ ,所以只能改成 $1,-1$ 。

先贪心的把 $> 0$ 的改成 $1$ ,$< 0$ 的改成 $-1$ ,并记录个数。$=0$ 不论怎么改代价都是 $1$ ,同样记录个数。

如果最后有奇数个 $-1$ ,且没有 $=0$ 的数,那么就必须把一个 $-1$ 改成 $1$ ,$ans+=2$ 。

#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,ans,cnt0,cnt1,cnt2;

signed main()
{
    n=read();
    for (int i=1;i<=n;i++)
    {
        s=read();
        if (s==0) cnt0++,ans++;
        else if (s<0) cnt2++,ans+=-1-s;
        else cnt1++,ans+=s-1;
    }
    if (cnt2&1 && cnt0==0) ans+=2;
    cout<<ans;
    return 0;
}

C. Almost Equal

题意

把 $1..2N$ 的数放在一个圆环上,要求所有连续 $N$ 个数之和差值不能超过 $1$ 。询问是否有满足条件的方案,如果有还要求输出方案。

$N\le 100000$ 。

题解

找下规律,可以发现奇数可以偶数不行。

顺时针前 $N$ 个数为 $1,2N,3,2N-2,5,...,N$ 。后 $N$ 个数为前 $N$ 个的同组另一个数,即 (s[i]+1)^1)-1

证明?OI是工科,意会一下就行了。

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

signed main()
{
    n=read();
    if (n%2==0) return 0&puts("NO");
    puts("YES");
    int l=1,r=n<<1;
    for (int i=1;i<=n;i++)
    {
        if (i%2==1) s[i]=l,l+=2;
        else s[i]=r,r-=2;
        printf("%d ",s[i]);
    }
    for (int i=1;i<=n;i++) printf("%d ",((s[i]+1)^1)-1);
    return 0;
}

D. Shortest Cycle

题意

有 $N$ 个数,如果 $A_i \ and \ A_j \neq 0$ ,则 $(i,j)$ 有一条边。求最小的环。没有环输出 -1

$N\le 100000 \ , \ A_i\le 10^{18}$

题解

直接连边显然是 $N^2$ ,考虑对其进行优化。

新建 $64$ 个中转点,如果 $A_i$ 的二进制的第 $k$ 位是 $1$ ,就把它和第 $k$ 个中转点相连。这样有 $N+64$ 个点,最多 $64N$ 条边。答案为最小环 $\div 2$ 。

但这样其实是有问题的,如下面的数据(我叉我自己):

3
1 1 3

三个点都连在第 $1$ 个中转点上,它们之间就可以构成环,但如果按照上述方式连边就会得到 -1

所以对每一个中转点记录度数 $c[k]$ ,如果 $c[k]\geq 3$ ,那么答案就是 $3$ 。

然后就可以 $\text{dfs}$ 找环了。记录深度和访问情况,如果找到环当前答案就是 $\dfrac{(deep[x]-deep[y])+1}{2}$ 。

但这样也有问题,如果遇到环套环,就可能会走冤枉路。那么从每个点出发 $\text{dfs}$ 一遍就好了。

什么?你说这是 $N^2$ 的?不,如果所有 $c[k] < 3$ ,那么最多 $128$ 个点,显然是够的。

Time limit exceeded on test 17(尴尬)

原来还有 $0$ 这个搅屎棍,把它忽略掉就行了。

#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;
}

struct Edge {
    ll next,to;
} edge[12800005];
bool vis[100105];
ll cnt,head[100105],n,ans=1e18,pcnt,id,s[100105],deep[100105],c[100105];

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

void dfs(ll x,ll f,ll dep)
{
    vis[x]=1;
    deep[x]=dep;
    for (ll i=head[x];i;i=edge[i].next)
    {
        ll y=edge[i].to;
        if (y==f) continue;
        if (vis[y])
        {
            ll cur=abs(deep[y]-deep[x])+1; //因为是双向边,所以可能出现负数,取绝对值即可
            if (cur==4) continue; //如果环大小为4,那么在原图中是自环
            ans=min(ans,cur>>1);
        }
        else dfs(y,x,dep+1);
    }
}

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) s[i]=read(),pcnt+=s[i]>0;
    for (ll i=1;i<=n;i++)
    {
        if (!s[i]) continue; //跳过0
        id++;
        for (ll j=63;~j;j--)
        {
            if (s[i]>>j&1)
            {
                add(id,j+pcnt+1);
                add(j+pcnt+1,id); //连边
                c[j]++;
            }
        }
    }
    n=pcnt;
    for (int i=63;~i;i--)
    {
        if (c[i]>=3)
        {
            ans=3;
            goto output;
        }
    }
    for (ll i=1;i<=n+64;i++)
    {
        memset(vis,0,sizeof(vis));
        memset(deep,0,sizeof(deep));
        dfs(i,0,1);
    }
    if (ans==1e18) ans=-1;
    output:
    cout<<ans;
    return 0;
}

新评论

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