AtCoder Beginner Contest 146


AtCoder Beginner Contest 146全题解

A. Can’t Wait for Holiday

签到题没啥好说的

int main()
{
    string s;
    cin>>s;
    if(s=="SUN") puts("7");
    else if(s=="MON") puts("6");
    else if(s=="TUE") puts("5");
    else if(s=="WED") puts("4");
    else if(s=="THU") puts("3");
    else if(s=="FRI") puts("2");
    else if(s=="SAT") puts("1");
    return 0;
}

B. ROT N

同签到模拟

int main()
{
    int n;string s;
    cin>>n;cin>>s;
    for(int i=0;i<s.size();i++)
    {
        char t=s[i]-'A';
        int temp=t+n;
        if(temp>=26) temp-=26;
        cout<<char('A'+temp);
    }
    puts("");
    return 0;
}

C. Buy an Integer

题目简述:

有编号$1-10^9$的物品 每个物品$N$的花费为$A\cdot N+B\cdot d(N)$元 其中$d(N)$数字$N$的位数 现在给定$X$元 求能买到编号最大的物品是多少

题解:

暴力枚举几位数即可 然后判断一下是否合法 注意只能判九位数 因为十位数只有一个$10^9$特殊判断即可

AC代码:

const int N=1000000000;
ll a,b,x;
int main()
{
    cin>>a>>b>>x;
    ll ans=0;
    for(int i=1;i<=9;i++)
    {
        ll temp=x-b*i;
        if(temp<=0) break;
        ll t=temp/a;
        if(t>=(ll)pow(10,i)) t=pow(10,i)-1;
        ans=max(ans,t);
    }
    if(a*N+b*10<=x) ans=N;
    cout<<ans<<endl;
    return 0;
}

D. Coloring Edges on Tree

题意简述:

给定一棵树 树的每个点连着的边颜色都不能相同 问把所有边都染色最少需要几种颜色

题解:

首先最大值很好看 就是树最大的度 然后在染色的时候我们可以dfs(比赛时候这里退缩了一下然后跑去尝试构造浪费了大量时间)对于每条边我们把$u,v$按小大排一下直接放到pair里 然后从点1开始dfs 我们需要保存三个值 当前节点 父亲节点 以及父亲连到当前的颜色 然后我们扫描每条边从颜色1开始逐个相加 假如加到了父亲的颜色还要再加1跳过去 比赛时候被dfs时候处理边困了一下 明明一个map解决的事情

AC代码:

const int maxn=100050;
int n,in[maxn],res;
map<PII,int> co;
int head[maxn],num;
PII ans[maxn];
struct node{
    int v,nex;
}e[maxn<<1];
void add(int u,int v)
{
    e[++num].nex=head[u];
    e[num].v=v;
    head[u]=num;
}
void dfs(int u,int fa,int pre)
{
    int c=1;
    if(c==pre) c++;
    for(int i=head[u];i;i=e[i].nex)
    {
        int v=e[i].v;
        if(v==fa) continue;
        co[make_pair(u,v)]=c;
        res=max(res,c);
        dfs(v,u,c);
        c++;
        if(c==pre) c++;
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n-1;i++)
    {
        int x,y;
        read(x),read(y);
        if(x>y) swap(x,y);
        ans[i]=make_pair(x,y);
        add(x,y),add(y,x);
    }
    dfs(1,0,0);
    cout<<res<<endl;
    for(int i=1;i<=n-1;i++) cout<<co[ans[i]]<<endl;
    return 0;
}

E. Rem of Sum is Num

题意简述:

给定一个序列 假如这个序列的其中一个连续子段满足子段值的和模$K$等于子段长度则符合要求 求符合要求的子段的数目

题解:

这大概算是本场ABC最难的题?首先处理子段的不难想到前缀和 那么我们现在知道一段前缀和 如何去统计它的贡献呢 其实这是一个数学的活 首先假设当前考虑到$i$ 那么从$j+1$到$i$的子段和就是$sum(i)-sum(j)$ 区间长度是$i-j$ 题目要求的是 $(sum(i)-sum(j))%K=i-j$ 所以$i-j$的值肯定是在模$K$意义下的 即$i-j$属于$[0,K)$ 然后把式子魔改一波
$ sum(i)-sum(j)\equiv i-j \mod K$
$sum(i)-i\equiv sum(j)-j \mod K$
到这里已经非常显然了 我们维护一个map 每次考虑到$i$看看$(sum(i)-i)%K$在map中有几个值就加几 再把自己加进map顺便注意考虑一下出界情况就行 因为$i-j\in[0,K)$
需要注意一下的是$j$要从0开始所以一开始就需要$mp[0]=1$

const int maxn=200050;
ll n,k,sum[maxn];
map<ll,ll> mp;
ll ans;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) read(sum[i]);
    for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
    mp[0]=1;
    for(int i=1;i<=n;i++)
    {
        if(i>=k) mp[(sum[i-k]-(i-k))%k]--;
        ans+=mp[(sum[i]-i)%k];
        mp[(sum[i]-i)%k]++;
    }
    cout<<ans<<endl;
    return 0;
}

F. Sugoroku

题意简述:

给定一个从$0$到$n$的长为$n+1$的$01$序列 保证开头和结尾都是$0$每次最多向前进$m$个 而且只能走到为$0$的点 问能不能从开头走到结尾 假如能那么最少需要几次操作 并输出最小字典序的操作序列

题解:

这道题我看了几个题解好像都是dp?其实的话直接贪心即可 首先显然的结论假如有大于等于$m$个连续的1那么一定走不到 否则一定可以走到 因为它不连续 所以我总归可以至少跳到它前一个然后跳出去 之后我们考虑最少步数 直接贪心 每次先走$m$步 假如是1再往前退 这里为什么直接贪心不用dp呢 因为是不存在我前面比它跳的近后面又反超的情况的 因为跳的近的所能转移到的状态跳的远同样可以转移而且步数一定不会更坏 这里可以画图感受一下 然后由于保证字典序最小 所以自然倒序处理一波即可 剩下就是一些小细节了

AC代码:

int n,m;
string s;
vector<int> ans;
int main()
{
    cin>>n>>m;
    cin>>s;
    int temp=0,flag=1;
    for(int i=0;i<=n;i++)
    {
        if(s[i]=='1')
        {
            temp++;
            if(temp>=m) 
            {
                flag=0;
            }
        }
        else temp=0;
    }
    if(!flag) puts("-1");
    else
    {
        int temp=n;
        while(temp)
        {
            if(s[max(temp-m,0)]=='0') ans.push_back(min(m,temp)),temp=max(temp-m,0);
            else
            {
                int t=m;
                while(s[temp-t]!='0') t--;
                temp=temp-t;
                ans.push_back(t);
            }
        }
        for(int i=ans.size()-1;i>=0;i--) cout<<ans[i]<<" ";
        puts("");
    }
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
CF Good Bye 2019 题解 CF Good Bye 2019 题解
时隔许久的题解,A到D题,感觉全是构造题啊) A. Card Game题意简述:有两个人玩游戏,第一个人有$k1$张牌,第二个人有$k2$张牌,一共有$n$张牌且牌值从$1$到$n$,每一次两人分别抽出一张牌,谁的牌大就拿走这两张牌,最后
下一篇 
CF1255C League of Leesins CF1255C League of Leesins
题意简述:给定一个长度为$n$的排列 并将连续的三个作为一组 如$[1,2,3,4,5]$就有三组$[1,2,3],[2,3,4],[2,4,5]$现在我们可以把每组内的数顺序交换 也可以把组交换 现在给出$n-2$个经过交换后的组 让你求
2019-11-26
  目录