[Codeforces]Round 653 Div3 补题
本文最后更新于 64 天前,其中的信息可能已经有所发展或是发生改变。

前言

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接:https://www.codein.icu/cfround653/

概述

赛后一天补题,虚拟参赛,2h只写完了前四题,E1没调出来,结束后看数据才调好。
整体难度不大,不少靠猜结论,E2实现有点麻烦。

CF1374A Required Remainder

求 $\max k \in [0,n],k \equiv y \pmod{x}$,多组数据。

即:$k = i \times x + y$,要求 $i$ 最大。不考虑 $y$ 时,$\max i = \left \lfloor \dfrac{n}{x} \right \rfloor$,代回计算,可以依次减 $x$ ,满足 $k \leq n$ 时即为答案。

其中 $y < x$,因此当 $\left \lfloor \dfrac{n}{x} \right \rfloor \times x + y > n$ 时,$(\left \lfloor \dfrac{n}{x} \right \rfloor – 1) \times x + y< n$ 一定成立。

#include <cstdio>
template<typename T>
void read(T &r)
{
    static char c;r=0;
    for(c=getchar();c>'9'||c<'0';c=getchar());
    for(;c>='0'&&c<='9';r=(r<<1)+(r<<3)+(c^48),c=getchar());
}
int T;
long long x,y,n;
int main()
{
    read(T);
    while(T--)
    {
        read(x),read(y),read(n);
        long long p = (n / x) * x + y;
        if(p > n) p -= x;
        printf("%lld\n",p);
    }
    return 0;
}

CF1374B Multiply by 2, divide by 6

给定 $n$,可以 $\div 6$ 或 $\times 2$,问几步后可得到 $1$。

顺序不会影响答案,若答案存在,则 $n \div 6^a \times 2^b = 1$,求 $a + b$。

化简为 $n \div 6^{a-b} \div 3^b = 1$,$\times 2 \div 6 = \div 3$ 计算两步贡献,直接统计。

#include <cstdio>
template<typename T>
void read(T &r)
{
    static char c;r=0;
    for(c=getchar();c>'9'||c<'0';c=getchar());
    for(;c>='0'&&c<='9';r=(r<<1)+(r<<3)+(c^48),c=getchar());
}
int T;
long long x;
int main()
{
    read(T);
    while(T--)
    {
        read(x);
        long long ans = 0;
        while(x % 6 == 0) ++ans, x /= 6;
        while(x % 3 == 0) ans += 2,x /= 3;
        if(x == 1) printf("%lld\n",ans);
        else puts("-1");
    }
    return 0;
}

CF1374C Move Brackets

给一个括号序列,每次可将任意括号移至首尾,求最少步数后括号串合法。

将左括号看做 $1$,右括号看做 $-1$,要求任意位置前缀和非负,即括号匹配。数据保证有解。

途中某位置前缀和为 $-1$ 时,将当前右括号移至末尾,统计答案,再将前缀和归零。

大致证明:

当前串设为 $s_1 + ) + s_2$,其中 $s_1$ 有 $a$ 个左括号,$a$ 个右括号,那么 $s_2$ 中有 $n – 2 \times a – 1$ 个括号,其中 $(n – 2 \times a) \div 2$ 是左括号,$(n – 2 \times a) \div 2 – 1$ 是右括号,将该右括号移至末尾一定能与某左括号匹配。

数据范围比较仁慈,把 $O(n^2)$ 做法放过去了,实际上无须真的移到末尾。

#include <cstdio>
const int maxn = 60;
int T,n;
char s[maxn];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %s",&n,s+1);
        int ans = 0,sum = 0;
        for(int i = 1;i<=n;++i)
        {
            sum += (s[i] == '(' ? 1 : -1);
            if(sum < 0) ++ans,sum = 0;
        }
        printf("%d\n",ans);
    }
    return 0;
}

CF1374D Zero Remainder Array

初始 $x = 0$,每次操作后 $+1$,两种操作:

  1. $a_i += x$
  2. 什么都不干

操作1对每个数最多进行一次。
求 $\forall a_i \equiv 0 \pmod{k}$ 的最小步数。
将所有数模 $k$ 处理,对于 $a_i$,$x = k – a_i$ 是唯一操作方法。
进行操作与什么都不干等代价,则能使 $a_i += x$ 时一定会进行操作。
由于 $x$ 单调递增,每次找到最小的 $x \leq a_i$,再进行计算转移,一定是最优的。
可以用set来处理。

#include <cstdio>
#include <set>
template<typename T>
void read(T &r)
{
    static char c;r=0;
    for(c=getchar();c>'9'||c<'0';c=getchar());
    for(;c>='0'&&c<='9';r=(r<<1)+(r<<3)+(c^48),c=getchar());
}
#define int long long
const int maxn = 2e5 + 100;
int T,n,k,a[maxn];
std::multiset<int> s;
signed main()
{
    read(T);
    while(T--)
    {
        s.clear();
        read(n),read(k);
        for(int i = 1;i<=n;++i) read(a[i]),a[i] = k - (a[i] % k);
        for(int i = 1;i<=n;++i) if(a[i] != k) s.insert(a[i]);
        int ans = 0,x = 0;
        while(!s.empty())
        {
            std::set<int>::iterator it = s.lower_bound(x);
            if(it == s.end())  ans += k - x,x = 0;//找不到则归零
            else ans += *it - x + 1,x = (*it) + 1,s.erase(it);
            x %= k;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

CF1374E1 Reading Books (easy version)

每本书都有权值,每本书可能被 A 喜欢,可能被 B 喜欢,要求选出的书中,A 与 B 都至少喜欢 $k$ 本,求最小权值和。
可以给书分类:

  1. A 与 B 都不喜欢
  2. A 喜欢
  3. B 喜欢
  4. A 与 B 都喜欢

不难发现,二人都不喜欢的书是完全无效的。
给每类书排序,做一遍前缀和。
设选 $i$ 本 A 与 B 都喜欢的书,就要选 $k – i$ 本 A 喜欢的书, $k – i$ 本 B 喜欢的书。
枚举 $i$ 求最小答案。

#include <cstdio>
#include <algorithm>
template<typename T>
void read(T &r)
{
    static char c;r=0;
    for(c=getchar();c>'9'||c<'0';c=getchar());
    for(;c>='0'&&c<='9';r=(r<<1)+(r<<3)+(c^48),c=getchar());
}
const int maxn = 2e6 + 100;
int n,k;
int A[maxn],B[maxn],C[maxn],acnt,bcnt,ccnt;
long long SA[maxn],SB[maxn],SC[maxn];
int main()
{
    read(n),read(k);
    for(int i = 1;i<=n;++i)
    {
        int t,a,b;
        read(t),read(a),read(b);
        if(a && b) C[++ccnt] = t;
        else if(a) A[++acnt] = t;
        else if(b) B[++bcnt] = t;
    }
    std::sort(A + 1,A + 1 + acnt);
    std::sort(B + 1,B + 1 + bcnt);
    std::sort(C + 1,C + 1 + ccnt);
    for(int i = 1;i<=acnt;++i) SA[i] = SA[i-1] + A[i];
    for(int i = 1;i<=bcnt;++i) SB[i] = SB[i-1] + B[i];
    for(int i = 1;i<=ccnt;++i) SC[i] = SC[i-1] + C[i];
    long long ans = 1ll << 60;
    for (int i = std::max(0,k - std::min(acnt, bcnt)); i <= ccnt && i <= k; ++i) 
        ans = std::min(ans, SA[k - i] + SB[k - i] + SC[i]);
    if (ans == 1ll << 60) puts("-1");
    else printf("%lld",ans);
    return 0;
}

总结

笔者只会做水题了。E2的题解会单独发。

本文标题:[Codeforces]Round 653 Div3 补题
本文作者:Clouder
本文链接: https://www.codein.icu/cfround653/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇