6月23日 AtCoder Regular Contest 99
题目链接:https://arc099.contest.atcoder.jp/

C – Minimization

思路:
最后序列的所有元素一定是序列中的最小值,然后每一次操作都能让序列中k-1个元素变为最小值,直接扫一遍就好了。

代码:

#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#define  LL long long
using namespace std;

int n, k;
LL ans;

int main()
{
    scanf("%d%d", &n, &k);
    for(int i=1; i<n; i+=k) ans++, i--;
    printf("%lld\n", ans);
}

D – Snuke Numbers

思路:
比较神奇的一题!我们设一个增量为d,即下一个数比这个数大d。d开始是为1,后面d要么保持不变,要么乘上10,这样我们就对每一个数都计算d需不需要乘10就可以了。(其实不是很明白为什么,有一点迷

代码:

#include <cstdio>
#include <iostream>
#define LL long long
using namespace std;

LL k, n, d=1;

int s(LL x)
{
    int sum=0;
    while(x) sum+=x%10, x/=10;
    return sum;
}

int main()
{
    scanf("%lld", &k);
    for(int i=1; i<=k; i++)
    {
        if((n+d*10)*s(n+d)<(n+d)*s(n+d*10)) d*=10;
        n+=d;
        printf("%lld\n", n);
    }
}

E – Independence

思路:
特别好的一题。题目简化来说就是要你找两个完全子图,并且使子图中的边数最少。

考虑这张图的补图,如果补图是二分图,则存在着两个完全子图,否则输出-1。(这个画一下应该不难发现)我们对补图进行二分图染色,但要注意补图可能不连通,所以有多种染色方法。这时染成同一种颜色的节点在原图中是构成了完全图的,于是我们记录所有可能的染色方法,对于所有方法计算答案并去其中的最小值就OK了。

代码:

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

int n, m, a, b, s1, s2, ans=INF, temp[1500], col[705], f[705];
bool mmp[705][705], vis[1005];

void dfs(int x, int color)
{
    if(vis[x])
    {
        if(col[x]!=color) {printf("-1\n"); exit(0);}
        return;
    }
    vis[x]=1; col[x]=color;
    if(color==1) s1++;
    else s2++;
    for(int i=1; i<=n; i++)
    {
        if(mmp[x][i]==0) continue;
        dfs(i, 3-color);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d", &a, &b);
        mmp[a][b]=mmp[b][a]=1;
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(i==j) mmp[i][j]=0;
            else mmp[i][j]^=1;
        }
    }
    f[0]=1;
    for(int i=1; i<=n; i++)
    {
        if(vis[i]) continue;
        s1=s2=0;
        dfs(i, 2);
        for(int i=0; i<=n; i++)
        {
            temp[i+s1]|=f[i];
            temp[i+s2]|=f[i];
        }
        for(int i=0; i<=n; i++)
        {
            f[i]=temp[i];
            temp[i]=0;
        }
    }
    for(int i=0; i<=n; i++) 
        if(f[i]) ans=min(ans, i*(i-1)/2+(n-i)*(n-i-1)/2);
    printf("%d\n", ans);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注